From: Ioannis Giotis (giotis@cs.washington.edu)
Date: Sun Oct 31 2004 - 19:53:21 PST
This paper talks about routing algorithms in the ARPANET. The first
implementations were standard Bellman-Ford shortest path algorithms. The
route delays (costs) were obtained by instant delay sampling. While in
theory, this algorithm is expected to perform well, two main issues caused
inefficiency. First, bursty traffic did not allow reliable measurements of
the actual delay and caused costs to change rapidly, resulting in weird
routing effects. Also, the collective behavior of packets was not taken into
account, resulting in an uneven distribution of the packets towards what
seemed to be the best route for all of them.
The authors present a revised version of the algorithm with certain
"normalizing" improvements. The delay costs are now propagated through the
network slower and the actual measurements are taken over a set time period.
There is also a limit on the delay variation, to handle unreliable
measurements during heavy traffic.
The resulting algorithm is evaluated by finding the algorithm's equilibrium
points that indicate its performance. Some results from a real-life study
are presented to further support the algorithm.
Of course, the performance achieved is questionable in terms of today's
standards. Significantly higher bandwidth links now produce different
variation effects and more advanced delay estimation techniques could now be
used, negating a lot of the motivation behind this paper.
This paper is a great example on why a solution perfect in theory could
become useless in practice by effects not accounted when designing it. It is
also a good example no how small changes can significantly alter the overall
performance in the real world.
This archive was generated by hypermail 2.1.6 : Sun Oct 31 2004 - 19:53:11 PST