From: Charles Reis (creis@cs.washington.edu)
Date: Sun Oct 31 2004 - 20:50:25 PST
A Revised ARPANET Routing Metric
Khanna, Zinky, 1989.
The authors describe the problems with previous routing algorithms and metrics for ARPANET, and they discuss and evaluate the improvements from using a hop-normalized version of the shortest path first (SPF) algorithm. The purely delay-based metric for SPF is shown to cause unstable routing oscillations and underutilize links under heavy loads, since all traffic would be simultaneously routed away from a link once it becomes heavily loaded. The authors designed the HN-SPF metric to treat light and heavy loads differently, optimizing for an average link in heavy loads. HN-SPF also places limits on how much a route can change in each update period to avoid large oscillations. These behaviors improved stability and allowed higher bandwidth utilizations in simulation and practice.
Interestingly, the new routing metric is carefully designed to fit within the existing SPF algorithm, so that only a small portion of the routing architecture needed to be changed. This slightly limited the amount that the authors could accomplish, but notable gains (especially under heavy loads) were still shown. Unfortunately, very little discussion was given about the actual deployment, with the paper merely showing that the switch was flipped in 1987 and benefits were seen right away. The paper did not address whether such a change in the future could be gradually deployed among routers or required all-at-once deployment to be effective.
This archive was generated by hypermail 2.1.6 : Sun Oct 31 2004 - 20:50:24 PST