From: Susumu Harada (harada@cs.washington.edu)
Date: Thu Oct 28 2004 - 02:55:20 PDT
"A Revised ARPANET Routing Metric"
A. Khanna and J. Zinky
This paper presents an overview of two previous versions of ARPANET
routing algorithms, namely the original based on Bellman-Ford shortest
path algorithm and the second algorithm called the delay-SPF (D-SPF),
points out their shortcomings, and presents a revised algorithm they call
Hop-Normalized SPF (HN-SPF) to address these issues.
One of the problem with the first version of the ARPANET routing
algorithm, in which each host maintained and broadcasted to its neighbors
its estimates of shortest distances to all other nodes in the network, was
that their link metric was based on the queue size for each link. This
caused several problems, such as great fluctuations in cost estimates,
formation of loopy routes when link metrics change too quickly, and
emergence of routing oscillations.
D-SPF resolved some of these problems by first having the hosts only
disseminate link cost information to each of its neighbors, and thereby
using Dijkstra's forward search algorithm to converge on a set of least
costly routes. It also used delay as the link cost, measuring it by
averaging over several transmissions to each neighbor. However, it turned
out that this predicted delay was not accurate under heavy load, and that
it was too extreme in reporting the cost variation between highly loaded
and lightly loaded links, leading to under/over-utilization of some links.
Finally, it still led to route oscillations given simultatenous route
updates.
With the goal of minimizing this oscillation in mind, the proposed HN-SPF
algorithm limits the range of the change in link's relative cost, and by
averaging the cost over prior routing periods. They also implemented a
self-feedback function mapping link utilization to relative cost metric
such that cost only depended on link utilization at higher loads. This
enabled links to be better utilized even under higher loads.
I thought the paper did a good job of comparing and highlighting key
issues with the evolution of routing algorithms in ARPANET. Their
discussion of the examination of the model transform was quite confusing
however. It appears that the choice of the particular
metric-versus-utilization profile for each of the different link types
were specifically tailored for these particular links. It is not clear
how this can be generalized to an arbitrary network with numerous link
types, and how the profiles update as certain links become unavailable or
available.
This archive was generated by hypermail 2.1.6 : Thu Oct 28 2004 - 02:55:21 PDT