Skip to content

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

Published inSDNTutorials

42 Comments

  1. RyuJordiSDN RyuJordiSDN

    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

  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.

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

  4. RyuJordiSDN RyuJordiSDN

    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

  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?

  6. Allen Allen

    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

  7. Sakib Sakib

    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

  8. Sakib Sakib

    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

    • 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.

  9. Sakib Sakib

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

  10. abhi abhi

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

  11. abhi abhi

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

  12. John K. John K.

    When i try executa this example, an error occurs:

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

    are you know what means?

    Thanks,

  13. 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?

  14. 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.

  15. 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.

  16. 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?

  17. Anonymous Anonymous

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

  18. 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.

  19. Sharanya Sharanya

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

  20. Moilfir Moilfir

    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..

  21. tp tp

    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??

  22. Assis TIago Assis TIago

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

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

  24. Assis Tiago Assis Tiago

    I’m using Ryu 4.18 and Open vSwitch 2.6.2!

  25. Assis Tiago Assis Tiago

    What version you use in the case study?

  26. HusaynS HusaynS

    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?

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

  28. mary mary

    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?

  29. flrnztwo flrnztwo

    Thank you for this example, RYU seems to be quite brief when it comes to topology discovery in its documentation. There are a few problems that I have noticed. First, you may experience scenarios where you have to run the ryu-manager several times to get all the links. This is expected as the method we are binding the topology discovery event to is a switch enter event. When a switch is added by the RYU topo discovery module it doesn’t imply that all its links were discovered so we have a race condition here. If the notification message is slow enough we will get all the links but sometimes it will not provide all links as they are unknown to RYU.

    After digging through the RYU source code I found that you can use the EventLinkAdd and EventLinkDelete topology events to detect all links. These methods are triggered when RYU detects a new link added to the topology and removed respectively.

    @set_ev_cls(event.EventLinkAdd)
    def event_link_add_handler(self, ev):
    src_sw = ev.link.src.dpid
    dst_sw = ev.link.dst.dpid
    src_pn = ev.link.src.port_no
    dst_pn = ev.link.dst.port_no
    self.logger.info(“Link added %s(%s) to %s(%s)” % (src_sw, src_pn, dst_sw, dst_pn))

    Second, some people were saying that they got a lot of packet in messages. This is actually the expected result. RYU will use a common SDN approach to detect the topology of the network. It will generate LLDP (link layer discovery protocol) packets and inject them using packet out OSPF commands on every switch in the network. Then, the switches are configured to redirect all LLDP packets back to the controller. RYU uses this info to essentially poll the network to discover topo info. So the mechanism has the inherent characteristic that we get a lot of controller packet in messages (plus the LLDP match rule installed) when we use the –observe-links flag. If you do not add this flag you will not get this storm of packet-in messages. As to whether you can configure the timing, I don’t think RYU offers you the option. you can modify the RYU source code to change its behaviour if you really need slower LLDP packet generation intervals.

    https://github.com/osrg/ryu/blob/0c0656f95a646756df5caae10734c2e561ff7b56/ryu/topology/switches.py#L511

    If you already know this, sorry, didn’t mean to re-explain it :-). Hopefully, this will help people that are having similar problems to what I encountered.

  30. Marco Marco

    Hi Flavio. Pycharm give me an error for the instruction
    self.net.add_edge(dpid,src,{‘port’:msg.in_port})
    how can I change this?
    And I think I have to change also
    out_port=self.net[dpid][next][‘port’]
    Thanks!

  31. litaguirre litaguirre

    Hey guys,

    I run the code https://github.com/castroflavio/ryu/blob/master/ryu/app/shortestpath.py, and I received the link description but I do not have ping.

    Any idea?
    liz@liz-VirtualBox:~/ryu$ PYTHONPATH=. ./bin/ryu-manager ryu/app/sp5.py –observe-links
    loading app ryu/app/sp5.py
    Generating grammar tables from /usr/lib/python2.7/lib2to3/Grammar.txt
    Generating grammar tables from /usr/lib/python2.7/lib2to3/PatternGrammar.txt
    loading app ryu.topology.switches
    loading app ryu.controller.ofp_handler
    instantiating app ryu.topology.switches of Switches
    instantiating app ryu/app/sp5.py of ProjectController
    instantiating app ryu.controller.ofp_handler of OFPHandler
    **********List of links
    []
    **********List of links
    [(’46:51:3d:6c:f6:2c’, 1), (1, ’46:51:3d:6c:f6:2c’), (1, 2), (2, 1)]

    mininet> pingall
    *** Ping: testing ping reachability
    h1 -> X
    h2 -> X
    *** Results: 100% dropped (0/2 received)

    • Shreyash Shreyash

      same issue

  32. Shahzad Shahzad

    Hi Flavio,
    1st of all, great article, very well explained.
    My question is, I want to get the link weight information of my topology and based on that I will populate the flow entries. In other words, How can I modify this code to do weighted shortest path finding? Because in this case nx,shortestpath assume weight 1 for all links. How can I get the weight info from the network.

  33. Chen Tang Chen Tang

    Hi Flavio,

    I read your code but I have one doubt, that is if the dst is unknown then you flood the packet.

    But in real-world network there might have some loop, if you flood all those packet then broadcast storm would happen.

    If you have any good solution feel free to contact me.

    Best regards

    Chen

    • Did find a solution to this problem? I’m struggling with the same issue. I want to make it work without having to use stp.

  34. Muhammad Muhammad

    Hey,
    Hope this comment finds you well. Although It may sound strange as it has passed many years from the topic, But lately I try to run this app with latest version of RYU, It has the following error:

    File “/home/osboxes/Desktop/Netlab_ryu/shortestpath.py”, line 106, in _packet_in_handler
    self.net.add_edge(dpid,src,{‘port’:msg.in_port})
    TypeError: add_edge() takes exactly 3 arguments (4 given)

    I would be grateful to hear more about the issue.

    • check the version of networkx installed. preferably use 1.11. I t should work.

    • Jona Jona

      Hello I had the same error, If you managed to solve, I would greatly appreciate it if you share the solution.

Leave a Reply to Muhammad Ilhamsyah Cancel reply

Your email address will not be published. Required fields are marked *