I discovered a topology that broke my previous implementation. An
updated implementation is attached.
Glen
Glen Gibb wrote:
Hi all,
I've implemented basic spanning tree support for NOX as a Python app.
I've attached my implementation as a diff. This requires the
send_port_mod patch that I sent to the list earlier to use. I suspect
the patch to configure.ac may not apply cleanly as my patch has
reference to two apps that we've added locally.
A couple of notes about my implementation:
* This is *not* an implementation of IEEE 802.1D Spanning Tree
Protocol and is *not* compatible.
* The app uses the information gathered by the discovery module to
identify links and construct the spanning tree.
* I have made no attempt to optimize the algorithm that builds the
spanning tree. It works well for a small number of switches -- I
haven't tested in large topologies.
* When a switch connects the app disables flooding to all ports
initially.
* Ports are only eligible for flooding after a waiting period. This
waiting period is currently a fixed period but should probably
adjust dynamically depending upon the number of ports in the
system. (Look at discovery to understand why it should adjust
dynamically with the number of ports.)
* The switch with the lowest DPID will always be the root in any tree.
* This implementation doesn't properly handle the case where one
port is connected to multiple switches.
* The app listens for packet in events to enable it to drop packets
received on non-flood ports. It must be the first app that
receives packet ins to allow it to return STOP before any other
event can process the packet.
I should point out that so far it has received relatively little
testing. I've only run it in a topology with 3 switches connected in a
triangle.
Again, let me know if you have comments/questions.
Glen
------------------------------------------------------------------------
_______________________________________________
nox-dev mailing list
nox-dev@noxrepo.org
http://noxrepo.org/mailman/listinfo/nox-dev_noxrepo.org
diff --git a/configure.ac b/configure.ac
index 4c6813b..825cc40 100644
--- a/configure.ac
+++ b/configure.ac
@@ -96,6 +96,8 @@ ACI_MODULE([examples],[Set of example apps],
[],[],[yes])
ACI_MODULE([mobilevms],[MobileVMs app for VM mobility],
[],[],[yes])
+ACI_MODULE([spanning_tree],[Basic spanning tree support],
+ [],[],[yes])
ACI_MODULE([throughput],[Monitor link throughputs],
[],[],[yes])
ACI_MODULE([hub],[dumb hub],
@@ -117,6 +119,7 @@ ACI_MODULE([apps],[main source libarary],
sepl storage tests topology discovery coreui
simple_c_app simple_c_py_app noop hub switch
examples exit directory
+ spanning_tree
bindings_storage switchstats mobilevms throughput],
[yes])
ACI_MODULES_VERIFY
@@ -226,6 +229,7 @@ src/nox/apps/hub/Makefile
src/nox/apps/examples/Makefile
src/nox/apps/exit/Makefile
src/nox/apps/mobilevms/Makefile
+src/nox/apps/spanning_tree/Makefile
src/nox/apps/throughput/Makefile
])
AC_OUTPUT
diff --git a/src/nox/apps/spanning_tree/Makefile.am b/src/nox/apps/spanning_tree/Makefile.am
new file mode 100644
index 0000000..d2271c6
--- /dev/null
+++ b/src/nox/apps/spanning_tree/Makefile.am
@@ -0,0 +1,17 @@
+include ../../../Make.vars
+
+EXTRA_DIST =\
+ meta.xml\
+ __init__.py \
+ spanning_tree.py
+
+NOX_RUNTIMEFILES = meta.xml \
+ __init__.py \
+ spanning_tree.py
+
+all-local:
+ @dlist="$(NOX_RUNTIMEFILES)";for f in $$dlist; do \
+ if test -f $(srcdir)/$$f && test ! -f $$f; then \
+ ln -sf $(srcdir)/$$f $(builddir)/$$f;\
+ fi;\
+ done;
diff --git a/src/nox/apps/spanning_tree/__init__.py b/src/nox/apps/spanning_tree/__init__.py
new file mode 100644
index 0000000..e69de29
diff --git a/src/nox/apps/spanning_tree/meta.xml b/src/nox/apps/spanning_tree/meta.xml
new file mode 100644
index 0000000..2c6fd15
--- /dev/null
+++ b/src/nox/apps/spanning_tree/meta.xml
@@ -0,0 +1,13 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<components:components xmlns:components="http://www.noxrepo.org/components.xsd";>
+ <component>
+ <name>spanning_tree</name>
+ <dependency>
+ <name>python</name>
+ </dependency>
+ <dependency>
+ <name>discovery</name>
+ </dependency>
+ <python>nox.apps.spanning_tree.spanning_tree</python>
+ </component>
+</components:components>
diff --git a/src/nox/apps/spanning_tree/spanning_tree.py b/src/nox/apps/spanning_tree/spanning_tree.py
new file mode 100644
index 0000000..4cdf03b
--- /dev/null
+++ b/src/nox/apps/spanning_tree/spanning_tree.py
@@ -0,0 +1,307 @@
+# ----------------------------------------------------------------------
+# Spanning tree -- software based
+# Authors: Glen Gibb <[EMAIL PROTECTED]>
+# Date: 08/08/08
+#
+# Changes:
+#
+# Notes: This won't work correctly if there are more than 2 switches on
+# any one "link". ie. if we were on a broadcast network or there was an
+# extra switch in the middle
+# ----------------------------------------------------------------------
+
+import array
+import struct
+import time
+from nox.apps.pyrt.pycomponent import CONTINUE, STOP
+from nox.apps.bindings_storage.pybindings_storage import pybindings_storage
+from nox.lib.core import *
+from nox.lib.util import *
+from nox.lib.packet.packet_utils import longlong_to_octstr
+from nox.lib.packet.ethernet import ethernet, ETHER_ANY, ETHER_BROADCAST
+import nox.lib.openflow as openflow
+from twisted.python import log
+
+# How often should we rebuild the flood ports?
+FLOOD_PORT_UPDATE_INTERVAL = 5
+
+# Hold time before allowing floods out a switch
+FLOOD_WAIT_TIME = 5
+
+class Spanning_Tree(Component):
+
+ def __init__(self, ctxt):
+ Component.__init__(self, ctxt)
+
+ self.datapaths = {}
+ self.debug = True
+
+ def getInterface(self):
+ return str(Spanning_Tree)
+
+ def debugPrint(self, text):
+ if (self.debug):
+ print(text)
+
+ def install(self):
+ # Register to learn about datapath join and leave events
+ self.register_for_datapath_join ( self.dp_join )
+ self.register_for_datapath_leave( self.dp_leave )
+ self.register_for_port_status( self.handle_port_status )
+ self.register_for_packet_in( self.handle_packet_in)
+
+ self.bindings = self.resolve(pybindings_storage)
+
+ self.post_callback(1, self.update_spanning_tree)
+ self.debugPrint("Spanning tree installed\n")
+
+ def dp_join(self, dp, stats):
+ self.debugPrint("Datapath join: "+longlong_to_octstr(dp)[6:])
+ if (not self.datapaths.has_key(dp)):
+ # Process the port information returned by the switch
+
+ # Build a list of ports
+ now = time.time()
+ ports = {}
+ for port in stats['ports']:
+ ports[port['port_no']] = port
+ if port['port_no'] <= openflow.OFPP_MAX:
+ port['join_time'] = now
+ port['flags'] |= openflow.OFPPFL_NO_FLOOD
+ self.ctxt.send_port_mod(dp, set_port(port))
+
+ # Record the datapath
+ self.datapaths[dp] = ports
+ return CONTINUE
+
+ def dp_leave(self, dp):
+
+ self.debugPrint("Datapath leave, "+longlong_to_octstr(dp)[6:])
+ if (self.datapaths.has_key(dp)):
+ del self.datapaths[dp]
+ return CONTINUE
+
+ def update_spanning_tree(self):
+ '''Get the links to update the spanning tree
+ '''
+ self.bindings.get_all_links(self.update_spanning_tree_callback)
+ self.post_callback(FLOOD_PORT_UPDATE_INTERVAL, self.update_spanning_tree)
+
+ def update_spanning_tree_callback(self, links):
+ '''Callback called by get_all_links to process the set of links.
+
+ Currently:
+ - updates the flood ports to build a spanning tree
+
+ Note: each link probably appears twice (once for each direction)
+
+ As a temporary hack to deal with the fact that we don't have
+ spanning tree support in NOX we build a set of "flood-ports". Each
+ datapath id representing a switch has a set of ports associated
+ which represent links that don't contain other OpenFlow
+ switches. This set of paths can be used safely for flooding to
+ ensure that we don't circulate broadcast packets.
+
+ @param links list link tuples (src_dpid, src_port, dst_dpid, dst_port)
+ '''
+ # Walk through the datapaths and mark all ports
+ # that are potentially enableable
+ now = time.time()
+ for dp in self.datapaths.iterkeys():
+ for port_no, port in self.datapaths[dp].iteritems():
+ if port_no > openflow.OFPP_MAX or now - port['join_time'] > FLOOD_WAIT_TIME:
+ port['enable'] = True
+ else:
+ port['enable'] = False
+ port['keep'] = False
+
+
+ # Walk through the links and create a dict based on source port
+ my_links = {}
+ for (src_dpid, src_port, dst_dpid, dst_port) in links:
+ # Sort ports if dpids are identical
+ if src_dpid == dst_dpid:
+ if src_port > dst_port:
+ (src_port, dst_port) = (dst_port, src_port)
+
+ # Track the link
+ try:
+ if self.datapaths[src_dpid][src_port]['enable'] and \
+ self.datapaths[dst_dpid][dst_port]['enable']:
+ if my_links.has_key(src_dpid):
+ if (my_links[src_dpid].has_key(dst_dpid)):
+ my_links[src_dpid][dst_dpid].add((src_port, dst_port))
+ else:
+ my_links[src_dpid][dst_dpid] = set()
+ my_links[src_dpid][dst_dpid].add((src_port, dst_port))
+ else:
+ my_links[src_dpid] = {dst_dpid:set()}
+ my_links[src_dpid][dst_dpid].add((src_port, dst_port))
+ except KeyError:
+ pass
+
+ # Now try to build the spanning tree
+ seen = set()
+ if len(my_links) > 0:
+ # Get all sources in reversed sorted order
+ srcs = my_links.keys()
+ srcs.sort()
+ srcs = srcs[::-1]
+
+ # Process all sources
+ while len(srcs) > 0:
+ src_dpid = srcs.pop()
+
+ # Walk through all dests
+ dsts = my_links[src_dpid].keys()
+ dsts.sort()
+ next_dpids = []
+ for dst_dpid in dsts:
+ # For links to the switch, disable one of the two ports
+ if src_dpid == dst_dpid:
+ for (src_port, dst_port) in my_links[src_dpid][dst_dpid]:
+ # Disable the second of the two ports
+ try:
+ self.datapaths[src_dpid][dst_port]['enable'] = False
+ except KeyError:
+ pass
+ # Process links to other switches
+ else:
+ # Unseen dpids
+ if dst_dpid not in seen:
+ # Attempt to find the fastest link to the other switch
+ best_speed = -1
+ best_pair = (-1, -1)
+ for (src_port, dst_port) in my_links[src_dpid][dst_dpid]:
+ try:
+ speed = self.datapaths[src_dpid][src_port]['speed']
+ if speed > best_speed:
+ best_speed = speed
+ best_pair = (src_port, dst_port)
+ except KeyError:
+ pass
+
+ # Disable all links but the fastest
+ for (src_port, dst_port) in my_links[src_dpid][dst_dpid]:
+ try:
+ if (src_port, dst_port) != best_pair:
+ self.datapaths[dst_dpid][dst_port]['enable'] = False
+ else:
+ self.datapaths[dst_dpid][dst_port]['keep'] = True
+ except KeyError:
+ pass
+
+ # Record that we've seen the dpid
+ seen.add(dst_dpid)
+ next_dpids.append(dst_dpid)
+
+ # Seen dpids
+ else:
+ # Disable all links in one direction only
+ if src_dpid > dst_dpid:
+ for (src_port, dst_port) in my_links[src_dpid][dst_dpid]:
+ # Disable the second of the two ports
+ try:
+ if not self.datapaths[src_dpid][src_port]['keep']:
+ self.datapaths[src_dpid][src_port]['enable'] = False
+ except KeyError:
+ pass
+
+ # Once we've processed all links from this source, update the
+ # list of sources so that the DPIDs we've just linked to will
+ # be processed next. This is achieved by placing them at the
+ # end of the list.
+ next_dpids = next_dpids[::-1]
+ for dpid in next_dpids:
+ try:
+ srcs.remove(dpid)
+ except ValueError:
+ pass
+ srcs.extend(next_dpids)
+
+ # Walk through links and enable/disable as appropriate
+ for dp in self.datapaths.iterkeys():
+ floodports = []
+ for port_no, port in self.datapaths[dp].iteritems():
+ if port_no <= openflow.OFPP_MAX:
+ enabled = (port['flags'] & openflow.OFPPFL_NO_FLOOD) == 0
+ if port['enable'] != enabled:
+ if enabled:
+ port['flags'] |= openflow.OFPPFL_NO_FLOOD
+ msg = 'Disabling'
+ else:
+ port['flags'] &= ~openflow.OFPPFL_NO_FLOOD
+ msg = 'Enabling'
+
+ self.debugPrint("%s port: %s--%d"%(msg, longlong_to_octstr(dp)[6:], port_no))
+ self.ctxt.send_port_mod(dp, set_port(port))
+
+ if (port['flags'] & openflow.OFPPFL_NO_FLOOD) == 0:
+ floodports.append(port_no)
+
+ self.debugPrint("Floodports for %s: %s"%(longlong_to_octstr(dp)[6:], floodports))
+
+ def handle_port_status(self, dpid, reason, port):
+ '''Port_status_event handler
+
+ Handles port stats events, such as adding and deleting ports
+
+ dpid - Datapath ID of port
+
+ reason - what event occured
+
+ port - port
+ '''
+ # Work out what sort of event we're processing
+ if reason == openflow.OFPPR_ADD:
+ if port['port_no'] <= openflow.OFPP_MAX:
+ port['join_time'] = time.time()
+ port['flags'] |= openflow.OFPPFL_NO_FLOOD
+ self.ctxt.send_port_mod(dp, set_port(port))
+ self.datapaths[dpid][port['port_no']] = port
+ elif reason == openflow.OFPPR_DELETE:
+ del self.datapaths[dpid][port['port_no']]
+
+ return CONTINUE
+
+ def handle_packet_in(self, dpid, inport, reason, len, bufid, packet):
+ '''Packet in callback function
+
+ Allow packets to be processed by other modules only if
+ the port is a flood port or it's an LLDP packet
+
+ dpid - DPID of switch
+
+ inport - inport port
+
+ reason -
+
+ len - length
+
+ bufid - buffer ID of packet
+
+ packet - received packet
+ '''
+
+ if not packet.parsed:
+ log.msg('Ignoring incomplete packet',system='spanning_tree')
+
+ # Allow LLDP messages to be processed
+ if packet.type == ethernet.LLDP_TYPE:
+ return CONTINUE
+
+ # Check if the port is a flood port
+ try:
+ if (self.datapaths[dpid][inport]['flags'] & openflow.OFPPFL_NO_FLOOD) == 0:
+ return CONTINUE
+ else:
+ return STOP
+ except KeyError:
+ return STOP
+
+def getFactory():
+ class Factory:
+ def instance(self, ctxt):
+ return Spanning_Tree(ctxt)
+
+ return Factory()
_______________________________________________
nox-dev mailing list
nox-dev@noxrepo.org
http://noxrepo.org/mailman/listinfo/nox-dev_noxrepo.org
