From: Lillie Kittredge (kittredl@u.washington.edu)
Date: Mon Nov 01 2004 - 07:46:00 PST
Arpanet routing metric
This paper shows the effect of fiddling with the central metric of the
ARPANET's routing protocol.
At first glance, the link metric for a network doesn't seem like it ought
to matter all that much; as long as it calls bad links bad and good links
good, it'll work, right? This paper shows that fairly subtle changes to
the metric can have substantial effects on routing performance. In this
case, the proposed link metric replaces a metric which performed well
under light traffic conditions and poorly under heavy. The main symptom
was an oscillation of routing paths. This is essentially equivalent to
everybody at once saying "sure is crowded on link A. hey, link B's
empty!" and everybody rushing to B, making it the crowded one. The key
problem is that each node is being greedy; each trying to get the best
path. In the improved algorithm, we try to get the best _average_ route.
The other main problem is the difference between light traffic loads and
heavy; the new metric makes an explicit distinction between these two and
treats them differently.
In the context of computing today, a difficulty with this class of routing
algorithms, regardless of the metric, is that all nodes must know the full
topology of the network. While this is a fairly reasonable assumption in
wired networks, it's less solid to assume in wifi LANs, where nodes may
come and go with fairly high frequency.
This archive was generated by hypermail 2.1.6 : Mon Nov 01 2004 - 07:46:00 PST