Summary: Revised ARPANET Metric

Summary: Revised ARPANET metric

The goal is to devise a revised ARPANET routing metric called "HN-SPN" to
dampen the routing oscillations, reduce routing overhead and PSN CPU.

The paper proposes a revised metric HN-SPF routing algorithm, which
retains the previous SPF algorithm, but only proposes changes to the way
link metric is calculated. Previous algorithms used absolute packet delay
averaged over a period of time as delay metric. While the previous
algorithms worked fairly well under light/medium network loads, they
resulted in routing oscillations under high network loads. The main reason
for this problem is due to the significant influence of queuing delay on
delay computed for a link under heavy loads. This observation was ignored
by previous routing algorithms.

Primarily, there are essentially four changes that differentiate new delay
metric from the old one. (1) Use flooding to disseminate link cost quickly
to every other node (2) Use a transformed value of measured delay instead
of using absolute delay to take network response into account while
calculating delay metric. (3) Placing limits on relative changes between
successive routing updates helps to dampen routing oscillations (and also
to keep oscillating amplitude within a specified range) (4) Use hop
normalization to make routing sensitive to packet delays. Load < 50%, use
constant metric, else if Load > 50%, distribute the traffic in alternate
paths. With these minor modifications to delay metric, new metric achieves
significantly better results in dampening oscillations, reduction of
routing overhead time and better network utilization (indirect effect).

The later parts of paper also show that the behavior analysis and
equilibrium calculations of new metric yielded much better results as
compared to previous algorithms.
Received on Tue Sep 19 2006 - 06:27:42 EDT