IEN 189
ISSUES IN INTERNETTING
PART 4: ROUTING
Eric C. Rosen
Bolt Beranek and Newman Inc.
June 1981
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
ISSUES IN INTERNETTING
PART 4: ROUTING
4. Routing
This is the fourth in a series of papers that discuss the
issues involved in designing an internet. Familiarity with the
previous papers (IENs 184, 187, and 188) is presupposed.
The topic of the present paper is routing. We will discuss
the issues involved in choosing a routing algorithm for the
internet, and we will propose a particular algorithm. The
algorithm we propose will be based on the routing algorithm
currently operating in the ARPANET, called "SPF routing." This
algorithm is described in [1] and [2], which interested readers
will certainly want to look at. Although we will try to make
this paper relatively self-contained, we will of course focus our
discussion on those aspects of the algorithm which might have to
be modified to work in the internet.
Any discussion of the proper routing algorithm to use in a
particular Network Structure must begin with a consideration of
just what characteristics we want the routing algorithm to have.
That is, we must decide in advance just what we want the routing
algorithm to do. Everyone will agree that the routing algorithm
ought to be able to deliver data from an arbitrary source Switch
to an arbitrary destination Switch, as long as there is a
- 1 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
physical path between them. Or at least, the routing algorithm
should make the probability of being able to do this arbitrarily
high. However, this is a very minimal criterion (as indicated by
the fact that everyone would agree to it). There are many other
requirements we must place on the routing algorithm if we intend
to design a robust and high performance Network Structure. We
will present some requirements and some possible routing
algorithms which fulfill the requirements to a greater or lesser
degree. We hope that by the end of this paper, we will have made
a case that our proposed routing algorithm does a better job of
meeting more of the desired requirements than does any other that
we know of.
4.1 Flexibility and Topological Changes
One extremely important, though little noticed, feature that
we should require of a routing algorithm is that it enable us to
make arbitrary changes in the topology of the Network Structure,
without the need to make manual changes in the internal tables of
the Switches. This is a capability that has always existed in
the ARPANET. IMPs can be added, removed, or moved around
arbitrarily, and the routing algorithm automatically adapts to
the new topology without any manual intervention. This seems
simple enough, but it does place some significant constraints on
the nature of the routing algorithm. For example, it immediately
rules out fixed routing. By "fixed routing," we refer to any
- 2 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
scheme where a set of routes to each destination Switch is
"compiled into" each Switch. In fixed routing schemes, there is
generally a "primary route", to be used when the Network
Structure is not suffering from any outages, and a set of
alternate or secondary routes to be used if some component of the
primary route should fail. We know of one network which does use
this sort of fixed routing, and as a result, they are forced to
adhere to a very strict rule which allows them to add or remove
Switches only once every six months. Certainly, we would not
want to build such a restriction into the internet.
Fixed routing also prohibits certain important day-to-day
operational procedures that are often used in the ARPANET. For
example, it is quite common, when an IMP is brought down for
preventive maintenance, to "splice" that IMP out of the network
by wiring together two of its modems. This causes two IMPs that
ordinarily have a common neighbor to suddenly become direct
neighbors of each other. (A similar function can also be
performed by the telephone company, in case the power to the
modems is shut off, or if the site cannot be reached.) This
ability to preserve network bandwidth even when a site is down is
quite important to robust network performance. Yet it is very
difficult, if not impossible, to do this if the network has a
fixed routing algorithm. It is not yet clear to what extent such
day-to-day "firefighting" techniques will be applicable in the
internet, but it certainly does not seem wise to design an
- 3 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
internet routing algorithm which would be too inflexible to
permit the use of such techniques.
Another very useful capability which is difficult to combine
with fixed routing is the ability to create arbitrarily
configured test networks in the lab, and then to connect them to
the real network. This is something that is done quite often in
the ARPANET, usually for the purposes of testing out new
software, and we will definitely need this capability in the
internet in order to test out new gateway software (as well as to
test out patches and bug fixes to the old).
It is also worth noting that implementing a scheme of fixed
routing with a primary route and alternates to be used in case of
outages is not nearly as trivial as it may seem. Remember that
it is not enough for each individual Switch, when its Pathway to
a particular neighbor fails, to pick an alternate neighbor as its
next hop to some destination. Rather, any outage requires ALL
the Switches to pick alternates in a COORDINATED MANNER, so that
the routing produced by the use of the alternate paths is
loop-free. This is quite a difficult problem, and if there are a
large number of Switches and Pathways, any combination of which
could fail, this means that a very large number of alternate
paths must be maintained, requiring a consequently large amount
of table space.
- 4 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
We will not be giving much serious consideration to the use
of fixed routing in the internet. We mention it largely for the
sake of completeness, and because there is a natural tendency,
which we wish to oppose, to suppose that fixed routing must be
simpler, cheaper and more reliable than dynamic routing. This
tendency ignores the day-to-day operational problems involved in
the use of fixed routing, as well as the difficult technical
problems involved the the creation of fixed routing tables.
Preserving maximum flexibility to make topological changes
requires the Switches to be able to determine, dynamically, just
who their neighbors are. (Remember that two Switches of a
Network Structure are neighbors if and only if they are connected
by a Pathway, i.e., by a communications path containing no
intermediate Switch of the same Network Structure.) In the
ARPANET, each IMP is initialized to know how many modem
interfaces it has, and does not determine that dynamically.
However, initialization only tells the IMP how many interfaces it
has; it does not tell the IMP who its neighbor is over each
interface. The IMPs determine who their neighbors are
dynamically, via the line up/down protocol, and a line between
two IMPs cannot come up unless and until each of the IMPs knows
the identity of the other.
The situation in the present Catenet gateways is quite
different. Each gateway has a table of potential neighbors
- 5 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
"assembled in." When a gateway comes up, it attempts to
communicate (via a special gateway neighbor protocol) with each
of the gateways in its pre-assembled neighbor table. Two
gateways are considered neighbors only if this communication is
successful. Gateways will also consider themselves neighbors of
other gateways that communicate with them according to the
gateway neighbor protocol, even if the other gateway is not in
the pre-assembled neighbor table. This means that two gateways,
G1 and G2, cannot become neighbors unless either G1 is in G2's
pre-assembled neighbor table, or G2 is in G1's pre-assembled
neighbor table.
Of course, in a real operational environment, it is very
important to ensure that site-dependent information is not
assembled or compiled in. Rather, it must be separately loadable
(over the network itself) by the Network Control Center, or
whatever equivalent organization we create for operating the
internet. In fact, site-dependent information ought to be
preserved over reload of site-independent information, and vice
versa. (This discipline is followed in the ARPANET.) Designing
the gateways according to this discipline is a very non-trivial
task, which must be planned for by the gateway designers at the
earliest stage of gateway design. Otherwise, we will build for
ourselves a very difficult set of unnecessary operational
problems.
- 6 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
However, it is not a very good idea to have a fixed table of
neighbors in each Switch, even if this table is separately
loadable. This just does not give us the flexibility we desire
for making arbitrary topological changes. If there has not yet
been any difficulty with the Catenet's current scheme, that is
probably because of the small number of gateways and component
networks in the current internet environment. As the number of
gateways increases, the need to have them dynamically determine
who their neighbors are becomes increasingly more important.
However, having gateways discover (dynamically) who their
neighbors are is a more difficult problem than having IMPs
discover who their neighbors are. The interfaces on the IMPs
function as point-to-point lines, so there can be at most one
other IMP on the other end of a line, and any data sent out that
line can be expected to reach just that IMP. Therefore it is not
very hard for an IMP to discover which IMP is at the other end.
An IMP simply sends its identity (a unique number which it reads
from its hardware configuration cards) down the line in a
message, and if the line is operational, the message must reach
the IMP on the other end. For two gateways connected by a
packet-switching network, the problem is more complicated,
because, unlike telephone circuits, a packet-switching network is
not a point-to-point line with a relatively transparent
interface. In order for one gateway to identify itself to
another, it must be able to address the other, using the Access
- 7 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
Protocol of the packet-switching network which serves as the
Pathway between them. This seems to mean that for a gateway to
be able to send its identity to a neighbor, it must already know
the neighbor's name. This seems like Catch-22 -- there is no way
to determine dynamically who your neighbor is, unless you can
address him, but there is no way to address him unless you
already know who he is.
This problem can be made more tractable through the
cooperation of the packet-switching networks underlying the
Pathways which connect the gateways. A packet-switching network
could recognize that certain of its own components (which might
be either Switches or Hosts within its own Network Structure) are
also Switches within a Network Structure which is one level
higher in a hierarchy. For example, in the ARPANET, there might
be some special protocol (call it the "gateway discovery
protocol"), carried out on the host-IMP level, by which certain
hosts identify themselves as internet gateways. Whenever a
gateway connected to a particular IMP comes up or goes down, this
information could be broadcast to all other IMPs. Whenever a
gateway comes up, the IMP it is connected to could tell it which
of the other hosts are internet gateways. In this way, the IMPs
could keep the gateways informed as to which other gateways are
up or down at any particular time. This sort of scheme
eliminates the need for the gateways to know in advance who their
neighbors might be, and moves the responsibility for keeping
- 8 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
track of the gateways and their up/down status to the
packet-switching network itself, which is better equipped to
carry out this responsibility.
Such a scheme would not be very difficult, in principle, to
build into the ARPANET. Information about gateways could be
subsumed into the routing information. That is, an IMP connected
to a gateway could represent the gateway as a stub node, and
report on it as such in its ordinary routing updates. (Of
course, this is only feasible if the number of gateways is
relatively small when compared to the number of IMPs. Otherwise
the additional overhead this would add to the ARPANET's internal
routing algorithm would make the scheme infeasible. However, it
does seem likely that the number of gateways on the ARPANET will
always be much smaller than the number of IMPs.) This scheme
would automatically cause the information about the gateways to
be broadcast to all IMPs as part of the routing updates. (See
section 4.5 for a description of the routing update procedure.)
Each IMP which is connected directly to a gateway could forward
information about other gateways to its own gateway as the
information is received. The most difficult problem might be to
get enough "security" in the gateway-to-IMP protocol so that only
real gateways could declare themselves to be gateways. (Some of
the issues involved in preventing a host from "fooling" the
network into thinking it is a different host than it really is
are discussed in IEN 183. See the discussion of LAD messages.
- 9 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
However, that note does not consider the real issue of security
that arises here.)
This scheme for having gateways dynamically discover their
neighbors through the cooperation of the networks underlying the
internal Pathways of the internet is an important step towards
the solution of the "flying gateway" problem. The flying gateway
problem is the following. Suppose that N is a packet-switching
network which is one of the component networks of the internet.
Now suppose that due to some sort of emergency or natural
disaster, N becomes partitioned into two "pieces", call them N1
and N2, and that this partition is expected to last for a
significant amount of time. If H1 is a Host in N1, and H2 is a
Host in N2, then H1 and H2 will no longer be able to communicate
through the network N. (Of course, H1 and H2 might still be able
to communicate though the internet, if there is an internet
gateway on N1 and an internet gateway on N2, and a route between
these two gateways other than the "direct" route via N. In fact,
the addressing scheme proposed in IEN 188 will automatically
cause traffic from H1 to H2 to be delivered over this alternate
route, AS LONG AS H1 SUBMITS THIS TRAFFIC TO ONE OF THE INTERNET
GATEWAYS CONNECTED TO N1, RATHER THAN TRYING TO SEND IT DIRECTLY
TO H2 OVER THE NETWORK N.) However, in some cases, there may be
no such alternate route, or else its characteristics might be
unsatisfactory. In addition, it must be remembered that the
partition of network N might actually result in the partition of
- 10 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
the internet itself, so that some pairs of Hosts which ordinarily
communicate over the internet can no longer reach each other. In
such cases, it might be desirable, at the level of the internet,
to treat N1 and N2 as separate component networks, and to place
an internet gateway between them so that internet traffic can
flow from N1 to N2. One possible scenario is for this new
gateway to be an airborne packet radio, hence the name "flying
gateway."
If a flying gateway can be connected to both N1 and N2, and
if the network N has a gateway discovery protocol of the sort we
have been advocating, then the flying gateway need merely come up
on N1 and N2, declaring itself to be an internet gateway. The
gateway discovery protocol run in the network pieces N1 and N2
will cause the other internet gateways in N1 and N2 to become
aware that they have a new neighbor, the flying gateway. Once
the gateways in N1 and N2 become aware of their new neighbor, it
automatically begins to participate in the routing algorithm (see
section 4.5 for details of the routing updating algorithm that
brings this about), and routing automatically begins to use the
flying gateway for store-and-forwarding internet traffic. Thus
any partition of the internet is automatically brought to an end.
In addition to using the flying gateway as a transit or
intermediate gateway for internet traffic, it may also be
desirable to use it as a destination Switch in the internet.
- 11 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
That is, it may be desirable to allow the other internet Switches
(gateways) to use the flying gateway as the address to which they
route traffic for Hosts in N1 or N2. This is slightly more
complicated than simply using the flying gateway as an
intermediate Switch. The logical-to-physical address translation
tables in the gateways (we are assuming the addressing scheme
proposed in IEN 188) will not, in general, map any Host logical
addresses into the address of the flying gateway, which after all
is not ordinarily on the internet. However, as long as the
flying gateway indicates that it is a special, flying, gateway,
and as long as this information is made known to all the other
gateways, this problem is simple enough to solve. If F is a
flying gateway, and G is an ordinary gateway, and F and G are
neighbors, then any logical address which maps to G but cannot
currently be reached through any ordinary gateway should be
mapped to F. (As we shall see, the routing algorithm we propose
makes available to each Switch all information about which pairs
of Switches are neighbors.) Attempting to reach the destination
Host via the flying gateway F will either be successful, or else
should result in the return of a DNA message, which would
indicate that the Host cannot be reached from the flying gateway
either. The only remaining problem is for the flying gateway
itself to determine which of the two pieces of the partitioned
network contain some particular Host for which it is the
destination Switch. Any data for destination Host H which
- 12 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
arrives at Switch F can potentially be sent to either piece of
the partitioned network. The situation is no different than the
problem of how an ordinary gateway, which has two Pathways to a
particular Host, one of which is non-operational, decides which
one to use. Note that the individual Hosts do not need to be
aware at all of the existence of the flying gateway, since the
logical addressing scheme automatically finds the right physical
address. Of course, for this mechanism to be at all effective,
there must be a robust and efficient Host-Switch up/down
protocol, which works through the cooperation of the network
underlying the Pathway between Host and Switch.
Unfortunately, not every component network of an internet
can be expected to cooperate this way in a "gateway discovery
protocol." In fact, if two Switches of the internet Network
Structure are connected by a Pathway which is itself an internet,
rather than a single packet-switching network, then this sort of
cooperation in the "gateway discovery protocol" might be
extremely difficult if not impossible. It seems though to be
quite important to get the communications media which underlie
the Pathways to participate in such a protocol, for that
significantly increases both the reliability and the flexibility
of the internetting scheme. It does not seem possible for
Switches which are connected by uncooperative Pathways to
determine dynamically who their neighbors are. In such cases, we
may then have to live with hand-built neighbor tables (as in the
- 13 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
present Catenet), and a protocol which the Switches attempt to
carry out with their neighbors to see which potential neighbors
are really reachable. Networks which do not provide a gateway
discovery protocol, however, cannot be patched together with a
flying gateway if they should partition.
Even for Switches which are connected by cooperative
Pathways, it is desirable to have a protocol which the Switches
attempt to run with each one of their neighbors, to see whether
they really can send and receive data to or from each neighbor.
Suppose, for example, that two Switches are connected by a
Pathway which is a very congested network. In such a network,
the messages which are used to tell the internet Switches who
their "neighbors" are might well be flowing, even though the
congestion prevents ordinary (user) data from flowing. This is
not at all unlikely, if the gateway discovery protocol makes use
of the network's routing updates, which would probably be of much
higher priority than ordinary data packets. Since we don't want
to use this Pathway for internet traffic unless it can carry
data, some independent means of determining this may be needed.
The situation is somewhat more complicated if the Pathway is a
packet-switching network with different "acceptance classes", so
that only certain classes of traffic are accepted at any given
time, depending perhaps on the internal loading conditions of the
network. If a Pathway is only accepting a certain sub-class of
data traffic, any internet Switches which are connected to that
- 14 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
Pathway must be able to determine which classes are being
accepted (presumably the network underlying the Pathway will
inform the Switches as to any access restrictions), and this
information will have to be fed back into the internet routing
algorithm, so that traffic which cannot be placed on a certain
Pathway is not routed there nonetheless.
The reader will doubtless have noticed that these
considerations, of determining who one's neighbors are, and of
determining whether the Pathway to each neighbor is operational,
are quite similar to the considerations adduced in IEN 187 in the
discussion of Pathway up/down protocols to be run between a Host
and a Switch. What we have been discussing is really an
inter-Switch Pathway up/down protocol. The gateway discovery
protocol corresponds to what we called a "low-level up/down
protocol", and the type of protocol discussed in the previous
paragraph corresponds to what we called the "higher-level up/down
protocol."
4.2 Why We Cannot Require Optimality
What else would we like the routing algorithm to do, besides
giving us the maximum flexibility to make topological changes?
Generally, we tend to feel that a really good routing algorithm
should optimize something, delay or throughput, for example.
However, true optimality is really not possible. If we are given
a complete description of a network, including its topological
- 15 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
structure, and the capacities and speeds of all its lines and
Switches, and if we are also given the traffic requirement (as a
Switch-Switch traffic matrix which tells us how much traffic each
Switch will originate which is destined for each other Switch),
and if the packet inter-arrival rates and sizes vary according to
certain specific probabilistic distributions, and if the traffic
is in a steady-state condition, it is just a mathematical problem
to devise a set of routing tables for the Switches which will
minimize the network average delay. Applied mathematicians have
devoted a great deal of effort to devising algorithms to produce
this optimal solution. There are a large number of problems with
attempting to use this sort of "optimal routing algorithm" as
the operational routing algorithm of a network:
1) Packet arrival rates and sizes do not necessarily vary
according to the probabilistic distributions which are
assumed by optimal routing algorithms.
2) Optimal routing algorithms are ALWAYS based on
mathematical models of the relationship between delay and
throughput which are not supported by empirical data.
3) Actual traffic requirements are quite variable, and may
not really approach a steady-state for a long enough
period of time to enable true optimization. Traffic
requirements are also generally unknown, and difficult to
predict or measure.
- 16 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
4) Most algorithms to compute the optimal routes are real
number crunchers, and require large floating point
computers. These algorithms would have to be run in a
central location, producing routing tables for all
Switches, and then distributing them somehow (centralized
routing), with consequent problems of robustness and
overhead.
5) There are distributed optimizing algorithms (e.g.,
Gallager's algorithm), but they are not implementable.
That is, the proofs of these algorithms make assumptions
which could not be made to hold in the real software and
real hardware of a real network. Hence the algorithms
would not be expected to give optimal results (or even
anything close to optimal) in real networks.
Furthermore, such algorithms seem to rely on updating
protocols which are insufficiently robust in the
operational environment. These algorithms also seem to
contain parameters whose precise settings are quite
important to proper performance, but whose most
appropriate values are unknown and quite difficult to
determine.
We realize that these rather brusque comments may make it
seem like we are giving short shrift to the consideration of
optimizing algorithms. We have made these comments simply in
- 17 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
order to state our reasons for not giving further consideration
to such algorithms. Arguing in support of these reasons,
however, would require another paper.
Another problem with optimal routing algorithms which is
more specific to the internet environment has to do with the
requirement that the capacities of the network components be
known. With telephone circuits as the "links", it is possible to
assign a fixed capacity and fixed propagation and transmission
delays to each link. With packet-switching networks as the
"links", it is doubtful that this even makes sense. If two
gateways are connected by the ARPANET, there is no number we can
assign as the capacity of the "link" connecting the gateways!
The amount of throughput that can be sent between two gateways
via the ARPANET is a highly variable quantity, with dependencies
on hundreds of other things going on within the ARPANET. It is
hard enough to get a handle on just what other things the
throughput of a given connection depends on; we certainly can't
express this dependency as a function, or assign numerical values
to the "capacity." This seems to mean that currently known
optimal routing algorithms are really quite useless within the
context of the internet. Of course, they are not too useful even
in individual networks, when considered as the operational
routing algorithm of the network. They are, however, sometimes
useful as a benchmark to which the operational routing algorithms
can be compared. That is, it is a meaningful question to ask,
- 18 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
"how close does SPF routing in the ARPANET come to optimal?",
where "optimal" is defined as the result produced by some optimal
algorithm, run off-line. Within the context of the internet, it
is difficult even to give meaning to this question. There is no
mathematical model of the internet to which we can appeal.
This also raises an interesting question about the design of
the internet topology, i.e., where to place the gateways and how
best to interconnect them. The usual mathematical techniques for
trying to optimize network topological design also assume some
fixed assignment of capacity to the links; it's not obvious how
such techniques can be extended to the internet.
4.3 Some Issues in SPF Routing
Even if we give up the quest for optimal routing, there are
still a number of substantive things we can require of a routing
algorithm. For example, we would like to have some form of
distributed routing, rather than centralized routing, simply for
reasons of robustness. ("Distributed routing" refers to any
routing scheme in which each Switch computes its own routing
table.) What this means basically is an algorithm based more or
less on the routing algorithm of the ARPANET, i.e., an algorithm
which runs in each Switch and computes the shortest path to each
other Switch, based upon (dynamically determined) knowledge of
the connectivity of the internet Network Structure, and an
assignment of "length" to each Pathway that connects two
- 19 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
Switches. Routing algorithms of this sort can be characterized
by three separable components: (a) the algorithm used to compute
the shortest path, given the assignment of lengths to Pathways,
(b) the algorithm used to assign a length to a given Pathway, and
(c) the protocol used by the Switches for sharing routing
information.
The most efficient shortest path algorithm that we know of
is the SPF algorithm of the ARPANET [1,3] (which is basically
just a modification of Dijkstra's shortest path algorithm), and
we propose to base an internet routing algorithm on this. There
are other algorithms for performing a shortest path computation,
but the SPF algorithm seems to dominate them. One possible
alternative to SPF would be something based on the distributed
computation of the original ARPANET routing algorithm (which is
the basis for the current Catenet routing), but we have studied
that algorithm at great length and in great detail and it is
inferior to SPF in a large variety of ways [3]. There are many
other shortest path algorithms (such as Floyd's algorithm, or the
algorithm advocated by Perlman in IEN 120), but the efficiency of
these algorithms does not compare with that of SPF. We will not
consider the issue of choosing a shortest path algorithm any
further.
In the ARPANET, the "length" assigned to a line is just the
average per-packet delay over that line during a preceding period
- 20 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
of ten seconds. The current Catenet routing algorithm assigns a
length of 1 to each Pathway, irrespective of the delay. Other
possible assignments of lengths to Pathways are also possible.
We will recommend the use of measured delay as the best metric
for the internet routing algorithm to use, and we argue for this
proposal in sections 4.3.1 and 4.3.3. Section 4.3.2 covers the
related topic of "load splitting." (One purpose of that section
is to show that the two topics are indeed related, and in ways
more subtle than generally realized.) In section 4.4, we discuss
some of the issues in the design of an algorithm to measure the
delays.
In the ARPANET, a routing update generated by an IMP A
specifies the average per-packet delay on each of A's outgoing
lines. Every update generated by an IMP is sent to every other
IMP in the network, not just to the neighboring IMPs, as in the
Catenet routing algorithm. This updating protocol, and its
applicability to the internet, are discussed in section 4.5.
Although a routing scheme can be divided into a number of
separable components, it is important to keep in mind that the
ultimate characteristics of the routing scheme will result from
the combination of the components. A routing scheme must be
judged as a whole. The reader should try to focus throughout on
how the components work together, and resist the temptation to
judge each component separately.
- 21 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
4.3.1 Min-Hop Routing (Why Not to Use it)
The simplest routing scheme which is based on having each
Switch compute its shortest path to each other Switch is
"min-hop" routing. In min-hop routing, all Pathways are assigned
unit length, so that the shortest path between two Switches is
just that path which has fewer Pathways than any other.
(Generally, ties are broken arbitrarily.) This sort of routing
is used in the current Catenet, where traffic is routed through
the fewest possible number of intermediate networks (or
equivalently, through the fewest number of intermediate
gateways.) This form of routing is quite simple, and does not
require us to worry about anything as complicated as detecting
changes in load or delay in remote components of the Network
Structure. Such changing conditions within the Network Structure
have no effect at all on the routing. This form of routing can
be done with the minimal amount of overhead (in terms of the need
to send routing updates from Switch to Switch). Updates need to
be sent only when the Pathways go down or come up. Any algorithm
which attempts to be more responsive to changing conditions in
the Network Structure than min-hop routing still needs these
up/down updates, plus more besides. Min-hop routing is
definitely what one would use if one wanted to put in a "quick
and dirty" routing algorithm, and put off worrying about
complexities until some unspecified later time. It is also
possible to argue for min-hop routing in the internet on more
principled grounds, as follows:
- 22 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
"In general, it is not unreasonable to expect that the more
component networks an internet packet goes through, the less
likely it is to get to its destination, and the longer its
delay is likely to be, if it does reach its destination. We
might expect that the number of component networks a message
goes through would generally correlate fairly high with the
delay of the message, and would generally correlate fairly
low with the obtainable throughput of a host-host transfer."
Unfortunately, this sort of reasoning is only valid when
applied to a Network Structure consisting of homogeneous
Pathways, which have similar characteristics with respect to
delay, throughput, and reliability. This is rather unlikely to
be the case in the internet, whose distinguishing characteristic
is the heterogeneity of its Pathways. Where the Pathways of a
Network Structure have widely varying characteristics, delay and
throughput are not very likely to correlate well simply with the
number of hops.
It is true that the delay-oriented routing of the ARPANET
generally gives the min-hop paths. (Remember, though, that the
ARPANET, unlike the internet, has generally homogeneous
Pathways.) Min-hop routing is all right for the "normal" case,
where there are no areas of congestion in the network or
internet, no areas where the delay is unusually high compared to
other areas. Routing, however, is no different from other
computer system applications, in that a scheme that works well
only in the normal case just is not robust enough to be
satisfactory. (Think of a magnetic tape driver which works in
the normal case, where no tape errors are encountered, but which
- 23 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
crashes the system in the presence of "unusual" events, like
errors on the tape. Such a driver may be acceptable if one
accesses one tape a month, but not if one needs to read or write
ten tapes a day. The analogy is that min-hop routing may perform
acceptably in an experimental network with little traffic, but is
much less likely to be acceptable in a heavily loaded operational
network.) It is extremely common for some area of the network to
be much more congested than another, so that traffic flows which
traverse a particular area experience a very much longer delay
(and lower throughput) than traffic flows which avoid that area.
Significant imbalances in load cause significant reductions in
the correlation between hop-count and performance. Such
imbalances may not be present in a network initially, but if the
ARPANET experience is any indication, imbalances start to occur
with increasing frequency as network utilization grows. If the
routing algorithm cannot account for such imbalances, network
performance problems will start to occur with ever-increasing
frequency as the network gains more users. This was our
experience with the original ARPANET routing algorithm. For all
its widely publicized faults, it provided generally acceptable
performance as long as the network was very lightly utilized, but
its failures became more and more evident as the ARPANET shifted
from a research prototype to a communications utility. If we
expect our network or internet to be heavily used by real users
who are sending real data that they really need for their
- 24 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
applications, OUR ROUTING ALGORITHM WILL HAVE TO BE ROBUST ENOUGH
TO DETECT EXCEPTIONAL CONDITIONS AND TO ROUTE THE TRAFFIC IN SUCH
A WAY AS TO MINIMIZE THE EFFECT OF THE EXCEPTIONAL CONDITIONS.
IF AREAS OF THE NETWORK BECOME CONGESTED OR EXPERIENCE UNUSUALLY
LONG DELAYS, THEN WE HAVE TO BE ABLE TO ROUTE THE TRAFFIC AROUND
THESE AREAS, instead of blindly sending traffic into congested
areas. At a certain level of congestion, sending traffic into a
congested area is like sending it into a black hole; the traffic
will never leave the area to progress to its destination.
Sending traffic into a congested area also induces a feedback
effect, causing the congestion to spread farther than it
otherwise would, and making it that much less likely that the
congestion will dissipate. Any routing algorithm which cannot
take this into account will not be robust enough to survive in a
real operational environment.
Min-hop routing also has another disadvantage which is more
specific to the internet environment. Let N1, N2, and N3 be
three networks, and suppose we have to get some traffic from N1
to N3 by using N2 as a transit network. Let G12 be a gateway
connecting N1 and N2, let G23 be a gateway connecting N2 and N3,
and let G2X be a gateway which connects N2 to some other
unspecified network. If we use min-hop routing, then any traffic
which must go from G12 to G23 must go "directly", through network
N2, without stopping at G2X, because the path G12-G2X-G23 has one
more hop than the path G12-G23. Perhaps this doesn't seem like
- 25 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
much of a restriction; why would one want to have traffic stop at
the intermediate gateway G2X when it could go directly from G12
to G23? Actually, two possible reasons come to mind immediately.
The first reason has to do with the possible effects of the
network's end-end protocol. In the ARPANET, for example, a
source host is allowed to send only 8 messages to a given
destination host before receiving the RFNM for the first of the 8
messages. Hence the throughput obtainable on a host-host
connection is inversely related to the amount of time it takes to
get a RFNM from the destination host to the source host. It
follows that higher throughputs are obtainable between hosts that
are "near" each other than between hosts that are "far" from each
other. It is also possible that G12 and G2X will be near to each
other, and that G2X and G23 will be near to each other, but that
G12 and G23 will be far from each other. So the throughput
obtainable in a transfer between G12 and G23 may be less than
that obtainable in a transfer between G12 and G2X, and less than
that obtainable in a transfer between G2X and G23. It follows
that the throughput obtainable between G12 and G23 via G2X may be
higher than the throughput obtainable between G12 and G23
directly. Basically, by using an additional gateway hop, the
ninth message from G12 can be put into the network while the
first message is still in transit from G2X to G23, while without
the intermediate hop, this is not possible. Of course, the best
solution to this sort of problem would be to fix the end-end
- 26 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
protocol so that it does not impose this sort of restriction.
Our present point, however, is that our routing algorithm should
not rule out the possibility of this sort of strategy. Note that
by using an intermediate gateway hop, we might not only increase
throughput, but also decrease the delay (since a ninth message
would not be blocked as long.)
(It is interesting to think about whether this sort of
strategy might not be useful entirely within the ARPANET.)
Another possible scenario in which an intermediate gateway
hop might be useful occurs if the intermediate gateway is
multi-homed. It is possible that an intermediate gateway will be
homed to two IMPs which are distant from each other within the
network. If so, the intermediate gateway may be used as an
"expressway" around a congested area of the network.
If we replace the intermediate gateway G2X with two gateways
G24 and G42, we also have the possibility of sending traffic from
N1 through G12 into N2 to G24 through N4 to G42 into N2 to G23
and thence into the destination network N3. This is akin to the
oft-discussed expressway problem, but cannot be handled within
the framework of min-hop routing. Of course, it might be very
difficult to take account of such factors, but one would not want
to have a routing scheme which makes it absolutely impossible.
- 27 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
Still another disadvantage of min-hop routing in the Catenet
is the following. The current Catenet routing algorithm, when
faced with three gateways on the same network, considers the
three to be equidistant. However, the delay and throughput
obtainable from gateway A to gateway B may be very much different
than the throughput obtainable from gateway A to gateway C. In a
large distributed network like the ARPANET, some pairs of hosts
are connected by high-performance paths, and some by
low-performance paths (either because they are separated by many
hops, or because the path between them is under-trunked, etc.)
Allowing the routing algorithm to be sensitive to this could
potentially have a large impact on the internet performance.
There may not be any network that actually uses min-hop
routing, except for the Catenet. There are, however, networks
that use a variant of it, which we might call "fixed cost"
routing. In fixed cost routing, each Pathway is still assigned a
constant length, but not all Pathways are assigned the same
length, and some Pathways have a length which is not equal to 1.
In a scheme like this, one attempts to assign values of length so
that slow-speed lines appear longer than high-speed lines,
reliable lines appear shorter than unreliable ones, and lines
with high propagation delays appear longer than lines with low
propagation delays. This sort of routing is used in DATAPAC and
in DECNET. Both those network architectures have routing
algorithms based on the original ARPANET routing algorithm. The
- 28 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
designers of those architectures apparently realized that min-hop
routing is not very satisfactory if the links are not of
relatively homogeneous quality, but were probably wary of the
problems that the ARPANET's original algorithm had in adapting to
changing traffic conditions. They avoided these problems by not
adapting at all to changing traffic conditions. Of course, this
is the weakness in fixed cost routing. It may be better than
min-hop routing in a lightly loaded Network Structure with
heterogeneous Pathways, but in a heavily loaded Network Structure
with unbalanced load it really is no better than min-hop routing,
and will still send traffic right into congested areas.
We have been emphasizing the claim that routing ought to be
able to detect congestion and route traffic around it. Some may
wonder whether we are confusing the proper functions of routing
with the proper functions of congestion control. That is not the
case. Congestion control schemes generally try to limit the
amount of traffic entering a network so as to prevent or to
reduce the overloading of some resource or of the whole network.
When congestion actually exists in the network, however, it is
the job of routing to try to send traffic around the congested
areas; otherwise the routing actually causes the congestion to
increase. Of course, one might attempt to design the routing
algorithm under the assumption that there will be a congestion
control scheme that will make congestion impossible. However,
such a design could not be very robust. If we want to build a
- 29 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
robust Network Structure which will continue to operate under a
variety of unforeseen conditions, then we want each software
module or protocol to be designed with the assumption that the
other modules or protocols will be less than optimal. The
resulting system will be much less prone to system-wide failure
than one which is designed so that no part of it will work at all
unless every part of it works perfectly. Although we will not be
discussing explicitly, in this paper, any schemes for controlling
the amount of traffic which is input to the internet, that
doesn't mean that we can ignore the way in which the routing
algorithm affects and is affected by the existence of congestion.
Particular problems related to overload of network resources
should be discussed in whatever context they arise in, without
worrying about whether the problem is properly called "congestion
control" or "routing." There is in general no way of telling in
advance whether the best solution to a particular problem is a
routing solution or a congestion control solution, and putting
labels on the problems just restricts our thinking.
4.3.2 Load Splitting
Routing in the ARPANET has always been "single-path
routing." We mean by this that at any given moment, the
ARPANET's routing algorithm provides only a single path between
each pair of IMPs. All traffic which enters the network at some
particular time, originating at IMP A and destined for IMP B,
- 30 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
will travel over the same path. Actually, this statement is
somewhat oversimplified, since there might be a change of routes
while some traffic is already in transit. The point, however, is
that at any given time, each source or intermediate IMP will send
all traffic for a particular destination IMP to a unique
neighbor; it cannot split the traffic among several neighbors.
Routing in the Catenet is currently somewhat different.
Suppose gateway A has two neighbors, B and C, and has some
traffic to send to gateway E. The routing algorithm run in A
assigns a distance value to the path to gateway E via neighbor B
and a distance value to the path to E via neighbor C. If the
distance from A to E via B is the same as the distance from A to
E via C, then gateway A will alternate between use of B and C
when sending traffic to E. That is, A makes simultaneous use of
two distinct paths to E. Such a scheme would be somewhat more
difficult to put into SPF routing, because in SPF routing, no
assignment of distance values from A to E via each of the two
neighbors is generated. Rather, only one path is computed, via
one of the neighbors, and only the distance on that one path is
known. Distance on other paths is not computed by the SPF
algorithm. (On the other hand, the SPF algorithm generates the
entire path, so that each Switch knows which other Switches its
traffic will be routed through on the way to the destination.
The original ARPANET algorithm does not do this, but only tells
each Switch which of its neighbors to use when sending traffic to
the destination.)
- 31 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
What is the significance of this? It seems to be commonly
regarded as obvious that multi-path routing, or load splitting,
is an important advantage, so that routing algorithms that permit
it are better than routing algorithms that do not. However, when
one asks advocates of multi-path routing why it is better than
single-path routing, a very common answer seems to be,
"Multi-path routing is better because it provides multiple
paths." This sort of answer is rather superficial.
Multiple-path routing is NOT a goal in and of itself; IT IS
IMPORTANT ONLY INSOFAR AS IT SERVES SOME MORE FUNDAMENTAL GOAL.
If a multi-path routing algorithm results in smaller delays or
larger throughput than some other algorithm, then that is a good
reason for favoring it over the other algorithm. Now, it is
certainly true that any routing algorithm which OPTIMIZES network
delay or throughput will be a multiple-path algorithm. THE
CONVERSE, HOWEVER, IS NOT TRUE. A routing algorithm which
provides multiple paths does not necessarily optimize delay or
throughput. In fact, merely because a routing algorithm provides
multiple paths, it does not follow that it provides better
performance in any respect than some other routing algorithm
which provides only a single path between a pair of Switches. An
algorithm which provides a single good path may be far superior
to an algorithm which provides several poor ones.
To see this, let's look at some possible effects of the load
splitting in the Catenet routing algorithm. Let A, B, C, D, and
- 32 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
E be five gateways, and suppose that there are two possible paths
from A to E, namely ABDE and ACDE. The Catenet routing algorithm
would regard these two paths as equidistant, since that algorithm
regards two paths as equidistant if they contain the same number
of intermediate gateways. Therefore gateway A would perform load
splitting on its traffic to E, sending half of the traffic to
neighbor B and half to neighbor C. Does this provide more
throughput than the use of a single one of these paths? Not
necessarily. If the bottleneck on the paths from A to E is the
Pathway DE, then the use of these two paths provides no more
throughput than the use of either one alone. In fact, if DE is
the bottleneck, the use of the two paths will probably result in
lower throughput than the use of a single path. The use of
several paths increases the likelihood of the packets from A to E
arriving out of order at the destination host. Yet as more
packets arrive out of order, more TCP resources are needed to
handle them, and the TCP just has that much more work to do. TCP
buffers that are occupied by out-of-order packets cannot be
"allocated" for receiving more packets, so acknowledgments must
be delayed, and windows must be kept smaller. The result of all
this will be higher delays and lower throughputs. This was
probably not the intention of load splitting, but is a likely
consequence of it.
Suppose there really are two independent paths from A to E
which are "equidistant", say ABDE and ACFE. Even here, sending
- 33 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
half the packets on each path may only degrade performance. To
see this, suppose each of the Pathways AB, BD, DE, AC, and CF has
a capacity of 50 kbps, but that link FE has a capacity of 10
kbps. Suppose also that we want to send 50 kbps of traffic from
A to E. If we alternate packets between these two paths, by
trying to send 25 kbps of traffic each way, we will be able to
get at most 35 kbps of traffic through to the destination, and we
will cause severe congestion on link FE (which will probably
result in its being able to carry even less than the rated 10
kbps, further lowering the network throughput.) Had we used only
the single path ABCD, we would have been able to pass more
traffic. Again, we see a situation where the use of load
splitting can reduce throughput and increase delay.
This sort of problem might at first appear to be too
unlikely to be worth worrying about. However, it has already
occurred in the Catenet, and has caused a significant problem.
In fact, in the Catenet's actual problem, half of the traffic was
sent on a path whose capacity was sufficient to handle all the
traffic, and the other half of the traffic was sent on a path
whose capacity was essentially zero (because a network partition
made the destination host unreachable on that path). In this
case, load splitting resulted in the throughput being cut in
half, as half the traffic was routed down a black hole! The
problem was "solved" by eliminating one of the two possible
paths, thereby eliminating the possibility of load splitting.
- 34 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
However, this does not seem like a proper way to deal with this
problem in the general case.
The Catenet's load splitting has been defended from this
latter objection as follows: "If there were no load splitting,
maybe all the traffic would have been sent into the black hole,
not just half." This is less a defense than a sad commentary on
the state of the Catenet routing; to accept this sort of defense
is just to give up entirely on the problem of internet routing.
Someone may reply to our first criticism of load splitting
by saying "maybe the bottlenecks will be Pathways AB and AC,
rather than DE, in which case the use of two paths does increase
the throughput." This reply is correct, but not very important.
The sort of load splitting done in the Catenet might, by pure
chance, increase throughput in some particular case. The point
though is that it is no more likely to increase throughput than
to decrease it. Certainly there is no reason to suppose that the
cases in which it might help are any more likely to occur than
the cases in which it hurts. In our experience with the ARPANET,
schemes that seem a priori as likely to hurt as to help always
end up hurting more than helping. (In networking, Murphy's law
is more than just a joke.) Choosing equidistant paths for load
splitting will generally result in paths which are only small
variants of each other (if it results in any paths at all, since
there are not necessarily several equidistant paths between a
- 35 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
pair of Switches), and there is no reason to suppose that the
bottleneck will not be common to each path. Even if we do get
two paths which do not share a bottleneck, unless we try
explicitly to apportion the flows to the relative capacities of
the two paths (rather than just dividing the traffic 50-50), we
will not, in general, gain any increase in throughput.
In chapter 4 of [6], we actually devised a multiple-path
routing scheme, based on SPF, whose purpose was to maximize
throughput. In this scheme, we make sure that any set of
simultaneously used paths between two Switches are
"bottleneck-disjoint", (i.e., they don't share a bottleneck), so
that we know that we can get more throughput by use of several
paths. We also devised a flow apportionment scheme which
attempts to match flows (or parts of flows) to the available
capacity of each path. Anyone interested in seeing what it
really takes to do multi-path routing should look at that
chapter. The scheme proposed there is quite complex, however,
and it is not obvious that it will work. Some simulation work
will eventually be done on it. Until that sort of algorithm is
much better understood, it would not be very wise to use the
internet to experiment with it. It will be difficult enough to
adapt a well-understood and much-used routing algorithm (like
that currently in the ARPANET) to the internet environment. The
internet is certainly not a place for experimenting with new and
untried routing algorithms.
- 36 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
Although it is quite difficult to design a multi-path
routing procedure that results in significant improvements of
delay or throughput over single-path routing, there are other
reasons for requiring multiple paths between a pair of Switches
that are more easily dealt with. For example, we may be required
to have different paths between a pair of internet gateways
because of ACCESS CONTROL RESTRICTIONS. That is, certain classes
of packets may not be allowed to traverse certain classes of
networks, so that different routes would be required for the
different classes of traffic. We may also decide that different
types of service that may be requested by the user should travel
over different paths, even if the source and destination gateways
are the same for the different traffic classes (e.g., maybe we
don't want to use multi-hop satellite networks for interactive
traffic.) This is easily handled within the framework of SPF
routing. Remember that the SPF algorithm produces the shortest
path to a destination, based on an assignment of lengths to the
Pathways. Rather than simply assigning a unique length to each
Pathway, we can assign a set of lengths, indexed by traffic
classes. We can then produce a set of routing tables, indexed by
traffic type, such that the routing table for a given traffic
type contains the "shortest" path, based on the length
assignments for that traffic type. For example, if traffic class
C is not permitted to traverse Pathway P, the length of P,
indexed by C, can be set to infinity. This ensures that that
- 37 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
Pathway will not be part of any path found in the routing tables
indexed by C. We even have the flexibility to assign to P a
length which, while not infinite, is much larger than the length
of any other Pathway. In this case, that Pathway will be used
for traffic of class C only if EVERY path to the destination
includes it (i.e., only if it can't be avoided). This sort of
load splitting might be quite important in the internet, and is
also quite simple to handle.
4.3.3 Delay vs. Throughput
In the ARPANET, each IMP measures the average delay per
packet on each of its outgoing lines. This average delay is
assigned as the "length" of the line, and shortest paths are
computed on that basis. We have studied the performance of this
algorithm a great deal [5]. It tends to use min-hop routes under
conditions of light or of uniform load. However, it does seem to
take account quite well of the varying delays that are produced
by lines of different transmission or propagation delay
characteristics. Since congestion causes large increases in the
delays, congestion is generally detected by the routing
algorithm, and traffic really is routed around congested areas
when that is possible. While we cannot claim that our routing
algorithm gives the optimal delay, the characteristics that it
does have seem to be the characteristics that we would really
like to see in any robust, operational network, and particularly
- 38 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
in the internet. The routing tends to be stable on what are
intuitively the best paths, except when exceptional conditions
arise which make it clear that some other path is likely to
provide better performance. It is this sort of routing which we
propose for the internet.
Before discussing further the use of delay-oriented routing
in the internet, we would like to briefly consider the issue of
throughput-oriented routing. In the previous section, we argued
against the use of multi-path routing as a means of optimizing
throughput, largely on the grounds that doing it right is
extremely difficult (much more so than one might at first think),
that the ways of doing it right are quite poorly understood, and
that the internet is not a good testing ground for new and
untried algorithms. However, one often hears that there are high
throughput applications (bulk traffic) for which delay doesn't
matter, and one may wonder whether there is not some kind of
single-path routing which is more appropriate for such
applications than is delay-oriented routing. One scheme that is
very commonly suggested is that of routing traffic on the path of
maximum excess capacity, instead of on the path of least delay.
Given an algorithm for determining the amount of excess
capacity on each Pathway (which could be quite difficult to
design for the internet environment -- how do we know what the
excess capacity of a packet-switching network is?), it is no
- 39 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
difficult matter to modify the SPF algorithm to produce the paths
of maximum excess capacity. However, it would not be a good idea
to use the resultant routes for bulk traffic. For one thing, we
must understand that such a routing algorithm would not maximize
total network throughput. (By "maximizing total network
throughput", we mean maximizing the amount of traffic that the
network can handle.) Suppose, for example, we wanted to send 40
kbps of traffic, and had the choice of using a one-hop path with
excess capacity of 50 kbps, or a 10-hop path, each of whose links
had an excess capacity of 100 kbps (so that the total composite
path has an excess capacity of 100 kbps). By using the shorter
path, we use up a total of 40 kbps of network capacity, capacity
which is now unavailable for other traffic. By using the longer
path (which is the path of maximum excess capacity), we use up a
total of 10x40 kbps (40 kbps per hop), thereby using up a total
of 400 kbps which is no longer available for other traffic. In
terms of maximizing the total network throughput, we do better by
using the one-hop path, rather than the path of maximum excess
capacity.
Maybe we are less interested in maximizing total network
throughput than in finding a path for some particular traffic
flow which has enough capacity to handle the required throughput
of that flow. We still would not want to use the path of maximum
excess capacity, for that path might have a delay which is much
too long. Although we often hear that certain classes of traffic
- 40 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
(e.g., file transfer) care only about throughput, not delay, this
is really a gross oversimplification. In file transfer, we don't
care how long it takes for the first packet to reach its
destination, AS LONG AS ALL THE FOLLOWING PACKETS FOLLOW
IMMEDIATELY, WITH NO DELAYS BETWEEN THE ARRIVALS OF SUCCESSIVE
PACKETS. Of course, if there are long delays between the packets
of a file transfer, the throughput will be very low. Hence it is
not quite true to say that file transfers and the like are
unconcerned with delay. If higher level protocols like TCP are
being used, then routing over a path of long delay will certainly
result in lower throughput. The reason is as follows. A TCP
sender will only send a certain amount of data, until he fills
the window specified by the TCP receiver. The size of the window
is very likely to depend on such network-independent things as
the amount of resources (e.g., buffers) in the destination host.
If the path between source and destination host is very long,
then the sending TCP will fill the window, and then have to wait,
idly, for some period of time while his data gets to the
destination, and while the message indicating the re-opening of
the window is transmitted from the receiving TCP. Since this
network-imposed long delay causes the sending TCP to have to be
idle for some period of time, it holds down the throughput. So
it seems that all things considered, simply routing
high-throughput application traffic on the path of maximum excess
capacity is unlikely to actually result in high throughput.
- 41 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
If we really wanted to do single-path throughput-oriented
routing, we would need something like the following. We would
want to route traffic on the shortest path (i.e., the path of
least delay) which does not contain any components whose
available capacity is too small to handle the needed throughput.
This would prevent us from choosing a path with arbitrarily long
delays, or a path with too little capacity. Unfortunately, it is
almost impossible to find out either what throughput is needed by
an application, or to find out just what the capacity of
particular components of the internet is. We might want to
consider some strategy such as not sending batch traffic on paths
which include components which are very heavily loaded. This is
fertile ground for experimentation. Our present point, however,
is that the delay-oriented SPF routing of the ARPANET already
provides the basic structure that we need to accommodate this
sort of strategy. If we knew that we wanted bulk traffic to
avoid certain Pathways (e.g., Pathways with too little
bandwidth), we could have SPF routing compute the shortest routes
that did not include those Pathways, by using the "indexed
length" scheme described in section 4.3.2. There is no need to
consider different sorts of routing schemes.
4.3.4 Knowing the "Whole Picture"
The use of the SPF algorithm requires that every Switch know
the complete topology of the Network Structure. That is, every
- 42 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
Switch must know of all the other Switches, must know which
Switches are "directly connected" to which other Switches, and
must know the "length" of each Pathway. This is not to say that
this information is "compiled in", or even loaded in manually.
Rather, it is determined dynamically, in real-time, through
interpretation of the routing updates (see section 4.5). It is
this uniform global knowledge of the topology and the Pathway
lengths that enables each Switch to run a shortest path
algorithm, while producing routes which are consistent with the
routes produced by other Switches, so that routing loops do not
form. The SPF algorithm does not merely tell a Switch to which
of its neighbors it should send packets for destination D.
Rather, it computes the entire path to the destination Switch.
However, when a packet is routed, it does not carry with it the
identity of the entire route, as computed by its source Switch.
Each Switch just forwards the packet to the next "hop" along its
route. The fact that all Switches have the same information
about the topology is what ensures that this routing will be free
of loops.
Since each Switch performs its routing based on a complete
picture of the topology of the Network Structure, we can call
this sort of routing scheme a "whole picture" scheme. In this
section, we will compare "whole picture" schemes with some other
schemes which do not require the Switches to have uniform global
knowledge of the topology. We argue that "whole picture" schemes
are always superior.
- 43 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
The original ARPANET routing scheme, and the current Catenet
routing scheme, are not "whole picture" schemes. In these
routing schemes, no Switch need have any knowledge of the
topology, other than who its own immediate neighbors are, and the
lengths of the Pathways to its immediate neighbors. These
algorithms function as follows. When a Switch first comes up, it
forms a hypothesis as to the best neighbor to which to send data
for each possible destination Switch. This initial hypothesis is
based only on its own local information about the lengths of the
Pathways to its neighbors. It then informs its immediate
neighbors of its hypotheses, and is informed of their hypotheses.
It then forms a new hypothesis, based on its own local
information AND the hypotheses communicated to it by its
neighbors. It then exchanges hypotheses with its neighbors
again, and again, and again, until its own hypotheses are in
complete agreement with those of its neighbors, at which point
stability is reached.
To see the difference between this sort of routing scheme
and the "whole picture" scheme, consider the following situation.
Suppose we have 100 people in a room, sitting in chairs which are
properly lined up so that we can talk of each person's having two
immediate neighbors. We also have a picture of an object, and
our goal is to have ALL the people agree on the identity of the
depicted object. Now we have a choice of two different
procedures for bringing this about:
- 44 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
Procedure 1: Cut the diagram into 100 pieces, and give one piece
to each person. Each person is now allowed to look
at his one piece, and then form a hypothesis as to
what is depicted in the full picture. Then each
person can exchange hypotheses only with his
immediate neighbors. Then each person can form a
new hypothesis and exchange that with his immediate
neighbors. The procedure terminates when all 100
people agree on what is depicted.
Procedure 2: Make 100 Xerox copies of the diagram, and distribute
the copies to each person.
If we really think it is important for each person to know what
is depicted in the picture, then we will certainly follow
procedure 2, which will make the whole picture immediately
available to all participants. Procedure 1 would only be useful
as a party game. It would be quite amusing to see all the
ridiculous hypotheses that are formed before all participants
converge to the correct one, IF they ever do manage to converge.
Even if they do converge, it might take quite a long time. We
must remember that different people form hypotheses at different
rates, and can communicate them at different rates. Some people
may simply refuse to talk to certain neighbors at all. If one's
left-hand neighbor has formed a good hypothesis, but one's
right-hand neighbor has not, one's own hypothesis is likely to be
thrown off the track, which in turn is likely to mislead one's
left-hand neighbor into a poorer hypothesis during the next
"iteration." This is not a very optimal procedure for bringing
about convergence of opinion.
- 45 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
However, this situation is really too simple and
straightforward to be truly analogous to routing. To improve the
analogy, we must suppose that the picture is constantly changing,
even as the people are still forming hypotheses. In procedure 2,
this change is accounted for by simultaneously giving each
participant a new copy of the picture. In procedure 1, changes
in the picture are accounted for as follows: if the part of the
picture originally given to person P has changed, then give him
the corresponding piece of the same picture; he can now use this
piece when forming his hypotheses, and should forget about the
previous piece. When the procedures are thus modified to take
account of changes in the picture, the situation described is
more analogous to routing, and the advantages of procedure 2 over
procedure 1 are even more pronounced.
The ARPANET's current routing algorithm is similar to
procedure 2, since the whole picture is made available to each
Switch. The ARPANET's original routing algorithm, and the
Catenet's current one, are more similar to procedure 1; perhaps
they should be called "jigsaw puzzle" algorithms. All of the
problems of procedure 1 have their analogies in those routing
algorithms. It should be obvious that in terms of
responsiveness, accuracy, and consistency, whole picture
algorithms are superior to jigsaw puzzle algorithms. Many of the
problems of the original ARPANET routing algorithm, such as
looping and very slow response to topological change, can be
attributed to its "jigsaw puzzle" nature.
- 46 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
Even if one agrees that we ought to avoid "jigsaw puzzle"
algorithms, one might still claim that we need not have a "whole
picture" algorithm. One might wish to argue that a given Switch
needs to know only the topology of a "region" which contains it.
This region would be larger than a single Switch, but smaller
than the set of all Switches. A region would also be
geographically contiguous, so that if two Switches are in the
same region, then there is a path between them which is entirely
within the region. Then traffic which does not need to leave a
region to get from its source to its destination is in effect
routed by a "whole picture" scheme. Traffic which must leave the
region, however, does not have its whole route preplanned.
Switches within one region will know only how to get traffic out
of the region. Other Switches in the next region will know how
to get the traffic through that region, etc. It seems, one might
argue, that this sort of regionalized routing scheme ought to be
possible. After all, consider the analogy with ordinary road
travel. If one wants to travel from Boston to Los Angeles, one
need not preplan the entire route. One can just head in the
general direction of Los Angeles, with no need to know anything
about the roads which are close to Los Angeles until one actually
gets close. A similar scheme ought to work with data.
One problem, however, with the suggested analogy, is that it
does not even hold in the case of ordinary automobile travel. If
one were planning an automobile trip to LA, one would want to
- 47 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
know about any record-setting blizzards in the midwest long
before one actually approached the midwest. One would want to
know about the status of Mt. St. Helen's volcano long before one
approaches Oregon. One might try not to be passing through
Chicago at rush hour. Avoiding any of these potential disaster
areas could require quite a bit of advance planning. Of course,
the amount of advance planning that one performs when travelling
is a matter of personality; some people are more adventurous
than others, and might actually enjoy a disaster or two along the
way. Users of a data communications utility, however, whatever
personality traits they may have, generally do not want their
data to be sent on an adventure. Rather, they want their data to
be treated with a conservatism and caution which require
considerable preplanning.
In any case, the analogy between the road system and a data
communications network is very misleading because of the very
rich interconnectivity of the road system. No matter how many
problems an automobile driver encounters as he approaches Los
Angeles, he still has a large number of choice points, in that he
can take any number of relatively short detours around problem
areas. In data networks, however, the connectivity is much less
rich, and the closer the data gets to its destination, the fewer
choice points there are. With a sufficiently sparse
connectivity, the entire path could even be determined by the
very first routing choice that is made, so that no detours around
- 48 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
problem areas are possible once the "trip" begins. The situation
is as if someone drove from Boston to Nevada, then found that all
roads from Nevada to California were closed, and that he then had
to drive all the way back to Boston to start on a new route to
California. This sort of sub-optimality is inherent to any
regionalized routing scheme for data communications networks.
In fact, the situation could be even worse. If Switches in
Boston know nothing about what is happening between Nevada and
California, then data for California which arrives at Nevada and
then is sent back from Nevada to Boston for alternate routing
will just loop back to Nevada. The data will be stuck in an
infinite loop, never reaching its destination. In IEN 179, Danny
Cohen proposes a regional routing scheme like this, apparently
not realizing that it suffers from loops. His proposal also
includes a form of hierarchical addressing which is closely bound
up with routing, so that a Switch in Boston might not even be
able to distinguish data for Nevada from data for California.
That is, in Cohen's scheme, data for Nevada and data for
California would be indistinguishable at the Boston Switches;
all such data would appear to be addressed to Nevada. Only the
Switches at Nevada would look further down the address hierarchy
to determine whether the data needs further forwarding to
California. Any such scheme is hopelessly loop-prone, except in
a Network Structure whose connectivity is extraordinarily rich,
much more so than the Catenet's will ever be.
- 49 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
It might seem like these objections would also have to apply
to the internet, since a gateway does not know all about IMPs and
packet radios and SIMPs, etc., in the component networks.
However, the looping problem is avoided in the internet since it
is organized in a strict hierarchy of Network Structures.
Switches in one Network Structure need not know anything about
Switches in any other Network Structure, but they must have
complete information (Whole Picture) about Switches in the same
Network Structure. All (source or intermediate) Switches in a
particular Network Structure always route data to a Switch in
that same Network Structure. This imposition of strict hierarchy
prevents looping, as long as the lower levels of hierarchy are
controlled by the higher levels. In the internet, this means
that, e.g., if a gateway hands a packet to an ARPANET IMP for
delivery to an ARPANET Host or to another internet gateway, the
ARPANET is required to deliver the packet as specified by the
gateway, or to say why not. It must not simply pass the packet
back to the gateway, or a loop will form. (This sort of looping
has been frequently noticed between IMPs and port expanders.)
This does not imply that an ARPANET IMP cannot pass a packet to
an internet gateway for delivery (through an "expressway
network") to another ARPANET IMP, but only that once an internet
gateway decides to send a packet into the ARPANET, the ARPANET
must get that packet to the intended destination, or else inform
the gateway that it cannot do so.
- 50 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
It is also important to note that the hierarchical levels in
the internet tend to be "horizontal", rather than "vertical".
That is, in an internet spanning North America, there would be
internet gateways located all across the continent, as well as
IMPs and packet radios and PSATs located throughout the
continent. This is quite different from regionalization, in
which Switches which are close geographically are in a common
region. This distinction is very important if we are to avoid
such problems as looping.
Although building the internet as a strict hierarchy of
Network Structures avoids the problems of looping, there is
always some degree of sub-optimality introduced whenever the
topological knowledge of the Switches is restricted in any way,
even if the restriction is just to Switches within the same
Network Structure. This is a point to which we return in section
4.6, where we discuss some of the basic limitations of
internetting.
4.4 Measuring Pathway Delay
One of the most basic problems in devising a scheme to do
delay-oriented routing is to figure out a way to determine the
delay. In the ARPANET, the delay measurement algorithm is quite
straightforward. When a packet arrives at an IMP, it is stamped
with its arrival time. When it is transmitted to the next IMP,
it is stamped with the time of transmission. ARPANET packets are
- 51 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
buffered in an IMP until acknowledged by the next IMP; if a
packet has to be retransmitted, its transmission time stamp is
overwritten with the time of latest transmission. When the
packet is acknowledged by the receiving IMP, the arrival time is
subtracted from the transmission time, yielding the total time
the packet spent in the IMP. The propagation delay (i.e., the
speed of light delay along the phone line from one IMP to the
next) is then added in to compute the total amount of time it
took to get the packet from one IMP to the next. There are three
important aspects of this delay measurement algorithm:
1) It is necessary to measure the amount time each packet
spends within the Switch. This should be as easy to
apply to a gateway as to an IMP.
2) It is necessary to determine how long it takes a packet
to travel from one Switch to another over the Pathway
connecting them. If the Pathway is a telephone line, as
in the ARPANET, this is just the propagation delay, and
is a constant which can be separately measured and then
stored in a table. On the other hand, if the Pathway is
a packet-switching network, or even an internet, this is
much more difficult to determine, and is certainly no
constant.
3) There must be some way to account for packets that don't
get through, or don't get through immediately, due either
- 52 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
to errors or to congestion. In the ARPANET, if a packet
doesn't get through on its first IMP-IMP transmission,
and has to be retransmitted 200 ms. later, this 200 ms.
gets added into the packet's delay. This is a very
important feature, since it enables the delay measurement
to reflect the effect of congestion or of a very flakey
line. But unless the gateways run a reliable
transmission protocol among themselves, it will be
difficult to make sure that our delay measurement really
reflects these factors. If we are trying to send data
through a network which is dropping most of the data we
send it, we want to make sure that our delay measurement
routines produce a high value of delay, so that traffic
will tend to be routed around this very flakey and
unreliable Pathway. (Remember that if too much traffic
is dropped, some (higher) level of protocol will have to
do a lot of retransmissions, resulting in very high
delays and low throughputs.)
The problem of how to measure delay is more tractable in the
case of AREA ROUTING than in the more general internet case.
Recall that by "area routing," we mean a sort of internet all of
whose component networks are basically identical (see IEN 184).
For example, we might at some future time decide to divide the
ARPANET into areas, connected by gateways, so that the ARPANET
itself turns into a hierarchical network. If we decide to use
- 53 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
the same routing algorithm at the high level (i.e., among the
intra-ARPANET gateways) as we use at the lower level (i.e., among
the individual IMPs in a particular area), then the gateways
could obtain the delay measurement information directly from the
routing updates sent by the individual IMPs. That is, the lower
level routing algorithm could provide information to the gateways
enabling them to deduce their delay to other gateways. If the
gateways are also ordinary IMPs, this information is
automatically available. If the gateways are hosts on the low
level ARPANET, a special protocol would have to be developed to
enable the IMPs to transmit the routing updates to the gateways
they are connected to (though this wouldn't be much different
from the protocol that IMPs now use to transmit routing updates
to their neighboring IMPs). Of course, if we were to implement a
scheme like this, we would still want to make the ARPANET appear
as a single Pathway (with no intermediate Switches) at the level
of the Network Structure of the Catenet. That is, the Catenet
would be a third hierarchical layer over the two hierarchical
levels of the ARPANET, which would be transparent to it.
In the more general internet case, we cannot rely on the
component networks to provide us with the sort of delay
information we would like to use for the internet routing
algorithm; the internet Switches will have to have some way of
gathering this information themselves. In general, it will not
be possible for a Switch to measure the one-way delay from itself
- 54 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
to its neighbors. (We wouldn't want to rely on the radio clocks
that are now beginning to be deployed at the gateways; while
these might be useful for doing measurements, we wouldn't want
the reliability of the entire operational internet system to
depend on a radio broadcast over which we have no control.) It
is possible, however, to measure round-trip delay between each
pair of neighboring gateways. In the ARPANET, for example,
round-trip time is easily measured by keeping track of when a
message is sent to a neighboring gateway, and then noting the
time when the RFNM is received. One-way delay would be
approximated by dividing the round-trip delay in half.
It is certainly true that the round-trip delay is not, in
general, exactly twice the one-way delay. However, it seems like
a good enough approximation to use in the internet routing
algorithm. All we really require is that it be roughly
proportional to the one-way delay, in that both one-way and
round-trip delays tend to rise and fall together, and that
congestion in the Pathway (component network) tends to make both
increase. Of course, before designing the precise delay
measurement scheme that we would want to use in the internet, we
would have to run a series of tests and experiments to see which
of several possible delay measurement algorithms gives us the
results we want. This would be similar to the extensive testing
of the ARPANET's delay measurement algorithm that is documented
in [4].
- 55 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
Unfortunately, there are many networks which do not return
anything like RFNMs that could be used to gauge even the
round-trip delay. (Many networks, e.g., SATNET and the
forthcoming wideband network, do not even tell you whether you
are sending traffic to a host which is down.) So we will need a
gateway-gateway protocol in which gateways receiving data from
other (neighboring) gateways send back replies which can be used
for timing.
This does not mean that every packet sent from one gateway
to another must be acknowledged by the receiving gateway.
Rather, we would propose something like the following. Suppose
we have, as part of the gateway-gateway protocol, a bit that a
sending gateway can set which requires the receiving gateway to
acknowledge the packet. The sending gateway can have a random
number generator, which lets it select packets at random in which
to set this bit. These packets will have their round-trip delay
measured, and will constitute a random (and hopefully a
representative) sample. The packets need not be buffered in the
sending gateway pending acknowledgment, but they will need to
have unique identifiers so they can be kept track of. The
round-trip delay of each packet is then easily determined when
the acknowledge is received. (This probably implies though that
gateways will have to run a protocol with their neighbors when
they first come up in order to synchronize sequence numbers to
use for identifying packets uniquely.) There will also have to
- 56 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
be a time-out, so that a packet which is not acknowledged within
a certain amount of time (perhaps dependent on the expected delay
of the packet, based on previous measurements) will be considered
to have been lost on the Pathway between gateways (or in the
receiving gateway). Packets which have been lost should be
assigned a very high delay, so that the routing algorithm assigns
a very high delay to Pathways which lose a lot of packets. This
will tend to cause internet traffic to avoid such Pathways.
There doesn't seem to be any problem in principle with a scheme
like this, but we will probably need to do some statistical
analysis in order to determine the best random sampling
technique, and to figure out how many packets we might need to
keep track of during some period of time (i.e., how big a table
do we need to keep track of packets which are awaiting
acknowledgments?).
This sort of random sampling can also be used as part of a
Pathway up/down protocol. If a certain percentage of the sampled
packets do not get through, it might be good to assume that the
Pathway is not of sufficient quality to be operational, and
should appear to be down as far as the internet routing algorithm
is concerned. In the absence of real data traffic, we could run
the up/down protocol with randomly generated test packets.
Randomly generated test traffic or randomly sampled data traffic
will give us a better result than periodic test traffic, since
measurements based on random sampling are less likely to be
correlated with other network phenomena.)
- 57 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
After we compute the delay for individual packets, we still
face the following two questions:
1) The delay which the routing algorithm assigns to a
particular Pathway will be a function of the measured
delays of the individual packets sent on that Pathway.
But what function should it be?
2) Once a Switch determines the delay on the Pathways
emanating from itself, it must inform all other Switches
of these values (in routing updates). What protocol
should it use for disseminating these updates?
The second question will be discussed in section 4.5. The
remainder of this section will deal with the first question.
After measuring the delays of individual packets, the
individual delays must be put through some sort of smoothing
function before they can be used as input to the routing
algorithm. For example, in the ARPANET, we take the average,
every 10 seconds, of the delays experienced by all the packets
traversing a particular line in the previous 10 seconds. This
average is used as input to the routing algorithm (i.e., it is
assigned as the "length" of the line when the shortest-path
computation is run.) We didn't choose this smoothing function at
random; we chose it because it meets certain desiderata. Our
real purpose in measuring delay on a particular line is to enable
- 58 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
us to predict the delay that will be seen by packets which are
routed over that line in the future. Knowing the average delay
during some period in the past is of no value except insofar as
it enables us to make predictions about the future. We found in
the ARPANET that for a given level of traffic, the delays
experienced by the individual packets would vary quite a bit, but
the delay when averaged over 10 seconds stayed relatively
constant. (It is interesting that everyone who does measurements
of individual packet delay always discovers this large variance,
and always expresses great surprise. This "surprising" result is
so often re-discovered that it should cease to be a surprise.)
When designing the delay measurement routines for the ARPANET, we
investigated some other smoothing functions (everyone seems to
have his own favorite), but none gave more reasonable results
than the simple average we adopted (which is not a running
average, but rather starts over again from scratch every 10
seconds). We also tried averaging periods of less than 10
seconds, but found what we regarded as too much variation, even
when the traffic load was stable.
Note that if we take an average every 10 seconds, we cannot
react to a change of conditions in less than 10 seconds, and we
are often criticized by people who claim that it is important for
routing to be able to react more quickly. Our reply, however, is
simply that it takes 10 seconds to be able to detect a
significant change in delay. Averages taken over smaller periods
- 59 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
show too much variation under constant load to be useful in
predicting the future delay, and hence are not useful in routing.
In other words, averages taken over smaller periods give spurious
results, "detecting" changes when in fact there are none. We
want to change routing in response to real changes in network
conditions, but not in response to the normal range of stochastic
variations in delay. Any change in routing made on the basis of
a shorter-term average is at least as likely to be harmful as to
be helpful. That is, if we attempt to make routing changes based
on delay data which is not sufficiently smoothed, we are really
making changes at random, since we have left too much random
variation in the delay data. And it seems that a good routing
algorithm should not make changes at random. Of course, it would
be nice if we could make routing changes instantaneously based on
instantaneously detected changes in real network conditions, but
this is not possible simply because there is no instantaneous way
of detecting important changes in network conditions.
It is important to realize, however, that the measurement
periods in the various IMPs are not synchronized. Although a
given IMP generates updates no more often than every 10 seconds,
some IMP or other is generating an update about every 500
milliseconds. Mathematical analysis indicates that synchronized
measurement and updating periods should be avoided, since they
give worst case performance [4].
- 60 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
There are other important reasons for not making routing
changes too often. During the lifetime of a single packet in the
network, we want the routing to be relatively constant, so that
the packet can get to its destination without having to take too
many detours. If we changed the routing every millisecond, for
example, a single packet in transit though the network would
experience many routing changes while in transit, which would
probably cause it to have a longer delay than necessary. The
rate at which we change routing should be low relative to the
average transit time of a packet through the network. Another
reason for not making routing changes too frequently has to do
with the time it takes routing updates to travel around the
network. We want to make sure that the information carried in a
routing update is not totally obsolete by the time the update is
received. This implies that the smoothing interval for delay
measurements has to be long relative to the time it takes updates
to traverse the network.
In the ARPANET, 10 seconds is much longer than the amount of
time it takes to get updates around, or the amount of time a
packet spends in transit in the network. We chose 10 seconds as
the averaging interval because it seemed to be the shortest
period that was long enough to give us a reasonable amount of
smoothing. If we think that in the internet, however, average
transit times might be measured in the tens of seconds, we may
have to make our smoothing interval considerably longer than 10
- 61 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
seconds, perhaps as long as a minute. This could seriously limit
the responsiveness of the routing algorithm to changing network
conditions. However, there is nothing we can do about this. THE
LONGER IT TAKES PACKETS TO TRAVEL AROUND A NETWORK, THE LESS
RESPONSIVE THE ROUTING ALGORITHM OF THAT NETWORK CAN BE, for the
simple reason that it will just take longer to disseminate the
information needed for routing around the network. The transit
time of a network places an upper limit on the responsiveness of
that network's routing algorithm. Any attempt to exceed this
upper limit (with kludges or heuristics) will just be futile, and
will result only in unstable and mysterious behavior on the part
of the routing algorithm, reducing, rather than increasing,
performance.
This is not to say that each Switch must generate routing
updates as often as every 10 seconds. If there is no change in
delay from one 10-second period to another, then there is no
reason to generate an update. Or if there is a change, but it is
not "significant", then there is no reason to generate an update.
In the ARPANET, a delay change is considered to be significant if
it exceeds a certain (parameterized) threshold. We devised a
scheme wherein the threshold decreases with time, so that a very
large change is always "significant", but a small change is
significant only if it persists for a long time. Of course,
routing updates must be generated not only in response to
measured changes in delay, but also if a line goes down or comes
up.
- 62 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
We would expect that the details of the delay measurement
and smoothing algorithms will have to be different in the
internet than in the ARPANET, but the principles outlined above
would seem to apply in the internet environment also. WE WILL
HAVE TO DO SOME CAREFUL EXAMINATION OF THE DELAY-THROUGHPUT
CHARACTERISTICS OF EACH OF THE INDIVIDUAL NETWORKS THAT ARE USED
AS PATHWAYS IN THE INTERNET, and it may be that somewhat
different smoothing algorithms will have to be used for the
different kinds of Pathways. However, there doesn't seem to be
any problem in principle with doing this sort of delay
measurement.
An interesting issue arises if a given pair of gateways is
connected by two or more distinct Pathways. For example, two
gateways might both be connected to ARPANET and SATNET, so that
each can be reached from the other by either of those two
networks. Or, a gateway might be multi-homed on the ARPANET, so
that it has two distinct access lines over which it can reach all
the other ARPANET gateways. In such cases, do we want to
separately report the delay on each of the distinct Pathways, or
do we want (at the level of routing) to represent the connection
between each pair of gateways as a single, unique line, whose
delay is some function of the delay of the distinct Pathways
which really exist? This issue is a generalization of an issue
we have been looking at in the context of the ARPANET, which we
call "parallel trunking." In parallel trunking, a single pair of
- 63 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
IMPs is connected by two or more trunks, and the same issue of
how to represent them in routing (as individual trunks, or as a
single, composite, trunk) arises. When the trunks are telephone
lines, the problem is relatively easy to deal with. Routing can
treat them as a single trunk, with a delay which is the average
delay of all packets sent over the composite trunk. The actual
decision as to which particular component trunk to use for
transmitting a particular packet can be made locally, by the IMP
to which the parallel trunks are connected; there is no need for
routing to play a role in this decision.
In the case where the parallel trunks are of comparable
lengths (so that there is not much difference in the propagation
delays), the trunks can serve a common queue according to the
standard FIFO single-queue multiple-server discipline. If the
trunks are more heterogeneous, say one is a terrestrial line and
one is a satellite line, a somewhat more complex queuing
discipline is required. We would like to avoid using the
satellite line until the load is such that if only the
terrestrial line were used, packets would experience a delay
comparable to that they experience over the satellite line. With
this sort of queuing discipline, packets sent to the composite
line experience a delay which is independent of the particular
component (land-line or satellite line) that they use. That is,
no packet is forced to suffer the quarter-second satellite delay
unless the terrestrial line is so backed up that the delay for
- 64 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
packets sent over it is comparable to the delay of packets sent
over the satellite line. This sort of scheme seems to ensure the
best delay performance for the composite trunk. (Actually, the
mathematics of queuing theory suggests that a smaller average
delay for the composite trunk might be achieved by starting to
use the satellite line sooner. That is, a somewhat smaller
average delay might be achievable if a few packets are given a
much longer delay by being forced over the satellite line sooner
than they would be with the queuing discipline we suggested.
Considerations of fairness would seem to rule that out, however;
how would you like it if your data got a much higher delay so
that someone else's could get a slightly smaller one? In
addition, the queuing discipline we suggested would seem to
produce a smaller variance in delays, thereby making the measured
average delay on the composite trunk a better predictor of future
performance, and the better we can predict future performance,
the better performance our routing algorithm can provide.)
Basically, there is no reason for routing to be aware that a
particular line consists of several parallel components rather
than a single component, because, if the argument above is right,
any decision as to which component to use can be best made
locally, at the IMP from which the parallel lines emanate. That
is, the global routing algorithm cannot really make effective use
of information about which lines consist of parallel components,
and should not be burdened with information that it cannot use.
- 65 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
This is good, since the SPF algorithm cannot really handle
parallel lines between a pair of Switches except by representing
them as a single line. (A careful study of the algorithm would
show that much of the algorithm's space and time efficiency would
be sacrificed if it had to be modified to handle parallel trunks
as separate trunks. Since this efficiency is the main thing that
recommends the SPF algorithm over other shortest-path algorithms,
we must be sure that we don't destroy the effectiveness of the
algorithm by making poorly thought-out changes to it.)
In the internet environment, however, we have a more complex
problem with parallel trunks than in the ARPANET. The scheme we
outlined for using parallel trunks in the ARPANET depends on our
being able to know when the load on the composite trunk is such
that exclusive use of the faster component would cause delays
that are just as high as we get when we use the slower component.
This is not difficult to know if the components are phone lines
of one sort or another, since the relation between load and delay
is pretty well-defined if we know the length of the lines and
their capacity. If the components of a parallel "trunk" are
really packet-switching networks, however, it is much harder to
figure out which components are slow and which are fast, and it
is hard to figure out when the load on the fast component is such
that we have to start using the slow one.
It seems that by separately measuring the delays obtained
over the "parallel trunks" in the internet case, we ought to be
- 66 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
able to devise some algorithm for splitting the traffic among the
parallel components in a way which gives reasonable
delay/throughput performance. However, we don't yet have a
solution to this problem, which we will put aside for the
present. Whatever scheme we eventually decide on, however,
should be compatible with treating the parallel components as a
single line at the level of routing. Of course, if we decide to
have different routes for different traffic types (say, excluding
satellite networks for interactive traffic, but using them for
batch traffic), then the problem is eased somewhat since we
partially solve the problem a priori. There would still be no
need to represent the parallel lines as separate lines. Rather,
we would represent them as a single line, with different delay
characteristics for different traffic types.
4.5 Routing Updates
4.5.1 Overhead
Everyone seems to be in agreement that the overhead due to
routing updates should be kept low. At least, no one seems to
advocate that the overhead should be made high. Unfortunately,
"apple pie" pronouncements like this aren't much help in actually
designing a routing scheme. In evaluating a routing algorithm
from the perspective of overhead, one must understand the way in
which overhead is traded off against functionality.
- 67 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
One advantage of the SPF routing algorithm is that it
provides a lot of handles that can be used to control overhead.
In SPF routing, a routing update generated by a particular Switch
identifies each neighbor of that Switch, and gives the delay over
the Pathway to that Switch. Thus the size of an update generated
by a particular Switch is proportional to the number of neighbors
that the Switch has, generally a fairly small number (no more
than 5 in the ARPANET, and probably of a similar magnitude in the
internet).
In the current Catenet routing algorithm, the size of the
routing updates is a function of the total number of gateways (or
equivalently, of the total number of component networks), a
number which can increase by a great deal over the years. In the
SPF algorithm, the size of the updates is a function of the
connectivity of the internet, which could not increase anywhere
near as much or as rapidly as the number of gateways. (In the
two years that SPF has been running in the ARPANET, the number of
IMPs has increased by a third, with another similar increase
expected in the next several months, while the connectivity, and
hence the average update size, has remained relatively constant.)
This is important, since we wouldn't want to get ourselves into a
situation where the update size eventually becomes so big (due to
network growth) that we can no longer fit a whole update into a
single packet (a situation that was imminent during the last days
of the original ARPANET routing algorithm.) In the internet, the
- 68 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
maximum size of an update packet is constrained by the component
network which has the smallest maximum packet size. It seems
likely that any component network whose packets are large enough
to carry the enormous TCP and IP headers should have no trouble
carrying the routing updates.
The amount of overhead due to routing updates is not only a
function of the update size, but also of the rate at which
updates are generated. In the ARPANET, since each IMP averages
the delay on its outgoing lines over a period of 10 seconds,
changes in delay on the lines emanating from a particular IMP
cannot occur, by definition, more often than once every 10
seconds. In addition to generating updates when the delay
changes, updates must also be generated when lines go down or
come up. In the ARPANET, a line which goes down cannot come up
for at least 60 seconds. So in an IMP with 5 neighbors, the most
updates that can be generated in a minute is 11 (due to each of
the lines either going down or coming up during the minute, for
5, and a delay change every 10 seconds, for 6). It is important
to note that this is the maximum rate at which updates can be
generated, not the average rate. Since IMPs need not generate
routing updates unless they have a "significant change" in delay
to report, the average rate can be much lower. In the ARPANET,
the average rate for generating updates is actually about one per
IMP per 40 seconds. This is a very limited amount of overhead.
Of course, the overhead will increase as the number of IMPs
- 69 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
increases, because there are just more IMPs to generate updates.
However, the amount of overhead is always under our control,
since we can always alter the averaging interval, or the
threshold of significant change in delay, to force updates to be
generated less frequently and thereby to reduce overhead. These
same principles apply to the internet also, so it doesn't seem as
if we will be generating enormous amounts of routing overhead.
There are some things we might want to do which would tend
to make the routing updates longer than so far indicated. For
example, if we defined several priorities of traffic at the
internet level, and mapped these priorities to different
priorities of some particular component network, we might want to
separately measure the delay across that network for each
priority. We might also want to compute a separate set of routes
across the internet for each priority. If we adopted some such
scheme, we would need to report in each update several different
delays for each Pathway, indexed by priority. These indexed
delays could then be used for computing a set of routing tables
indexed by priority, allowing traffic of different priorities to
use different routes. Of course, this would lengthen the
updates, adding more overhead. Part of the decision as to
whether to adopt such a scheme would involve an evaluation of the
trade-offs between the cost of this increased overhead and the
benefit of the expected improvement in performance. The issues,
however, are clear, and there are enough handles controlling the
- 70 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
amount of overhead so that we can put into effect any decision we
make.
It is important to understand that the number of routing
updates generated by a single internet event (such as the outage
of a gateway access line) is much less with SPF routing than with
the current Catenet routing algorithm. In SPF routing, a given
event causes the generation of ONE routing update, which must
then be sent to every gateway (thereby giving each gateway an
up-to-date copy of the "whole picture"). On the other hand, in
the current Catenet routing algorithm, a single internet event
causes a flurry of updates, as all gateways send and receive
updates repeatedly to and from each neighbor, until the routing
tables stabilize and the process settles down. This can take
quite a long time and quite a few updates, particularly if the
number of gateways is large.
In addition, in an internet with a large number of gateways,
the updates for the current Catenet routing algorithm are very
much larger than the SPF updates would be. It is clear that the
routing overhead due to a single network event would be much less
with SPF than it currently is. However, if we plan to send
routing updates when delay changes, as opposed to just when a
gateway access line comes up or goes down (as at present), then
we will be generating updates in response to more network events.
This tends to drive the overhead up. Again, the trade-offs are
- 71 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
relatively clear here; the amount of overhead simply trades off
against the responsiveness of the routing algorithm to changing
network conditions. The decision as to how to draw this
trade-off can be made as a policy decision, and can be changed if
performance considerations warrant it. The situation with the
current Catenet routing algorithm is quite different, since the
amount of overhead that it generates is almost impossible to
compute. In that algorithm, the number of routing updates
generated in response to a particular event depends on the order
in which the updates are processed by the individual gateways,
something that is essentially random and hence hard to predict.
The SPF algorithm has no such dependency.
The need for hysteresis in the Pathway up/down protocol run
between neighboring gateways is worth emphasizing. If
connections between neighboring gateways are allowed to come up
and go down with great frequency, causing a constant flurry of
routing changes, packets in transit will bounce around a lot.
Putting a limit on the frequency with which a gateway-gateway
connection can change state is needed not only to limit the
amount of overhead generated, but also to give some stability to
the routing. It is worth noting that the ARPANET, although
providing hysteresis in its own line up/down protocol, does not
provide any hysteresis in host up/downs. Hosts are allowed to go
down and come up repeatedly many times a minute, and this does
- 72 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
result in problems, causing congestion and instability.
Hysteresis in the gateway's Pathway up/down protocol will have to
be ensured explicitly; we cannot rely on the ordinary host access
protocol of the component networks to do the right thing. That
is, if a network interface goes down, we must keep it down for a
period of time, even if the network itself allows the interface
to come back up immediately.
4.5.2 Protocol
We turn now to the problem of how to disseminate the routing
updates around the Network Structure. Remember that the updates
generated by a particular Switch will contain information about
the delays to the neighbors of that Switch. When a Switch
generates an update, it must broadcast that update to ALL other
Switches. As a result, every single Switch will know the values
of delay between every single pair of neighboring Switches. It
is then straightforward to have each Switch run a shortest-path
algorithm which determines the shortest path from itself to each
other Switch. The basic idea is for each Switch to know the
entire topology of the Network Structure, so that the shortest
paths can be determined by a localized shortest path algorithm,
with no need for a distributed computation. In the ARPANET, the
IMPs do not start out with any knowledge of the topology. They
determine who their own neighbors are, and they reconstruct the
rest of the topology from the routing updates they receive.
- 73 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
It is possible to prove that, as long as all Switches have
the same information about the topology and the delays, then they
will produce routes which are consistent and loop-free. (That
is, the situation in which Switch A thinks its best path to B is
through C, and C thinks its best path to B is through A, can
never arise.) However, if some routing updates somehow get lost
before being received by every single Switch, then there is no
guarantee of consistent loop-free routing. In fact, if routing
updates get lost, so that different Switches have different
information about the topology or the delays, we would expect
long-term routing loops to arise, possibly making the Network
Structure useless for some period of time. So the protocol used
to broadcast the routing updates needs the highest possible
reliability. Of course, it will always take some amount of time
for an update to be broadcast around the Network Structure, and
during that time, some Switches will have received it and some
not. This means there will always be a transient period when
routing loops might arise. So another aim of the routing
updating protocol must be to keep this transient period as short
as possible. In the ARPANET, we have an updating protocol which
seems to provide these characteristics of extremely high
reliability and low delay. Some of its aspects adapt readily to
the internet, but others are more difficult to adapt. In what
follows, we first describe the ARPANET's routing updating
protocol, and then discuss its applicability to the internet.
- 74 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
Suppose IMP A has to generate a routing update, either
because of some "significant" change in the measured delay, or
because of a line up/down state change. Each update generated by
A has a sequence number, which is incremented by 1 for each new
update. (In the ARPANET, we use 6-bit sequence numbers, which
wrap around after 63.) After creating the update, IMP A sends it
to each of its neighbors. The update is transmitted as a packet
of extremely high priority; only the packets used in the line
up/down protocol are of higher priority. We use the notation
"A(n)" to refer to the update generated by IMP A with sequence
number n. Now let's look at what happens when a copy of update
A(n) is received by an IMP B. (IMP B is intended to be an
arbitrary IMP somewhere in the network, possibly identical to A
or to one of A's neighbors, but not necessarily so.) If B has
never received an update from A before, it "accepts" A(n), by
which we mean that it (a) remembers in its tables that the most
recent update it has seen from A is A(n) (i.e., the sequence
number n, the list of neighbors of A, and the delays from A to
each neighbor are stored in B's tables), (b) it forwards A(n) to
each of its neighbors, including the one from which it was
received, and (c) the SPF algorithm is run to produce a new set
of paths, given the new delay and topology information contained
in A(n). If B has received an update from A before, it
determines whether A(n) is more recent than the update it has
already seen, and "accepts" it (as just defined) if it is;
- 75 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
otherwise it simply discards A(n). The determination as to
whether A(n) is more recent than some previously received update
A(m) is made by a sequence number comparison (which, of course,
must account for the fact that sequence numbers can wrap around);
A(n) is not considered to be more recent than itself.
If one thinks a bit about this inductive definition of the
protocol, one sees that each IMP in the network will receive
every update which is generated by any IMP, and further that it
will generally receive a copy of each update on each of its
lines. This means of broadcasting an update from one IMP to all
other IMPs is called "flooding." It is highly reliable, since
updates cannot be lost in the network due to IMP crashes or
partitions. If there is any path at all between two IMPs,
flooding will get the update from one to the other. (Of course,
if there is no path at all from A to B, then updates cannot get
from one IMP to the other. However, this is not a problem, since
if traffic from A cannot even reach B, then it cannot use B's
outgoing lines, so there is no need for A to know the delays of
B's outgoing lines in this case. In saying that flooding
prevents updates from getting lost due to network partitions, we
are thinking of the case where an update is in transit from A to
B when a partition forms, such that A and B are in the same
partition segment, but the update is in a segment which is now
isolated from either A or B. Flooding ensures delivery in this
situation.)
- 76 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
Flooding also ensures that an update travels over the
shortest (in terms of delay) possible path. Basically, every
possible path is attempted, so the update necessarily gets
through first on the shortest path, by definition. In addition,
this means of transmitting routing updates does not depend in any
way on the routing algorithm itself. Since routing updates are
sent out all lines, there is no need to look in the routing
tables to decide where to send the routing update. The
transmission of routing updates is independent of routing, which
eliminates the possibility of certain sorts of disastrous
negative feedback.
One might think that a protocol which sends a copy of every
update on every line creates a tremendous amount of overhead. In
the ARPANET, however, the average update packet size is 176 bits,
and the average number of updates sent on each line (in each
direction) is less than 2 per second, for an average overhead of
less than 1% of a 50 kbps line. And this is with almost 75 IMPs
generating updates.
Of course, a protocol like flooding is only as reliable as
are the individual point-to-point transmissions from IMP to
neighboring IMP. We ensure reliability at this level with a
positive acknowledgment retransmission scheme. Note, however,
that no explicit acknowledgments are required. If IMP X sends
update A(n) to neighboring IMP Y, and then X receives from Y an
- 77 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
update A(m), where A(m) is at least as recent as A(n), we
consider that Y has acknowledged X's transmission of A(n). Since
an IMP which accepts an update sends it to all neighbors,
including the one from which it was received, in general, if X
sends A(n) to Y, Y will send A(n) back to X, thereby furnishing
the acknowledgment. We say "in general", since there is a little
further twist. As another reliability feature, we make each
update carry complete information, and forbid the carrying of
incremental information in updates. That is, each and every
update generated by an IMP A contains all the latest information
about A's neighbors and its delay to them, so that each update
can be fully understood in isolation from any that have gone
before. This means that if update A(n+1) is received and
processed by some IMP B, then the prior update A(n) is
superfluous and can just be discarded by B. In particular, if
IMP X sends A(n) to neighboring IMP Y while at the same time Y is
sending A(n+1) to X, then X can interpret the receipt of A(n+1)
from Y as an acknowledgment of the receipt of A(n); that is, X no
longer has to worry about retransmitting A(n), since that update
is no longer needed by Y. If no "acknowledgment" for an update
is received from a particular neighbor within a specified amount
of time, the update is retransmitted. Of course, it must be
specially marked as a retransmission, so that the neighboring IMP
will always "acknowledge" it (by echoing it back), even if the
neighbor has seen it before. This is needed to handle the case
- 78 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
where the update got through the first time, but the
acknowledgment did not. It should also be noted that all the
information in a routing update must be stored in each IMP's
tables in order to run the SPF computation. This means that if
it is necessary to retransmit an update to a particular neighbor,
the update packet can be re-created from the tables; it is not
necessary to buffer the original update packet pending
acknowledgment.
We must remember that if congestion forms in some part of
the network, we want routing to be able to adapt in a way which
can route traffic around the congestion. For this to have any
hope of working, we must be sure that ROUTING UPDATES WILL BE
ABLE TO FLOW FREELY, EVEN IF CONGESTION IS BLOCKING THE FLOW OF
DATA PACKETS. Therefore, routing updates in the ARPANET are not
sent by the ordinary IMP-IMP protocol, which provides only 8
logical channels between a pair of IMPs. That would be
disastrous, since congestion often causes all 8 logical channels
to fill up and remain filled for some time, blocking further data
transmission between the IMPs. Transmission of routing updates
must be done in a way that is not subject to this sort of
protocol blocking during periods of congestion. (This sort of
"out-of-band" signalling was quite easy to put into the ARPANET.
However, it is worth noting that such protocols as HDLC make no
explicit provision for out-of-band signalling, and it seems that
many networks are being built in which the routing updates will
- 79 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
not be able to flow when the network gets congested. Designers
of such networks will no doubt be quite surprised when they
discover what is inevitable, namely that their routing
algorithms break down completely in the face of congestion.) We
also want to be sure that we have enough buffers available for
holding routing updates, and that we process them at a relatively
high CPU priority.
There is one more twist to the updating protocol, having to
do with network partitions. A network partition is a situation
in which there are two IMPs in the network between which there is
no communications path. Network partitions, in this sense, may
be as simple as the case in which some IMP is down (an IMP which
is down has no communications path to any other IMP), or as
complex as the case in which four line outages result in
partitioning the network into two groups of 40 IMPs. When a
partition ends, we have to be sure that the two (or more)
segments do not get logically rejoined until routing updates from
all IMPs in each segment get to all the IMPs in the other
segments. That is, data packets must not be routed from one
segment to the other until all IMPs in each segment have
exchanged routing updates with all IMPs in the other segments.
Otherwise, routing loops are sure to form. We must also remember
that the sequence numbers of IMPs in one segment may have wrapped
around several times during the duration of the partition.
Therefore we must ensure that IMPs in one segment do not apply
- 80 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
the usual sequence number comparison to updates from IMPs in the
other segment.
We have dealt with these problems by adding the following
three time-outs to the updating protocol:
1) MAXIMUM INTERVAL BETWEEN UPDATES: Every IMP is required
to generate at least one update every minute, whether or
not there has been any change in delay or line state.
2) MAXIMUM UPDATE LIFETIME: If an IMP B has not received any
updates generated by IMP A for a whole minute, then B
will "accept" the next update it sees that was generated
by A, regardless of the sequence number.
3) WAITING PERIOD: When a line is ready to come up, it is
held in a special "waiting" state for a minute. While in
the waiting state, no data can be sent on the line.
However, routing updates are passed over the line in the
normal way, as if the line were up.
Since the ending of a partition is always coincident with
some line's coming up, these three features ensure that a
partition cannot end until a full exchange of routing information
takes place. They also ensure (given the facts that there is a
6-bit sequence number space and that IMPs can generate at most 11
updates per minute) that sequence numbers of updates generated
after the end of the partition are not compared with sequence
numbers of updates generated before the partition occurred.
- 81 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
The general idea of flooding the updates seems as important
in the internet as in the ARPANET. In general, we can expect the
internet to be subject to many more mysterious outages and
disturbances than is the ARPANET, and the reliability and speed
of flooding will be essential if an internet routing algorithm is
to have any hope of working. The issue of overhead may be
somewhat worrisome, though. If an IMP has to send each of 4
neighbors a copy of each update, it is just a matter of sending a
copy of a small packet on each of 4 wideband lines. On the other
hand, if a gateway has to send a copy of each update to each
neighbor, this may mean that it has to send 4 copies into a
single network, over a single network interface. This may be
somewhat more disruptive. Of course, this problem only exists on
networks which do not have group addressing. If a network allows
the gateways to be addressed as a group, then each gateway needs
only to place one copy of each update into the network, and the
network will take responsibility for delivering it to each other
gateway. (This might result in each gateway's receiving back its
own copy of the update, since the sending gateway will also be
part of the group, but that is no problem. As long as the
gateway can identify itself as the transmitter, it can just throw
away any updates which it transmitted to itself.) This idea of
sending the updates to all neighbors on a particular network by
using group addressing fits in well with an idea expounded in
section 4.1, namely the idea that a network should be able to
- 82 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
tell which of its hosts are gateways, and should inform the other
gateways when a new gateway come up. This same mechanism could
be used by the network to augment its group addressing mechanism,
to allow the group definition to change dynamically and
automatically as the set of gateways connected to it changes.
Unfortunately, few networks seem to have group addressing. Even
SATNET has only a primitive group addressing feature, although it
seems odd to have a broadcast network without full group
addressing capabilities. (Group addressing is much more complex
on a distributed network like ARPANET than on a broadcast
network.) Perhaps as further internet development proceeds, more
of the component networks will add group addressing, in order to
make their use of the internet more robust and efficient.
Retransmission of routing updates on a
gateway-to-neighboring-gateway basis, based on the scheme in the
ARPANET, also seems to offer no problems in principle. However,
the retransmission time-outs might have to be carefully chosen,
and tuned to the characteristics of the network connecting the
sending and receiving gateways. The retransmission time has to
be somewhat longer than the average round-trip delay in that
network, and this may vary considerably from network to network.
In principle, however, this is no different from the ARPANET,
where the retransmission timers for routing updates vary
according to the propagation delay of the phone line connecting
two IMPs.
- 83 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
There is a bit of a subtle problem that we discovered in the
ARPANET, having to do with the scheme of using the updates
themselves as acknowledgments. Suppose Switch A has two
neighbors, B and C. A receives a copy of update u from B, and
queues it for transmission to C. However, while u is still on
the queue to C, A receives a copy of u from C. If A had already
sent u to C, this copy from C would have served as A's
acknowledgment that C had received the update. But now, with u
on the queue to C, if we are not careful, A will send u to C
after having received a copy of u from C. When C gets this copy
of u from A it will not accept it (since it has already seen a
copy of u and sent that copy on to A), which will cause A to
retransmit u to C, resulting in an unnecessary retransmission.
In the ARPANET, we deal with this problem by turning on the
retransmission timer as soon as an update is received, rather
than when it is sent. That way, an update which is still queued
for transmission when its "acknowledgment" is received will still
get transmitted unnecessarily, but the retransmission timer gets
shut off, causing only one, rather than two, unnecessary
transmissions. A more logical scheme would be to check the
transmission queue to a Switch whenever an update is received
from that Switch. If a copy of the same update that was just
received is queued for transmission, it should just be removed
from the queue. This would prevent any unnecessary
transmissions. In the ARPANET, a few unnecessary transmissions
- 84 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
don't really matter, but in the internet, if we really want to
keep the overhead low, it is probably worthwhile trying to get
this just right. We must remember that network access protocols
may limit the number of packets we can get into the network
during some period, which makes it all the more important to
avoid sending unnecessary packets.
Suppose we find that for some reason or other, it is taking
a very long time to get updates from some gateway to one of its
neighbors. This would show up as an excessive number of
retransmissions of updates. In such a case, we would probably
have to consider that particular gateway-gateway Pathway to be
down, irrespective of what our ordinary Pathway up/down protocol
tells us. Remember that in order to ensure consistent and
loop-free routing, we must get the updates around the internet as
rapidly as possible. If updates cannot travel sufficiently
rapidly on some Pathway, then we just cannot use that Pathway at
all for transit within the internet. Attempting to keep that
Pathway up for transit can result in relatively long-term routing
loops, which could in turn cause a degradation in network
performance which swamps the degradation caused by not using that
Pathway at all. Especially disastrous would be a situation in
which ordinary data packets could pass, but routing updates, for
some reason, could not. It is hard to know what might cause such
a situation (perhaps a bug in the component network that we are
using as a Pathway), but it is certainly something we need to
- 85 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
protect against. (Note, however, that even if we declare some
gateway-gateway Pathway down, it does not follow that the network
underlying that Pathway cannot be used as a terminus network, to
which data for Hosts can be sent and from which data from Hosts
can be received. Even if some network is not usable for
providing a Pathway between two gateways on it, it may still be
useful for providing a Pathway between the gateways and some set
of Hosts.)
We have emphasized the need to transmit routing updates as
"out-of-band" signals, which bypass the ordinary communications
protocols (such as the IMP-IMP protocol in the ARPANET), so that
when congestion forms which causes those protocols to block, the
routing updates can still flow. That is, we would like to have a
protocol which is both non-blocking and non-refusing. This may
be quite difficult to achieve in the internet environment, where
sending an update from gateway to gateway requires us to use
whatever network access protocol is provided by the Pathway
network. Here our most difficult problem might be with the
ARPANET's 1822 protocol, which can cause blocking of the network
interface for tens of seconds. We really can't delay sending a
routing update for 15 seconds or so while the IMP is blocking, so
whenever this happens we would have to declare the pathway down.
In the ARPANET, we have two ways of trying to deal with
this. One way would be to send all packets into the ARPANET as
- 86 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
datagrams, which cannot cause blocking. Another way would be to
use the standard virtual circuit interface, but to obey the flow
control restrictions of the ARPANET (i.e., to control the number
of outstanding messages between a pair of hosts), and to avoid
the use of multi-packet messages (which can cause blocking if the
destination IMP is short of buffers, as ARPANET IMPs chronically
are). There are other situations in which blocking can occur,
but they all involve a shortage of resources at the source IMP,
and in such cases declaring the Pathway to be down is probably
the right thing to do. We do not want to be forced into
declaring Pathways down simply because we have ignored some
protocol restriction, but it seems much more sensible to declare
a Pathway down if, say, the IMP to which a gateway is attached is
too congested to provide reliable service for internet packets.
It is important to note that whatever restrictions we apply
to our use of the network access protocol apply not only to
routing updates, but also to all messages sent into the ARPANET
from the gateway. It would do no good, for example, to send in
routing updates as datagrams, while using non-datagrams for other
packets, since this would allow the other packets to block the
routing updates. At this point, it is not quite clear just what
the best scheme would be. The use of datagrams enables us to get
around the sometimes time-consuming but often unnecessary
resequencing which the ARPANET performs before delivering packets
to the destination host (it is neither necessary nor desirable
- 87 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
for the ARPANET to resequence routing updates before delivering
them to a gateway), but it also reduces the reliability of
transmission through the ARPANET, and it is not obvious how this
trades off. For each network which we intend to use as a
component of the internet, we will have to carefully study the
details of its network access protocol, and possibly do some
experiments to see how the various details of network access
affect the performance, in terms of delay, throughput, and
reliability of the network. Only by careful attention to the
details of network access on each particular network, and by
continuing measurements and instrumentation in the gateways to
see if we are getting the expected performance from the component
networks, can we hope to make the routing updating protocol quick
and reliable enough to ensure consistent and loop-free routing
throughput the internet. There are a few general principles we
might appeal to, such as making routing updates be the highest
priority traffic that we send into the component networks.
However, it is difficult to be sure a priori what effect even so
straightforward a principle might have. It's not hard to imagine
a poorly designed network in which low priority packets receive
better performance than high priority ones, under certain
circumstances. To make the internet robust, we need to be able
to detect such situations (and to gather enough evidence, via
measurements, to enable us to point the finger convincingly), and
we cannot simply assume that a component network will perform as
advertised.
- 88 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
If we might digress a little, the considerations of the
preceding paragraphs raise an interesting issue with respect to
the use of fragmentation in the gateways. We raised the
possibility of not using multi-packet ARPANET messages, and such
a strategy would doubtless require more fragmentation than is
presently done. Fragmentation in the gateways has long been
thought of as a necessary evil, necessary because some networks
have a smaller maximum packet size than others. If a gateway
receives a packet from network A which is too large to fit into
network B, then the gateway must either fragment it or drop it on
the floor. However, perhaps fragmentation is sometimes useful as
an optimization procedure. That is, some network may have a
suitably large maximum packet size so that fragmentation is,
strictly speaking, unnecessary. Nevertheless, the network might
actually perform better if given smaller packets, so that
fragmentation provides better performance. We see this in some
current Catenet problems. It seems that the BBN-gateway between
ARPANET and SATNET often receives packets from SATNET which are
2000 bits long, or twice the size of an ARPANET packet. The
gateway then presents these messages to the ARPANET as two-packet
messages. As it happens, two-packet messages generally give the
lowest possible throughput on the ARPANET (a consequence of the
limited buffer space at the destination IMPs and the fact that
the ARPANET assumes that all multi-packet messages will contain 8
packets); the gateway could probably obtain better performance
- 89 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
from the ARPANET by fragmenting the two-packet message into two
single-packet messages. Of course, the situation is a bit more
complicated in general than this may make it seem. If messages
are being sent from a source host through SATNET and then through
ARPANET to a destination host, best performance might well be
achieved by sending the messages as 2000-bit messages through
SATNET, then fragmenting them and sending them as 1000-bit
messages through ARPANET. However, what if the messages must go
beyond ARPANET, through another network, which handles 2000-bit
messages more efficiently than 1000-bit messages? This sort of
strategy, if useful at all, is best done in combination with the
hop-by-hop fragmentation/reassembly scheme suggested in IEN 187.
The part of the routing updating protocol which deals with
recovery from partitions (including the degenerate case of
initialization when a Switch comes up) is somewhat more tricky to
apply to the internet environment. In the ARPANET, we have a
number of one-minute timers. Each IMP must generate an update at
least once per minute; a line that is ready to come up must
participate in the updating protocol for a minute before being
declared up; and an update that has been held for a minute in an
IMP, with no later update from that update's source IMP having
been seen, is regarded as "old", in the sense that its sequence
number is no longer considered when the IMP is deciding whether
the next update it sees (from the same source) is acceptable. In
attempting to adapt these procedures to the internet, we must
- 90 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
take notice of the way in which these timers interact with each
other and with other features of the internet. Consider, for
example, the length of the maximum update lifetime, which
determines how long an update's sequence number remains valid for
the purposes of judging the acceptability of the next update.
There are two restrictions on the length of this timer:
1) A Switch A should not time out an update whose source
Switch is B unless there really is a partition which
destroys the communication path between A and B
(remember, this includes the degenerate case of a
partition where B simply goes down). This means that the
time-out period must be greater than the sum of the
maximum interval between updates PLUS the maximum amount
of time that an update from B could take to get to A.
2) The sequence numbering scheme used for the updates must
be such that the sequence numbers cannot wrap around in a
period of time which is less than the maximum update
life-time.
In the ARPANET, the sequence numbers cannot wrap in less
than a few minutes, each IMP generates an update at least once
per minute, and the time to get that update to all other IMPs is
negligible when compared to a minute, so a maximum update
lifetime of one minute is fine. In the internet, however, we
could not expect to measure transit times in the hundreds of
- 91 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
milliseconds; tens of seconds would be more like it. So even if
we forced each gateway to generate at least one update per
minute, we would still need a maximum update lifetime of several
minutes. And the longer our maximum update lifetime, the larger
our sequence number space must be (to prevent wrap-around), which
means additional overhead (memory and bandwidth) to represent the
sequence numbers.
A similar constraint applies to the "waiting period". The
purpose of the waiting period is to ensure that when a
gateway-gateway Pathway is ready to come up, it is not permitted
to carry data until an update from each other gateway traverses
it. Clearly, for this to have the proper effect, the waiting
period must be longer than the sum of the maximum transit time
plus the maximum interval between the generation of updates from
a single gateway. We would probably also have to set this to
several minutes. This does have a serious operational
consequence, namely that no outage will persist for less than
several minutes. This can be an inconvenience, lengthening the
time it takes to put out a new software release to all the
gateways, for example, and possibly affecting the MTTR
statistics, but it is something we just have to live with. Note,
by the way, that as long as the waiting period is at least as
long as the maximum update lifetime, a gateway that restarts
after a failure (or a reload) can start generating updates with
sequence number 0, irrespective of what sequence numbers it was
- 92 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
using before, since all its prior updates will have timed out (if
the timers are set right).
4.6 Limitations of Internetting
This discussion of routing in the internet points out some
of the inherent limits of internetting. Good performance
requires the use of a routing updating procedure which broadcasts
the updates in a very reliable and quick manner. Anything that
delays the routing updates, or makes their transmission less than
reliable, will lengthen the amount of time during which different
Switches have a different "picture" of the Network Structure,
which in turn will degrade performance. We believe that the
updating protocol we developed for the ARPANET solves these
problems in the context of the ARPANET. It seems clear, however,
that broadcasting routing updates in the internet is just going
to be slower and less reliable than it is in the ARPANET.
Although the same principles seem to apply in both cases, the
characteristics of the internet Pathways are not sufficiently
stable to ensure the speed and reliability that we really would
like to have. It is going to be very hard to ensure that we can
get our routing updates through the various component networks of
the internet in a timely and reliable manner, and it may be hard
to get the component networks to handle the internet routing
updates with enough priority to prevent them from being blocked
due to congestion. This is going to place a limit on internet
- 93 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
performance which we cannot avoid no matter what architecture we
choose.
The only way to eliminate this sort of problem would be to
have the component networks themselves give special treatment to
internet control packets, such as routing updates. Currently,
the component networks of the internet treat internet control
packets as mere data. We have suggested that in some cases, it
is impossible to meet certain of our goals without special help
from the underlying networks. For example, in our discussion of
the "gateway discovery protocol", we argued that preserving the
maximum flexibility for making topological changes in the
internet requires cooperation from the underlying networks. This
point can be generalized, though. The more cooperation we can
get from the underlying networks, the better we can make our
internet routing algorithm perform, and the better we can make
the internet perform. We would recommend therefore that serious
consideration be given to modifying the component networks of the
Catenet to maximize their cooperation with the internet.
Even if the component networks of the internet cooperate to
the fullest, there is another problem which may limit the
responsiveness of the internet routing algorithm. If there are
very long transit times across the internet, much longer than we
ever see in individual networks like the ARPANET, then the
responsiveness of routing is necessarily held down. This factor
- 94 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
will place a natural restriction on the growth of the internet.
At a certain point, it will become just too big to be treated as
a single Network Structure, so that further growth would make
routing too non-responsive to provide good service. That is,
eventually we reach a point of diminishing returns, where adding
more Switches, or even adding more levels of hierarchy, begins to
significantly degrade service throughout the internet by making
the routing algorithm too non-responsive. It is important to
understand that the notion of "big" here has nothing to do with
the number of Switches, but rather with the transit time across
the internet.
If there are two Hosts which cannot, for reasons like this,
be placed on the same internet, it may still be possible for them
to communicate, though at a somewhat reduced level of efficiency.
Each of the Hosts would have to be on some internet, but not
necessarily on the same one. Suppose, for example, that there
are two different internets, internet A and internet B, which
cannot be combined into one larger internet because the resultant
internet would be too large to permit a reasonably responsive
routing algorithm. However, it is still possible for each
internet to model the other one as an Access Pathway. Suppose
that Host H1 on internet A needs to communicate with Host H2 on
internet B. Then if a Switch SA of internet A can be connected
to a Switch SB of internet B, the internet A can represent Host
H2 as being homed to its Switch SA, via a Pathway (of whose
- 95 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
internal structure it is unaware) which is actually internet B.
A corresponding mapping can be made in the other direction,
permitting full-duplex communication. However, neither internet
could use the other as an internal (i.e., Switch-Switch) Pathway,
or the resulting configuration would be insufficiently
responsive. (This may seem akin to the regionalization against
which we argued in section 4.3.4. However, since neither
internet uses the other as an internal Pathway, there are no
problems of looping.) Naturally, just as Hosts on a common
network can expect to get more efficient communications than can
Hosts which must communicate over an internet, Hosts on a common
internet will get more efficient communications than will hosts
on different internets.
There are other reasons besides non-responsiveness which may
make it imperative to have separate internets which cannot use
each other as internal Pathways. For example, two internets
might cover the same "territory," geographically speaking, but
may be under the control of two different organizations, or may
use essentially different algorithms or protocols. In fact,
several different internets might even cover the same set of
Hosts, and consist of the same set of component packet-switching
networks. (It is important to remember that it is the set of
gateways which constitute the internet, not the set of component
networks. Imagine if every ARPA-controlled network had a Brand X
gateway and a Brand Y gateway. Then there would be two separate
- 96 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
internets, Brand X and Brand Y, which are logically rather than
physically separate.) Our procedure of having each internet
regard the other as an Access Pathway to a set of Hosts, but not
as an Internal Pathway, allows communication among Hosts on the
different internets, without introducing problems of looping, and
while preserving the maintainability of the individual internets.
Of course if the two internets have different access protocols,
then the Switches of one or the other internet (or both) must be
prepared to translate from one protocol to the other, but that is
a simpler problem than the ones we have been dealing with.
- 97 -
IEN 189 Bolt Beranek and Newman Inc.
Eric C. Rosen
REFERENCES
1. J.M. McQuillan, I. Richer, E.C. Rosen, "The New Routing
Algorithm for the ARPANET," IEEE TRANSACTIONS ON
COMMUNICATIONS, May 1980.
2. E.C. Rosen, "The Updating Protocol of ARPANET's New Routing
Algorithm," COMPUTER NETWORKS, February 1980.
3. J.M McQuillan, I. Richer, E.C. Rosen, ARPANET ROUTING
ALGORITHM IMPROVEMENTS: FIRST SEMIANNUAL TECHNICAL REPORT,
BBN Report No. 3803, April 1978.
4. J.M. McQuillan, I. Richer, E.C. Rosen, D.P. Bertsekas,
ARPANET ROUTING ALGORITHM IMPROVEMENTS: SECOND SEMIANNUAL
TECHNICAL REPORT, BBN Report No. 3940, October 1978.
5. E.C. Rosen, J.G. Herman, I. Richer, J.M. McQuillan, ARPANET
ROUTING ALGORITHM IMPROVEMENTS: THIRD SEMIANNUAL TECHNICAL
REPORT, BBN Report No. 4088, March 1979.
6. E.C. Rosen, J. Mayersohn, P.J. Sevcik, G.J. Williams, R.
Attar, ARPANET ROUTING ALGORITHM IMPROVEMENTS: VOLUME 1, BBN
Report No. 4473, August 1980.
- 98 -