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

35 Replies to “Shortest Path forwarding with Openflow on RYU”

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

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

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

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

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

  7. When i try executa this example, an error occurs:
    AttributeError: ‘SimpleSwitch’ object has no attribute ‘topology_api_app’
    are you know what means?
    Thanks,

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

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

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

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

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

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

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

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

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

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

Leave a Reply

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