Review - The Revised Arpanet Routing Metric

Review from the paper "The Revised Arpanet Routing Metric"
by Ivan Hernandez

The paper describes the shortcomings of the strict delay metric, then
introduces the new metric used by Arpanet Routing and shows how this
little change solves the routing oscillations and routing overhead on
link bandwidth and PSN CPU associated with the old metric.

The routing decisions of the old metric, delay-SPF (D-SPF), are based
on actual measured link delay values which were calculated during a
previous interval and propagated routing updates. This approach only
works properly under light network traffic, curiously, because in this
scenario the queueing delay is minimal and thus negligible. On the
other hand, under heavy traffic conditions, the queueing delay has a
great impact on the metric, which at the end will be a problem.

The paper shows three factors that influence the inefficient
performance of this approach: The range of permissible delay values is
too wide; there is no limit on the variation of reported delays in
successive updates for a particular link; and, all the nodes in a
network adjust their routes in response to a link metric update
simultaneously. This factors an oscillatory routing behavior, this is
where two links (A and B) that connect two regions are used in an
alternating way, in any given instant most of the routes will use A
and then in the following instant, because of the high delay most of
the routes now will use B. This kind of behavior is undesirable
because the network resources are not used efficiently, we will have
network links over-utilized while others are under-utilized; the
over-utilized links can lead to the spread of congestion; increase in
the number of routing updates, so less bandwidth for the applications
traffic and increase of CPU utilization in the routers.

On the opposite, the new metric, Hop-Normalized (HN-SPF), states that
under heavy loads the goal of routing should change to give the
average route a good path instead of attempting to give all routes the
best path. Of course, some of the routes will be diverted to longer
paths, but at the end this will result in a better use of network
resources. The value for HN-SPF metric is a function of delay that
then is normalized in terms of hops. In order to implement this new
metric, it is enough to change the metric computation module of the
network software, there is no need to make other modifications to the
routing mechanism. The HN-SPF metric is constant when a link is
lightly utilized until the utilization gets above 50%, then the metric
for the link rise in order to shed some of its traffic in a gradual
manner. Additionally, the HN-SPF has mechanisms that prevent the
values from changing by too much and from being to little. We do not
want values so different because this will result in routing
oscillation and we do not want minimum changes because this will
generate frivolous routing updates, and thus CPU and bandwidth
consumption.

The main concern in the paper is to solve two problems: reduce routing
overhead on link bandwidth and in the CPU of the routers (PSN). Both
of these resources were very limited and a very important
constrain. Nowadays we the same problems, but the constraints are not
that narrow. Another important aspect is the benefits of a modular
design and implementation of the routing protocol, this allow an
overall enhancement by just replacing the metric module.
Received on Mon Sep 18 2006 - 22:32:39 EDT