From: Rosalia Tungaraza (rltungar@u.washington.edu)
Date: Sun Oct 31 2004 - 21:27:40 PST
This paper describes the Shortest Path First (SPF) algorithm and its two
variants; the Delay-SPF and the Hop Normalized SPF (HN-SPF). Both
algorithms are used in networks for routing purposes in which they try to
find the best (cheapest) and thus shortest path for a packet to traverse
the
network from one node to another. Their major difference is in how they
define the best path. The D-SPF defines the best path to be any path that
will minimize the delay of the packet from one node to another, while the
HN-SPF defines the best path in a similar way, but also takes into account
issues such as link utilization, line-type, and line-speed.
The HN-SPF algorithm was meant to be an improvement to the D-SPF
algorithm. Hence, a means to reduce the shortcomings of the latter
algorithm, which included the fact that under heavy traffic much network
resources was wasted due to their inefficient allocation, and the
continuous possibility of congestion because some subnets were
over-utilized.
One of the successes of this paper and thus the HN-SPF algorithm is that
it ended up being an improvement to the D-SPF algorithm. For instance,
when the performance of both types of algorithm was tested by taking into
account their behavior at system equilibrium states, the following was
seen: the D-SPF tended to be either oversubscribed when the system (link)
has heavy traffic and idle when the system had light traffic at
equilibrium. On the other hand, the HN-SPF tended to be relatively stable
(oscillates around it equilibrium) in both situations at equilibrium.
As stated in the paper, one of the limitations of the HN-SPF algorithm is
that it is mostly effective when network traffic contains several small
node to node flow. Thus, I think one possible future work is to either
improve this algorithm further to make it equally effective in other
scenarios as well or to come up with a completely new algorithm that can
do so i.e. a multi-path routing algorithm.
This archive was generated by hypermail 2.1.6 : Sun Oct 31 2004 - 21:27:52 PST