From: Alan L. Liu (aliu@cs.washington.edu)
Date: Sun Oct 31 2004 - 17:27:42 PST
The paper describes a newer version of the routing metric used in the
ARPANET, which is better than the old one at increasing throughput while
reducing overall delay.
The paper presents scenarios in which the original delay metric was
ineffective, and the reasons why. For instance, the range of values was
too wide, causing lines to be ignored completely by all sources. This
causes oscillations where a heavily loaded line in one time frame can
become underutilized the next, because everyone switches routes off of
it, potentially overloading another line.
The problem with the delay metric is that it tries to minimize delay
for all flows without regard for the fact that each individual flow will
try to do the same thing. The revised algorithm is designed to find a
good route for the average case, while ensuring that the alternate
routes used are not too much worse. The new hop-normalized metric uses a
hop as a unit of cost. There is a limit to how much the cost can change
between updates, and the range for a line is predefined so that even a
heavily loaded line can never cost more than two additional hops.
The paper makes use of the equilibrium point in control theory. The
iddea of this point is to show stability (or lack thereof). It is clear
that the HN-SPF design prevents the cost from fluctuating too wildly
around the equilibrium point, while the original D-SPF design has no way
of ensuring this.
I thought a few things could have been better covered. For instance,
HN-SPF has eight different line-types, each with their own ranges for
hops. How are these values chosen, and what effect do they have? The
charts showing oscillation tendencies did not make much sense to me. I
was not quite sure how time was represented, because oscillations occur
over time.
An interesting nugget contained in the paper is that HN-SPF is designed
to be dropped in to current routing update code. The authors imply that
if they did not have to design something to easily fit in with existing
software, they would do something else. That raises the question of
whether a better routing update mechanism that avoids the problems that
HN-SPF tries to solve. Maybe this is a stupid question?
This archive was generated by hypermail 2.1.6 : Sun Oct 31 2004 - 17:30:18 PST