Shortest Path forwarding with Openflow on RYU

So, Openflow doesn’t do shortest path forwarding? How can a network architecture NOT do shortest path forwarding? SDN is BS.

Yes, Openflow doesn’t do shortest path forwarding by itself, in fact, it doesn’t do anything by itself. Openflow is a tool that allows you to programmatically control your network devices.

However, it gives you the power to do it. In this post I’ll guide you through the development of a shortest-path forwarding network application using the RYU Controller and Openflow. Hopefully I’ll post a few thoughts on different forwarding schemes and Openflow.

For this tutorial, I’m assuming you are familiar with Openflow, Mininet and RYU. If you are not, go ahead and check this other posts. I’m using RYU, which is an OpenFlow Controller written in python with support to OpenFlow 1.3. To know more about it visit their website

To install RYU you can easily do pip install ryu and BOOM! If it doesn’t work you can try using the Mininet installation script with the -y option.

The network application will be organized in three blocks:

  • topology discovery
  • network view construction
  • forwarding

For the topology discovery we’ll use a RYU module/library called topology. For network view construction we’ll use an awesome python graph library called networkX. For forwarding we’ll use OpenFlow.

Topology discovery

First, let’s see how the topology discovery works on RYU. Go ahead and copy the simple_switch.py application, to a new file called sp.py. We’ll start from that. Now, import the topology module adding this:

from ryu.topology import event, switches
from ryu.topology.api import get_switch, get_link

Also add the following function at the end of the code.

@set_ev_cls(event.EventSwitchEnter)
    def get_topology_data(self, ev):
    switch_list = get_switch(self.topology_api_app, None)
    switches=[switch.dp.id for switch in switch_list]
    links_list = get_link(self.topology_api_app, None)
    links=[(link.src.dpid,link.dst.dpid,{'port':link.src.port_no}) for link in links_list]

The event EventSwitchEnter will trigger the activation of get_topology_data(). Next we call get_switch() to get the list of objects Switch, and get_link() to get the list of objects Link. This objects are defined in the topology.switches file. Then, we build a list with all the switches ([switches]) and next a list with all the links [(srcNode, dstNode, port)]. Notice that we also get the port from the source node that arrives at the destination node, as that information will be necessary later during the forwarding step.

Let’s go ahead and add a “print links” and “print switches” to get_topology_data() and see what happens. Start ryu, then start mininet. ATTENTION: make sure you run ryu-manager sp.py --observe-links. You should see something like this:

[1, 2, 3, 4]
[(2, 3, {'port': 3}), (3, 2, {'port': 2}), (3, 4, {'port': 3}), (2, 1, {'port': 2}), (4, 3, {'port': 2}), (1, 2, {'port': 2})]

If you forget to add the –observe-links option you will see something like this:

[1, 2, 3, 4]
[]

Now that topology discover is working we can move ahead and build a central view of the network.

Network view

To build the network view we will need the networkx library. To install it do:
sudo pip install networkx They can do SEVERAL cool graph operations for you, you should check their documentation.
First we’ll instantiated a Graph to represent the network adding this to the init function of our application:

self.net=nx.DiGraph()

Next we’ll update the graph every time we get topology data:

self.net.add_nodes_from(switches)
self.net.add_edges_from(links)

And BOOM! Now we have real-time info from our topology in the self.net. Also don’t forget to import networkx as nx.

Shortest path forwarding

The last step is the actual forwarding. This is the pseudo code for it.

If source MAC is unknown then learn it
If destination MAC is unknown then flood it.
If destination MAC is known then:
get shortest path
get next hop in path
get output port for next hop

The actual code is:

if src not in self.net: #Learn it
    self.net.add_node(src) # Add a node to the graph
    self.net.add_edge(src,dpid) # Add a link from the node to it's edge switch
    self.net.add_edge(dpid,src,{'port':msg.in_port})  # Add link from switch to node and make sure you are identifying the output port.
if dst in self.net:
    path=nx.shortest_path(self.net,src,dst) # get shortest path  
    next=path[path.index(dpid)+1] #get next hop
    out_port=self.net[dpid][next]['port'] get output port
else:
    out_port = ofproto.OFPP_FLOOD

The code is self explanatory, feel free to contact me if you have any doubts.

The full code for this application can be download from the following github repo: https://github.com/castroflavio/ryu.

To run the topology feature from RYU, make sure you run the controller as ryu-manager –observe-links shortestpath.py

Advertisements

I'm a Network Engineer with software development experiences. MSCS from Georgia Tech. CCNA certified. ONF-SDN certified.

Tagged with: , , , ,
Posted in RYU, SDN, Tutorials
32 comments on “Shortest Path forwarding with Openflow on RYU
  1. RyuJordiSDN says:

    Hi Flavio,

    Nice work!! I am a newbie with SDN and this code is really self-explanatory.
    I’ve been working and playing with the code, but I realised about some problems when executing it. I create a linear topology of 3 elements with mininet.
    My working environment is a virtual machine downloaded from (http://sdnhub.org/tutorials/sdn-tutorial-vm/) with OVS version 2.3.90, Mininet version 2.1.0 and Ryu version 3.7.
    These are my concerns:

    a) I uncommented the logger line (self.logger.info(“packet in %s %s %s %s”, dpid, src, dst, msg.in_port)) and then I have seen that a lot of packetin messages are generated. Checking with wireshark, I have seen that there are a lot of OFPT_ERROR messages. Maybe this is produced by the LLDP messages. At the end this is a problem because the quantity of packetin messages can overflow the SDN controller. Could it be possible to run LLDP only for 20 seconds (assuming a static network) so we can get the topology?

    b) On the other hand, I have realised that I need to restart several times mininet until the topology discovery is able to discover all the switches. For the moment I am using only 3 switches but if I want to scale the topology, this could be a problem.
    It is like Ryu is not able to catch all the EventSwitchEnter events. Has anyone experience the same problem? Maybe we can save the LLDP process if we catch all the events when the switches enters the network….

    Bufff, too much!! I really squeeze the code… Any discussion will be welcome

    Like

  2. a) I’ve never had a problem like that. So I’m not sure on how to help. The ryu mailing list might be a good resource. I have a guess maybe try updating the ryu-controller. No guarantee that will help, but I did my work using ryu 3.15.

    b) I’ve had that problem. I haven’t really spend much time reading the topology code so I don’t know the cause of it but I have a solution. Normally, what I did was starting the controller/mininet in a different order. If I remember right, it was stable whenever I started the controller after mininet. If it works please let me know.

    Like

  3. Also for the cause of the instability, the ryu mailing list might be a good resource.

    Like

  4. RyuJordiSDN says:

    Thank Flavio,

    a) So when you uncomment the line, don’t you see the packet in trace in your computer?
    b) I’ve tried what you say, but according to the code, we have to start first the controller because it is waiting for enter_switch events.

    Something is weird at my computer… :s
    My environment is: OVS version 2.3.90, Mininet version 2.1.0 and Ryu 3.17

    Like

  5. a) No I don’t have packet-in floods in my computer. Would you capture the packets using wireshark and post it here?
    b) Have you tried starting it after?

    Like

  6. Allen says:

    Hi Flavio,

    I also encounter the same problem with RyuJordiSDN. I have receive a lot of packet in messages when I run ryu-manager –observe-links sp.py.However,It will display the normal state when I run ryu-manager sp.py,but I can’t discover link information.

    thanks

    Like

  7. Sakib says:

    Hi RyuJordiSDN

    I am having same kind of problem with this application. Did you solve the problem? If you have a solution can you please share it.?

    Thanks

    Like

  8. Sakib says:

    Hi Flavio:

    I did the following tests with the app-

    Topology:
    –topo linear,3 –controller=remote : OK
    –topo tree,2 –controller=remote: OK
    –topo tree,3 –controller=remote: Failed
    For any topo with looping path: Failed
    In loop topology with STP enabled: Failed

    Notice that it is working for tree,2 but not for tree,3. Let me know if you face the same thing.

    The thing is when we want to calculate shortest path most of the time there will be multiple path and switching loop also.
    Please let me know what is your opinion regarding this situation.

    Thanks

    Like

  9. Sakib says:

    Sorry the topology is not how i designed. It changed. ignore the topology.

    Like

  10. The topology info comes from the LLDP module. It did work for me with topologies with loops. But it didn’t work with STP enabled.

    Without STP, apparently, there is a LLDP FLOOD happening.

    I can’t work on this now, but one way to debug it is to use the networkx graphical capabilities to visualize the network and debug the LLDP module.

    Like

  11. abhi says:

    your code is running but it doesn’t show that in a link which is switch and which is host.

    Like

  12. abhi says:

    actually your code is only showing that which switch is connected to whom, which we can do by running the dumper file

    Like

  13. John K. says:

    When i try executa this example, an error occurs:

    AttributeError: ‘SimpleSwitch’ object has no attribute ‘topology_api_app’

    are you know what means?

    Thanks,

    Like

  14. Some people had that before.

    Would you double check you are importing all the necessary libraries?
    The original code is here:

    https://github.com/castroflavio/ryu/blob/master/ryu/app/shortestpath.py

    Let me know if it doesn’t work. I’ll take a look at it soon.

    Like

  15. Jack Zhao says:

    for mininet command: sudo mn –topo tree,depth=3 –mac –switch ovsk –controller=remote

    Are we expecting the following results?

    instantiating app ryu.controller.ofp_handler of OFPHandler
    **********List of links
    []
    **********List of links
    [(2, ‘be:70:6a:73:75:7b’), (‘be:70:6a:73:75:7b’, 2)]
    **********List of links
    [(1, 2), (1, ‘9e:cd:2d:3a:92:e9’), (2, 1), (2, ‘be:70:6a:73:75:7b’), (2, ‘b2:db:5b:9f:1c:ce’), (‘9e:cd:2d:3a:92:e9’, 1), (‘be:70:6a:73:75:7b’, 2), (‘b2:db:5b:9f:1c:ce’, 2)]
    **********List of links
    [(1, 2), (1, ‘9e:cd:2d:3a:92:e9’), (2, 3), (2, 1), (2, ‘be:70:6a:73:75:7b’), (2, ‘b2:db:5b:9f:1c:ce’), (2, ’12:0f:ae:77:42:cd’), (3, 2), (3, ‘ca:6a:ac:d2:e9:c0’), (‘9e:cd:2d:3a:92:e9’, 1), (‘be:70:6a:73:75:7b’, 2), (‘ca:6a:ac:d2:e9:c0’, 3), (‘b2:db:5b:9f:1c:ce’, 2), (’12:0f:ae:77:42:cd’, 2)]
    **********List of links
    [(1, 2), (1, ‘9e:cd:2d:3a:92:e9′), (2, 1), (2, 3), (2, 4), (2, ’12:0f:ae:77:42:cd’), (2, ‘be:70:6a:73:75:7b’), (2, ‘b2:db:5b:9f:1c:ce’), (3, 2), (3, ’00:00:00:00:00:01′), (3, ‘ca:6a:ac:d2:e9:c0’), (4, 2), (4, ‘6a:28:2e:d6:bb:86’), (‘6a:28:2e:d6:bb:86’, 4), (‘9e:cd:2d:3a:92:e9′, 1), (’00:00:00:00:00:01’, 3), (‘be:70:6a:73:75:7b’, 2), (‘ca:6a:ac:d2:e9:c0’, 3), (‘b2:db:5b:9f:1c:ce’, 2), (’12:0f:ae:77:42:cd’, 2)]
    **********List of links
    [(1, 2), (1, 5), (1, ‘8e:fa:09:b4:9a:9b’), (1, ‘9e:cd:2d:3a:92:e9′), (2, 1), (2, 3), (2, 4), (2, ’12:0f:ae:77:42:cd’), (2, ‘be:70:6a:73:75:7b’), (2, ‘b2:db:5b:9f:1c:ce’), (3, 2), (3, ’00:00:00:00:00:01′), (3, ‘ca:6a:ac:d2:e9:c0’), (4, 2), (4, ‘6a:28:2e:d6:bb:86’), (‘6a:28:2e:d6:bb:86’, 4), (‘9e:cd:2d:3a:92:e9′, 1), (’00:00:00:00:00:01’, 3), (‘ba:33:cc:0c:31:5c’, 5), (‘be:70:6a:73:75:7b’, 2), (‘ca:6a:ac:d2:e9:c0’, 3), (‘8e:fa:09:b4:9a:9b’, 1), (‘b2:db:5b:9f:1c:ce’, 2), (’12:0f:ae:77:42:cd’, 2), (5, 1), (5, ‘ba:33:cc:0c:31:5c’)]
    **********List of links
    [(‘8a:40:e4:93:2d:7f’, 5), (1, 2), (1, 5), (1, ‘8e:fa:09:b4:9a:9b’), (1, ‘9e:cd:2d:3a:92:e9′), (2, 1), (2, 3), (2, 4), (2, ’12:0f:ae:77:42:cd’), (2, ‘be:70:6a:73:75:7b’), (2, ‘b2:db:5b:9f:1c:ce’), (3, 2), (3, ’00:00:00:00:00:01′), (3, ‘ca:6a:ac:d2:e9:c0’), (4, 2), (4, ‘6a:28:2e:d6:bb:86’), (‘6a:28:2e:d6:bb:86’, 4), (6, ‘5e:4a:73:52:ac:b9′), (6, ’00:00:00:00:00:06’), (6, 5), (‘9e:cd:2d:3a:92:e9’, 1), (‘5e:4a:73:52:ac:b9′, 6), (’00:00:00:00:00:01’, 3), (‘ba:33:cc:0c:31:5c’, 5), (‘be:70:6a:73:75:7b’, 2), (‘2a:b0:dc:0a:90:ff’, 5), (‘ca:6a:ac:d2:e9:c0’, 3), (‘8e:fa:09:b4:9a:9b’, 1), (‘b2:db:5b:9f:1c:ce’, 2), (’00:00:00:00:00:06′, 6), (’12:0f:ae:77:42:cd’, 2), (5, ‘8a:40:e4:93:2d:7f’), (5, 1), (5, ‘ba:33:cc:0c:31:5c’), (5, 6), (5, ‘2a:b0:dc:0a:90:ff’)]

    Can you explain why it got printed multiple times?

    Like

  16. Sometimes the topology view app is just inconsistent, I still haven’t figured a really good way to debug it.

    Normally I just change the order that I’m running ryu and mininet (Ryu, first.. or Mininet first) until I get a consistent view of the network.

    I should post an updated version of the tutorial soon with some added features and troubleshooting tips, I’ll let you know when I do this.

    Like

  17. Olá Flávio!

    Estou usando ryu e mininet. Estou tendo problemas em obter os parâmetros dos links entre switches (delay, loss…). Você poderia me ajudar?

    Muito obrigado!
    Neto.

    Like

  18. I want to change the shortest path algorithm (nx.shortest path) with johnson algorithm (nx.johnson). how I can add the weights that are edges?

    Like

  19. Anonymous says:

    Hi,
    I want to use shortest path algorithm with weights for edges that this weights changes every time, how can I write it?

    Like

  20. The easy way is to change the weights in the graph structure. Other problems may arise from that, such as, changing the flow rules dynamically or stuff like that.

    Like

  21. Sharanya says:

    Hi Flavio,
    Can I use the same code to implement the widestpath?

    Like

  22. Moilfir says:

    Hi Flavio,
    I modified your program using johnson algorithm with random weight. And it works when I try “pingall” using 4 nodes. But I need to do “pingall” several times while using 6 nodes or more.
    Why did it happen?
    Thank you..

    Like

  23. t says:

    Will this code run on GENI platform??
    http://www.geni.net/

    Like

  24. I don’t see why it would not work.

    Like

  25. tp says:

    Error in the datapath 0000000000000001 from (‘127.0.0.1’, 54286)
    hub: uncaught exception: Traceback (most recent call last):
    File “/usr/local/lib/python2.7/dist-packages/ryu/lib/hub.py”, line 60, in _launch
    return func(*args, **kwargs)
    File “/usr/local/lib/python2.7/dist-packages/ryu/controller/controller.py”, line 460, in datapath_connection_factory
    datapath.serve()
    File “/usr/local/lib/python2.7/dist-packages/ryu/controller/controller.py”, line 378, in serve
    self._recv_loop()
    File “/usr/local/lib/python2.7/dist-packages/ryu/controller/controller.py”, line 132, in deactivate
    method(self)
    File “/usr/local/lib/python2.7/dist-packages/ryu/controller/controller.py”, line 281, in _recv_loop
    handler(ev)
    File “/usr/local/lib/python2.7/dist-packages/ryu/controller/ofp_handler.py”, line 278, in error_msg_handler
    if msg.type == ofp.OFPET_EXPERIMENTER:
    AttributeError: ‘module’ object has no attribute ‘OFPET_EXPERIMENTER’

    I’m getting this error. Can anyone help??

    Like

  26. Assis TIago says:

    The same thing happened to me and the user “tp”

    Like

  27. That seems to be an issue with the OpenFlow version. What versions of OVS, and RYU are you using?

    Liked by 1 person

  28. Assis Tiago says:

    I’m using Ryu 4.18 and Open vSwitch 2.6.2!

    Like

  29. Assis Tiago says:

    What version you use in the case study?

    Like

  30. HusaynS says:

    Hi Castro. How can I use your shortest path code to do L3 routing and modify the flow entries once there is a failure on one path to the destination?

    Liked by 1 person

  31. That’s a great question. I’ll address it in another post.

    Like

  32. mary says:

    Thanks for sharing your code. For topologies with loop, it does not work properly. I have connectivity between some of the hosts only. Also, can you share an updated version for OpenFlow 13?

    Like

Please leave any feedback

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Network Heresy

Tales of the network reformation

How to Do Great Research

Grad school survival advice from Nick Feamster and Alex Gray

n40lab

A blog about cloud, virtualization, sdn and centos

%d bloggers like this: