From: Ethan Phelps-Goodman (ethanpg@cs.washington.edu)
Date: Mon Nov 01 2004 - 09:47:04 PST
A Revised ARPANET Routing Metric
Khanna and Zinky
This paper describes updates made to the ARPANET routing algorithms to
reduce oscillatory behavior under high loads. The changes come entirely from
a new distance metric. Previously, a raw average of load over a fixed
interval was used as the distance metric. This worked well for light loads,
but failed under heavy loads. One link reaching congestion could cause all
traffic to move off that link after one routing update, potentially causing
congestion in another link, and creating oscillations. Their solution is
straight-forward (at least in hindsight). The distance metric is smoothed
and bounded by the following mechanisms: a running average is
maintained--essentially a low pass filter; the change from the previously
reported value is capped; the value is scaled by some link-dependent
normalization; and the absolute value is capped at three times the expected
average value.
These changes are unarguably for the better. However, I found their analysis
unconvincing. They rely on a very simplified model, where only one link
under consideration changes, and the rest of the network is static. How
could they find oscillatory behavior, when they're fixing all but one link?
The data in their graphs seems to be a presentation of how they think the
system would work in theory, not a measurement of any real results. On the
other hand, they cite another paper which carried out a measurement study on
a deployed implementation of their system. One potential problem I saw is
that a variety of normalization parameters have to be set by hand for each
link type. As a network grows more diverse, this becomes more difficult and
less powerful.
This archive was generated by hypermail 2.1.6 : Mon Nov 01 2004 - 09:47:09 PST