# Copyright 2012-2013 James McCauley## Licensed under the Apache License, Version 2.0 (the “License”);# you may not use this file except in compliance with the License.# You may obtain a copy of the License at:## http://www.apache.org/licenses/LICENSE-2.0## Unless required by applicable law or agreed to in writing, software# distributed under the License is distributed on an “AS IS” BASIS,# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.# See the License for the specific language governing permissions and# limitations under the License.”””A shortestpath forwarding application.Thisis a standalone L2 switch that learns ethernet addressesacross the entire network and picks short paths between them.You shouldnt really write an application this way — you shouldkeep more state in the controller (that is, your flow tables),and/or you should make your topology more static. However, thisdoes (mostly) work. :)Depends on openflow.discoveryWorks with openflow.spanning_tree“””from pox.core import coreimport pox.openflow.libopenflow_01 as offrom pox.lib.revent import *from pox.lib.recoco import Timerfrom collections import defaultdictfrom pox.openflow.discovery import Discoveryfrom pox.lib.util import dpid_to_strimport timelog = core.getLogger()# Adjacency map. [sw1][sw2] -> port from sw1 to sw2adjacency = defaultdict(lambda:defaultdict(lambda:None))# Switches we know of. [dpid] -> Switchswitches = {}# ethaddr -> (switch, port)mac_map = {}# [sw1][sw2] -> (distance, intermediate)path_map = defaultdict(lambda:defaultdict(lambda:(None,None)))# Waiting path. (dpid,xid)->WaitingPathwaiting_paths = {}# Time to not flood in secondsFLOOD_HOLDDOWN = 5# Flow timeoutsFLOW_IDLE_TIMEOUT = 10FLOW_HARD_TIMEOUT = 30# How long is allowable to set up a path?PATH_SETUP_TIME = 4def _calc_paths (): “”” Essentially Floyd-Warshall algorithm “”” def dump (): for i in sws: for j in sws: a = path_map[i][j][0] #a = adjacency[i][j]if a is None: a = “*” print a, print sws = switches.values() path_map.clear() for k in sws: for j,port in adjacency[k].iteritems(): if port is None: continuepath_map[k][j] = (1,None) path_map[k][k] = (0,None) # distance, intermediate #dump() for k in sws: for i in sws: for j in sws: if path_map[i][k][0] is not None:if path_map[k][j][0] is not None: # i -> k -> j exists ikj_dist = path_map[i][k][0]+path_map[k][j][0]if path_map[i][j][0] is None or ikj_dist < path_map[i][j][0]: # i -> k -> j is better than existing path_map[i][j] = (ikj_dist, k) #print “——————–“ #dump()def _get_raw_path (src, dst): “””Get a raw path (just a list of nodes to traverse) “”” if len(path_map) == 0: _calc_paths() if src is dst: # Were here!return[]if path_map[src][dst][0]isNone:returnNone intermediate = path_map[src][dst][1]if intermediate isNone:# Directly connectedreturn[]return _get_raw_path(src, intermediate)+[intermediate]+ \_get_raw_path(intermediate, dst)def _check_path (p):“”” Make sure that a path is actually a string of nodes with connected ports returns True if path is valid “””for a,bin zip(p[:-1],p[1:]):if adjacency[a[0]][b[0]]!= a[2]:returnFalseif adjacency[b[0]][a[0]]!= b[1]:returnFalsereturnTruedef _get_path (src, dst, first_port,final_port):“”” Gets a cooked path — a list of (node,in_port,out_port) “””# Start with a raw path…if src == dst: path =[src]else: path = _get_raw_path(src, dst)ifpathisNone:returnNone path =[src]+ path +[dst]# Now add the ports r =[] in_port = first_portfor s1,s2 in zip(path[:-1],path[1:]): out_port = adjacency[s1][s2] r.append((s1,in_port,out_port)) in_port = adjacency[s2][s1] r.append((dst,in_port,final_port))assert _check_path(r),“Illegal path!”return rclass WaitingPath(object):“”” A path which is waiting for its path to be established “””def __init__ (self, path, packet):“”” xids is a sequence of (dpid,xid)first_switch is the DPID where the packet came from packet is something that can be sent in a packet_out “””self.expires_at = time.time()+ PATH_SETUP_TIMEself.path = pathself.first_switch= path[0][0].dpidself.xids =set()self.packet = packet if len(waiting_paths)>1000:WaitingPath.expire_waiting_paths()def add_xid (self, dpid, xid):self.xids.add((dpid,xid)) waiting_paths[(dpid,xid)]=self@propertydef is_expired (self):return time.time()>=self.expires_at def notify (self,event):“””Called when a barrier has been received “””self.xids.discard((event.dpid,event.xid))if len(self.xids)==0:# Done!ifself.packet: log.debug(“Sending delayed packet out %s”%(dpid_to_str(self.first_switch),)) msg = of.ofp_packet_out(data=self.packet, action=of.ofp_action_output(port=of.OFPP_TABLE)) core.openflow.sendToDPID(self.first_switch, msg) core.l2_multi.raiseEvent(PathInstalled(self.path))@staticmethoddef expire_waiting_paths (): packets =set(waiting_paths.values()) killed =0for p in packets:if p.is_expired: killed +=1for entry in p.xids: waiting_paths.pop(entry,None)if killed: log.error(“%i paths failed to install”%(killed,))classPathInstalled(Event):“”” Fired when a path is installed “””def __init__ (self, path):Event.__init__(self)self.path = pathclass Switch(EventMixin):def __init__ (self):self.connection =Noneself.ports =Noneself.dpid =Noneself._listeners =Noneself._connected_at =Nonedef __repr__ (self):return dpid_to_str(self.dpid)def_install(self,switch, in_port, out_port, match, buf =None): msg = of.ofp_flow_mod() msg.match = match msg.match.in_port = in_port msg.idle_timeout = FLOW_IDLE_TIMEOUT msg.hard_timeout= FLOW_HARD_TIMEOUT msg.actions.append(of.ofp_action_output(port = out_port)) msg.buffer_id = bufswitch.connection.send(msg)def _install_path (self, p,match, packet_in=None): wp =WaitingPath(p, packet_in)for sw,in_port,out_port in p:self._install(sw, in_port, out_port, match) msg = of.ofp_barrier_request() sw.connection.send(msg) wp.add_xid(sw.dpid,msg.xid)def install_path (self, dst_sw, last_port, match,event):“””Attempts to install a path between this switch and some destination “”” p = _get_path(self, dst_sw,event.port, last_port)if p isNone: log.warning(“Cant get from %s to %s”, match.dl_src, match.dl_dst)import pox.lib.packetas pkt if(match.dl_type == pkt.ethernet.IP_TYPE andevent.parsed.find(ipv4)):# Its IP — lets send a destination unreachable log.debug(“Dest unreachable (%s -> %s)”, match.dl_src, match.dl_dst)from pox.lib.addresses importEthAddr e = pkt.ethernet() e.src =EthAddr(dpid_to_str(self.dpid))#FIXME: Hmm… e.dst = match.dl_src e.type = e.IP_TYPE ipp = pkt.ipv4() ipp.protocol = ipp.ICMP_PROTOCOL ipp.srcip = match.nw_dst #FIXME: Ridiculous ipp.dstip = match.nw_src icmp = pkt.icmp() icmp.type= pkt.ICMP.TYPE_DEST_UNREACH icmp.code = pkt.ICMP.CODE_UNREACH_HOST orig_ip =event.parsed.find(ipv4) d = orig_ip.pack() d = d[:orig_ip.hl *4+8]importstruct d =struct.pack(“!HH”,0,0)+ d #FIXME: MTU icmp.payload = d ipp.payload = icmp e.payload = ipp msg = of.ofp_packet_out() msg.actions.append(of.ofp_action_output(port =event.port)) msg.data = e.pack()self.connection.send(msg)return log.debug(“Installing path for %s -> %s %04x (%i hops)”, match.dl_src, match.dl_dst, match.dl_type,len(p))# We have a path — install itself._install_path(p, match,event.ofp)# Now reverse it and install it backwards# (well just assume that will work) p =[(sw,out_port,in_port)for sw,in_port,out_port in p]self._install_path(p, match.flip())def _handle_PacketIn (self,event):def flood ():“”” Floods the packet “””ifself.is_holding_down: log.warning(“Not flooding — holddown active”) msg = of.ofp_packet_out()# OFPP_FLOOD is optional; some switches may need OFPP_ALLmsg.actions.append(of.ofp_action_output(port = of.OFPP_FLOOD)) msg.buffer_id =event.ofp.buffer_id msg.in_port =event.portself.connection.send(msg)def drop ():# Kill the bufferifevent.ofp.buffer_id isnotNone: msg = of.ofp_packet_out() msg.buffer_id =event.ofp.buffer_idevent.ofp.buffer_id =None# Mark is dead msg.in_port=event.portself.connection.send(msg) packet =event.parsed loc =(self,event.port)# Place we saw this ethaddr oldloc = mac_map.get(packet.src)# Place we last saw this ethaddr if packet.effective_ethertype == packet.LLDP_TYPE: drop()returnif oldloc isNone:if packet.src.is_multicast ==False: mac_map[packet.src]=loc# Learn position for ethaddr log.debug(“Learned %s at %s.%i”, packet.src, loc[0], loc[1])elif oldloc != loc:# ethaddr seen at different place!if core.openflow_discovery.is_edge_port(loc[0].dpid, loc[1]):# New place is another “plain” port (probably) log.debug(“%s moved from %s.%i to %s.%i?”, packet.src,dpid_to_str(oldloc[0].dpid), oldloc[1], dpid_to_str( loc[0].dpid), loc[1])if packet.src.is_multicast ==False: mac_map[packet.src]= loc # Learn position for ethaddrlog.debug(“Learned %s at %s.%i”, packet.src, loc[0], loc[1])elif packet.dst.is_multicast ==False:# New place is a switch-to-switch port!# Hopefully, this is a packet were flooding because we didnt# know the destination, and not because its somehow not on a# path that we expect it to be on.# If spanning_tree is running, we might check that this port is# on the spanning tree (it should be).if packet.dst in mac_map:# Unfortunately, we know the destination. Its possible that# we learned it while it was in flight, but its also possible# that something has gone wrong. log.warning(“Packet from %s to known destination %s arrived ““at %s.%i without flow”, packet.src, packet.dst, dpid_to_str(self.dpid),event.port)if packet.dst.is_multicast: log.debug(“Flood multicast from %s”, packet.src) flood()else:if packet.dst notin mac_map: log.debug(“%s unknown — flooding”%(packet.dst,)) flood()else: dest = mac_map[packet.dst]match= of.ofp_match.from_packet(packet)self.install_path(dest[0], dest[1], match,event)def disconnect (self):ifself.connection isnotNone: log.debug(“Disconnect %s”%(self.connection,))self.connection.removeListeners(self._listeners)self.connection =Noneself._listeners =Nonedef connect (self, connection):ifself.dpid isNone:self.dpid = connection.dpidassertself.dpid == connection.dpidifself.ports isNone:self.ports = connection.features.portsself.disconnect() log.debug(“Connect %s”%(connection,))self.connection = connectionself._listeners =self.listenTo(connection)self._connected_at = time.time()@propertydef is_holding_down (self):ifself._connected_at isNone:returnTrueif time.time()self._connected_at > FLOOD_HOLDDOWN:returnFalsereturnTruedef _handle_ConnectionDown (self,event):self.disconnect()class l2_multi (EventMixin): _eventMixin_events =set([PathInstalled,])def __init__ (self):# Listen to dependenciesdef startup (): core.openflow.addListeners(self, priority=0) core.openflow_discovery.addListeners(self) core.call_when_ready(startup,(openflow,openflow_discovery))def _handle_LinkEvent (self,event):def flip (link):returnDiscovery.Link(link[2],link[3], link[0],link[1]) l =event.link sw1 = switches[l.dpid1] sw2 = switches[l.dpid2]# Invalidate all flows and path info.# For link adds, this makes sure that if a new link leads to an# improved path, we use it.# For link removals, this makes sure that we dont use a# path that may have been broken.#NOTE: This could be radically improved! (e.g., not *ALL* paths break) clear = of.ofp_flow_mod(command=of.OFPFC_DELETE)for sw in switches.itervalues():if sw.connection isNone:continue sw.connection.send(clear) path_map.clear()ifevent.removed:# This link no longer okayif sw2 in adjacency[sw1]:del adjacency[sw1][sw2]if sw1 in adjacency[sw2]:del adjacency[sw2][sw1]# But maybe theres another way to connect these…for ll in core.openflow_discovery.adjacency:if ll.dpid1 == l.dpid1 and ll.dpid2 == l.dpid2:if flip(ll)in core.openflow_discovery.adjacency:# Yup, link goes both waysadjacency[sw1][sw2]= ll.port1 adjacency[sw2][sw1]= ll.port2# Fixed — new link chosen to connect thesebreakelse:# If we already consider these nodes connected, we can# ignore this link up.# Otherwise, we might be interested…if adjacency[sw1][sw2]isNone:# These previously werent connected. If the link# exists in both directions, we consider them connected now.if flip(l)in core.openflow_discovery.adjacency:# Yup, link goes both ways — connected! adjacency[sw1][sw2]= l.port1 adjacency[sw2][sw1]= l.port2 # If we have learned a MAC on this port which we now know to# be connected to a switch, unlearn it.bad_macs=set()for mac,(sw,port)in mac_map.iteritems():if sw is sw1 and port == l.port1: bad_macs.add(mac)if sw is sw2 and port == l.port2: bad_macs.add(mac)for mac in bad_macs:log.debug(“Unlearned %s”, mac)del mac_map[mac]def _handle_ConnectionUp (self,event): sw = switches.get(event.dpid)if sw isNone:# New switch sw =Switch() switches[event.dpid]= sw sw.connect(event.connection)else: sw.connect(event.connection)def _handle_BarrierIn (self,event): wp = waiting_paths.pop((event.dpid,event.xid),None)ifnot wp:#log.info(“No waiting packet %s,%s”, event.dpid, event.xid)return#log.debug(“Notify waiting packet %s,%s”, event.dpid, event.xid) wp.notify(event)def launch (): core.registerNew(l2_multi) timeout = min(max(PATH_SETUP_TIME,5)*2,15)Timer(timeout,WaitingPath.expire_waiting_paths, recurring=True)

可以看到,通过Floyd算法计算两个终端之间的最短路径。

发表回复

您的电子邮箱地址不会被公开。