From: Daniel Lowd (lowd@cs.washington.edu)
Date: Mon Nov 01 2004 - 07:58:03 PST
This paper presented a clear, intuitive description of the first two
ARPANET routing protocols, along with a more detailed analysis of why the
third version presented necessary and effective corrections to the second.
This paper was easy to read and quite convincing in most of its points:
the example of two lines that alternately have all or no traffic was a
good illustration of previous issues, and the statistics on ARPANET
dropped packets after the change was a good argument for the effectiveness
of the changes.
In fact, I was surprised at how convincing this paper was, given its
limited formalisms and few controlled experiments. Rather than
emphasizing theoretical perfection, it demonstrated real-world usefulness.
The solution also had a hackish feel to it: the authors used qualitative
arguments for rough heuristics, that became a solid algorithm by way of
magic numbers. In one portion of the paper, the authors even explained
that the metric supported up to 8 distinct line types. Huh? 8 line
types? Couldn't individual implementations support any number of line
types they wanted to? On the other hand, if hacks like these yield
effective and understandable systems, who am I to argue? Sometimes what's
best isn't theoretically nice, because what's theoretically nice is
intractable, undefinable, or overly simplified.
Reading this paper also made me wonder what could be done with a different
routing algorithm. For example, is there a way to perform randomized
routing with good expected performance bounds? That is, the probability
of choosing a given link is zero if it induces a loop, and is otherwise
inversely proportional to utilization. This would certainly avoid the
problem of routes switching off of a link.
Overall, this paper was a very readable discussion of routing on the
ARPANET. It remains relevant today both as a description of routing
issues and as a success story of successful system maintenance: as
the operating environment changed, simple modifications of limited scope
were sufficient to meet new requirements. If only everything worked that
well.
This archive was generated by hypermail 2.1.6 : Mon Nov 01 2004 - 07:58:04 PST