Learning POX OpenFlow controller : Global Forwarding Database

The application name is l2_multi.py.
This module works in a reactive mode. It is dependant on discovery module and can work with spanning_tree module in the topology with loops.

The idea behind this module is to have a forwarding database for a whole topology, i.e. several connected switches. A shortest path is calculated between each and every switch and OpenFlow rules matching each observed flow are installed to switches along aforementioned path.

Rules in OVS, retrieved using sudo ovs-ofctl dump-flows s1 command, will look the folllowing way.

 cookie=0x0, duration=6.681s, table=0, n_packets=0, n_bytes=0, idle_timeout=10, hard_timeout=30, idle_age=6, priority=65535,arp,in_port=1,vlan_tci=0x0000,dl_src=1e:58:08:9b:8d:8f,dl_dst=2a:12:2e:f9:fe:63,arp_spa=10.0.0.1,arp_tpa=10.0.0.2,arp_op=2 actions=output:2
 cookie=0x0, duration=6.771s, table=0, n_packets=1, n_bytes=42, idle_timeout=10, hard_timeout=30, idle_age=6, priority=65535,arp,in_port=1,vlan_tci=0x0000,dl_src=1e:58:08:9b:8d:8f,dl_dst=2a:12:2e:f9:fe:63,arp_spa=10.0.0.1,arp_tpa=10.0.0.2,arp_op=1 actions=output:2
 cookie=0x0, duration=6.721s, table=0, n_packets=1, n_bytes=42, idle_timeout=10, hard_timeout=30, idle_age=6, priority=65535,arp,in_port=2,vlan_tci=0x0000,dl_src=2a:12:2e:f9:fe:63,dl_dst=1e:58:08:9b:8d:8f,arp_spa=10.0.0.2,arp_tpa=10.0.0.1,arp_op=2 actions=output:1
 cookie=0x0, duration=6.768s, table=0, n_packets=0, n_bytes=0, idle_timeout=10, hard_timeout=30, idle_age=6, priority=65535,arp,in_port=2,vlan_tci=0x0000,dl_src=2a:12:2e:f9:fe:63,dl_dst=1e:58:08:9b:8d:8f,arp_spa=10.0.0.2,arp_tpa=10.0.0.1,arp_op=1 actions=output:1

There are two flows of ARP requests and replies that result in four rules for two directions.

Several classes are created to encapsulate logic required for thsi module:

• l2_multi – the main entity responsible for handling events coming from openflow library, i.e. ConnectionUp, BarrierIn and discovery module, i.e. LinkEvent
• Switch – represents a physical switch and contains logic to handle PacketIn events and installing forwarding rules
• WaitingPath is a cache of packets that are waiting on its path to be installed
• PathInstalled is an event, fired once the rules are installed to all the switches along the shortest path enabling traffic with a particular destination MAC to traverse the topology according to previously calculated path

Once a packet is received by a controller, its “location”, namely switch and originating port, is saved to a map named mac_map and source MAC address is used as a key.

In case if aforementioned map already contains “location” for destination MAC, the shortest path is installed, meaning all switches between originating switch and destination switch are appropriately programmed with rules to forward packets that have the same headers along one shortest path.

dest = mac_map[packet.dst]
match = of.ofp_match.from_packet(packet)
self.install_path(dest[0], dest[1], match, event)

Shortest path is returned by _get_path method that uses Floyd-Warshall algorithm to calculate “raw” path, namely a list of nodes.
Then this information is augumented with output ports.

As soon as shortest path is calculated it is converted to appropriate rules and is installed to all switches that belong to it.

  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)

First of all WaitingPath is created that caches our packet to be sent out after we receive Barrier reply. Then rules for each switch belonging to the shortest path are installed accomponied with Barrier request message. All rules are basically the forwarding rules that have a common match but different output port.

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 = buf
  switch.connection.send(msg)

As soon as Barrier reply is received WaitingPath is notified to output previously cached packet and raise PathInstalled event. WaitingPath is using a list of Barrier requests identifiers, called XIDs, to wait until all switches reply with Barrier reply. Each time Barrier reply from one of switches along the path is received, its XID is removed from the list. Thus emtpy list, named xids, indicates that path is installed to all the switches and it is safe to send the cached packet.

  def notify (self, event):
    self.xids.discard((event.dpid,event.xid))
    if len(self.xids) == 0:
      # Done!
      if self.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))

PathInstalled event could be used in other modules subscribed to events from l2_multi.

New things that appered in this module

• Barrier
• Floyd-Warshall algorithm
• XID
• core.l2_multi.raiseEvent

References

• l2_multi description in POX Wiki
• l2_multi.py source code
• Floyd-Warshall algorithm description in Wikipedia