Author: Olden Fabre

GSoC 2014: Source-sensitive routing in Babel

Posted on by Olden Fabre

In Google Summer of Code 2014. I managed to finish my implementation of source-sensitive routing in Babel, and here is a complete review of the project :

I. Introduction and Background

    1. The Packets

Data on the Internet is transmitted by packet switching, this means that data is cut in several packets and each packet is sent on the network. In order to get the packets to their final destination, these jump from router to router. They are then recombined to get the original data. The source and the destination of each packet are stored in its header.

    2. Next-Hop Paradigm

Packets then travel via routers, which are computing devices connected to one another. Their role is to forward each packet to their right neighbor so that the packet can reach its destination. To do so, they use a data structure called the RIB or Routing Information Base. This RIB gives, for each destination, the next correct router. By doing so, each packet can reach its destination by following local routes. This paradigm is called the “Next-Hop Routing”.

    3. The Quagga Project

Quagga is routing software that takes care of building the RIB. It implements several routing protocols, including Babel.

    4. Zebra / Babel

Quagga is implemented on two levels. The daemon that takes care of the level that is the closest to the kernel is called Zebra, its role is to install the routes in the kernel. Quagga installs all the possible routes to a destination, in addition of the ones the user gives him, and sends all those routes to Zebra. Zebra then chooses the best one for each given destination and install them in the kernel.

    5. Source-Specific

Source-specific routing is a small extension of current routing systems. Instead of looking only at the destination in order to choose the next-hop, we use other informations already present in the packet but not used yet, the source being one of them. My contribution adds the possibility to route packets according to the pair (source, destination) instead of looking only at the destination to Babel.

    6. Its Application

One of the main goals of source-specific routing is to enable multi-homing quite easily in the absence of NAT, for example IPv6. Without source-specific routing, there is no way to identify the route taken by two packets when they have the same destination, since they just follow the route indicated by the RIB. With source-specific routing, the packets can travel to border routers using different routes and then be treated as normal packets by these border routers. The packets are then sent normally through the Internet. The source-specific routing inside a local network is a solution to the multi-homing problem in a setup in which there is no collaboration of the Internet Service Provider (ISP).

II. What I Contributed

    1. Getting in a large project

The Quagga project is a large open source routing software. It contains 287000 lines of code, and is separated in different routing protocols, including Babel. The Babel code is only 9860 lines, but it is a reasonable project to start with. With its event-driven code, Babel was a little hard to understand at first, but I had several works I could rely on.

    2. My participation

First, I took a few days getting used to ad-hoc networks and then proceeded to code the program itself. I could rely on Matthieu’s work, who implemented a stand alone version of Babel to have a backbone that supported my work. I recoded the functions that needed a prefix by including a source in them as well. I then merged my work in Quagga by using Zebra’s new source-specific functions, and after a bit of rewriting, everything was running well. I tested my code in complicated circumstances, by running it and moving around the lab. At first, my program crashed a lot, but after modifications in my code, it crashed less and less. I reached a point where I couldn’t make it crash anymore. I let the program run for several hours, moved with the computer, and Babel was still running fine. I can now tell that the program is solid.

III. How-To

Now that I introduced the work I have done, you might wonder how to use these new source-specific routes. Babel users can now skip to part 7, for the others I will explain how to get a mesh network running. I will show you how to do it via cable. To do it via wifi, I suggest looking at how to configure an ad-hoc network.

    1. Configure your network

The first thing you want to do is to shut down any network manager that is running. For example under Debian: “service  <network manager> stop”. Then to make sure your interface is up, run for example, “ifconfig” in a terminal. You should see something like this:

$ ifconfig
eth0        Link encap:Ethernet  HWaddr 00:11:22:33:44:55
            UP BROADCAST MULTICAST  MTU:1500  Metric:1
            RX packets:0 errors:0 dropped:0 overruns:0 frame:0
            TX packets:0 errors:0 dropped:0 overruns:0 carrier:1
            collisions:0 txqueuelen:1000
            RX bytes:0 (0.0 B)  TX bytes:0 (0.0 B)

lo          Link encap:Local Loopback
            inet addr:127.0.0.1  Mask:255.0.0.0
            inet6 addr: ::1/128 Scope:Host
            UP LOOPBACK RUNNING  MTU:65536  Metric:1
            RX packets:12 errors:0 dropped:0 overruns:0 frame:0
            TX packets:12 errors:0 dropped:0 overruns:0 carrier:0
            collisions:0 txqueuelen:0
            RX bytes:1134 (1.1 KB)  TX bytes:1134 (1.1 KB)

wlan0       Link encap:Ethernet  HWaddr 55:44:33:22:11:00
            UP BROADCAST MULTICAST  MTU:1500  Metric:1
            RX packets:12 errors:0 dropped:0 overruns:0 frame:0
            TX packets:194 errors:0 dropped:0 overruns:0 carrier:0
            collisions:0 txqueuelen:1000
            RX bytes:1442 (1.4 KB)  TX bytes:25177 (25.1 KB)

If eth0 is not available, type “ifconfig eth0 up”.

You can now add an address to your eth0 interface by typing “ip -6 route add __your_address__ dev eth0”. By doing so, you have the address you wanted on the eth0 interface.

$ ifconfig
eth0      Link encap:Ethernet  HWaddr 00:11:22:33:44:55
          inet6 addr: fdbf:e793:18b3::1/128 Scope:Global
          UP BROADCAST MULTICAST  MTU:1500  Metric:1
          RX packets:0 errors:0 dropped:0 overruns:0 frame:0
          TX packets:0 errors:0 dropped:0 overruns:0 carrier:1
          collisions:0 txqueuelen:1000
          RX bytes:0 (0.0 B)  TX bytes:0 (0.0 B)

Babel can now be used.

    2. Compile programs

Before doing the following, you should compile zebra and babel. First, run “./configure –enable-vtysh” in the main directory “quagga”, (we will talk about the vtysh option later on), then go in their respective folders (“quagga/babel” and “quagga/zebra”) and run “make”.

    3. Launch Zebra

You have to launch Zebra and Babel in two separate terminals. To run Zebra, go in the right directory, and type “./zebra”. It is a silent program, so there should be very little outputs.

    4. Launch Babel

To run Babel, go in the babel folder and run “./babel”. This one is more wordy. It will tell everything that is happening on the babel network, but because you don’t yet have any Babel networks running, it should stay silent.

    5. Add Routes

To add routes, you will use the vtysh program we talked about earlier. Go in the folder “vtysh” and run vtysh. Here you can type commands to add routes. Vtysh is an interactive shell where you can type commands to interact with your router. To have a full list of the command, just hit the “?” button. The first command you want to use is “show ipv6 route”, to bring all the current routes. You can then enter configuration by typing “configure terminal”. If you want more information, you can type “?” anytime and see all you can do.

    6. Add Source-Sensitive routes

You can add source-specific routes as well, type “help” in vtysh for more information.

    7. A concrete example

Here is a simple example of a network where source-specific routing is useful:
                                 |——–N3–(
N1———N2———|                  (
                                 |——–N4–(

Here, N3 and N4 are two gateways to the Internet. N1 would like to use N3 or N4 to reach a website. Here is the RIB of N1 and N2 :

N1
—–
Codes: K – kernel route, C – connected, S – static, R – RIPng,
O – OSPFv6, I – IS-IS, B – BGP, A – Babel,
> – selected route, * – FIB route

A>* ::/0 from 2001:660:3301:9208::/64 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:34:51
A>* ::/0 from 2001:660:3301:9209::/64 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:09:56
C>* ::1/128 is directly connected, lo
A>* 2001:5c0:1505:6b00:21b:b1ff:fe83:8d32/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:49
A>* 2001:5c0:1505:6b00:21b:b1ff:fe83:8d3b/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:5c0:1505:6b00:21b:b1ff:fe83:8d3f/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:5c0:1505:6b00:21b:b1ff:fe83:8db3/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:5c0:1505:6b00:a021:b7ff:feba:df57/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:5c0:1505:6b00:e246:9aff:fe4e:91e2/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:03:45
A>* 2001:660:3301:9202::ac17:248a/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:660:3301:9208::1de/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:22:03
C>* 2001:660:3301:9208::2de/128 is directly connected, eth0
A>* 2001:660:3301:9208:b6b5:2fff:feb8:35c3/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:660:3301:9208:e091:f5ff:fecc:7a93/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:660:3301:9208:e246:9aff:fe4e:912e/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:660:3301:9209::1de/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:08:55
C>* 2001:660:3301:9209::2de/128 is directly connected, eth0
A>* 2001:660:3301:9209:e246:9aff:fe4e:912e/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:31:06
A>* 2001:41d0:1:f19f:21b:b1ff:fe83:8d32/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:49
A>* 2001:41d0:1:f19f:21b:b1ff:fe83:8d3b/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:41d0:1:f19f:21b:b1ff:fe83:8d3f/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:41d0:1:f19f:21b:b1ff:fe83:8db3/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:41d0:1:f19f:a021:b7ff:feba:df57/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:41d0:1:f19f:e091:f5ff:fecc:7a93/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:41d0:1:f19f:e246:9aff:fe4e:912e/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:41d0:1:f19f:e246:9aff:fe4e:91e2/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:03:45
A>* 2001:41d0:1:f19f:e291:f5ff:fecc:7a00/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
A>* 2001:41d0:1:f19f:e291:f5ff:fecc:7abd/128 [95/0] via fe80::868f:69ff:fef0:338e, eth0, 00:44:53
C>* fe80::/64 is directly connected, eth0
—–

N2
—–
Codes: K – kernel route, C – connected, S – static, R – RIPng,
O – OSPFv6, I – IS-IS, B – BGP, A – Babel,
> – selected route, * – FIB route

A>* ::/0 from 2001:660:3301:9208::/64 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:46:52
K>* ::/0 from 2001:660:3301:9209::/64 via fe80::e291:f5ff:fecc:7a93, wlan0
C>* ::1/128 is directly connected, lo
A>* 2001:5c0:1505:6b00:21b:b1ff:fe83:8d32/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:5c0:1505:6b00:21b:b1ff:fe83:8d3b/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:5c0:1505:6b00:21b:b1ff:fe83:8d3f/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:5c0:1505:6b00:21b:b1ff:fe83:8db3/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:5c0:1505:6b00:a021:b7ff:feba:df57/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:5c0:1505:6b00:e246:9aff:fe4e:91e2/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:08:09
A>* 2001:660:3301:9202::ac17:248a/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
C * 2001:660:3301:9208::1de/128 is directly connected, eth0
C * 2001:660:3301:9208::1de/128 is directly connected, wlan1
C>* 2001:660:3301:9208::1de/128 is directly connected, wlan0
A>* 2001:660:3301:9208::2de/128 [95/0] via fe80::222:15ff:fe80:d0da, eth0, 00:07:25
A>* 2001:660:3301:9208:b6b5:2fff:feb8:35c3/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:660:3301:9208:e091:f5ff:fecc:7a93/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:660:3301:9208:e246:9aff:fe4e:912e/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
C>* 2001:660:3301:9209::1de/128 is directly connected, wlan0
A>* 2001:660:3301:9209::2de/128 [95/0] via fe80::222:15ff:fe80:d0da, eth0, 00:07:25
A>* 2001:660:3301:9209:e246:9aff:fe4e:912e/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:43:06
A>* 2001:41d0:1:f19f:21b:b1ff:fe83:8d32/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:41d0:1:f19f:21b:b1ff:fe83:8d3b/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:41d0:1:f19f:21b:b1ff:fe83:8d3f/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:41d0:1:f19f:21b:b1ff:fe83:8db3/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:41d0:1:f19f:a021:b7ff:feba:df57/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:41d0:1:f19f:e091:f5ff:fecc:7a93/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:41d0:1:f19f:e246:9aff:fe4e:912e/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:41d0:1:f19f:e246:9aff:fe4e:91e2/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:08:09
A>* 2001:41d0:1:f19f:e291:f5ff:fecc:7a00/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
A>* 2001:41d0:1:f19f:e291:f5ff:fecc:7abd/128 [95/0] via fe80::e246:9aff:fe4e:912e, wlan1, 00:56:53
C * fe80::/64 is directly connected, wlan1
C * fe80::/64 is directly connected, wlan0
C>* fe80::/64 is directly connected, eth0
—–

In this example, N1 has two addresses A1 (2001:XXX:XXXX:9208::2de) and A2 2001:XXX:XXXX:9208::2de), it can send packets and choose A1 or A2 as source. All the packets will go to N2, which will forward them. But N2 implements source-specific routing and even if two packets have the same destination, it will read their source and send them to different locations. In our example, it is N3 and N4. Once on the Internet, these packets behave identically to any other packet. This is due to the fact that the source is not handled by routers not implementing source-specific routing. Here are the traces of the packets with two different sources :

traces :
———
ping6 2001:4860:4860::2de -I 2001:XXX:XXXX:9208::2de

My traceroute  [v0.82]
computer (::)                                                                                  Mon Aug 18 18:55:27 2014
Keys:  Help   Display mode   Restart statistics   Order of fields   quit
Packets               Pings
Host                                                                         Loss%   Snt   Last   Avg  Best  Wrst StDev
1. 2001:XXX:XXXX:9208::1de                                  0.0%    62    0.8   1.0   0.6   2.7   0.5
2. 2001:XXX:XXXX:9208:e246:9aff:fe4e:912e           0.0%    62    3.1   3.7   2.3  14.5   1.9
3. 2001:XXX:XXXX:9202::ac17:2ffe                         0.0%    62    3.0   3.9   2.4  21.2   2.6
4. 2001:XXX:XXXX:80fc::4                                      0.0%    62    2.8   4.4   2.7  12.5   2.0
5. 2001:660:2401:2001::1                                             0.0%    62    4.8   6.2   2.9  32.3   5.5
6. 2001:660:3300:1004:0:82:0:2200                               3.2%    62    4.0   4.4   3.0   8.3   1.5
7. 2001:660:7903:124:1::1                                            8.1%    62    9.2  11.9   6.0  70.5  11.9
8. 2001:660:7903:2:2::2                                               4.8%    62   12.9  12.1   9.5  18.7   1.4
9. 2001:660:7903:159:1::1                                            0.0%    62   16.0  17.1  14.1  35.8   3.4
10. ???

ping6 2001:4860:4860::2de -I 2001:XXX:XXXX:9209::2de

My traceroute  [v0.82]
computer (::)                                                                                  Mon Aug 18 18:56:07 2014
Keys:  Help   Display mode   Restart statistics   Order of fields   quit
Packets               Pings
Host                                                                         Loss%   Snt   Last   Avg  Best  Wrst StDev
1. 2001:XXX:XXXX:9208::1de                                   0.0%     5    0.8   1.3   0.8   2.6   0.7
2. 2001:XXX:XXXX:9208:e091:f5ff:fecc:7a93             0.0%     5    3.1   3.1   3.0   3.2   0.1
3. 2001:XXX:XXXX:9208:e246:9aff:fe4e:912e             0.0%     5    3.0   3.6   3.0   4.6   0.8
4. 2001:XXX:XXXX:9202::ac17:2ffe                           0.0%     5    4.7   5.0   3.8   6.1   0.9
5. 2001:XXX:XXXX:80fc::4                                        0.0%     4    6.2   9.2   3.1  23.9   9.9
6. 2001:660:2401:2001::1                                               0.0%     4    5.6   4.2   3.1   5.6   1.3
7. 2001:660:3300:1004:0:82:0:2200                                 0.0%     4    6.6   5.4   3.4   6.6   1.4
8. 2001:660:7903:124:1::1                                              0.0%     4   96.7  30.4   7.5  96.7  44.2
9. 2001:660:7903:2:2::2                                                  0.0%     4   11.8  20.3  11.6  45.9  17.0
10. 2001:660:7903:159:1::1                                             0.0%     4   18.0  23.5  15.8  30.2   7.6
11. ???
———
The important thing to notice here is that the two traces don’t use the same first router. After that, the routes are quite alike because routers quickly get the packets on the external network and they are then treated as normal packets.

You can find my branch of the Quagga project here: https://github.com/OFabre/ss-babel
And as our web server at university got shut down recently, I moved my blog here: http://ofabre.github.io/

I really appreciated working on networking and I will try my best to continue my work in the Quagga project.

GSoC : Source-Sensitive Routing

Posted on by Olden Fabre

The first weeks of my Google Summer of Code project were a little complicated, as I still had exams at university, and I was not really aware of what mesh networks were about.  I also needed a little time to get to know network and routing better, both pratically and theorotically.

At the beginning, in order to understand quagga and babeld, Iread a lot of documentation on the routing topic including theoretical papers and some RFCs, while also browsing the code of both babeld and quagga.

On the other hand, I have been able to experiment mesh routing with the mesh network available at university.  In order to use that network from home, and being able to test my programs at all time, I also established a VPN connection between university and my home computer. By doing so, I can connect to the university’s babel network at any time. I have also been able to understand the functionning of quagga and zebra and to install source-sensitive static routes on a mesh network.

After having spent much time reading the codes of babel, quagga, and babel in quagga, I achieved to use the zebra’s API in babeld and began to add support for source-sensitive routing in babeld. Currently, my code runs and segfaults proudly ! I hope to see the first results of source-sensitive routing with my version of babel, in the worst case, at the end of the week.

At first, my goals were not really clear, but now, I have precise objectives on the short, middle, and long term.  In brief, my short term objectives would be to get a source-sensitive routing Babel running by the end of the week.  After getting a working version of Babel source sensitive, I will implement the same work in RIPng. RIPng is a quite simple protocol and Juliusz and Matthieu told
me it would be a good idea to offer it source-sensitive routing.  And finally, after everything will be tested and running fine, I will be implementing the source-sensitive commands in Babel.  Then, I will complete the documentation about my work. And in the end, the ultimate goal would be to be included in the official repository of Quagga.

If you want more details about the work I did, you can read my blog here : http://ariane.wifi.pps.univ-paris-diderot.fr/~olden/. I posted an entry every week to keep you informed of the progress on the short term. 

Google Summer of Code – Source Sensitive Routing

Posted on by Olden Fabre

Hello everyone,

I am Olden, a master degree student at the Université Paris Diderot. After speaking with Juliusz Chroboczek, one of my teacher, he introduced me to his work on source sensitive routing and offered me to join the Freifunk community to implement it in Quagga. Under the direction of Matthieu Boutier, who has wrote the first implementation of source sensitive routing, I will be working on the integration of that procole in the next release of Quagga.

After discussing with David Lamparter, he informed me that he already implemented most of the necessary functions in Zebra and that the code will be pushed soon on their git repository. I will therefore be waiting a bit before modifying the Quagga code.

But my first aim will be to get used to the Quagga code and see how to include my modifications as easily as I can. I will therefore be waiting for the code of David Lamparter to be pushed on the git repository and then work on it.

During the time I will be waiting for that, I will read the code of Quagga and get used to it for around two weeks and then will be implementing source-sensitive routing into it. If my work is fully functioning, and if I get time afterwards, I will also be looking at the possibility of implementing the same algorithm in OSPF.

I don’t have for now a precise timeline concerning the work I will be doing on Quagga, but I will be posting on a regular basis the progress of my work on a blog. My git repository is not created yet, but I will be sharing its address with the one of my blog as soon as possible.

Thanks again Freifunk for taking me on this project, and see you soon for the beginning of my work !

Olden