IEN 184
ISSUES IN INTERNETTING
PART 1: MODELLING THE INTERNET
Eric C. Rosen
Bolt Beranek and Newman Inc.
May 1981
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
ISSUES IN INTERNETTING
PART 1: MODELLING THE INTERNET
1. Modelling the Internet
This is the first in a series of papers which attempt to
deal with the problems of internetting in a comprehensive manner.
By "internetting", we mean the establishment of data
communications among some set of host computers which cannot all
access the SAME data communications network (though we will, of
course, require that each host be on some particular data
communications network). The traditional approach to getting
data from a host on one network to a host on another is to pass
the data through an intermediate, or "gateway", host, which is a
host on both networks. As we shall see, however, building an
internet which is sufficiently robust, and which offers
sufficiently high performance, to be useful in day-to-day data
communications operations involves much more than simply pasting
networks together in a pairwise manner. Rather, it requires us
to build an entirely new network, which can be regarded as being
hierarchically "above" the existent data communications networks.
We shall see that building this new network is no simple task,
but that it raises all the same issues that one must deal with in
building any sort of data communications network. Our basic
approach will be to consider SYSTEMATICALLY the ways in which an
internet is and is not similar to "ordinary" data communications
- 1 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
networks, so that we can easily see how the knowledge we have
gained from studying such networks (in particular, the ARPANET)
can be applied to internetting. This paper will present a model
for the internet which will help us to organize the issues;
further papers will deal more explicitly with such issues as
internet access, addressing, routing, and congestion control.
1.1 The Model Described
We begin by introducing a very general model for a class of
abstract entities called NETWORK STRUCTURES. A Network Structure
consists of three kinds of entities: SWITCHES, PATHWAYS, and
HOSTS. When we say that a particular entity is a Host WITHIN
SOME PARTICULAR NETWORK STRUCTURE, we mean that within that
Network Structure it functions as a data sink and/or source, and
does not perform such functions as store-and-forwarding traffic
which originated elsewhere and is destined for elsewhere. By
saying that a certain entity is a Switch WITHIN A PARTICULAR
NETWORK STRUCTURE, we mean that, within that Network Structure,
it is responsible for store-and-forward functions, i.e., for
receiving data from a source Host, and sending it (possibly
through a sequence of intermediate Switches) into a destination
Host. A Pathway WITHIN A PARTICULAR NETWORK STRUCTURE is a
communications path which has as one endpoint a Switch of the
Network Structure, as its other endpoint either a Switch or a
Host of that Network Structure, and NO intermediate Switches of
that Network Structure.
- 2 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
It is important to understand that the notion of a Network
Structure is intended to be an abstraction which we use in order
to impose a conceptual organization on a set of physical
entities. It makes no sense simply to ask of some particular
computer, is it a Host or a Switch, unless one also references
some particular Network Structure. Saying that a computer is,
e.g., a Switch, attributes to it a certain functionality relative
to a certain Network Structure. A particular computer might well
be a Switch in one Network Structure while simultaneously being a
Host within another Network Structure. (We will capitalize the
terms "Host," "Switch," "Pathway," and "Network Structure" as a
reminder of the abstract nature of these terms.)
Let's look at some examples. The ARPANET can be regarded as
a Network Structure whose Switches are the IMPs, whose Pathways
are the telephone lines that connect the IMPs, as well as the
1822 and VDH lines, and whose Hosts are the devices connected to
the IMPs via either the 1822 or VDH interfaces. From the
perspective of this Network Structure, the Pathways (telephone
lines) have no internal structure, but rather are merely a
passive and transparent medium. When we say that the Pathways
have no internal structure, we mean simply that they contain no
intermediate Switches (i.e., IMPs) and no Hosts of the particular
Network Structure (the ARPANET) under discussion. Of course,
this is quite a significant abstraction. What we regard as a
simple wire (a telephone line) may in fact be no wire at all, but
- 3 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
an entire network, the telephone network! Within the telephone
network, there may be any number of fancy computer switching
devices, which might be just as complicated as the ARPANET's
IMPs. From the perspective of the telephone company, one might
want to regard each telephone line as a Network Structure, which
contains exactly two Hosts (viz., the two IMPs at the end-points
of the line). The Switches of this Network Structure are the
telephone switching devices, and the Pathways really are just
wires. Or, if we had reason to, we could regard the ARPANET as a
sort of hybrid Network Structure, whose Switches included both
the IMPs and the telephone company switching devices, and whose
Pathways were wires terminating either at the IMPs or the other
switching devices. As it happens, we generally don't find this
last means of conceptual organization to be very useful. Since
we have no control over, and little information about, the
telephone company switching devices, it is most "convenient" not
to have to think about them, but rather to just regard each
telephone line as a simple Pathway, with no internal structure,
and no intermediate Switches. It is important to understand that
calling the ARPANET a Network Structure whose Switches are IMPs
and whose Pathways are telephone lines does not beg any questions
about how the telephone network really works; it is just a matter
of imposing a conceptual organization that we find useful for
some purpose.
- 4 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
Of course, the telephone lines are not the only Pathways in
the ARPANET. Each (local or distant) host is also the endpoint
of a Pathway, though one which really is a wire. In general, we
will find it useful to distinguish those Pathways in a Network
Structure which connect Host to Switch (ACCESS PATHWAYS) from
those which connect Switch to Switch (INTERNAL PATHWAYS).
Another example of a Network Structure is one whose Switches
are the gateways on the ARPA Catenet, whose Pathways are segments
of ARPA-controlled networks, and whose Hosts are hosts on the
networks which are part of the Catenet. Within this Network
Structure, the gateways must be regarded as Switches, since they
perform store-and-forward functions, and data from one host to
another is routed through a sequence of gateways. Of course, a
gateway, while a Switch within the Network Structure of the
Catenet, may also be a Host within the Network Structure of the
ARPANET. The proper classification of an entity is a matter of
what function it performs within the concrete realization of some
particular Network Structure; the same physical entity may
perform different functions in different Network Structures of
which it is a part.
We should be a bit more precise about the Pathways of the
Catenet Network Structure. Suppose there are 4 gateways on the
ARPANET. Then the gateways are fully connected through a set of
12 distinct Pathways (i.e., each gateway has a Pathway to each of
- 5 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
the other 3 gateways). Although each of the 12 Pathways utilizes
the ARPANET, we really have 12 distinct Pathways, each of which
has different characteristics as regards delay, throughput, and
operability. That is why we said above that the Pathways of the
Catenet should be identified with SEGMENTS of ARPA-controlled
networks, rather than with the entire networks. Furthermore,
each of the 4 Gateways has a distinct Pathway to EACH host on the
ARPANET. That is, within the Network Structure of the Catenet,
each of the hosts on the ARPANET (all of which are also Hosts on
the internet) is MULTI-HOMED to each of the 4 Gateways via a
distinct Pathway. IN PRINCIPLE, THIS MULTI-HOMING IS NO
DIFFERENT THAN THE MULTI-HOMING OF A SINGLE (LOGICALLY ADDRESSED)
HOST TO TWO DIFFERENT ARPANET IMPS (see IEN 183). As we shall
see, regarding all the Hosts on the Catenet as being multi-homed
to the Switches (i.e., gateways) of the Catenet is a very
important feature of the network architecture we will propose for
internetting. We will argue that many of the problems
encountered in the current Catenet configuration are a result of
the failure to properly conceive internet hosts as being
multi-homed, and that the lessons learned from a study of how to
do multi-homing on individual packet-switching networks can be
applied fairly directly.
The "Network Structure" model is intended to be completely
general. We can, for example, handle an arbitrarily nested
hierarchical internet by establishing a Network Structure whose
- 6 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
Pathways are themselves complex internet configurations. We can
also model overlapping internet configurations. Consider, for
example, four machines, A, B, C, and D connected in order in a
ring. In principle, we could treat this as two Network
Structures, one in which A and C are Switches and B and D are
Hosts, and another in which B and D are Switches and A and C are
hosts. This might be useful if, for example, we have two
different internets, with incompatible gateways, connecting the
same set of packet-switching networks. The model should be
general enough to accommodate complex configurations like this.
1.2 Deficiencies of the Old Model
The idea that the design of an architecture for the internet
should be guided by the development of an abstract model is
hardly original. The earliest IENs often considered the need for
a model, but the discussion there seems to be at an insufficient
level of abstraction. That is, there is much discussion of the
need for a "model of a gateway," but no discussion of the need
for a model of the internet as a gestalt, with a network
architecture of which the gateways are only a part.
It is apparent though that gateway designers and
implementers did work with an IMPLICIT model of the internet in
mind. While the gateway was the focus of much discussion,
however, little critical attention was focussed on the implicit
model of the internet itself. This implicit model represents the
- 7 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
gateways as ordinary network nodes, and the component networks of
the internet as ordinary network lines. Surprisingly, hosts are
not represented at all in this model. (One may be tempted to
think of a host as a sort of piece of one of the "lines" in this
model, but remember that the lines are not supposed to have any
internal structure.) The internet routing problem was conceived
of as the problem of how to get data from one gateway through a
sequence of intermediate gateways to a destination network
(which, in the model, is a destination line!?).
Our experience with the Catenet should have made it quite
clear by now that the basic idea underlying this implicit model
is overly simplistic. This basic idea is that the end-user will
know what network his destination host is attached to, and only
needs the gateways to get his data somewhere or other (it doesn't
matter where) on that destination network. At that point, the
destination network is supposed to take over, and there is no
further work for the gateways to do. We now know, of course,
that things are not so simple. The way in which the gateways get
traffic to the destination network may be very important. A
particular host on a particular network might be reachable from
one gateway on that network, but not from another gateway on that
network. (This is the "partitioned net" problem.) Or
performance considerations might dictate that a host be reached
through one gateway in preference to another gateway on that same
net. It should not be any surprise that this sort of problem has
- 8 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
proved very troublesome in the Catenet, for the problem is built
right into the conceptual mechanism that guided the development
of the Catenet. The fact that the old implicit model of the
internet contains no representation at all of hosts makes it
virtually impossible for gateways that were built with that model
in mind to have any means of representing host-specific
information. It also makes it virtually impossible to take
advantage of (or even to take cognizance of) the way in which
Hosts can be regarded as being "multi-homed" to the gateways.
Failure to model the hosts also makes it difficult to handle the
case of hosts which are not always connected to the same network
(e.g., "mobile hosts"), or hosts which are connected to two or
more networks.
Further difficulties arise from the way in which networks
are represented as "lines." If a network is like a line, then it
must be either up or down. There is no way to represent the fact
that some "parts" of the "line" can be reached from only one
end-point, but not the other. That is, it is difficult to make
the internet system respond to peculiarities in the behavior or
operational status of the underlying packet-switching networks,
since much of that behavior has no analog in the world of
telephone lines. Of course, it cannot really be claimed that
problems like these can never be resolved at all within the
current Catenet configuration, but only that possible resolutions
will not fit easily into the Catenet's architecture, and so will
- 9 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
generally appear to be "kludges" or "hacks" which are grafted on
in order to get around particular operational problems as they
happen to arise. Perhaps a reading of some of the more recent
IENs will bear out this impression.
In attacking the old implicit internet model, we are not
simply trying to beat a dead horse, or to attack a straw man.
Rather, we are just trying to emphasize that the way in which one
initially models or thinks of a set of related problems will
necessarily have a large effect on the way the problems are dealt
with in the final system. A good model for the internet should
provide a framework for discussion of internetting issues which
enables us to place each issue in proper perspective, and which
makes clear the inter-relationships among the various problems
and proposed solutions to them. When important problems (such as
the "partitioned net" problem) cannot even be stated in the terms
of a particular model, it becomes clear that that model does not
provide a proper framework for the discussion of the issues. A
good model should also make it possible to evaluate the effect of
various schemes as part of an integrated system, making it easier
to determine whether or not some proposed scheme gives rise to
more problems than it solves. By allowing us to see solutions to
particular problems as part of an integrated system, the model
also gives us a means of choosing among different schemes which
seem to solve the same problem, since some of those schemes may
fit more easily or more naturally into the integrated system than
- 10 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
do others. A good model should also suggest solutions to
problems that have previously seemed very vexing (we shall argue,
in subsequent papers of this series, for example, that
representing hosts as being multi-homed to gateways suggests
certain addressing schemes that might otherwise be overlooked,
and also subsumes a number of problems previously thought
unrelated under a common rubric). We believe that the model we
proposed in the previous section offers a much more coherent
framework; hopefully this will become apparent as we begin to
work through the issues of internetting in this and subsequent
papers.
1.3 The Importance of Pathway Characteristics
As we have already pointed out, the proposed new model of
the internet as a Network Structure allows us to see the ARPANET
itself as an internet, built upon pieces of the telephone
network. In principle, then, the ARPANET is no different than
the Catenet, which is an internet built upon pieces of the
ARPANET, SATNET, and various other ARPA-controlled networks. Yet
it does seem that the Catenet poses problems which are more
difficult and less tractable than are the problems posed by the
ARPANET. Why should this be the case, if the ARPANET and the
Catenet are both internets of a sort? The answer seems to lie in
the characteristics of the individual networks that constitute
the Pathways in these two different "internets." The pieces of
- 11 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
the telephone network which transmit data within the ARPANET do
so with well-known and well-understood (indeed, with constant)
delay characteristics. The capacity of these pieces of the
telephone network is also a constant. Many of the ARPANET's
protocols and algorithms (both internally and at the host access
level) make use of these facts, and break down when applied to
Pathways of significantly different characteristics. Even within
the ARPANET, we have seen the importance of modifying our
protocols and algorithms to take account of differing Pathway
characteristics. For example, the line up/down protocol which
each pair of neighboring IMPs runs together to determine the
operational status of the line connecting them must be tuned
differently for lines of differing bandwidths or propagation
delays. Particular difficulty has been encountered in making
this protocol work properly over "line 77," the "transparent"
connection via SATNET to London. One problem in trying to extend
ARPANET-like protocols and algorithms to the Catenet environment
is to come to a better understanding of how those protocols and
algorithms actually depend on assumptions about the Pathway
characteristics. Since many of these assumptions may be
implicit, and nowhere clearly stated, this is not a simple
problem. As we develop our proposed internet architecture, we
will try to emphasize the role played by assumptions about
Pathway characteristics.
- 12 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
(Although we will be primarily concerned with protocols and
algorithms to be used in the actual day-to-day operation of the
internet, it is worth noting that the variability of the Pathway
characteristics of the internet also has implications with
respect to the topological layout of the internet. When
designing the topology of a packet-switching network, one often
makes use of mathematical tools (often automated) for optimizing
the topology with respect to some cost-function, such as delay.
These mathematical tools are based on particular mathematical
models of networks which in turn are based on results from
queuing theory which assert a particular relationship between
delay and load over telephone lines. Whatever the merits of
those mathematical models (and there is much to question in
them), they will not be applicable at all to the topological
design of the internet. When a Pathway is a packet-switching
network, rather than a telephone line, it is probably meaningless
even to ask what its bandwidth is, since it just does not have a
constant bandwidth. That is, the maximum throughput that can be
obtained between two gateways over a particular packet-switching
network will vary quite a bit over time, and will depend on what
happens to be going on within that network. In addition, the
relationship between delay over a packet-switching network and
the offered load is much more difficult to model mathematically
than is the same relationship over a telephone line. Issues of
how to properly lay out the topology of the internet to obtain
- 13 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
best performance or least "cost" probably will not be able to be
dealt with in any systematic way until we have much more
experience with day-to-day internet operations.)
The gateways which are currently deployed on the Catenet do
not seem to take Pathway characteristics into account at all.
Certainly there has been no attempt to optimize the gateways to
the particular packet-switching networks that they are connected
to, or even to make the gateways take proper notice of the
various protocol messages that the networks will send to the
gateways. To some extent, gateways really do seem to treat
packet-switching networks as mere wires, simply throwing the bits
at the network interface, and not dealing with the various
exception states that continually arise when attempting to access
a network. One of the main themes that we shall be developing is
that A ROBUST AND HIGH-PERFORMANCE NETWORK STRUCTURE JUST IS NOT
POSSIBLE UNLESS THE SWITCHES ARE CAREFULLY TUNED TO MAKE THE MOST
EFFICIENT POSSIBLE USE OF THE PATHWAYS. As we have stated above,
the ARPANET IMPs often have to be tuned to the particular
characteristics of different telephone lines, and it is that much
more important for the gateways to be tuned to the particular
characteristics of the packet-switching networks that serve as
Pathways between them. It is important to understand that this
sort of issue does not apply only to the way in which gateways
use the INTERNAL PATHWAYS of the internet, but also to the way in
which hosts and gateways use the ACCESS PATHWAYS of the internet.
- 14 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
We will develop these issues in much more detail in subsequent
papers.
We have claimed that the only reason we tend to regard the
telephone network as a Pathway with no internal structure is that
we find it "convenient" to do so. If we are going to properly
apply the Network Structure model to the ARPANET, the Catenet, or
any other networking or internetting environment, it is important
to come to a clear understanding of just when it is and is not
"convenient" or "useful" to ignore the internal structure of a
communications medium, and model it as a Pathway. (Though
ignoring the internal structure of a communications medium is NOT
the same thing as ignoring its delay/throughput/reliability
characteristics; as we shall repeatedly emphasize, there are no
conditions under which it is possible to do that without
incurring extreme penalties in efficiency and/or reliability.)
There are basically two good reasons why we might want to ignore
the internal structure of a communications medium:
1) Efficiency. Some algorithms or protocols in the Network
Structure may need to be driven off some sort of model or
representation of the network. For example, the SPF
routing algorithm in the ARPANET has a database which
represents the network topology. (We will often use the
term "SPF routing" to refer to the ARPANET's current
routing algorithm [1,2], in contradistinction to the
- 15 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
ARPANET's original routing algorithm [3]. The Catenet's
current routing algorithm is based on the original
ARPANET routing algorithm, but internetters should be
aware that that algorithm had a number of serious
deficiencies, especially under heavy load, and was
removed from the ARPANET over two years ago, to be
replaced with SPF routing.) Dividing a single network
into several different Network Structures, and
representing some of those as Pathways with no internal
structure, may be necessary if we need to keep a bound on
the size of the database while allowing the actual
physical configuration of the network to grow without
bound. This is one of several important considerations
driving the internet development.
2) Partial transparency. One may want to be able to replace
the networks which underlie certain Pathways without
having to make extensive changes to the software of the
Switches. Or one may simply not be able or willing to
get any information about some underlying network.
Either of these is a good reason to try to treat that
underlying network transparently. Note, however, that
the best that we can hope to achieve is PARTIAL
transparency. If a Pathway is replaced by another
Pathway of very different characteristics, we cannot
realistically expect to maintain efficient performance
- 16 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
without modifying the Switches in some way to take
account of the new characteristics. However, it may be
possible to restrict the magnitude of the changes; for
example, perhaps only the software in the Switches which
are the endpoints of the Pathways will need to be
changed. This is an issue that we will have to consider
in great detail; certainly it is one of the most
important considerations driving the internet effort.
Note that these considerations, important as they may be, are
really just matters of degree, and generally must be traded off
against other considerations. We can ignore the internal
structure of a Pathway to a greater or lesser degree. It is
possible, for example, that we will want our internet gateways to
exchange information with certain ARPANET IMPs, even though in
general we want the internet gateways to be able to ignore the
internal structure of the ARPANET. The principle of ignoring the
internal structure of a Pathway is supposed to be a tool to help
us, not a straitjacket to prevent us from getting needed
information. This is another issue to which we shall return
repeatedly in subsequent papers of this series.
One of the aspects of a Network Structure that is most
sensitive to Pathway characteristics, and to the decision to
ignore the internal structure of a Pathway, is its
MAINTAINABILITY. Maintainability is one of the most important,
- 17 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
though most neglected, areas of network design. In the long run,
the ability to maintain the network (which means the ability to
isolate faults and to repair them) can have a much larger effect
on the network's efficacy as a communications utility than almost
any other consideration. In some sense, maintainability is the
"bottom line;" if a network is subject to repeated inexplicable
failures and degradations, then the users will be driven away,
and all the effort that has gone into careful optimizations of
the algorithms and protocols will have been wasted. In a complex
Network Structure, which may include Pathways of arbitrary
internal complexity, maintainability is a very crucial issue. A
good example of the kinds of problems that can arise may be taken
from our experience with the ARPANET's line 77 (the "transparent"
connection to the London-TIP via SATNET). The ARPANET generally
treats this as if it were a telephone circuit, even though it
actually consists of a large number of terrestrial access lines,
SIMPs (SATNET nodes), and satellite broadcast facilities, any
component of which might fail in its own peculiar way. When this
special connection was installed, the intention was that it be as
transparent as possible to the ARPANET. It turns out, however,
that a side-effect of treating SATNET transparently is that IT
ALSO BECOMES TRANSPARENT TO THE FAULT-ISOLATION TECHNIQUES WHICH
ARE USUALLY USED FOR TROUBLE-SHOOTING ARPANET LINES. That is,
the usual fault isolation techniques do not see into the
structure of this "line", and hence can say no more than that the
- 18 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
line is up or down. While this is a consequence of the
transparent design, it causes great difficulty, especially since
the various components of this line are maintained by different
organizations, each of which prefers to believe that the problem
is someone else's responsibility. Furthermore, since the IMPs at
each end of the line (which are also Hosts on the Network
Structure of SATNET) don't realize that they are actually
accessing another network, and don't use the usual network access
protocol for SATNET, some of SATNET's standard fault isolation
techniques are bypassed too. A problem that has been recurring
with some frequency is that the ARPANET's line up/down protocol
just will not bring the SATNET "line" up, even though SATNET
itself seems to be working fine, according to the independent
SATNET monitoring. At one time, the team of ARPANET and SATNET
people working on the problem originally seemed to be in
agreement that the source of the problem was in the design of the
ARPANET's line up/down protocol. On further investigation,
however, it turned out that the real problem was that the
terrestrial access line between the London-TIP and one of the
SIMPs really was experiencing intermittent failures, and hence
that the ARPANET's protocol had been performing correctly when it
refused to bring the SATNET "line" up. However, since neither
the SIMP nor the London-TIP (really a host on SATNET) treated
this access line as SATNET-host access lines are normally
treated, the SATNET people found it very difficult to test this
- 19 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
line by itself in order to do fault isolation. If we have a
Network Structure whose Pathways can themselves be arbitrarily
complex and nested internets, then this sort of problem can be
expected to arise with great frequency, UNLESS PROPER
INSTRUMENTATION AND FAULT ISOLATION MECHANISMS ARE DESIGNED INTO
THE NETWORK STRUCTURE FROM THE VERY BEGINNING. To some extent,
some of these problems may just be inevitable once we decide to
ignore the internal structure of a Pathway. The extent to which
this is or is not true is a very important issue for us to
consider, since it may ultimately be one of the most important
factors in determining whether a reliable, operational, flexible,
and growing internet configuration is really feasible. We will
try to keep maintainability issues in mind throughout our entire
discussion of the internet architecture that we propose.
To a lesser extent, this sort of problem can occur even
purely within the ARPANET. Since ARPANET links are really pieces
of the telephone network, it is worth asking whether the
transparency of the telephone network impacts our ability to
maintain the ARPANET. In fact, this does sometimes cause
problems. When the ARPANET Network Control Center complains to
the telephone company that a line is not operational, they really
cannot provide the telephone company with very much data as to
what is really wrong. Sometimes it takes the telephone company a
long time to fix the problem, and it is not uncommon for the
telephone company to claim that a line is fixed and to return the
- 20 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
line to the ARPANET, after which it is discovered that the
ARPANET's line up/down protocol still will not bring it up
(because the packet error rate is too great). Yet the situation
is generally acceptable -- the ARPANET itself does a good enough
job of detecting when there are problems with the lines, and the
phone company does a good enough job (generally) of fault
isolation within their own network to be able to fix problems
relatively quickly. However, in a Network Structure whose
Pathways consist of packet-switching networks, rather than
telephone lines, we probably wouldn't be so lucky. The more
complex and poorly understood the Pathways actually are (and the
behavior of packet-switching networks, not to mention internets,
is still quite poorly understood), the less likely it is that a
simple complaint to the maintainer of the Pathway will get timely
results. As the Pathway characteristics become more and more
complex, it will become more and more important to have
instrumentation at all levels, including the Switches and Hosts
at Pathway end-points, to aid in diagnosing possible problems.
As much as we might want to be able to regard the Pathways as
fully transparent, it may turn out that the sort of
instrumentation needed to help in fault isolation is dependent on
the particular characteristics of the Pathway. This is another
issue that we will have to keep in mind throughout.
Wherever possible, as we develop our proposed internet
architecture, we will try to "parameterize" the effect of Pathway
- 21 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
characteristics on the robustness and performance of the
architecture. It will certainly be important to know whether it
is really possible to build a robust high-performance Network
Structure out of Pathways with totally arbitrary characteristics
(probably not), and if not, just how many constraints we must put
on the Pathway characteristics in order to get reasonable
performance out of our architecture. This approach will help us
to get some understanding in advance of how large and varied a
configuration our architecture can support. This approach will
also help us to understand how our architecture can be adapted to
other applications in which we can place more constraints than
would be appropriate for the Catenet. Consider, for example, a
Network Structure all of whose Pathways are versions of the
ARPANET which are largely homogeneous and under the control of a
single organization. Within this Network Structure, we might be
able to introduce much more effective and efficient routing and
congestion control mechanisms than in a Network Structure whose
Pathways consist of many different kinds of networks controlled
by many different organizations with varied interests (e.g., the
Catenet). In fact, this rather homogeneous Network Structure
might not properly be called an "internet" at all; it might just
be regarded as the ARPANET with area routing. ("Area routing"
refers to any routing scheme in which a network is divided into
several areas, such that Switches in each area have explicit
routes only to other Switches in the same area, but not to
- 22 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
Switches in other areas. Routes are available for getting to
other areas, but the internal structure of these other areas is
disregarded. The term is usually applied to routing schemes used
in single homogeneous, packet-swtiching networks, as opposed to
internets, however.) One of the advantages of our model is that
it enables us to see internetting and area routing as
applications that differ only in regard to the Pathway
characteristics of the appropriate Network Structure.
1.4 A Functional View of the Internet
Let's look now at how we might model the OPERATION of a
Network Structure. There seem to be four main steps involved in
getting data from a source Host to a destination Host:
1) A source Host submits a message to a source Switch,
providing it with the name of a destination Host to which
the message should be delivered, as well as with any
other information which is needed to specify necessary
constraints on the characteristics of data delivery.
(Note that we said "the NAME of a destination Host", not
the address of a destination Host. We will return to
this very important point in later papers.)
2) The source Switch must map the name of the destination
Host into the address OF A DESTINATION SWITCH. This may
or may not be identical to the source Switch itself. If
- 23 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
the name of the destination Host maps to several possible
destination Switch addresses (multi-homing), the source
Switch must choose one, and this must be one which has a
currently operational Pathway to the destination Host.
3) Using the routing scheme of the Network Structure, the
source Switch must get the message to the destination
Switch, via some (possibly empty) sequence of
intermediate Switches.
4) The destination Switch must get the message to the
destination Host.
This model of operation attempts to make a clear separation
between the protocols which the source and destination Hosts must
use to access the Network Structure (steps 1 and 4), the
protocols which the Network Structure uses internally to move
data from one point to another (steps 2 and 3), and the protocols
used by the Hosts to talk to each other. This separation is
required by the precepts of protocol layering, and also by common
sense, since only with a clear separation of access functions
from internal functions can we maintain the flexibility to make
internal changes in the Network Structure without impacting the
access software in the Hosts. The need for this separation
between access functions and internal functions is taken for
granted in most ordinary packet-switching applications, but has
not been incorportated at all into the current Catenet. The
- 24 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
current Catenet protocols freely intermix access functions with
internal functions, and in fact there is only a single protocol,
IP, which contains elements needed for Hosts to talk to each
other, for Hosts to talk to Switches, and for Switches to talk to
Switches. This seems to be a consequence of the old idea that
the internet is just a series of networks pasted together by
hosts which are on two or more of the networks. That idea makes
it difficult to distinguish the gateways from the hosts, or to
properly take account of the fact that although gateways are
Hosts in some Network Structure (that of the individual
packet-switching networks), they are also Switches in another
(that of the internet). A proper distinction of access functions
from internal functions seems essential, though, if we are to
build an internet which functions as a real network, rather than
as a series of pasted together networks and gateways.
Any Network Structure which is to be operational must have
some way of performing these four steps. Furthermore, in order
for particular applications to get satisfactory performance out
of their use of the Network Structure, the Network Structure must
perform these functions under certain constraints with respect to
delay, throughput, reliability, sequential delivery, and fault
detection. (By "fault detection", we mean the ability of the
Network Structure to inform the user about exceptional
conditions, such as the destination host's being down or
unreachable. This constraint is often neglected in the design of
- 25 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
network architectures or protocols, but seems quite important in
a robust operational environment.) The ability to gather and
report exception information at various levels of protocol is
important both for system maintenance and for general user
satisfaction. Nothing makes a worse impression on a user than a
mysterious degradation in service about which he can get no
feedback. It is not immediately obvious, though, to what extent
the various protocols used to operate a Network Structure must
ensure that these constraints are met. It is generally
understood that if some application requiring inter-process
communication must place constraints (such as sequentiality) on
the characteristics of the communications, then the application
itself must utilize some high level protocol (at the Host-Host
level, or even higher) which will enforce the constraints, rather
than depending on the low-level communications medium to enforce
them. What seems to be less generally understood is the fact
that, in general, and other things being equal, the performance
which some user gets from his high-level protocol will be better
if the lower level protocols pass data to the high level
protocols in a way which already satisfies the constraints that
the high level protocols must impose. For example, an
application which requires sequentiality will have to use a high
level protocol like TCP which guarantees sequentiality. However,
the end user will generally see much better performance, in terms
of throughput and delay, if the protocols below TCP maintain
- 26 -
IEN 184 Bolt Beranek and Newman Inc.
Eric C. Rosen
sequentiality, since this will require TCP to do less work, and
put less of a drain on the resources (such as buffer space,
sequence number space, and host CPU bandwidth) needed by TCP.
The area of fault detection and reporting provides a good example
here. A user attempting to talk to a dead host might find his
TCP typing the message "excessive retransmissions" to him. This
sort of message would not generally be too useful to a user
since, if he is not a network expert, it gives him no clue of
what the actual situation is. The average user might prefer to
know that the destination host is dead, so he can try again
later, but this information is very difficult, if not impossible,
to obtain solely at the TCP level, although it might be quite
simple to obtain at a lower protocol level. Of course, putting
more functionality in lower level protocols also has a cost, as
well as a potential benefit, and costs often trade off with
benefits in surprising ways. As we shall see, producing an
operational Network Structure requires a large number of
protocols, and we will attempt to deal with considerations like
these as we consider specific protocol issues. Not surprisingly,
we will find that cost-benefit trade-offs for both access
protocols and internal protocols will often depend on the
characteristics of the Pathways in the Network Structure.
- 27 -
IEN 184 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, G. Falk, I. Richer, "A Review of the
Development and Performance of the ARPANET Routing
Algorithm," IEEE TRANSACTIONS ON COMMUNICATIONS, December
1978.
- 28 -