-----------------------------------------------------------
Computer communication network design
Experience with theory and practice*
by HOWARD FRANK
Network Analysis Corporation
Glen Cove, New York
and
LEONARD KLEINROCK
University of California
Los Angeles, California
ROBERT E. KAHN
Bolt Beranck and Newman Inc.
Cambridge, Massachusetts
INTRODUCTION
The ARPA Network (ARPANET) project brought
together many individuals with diverse backgrounds,
philosophies, and technical approaches from the fields
of computer science, communication theory, operations
research and others. The project was aimed at providing
an efficient and reliable computer communications
system (using message switching techniques) in which
computer resources such as programs, data, storage,
special purpose hardware etc., could be shared among
computers and among many users? The variety of
design methods, ranging from theoretical modeling to
hardware development, were primarily employed
independently, although cooperative efforts among
designers occurred on occasion. As of November, 1971,
the network has been an operational facility for many
months, with about 20 participating sites, a network
information center accessible via the net, and well over
a hundred researchers, system programmers, computer
center directors and other technical and administrative
personnel involved in its operation.
In this paper, we review and evaluate the methods
used in the ARPANET design from the vantage of
over two years' experience in the development of the
network. In writing this paper, the authors have each
made equal contributions during a series of intensive
* This work was supported by the Advanced Research Projects
Agency of the Department of Defense under Contract No.
DAHC 15-70-C-0120 at the Network Analysis Corporation,
Contract Nos. DAHC 15-69-C-0179 and DAHC-71-C-0088 at
Bolt Beranek and Newman Inc., and Contract No. DAHC
15-69-C-0285 at the University of California at Los Angeles.
discussions and debates. Rather than present merely a
summary of the procedures that were used in the
network design, we trove attempted to evaluate each
other's methods to determine their advantages and
drawbacks. Our approaches and philosophies trove often
differed radically and, as a result, this has not been an
easy or undisturbing process. On the other hand, we
have found our collaboration to be extremely rewarding
and, notably, we have arrived at many similar con-
clusions about the network's behavior that seem to be
generally applicable to message switched networks.
The essence of a network is its design philosophy, its
performance characteristics, and its cost of implementa-
tion and operation. Unfortunately, there is no generally
accepted definition of an "optimal" network or even of
a "good" network. For example, a network designed to
transmit large amounts of data only during late evening
hours might call for structural and performance char-
acteristics far different from one servicing large numbers
of users who are rapidly exchanging short messages
during business hours. We expect this topic, and others
such a the merits of message switching rs. circuit
switching or distributed rs. centralized control to be a
subject of discussion for many years.
, cost analysis performed in 1967-1968 for the ARPA
Network indicated that the use of message switching
would lead to more economical communications and
better overall availability and utilization of resources
than other methods. '6. In addition to its impact on
the availability of computer resources, this decision has
generated widespread interest in store-and-forward
communications. In many instances, the use of store-
and-forward communication techniques can result in
255
-----------------------------------------------------------
256 Spring Joint Computer Conference, 1972
greater flexibility, higher reliability, significant tech-
nical advantage, and substantial economic savings over
the use of conventional common carrier offerings. An
obvious trend toward increased computer and com-
munication interaction has begun. In addition to the
ARPANET, research in several laboratories is under
way, small experimental networks are being built, and
a few examples of other government and commercial
networks are already apparent.
In the ARPANET, each time-sharing or batch
processing computer, called a Host, is connected to a
small computer called an Interface Message Processor
(IMP). The IMPs, which are interconnected by leased
50 kilobit/second circuits, 'handle all network eom~
munieation for their Hosts. To send a message to
another Host, a Host precedes the text of its message
with an address and simply delivers it to its IMP. The
IMPs then determine the route, provide error control,
and notify the sender of its receipt. The collection of
Hosts, IMPs, and circuits forms the message switched
resource sharing network. A good description of the
ARPANET, and some early results on protocol develop-
ment and modeling are given in References 3, 12, 15,
23 and 38. Some experimental utilization of the
ARPANET is described in Reference 42. A more recent
evaluation of such networks and a forward look is
given in References 35 and 39.
The development of the Network involved four
principal activities:
(1) The design of the IMPs to act as nodal store-
and-forward switches,
(2) The topological design to specify the capacity
and location of each communication circuit
within the network,
(3) The design of higher level protocols for the use
of the network by time-sharing, batch pro-
ceasing and other data processing systems, and
(4) System modeling and measurement of network
performance.
Each of the first three activities were essentially per-
formed independently of each other, vhereas the
modeling effort partly affected the IMP design effort,
and closely interacted .with the topological design
project.
The IMPs were designed by Bolt Beranek and
Newman Inc. (BBN) and were built to operate in-
dependent of the exact network connectivity; the
topological structure was specified by Network Analysis
Corporation (NAC) using models of network per-
formance developed by NAC and by the University of
California at Los Angeles (UCLA). The major efforts
in the area of system modeling were performed at
UCLA using theoretical and simulation techniques.
Network performance measurements have bccn con-
ducted during the development of the network by
BBN and by the Network Measurement Center at
UCLA. To facilitate effective use of the net, higher
level (user) protocols are under development by a
group of representatives of universities and rcscareh
centers. This group, known as the Network Working
Group, has already specified a Host to Host protocol
and a Telnet protocol, and is in the process of com-
pleting other function oriented protocols. . We make
no attempt to elaborate on the Host to Host protocol
design problems in this paper.
THE NETWORK DESIGN PROBLEM
A variety of performance requirements and system
constraints were considered in the design of the net.
Unfortunately, many of the key design objectives had
to be specified long before the actual user requirements
could be known. Once the decision to employ message
switching was made, and fifty kilobit/second circuits
were chosen, the critical design variables were the
network operating procedure and the network topology;
the desired values of throughput, delay, reliability and
cost were system performance and constraint variables.
0thcr constraints affected the structure of the network,
but not its overall properties, such as those arising from
decisions about the length of time a message could
remain within the network, the location of IMPs
relative to location of Hosts, and the number of Hosts to
be handled by a single IMP.
In this section, we identify the central issues related
to IMP design, topological design, and network
modeling. In the remainder of the paper, we describe
the major design techniques which have evolved.
IMP properties
The key issue in the design of the IMPs was the
definition of a relationship between the IMP subnet
and the Hosts to partition responsibilities so that
reliable and efficient operation would be achieved. The
decision was made to build an autonomous subnet,
inde. pendent (as much as possible) of the operation of
any Host. The subnet was designed to function as a
"communications system"; issues concerning the use of
the subnet by the Hosts (such as protocol development)
were initially left to the Hosts. For reliability, the
IMPs were designed to be robust against all line failures
and the vast majority of IMP and Host failures. This
decision required routing strategies that dynamically
adapt to changes in the states of IMPs and circuits,
-----------------------------------------------------------
Computer Communication Network Design 257
and an elaborate flow control strategy to protect the
subnet against Host malfunction and congestion due to
IMP buffer limitations. In addition, a statistics and
status reporting mechanism was needed to monitor the
behavior of the network.
The number of circuits that an IMP must handle is a
design constraint directly affecting both the structure
of the IMP and the topological design. The speed of the
IMP and the required storage for program and buffers
depend directly upon the total required processing
capacity, which must be high enough to switch traffic
from one line to another when all are fully occupied. Of
great importance is the property that all IMPs operate
with identical programs. This technique greatly
simplifies the problem of network planning and main-
tenance and makes network modifications easy to
perform.
The detailed physical structure of the IMP is not
discussed in this paper. 2. However, the operating
procedure, which guides packets through the net, is
very much of interest here. The flow control, routing,
and error control techniques are integral parts of the
operating procedure and can be studied apart from the
hardware by which they are implemented. Most
hardware modifications require changes to many
IMPs already installed in the field, while a change in
the operating procedure can often be made more
conveniently by a change to the single operating
program common to all IMPs, which can then be
propagated from a single location via the net.
Topological properties
The topological design resulted in the specification of
the location and capacity of all circuits in the network.
Projected Host--Host traffic estimates were known at
the start to be either unreliable or wrong. Therefore,
the network was designed under the assumption of
equal traffic between all pairs of nodes. (Additional
superimposed traffic was sometimes included for those
nodes with'expectation of higher traffic requirements.)
The topological structure was determined with the aid
of specially developed heuristic programs to achieve a
low cost, reliable network with a high throughput and
a general insensitivity to the exact traffic distribution.
Currently, only 50 kilobit/second circuits are being
used in the ARPANET. This speed line was chosen to
allow rapid transmission of short messages for inter-
active processing (e.g., less than 0.2 seconds average
packet delay) as well as to achieve high throughput
(e.g., at least 50 kilobits/second) for transmission of
long messages. For reliability, the network was con~
strained to have at least two independent paths between
each pair of IMPs.
The topological design problem requires consideration
of the following two questions:
(1) Starting with a given state of the network
topology, what circuit modifications are required
to add or delete a set of IMPs?
(2) Starting with a given state of network topology,
when and where should circuits be added or
deleted to account for long term changes in
network traffic?
If the locations of all network nodes are known in
advance, it is clearly most efficient to design the
topological structure as a single global effort. However,
in the ARPANET, as in most actual networks, the
initial designation of node locations is modified on
numerous occasions. On each such occasion, the
topology can be completely reoptimized to determine a
new set of circuit locations.
In practice, there is a long lead time between the
ordering and the delivery of a circuit, and major topo-
logical modifications cannot be made without sub-
stantial difficulty. It is therefore prudent to add or
delete nodes with as little disturbance as possible to
the basic network structure consistent with overall
economical operation. Figure i shows the evolution of
the ARPANET from the basic four IMP design in 1969
to the presently planned 27 IMP version. Inspection of
the 24 and 27 IMP network designs reveals a few
substantial changes in topology that take adwntage of
the new nodes being added. Surprisingly enough, a
complete "reoptimization" of the 27 IMP topology
yields a network only slightly less expensive (about
I percent) than the present network design?
Network modets
The development of an accurate mathematical model
for the evaluation of time delay in computer networks is
among the more difficult of the topics discussed in this
paper. On the one hand, the model must properly
reflect the relevant features of the network structure
and operation, including practical constraints. On the
other hand, the model must result in a mathematical
formulation which is tractable and from which mean-
ingful results can be extracted. However, the two
requirements are often incompatible and we search for
an acceptable compromise between these two extremes.
The major modeling effort thus far has been the study
of the behavior of networks of queues? This emphasis
is logical since in message switched systems, messages
experience queueing delays as they pass from node to
node and thus a significant performance measure is the
-----------------------------------------------------------
258
Spring Joint Computer Conference, 1972
SRI UTAH
¸
UCLA
4-iMP NETWORK- 12/I/69
(a) '
SRI UTAH MIT LINC SRI UTAH ILL MIT
UCSBi
UCLA RAND BBN HARV UCLA RAND BBN
'10-NODE NETWORK- 7/i/70
(b)
LINC
¸
CASI
ß
CARN
¸
HARV BURROUGHS
15-IMP NETWORK- 5/i/71
McCLELLAN
SRI UTAHC
X yusc
u:) STAN S DC O IMIT O
UCLA
CASE
CARN
tMITRE
ETAC
RAND TINKER BBN HARV NBS
24-IMP NETWORK - 4/i/72
(d)
SRI LRL UTAH ILL MIT
LINC
UCSB'
RAOC
UCLA SDC USC BOULDER GWC CASE
27-iMP NETWORK- PLANNED
(e)
Figure 1--The evolution of the AttPANET
speed at which messages can be delivered. The queueing
models were developed at a time when there were no
operational networks available for experimentation and
model validation, and simulation was the only tool
capable of testing their validity. The models, which at
all times were recognized to be idealized statements
about the real network, were nonetheless crucial to the
A_RPANET topological design effort since they afforded
the only known way to quantitatively predict the
properties of different routing schemes and topological
structures. The models have been subsequently demon-
strated to be very accurate predictors of network
throughput and indispensable in providing analytical
insight into the network's behavior.
The key to the successful development of tractable
models has been to factor the problem into a set of
simpler queueing problems. There are also heuristic
design procedures that one can use in this case. These
procedures seem to work quite well and are described
later in the paper. However, if one specializes the
problem and removes some of the real constraints,
theory and analysis become useful to provide under-
standing, intuition and design guidelines for the original
constrained problem. This approach uncovers global
properties of network behavior, which provide keys to
good heuristic design procedures and ideal pcrformance
bounds.
DESIGN TECHNIQUES
In this section we describe the approaches taken to
the design problems introduced in the previous section.
We first summarize the important properties of the
ARPANET design:
(1) A communications cost of less than 30 cents per,
thousand packets (approximately a megabit).
(2) Average packet delays under 0.2 seconds through
the net.
(3) Capacity for expansion to 64 IMPs without
major hardwarc or software redesign.
(4) Average total throughput capability of 10-15
kilobits/second for all Hosts at an IMP.
(5) Peak throughput capability of 85 kilobits/second
' per pair of IMPs in an otherwise unloaded
network.
(6) Transparent communications with maximum
message size of approximately 8000 bits and
error rates of one bit in 10 2 or less.
-----------------------------------------------------------
Computer Communication Network Design 259
(7) Approximately 98 percent availability of any
IMP and close to 100 percent availability of all
operating IMPs from any operable IMP.
The relationships between the various design efforts
ß are illustrated by these properties. The, topological
design provides for both a desired average throughput
and for two or more paths to be fully used for com-
munication between any pair of Hosts. The operating
procedure should allow any pair of Hosts to achieve
those objectives. The availability of IMPs t( com-
municate reflects both the fact that IMPs are down
about 2 percent of the time and that the topology is
selected so that circuit failures contribute little addi-
tional to the total system downtime.
IMP design
The IMP design consists of two closely coupled but
nonetheless separable pieces--the physical hardware
specification (based on timing and reliability considera-
tions and the operating procedure) and the design and
implementation of the operating procedure using the
specified IMP hardware. The IMP originally developed
for the ARPANET contains a 16-bit one microsecond
computer that can handle a total of about megabits/
second of "useful" information on a total of approxi-
mately one megabit/second of circuit capacity (e.g.,
twenty 50 kilobit/second circuits). Hardware is likely
to change as a function of the required IMP capacity
but an operating procedure that operates well at one
IMP capacity is likely to be transferable to machines
that provide different capacity. However, as a network
grows in size and utilization, a more comprehensive
operating procedure that takes account of known
structural properties, such as a hierarchical topology,
is appropriate.
Four primary areas of IMP design, namely message
handling and buffering, error control, flow control, and
routing are discussed in this section. The IMP provides
buffering to handle messages for its Host and packets
for other IMPs. Error control is required to provide
reliable communication of Host messages in the
presence of noisy communication circuits. The design
of the operating procedure should allow high through-
put in the net under heavy traffic loads. Two potential
obstacles to achieving this objective are: (1) The net
can become congested and cause the throughput to
decrease with increasing looA, and (2) The muting
procedure may be unable to hvays adapt sufficiently
fast to the rapid movement of packets to insure efficient
routing. A flow control and routing procedure is
needed that can efficiently meet this requirement.
Message handling and buffering
In the ARPANET, the maximum message size was
constrained to be approximately 8000 bits. A pair of
Hosts will typically communicate over the net via a
sequence of transmitted messages. To obtain delays of
a few tenths of a second for such messages and to lower
the required IMP buffer storage, the IMP program
partitions each message into one or more packets each
containing at most approximately 1000 bits. Each
packet of a message is transmitted independently to
the destination where the message is reassembled by
the IMP before shipment to that destination Host.
Alternately, the Hosts could assume the responsibility
for reassembling messages. For an asynchronous IMP-
Host channel, this marginally simplifies the IMP
