Loop-free Internet routing using hierarchical routing trees
Shree Murthy, Jose Joaquin Garcia-Luna-Aceves · 2002
We present a new hierarchical routing algorithm that combines the loop-free path-finding algorithm (LPA) with the area-based hierarchical routing scheme first proposed by McQuillan (1974) for distance-vector algorithms. The new algorithm, which we call the hierarchical information path-based routing (HIPR) agorithm, accommodates an arbitrary number of aggregation levels and can be viewed as a distributed version of Dijkstra's algorithm running over a hierarchical graph. The HIPR is verified to be loop-free and correct. Simulations are used to show that the HIPR is much more efficient than the OSPF in terms of speed, communication and processing overhead required to converge to correct routing tables. The HIPR constitutes the basis for future Internet routing protocols that are as simple as RIPv2, but with no looping and better performance than protocols based on link-states.