On Routing Algorithms

It is really amazing to know that the ground work for routing algorithms have been laid with ARPANET itself. The distance vector routing protocol and the new improved link state routing protocol etc. have been invented and applied when operating ARPANET. In one of those famous papers, The ARPANET routing algorithm, the BBN folks (who were given the task of setting up, operating and maintaining ARPANET) lay three functional properties of any routing protocol:

  • A mechanism to measure the delay to appropriately allocate a cost to the link
  • A mechanism to reliably distribute the information among the nodes in the network
  • A mechanism to calculate the shortest paths given the costs and the connectvitiy information.

Measuring delay may be very necessary then, but does not sound so anymore given all the high speed links. The cost in case becomes mostly the administrative cost. The algorithm to calculate the shortest path has already been invented by Dijkstra. After this paper was published, and when everybody was thinking everything is fine with the new routing protocol, suddenly something happened in the ARPANET and it collapsed. It turned out that it was a hardware problem, but still the routing protocol could have done something about it to prevent the damage that occured. Radia Perlman (yes, the same brilliant lady who later on invented spanning tree protocol and rbridges) wrote a paper that details how information can be distributed reliably among the nodes in the network. Those foundational principles can be seen even today in the OSPF protocol.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s