Local Rules: Of Ants and IP Routingby Ravi Malhotra, author of IP Routing
During the summer months, I will most likely be on the roof of my apartment building -- gardening, reading, drinking tea, looking around at the skyline of Manhattan, or looking up at the big sky. When the sun gets too hot I might just lie down in whatever shade there is on the dark tar of the roof.
It was during one of these hot spells a couple of summers ago that I began noticing small red ants on the roof. Not just a few ants, but hundreds and hundreds of ants. I traced the ants to cracks in the bricks of the chimney walls. The cracks in the chimney appeared to be the home of the colony of ants I was watching. I watched some more, and it became obvious that the ants were not moving about randomly but moved in an almost straight line between the chimney and a cube of sugar that had dropped off my tea tray. These industrious creatures were carrying tiny white crystals of sugar in their mouths while the ants coming back from the chimney were all empty mouthed. The first surprise for me was that the ants had discovered the shortest path between a food source and their home.
One particularly hot afternoon my kids were running around on the roof with the end of the hose, dousing each other. Before I could warn them that they were too close to a line of ants -- stretching from the chimney to a sugar cube I had purposefully put on the roof -- a big puddle of water landed right smack in the middle of the ant highway! The puddle presented a nice round obstacle to the ants. The ants had two ways around the puddle, one a little longer than the other. In a few minutes the ants had figured out their way around the puddle. This did not surprise me, but what I found miraculous was that the ants had figured out the shorter way around the puddle!
That hot summer I did some research into how ant colonies work. As far as we can tell, individual ants do not have an overall understanding of their universe (the ant colony) or of their purpose in it. Each ant follows local rules, meaning that each ant repeats simple acts, over and over again, based on chemical cues from its neighbors. The chemical is a pheromone, secreted by all worker ants. The local rule that requires each worker ant to follow the path with the highest pheromone concentration explains how ants find the shortest path to a food source.
There are other, more complex examples of ant behavior. Ant colonies in trees are known to migrate from a branch in a tree to a branch in another tree. This stupendous task is achieved by building bridges between the trees, made of ants.
The behavior of ants demonstrates complexity and intelligence without any master planner. Such behavior is not unique to ants. The simple single-celled slime mold displays mysteriously complex behaviors that enable it to survive in hostile environments. This capacity of simple systems to self organize has been applied to such diverse disciplines as urban studies, software development, and cellular biology. An excellent reference in this area is Steven Johnson's Emergence: The Connected Lives of Ants, Brains, Cities and Software.
What does all this have to do with IP routing? Routers, those little entities that make up IP networks, operate using local rules. Collectively, the routers in a network present a robust, dynamic routing infrastructure, adapting to failures and congestion. In other words, the problem of IP routing lends itself to the same bottom-up self-organization as the world of ants and the slime mold.
Like ants performing simple actions based on chemical input from other ants, a router repeats actions based on input from its neighboring routers. The actions of routers are described in detail in the specification of the Routing Protocol, say OSPF or RIP. Just as there is no single ant directing the colony, there is no single router with control of all paths through the network.
The IP routing protocols currently in vogue -- OSPF, BGP-4, RIP, and others -- attempt to find the shortest path between any source and destination pair in the network. These routing protocols solve this problem by assigning static costs to each link in the network and then finding the path with the minimum overall cost between every source and destination pair in the network.
Most implementations of these protocols do not account for variances in congestion due to buffer overloads or router processing delays. Further, some applications prefer a path that maximizes the throughput, whereas others prefer a path that minimizes the delay. These routing protocols do not do a great job of finding the best path for each application type. Several efforts are under way to improve the current IP routing techniques. Some of the more daring approaches are using the new science we have described above, called "Emergence" by Johnson.
IP Routing is about the routing protocols in use today -- OSPF, BGP-4, RIP, and the others. I hope that this analogy with the world of ants will help the student of routing focus his or her attention. The best way to understand routing protocols is to focus on the small, simple acts each router executes. Much like the ant colony, all the work of routing happens through these local rules.
Return to the O'Reilly Network.