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.