Routing paper summary

This paper describes a modification to the D-SPF algorithm, a packet
routing algorithm previously used within routers in the ARPANET
network. The replacement algorithm, named HN-SPF, alters the metrics
for individual link costs without altering the algorithms used for
computing routes.

The paper explains that D-SPF uses averaged delay for each of its
outgoing links as a basis for computing link cost. If the delay changes
sufficiently between successive measurements, a routing update is
generated for the rest of the network. The paper then goes on to
explain how this approach can cause routing oscillations during heavy
use between two or more links and how these oscillations waste bandwidth
and CPU cycles, increase delays, etc. The authors then list what they
believe are the causes of this behaviour: queuing delay dominates the
delay metric, the range of permissible cost values is too wide, there is
no limit on the delta of successive reported delays, etc.

The revised HN-SPF metric effectively changes the routing updates from
reporting delays to reporting a value which is a function of the delay.
This function bounds the reported values of delay, limits the amount by
which delays can change between successive updates, and limits the
frequency of routing updates. Additionally, the delay averages are
cumulative and the reported cost is normalized to account for the line
type, a necessary step for networks with heterogeneous links. This
bounds the amplitude and reduces the frequency of routing oscillations,
gradually shedding routes from oversubscribed links. The theoretical
results and data collected from the real network show considerable
improvements (round trip delay, routing update frequency, path
optimality, etc).

The paper is well written and well presented. The pseudo-code figure
helps in understanding and reproducing the algorithm. The authors do a
thorough job of analyzing the behaviour of HN-SPF for the important
performance measures and independent variables (theoretically and in
practice). This paper shows the potential for moderate changes to
effect drastic performance improvements on even well established
algorithms (D-SPF was in use for 8 years).
Received on Mon Sep 18 2006 - 18:46:53 EDT