From: Michelle Liu (liujing@u.washington.edu)
Date: Sun Oct 31 2004 - 13:54:46 PST
Review of "The Revised ARPANET Routing Metric"
Jing Liu
This paper presents an ARPANET revised routing metric for shortest path first (SPF) routing algorithm. The revised routing metric takes traffic load into account. It especially considers heavy load traffic. While it acts similar to a delay-based metric under light load traffic, under heavy load traffic, it is similar to a capacity-based metric.
In the beginning of the paper, two ARPANET routing algorithms ¾ distributed Bellman-Ford shortest path and Shortest Path First (SPF) are discussed. The distributed Bellman-Ford shortest path uses a link metric, which is an instantaneous sample rather than an average. Each node only gets information from its neighbors and its own estimate of the distance to each of its neighbors. Thus, the performance is far from optimal. Moreover, the rapidly changing of link metric will cause persistent loops and it is potentially unstable. In contrast to distributed Bellman-Ford shortest path, each node of SPF has full knowledge of the topology of the network, thus loops could be avoided for routing. However, SPF is still unstable. This is mainly because of the routing metrics used for SPF. SPF uses individual delay metric.
Individual delay metric causes routing oscillations under heavy loads. In consequence, routing oscillations bring a set of limitations, such as some links are with over-utilization while others are with under-utilization, overhead for route computation, updating and consumption of ink bandwidth by network control traffic, etc. The revised link metric uses mechanisms to relieve routing oscillations and increase utilization of link bandwidth by normalizing the reported cost to take into account how the network will respond to it, limiting relative report value and amount of routing updates. The round-trip delay is correspondingly reduced. Moreover, considering equilibrium of networks, HN-SPF (shortest path first routing using revised link metric) is stable under most conditions and the amplitude of oscillations is limited so that not all traffic is shed from one link.
The principle for the proposal of the revised link metric or the based consideration is the following statement: under heavy loads, the goal of routing should change to give the average route a good path instead of attempting to give all routes the best path. This is what I can learn from this paper. The individual best does not mean overall best or quite often can not achieve overall best.
This archive was generated by hypermail 2.1.6 : Sun Oct 31 2004 - 13:55:03 PST