Shortest Path Routing

This is a very simple and efficient routing algorithm that is widely used in many forms. The idea is to build a “graph” of the subnet, with each node of the graph representing a router and each arc of the graph representing a physical communication link between two nodes. To choose the best route between a given pair of routers, the algorithm then simply has to find the shortest path between them on the graph.

The figure below shows the modified graph of the subnet computed by node B, displaying the shortest routes from all other nodes to it. Such a graph representing the shortest paths from all sources to a given destination is called a sink tree.

Sink tree

Figure 2: Sink tree

Remember that the sink tree is not computed just once, but is updated from time to time. This is because the individual nodes on the subnet may go up and down from time to time, and the algorithm must account for these changes. Also, excessive traffic on one particular link may render it unfavorable due to transmission delays, and hence an alternate link may be given preference.

The concept of a shortest path differs from algorithm to algorithm, depending on what system of measurement (called a metric) is used. One way of measuring path length is to measure the number of hops. Using this metric, the paths B-A-D and B-A-F are equally long. Another metric is the geographical distance in kilometers, in which case B-A-D is clearly longer than B-A-F. Many such other metrics are possible, such as mean queueing and transmission delay on a link, etc.

Several algorithms for computing the shortest path are known. My program is based on Floyd’s Algorithm. It uses an array to store the list of links from any node to every other node. Using the array then, the algorithm computes the shortest paths between the node on which it is running and every other node and thus forms its sink tree.

The next section gives a detailed explanation of Floyd’s algorithm.