From: Jonas Lindberg (jonaslin@cs.washington.edu)
Date: Sun Oct 31 2004 - 13:35:14 PST
Review of A. Khanna, and J. Zinky's "The Revised ARPANET Routing Metric".
By: Jonas Lindberg
In this paper from 1989, the authors present and discuss improvements to the
SPF routing algorithm installed in ARPANET in 1979. The introduction
contains a description of the original SPF algorithm (called D-SPF). The
authors then continue with presenting and motivating their revised link
metric. Finally they show some performance results that indicate that their
improved algorithm, HN-SPF, is better than D-SPF.
The main problem with D-SPF is that it can experience routing oscillations
when under heavy load. The authors clearly explain the reason for this. It
is a consequence of using instantaneous values (rather than average) as
metric in combination with a not-so-good formula for calculating the cost of
links. The idea behind their suggested improvements is to make the algorithm
less sensitive to queuing delays for heavily loaded links. This is achieved
by limiting relative metric changes in the following way: use an average
measured link delay value (instead of the instantaneous value); limit
maximum and minimum change in link costs. The improved algorithm, which uses
these reversed metrics, is called Hop-Normalized SPF.
The most important contribution of this paper is of course the suggested
HN-SPF, which in fact led to significant performance improvements. This
contribution makes the paper relevant and it was also quite enjoyable
reading. It was interesting to read how they managed to improve performance
with rather small changes. I think the paper is overall well written. May be
the part in which the performance is presented is a little short.
This archive was generated by hypermail 2.1.6 : Sun Oct 31 2004 - 22:35:47 PST