From: Danny Wyatt (danny@cs.washington.edu)
Date: Sun Oct 31 2004 - 21:17:26 PST
The Revised ARPANET Routing Metric
Atul Khanna, John Zinky
This paper presents a new cost metric for the existing route calculation
algorithm for ARPANET. That algorithm simply calculates the shortest
path from each node to every other node. The cost for each edge in the
network graph was simply the mean delay over ten seconds for that link.
This resulted in bandwidth wasting oscillations under heavy load, so the
authors propose a new cost metric that both more accurately
characterizes utilization than plain delay and is designed to confront
the observed oscillation problem. Their new metric normalizes link
costs in terms of virtual hops in an unloaded network. Once the cost is
in those terms, they can define upper and lower bounds to the number of
virtual hops a link should be seen as by the shortest-path algorithm.
This allows the cost metric to control (somewhat) the re-routing decisions.
Their metric seems reasonable enough, and it is devised well to cleanly
"plug in" to the existing routing algorithm. However, the
transformations based on a line-type lookup seem very ad hoc and hackish
to me. They compress all variations into 8 discrete line-type classes.
I'm wary of how well those classes could encapsulate all possible line
types, and thus how much room they leave for growth. Additionally, the
choice to limit link cost to a maximum of 2 virtual hops seems sensible
enough, but I'm sure it's tied to the architecture of the ARPANET at
that moment in time. I would have liked to have seen a more general
consideration of the bounds.
Their equilibrium models were interesting. Though not as detailed as
those in the (much later, of course) Katabi paper, at least they existed
at all---unlike some other early papers we've read. Their empirical
validations were also notable for being done through an actual
deployment, not a simulation. But they also show a downside of that
method: its inability to isolate variables and lead to a definitive
conclusion.
This archive was generated by hypermail 2.1.6 : Sun Oct 31 2004 - 21:16:01 PST