(no subject)

This paper describes a modification to the delay metric used in the
ARPANET's routing algorithm that was made primarily to address the
issue of routing oscillations, where paths are alternately under- and
over-utilized while the routing algorithm switches back and forth
between them. This is primarily done through using a geometric
average instead of an instantaneous delay measure and then
linearizing the result.

The paper does an excellent job of outlining the situations under
which routing oscillations occur and the reasons for them. When it
moves into a description of the new algorithm, however, there seems
to be a lack of theoretical explanation, although this may be a
reflection of some of the realities of doing systems and networking
research. While it's clear from their results that the approach
works, it is not entirely clear why it works. My impression is that
the techniques were derived largely through experimentation, and rely
heavily on the correctness of a number of magic numbers. One concern
with any such approach is that as networking technology evolves, it
is not clear that this approach will keep pace, particularly since
the linear curves are predetermined based upon a fairly limited set
of link capacities. An algorithm with more theoretical backing might
be better able to adapt to changing conditions, although I admit my
experience suggests that many approaches that seem sound in theory
don't actually work.
Received on Mon Sep 18 2006 - 21:10:17 EDT