From: Tom Christiansen (tomchr@ee.washington.edu)
Date: Wed Oct 27 2004 - 15:29:31 PDT
This paper presents the challenges in designing network routing protocols
and describes an improvement to an existing routing strategy (SPF). In SPF
(Shortest Path First) the router attempts to route all network traffic
along the path with shortest network delay. This approach works well under
low to moderate load conditions, but when congestion occurs, the SPF
strategy proves inefficient. The proposed improved scheme, HN-SPF, uses SPF
during low, moderate load but uses a new scheme for peak load conditions.
During peak load conditions, HN-SPF will route the network traffic so that
the average delay for all traffic is as low as possible. The proposed
method improved network throughput by 13 % while reducing RTT by 46 %.
In a way the routing dilemma is similar to the bandwidth sharing,
congestion control dilemma we have discussed over the past few weeks. The
difference here is that the routing protocols try to route traffic fairly
between several hosts on the same network, while data transfer protocols
try to allocate bandwidth fairly between hosts sharing the same physical
link. I'm sure a quality of service debate similar to the one we went
through on the data package level could be held for the routing schemes as
well.
It is also interesting to note that the routing protocols fall apart due to
increases in network traffic at about the same time as the data transfer
protocols (TCP in particular) did.
The article provides a good background and motivation description and
provides enough information on previous protocols to allow the reader to
understand why the proposed method would work better. Unfortunately, this
also makes the article relatively long.
The article briefly touches on the stability issue by mentioning routing
oscillations. This seems to be a big deal as I would expect routing
oscillations to result in lower utilization of available routes and network
bandwidth. Thus, I'm surprised that the authors didn't go into greater
detail describing the stability analysis of the proposed protocol. Control
system theory has been around for decades (even in 1989 when this article
was written) so the theory is there... It also seems like the routing
oscillations described could have been limited by using some form of
hysteresis in the cost calculator in the router.
The pseudo code for the HN-SPF scheme is inserted as a sort of footnote and
is not detailed at all.
This archive was generated by hypermail 2.1.6 : Wed Oct 27 2004 - 15:30:21 PDT