Implementing Pop-Routing in OSPF – June Updates

This is a continuation of the previous post [1].

During this month I have implemented the NetJSON plugin for BIRD. It exposes the topology of an OSPF Area using the network-graph format and thus allows Prince to fetch the topology and calculate the timer’s value.
I deployed a small testbed to debug my code using the network emulator called CORE [2]
Here you can see the testbed:

I’m currently working on this repository [3] and I’m looking forward to send a PR to BIRD.
I defined a new command in the bird’s cli: “show ospf topology netjson”. It returns a network-graph output that can be used by prince or by any other NetJSON[4] compatible software.
Here you can see the topology of the testbed using d3.js [5][6].

In this next coding period I will implement a plugin for Prince that interacts with BIRD. Unfortunately it uses a UNIX Domain socket instead of a network socket, so I’ll need to code the communication routines from scratch.

Cheers, Gabriel

[1]: https://blog.freifunk.net/2017/05/30/implementing-pop-routing-ospf
[2]: https://www.nrl.navy.mil/itd/ncs/products/core
[3]: https://github.com/AdvancedNetworkingSystems/bird/tree/origin/int-new
[4]: http://netjson.org
[5]: http://ninux-graph.netjson.org/topology/49aecbcf-a639-47a7-9f58-e39de5d57161/
[6]: https://github.com/netjson/django-netjsongraph

Implementing Pop-Routing in OSPF

Hello everyone.

I’m Gabriele Gemmi, you may remeber me for… Implementing Pop-Routing[1]
This is the second time I participate in GSoC and first of all I’d like to thanks the organization for giving me this opportunity.
Last year I implemented PR for OLSR2. The daemon, called Prince [2], is now available in the LEDE and the OpenWRT feeds.

What is Pop-Routing

PR is an algorithm that calculate the betwenness centrality [3] of every nodes of a network and then uses this values to calculate the optimal message timers for the routing protocol on each node. In this way a central node will send messages more frequently and an outer one less frequently.
At the end the overall overhead of the network doesn’t change, but the convergence gets faster.

Objectives

My project focuses on extending Prince functionalities to use Pop-Routing with OSPF. I decided to work with BIRD, since it’s written in C and it’s already available for OpenWRT/LEDE
In order to do this I need to develop 2 components:
— A plugin for BIRD that expose the OSPF topology in NetJSON and allows to update the timers
— A plugin for Prince that communicate with the BIRD plugin

I already started developing the former [4], and I’m looking forward to implement the latter.
I’ll keep reporting my updates here, so stay tuned if you wanna hear more.

Cheers, Gabriele

[1]: https://blog.freifunk.net/2016/05/23/implementing-poprouting/
[2]: https://github.com/AdvancedNetworkingSystems/poprouting/
[3]: https://en.wikipedia.org/wiki/Betweenness_centrality
[4]: https://github.com/AdvancedNetworkingSystems/bird

Implementing Pop-Routing – Final Evaluation

Hello again, for two months I have been working on my project and I have achieved all the goals.

An alpha version of my program was released for the mid-term evaluation.Since then I have fixed all the bugs, packaged the program for OpenWRT, tested the code and written the documentation.

Everything is available on the GitHub repository [0]

I structured my work opening by issues for all the bugs I had to fix and for everything I wanted to improve. Then, I organized the issues in milestones. Milestone 0.1 [1] is the one that I had to complete to finish the project. When that milestone was closed I made the branch “v0.1” [2].

Tests

In order to be sure that my program worked correctly. I wrote a simulator in python. It’s made by a small server, with the same interface as OONF’s telnet plugin, and two python libraries written by my mentor: cn_generator [3] and pop-routing[4]. The first one generates synthetic graphs using the Cerda-Alabern[5] algorithm, the second one is a pop-routing implementation in python. In the server I implemented the commands to push the NetJson[6] topology and the ones to receive the timers values.

When prince requests a topology from my test program, cn_generator generates a random graph and pushes it back; meanwhile using the python implementation of pop-routing, the references values are computed. The values received from prince are then compared to ones calculated using python.

The goal of tests is to verify that the difference between the reference and the measured values is always less than 1%.

Measurements

I’m going to use my work to write my Bachelor Thesis, so I wanted to perform some measurements to check how well it worked.

My goal was to implement the algorithm on an embedded device, so I chose to measure the execution time on a “Ubiquiti Picostation M2HP” to see how well it was performing.

I branched Prince [7], modifying the code to measure the time needed to calculate the betweenness centrality and push it back along with the timers.

I used the graph generator to create graphs from 5 to 500 nodes, and I measured the time needed to compute with a sample every 10 nodes. For each sample I ran 5 tests, then calculating the mean and the standard deviation. The results are shown here:

As you can see from the graphic above, the computation time on the embedded device is quite good if we use the heuristic (8s for 100 nodes), it proved to be unusable without it (100s for 100 nodes)

OpenWRT Package

The last objective I gave myself in the previous post was to write a plugin for OLSRd. Since OLSRd isn’t maintained anymore – and since all the developers are working on OONF – I decided to focus on it while avoiding the plugin. Instead, I wrote a makefile and packaged prince for openWRT / LEDE. The makefile hasn’t been published yet in any openWRT feed, but it is hosted in my repository [8]. Instructions are available along with documentation.

Future Work

I’ll keep working on this project, mantaining the code and fixing the future issues. Since the graph-parser library is the last piece of code implemented in C++ and it depends on the Boost libraries, I’m looking forward to re-implement it in pure C.

One of my goals was also to run prince in my WCN (Ninux Firenze), but switching from OLSRd to OONF is taking more time than expected, so I’m hoping to try it in the future.

Gabriel

[0]: https://github.com/gabri94/poprouting/
[1]: https://github.com/gabri94/poprouting/milestone/1?closed=1
[2]: https://github.com/gabri94/poprouting/tree/v0.1
[3]: https://ans.disi.unitn.it/redmine/projects/cn_generator/repository
[4]: https://ans.disi.unitn.it/redmine/projects/pop-routing/repository
[5]: https://pdfs.semanticscholar.org/4ac8/05e7359c6b20c3cdd5da24284d3826b9609c.pdf
[6]: http://netjson.org/
[7]: https://github.com/gabri94/poprouting/tree/exec_time
[8]: https://github.com/gabri94/poprouting/blob/master/Makefile.openwrt