Review: The Revised ARPANET Routing Metric

Paper: The Revised ARPANET Routing Metric

Name: Robert Danek.
Course: CS2209, Fall '06.

    This paper provides a detailed explanation of a revised link metric
used in routing in ARPANET. The authors start by examining a history of
the different routing algorithms and metrics that were used in ARPANET,
and illustrating some of their problems. They then explain the new
routing metric and provide details on how it solves the problems of the
preceding metrics.

    The distributed Bellman-Ford routing algorithm was the first routing
algorithm used on the ARPANET. Its purpose was to calculate shortest
path between nodes, where the distance between any two neighbouring
nodes was based on an associated "link metric." Bellman-Ford used as its
metric an instantaneous sample of the queue length. This turned out to
be poor choice of metric, and the resulting problems included:
suboptimal routes being found, formation of routing loops, and routing
oscillations.

    The algorithm that replaced Bellman-Ford was the Delay-Shortest Path
First (D-SPF) algorithm. The Shortest Path First algorithm was based on
Dijkstra's algorithm, and the distance between neighbouring nodes (the
link metric) was the average total delay between nodes. This algorithm
with its new link metric solved the problems of Bellman-Ford, but
introduced a new one. Under heavy load, it was possible that the
shortest path found by the algorithm could oscillate frequently between
two different paths.

    To solve this problem of routing oscillations, the Shortest Path
First algorithm was kept, but the link metric was revised. The new
metric, called the Hop Normalized metric, was still based on total
delay, but it underwent a number of transformations. The end result was
that routing updates now work as follows: when a particular link is
heavily loaded, all shortest paths will not be updated to go through a
link that has no load on it. Instead, routes that have a slightly longer
path will move away from using the heavily loaded link, but others will
keep using the same link. This process will repeat in subsequent routing
periods as long as the link is heavily loaded.

    The paper goes on to describe a number of issues when the network
has heterogeneous trunking, and how the link metric needs to be
normalized to take this into account. The last two sections of this
paper discuss modelling the equilibrium behavior of SPF and the
performance of the Hop Normalized metric in ARPANET. The performance
results were very positive, with a significant reduction in round-trip
delay time being found when compared against using an earlier metric.

   
Received on Mon Sep 18 2006 - 22:13:34 EDT