// The Song Remains The Same

“Well, in our country,” said Alice, still panting a little, “you’d generally get to somewhere else — if you run very fast for a long time, as we’ve been doing.”

“A slow sort of country!” said the Queen. “Now, here, you see, it takes all the running you can do, to keep in the same place. If you want to get somewhere else, you must run at least twice as fast as that!”

— Lewis Carroll’s Red Queen from Through the Looking-Glass

For my Master’s thesis, I did work in Mobile Ad Hoc NETworks (MANETs) and self organizing routing algorithms. At the present time, I can’t post my thesis online as we are waiting to see about some journal publications, but I’d like to talk a little about decentralized discovery in MANETs (however, I have a large article ready to go about my Master’s thesis, so when I get the clearance, it will be posted).

MANETs are decentralized networks that have no leader node or central controller where each node can only hear a subset of all nodes. Every node has to be a good citizen and agree to forward packets for other nodes in order for the network to function. Routing is a key issue in MANETs since a different set of obstacles are faced as opposed to traditional wired networks. There are many different ways that a network can approach the issue of routing, however there are two (main) classes in MANETs: Proactive and Reactive networks.

• Proactive: A proactive ad-hoc network seeks to constantly have the best possible global routing information in its routing tables, updating the routing table as new information comes online.
• Reactive: A reactive ad-hoc network only caches routing information in its tables relative to the routes it has seen recently or needs to forward the current packets in its queue

Beyond the type of MANET, another major designation is how the network routes its packets. There are generally two main types of of routing protocols used in packet-switched networks : link-state and distance vector.

With link state routing each node broadcasts to all other nodes in the network its view of the status of each of its adjacent network links — it sends its map. Each node then computes the shortest distance to each host based on the complete picture of the network formed from the most recent link information from all nodes. This approach is closer to the centralized version of the shortest path computation method, with each node maintaining a view of the network topology with a cost for each link. RIP and OLSR are link state algorithms.

A distance vector routing protocol requires that a router informs its neighbors of topology changes periodically — it sends its routing table. It also informs neighbors when changes are detected. They have less computational complexity and less message overhead. AODV and Termite are distance vector algorithms.

Termite is a biologically inspired routing algorithm for MANETs that is based on previous work in adapting the effects of stigmergy. Termite models how termite colonies lay pheromone to communication in a decentralized manner. The concept of pheromone (as I’ve talked about before) is taken directly from the social insect metaphor where social insects use the chemical pheromone as a way to communicate indirectly. Termite piggybacks pheromone on normal network traffic which “trains” the network in an “on-line” manner. A more common technique is to send special packets out with the purpose of updating routing information around the network.

Termite is based on stigmergy powered by digital pheromone, which creates patterns of self organization in the ad hoc network. Termite was developed by Martin Roth and Stephen Wicker at Cornell. Distance vector algorithms such as Termite use routing tables in order to choose a next hop for a packet. Each Termite node has a pheromone table (a routing table) in which it lists the neighbors that the node can hear locally. Termite uses this routing table, which has a goodness rating for taking a neighbor node as the next hop of a path towards a destination node, as a way to probabilistically choose a next hop for the packet (the higher the pheromone rating for a neighbor+destination pair, the higher the chance that that neighbor will be chosen for the next hop “towards” the destination). In Figure 1 and 2 below, we see how a packet traveling from the source node 0 to the destination node 6 updates the pheromone table at node 6 on its final hop.

Figure 1: Packet movement through Termite network. A packet moves from node 4 to node 6 on its final hop to the destination node 6.

Figure 2: Pheromone table update. As the packet in Figure 1 hops to node 6, node 6 updates its pheromone table to reflect the incoming packet’s information. The pheromone table is updated such that neighbor node 4’s destination entry for node 0 (source node) has its value adjusted. The rows in node 6’s pheromone table reflect the nodes that node 6 can hear locally. The destinations are nodes that node 6 knows about.

As packets move from node to node (they are routed at each hop), they follow the “pheromone gradient” that is relevant to their destination. The higher the level of destination pheromone for a next hop neighbor, the more likely a packet is to be routed towards the destination via that neighbor. Packets also carry a pheromone factor which represents the quality of the path that the packet has traveled and influences each node’s pheromone table that the packet passes through. The pheromone table for each hop is influenced by the amount of pheromone on the packet (the pheromone table is updated “towards” the source (as the destination in the table) and the previous hop (as neighbor that is updated). In this way, Termite updates node pheromone table in an on-line manner with no special control traffic.

If a destination node is requested that the forwarding node has no entry for in it’s pheromone table, the packet is stored in a queue, and a Route Request (RREQ) packet is broadcast. A RREQ packet is forwarded to neighbors who check to see if they have an entry for the requested destination. If the node does in fact have an entry for the requested destination, it generates a Route Reply (RREP) packet and sends it back towards the source node (node which generated the RREQ). At each hop the RREP influences the pheromone table so that the originator of the RREQ is linked with the node that had a next hop for its required destination. When the RREP reaches the source node, the source node’s pheromone table is updated and the queued data packet is forwarded.

The effects of the pheromone based probabilistic routing system with a RREQ / RREP discovery mechanism allow Termite to be flexible and robust in the face of many types of deployment climates. Just like with social insects foraging for food, Termite can endure and thrive in uncertain conditions where tradtional techniques would fail. Termite is a very interesting application of biologically inspired systems that use nature to find good engineering solutions. These types of biologically inspired decentralized systems show how emergence can be leveraged in technology. Kevin Kelly has an interesting take on the strategy of these biologically inspired system in that:

A network nurtures small failures in order that large failures don’t happen as often

— from the book Out of Control: The New Biology of Machines, Social Systems, & the Economic World by Kevin Kelly

These systems bend, but they rarely break. Highly linear, clockwork type systems are rarely this robust in the face of uncertainty (not that they don’t have their strengths). I see ad-hoc networks as a metaphor for a lot of different areas of technology and complex systems. Decentralized discovery seems to me as if it can be useful in a lot of different places.

Something that has really interested me is the parallel between ad-hoc networks and the emerging ad-hoc nature of today’s web of linked data. The more I dig, the more I see similarities in the development of a decentralized ecosystem that has value in how it is interconnected. As we’ve seen with Termite, there is also tremendous value in a system that is interconnected, yet loosely coupled.  Something I want to explore further is how we can add small properties to the web at the “node” level that give it more decentralized robustness, more ways to auto discover itself.