From: Andrew Putnam (aputnam@cs.washington.edu)
Date: Sun Oct 31 2004 - 16:51:38 PST
The Revised ARPANET Routing Metric
Atul Khanna and John Zinky
Summary: The ARPANET routing algorithm relies on a delay metric to
make effective routing decisions. The original delay metric used
measured delay times, and resulted in instability and inefficiency in
the routing algorithm. This paper introduces a heuristic-based delay
metric that helps the same routing algorithm achieve more stable and
efficient routing configurations.
The old delay metric is very simple and makes intuitive sense. By using
the actual delay times between nodes, the routing algorithm can
determine the quickest paths for network traffic. The authors make a
key observation that this metric can fail when network links are
heavily utilized. In light network traffic, switching traffic to faster
links does not tend to change the delay on the faster link
significantly. However, in heavy network traffic the faster link can
quickly get saturated and become a slower link. This results in rapidly
changing network paths and inefficient use of network bandwidth.
The authors realize that the actual numbers produced by the delay
metric are unimportant, but that the ratio of numbers is important. So
the authors develop a new metric based on heuristics that will retain
the good low-delay path characteristics under light network traffic,
but perform well during heavy network traffic.
This paper can be taken as a study in time scales. The time scale of
the delay updates is in the tens of seconds, while the changes to link
utilization reports is nearly instantaneous. This leads to an imbalance
in the delay reported by the delay metric and the actual behavior of
the network. In order to bring these back into balance, either the
frequency of delay reports needs to increase, or the rate of network
reconfiguration needs to decrease. The authors choose the more
manageable and likely more efficient choice of changing the delay
metric to result in slower network adaptation to changes in delay
reports.
Another characteristic key to the effectiveness of the new delay metric
is the limit on the variance of delay in successive reports. The new
metric averages the new measured delay and the previous delay report to
get the new delay report. This prevents rapid changes in the reported
link characteristics which serves to slow the rate of network
reconfiguration.
The way in which the authors choose the delay numbers seems ad-hoc, and
there is no indication that the choices they made are optimal. For
example, 56kbps terrestrial lines are chosen to be half as expensive as
56kbps satellite lines, yet the ratio for terrestrial to satellite
lines on 9.6kbps connections is slightly different. Also, the
difference between 56kbps satellite lines and 9.6kbps terrestrial lines
is small relative to the difference between the two types of 56kbps
lines. If the authors had a good reason to choose the values they
chose, they did not elaborate on that method clearly. Even if the
resulting metric results in improved performance, it will be hard to
tell if that performance is optimal, or how far away from optimal the
performance really is.
The testing methodology certainly does not assist in determining
whether the delay metric performs optimally. Rather than use a closed,
adaptable network configuration to test various configurations, the
authors tested their implementation by deploying it on the actual
Internet. This certainly proves the effectiveness in a real-world
system, but it is dangerous and could not be attempted on the Internet
today. Testing on the real Internet also does not allow for duplication
of conditions, so the resulting changes in performance are not
guaranteed to be due to the changes in the delay metric.
This archive was generated by hypermail 2.1.6 : Sun Oct 31 2004 - 16:51:48 PST