The Revised ARPANET Routing Metric

Motivation: To dampen routing oscillations and reducing routing overhead
on link bandwidth and PSN CPU by introduction of a revised routing metric.

Key Points:
1)The paper outlines the limitations of bellman-ford algorithm which led
to delay-SPF and the limitations of delay-SPF which resulted in HN-SPF
and hints on some unsolved issues like simultaneous route-recomputation
and scenario of several large flows suggesting a multi-path routing
algorithm.
2) The routing algorithms used SPF for route computation and link metric
for computation of link costs. The assumption of co-relation between
reported delay values and those experienced after re-routing was broken
in heavy load scenarios.
3) Problem was Delay-SPF was too fragile and dynamic in the sense that
it reported wide variations in the values resulting in immediate
updation of routing information which led to the overhead of information
dissemination as well as CPU utilization. Such huge load shedding
resulted in under-utilization of the link subsequently and also resulted
in routing oscillations.
4) HN-SPF took into account more than just delay and introduced bounds
and normalization for the response advertised in the network so that
huge fluctuations be controlled.
5) The approach successfully applied itself to heterogeneous networks
providing more effective usage of bandwidth than in delay-SPF.
6) The changes were restricted to the metric for reasons related to
simplicity of implementation. This highlights the fact that newer
designs should be able to integrate with the exisiting infrastucture
relatively easily in order for their use to be practical.
7) The average link approach seems to give desirable results although in
essence the network should be monitored as a whole with the interplay of
all the links of a live network. More specifically, the assumption that
"flow of traffic on and off the considered link during the process of
determining its equilibrium does not significantly affect the costs of
other network links" breaks in the case of heavy load traffic which is
exactly the case for which HN-SPF was introduced.

Lesson learnt: Small changes can result in substantial improvements.
Received on Tue Sep 19 2006 - 02:31:06 EDT