Review: The Revised ARPANET Routing Metric

        This paper describes the ARPANET routing metric that was introduced in 1987. It starts by briefly describing
 both the distributed Bellman-Ford shortest path algorithm that was originally used, and the Shortest Path First (SPF)
algorithm that was later introduced. The original SPF used the measured delay as the link metric (D-SPF) where the
underlying assumption was that the packet delay measured during an interval was a good predictor of the delay after
re-routing too. This assumption led to several limitations for heavy traffic such as unused (or inefficiently used)
bandwidth and routing oscillations in which traffic shifts between two links rather than being shared between them.
This resulted in a lot of network control traffic and high CPU utilization of the PSN due to frequent routing table updates.
        The revised link metric is based on the idea that the average route should get a good path rather than giving all
routes the best path. The new Hop Normalized metric is a normalized function of delay which takes into account how the
network will respond to changes. The goal is to damp routing oscillations and reduce the routing overhead on the link
bandwidth and PSN CPU, which is done by controlling the changes between successive reported updated values through
averaging, and bounding both the maximum and minimum allowed changes. The paper shows that HN-SPF is stable and more
efficient compared to D-SPF.
        Overall the paper was well written. The authors started with the background and slowly led the reader into the
central topic. However, I felt that the 'Behaviour of SPF' section was not properly motivated.
        
Received on Mon Sep 18 2006 - 17:04:59 EDT