From: Karthik Gopalratnam (karthikg@cs.washington.edu)
Date: Sun Oct 31 2004 - 23:40:36 PST
Review: A Revised ARPANET routing metric
This paper presents a new routing metric to aid routing decisions - the
HN-SPF metric. This is intended to fix the instability problems with the
earlier D-SPF metric. The authors note that under heavy loads, the D-SPF
metric, which is based on estimating instantaneous delay from neighboring
nodes, can lead to oscillations in routes, and also causes links to be
underutilized as routes tend to all shy away from heaviliy loaded links at
the same time. The authors' solution to this is the Hop-Normalized SPF
metric, which is based on using a virtual hop as a cost unit for a link, and
then normalizing the cost across various links. This enables the authors to
prove in a nice mathematically rigorous way using equilibrium points, that
the fluctuations of the HN-SPF metric are minimal under heavy load. On the
other hand, this metric performs just as well as the original delay metric
under light loads. Another feature of this solution is that it is orthogonal
to the underlying method of finding routes, and merely adds the (crucial)
delay metric component.
Overall, the authors have done a great job in indenftifying a problem with
the existing ARPANET implementation and proposing an elegant solution.
However, the choice of the parameters for the 8 lines in their proposed
solution, is somewhat of a black art. Of course, it can be argued that this
gives designers more leeway in making things work optimally, but it seems
that these parameters have to be tuned really well for the true strengths of
this solution to be exploited.
This archive was generated by hypermail 2.1.6 : Sun Oct 31 2004 - 23:40:38 PST