LTH-image

Homework Assignment 4

This homework covers the same aspects as the previous homework - SDN, but in a more thorough way. The goal of this homework is to illustrate what you can do with SDN. For some more motivation I recommend that you look at this talk by Scott Shenker. This homework is based on a homework in the ETH course Advanced Topics in Communication Networks HS 2014: Software-Defined Networking, by Prof. Bernhard PLattner. The original homework can be found here. Note that our homework only covers Part A - step 2. An FAQ on POX is found here.

Overview

In this homework you will develop a SDN controller that routes traffic in a simulated datacenter. The datacenter topology is defined below, and as you can see it contains lots of loops. Therefore it will not be possible to just use a bunch of learning switches, since when you flood the switches the network traffic will explode. Instead you will have to implement a smart way of routing the traffic between the switches and hosts.

The way we will route traffic between a source and destination is to compute a list of all the shortest paths between them (because of the topology structure there might be several paths that are the shortest possible path between two switches). Then we will randomly select one of these paths and install a flow on each of the switch lying on this path. This will ensure that we don’t loop any packages and that we utilize all of the network structure.

The topology you will use is a clos topology with one core switch, two aggregate switches, four edge switches, and 8 hosts.

For this homework you will get the mininet topology for free (clos_topo.py). For the development of the SDN controller you will be given some starter code (hw4_controller.py). Your job is to finish the methods within this code (you will see the “TO BE WRITTEN BY YOU” comments). The controller-code is developed by ETH for their original homework, but it is commented by us.

The structure of the homework is as follows:

  1. Download and install necessary software
  2. Study the code in hw4_controller.py
  3. Complete ShortestPaths
  4. Complete flood_on_switch_edge
  5. Complete send_arp_reply
  6. Complete install_end_to_end_IP_path

For simulating the network you will once again use Mininet, and for SDN you will use OpenFlow with POX as the API.

Deadline and Deliverables

Deadline for this homework is April 14. You will hand in the source code.

Installing the necessary software

For this assignment you will have to download our clos_topo.py (can be found here) and the starting code hw4_controller.py (can be found here). You will also have to install a necessary package NetworkX that will be needed when you will calculate the shortest path between two switches.

  1. Download hw4_controller.py and clos_topo.py and copy them into your VM
    • make sure to copy hw4_controller.py to directory ~/pox/pox/
  2. Install the NetworkX package
    1. install pip on your Linux VM:
      • $ sudo apt-get install python-pip
    2. install NetworkX
      • $ sudo pip install networkx

Run the controller and the topology

To run the controller and the topology you can follow these steps:

  1. Start two terminal windows (W1) and (W2) and ssh into your VM
  2. (W1): Run the Mininet topology
    • $ sudo python clos_topo.py -c 1 -f 2
    • Will generate the desired topology
    • -c is the number of core switches
    • -f is the number of switches in the layer beneath per switch
  3. (W2): Start the controller
    • $ cd pox/
    • $ ./pox.py openflow.discovery hw4_controller
    • openflow.discovery is used to discover the links between all the switches

Controller - overview

The SDN controller that is used in this assignment has some data structures that you will need to understand. They will be covered in short here and include:

  • SwitchWithPaths
  • switches
  • adjs
  • sw_sw_ports

When a new packet arrives at a switch a PacketIn event is raised. This event is then forwarded to the controller and handled by the _handle_PacketIn() method. There, different actions are taken depending on wether it is an IP-packet or an ARP-packet. If we don’t know the destination of the packet we will have flood the packet (which will be implemented by you). If it is an ARP packet and we do know the destination we will send it to the correct switch. If it is an IP packet and we know the destination we will install a flow between the source and the destination of the packet, and of course also send the packet.

If you feel that you need more about the code, please take a look at The original homework.

SwitchWithPaths

This is an internal class that allows the controller to store information about each switch. Some of the useful attributes of this class are:

  • connection - is the connection to the actual switch
  • dpid - the id of this switch
  • ports - a list of the port-objects
  • _paths - a dictionary with lists of all the shortest paths to the other switches.
    • key = destination switch id (dpid)
    • value = a list of the shortest length-paths to the destination switch.

When a new ConnectionUp event is fired the method _handle_ConnectionUp() in our controller is called. In this method we create a new SwitchWithPaths-instance and store it in the controller. It’s stored in the structure self.switches which is described more below.

When the controller wants to install a flow on a switch, or send an arp-reply to/form a switch it calls an appropriate method in SwitchWithPaths. Some of the methods of this class are:

  • appendPaths(dst, paths_list)
    • Method to add a list of paths from this switch to the destination (dst) switch.
    • The the list, paths_list, will contain all the shortest length-paths to the destination switch.
  • clearPaths()
    • Method to erase all the paths in _paths
  • printPaths()
    • Method to print all the paths in _paths
  • flood_on_switch_edge(packet, no_flood_ports)
    • TO BE WRITTEN BY YOU
  • send_packet(outport, packet_data)
    • Method to send a packet from this switch on a specified port
  • send_arp_reply(packet, dst_port, req_mac)
    • TO BE WRITTEN BY YOU
  • install_output_flow_rule(outport, match, idsle_timeout, hard_timeout)
    • Method to install a flow rule on this switch.
    • This method is very useful when you will write your install_end_to_end_IP_path()

switches

This is a dictionary in the controller in which it stores all the instances of SwitchWithPaths that has been created. This dictionary is updated automatically whenever a new switch is found.

  • key = dpid (the id of the switch)
  • value = the SwitchWithPaths-instance that correspond to the dpid

  • Example 1 - iterate through all the switches in the dictionary

    for s in self.switches:
        # print all the paths
        s.printPaths()
        # clear all the paths
        s.clearPaths()
    
  • Example 2 - retrieve the SwitchWithPaths-instance of the switch that fired an event (event) (for instance, a PacketIN event)

    dpid = event.dpid # get the dpid
    my_switch = self.switches[dpid] # get the SwitchWithPaths instance
    # do your thing...
    

adjs

This is a dictionary in the controller that stores a list of all the adjacent switches for each switch. This dictionary is updated automatically whenever a new switch or link between switches are found.

  • key = dpid (the id of the switch)
  • value = a list of neighbors

  • Example - print a list of all the neighbor switches for the switch with id my_dpid:

    my_adj_list = [] # create an empty list
    my_adj_list = self.adjs[my_dpid] # retrieve the list of neighbors
    print my_adj_list
    

sw_sw_ports

This is a dictionary that stores information about which port connect two neighbors. This dictionary is also updated automatically whenever we find a new link or a new switch.

  • key = (dpid1, pdid2)
  • value = outport of dpid1

  • Example - let’s say that switch1 (with id dpid1) and switch2 (with dipid2) are neighbors and we wish to know which port on switch1 connects to switch2 as well as which port on switch2 that connects to switch1.

    sw1_port = self.sw_sw_ports[(dpid1, dpid2)]
    print "Switch 1 connects to Switch 2 on port %i" %sw1_port
    sw2_port = self.sw_sw_ports[(dpid2, dpid1)]
    print "Switch 2 connects to Switch 1 on port %i" %sw2_port
    

ShortestPaths - to be written by you

This method is called automatically whenever the controller discovers a new switch, a new link between two switches, or when a switch goes down.

The goal of this method is to:

  1. Build a network topology using the two structures switches and adjs as well as the NetworkX-package
  2. For each switch in switches,
    1. Calculate all the shortest paths to each of the other switches
    2. Store this information in the switch

Stay Sane - a good idea is to print the shortest paths between two switches (so you can verify if it works).

NetworkX is a python package that will help you build a network network topology and calculate the shortest paths in an easy manner. To help you a little bit we provide to useful examples on how to use this package.

  • NetworkX documentation

  • Example 1 - Create a directed graph and add a link between a switch s1 (with dpid dpid1) and its neighbors:

      import NetworkX as nx     # import the package 
    
    
      G = nx.DiGraph() # create a directed graph
      s1 = switches[dpid1] # get the switch with dpid1
      for a in adjs[s1]: # iterate through all the neighbors of switch s1
         G.add_edge(s1, a) # add a link between s1 and a
    

    Note: G.add_edge(s1, a) will create a node for s1 and for a (if they don’t already exist) and add a link between them.

  • Example 2: Compute a list of all the shortest paths between switch source (with dpid source_dpid) and switch dest (with dpid dest_dpid). Both switches are assumed to have been previously added in the directed graph G.

    import NetworkX as nx       # import the package
    
    
    # we assume the topology and graph has already been created
    
    
    source = switches[source_dpid]
    dest = switches[dest_dpid]
    try:
        # calculates a list of all the shortest paths between source and dest
        paths_list = [p for p in nx.all_shortest_paths(G, source, dest)]
    except Exception, e:
        pass
    

    Note: all_shortest_paths(G, s, d) might cause an exception if there is no possible path between s and d. So you need a try-except statement.

Some useful methods

# clear all the paths for the switch with dpid s_dpid
switches[s_dpid].clearPaths()

# create an empty list
my_paths_list = []

# store a list of all the shortest paths from switch source to switch dest
# assumes that the paths have been calculated prior to this
# and stored in "my_paths_list"
switches[source_dpid].appendPaths(dest, my_paths_list)

flood_on_switch_edge - to be written by you

This method is called when the controller doesn’t know the destination address of the packet. This means that we need to flood that packet to the network. Since our network contains a lot of loops this is quite dangerous to do. If done wrong the network traffic will explode! To ensure that this doesn’t happen, we should only flood the packet on the ports of the switches that are connected to the hosts. Or, to put it in a different way, we should flood the packet to the switch-ports that are not connected to other switches.

The goal of this method is to:

  1. send the packet to every port of this switch that is not in the list no_flood_list

Stay Sane - when this method works you should be able to ping different hosts.

Note: no_flood_ports is a list of port-numbers while the structure self.ports, in SwitchWithPaths, is a list of port-objects. To get the actual port numbers of the port object in self.ports you can use the following:

# iterate through all the port objects in ports
for p in self.ports:
    port_number = p.port_no
    # do your thing here...

Some useful methods

# get a list of all the port objects in this switch
self.ports

# print the port number of all the ports
for p in self.ports:
    # note that p is a port object
    print p.port_no

# send a packet to port p (a port object)
self.send_packet(p.port_no, packet)

send_arp_reply - to be written by you

This method is called when the controller wants to send an arp-reply and knows the address of the destination.

The goal of this method:

  1. craft an arp.REPLY message
  2. craft an ethernet.ARP_TYPE message
  3. pack the ethernet message
  4. send the packet

Some useful methods:

# create a arp message
my_arp = arp()
... fill in the fields ...

# create an ethernet message
ether = ethernet()
... fill in the fields ...

# pack the ethernet message
ether.pack()

If you need more help you can take a look at this example of an arp-message.

install_end_to_end_IP_path - to be written by you

When an IP packet arrives on a switch and the controller knows the address of the destination for this packet this method is called. The switch on which the packet first arrived will raise an PacketIN event (which can be used to get the id of this switch event.dpid). To install a flow from the source switch to the destination switch one will need to install a flow rule on each of the switches that is on the path. Installing a flow from the source switch to the destination switch is much like building a channel from a full lake to an empty lake, it raises the following question: in which order should one install the flow?

Another important aspect of this method is to ensure that we utilize as much as we can of the network structure. Since we have a lot of loops in our network structure, we may have multiple (and equally short) paths between two switches. This means that we can do better than always using the same path between such two switches.

To ensure that we don’t loose any packets, we need to send the packet that caused the event before we exit the method.

The goal of this method:

  1. Get the switch that triggered the event
  2. Get the destination switch
  3. Get the list of all the paths between the source and destination switch
  4. Randomly select one of these
  5. Install a flow rule on each of the switches in this path
    • what should the flow rule match on?
    • remember the install_flow_rule(outport, ...) method ;)
  6. Send the packet

Some useful methods:

# get the dpid of the switch that raised the event
# this is the switch connected to the host that sent the packet
source_dpid = event.dpid

# create a flow match
my_match = of.ofp_match()
my_match.dl_src = ... 
my_match.dl_dst = ...

# select a random item from a list
rand_item = random.choice(my_list)

# get the port that connect switch1 --> switch2
port = self.sw_sw_ports[(switch1_dpid, switch2_dpid)]

# iterate a list in a reversed manner
for s in reversed(my_paths_list):
    # do your thing...

If you need more help, take a look at The original homework.

Python help

If you are unfamiliar with Python, you should check out this turorial.

OpenFlow and POX help

I highly recommend the OpenFlow POX wiki for any question on OpenFlow and POX.