Basic Spanning Tree

From OpenFlow Wiki

A basic spanning tree module is currently maintained by Glen Gibb (grg@stanford.edu). The module attempts to build a spanning tree within an OpenFlow network. It does not interact with standard spanning tree protocols such as STP, MSTP, RSTP, PVST or R-PVST.

Warning: The current version of the module will not work in networks in which a single port on one switch connects to multiple switches.

Contents 1 Overview of processing performed by the module 2 Installation 3 Usage 3.1 Basic usage 3.2 Interaction with other modules 3.3 Useful spanning tree functions 4 Enhancements/bug fixes/documentation updates

Overview of processing performed by the module

The spanning tree module operates in a network as follows:

• When a new switch connects to NOX, the module:
  • sets the NO_FLOOD bit on every port of the switch. This prevents packets being sent out the ports when the action is OFPP_FLOOD.
  • records the connect time and prevents the NO_FLOOD bit from being cleared until a preset period (FLOOD_WAIT_TIME) has elapsed.
• Periodically, the module queries bindings_storage for a list of all links. The module uses the list of all links to build a spanning tree. The spanning tree is built as follows:
  1. Place all switches in a candidate list and sort this list by DPID.
  2. Remove the first element from the candidate list (lowest DPID) and treat this switch as the root. Call this switch the current switch.
  3. All links from the current switch are examined to identify the destination switches they lead to. Links are enabled (added to the spanning tree) for which the destination switch has not been processed in this round and:
     • Only one link leads to the destination
     • Multiple links lead to the destination and this link is the fastest. If there are multiple fastest links then the lowest-numbered link is chosen.
  4. Move all destinations that were just added to the spanning tree to the head of the candidate list. Maintain sorted order amongst the elements that were just moved. (After one round the candidate list should appear as follows: [[sorted list of DPIDs reachable from the root via a single hop], [sorted list of DPIDs not reachable from the root via a single hop]].)
  5. If the candidate list is non-empty, take the next element from the candidate list and treat this switch as the current switch. Repeat from step 3.
• When a packet is received:
  • The module looks at the NO_FLOOD bit of the port to identify whether the port is in the spanning tree.
  • If the packet is received on a port in the spanning tree then the packet is passed on to the next module for processing.
  • If the packet is not received on a port in the spanning tree then the packet is only passed on to the next module if the location of the destination MAC or IP is known.

The spanning tree module utilizes the services the discovery module for neighbor link detection and the bindings_storage module for querying current link state.

Installation

1. Download version 0.5 of NOX from noxrepo if you don't already have it ([1])
2. Download the latest version of spanning tree: [2]
3. Change into the NOX netapps directory and uncompress the spanning tree implementation:

cd noxcore/src/nox/netapps
tar -xvzf <spanning_tree_tar_locn>/spanning_tree.101122.tgz

4. Change into the top-level NOX directory:

cd ../../..

5. Modify configure.ac.in. Find the section "ACI_PACKAGE([netapps]" and add spanning_tree to the list of modules. For example:

ACI_PACKAGE([netapps],[misc network apps],
              [configuration authenticator migration
              routing user_event_log storage tests topology discovery 
              directory bindings_storage switchstats flow_fetcher
              spanning_tree],
              [TURN_ON_NETAPPS])

6. Modify src/etc/nox.xml and add the line in bold below to beginning the Packet_in_event section:

   <event name="Packet_in_event">
     <filter>spanning_tree</filter>
     <filter>authenticator</filter>

7. Run the remainder of the NOX compilation process:

./boot.sh
mkdir build
cd build/
../configure –with-python=yes
make

Usage

Basic usage

To use the spanning tree module, add spanning_tree to the list of modules on the NOX command line.

Interaction with other modules

By default the spanning tree module knows nothing about other modules. Correct operation may require minor modification of other modules as outlined here.

For the purposes of illustration, assume that we have the network outlined below. In this network Sw_A, Sw_B and Sw_C are OpenFlow switches and H1 and H2 are hosts.

             Sw_A
            /    \
           /      \
          /        \
H1 ---- Sw_B ---- Sw_C ---- H2

Assume that spanning tree for this network disables the link between Sw_B and Sw_C:

             Sw_A
            /    \
           /      \
          /        \
H1 ---- Sw_B      Sw_C ---- H2

A controller might install a flow between H1 and H2 that goes H1 -> Sw_B -> Sw_C -> H2. The spanning tree module does not, and should not, prevent a flow like this from being installed -- OpenFlow should allow use of links like this that are not on the spanning tree.

Complexity arises in this example if the flow table entry in Sw_C is deleted for this flow. In this instance the packets from H1 to H2 arrive as Sw_C on a port not in the spanning tree. The spanning tree receives the packet in message before any other modules and would drop the packet since the input port is not in the spanning tree. To prevent these packets from being dropped if they arrive at the controller a module may call the add_ip_bypass or add_mac_bypass functions. These functions instruct the spanning tree module not to drop packets destined to the corresponding MAC or IP.

Useful spanning tree functions

The following functions are defined in the spanning tree module and may be called by other modules:

add_ip_bypass 

Any packets destined to the corresponding IP address will not be dropped even if received on a port not in the spanning tree

del_ip_bypass 

Remove the bypass for the corresponding IP address

add_mac_bypass 

Any packets destined to the corresponding MAC address will not be dropped even if received on a port not in the spanning tree

del_mac_bypass 

Remove the bypass for the corresponding MAC address

reset_bypass 

Reset all bypasses

get_roots 

What are the root switches in the network? (Multiple switches are returned if the network is partitioned.)

Enhancements/bug fixes/documentation updates

Please send bug fixes and enhancements to the code to Glen Gibb. Bug fixes/enhancements should be submitted in the form of diffs produced using diff -u:

diff -u spanning_tree.py.orig spanning_tree.py

Please make documentation updates directly to this Wiki page.