Thursday, 28 August 2008

Ad-hoc network and Pro-active Routing Protocols Part 1 : AWDS and Babel.

Ad-hoc network
- An ad-hoc (or "spontaneous") network is a local area network or other small network, especially one with wireless or temporary plug-in connections, in which some of the network devices are part of the network only for the duration of a communications session or, in the case of mobile or portable devices, while in some close proximity to the rest of the network. In Latin, ad hoc literally means "for this," further meaning "for this purpose only," and thus usually temporary. The term has been applied to future office or home networks in which new devices can be quickly added, using, for example, the proposed Bluetooth technology in which
devices communicate with the computer and perhaps other devices using wireless transmission.

One vendor offers an ad-hoc network technology that allows people to come to a
conference room and, using infrared transmission or radio frequency (RF)wireless signals, join their notebook computers with other conferees to a local network with shared data and printing resources. Each user has a unique network address that is immediately recognized as part of the network. The technology would also include remote users and hybrid wireless/wire connections.
from: search mobile computing

Ad Hoc Network Routing Protocols Studied
The protocols were carefully implemented according to their specifications published as of April 1998 and based on clarifications of
some issues from the designers of each protocol and on our own experimentation with them. In particular, during the process of implementing
each protocol and analyzing the results from early simulation runs.

Type of protocols
Pro-active Routing (Table-driven)
This protocols maintains fresh lists of destinations and their routes by periodically distributing routing tables throughout the network. The main disadvantages of such algorithms are -

1. Respective amount of data for maintenance.
2. Slow reaction on restructuring and failures.

Examples of proactive algorithms are -
A). AWDS - Ad-hoc Wireless Distribution Service
Ad-hoc Wireless Distribution Service (AWDS) is a layer 2 routing protocol to connect mobile ad-hoc networks, sometimes called wireless mesh networks. It is based on a link-state routing protocol, similar to OLSR.

Principle of operation
AWDS uses a link-state routing protocol for organizing the network. In contrast to other implementations like OLSR it operates in layer 2. That means no IP addresses must be assigned because the unique MAC addresses of the WLAN hardware is used instead. Furthermore, all kinds of layer 3 protocols can be used, like IP, DHCP, IPv6, IPX, etc. The protocol daemon creates a virtual network interface, which can be used by the kernel like a typical LAN interface.

The ad hoc routing protocol list contains a large set of alternatives. However, most of them are academic and do not exist as practical implementations.

B). Babel — a loop-free distance-vector routing protocol
Babel is a 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 uses a variant of ETX link cost estimation rather than a simple hop-count metric.

About Babel

Babel was designed to be robust and efficient on both wireless mesh networks and classical wired networks.

Babel on wireless networks

Babel was primarily designed for wireless ad-hoc networks. Because of that, 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.)

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.

Babel uses a number of techniques to avoid route flapping, the situation in which routers repeatedly switch between two routes of similar quality. This, again, is unlike OLSR, which, being a link-state protocol, cannot reliably implement history-dependent route selection.

Babel enjoys fairly fast convergence. Since Babel uses triggered updates and explicit requests for routing information, it usually converges almost immediately after the link quality measure has completed. In the presence of heavy packet loss, however, converging on an optimal set of routes may take up to a minute or so (with the default update interval of 30 seconds).
Babel on wired networks

Babel will also work 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.

In the absence of mobility (on a stable network with no link failures), Babel over a wired network will generate roughly between 1.2 and 2.4 times the amount of traffic that RIPng would generate, depending on the exact network topology. However, since Babel uses explicit Hello messages and never counts to infinity, its update interval can be set to much larger values.
Babel on embedded systems

Being a distance vector protocol, Babel has extremely modest memory and CPU requirements. I have never seen the Babel daemon appear on either a CPU or a memory monitor.

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 on dual (IPv6 and IPv4) networks.
Formal proofs

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

Technical details

Babel has the following features:

* it is a distance-vector protocol;
* it is a proactive protocol, but with adaptative (reactive) features;
* it senses link quality for computing route metrics using a variant of the ETX algorithm;
* it uses a feasibility condition that guarantees the absence of loops (the feasibility condition is taken from EIGRP and is somewhat less strict than the one in AODV);
* it uses sequence numbers to make old routes feasible again (like DSDV and AODV, but unlike EIGRP);
* it speeds up convergence by reactively requesting a new sequence number (like AODV, and to a certain extent EIGRP, but unlike DSDV);
* it allows redistributed external routes to be injected into the routing domain at multiple points (like EIGRP, but unlike DSDV and AODV).


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

Download the Babel routing daemon (Linux and Mac OS X only, for now).

You can also get my latest (possibly unstable) sources using Darcs by doing

$ darcs get

Babel-aware tcpdump

A patch (due to Grégoire Henry) to make tcpdump aware of the Babel and AHCP protocols is available in my download area.

* Babel's README file.
* The babel(8) manual page.
* Babel's changelog.
* The Babel protocol.

Mailing list
Please subscribe to the Babel users mailing list.

You may browse the archives on Alioth, at Gmane using HTTPand at
from: PPS

No comments: