From: Michael J Cafarella (mjc@cs.washington.edu)
Date: Sun Oct 31 2004 - 19:15:10 PST
The Revised ARPANET Routing Metric
By Atul Khanna and John Zinky
Review by Michael Cafarella
CSE561
November 1, 2004
Main result:
The authors show that traditional hop delay metrics, when used with a standard
shorted-path-first algorithm, result in crazy oscillating route selection when
a network is under load. They suggest an alternate distance metric that does
not suffer from the same problem.
Strengths of the paper:
From an educational point of view, the paper makes very clear how naive approaches
to selecting the best route can easily lead to wild behavior when networks become
loaded. Metric updates eventually start to operate in sync, and when the metric
changes due to new load information, many routes will be recomputed simultaneously.
It's easy to see how this can lead to all the routes "chasing" low-delay links
that are quickly saturated.
From a research point of view, the paper's strength is in coming up with a fairly
simple metric that stays within the shortest-path-first framework and yet avoids
a lot of the oscillating behavior. It does this by using a larger window for the
link performance period, by disallowing too much change every time the metric is
updated (preventing huge changes in behavior), and by disallowing small but meaningless
changes to the metric value (preventing changes that are unlikely to be productive).
Limitations, other problems:
As with many of these papers, there is no easy mathematical framework with which
to analyze the metric. This is a serious problem, as we can't determine likely
behavior under unseen topologies or load.
Modern relevance, future work:
As we saw in the Kitabi paper, metrics and choosing routes is a critical part of
engineering a better Internet. Some of the ideas here, like averaging over a long
window to minimize the variance, are found in modern work. But it seems like
the field has consumed this paper and moved on.
This archive was generated by hypermail 2.1.6 : Sun Oct 31 2004 - 19:15:11 PST