(no subject)

Paper Review: The Revised ARPANET Routing Metric

The paper introduces a new ARPANET routing metric which is said to
vastly improve performance under heavy traffic conditions.
Specifically, the new metric attempts to correct routing instabilities
and wasted link/processor bandwidth, a problem which existed under the
previous metric.

The paper begins by addressing routing in the ARPANET. Originally, a
distributed version of the Bellman-Ford algorithm was employed. The
algorithm resulted in persistent loops in the case of a rapidly
changing link metric. To address the shortcomings of distributed
Bellman Ford, a Shortest Path First algorithm was installed resulting
in loop-free and more stable routes. The link metric first utilized
in this scheme (D-SPF) was a measurement of the queuing and processing
delay along with an added transmission and propagation delay.

The focus then shifts to the delay metric (D-SPF) and its limitations.
  For a link metric to be useful, it must be a good predictor of the
link delay encountered after all nodes re-route their traffic based on
the reported value. With D-SPF, the correlation between reported and
actual values was high in a lightly loaded network, but very poor
under heavy traffic loads. Due to the unbounded delay variation in
link costs, the network tended to enter an oscillatory state.

Specifically, the system had several undesirable qualities:
- Available network bandwidth was left unused
- Unnecessary use of long-hop network paths (due to oscillation)
- Large number of routing updates lead to increased PSN CPU utilization

At this point the paper introduces a revised link (HN-SPF) metric
which continues to work with the SPF algorithm. The new metric
normalizes the cost in terms of hops. The link metric makes use of
averaging samples and also sets upper and lower bounds on cost
changes. This effectively solved the oscillation problem. While a
D-SPF scheme was only meta-stable, an HN-SPF scheme converges to the
equilibrium point (it may oscillate with a small, bounded amplitude.
The findings were supported with experimental results from the
ARPANET. The new metric resulted in performance enhancements in all
desired categories.

This paper is well-organized. It is logically organized as each
section naturally flows into the next. The main idea is supported
with analytical and experimental results that are clear and concise.
The paper presents an original idea to solve an existing problem. The
problem it posed was intrinsically difficult as network traffic is
difficult to model and thus to create a metric which works optimally
in every situation is unrealistic. Their solution provably provides a
feasible performance improvement. Routing in networks is an
interesting problem as it is an inexact science and thus this paper,
in my opinion, made a recognizable contribution to network research.

-- Nadeem Abji
Received on Tue Sep 19 2006 - 00:36:27 EDT