Babel

Babel — a loop-avoiding distance-vector routing protocol

Babel is a loop-avoiding distance-vector routing protocol for IPv6 and IPv4 with fast convergence properties. It is based on the ideas in DSDV, AODV and Cisco's EIGRP, but is designed to work well not only in wired networks but also in wireless mesh networks, and has been extended with support for overlay networks.

See download below for source and binaries.

Reading

Specifications

Human-friendly documents

Peer-reviewed papers

M. Abolhasan, B. Hagelstein, J. C.-P. Wang. Real-world performance of current proactive multi-hop mesh protocols. Asia-Pacific Conference on Communication (APCC 2009), Shanghai, China. 2009.

David Murray, Michael Dixon and Terry Koziniec. An Experimental Comparison of Routing Protocols in Multi Hop Ad Hoc Networks. In Proc. ATNAC 2010. 2010.

Jesús Friginal, David de Andrés, Juan-Carlos Ruiz, Pedro Gil. Towards Benchmarking Routing Protocols in Wireless Mesh Networks. In Ad Hoc Networks, Volume 9, Issue 8, November 2011, Pages 1374-1388.

Jesús Friginal, Juan-Carlos Ruiz, David de Andrés and Antonio Bustos. Mitigating the Impact of Ambient Noise on Wireless Mesh Networks Using Adaptive Link-Quality-based Packet Replication. DSN'2012:1-8. 2013.

Somewhat more tentative:

María E. Villapol, David Pérez Abreu, Carolina Balderama, Mariana Colombo. Performance comparison of mesh routing protocols in an experimental network with bandwidth restrictions in the border router. Revista de la Facultad de Ingeniería U.C.V., Vol. 28, N° 1, pp. 7-14, 2013.

Contact

To contact us, please write to the Babel users mailing list. You may browse the archives on Alioth, at Gmane using HTTP, at Gmane using NNTP, and at mail-archive.com.

There is also a #babel channel on Freenode.

Babel features

If you do not have brains you follow the same route twice. — Greek proverb

Babel's main features are the following:

Babel on wireless networks

Babel is extremely robust in the presence of mobility: only under very exceptional situations circumstances will Babel cause a transient routing loop. (This is unlike OLSR, which will cause transient routing loops just after a mobility event before the new topology information is flooded throughout the network.)

Maluch

In its default operation, Babel uses a link quality measurement that is designed for networks using the IEEE 802.11 MAC. In other words, the paths chosen should be reasonable on any sort of network, but are particularly suitable for 802.11 networks.

When run with the -z 3 command-line flag, Babel will aditionally take radio frequency into account in order to avoid interference.

Babel enjoys fairly fast convergence. Since Babel uses triggered updates and explicit requests for routing information, it usually converges almost immedia­tely after the link quality measure has completed. This initial solution is not optimal — after converging to a merely satisfactory set of routes, Babel will take its sweet time before optimising the routing tables. In the presence of heavy packet loss, converging on an optimal set of routes may take up to a minute or so (with the default update interval of 20 seconds).

Babel on wired networks

Babel works efficiently on wired networks. When the Babel daemon detects a wired network, it will use a larger interval between hellos, disable link quality estimation, and perform split horizon processing.

BabelTool screenshot

Babel on overlay networks

A recently developed protocol extension, Babel-RTT, allows Babel to optimise routing on overlay networks. This is described in detail in Baptiste Jonglez' report and in a draft research paper.

The code is available since babeld-1.5.0. Search for "enable-timestamps" in the manual page.

Babel on dual-stack networks

Unlike most routing protocols, which route either IPv4 or IPv6 but not both at the same time, Babel is a hybrid IPv6 and IPv4 protocol: a single update packet can carry both IPv6 and IPv4 routes (this is similar to how multi-protocol BGP works). This makes Babel particularly efficient and simple to manage on dual (IPv6 and IPv4) networks.

Babel on embedded systems

Being a distance vector protocol, Babel has extremely modest memory and CPU requirements.

(Note however that the current implementation uses somewhat naive data structures. I've done some optimisation of the data structures, and babeld should therefore be able to scale to networks of a few thousand nodes; however, some low-hanging fruit remains, and if you're running babeld on a large network, I'm interested in your profiling results.)

Formal proofs

A mathematician is expected to sit at his computer and think. — Hari Seldon

The most important correctness properties of Babel — loop-freedom and convergence — have been formally proved. This is unlike most other routing protocols, the correctness of which has to be taken on trust.

Download

If you don't know what to do with many of the papers piled on your desk, stick a dozen colleagues' initials on 'em, and pass them along. When in doubt, route. — Malcolm Forbes

There are two implementations of Babel: a standalone daemon and an experimental version integrated in Quagga.

Standalone daemon

Stable tarballs of babeld are available in my download area.

You can get my latest (possibly unstable) sources using git:

git clone git://github.com/jech/babeld.git

Debian and Ubuntu packages should be available in your favourite repository (merci, Stéphane !).

apt-get install babeld

Versions are also included in Fedora Extras and Arch Linux. On other Linux and BSD systems (including Mac OS X), building the daemon is a simple matter of make && make install.

Babel in Quagga

The Quagga version of babeld is available in both the main and the quagga-RE branches of Quagga:

git clone git://github.com/Quagga-RE/quagga-RE.git

The version included in mainline Quagga has a number of limitations.

Related software

BabelWeb, a web interface for visualising Babel routes, fully buzzword-compliant (HTML5, CSS, client- and server-side Javascript), by Gabriel Kerneis. Live demo (currently down).

Tcpdump has support for displaying Babel packets since version 4.2.1 (tcpdump download). Wireshark has support since version 1.7.0 (Wireshark download).

Babel-pinger, a hack to export a default route into Babel for people using DHCP to configure their routers rather than speaking to their upstream provider with a proper routing protocol, is available in my download area.

AHCP is a configuration protocol for mesh networks.