Author: Gabriele Gemmi

Implementing Pop-Routing in OSPF – Final evaluation updates

Posted on by Gabriele Gemmi

Hello again, since last updates I worked hard to finish my project and to reach the final milestone for this project.

As I explained in my previous post[1], due to some issues, we’ve decided to change the topic of the project to Implementing Pop-Routing in OLSRd instead of OSPF.

In this last month I completed the code for the OLSRd plugin[2], which I hope will be merged soon [3].In order to allow PRINCE to interact with OLSRd I had to modify the PRINCE source code[4] and create a new plugin[5].

The last part of my GSOC was testing the functionalities of my project.
To perform this tests I used a tool developed by the University of Trento, called “NePA TesT”[6]. NePA allowed me to simulate a mesh network in my laptop and to perform tests on it. The network topology was defined using NetJSON, but for my purpose modified it to use graph generators[7]

To ensure that PRINCE was working correctly on this virtual network I measured the centrality and the tuned timer for each node. Then I compared these values to the ones calculated by the original algorithm. Since the simulated network was real, and it needed a bit of time to converge, I took the last 10 values to avoid to measure errors. This are the maximum errors for each size and each kind of graph:

Maximum of percentage errors calculating nodes centrality

I also measured the “hello” messages’ rate to check if it was being calculated correctly by PRINCE. As I did for the centrality I took the mean of the last 10 values for each node and I compared them against the ones calculated using the python Pop-Routing algorithm.

Maximum of percentage errors calculating “Hello” messages’ emission rate

Hence, as we can see from these tables, PRINCE is calculating the Centrality, and the timer’s value, with a really small error. This test also highlighted a bug (*) in the c_graph_parser library with very that particular kind of graph [8].

The last test I performed was to check whether the message to update the timers’ emission rate was actually modifying the emission rate of the messages.
I used a simple graph: 2 nodes connected by one link. And I captured the traffic with tcpdump, before and after the update message.
After 30 seconds I sent a message to the OLSRd poprouting plugin to update the hello timer to 5s. As you can see from the graph below it is working correctly!

Hello messages measured emission rate

I can conclude that PRINCE is working correctly with OLSRd and now it can be used to enhance the Wireless Community Networks that are still using it.
I would like to thank Freifunk, Ninux and Google for giving me the opportunity to participate in GSoC.

Cheers, Gabriele Gemmi

[1]: https://blog.freifunk.net/2017/07/27/implementing-pop-routing-ospf-july-updates/
[2]: https://github.com/AdvancedNetworkingSystems/olsrd/tree/poprouting
[3]: https://github.com/OLSR/olsrd/pull/38
[4]: https://github.com/AdvancedNetworkingSystems/poprouting/tree/refactor_ospf
[5]: https://github.com/AdvancedNetworkingSystems/poprouting/tree/refactor_ospf/prince/lib/olsrd
[6]: https://ans.disi.unitn.it/redmine/projects/community-newtork-emulator/wiki
[7]: https://github.com/AdvancedNetworkingSystems/wcn_emulator
[8]: https://github.com/AdvancedNetworkingSystems/poprouting/issues/23

Implementing Pop-Routing in OSPF – July Updates

Posted on by Gabriele Gemmi

In the last months some issues emerged with the original plan of my project.
After implementing topology export in NetJSON format for BIRD, I started investigating how to modify the timers of OSPF, and finally found that OSPF has a limitation regarding the timers, which states that all the routers on the same network must have the same timers. This is surprising, since the RFC supports specifying the timer in the messages, and thus it would be trivial to have nodes with differentiated timers (as OLSR and other protocols do, for instance). Actually somewhere else in the RFC it is stated that even if the timers could be diversified, they must be used as a network-wide parameter, otherwise routers wont pair as neighbor. This issue is not easy to solve, and would break the compatibility with other OSPF implementations, thus, together with my mentor we decided to change the project on something that we could accomplish in the remaining time and that was still helpful for Wireless Communities.

Since many WCNs in Europe are still using OLSRv1 we’ve decided to implement PopRouting on it. The NetJSON plugin[1] is already available so we only had to implement the Timer’s plugin and the PRINCE plugin to communicate with it.

During this mont I’ve implemented and alpha version of the Pop-Routing plugin[2] for OLSRd. This plugin is quite simple, it listens to a specified port and it parse two commands : “/HelloTimer=xx.yy” and “/TcTimer=xx.yy”, where xx.yy are floating point numbers.

I’ve also implemented the Prince plugin[3] that communicate with OLSRd. It fetches the topology from the NetJSON plugin and it pushes the updated timers to the PopRouting Plugin.

The next month I am going to fix all the bugs I found, document the plugins and test Pop-Routing with NEPA test.

Despite those problems the implementation of NetJSON for OSPF is working and we hope it will be merged in the BIRD codebase soon.

Cheers, Gabriel

[1]: https://github.com/OLSR/olsrd/tree/master/lib/netjson
[2]: https://github.com/AdvancedNetworkingSystems/olsrd/tree/poprouting/lib/poprouting
[3]: https://github.com/AdvancedNetworkingSystems/poprouting/blob/refactor_ospf/prince/src/olsr/olsr.c

Implementing Pop-Routing in OSPF – June Updates

Posted on by Gabriele Gemmi

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

Posted on by Gabriele Gemmi

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

Posted on by Gabriele Gemmi

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

Implementing Pop-Routing – Midterm Updates

Posted on by Gabriele Gemmi

 

Hi Everyone!

Today has started the midterm evaluation, the deadline Is next Monday, so I have to show the work I have done ‘till now. It can be resumed in the following parts:


1) Refactoring of graph-parser and C Bindings

During the community bonding period I started working on the code of Quynh Nguyen’s M.Sc. Thesis. She wrote a C++ program capable of calculating the BC of every node of a topology [1]. I re-factored the code, and now it is a C/C++ shared Library [2]. I’ve also applied some OOP principles (Single responsibility and inheritance) and unit tests to make it more maintainable.

The interface of the library Is well defined and it can be re-used to implement another library to perform the same tasks (parsing the json and calculating the BC).


2)Prince Basic functionalities

After I completed the library a started working on the main part of the project. the daemon. We decided to call it Prince in memory of the Popstar.

This daemon connect to the routing protocol using the specific plugin (see below), calculate the BC using graph-parser, computes the timers and then it push them back using again the specific plugin. With this architecture it can be used with any routing protocol.I wrote the specific plugin for OONF and OLSRd. At the moment it has been tested with both, but I need to write a plugin for OLSRd to change the timers at runtime. For OONF I used the RemoteControl Plugin.

With these feature Prince is capable of pulling the topology, calculate the BC and Timers and push them back to the routing protocol daemon.

 

3) Additional Features: Configuration file, Dynamic plugins,

I wrote a very simple reader for a configuration file. Using the configuration file the user can specify: routing protocol host and port, routing protocol (olsr/oonf), heuristic, (un)weighted graphs.

As you can see from this Issue [3], I’m going to use INI instead of this home-made format.

As I said before I moved to a specific plugin all the protocol specific methods (pulling the topology and pushing the timers), to keep the daemon light I decided to load this plugin dynamically at runtime. So if you specify “olsr” in the configuration file just the OLSRd specific plugin will be loaded.

 

 

At the moment I consider this an “alpha” version of Prince. In the next 2 months I’ll be working on it to make it stable and well tested. The next steps will be:

 

  • Close all the Issues [4]
  • Write tests and documentation for Prince.
  • Write a plugin for OLSRd

 

Cheers, Gabriel

 

[1]: https://ans.disi.unitn.it/redmine/projects/quynhnguyen-ms

[2]: https://github.com/gabri94/poprouting/tree/master/graph-parser

[3]: https://github.com/gabri94/poprouting/issues/4

[4]: https://github.com/gabri94/poprouting/issues

Implementing Pop-Routing

Posted on by Gabriele Gemmi

Hi everyone!

I am Gabriele from the Ninux community. I am participating in GSoC 2016 for the first time and I am very glad I have been accepted as a Student for Freifunk. I am from Florence, Italy. Here I’m studying Computer Science, soon I will graduate and I hope to use the results of this project to write my bachelor thesis.

Four years ago, with others community networks’ enthusiasts we have funded Ninux Firenze[1], the fist Wireless Community Network in Florence where I had the chance to learn how these networks work and to meet many others people interested in this field. The network is constantly growing, and now it counts almost 20 nodes. In May ’14 I have been for the first time to Wireless Battle of the Mesh in Leipzig where I met the Freifunk community. For this GSoC I will work on a project called PopRouting[2]:

OONF (OLSRv2) is a link state routing protocol. It works sending periodical messages to his neighbors with the aim of transmitting information about topology changes. With these information each node of the network is able to calculate the paths to reach any other destination. These messages are periodically generated, based on the configuration parameter that regulates the sending interval. A short period will make the network react rapidly but it will also cause a large overhead due to control messages. Pop Routing is a recent technique that takes advantage of the knowledge of the network topology to find the optimal value for the OONF’s timers. Using Pop Routing every node computes the “betweenness centrality” of every other node and uses it to calculate the optimal trade-off between convergence and overhead for its timers. The algorithm has been developed at the UniTN and the algorithm to compute the BC in C++ is available as free software. My goal is to code a daemon (in C) that is able to calculate autonomously the BC of the network and push it to OONF using the telnet plugin.

In this month of community bonding I have been to Wireless Battle of the Mesh v9 in Oporto(PT). There I met the OONF developers and we discussed how to implement this inside OONF. I also gave a presentation on the project. After the Battlemesh I started working on the algorithm developed by UniTN and I made a C/C++ library out of it [3].

Today I will start coding for the GSoC, stay tuned and I will give you more updates soon.

 

Gabriel

 

[1]: http://firenze.ninux.org/

[2]: https://ans.disi.unitn.it/users/maccari/assets/files/bibliography/INFOCOM2016.pdf

[3]: https://github.com/gabri94/poprouting/tree/master/graph-parser