Summary: The Revised ARPANET Routing Metric

A. Khanna, J. Zinky, The Revised ARPANET Routing Metric, ACM SIGCOMM 1989.

This paper describes a (then) new metric termed HN-SPF used to compute the
relative value of links on the ARPANET. The previous metric was simply the
average packet delay over a link for some fixed period of time. The paper
explains that this packet delay comes from three sources: queueing delay,
transmission delay, and propagation delay. Under light loads, queueing delay
is small, and therefore the overall link delay is dominated by transmission
(ie. bandwidth) and propagation (ie. latency). As a result, routing
decisions are made using the number and relative quality of the links between
two routers.

However, under heavy loads, queueing delay dominates. Instead of making
routing decisions based on the quality of the pathes, the old algorithm
decides almost exclusively based on the paths' current load, all but
disregarding the number and quality of the links along those paths. This
results in route flapping: a condition where the routing algorithm alternates
between sending all traffic down one path or another, since the unloaded one
always appears vastly better. This results in lower overall capacity, as
various perfectly usable links are kept underloaded.

The replacement metric has several modifications which improve the network's
behaviour under high-load cases while not changing its behaviour under low
loads.

The pseudo-code algorithm seems to make use of statically-set data tables
keyed on "line type". These appear to be constants selected in order to
allow drastically different networking technologies to "play nice" with this
metric. These tables would appear to require manual adjustment as new
networking technologies come online. However, it is hard to argue with
Figure 13... this seems to be a huge improvement over what was in place
before.
Received on Tue Sep 19 2006 - 01:30:44 EDT