From: Tyler Robison (trobison@cs.washington.edu)
Date: Mon Nov 01 2004 - 00:00:17 PST
This paper discusses some earlier versions of routing metrics used
in the ARPANET, some of the problems that these faced, and then goes into
a revised metric that helps alleviate these problems. The revised metric
is used in place of link delay for the metric in the shortest path first
algorithm; the same algorithm is used, and only the cost of the links is
changed by this metric. In the SPF algorithm, the cost of each link is
sent to all hosts on the network, and they use this information along with
Dijkstra's algorithm to determine the shortest path to any destination.
D-SPF actually works well for the most part, but when the network is under
heavy loads 'routing oscillations' are caused as many hosts may choose to
transmit on a relatively unused link, so they all do so and heavily load
that link, then all choose another, and so on. The revised metric was
created with this in mind, and is meant to prevent such problems.
Essentially, instead of the delay, a function of the delay is used for the
link cost. The process involves taking the average of the delay over a 10
second window, and making sure that the change of the rate falls within a
certain maximum and minimum; the measure can't jump quite as much at one
time.
The paper feels pretty solid; the arguments about D-SPF failing at
heavier loads makes good intuitive sense, so it does appear to be solving
a very real problem. The results are especially impressive given the
performance before and after it was tried on the ARPANET; success in a
simulation is one thing, but good results in a real environment, on a
large scale and over a period of time are much more interesting. Some more
details of the usage would have been nice though (were there other changes
in the network during this time that could have contributed to the results
seen?).
One limitation of the paper is that, apart from the previous
metrics used, no other possibilities are considered. HN-SPF is certainly
an improvement over D-SPF, but is there any evidence that there isn't
something much better to be tried? The paper seems too narrow in its
focus, looking only at this particular problem with the old metric, and
how it was remedied.
This archive was generated by hypermail 2.1.6 : Mon Nov 01 2004 - 00:00:18 PST