Not The Dart!

Actually, it is the Dart.

I've been spending some of my free time jotting down my thoughts about how to make a Mesh network truly scalable. At the moment, the most widely implemented mesh network protocol, OLSR, is a flat network. That means it is not heirarchical. That means that every node on the network has information about every other node on the network. So if there are 200 nodes on the network, the routing table has 200 entries. Each entry takes up memory and processor resources. The protocol has to calculate routes and reachability information for each entry.

Basically, more nodes = bad performance.

In network-speak, OLSR is not scalable.

I, and many others, would love to see a massively scalable, zero configuration mesh routing protocol. I would love to be able to take the shrink-wrap off a router, load the firmware, and start mesh-networking straight away. I would like to see mesh networking be accessable by the masses - every device that is capable of networking wirelessly could conceivably participate in a city-wide network cloud.

In the here and now, the Freifunk Firmware (FFF) for the Linksys WRT54G comes closest to this ideal. You can install it to your router, make a couple of configuration changes using the easy-peasy web-based interface, and you're up and running. In the here and now, I believe the FFF offers the easiest and quickest road to a mesh-network roll-out. It is ideally suited to Community Wireless Networks. OLSR is much easier than any other routing protocol I've come across to configure. To be usable by the masses, the routing protocol has to be basically invisible.

But, as I've pointed out, any community network that uses OLSR will sooner or later run into the scalability problem. Even in the face of this problem OLSR is better than any other routing protocol for a community wireless network. Any community network that has 100 or more active nodes is a healthy network. A network with that many participants should be able to sort out it's problems - perhaps by fragmenting the OLSR network into clusters. Fragmenting the network into clusters makes route aggregation possible, but makes mobile roaming between clusters difficult - seamless routing from one cluster to another would be basically impossible.

Clustering is a solution offered by some mesh network protocols. This powerpoint presentation describes some of them. Basically they bring heirarchy to mesh networking. But none of the protocols described are nearly as widespread as OLSR.

OLSR also has the problem of most other network protocols in that it requires manual allocation of IP addresses. When an OLSR router joins a network, it's human owner needs to have given it an IP address that doesn't conflict with any other on the network. So a degree of planning and organisation is required in allocating addresses. This slows down the growth of the network.

To cut a long story short, I've discovered a project that is working towards killing two birds with one stone. It's called the DART Project - Dynamic Address RouTing. The project recognises that static IP addressing slows network growth and and makes node mobility difficult. It proposes that all nodes on the network have dynamically allocated addresses, whilst at the same time having a static identifier so that the node can always be reached no matter what dynamic address it has.

Basically it proposes breaking a long standing tenet of wired networking - address = identity. Under DART, a node's address is simply a marker of where it is currently located within the network topology. If a node moves to a different part of the network, it automatically gets a new address. With current IP routing, chaging a node's IP address causes it to lose it's link to the network. This is bad news for applications like VoIP. DART's dynamic address are to be "wedged" between a node's MAC address and it's IP address. This maintains compatibility with existing network-layer protocols. Nodes can still have IPv4 addresses, but they now no longer represent the nodes location within the network topology. DART routing should be invisible to the IP layer.

DART is also heirarchical. Changes to the local network topology are only signalled to nearby nodes. This reduces the size of the routing table for any one node. This in turn reduces the memory and CPU requirements for all nodes. A nodes dynamic address is changed whenever the node changes it's links to nearby nodes. This results in an address that is nearly always an accurate description of where the node is located, and also means that the most efficient route can be found simply by knowing another node's dynamic address.

Networking gurus will recognise that such a protocol would require lookup tables to make it possible to discover a nodes dynamic address using it's static identifier. The aim of DART is to make it decentralised, so that information like a lookup table is not burdened upon some nodes and not others. The static-to-dynamic lookup table is to be a distributed database. DART uses a clever hashing system to distribute the contents of the table across all nodes on the network.

The DART project promises to have a Linux version released "soon". Let's hope that "soon" is sooner rather than later!