1320 VOL. 66, NO. 11, NOVEMBER
Prin es clnd r,r Lessons'
in: "lmunications
LEONARD KLEINROCK, FELLOW, tEEE
2K: PR
Invited Paper
Abstract-After hearty a decade of experience, we reflect on the
principles and lessons which have emerged in the field of packet com-
munications. We begin by identifying the need for efficient resource
sharing and review the original and recurring difficulties we had in
achieving this goal in packet networks. We then discus various lessons
learned in the areas of: deadlocks; degradations; distributed control;
broadcast channels; and hierarchical design. The principles which we
discu, have to do with: the efficiency of large system; the switching
computer; network constraints; distributed control; flow control; stale'
protocols; and designers not yet experien:ed in packet communications.
Throughout the paper, we identify various open issues which remain to
be solved in packet communications.
I. INTRODUCTION
HAT IS IT WE now know about packet communica-
tions that we did not know a decade ago? What made
the problem difficult, and why were the solutions not
immediately apparent to us in the late 1960's7 Whereas the
answers to these questions may entice the system designer (in-
deed, I, for one, delight in such investigations), why should
the network user care a whit? To most users (and, alas, to
many designers), communications is simply a nuisance and they
would just as soon ignore those problems and get on with the
"real" issues of information processing!
In this paper (and in conjunction with the other papers in
this Special Issue of the PROCEEDINGS), we hope to answer
some of these questions. We will identify the need for resource
sharing, explain why the problem of efficient resource sharing
is hard, and why it must be understood, review some of the
lessons we learned (mostly from the three ARPA packet net-
works), and then, finally, state some principles which have
evolved from the study and extensive use of packet communica-
tions.
II. RESOURCE SHARING
A privately owned automobile is usually a waste of money!
Perhaps 90 percent of the tinitig9.tly parked and'not in use.
However, its "convenience" 'i$6 'euctive that few can resist
the temptation to own one. WheWthe price of such a poorly
utilized device is astronomically high, we do refuse the temp-
tation (how many of us own private jet aircraft?). On the
other hand, when the cost is extremely low, we are obliged to
own such resources (we all own idle pencils).
An information processing system consists of many poorly
utilized resources. (A resource is simply a device which can
perform work for us at a finite rate.) For example, in an in-
formation processing system, there is the CPU, the main mem-
ory, the disk, the data channels, the terminals, the printer, etc.
Manuscript received March 24, 1998; revised June 16, 19'/8. This
research was supported by the Advanced Research Projects Agency of
the Department of Defense under Contract MDA 903-77-C-0272.
The author is with the Computer Science Department, University
of California, Los Angeles, CA 90024.
was very high) but who collectively presented a total
profile which was relatively smooth a.nd of medium to
utilization..This was an example of the advantages Io
gained through the smoothing effect of a large popuh,:4
(i.e., the "law of large numbers") [ 1 ]. The need for
sharing is present in many many systems (e.g., the shatca
of public jet aircraft among a large population of users).
In computer communication systems we have a great
for sharing expensive resources among a collection of n
peak-to-average (i.e., "bursty") users [ 1 ]. In Fig. l we
the structure of a computer network in which we can dt.-'r.
three kinds of resources:
1) the terminals directly available to the user and the ..
munications resources required to connect those termina:
their HOST computers or directly into the network (via
in the ARPANET, for example-this is an expensive pomo
the system and it is generally difficult to employ
resource sharing here due to the relative sparseness of the
sources;
2) the HOST machines themselves which provide the
formation processing services-here multiaccess time
pro'fides the mechanism for efficient resource sharing:
3) the communications subnetwork, consisting of
munication trunks and software switches, whose function
to provide the data communication service for the exchat
data and control among the other devices.
The HOST machines in 2) above contain hardware and
ware resources (in the form of application programs and
files) whose sharing comes under the topic of time shannt.
dwell no further on thesw resources. Rather, we shall
attention on those porfibns of the computer communicat''
system where packet communications has had an imp
impact. Perhaps the most visible component is that of the
munications subnetwork listed in item 3) above. Herc l
communications first demonstrated its enormous efficienc:ø'
the form of the ARPANET in the early 1970's (the deca-
computer networks). The communication resources Io
shared in this case are storage capacity at the nodal
(these switches are called IMP's in the ARPANET),
capacity in the nodal switches, and communications capact:'
the trunks connecting these switches. Packet switching
env/ronment has proven to be a major technological I
through in providing cost effective data communications a
packet-switched networks there is a need for 1ong-h
capacity inexpensive communications, and it is here
One of the major system advances of the early 1960's
development oœ multiaccess time-sharing systems
computer system resources were made available to
population of users, each of whom had relatively small
(i.e., the ratio of their peak demands to their average
0018-9219/78/1100-1320500.75 ¸ 1978 IEEE
iecond
sharing
n this PR
RPANE'
pro
the use
ß mications reso
tiaccess bn
,.'. known a.
has spons
i,y be fou
l,at running
[.thing ef
.':sharing,
..communi
g describ
!'let us nc
I -.1',' us to evai
I.___e way. In
.e system
provk
networks
commr
)recise
the
the user
as he
regar
seldc
state
Credit
the last
lnd well
tl
the infi
III.
1967,'
we f
-----------------------------------------------------------
1322
'We quickly found that many of our old techniques could not
be directly applied to packet network design and that new
'techniques had to be developed.; these new techniques turned
out 'o be of great generality and have led to principles and to
understanding which are sure to benefit us for many years to
come. One of our first tasks was to develop tools which would
allow us to analyze the performance of a given network. This
involved evaluating the delay-throughput profile for networks.
Basically, this is a queueing problem in a network environment.
It had earlier been recognized [8] that the probabilistic com-
plexities one encounters in computer networks are extremely
difficult. One of the simplest analytical questions involving
the solution of two nodes in tandem was first posed at that
time in 1964 and has only been satisfactorily answered (in the
queueing theoretic sense) within the past year [9] ;this, note,
is for the simplest problem. Indeed we have come to realize
that an exact solution for the delay-throughput .profile is prob-
ably hopeless in a complex network environment. Fortunately
suitable approximations [ 1 ], [8] have been developed wkich
permit one to predict the performance of given networks with
a high degree of accuracy. More than that, these approximate
tools allow us to expose and understand the phenomenological
behavior of networks.
The astute reader will observe that the resource sharing prob-
lem stated above sounds very much like the problem faced in
the design of time sharing systems. Surely, with time sharing,
we are faced with the problem of sharing resources among
asynchronous processes which behave in a bursty fashion. The
major difference between the two problems, however, is that
our problem exists in a geographically distributed environment
which requires expensive communication resources in the com-
munications and coordination functions. The implications
here are strong. For example, when communication is cheap,
then wide-band communications can be obtained with ex-
tremely small delays; such is the case, for example, within the
resources of a local operating system connected together by a
data bus. In a regional or nationwide network subject to the
relatively expensive cost of telecommunications, we find that
typical bandwidths are many orders of magnitude less than that
in a local time-sharing environment, and the delays are many
orders of magnitude greater. Furthermore, the control of these
processes in the time sharing environment can be very tightly
coupled if desired or left loosely coupled if there is sufficient
reason; in the network environment we typically find our pro-
cesses are very loosely coupled c[u_e-o the difficulty of tighten-
ing the control between them-:(in'di,. the inherent delay due
to the finite speed of light is'Luntamental limitation on the
tight coupling of remote processes). The overhead in the time
sharing system is variable and may be very high with poor system
design (for example, thrashing) but may be made small with
clever design. In the network environment, for a variety of
reasons, we find that the overhead due to packet headers,
control information and resource allocation tends to be
relatively high. These comparisons are summarized in Table I.
Not only do we have extremes in communications cost
between these two systems, we also have a significant difference
in the reliability of that communications. Indeed, in the local
time shared system, the process-to-process communication is
usually assumed to be reliable and therefore the acknowledg-
ment procedure (if any exists)is simple and tends to be invoked
only under exceptional circumstances. On the other hand, in
the distributert computer network environment, communica-
tions reliability is not assumed, and, therefore, an elaborate
PROCEEDINGS OF THE IEEE, VOL. 66, NO. 11, NOVEMBER
TABLE 1
ASYNCHRONOUS PROCESS-TO-PRocEsS COMMUNICATION AND
COST COMPARISON BETWEEN LOCAL PROCESSES IN A TIMF-
SYSTEM AND DISTRIBUTED PROCESSES IN A NITWoRK
Multiacess Geographicalh
Time-Shared Distribulcd '
Systems Computer Nctm
Typical bandwidth megabyies/sec kilobits/see
Typical coremunica- fractions of a micro- tens to hundreds .,.
tinns delay second milliseconds
ProcesS-process
coupling tight to loose typically
Overhead due to variable (typically variable (lypic
system control low) high)
acknowledgment procedure (often including timeouts and
defaults) is usually invoked. We are here reminded ol n,
"two-army" problem. This is the problem where two
armies are each poised on opposite hills preparing to
single red army in the valley. The red army can conquer
of the blue armies separately but will fall to defeat if bmh ..,
armies attack simultaneously. The blue armies comlnum½.,
with each other over an unreliable communications
The problem is to coordinate the two blue armies so that
will attack simultaneously. Let us assume that Blue Arm,
(BI) sends a message to Blue Army 2 (B2) indicating that I...
should jointly attack at noon the next day. Clearly BI
await a positive acknowledgment from B2 that the coinings.:
was properly received; were BI to attack without
acknowledgment, then the possibility exists that B2 did
receive the message correctly, in which case B1 is subjc,::
the certain annihilation of his army. If B2 properly
the command and acknowledges it, then he m:.is awI
acknowledgment of the acknowledgment from B1, for :t !
did not receive his acknowledgment then we know B 1 wdl
attack and B2's attack will then be doomed to failure. I
argument continues in a circular fashion where acks of .'
of acks . . . are continually transmitted with no action
being taken; the two blue armies can never get perfee:
synchronized with certainty'using this unreliable corn
tinns systemß
We see therefore that the new culprit in resource sharing :
distributed environment is the fact that the resourcc
distributed and cannot easily be assigned to the demands t:
deed,. in previous resource. allocation problems, wlUch
come under the :nS'me of scheduling algorithms, we made: ?a
assumption, namely, that the scheduling information coulZ
passed around for flee. That is, the competing demands
organize themselves into a cooperating queue at no price. t
fortunately, in the distributed environment, the cost of org
ing demands into a cooperating queue may be very large.
in one fashion or another nature will make you pay a price [ I½'
The problem of resource sharing in a distributed enb-ronrzr
manifests itself in the routing control and flow control
lems. The problem of flow control is to regulate the rate
which data crosses the boundary of the communications r'..
network (both into and out of the network)ß The pro.!l.7,
routing control is to efficiently transport the data
been admitted by the flow control procedure) acroSS the "
work to its destination In 1967 we were aware of the
ticarSon needed in the routing procedure, but were re!
ignorant of the need for effective flow control (see
These two problems are difficult because we are dealing
i. proced
delays
to cont
iS t{
IMP P
In ack
rOB'
[twork, xn
traffic
pr
come tc
Belov
alloc t
some r
distribt
topolo
'set of c
fin;
feats
be' solv
desi
the p.
exceed t
small
"uld exas
[l__til;nay ef
given p
. .the co
]IlLIIbblems
'boptim al s
I _._.u. re whic
I .J' the best
I I½or may rio
h
rap.
deve
t
what is
flow t
thxou
of an
depem
th
in th
capaci
.we do -
for fu
-----------------------------------------------------------
)V œiNF, oCK: PRINCIPLES AND LESSONS IN PACKET COMMUNICATIONS 1323
tbl, ( ..... ' have
n tr01 procedure in a distributed environment subject to
t'ms-gi t0rn delays in passing that control information around
'wotri rder to control the random demands. The purpose of both
cedures is to efficiently use the network resources (IMP
IMP processing capacity, and communications ca-
pute itY). In achieving this goal one must attempt to control
:stion, route data around busy or defective portions of
)its/.sc .etwork, and in general must adaptively assign capacity to
'.data traffic flow in an efficient, dynamic way.. These are
:3 control problems and represent a class which has not
adequately studied up to and including the present time.
: come to learn that distributed control is a sophisticated
,,h) :t, lern. Below we return to the issues involved in distributed
,,urce allocation and sharing. For the moment let us in-
:outs and o
here
ag
conquetl]!
at if bo
, comm
atiom
so
th
thout
1 Mmb
BI,
ow al
no a
get; .
le co
we
ost of
very
:d
,ate
ata
acro,
)1 (sot
.:3uce some of the other sources of complexity in packet
::munications.
In any distributed communications system design one is faced
c: a topological design problem. The problem basically is,
;.,:n.a set of constraints to meet, find that topological design
:-xture which meets these constraints at least cost. The field
ß network flow theory addresses itself to such problems and
:: ,silent feature of this theory is that most of its problems
cn0t be' solved! To exhaustively search over all possible
¾-01ogical designs for a given problem is certainly not a solu-
:,:.n since the number of possible alternatives to consider can
-ady exceed the numbe of atoms in the universe even for
:.:tively small problems. (For example, if at some stage you
:., consider all permutations of 20 objects, then a computer
,.uld take more than 75 000 years to process all 20! cases even
ß :l could examine one million cases per second.) Rather, a
,.,tion consists of elegant search procedures which are com-
-.mienally efficient and which find the optimal topology
:Ihe given problem. Very few problems in network flow
?.,:0ry yield to such efficient algorithms. Rather, one gets
: and the combinatorial complexity naturally inherent in
.:w problems by accepting suboptimal solutions. (Beware!
t roboptimal solution to a problim is simply the result of a
..'xedure which examines a subset of possible solutions and
,s the best of those examined-this suboptimal solution
:.;' or may not be close to the optimal.) The trick here is to
!:3 efficient heuristic search procedures which come close to
optimal rapidly. Over the past decade, efficient procedures
a,e been developed in many cases and new procedures are
-:4tantly being investigated for the topological design problem.
nothr 0urce o.f diffi.cult¾ in the resource 5hating problem
:n defining the appropriate performance measure. For ex-
topic, what is the capacitY-Of a network? It is well-known in
.''ork flow theory tha[-oxti}:n easily calculate the capacity
ß :, the throughput) bet',ve-any two pairs of points. What
ß ,not straightforward is' to evaluate the total data-carrying
aPcity of a network where throughput is measured in terms
messages successfully received at their destination. The dif-
k~lty comes about because the capacity of the network
tnglY depends upon the traffic matrix one assumes for the
flowing through that network. For example, if the traffic
rix were such that traffic passes only between immediate
t"qhbors in the topological structure and in an amount equal
. the capacity of the line connecting those two, then the net-
capacity would approach a value equal to the sum ufall
capacities in the network. This is clearly an upper
to the capacity for any other traffic matrix. Since in
we do not know the traffic matrix for a network to be
for future use, how is one to evaluate that capacity?
Yet another source of difficulty in the network problem is
that of interfacing terminals and HOSTS to networks as well as
one network to another network. For example, there is the
general issue of virtual circuit service as opposed to datagram
service. A virtual circuit service presents to the user a com-
munications environment in which all functions appear as if
she were directly connected between the two points com-
municating (i.e., an orderly and controlled flow is maintained
whereby data is guaranteed to be correct upon delivery to the
destination, comes out of the network in the same order in
which it came in, and a flow control may be applied to that
transmission to maintain efficient use of network resources
and of terminal-HOST resources). A datagram service ensures
none of these things and simply sends blocks of data (packets)
across the network, not guaranteeing correct delivery (or
delivery at all), not guaranteeing orderly flow in terms of se-
quencing (packets may arrive at the destination out of order),
and not enforcing any flow control procedure at the process-
to-process level. Which of those two services is desirable has
become an issue of international proportions discussed else-
where in these proceedings [7], [111. Futhermore, theinter-
connection of two networks presents an enormous and rich
variety of difficult problems. For example, should one apply
flow control at the boundary of each network in a tandem
chain of networks or should one apply flow confrol from the
source HOST to the destination HOST across many networks
simultaneously? If we consider the interconnection of networks
with different packet sizes, we have the general problem of
fragmentation whereby long packets get fragmented into smaller
packets when crossing network boundaries. A variety of other
very important issues arise in internetting (see [271 for a more
detailed discussion of internetting).
Many of the problems we have just presented come about
due to the distributed nature of our message sources and system
resources. The problems created by distributed sources are
very clearly seen in the environment of geographically dispersed
message sources which communicate with each other over a
common broadcast channel; in this case, access to the capacity
of the channel must be carefully coordinated.
Thus in answering the question, "Why is the problem hard?"
we have found the following sources of difficulty:
1) the analytic problems from queueing theory and the
probabilistic complexity resulting therefrom;
2) the topological design problems from network flow theory
and the combinatorial complexity. resulting therefrom;
) the pri' for coordinating and sharing resources in a
gee _graphically distributed environment (the new culprit)
leading-to-problems of res6urc allocation, routing con-
trol, flbw. control',. and general process-to-process com-
munication problems.
IV. LESSONS LE^aNEn
After a decade of experience with packet communications it
is fair that we ask what lessons have we learned and what have
we come to know about the needs of the user and the questions
he would like to have answered. So far as the user is concerned
we shall see as we step through the lessons learned below that
he cannot insulate himself completely from the underlying
technology of packet communications. Indeed the service he
ß sees is quite different from that which he has with leased lines
as mentioned above. Moreover, certain decisions will either be
thrust upon him or accepted by him due to the nature of the
service offered; if he is unaware of the consequence of setting
-----------------------------------------------------------
1324
parameters in that decision-making process then he may
seriously degrade the performance of the network due to his
ignorance. Let us now list some of the lessons we learned and
return to the principles in the following section.
A. Deadlocks
In [1], [12], and [131 we described in detail some of the
deadlocks and degradations of which we have become aware.
In this section we simply enumerate and sketch the details of
the deadlocks. Simply stated, a deadlock (also commonly
referred to as a lockup) is the unpleasant situation in which
two (or more) competing demands have each been assigned a
subset of their necessary resources; neither can proceed until
one of them collects some additional resources which currently
are assigned to the. 6fher and' neither demand is willing to
release any resource currently assigned' to him. Deadlocks are
one of the most serious system malfunctions possible, and one
must take great care to avoid them or find ways to recover from
them. It is ironic that flow control procedures by their very
nature present constraints on the flow of data (e,g., the re-
quiremerit for proper sequencing), and if the situation ever
arises whereby the constraint cannot be met, then, by defini-
tion, the flow will stop, and we will have a deadlock! This is
the philosophical reason why flow control procedures have a
natural tendency to introduce deadlocks. In this section we
briefly discuss four ARPANET deadlocks which have come
to be known as: reassembly lockup; store-and-forward dead-
lock; Christmas lockup; and piggyback fockup.
Reassembly lockup, the best known of the ARPANET dead-
lock conditions (and one which was known to exist in the very
early days of the ARPANET implementation), was due to a
logical flaw in the original flow-control procedure. In the
ARPANET, a stritig of bits to be passed through the network
is broken into "messages" which are at most approximately
8000 bits in length. These messages are themselves broken
into packets which are at most approximately 1000 bits in
length. A message requir{ng more than one packet (up to a
maximum of eight) is termed a multipacket message and each
of these packets traverses the network independently; upon
receipt at the destination node, these packets are "reassembled"
into their original order and the message itself is recomposed,
at which time it is ready for delivery out of the network. (A
more complete description of .tizeARPANET protocols may
be found in [I], [13].) Reasrrty lockup occurred when
partially reassembled message could not be completely reas-
sembled since the network through which the remaining packets
had to traverse was congested, thus preventing these packets
from reaching the destination; that is, each of the destination's
neighbors had given all of their relay (store-and-forward) buf-
fers to additional packets (from messages other than those
being reassembled) heading for that same destination and for
which there were no unassigned reassembly buffers available.
Thus the destination was surrounded by a barrier of blocked
IMP's which themselves could. provide no store-and-forward
buffers for the needed outstanding packets, and which at the
same time were prevented from releasing any of their store-
and-forward buffers since the destination itself refused to ac-
cept these packets due to a lack of reassembly buffers at the
destination. The deadlock was simply that the remaining
packets could not reach the destination and complete the
reassembly until some store-and-forward buffers became free,
PROCEEDINGS OF THE IEEE, VOL. 66, NO. I l, NOVEMBER
and the store-and-forward buffers could not be released unttl
remaining packets reached the destination.
Store-and-forward deadlock is another example of a
that can occur in a packet-switched network if no
precautions are taken Ill, 1131. The case of "direct"
and-forward lockup is simply a "stand-off." Let us
that all store-and-forward buffers in some IMPA are fillc0
packets headed toward some destination IMP C throug2.
neighboring IMP B and that all store-and-forward buffc:
IMP B are filled with packets headed toward some destinal:,.n
IMP D through IMP A. Since there is no store-aad-fma,.:
buffer space available in either IMP A or B, no act-----------------------------
OVEM[
pie of
k if no
'"dir
Let u
4 are
PC
ward bu!
o packet.7ej
P's and
pymg all' f '
by the 'p
he introd
ß ives at a
t ge t0ifi'"
ore the .
oop
none of [
the A "' ?
comm ,
ockup
ed by
assembly'
nbly
f
tck to
)f the
sured
the
s faras
s about d
;onable
ne
ver
3c
the
onable
tnsfer
:oCK: pRINCIPLES AND LESSONS IN PACKET COMMUNICATIONS
1325
the reservation. The ARPANET flow control proce-
then maintain that reservation for a given file transfer
. as successive multipacket messages from that file are
,tlY received in succession at the source IMP. We have
the groundwork for piggyback lockup. Assume that
s a maximum of eight reassembly buffers in each IMP;
oice of eight is for simplicity, but the argument works
;? value. Let IMP A continually transmit eight-packet
(from some long file) to some destination IMP B
all gight reassembly buffers in IMP B are used up by
:nsmission of multipacket messages. If now, in the stream
:t.packet messages, IMP A sends a single-packet message
-art of the file transfer) to destination IMP B it will gert-
, .0t be accepted since there [s no reassembly buffer space
k'. The single packet message will therefore be treated
:cquest for. buffer allocation (these requests are the
yahism by which reservations are made). This request will
x serviced before the RFNM (an end-to-end acknowledg-
:'tom the destination to source) for the previous multi-
:t message has been sent. When the RFNM is generated,
,cr, all the free reassembly buffers will immediately be
,:td to the next multipacket message in the file transfer
:.:ciet transmission as mentioned above; this ullocation
.' 10 be "piggybacked" on the RFNM. In this case, the
;cket message from IMP A that arrives later at IMP B
hich is stored in the eight buffers) cannot be delivered
destination HOST because it is out of order. The single-
l: message that should be delivered next, however, will
reach the destination IMP since there is no reassembly
,,: available, and, therefore, its requested reservation can
be serviced. Deadlock! A minor modification removes
,,yback lockup.
-, various deadlock conditions are usually quite easy to
,.--: once they are detected and understood. The trick,
I,,cr, is to expurgate all deadlocks from the control
.,mn ahead of time, either by careful programming
.".cult task) or by some automatic checking procedure
may be as difficult as proving the correctness of pro-
Those deadlocks found in the ARPANET have, to
l of our knowledge, been eliminated.
.'tradations
:cgradation is just that, namely, a reduction in the net-
of performance. (Deadlocks are, of course, an ex-
form of degradation whic..h is why we discussed them in
section fibore.) For our purpos. es, we shall measure'
in terms oœ del.a E and throughput. In this section
acuss four source'of .RPANET degradation, namely:
the routing p_f9fi_edu. re.; gaps in transmission; single-
turbulence; and phasing.
ß ,ting comes about due to independent routing decisions
bit separate nodes which cause traffic to return to a
node (or, in a more general definition, causes
make unnecessarily long excursions on the way to its
Of course any reasonable adaptive routing proce-
ß -11 detect these loops (through the build-up of queues
perhaps) and will then break the loop and guide
-ffic directly on to its destination. However, the occur-
of loops does cause occasional large delays in the traffic
ncl in some applications this is quite unacceptable. It is
that a remedy which was introduced in the ARPANET
the occurrence of loops, in fact made them worse in
the sense that whereas they occurred less frequently, when
they did occur, they persisted for a longer time. Some loop-free
algorithms have recently been published [ 15 ], [ 16 ].
The next degradation we wish to discuss is the occurrence
of gaps in the message flow. These gaps come about due to a
limitation on the number of messages in transit which the
network will allow. Assume that between any source and
destination, the network will permit n messages in flight at a
time. If n messages are in flight, then the next one may not
proceed until an end-to-end acknowledgment is returned back
at the source for any one of the n outstanding messages. We
now observe that if the round-trip delay (i.e., the time required
to send a message across the network in the forward direction
and to return its acknowledgment in the reverse direction) is
greater than the time it takes to feed the n messages into the
network, then the source will be blocked awaiting ack's to
release further messages. This clearly will introduce gaps in
the message flow resulting in a reduced throughput which we
might classify as a mild form of degradation.
We now come to the issue of single packet turbulence as
observed in the ARPANET. We note that "regular" single-
packet messages in the early ARPANET were not accepted by
the destination if they arrived out of order. Rather, they were
then treated as a request for the allocation of one reassembly
buffer. Therefore if, in a stream of single-packet messages,
packet p arrived out-of-order (say it arrived after packetp + 3),
then packets p + 1, p + 2, and p + 3 would all be discarded at
the destination, and only after packet p arrived would a single
packet buffer be allocated to message p + I. This allocation
piggybacked on the end-to-end ack for packet p, and when it
arrived at the source IMP, it then caused a retransmission of
the discarded packet p + I (which had been stored in the
source).. Of course any packets arrving at the destination after
packet /J + 3, but before p + 1 arrived in order, would them-
selves be discarded. When packet p + 1 finally arrived for the
second time at the destination IMP it was then in order and this
caused an allocation of a single-packet buffer to packet p + 2,
etc. The net result was that only one packet would be deliver-
able to the destination per round-trip time along this path;
had no packets been received out-of-order, then we would have
been pumping at a rate close to n packets per round trip time
(if the maximum number in transit n could fit into the pipe).
Observe that once a single packet arrived out-of-order in this
stream, then the degradation from n to 1 packets per round-
trip time wouId persist forever until either some supervisory
action was taken or until. the traffic stream. ceased and began
again from a fresh start in the future. We refer to this effect
as "singe-packet tufbutence," .:and it was observed in the
ARPANET.as described in [17]. The need to handle a con-
tinuous strektn" of traffic (e.g., packetized speech) was
recognized some time ago and resulted in the definition of
"irregular" packets known as type 3 packets (as contrasted
to "regular" type 0 packets); these packets are allowed to
be delivered out of order, receive no end-to-end acknowledg-
ment, and are generally handled in a much more relaxed
fastdon.
The last degradation we discuss is known as "phasing." In a
typical packet network, more than one resource is often re-
quixed before a message is allowed to flow across that net-
work. For example, some required resources may be: a message
number; storage space at the source; storage space at the
destination, etc. Tokens move around the network passing out
-----------------------------------------------------------
these resources in some distributed fashion. Phasing is the
phenomenon whereby enough free tokens are available in the
network to permit message flow, bt, the.proper mix of tokens
is not available simultaneously at the proper location in the
net. The delay in gathering these tokens represents a degrada-
tion[I],[18].
Fortunately, the degradations here described have been
remedied in the ARPANET and in later networks.
C. Lessons of Distributed Control
We have had "lessons" in two areas of distributed control.
The first has to do with flow control, and it is simply the
observation that flow control procedures are rather difficult
to invent and extremely difficult to analyze. The deadlocks
and degradations referred to the in previous subsections were
principally due to flow control failures (and occasionally rout-
in co'ntrol faiiuresj. 'To data there is no satisfactory theory or
procedure for designing efficient flow control procedures, much
less evaluating their performance, proving they contain no
deadlocks, and proving that they are correct. Attempts in this
direction are currently under way.
An important lesson we have learned with flow control is
that a packet communications system offers an opportunity
for passing data between two devices of (very) different speeds.
We can effectively connect a slow-speed teletype to an enor-
mously high-speed memory channel over a packet network and
apply flow control procedures which protect the two devices
from each other as well as protecting the net from both.
Specifically, we must not drown the teletype with a flood of
high-speed input, nor must we "nickel-and-dime" a high per-
formance HOST to death with incessant interrupts, nor must
we use the network as a storage medium for megabytes of data.
Flow control mechanisms provide the means to accomplish
this; the trick is to do it well.
The second area of distributed control in packet communica-
tions has to do with the routing control. The ARPANET, and
many of the networks which have since based their design on
the packet-switching technology which emerged from the
ARPANET experiment, employ an adaptive routing procedure
with distributed control. In such a procedure, routes for the
data traffic are not preassigned but rather are dynamically as-
signed when they are needed according to the current network
status. Control packets (called routing update packets) which
describe the state of the network to some degree are passed
back and forth between neighb?oHiag !MP's in somefashion and'
current queue lengths and-c6igs'i0n measures are added to
these updates by each IMP. THe..'RPANET employs a periodic
update routing procedure whose rate depends upon channel
utilization and line speed. The updates passing between IMP's
have no priority in competing for the processing capacity of
the CPU at the IMP's but do have priority in the queue discip-
line feeding the output modems between IMP's. An important
lesson learned is that giving low priority to the processing of
routing updates appears to be advantageous since the processing
load on the CPU is rather large and prevents the further dis-
patching of arriving packets to output queues [19]. Another
routing lesson we have learned is that frequent updates cause
background congestion in a network which may be intolerably
high even in the absence of other data traffic; the update proce-
dure and update rate must be carefully chosen. A number of
alternatives to periodic updates have been suggested [l] in-
eluding such things as aperiodic updating (send updates only
when status information has crossed certain thresholds and
then send it immediately); and purely local information for
PROCEEDINGS OF THE IEEE, VOL. 66, NO. 11, NOvE?4B[): i:' PRINClI:
within a !ledicated"
routing decisions based on queue lengths
and knowledge of the current topology. Furtherm m is that
.. re.-.lllpac./ty in
care is taken, there is a tendency for looping .o occur :=on Multip
distributed control algorithms; looping can be prcvcnttd ..'inthis cate
more sophisticated algorithms [ 15 ].
E eservatiøn
One of the lessons which is now beginning to emerge he has d.
the most important advantage of distributed control
routing is its ability to automaticall); sense confi.....* :øf impleto
changes in the network; these configuration changc ..-if,' ß .g(where om
IMP failure. This is important for two reasons: firsl am
re uirement for a centralized control evaluo;,-, m..
tables based on the current configuration would be a- ,".'a]l fall mth
mously complex task from an administrative point o' )tø nature
second because it. is specifically at times of conr..,.t,_ately,. at
changes when drastic ,network action must be taken an m_: price
then s the adaptive routing procedure really called -, [ofie must pa:
do serious work (it is not yet clear to what extent the .,e:, I.'. ønment'
algorithm should adapt to statistical fluctuations in trat;.'
Without diminishing the result of these lessons, it t,'"'u.. i'in that the
say that the most significant lesson learned regardin: .:. lilhere the thr,
is that it works at all. Perhaps one of the ?'eatcst ... d clay incr
of the ARPANET experiment was to show that a ,dt::,,, 'design an,
control adaptive routing algorithm would indeed conc:, which stat
routes which were sufficiently good. The difficult>' in 7' " I fOn we hax
this lies in the fact that we are dealing with a dynat:::. . two access s
tion in a distributed control environment with dcla>, - .,.fraction of t
feedback paths for control information flow. The c:.,:, .g that cap
proof that things do work has had an important m?.' ,_cheme) do{
network design; indeed, these distributed algorithr:.- im[-dceY
currently operating successfully in a number of packr: .$ e ß
works. cremes
certain
ystem ca
D.- Lessons from Broadcast Channels perle
As mentioned earlier, packet communications has t0u. [20I.
portant applications in the areas of satellite packet bt,,,2. fob
ing and in ground radio packet switching. In both few buffc
ments we have a situation in which a common to handl
channel is available to be shared by a multiplicily ,': '> due
Since these users demand access to the channel aI unr:: they
able times, we must introduce some access sc h½:"a W
coordinate their use of the channel in a way which channels
degradations and mutual interference. In many of the in a
described [ 10 ]- we. have .fou. nd. that "burst" c [22].
provides efficiencies over that of "rickle" trans mi:"= range
this we mean ihat when a data source' requires accc :: n
channel, it should be given access to the full capacit? c: is not t
broadcast channel and not be required to transmit at channelu
speed using only a fraction of the available band'd:-' tl
Section V-A on principles regarding "bigger is better"). cortespot
In examining the recent literature, we find that a nu ' ,we point
access schemes have been invented, analyzed. and
for a summary of many of these access schemes, see [ or
observe that these access schemes fall into one ch:
categories, each with its own cost. The first of
random access contention schemes whereby little
is exerted on the users in accessing the channel, and this:
in the occasional collision of more than one packet; hum'
destroys the use of the channel for that transmiøn' topo
schemes as pure ALOHA, slotted ALOHA, and (to E is t
lesser extent) Carrier Sense Multiple Access fall it,
category. At the opposite extreme, we have the stanC not
tion access methods which preassign capacity to in tt
-----------------------------------------------------------
-- ':i'il -,docK: ?RINCIPLES AND LESSONS tN PACKET COMMUNICATIONS
wit,_ "? .Jll' .. ,,dedicated" as opposed to multiaccess channels. Here
,-mi a
F .... % blem is that a bursty user will often not use his preas-
the , ,,-*, ru ....
:--- 7"', caoacity which case ,t is wasted. Such schemes as
"2Tø.,}jj[sion Multiple Access and Frequency Division Multiple
,; falln th,s ca tegory. B etween these two ext re mes are t he
g to e' ' [ Znfic reseaton systems whmh only assign capamty to a
_ -8 -n he has data to send. The loss here due to the
.es consol
sense
:cad of implementing the demand access. Such schemes
ion c '. ; (where one waits to be asked if he has data to send),
. result of z', resc:'.',tion schemes (where one asks for capacity when
:=OHS: '::eSs it), and Mini-Slotted Alternating Priority (where a
en .[n is passed among numbered users in a prearranged se-
ving each permission to transmit as he receives a
. would :1 all fall in this category. Each of these schemes pays
ttive Pot ' .rbute to nature as shown in Table II.
es of m'[ ::'0nunately, at this point in time we are unable to evaluate
: be taken =inimum price (i.e., a deadation to throuput and/or
y ca' one must pay for a ven disthbuted multiaccess broad-
tel;.'ave found that contention schemes are fundamentally
1 .... !-.'ble in that they have a tendency to drift into a congested
'5;i} ] . .here the throughput decreases significantly at te same
e eat=t l.: re delay increases. Fortunately, however, we have been
v that a [: 0 design and implement areaTinny effective control
.--cs wNch stabilize these contention schemes [20]. An-
Ndeed n.
tifficulty :' .::: lesson we have learned is that ceaain tempting ways of
th a d; two access schemes (e.g., tang a fraction of the traffic
with delayi h l
ow. The m,
,portant impel m
ed algoriflll
ber of pael I
tions has
.' packet br
In both
:oremort
fitiplicityd
annel at
access
,ay w'
any of
ß " com
:
u= a
transit ii
,le
is k
ed, and
mes,
ato on
:t
tel,
and (.
ess fall
Y
t fraction of the capacity assigned to one access scheme,
z; aing that capacity to handle that traffic using a second
_m $chev,e) does not give an improvement in the overall
:.::ghput-delay performance [10]. Furthermore we have
-: that certain capture effects exist in some of the con-
,':n schemes (e.g., a group of terminals may temporarily
:he system capacity and thereby "lock out" other groups
:xlended periods of time) and one must be wary of such
=:.mcna [20]'.
}: have also found that in a ground radio broadcast environ-
*-.:. a few buffers in each packet radio unit appear to be
Snent to handle the storage requirements [21/;this comes
a:,;: larg:b. due to the fact that our transceivers are half-
:;:,:x (i.e., hey can either transmit or receive, but not both,
oven time). We can show (see Section IV-E) that dedicated
'*:cast channels have an inherent advantage over dedicated
networks in a large (many-user) bursty store-and-forward
*':anment [22]. Moreover, we have investigated the optimal
i.miision.tange 'for .LOHA het/drks'and' have found that"
o< broadcast networks cam be made quite effective when
.'raffle is not bursty; :tiic-Zhis optimal range is chosen so
the channel utilization in the resulting local ALOHA system
:e and then those net;Xheed only more capacity
corresponding M/M/I network [ 22].
-rely we point out that perhaps one of the first applications
%adcast radio access schemes will be to implement these
on wire networks (for example, coaxial cables
":"r'optics channels) in a local environment;an example of
.ntation is the Ethernet [23].
!f:erarchical Design
.V (the trambet e(.nodes in a network) grows, the cost of
the topological design of such a network behaves like
E is typically in the range from 3 to 6. Thus we
'hal topological design quickly becomes unmanageable.
';:dly, we note that as N grows, the size of the routing table
IMp in the network grows linearly with N and this too
1327
TABLE II
TtE Cost oF DISTRIBUTED RESOURCES
Access C9ntrol Idle
Method Collisions Overhead Capacity
Random access contention Yes No No'
Dynamic reservation No Yes No
Fixed allocation No No Yes
places an unacceptable burden on the storage requirements
within an IMP. In addition, the transmission and processing
costs for updating such large tables is p17ohibitive. Third, even
were the design possible, the cost of the lines connecting this
huge number of nodes together grows very quickly unless
extreme care is taken in that design. In all three cases just
mentioned, one finds that the use of hierarchical structures
saves the day. In the design case, one may decompose the net-
work into clusters of nodes, superclusters of clusters, etc.,
designing each level cluster separately. This significantly reduces
the number of nodes involved in each subdesign, thereby
reducing the overall design cost significantly. For example, a
100-node net would have a cost on the order of 100'* = 10 s
(for E = 4), whereas a 2-level hierarchical design with 5 clusters
would cost on the order of 5(20)'* + 5(4) < l0 s, yielding an
improvement of three orders of magnitude! The same approach
may be used in routing, where names of distant clusters, rather
than names of distant nodes, are used in each routing table,
thereby reducing the table length down from N to a number as
small as e In N giving a significant reduction [ 24 ]. For example,
a 1000-node net would give a 50-fold reduction in the routing
table length when hierarchical routing is used.
In [22] we discuss the overall effect and gain to be had in
the use of hierarchically designed wire networks and broadcast
networks. For example, we can show that in a bursty dedicated
broadcast environment, the use of hierarchical network struc-
tures (even with fixed allocation schemes) yields a system cost
which is proportional to [log M], where M is the number
of users. Comparing this to the case of wire networks where
the cost is proportional to the V'-, we see the significant ad-
vantages that broadcast channels have over wire networks in
a bursty environment when hierarchical structures are allowed.
We can see this intuitively since we assume that the cost of a
broadcast channels is proportional only to capacity, but is
independent of distance;if we properly select the transrrdssion
rangd, then the broadcast capacity'can"be reused spa'ially (i.e.,
it can be used independently andsimultaneously in more than
one area):' 'Further, it can be shown that a 2-level hierarchy
using randorb access in the lower level and dedicated channels
in the upper level can be quite efficient in a broadcast environ-
ment; this is true since the lower level has gathered together
enough traffic so that it is no longer bursty when delivered to
the upper level (recall that dedicated channels do well with
nonbursty traffic)
V. PRINCIPLES ESTABLISHED
This section is really a continuation of the last since there is
a somewhat fuzzy boundary between lessons and principles.
Indeed, one might accept the pragmatic definition that a
principle is a lesson you had to learn twice.
A. Bigger is Better
The law of large numbers states that a large collection of
demands presents a total demand which is far more predictable
-----------------------------------------------------------
328
than are the individual demands. We are thus led to the con-
sideration of large shared resources (large in the sence that we in-
crease both the number of users-or the load presented by each
user-and the capacity of the resources). Furthermore it is
easy to show that the performance improves significantly as
we make our systems larger. In particular we can show that
a small system whose capacity is C operations per second and
whose throughput is J jobs per second (with each job requir-
ing an average of K operations per job) performs A times as
slowly (i.e., the response time is A times longer) as a system
whose capacity is A C and whose throughput is AJ. The lesson
here is very clear, namely that bigger systems perform far better
than smaller ones [25]. This is a statement about performance
and not one about cost. Indeed if one is talking about com-
munication channel capacity, then one usually also gains
through an economy of scale due to the tariff pricing structure
as presented.by the common carriers. All the more reason,
therefore, to concentrate more and more traffic on ever larger
channels to gain both cost and efficiency in performance; of
course one must be careful not to abuse any "resale" restric-
tions. Moreover, our lesson about burst communications tells
us that in sharing this large' channel dynamically, one should
provide the full capacity to a single user on demand, rather
than to preallocate fractions of the capacity on a permanent
basis (omitting consideration of such channel-sharing schemes
as spread-spectrum).
The "bigger is better" principle may not apply to the case
of stream traffic (defined as real-time traffic which requires a
low delay and moderately large throughput requirement-an
example being packetized speech). Indeed, an unresolved
issue recently raised by Dr. Robert E. Kahn (Editor of this
Special Issue) is how effective it would be to handle stream
traffic by dividing each trunk into a multiplicity of medium-
capacity channels which may then be linked together to form
a stream traffic path. We are currently looking at this issue.
B. The Switch
Our second principle has to do with the use of a software
switch at the nodes of a network. The principle here is that
it pays to place intelligence at the switching nodes of a net-
work since the cost of that intelligence is decreasing far more
rapidly than the cost of the communications resource to which
it is attached. The idea is to invest some cost in an intelligent
switch so as to save yet greater cost in the expensive com-
munications resource. The ab'Ii'introduce new programs,
new functions, new topologies,.n_e_. _w n_odes, etc., are all enhanced
by the programmable features of a clever communications pro-
cessormultiplexer at the software node.
C. Constraints
The principle here is simply, "constraints are necessary and
often are evil." Indeed some of the constraints we have seen
are sequencing, storage management, capacity allocation, speed
matching, and other flow and routing control functions. These
"natural" constraints render us vulnerable to dangerous dead-
locks and degradations. As mentioned above, if the constraint
cannot be met due to some possibly unfortunate accident,
than the system will stop all flow. If one is slow in meeting
the constraints, then that represents a delay-throughput
degradation. As a result of this principle, we see that it be-
hooves us to provide sufficient resources in the network which
then allow us to be more relaxed about assigning them. That
is, the more precious is a given resource, the tighter we are in
PROCEEDINGS OF THE IEEE, VOL. 66, NO. 11, NOVEMBI. i} :
allocating it to a demand, the more likely we are to rut. ..
deadlock or degradation. With an ample resource, w
more cavalier in assignment and even renege on the aSSl
if necessary, assuming that a backup facility (in the for, -.:
ample resource elsewhere in the network) is provided.
D. Distributed Control
The principle here is that one must pay a price to nat,:,
organizing a collection of distributed resources into a co,,?.
ing group. We have not yet established what that rnr.:
price is, but we have classified the price in the form ,!.
sions, control overhead, and idle capacity.
E. 'Flow Control
The "principle" here is that flow control is a critical
tion in packet communications and we are still naive.
invention and analysis of flow control procedures,
cleaner.code and cleaner concepts will simplify our abli::,
design and evaluate flow control procedures in the i;...:.,
There is a "miniprinciple," which seems to be emerging fr,,.-...,
preliminary studies [26] which states that if one .-.-,
maximize the power in a network at fixed cost, where
is defined as throughput divided by response time, thor..- ....
simple statistical assumptions on the flow, on; slould
at a point where the throughput delivered is half the lnax;n
possible and the response time is then twice the minimutt
load) response time.
F. Stale Protocols
In our experiments in the ARPANET, the SATNET. an:
packet radio network, we have occasionally attempted t,,,: ....
a protocol from one network directly over into a new not',
We have found that this is a dangerous procedure and
be carefully analyzed and measured before one adopts v..
procedure. Indeed, the use of old protocols in a new cn,;'
ment is dangerous. For example, we found that the use
ARPANET4ike RFNM end-to-end protocol was
wasteful of channel capacity .and resulted in a capt,re
between pairs of users when used in the SATNET. Ina :''
Time Division Multiple Access scheme (in which odd-nun'-"
slots are permanently assigned to user A and even -nm::" '
slots to user B), user A could prevent B from sending av...
if he simply started transmitting first in each of his s}o
this would require B to devote all of his slots to
RFNM's to A. Time in the SATNET is divided into t'ixcd
slots (of 30-ms d-ufati0n). "A slot is used for a single ;''
transmission even if the packet itself is' tiny, as is the c ....
RFNM. This inefficiency does not exist in the AR
since no extra bits are stuffed into ARPANET packC:
artificially increase their size. Indeed, gateways have l, rt:
troduced between the ARPANET and SATNET which
these nets independent of each other's protocols and
[21.
G. Inexperienced Designers
It is important that users recognize the difference ir
tion, performance, and operation of a packet not..-
o osed to a leased line Certain decisions regardr4
pp . .
parameter settings in any process-to-process com. mu ...
are often left up to the user of a packet network; lot
the buffer allocation he provides in his HOST to
from another process communicating through the
with his HOST is a decision often left to the system user.
buffer allocation is too small, he may degradc the apr
PRINCIPI
ace of the n
about, not
his allocation
design de
designers) th
of their
cannot be
actions withe:
>ose of this
with pack
le lessons an(
ded only in par
and we are I
to lessons an
issues whick
ples we
to ma'ke
one must
as a trivia
offe
hand and
that tt
and othe.
by the pr
from our
through mist
In all of
of the op
ulations of
to incorpor
arise; we c
become ir
' must p,
in the net'
modem
task to a:
fasb
resou
one must
where his j,
at which h
' when all thi:
address t:
among HOS
next
[in a positio
sharing of
New Yo
',M. Jacobs,
-----------------------------------------------------------
ß are ,- ,-. ].;0rrnance of the network to an unacceptably low degree; . packet satellite networks," this issue, pp. 1448-1467.
tulllll[ .. '- U' _. ,_ ......... -__, ..... [31 R.E. Kahn S A. Gronemeyer J Burchfiel andR C Kunzelman
u '"i comes sup [, not uecause me nccwor,; 1 suw out ra[ner ,, : ' . ' ' , . '. ' ' '
rce, w- , Advances in packetradotechnology ' thmssue pp 1468-1496
ß , t ' .e his allocation was too small The principle here is that 41 P Baran On dstnbuted commumcatons,' IAND Setres
1 tt; foaX_ 'leaves design decisions in the hands of the users (or even !5' RDePI[' RanrdhCeørrnørtitøn' Santa Monica, CA, Aug. 1964.
I111[,. : - - -' -er - -,-- ,ho ;,4;.;,4, ..... ß . ;r .... ,4 I I . a 'es, "T p ' c'p es of a data communication network for
Vidcd 90r}( aeslgn s/ tn,, ,,,,,o,. ,,,u,,uuo. aa ,,,,,, u,. ,,,,,,,,u a computers and remote peripherals," in Pros. IFIP Congress '68,
ß .he effect of their decisions regarding these parameter set- Edinburgh, Scotland, pp. 709-714; Aug. 1968.
.. they cannot be expected to understand the consequence 161 L. G. Roberts, "Multiple computer network deveIopment to
ice to atll ."-'elf actions without being so informed.
into a coo
VI. CONCLUSIONS
t that miat
: .,, purpose of this paper has been to boil down a decade of
te form o[ uli,, .fience with packet communications and from this to ex-
g some lessons and principles we have established. We have
txeded only in part in this endeavor; the field is stl mong
t n
res. Ho
' our ab
: m the f
erg f
ff one
st, whe . ;unications offers opportuties to the informed user on
:e, th : )he hand and sets traps for the naive user on the other. It
shodo:fessary that the overriding principles which we have
If the .hshed and others which we have yet to establish be well
e ml :atood by the practitionem in the field. We must continue
.2.d am from our experience, and alas, that experience is often
..::d through mistakes obseed rather than through clever
,TNET,
;rapted lo
a new
edure tad
e adopt
a a new
at the
w
a cap
4ET.
. even-n
;endg
of do
ots to
nto ffm'
s th0
the
qET
ys Mvo
T w
-ols
feron
:ket
..CIy and we are learning new things each day. Indeed, in
;ion to lessons and principles, we have identified a number
:pen issues which require further study. Aside from the
a.er principles we stated in the preceding section, we feel it
::c½ssary to make some concluding statements. First we
:that one must view packet communications as a system
.::r than as a trivial leased line substitute. The use of packet
ß ::dion. In all of our design procedures we must constantly
. a'are of the opportunity to share large resources among
.-;: populations of competing demands. We must further be
-nred to incorporate new technologies and new applications
:hey arise; we cannot depend upon "principles" as these
ß :aples become invalid in the face of changing technologies
:. pplications.
,stly, we must point out that the true sharing of processing
-_ties in the network (i.e., the HOSTS) has not yet been
=~zed in modern day networks. One would dearly love to
;'-nit a task to a network, ask that it be accomplished in the
:: efficient fashion, and expect the network to find the
,c suitable resources on which to perform that task. Cur-
-.y, one must specify on which HOST his program should be
red, where his job should be executed, where to store his
ts, at which location his results should be printed, and
'.'.fY when all this must happen. The next phase of network-
ß -9st address this 'general question. .of' automatic ;esource
k~g among HOSTS in a distrLbuted processing environment.
ß ps m the next special s$-U pocket communications we
< be in a position to identif(!lessons and principles for true
n:':rce sharing of this typ TM '
REFERENCES
L. Kleinrock, Queueing System& Volume II: Computer Applica-
tions. New York: Wiley Interscience, 1976.
1. M. Jacobs, R. Binder, and E. V. Hoversten, "General purpose
achieve resource sharing," in Pros. ACM Syrup. Operating
Gattinburg, TN, 1967.
[7] L.G. Roberts, "The evolution of packet switching," this issue, pp.
1307-1313.
[ 8 ] L. Kleinrock, Communication Nets; Stochastic Message Flow and
Delay. New York: McGraw-Hill, 1964, out of print. Reprinted
by Dover Publications, 1972. (Published in Russian, 1970,
Published in Japanese, 1975.)
[9] O. J. Boxres, "On a tandem queueing model with identical service
times at both counters, I.," University Utrecht, Dept. of Mathe-
matics, Preprint No. 78, Mar. 1978.
[ 10 ] L. Kleinrock, "Performance of distributed multi-access computer-
communication systems," in Proceedings of IFIP Congress '77
Toronto, Canada, pp. 547-552; Aug. 1977.
[11] L. Pouzin and H. Zimmerman, "A tutorial on protocols," this
issue, pp. 1346-1370.
[t21 L. Kleinrock, "ARPANET lessons," in Pros. Int. Conf. Com-
munications, PhiladeIphia, PA, pp. 20-1-20.6; June 1976.
[13] R. Kahn and W. Crowther, "Flow control in a resource sharing
computer network," in Proc. 2nd IEEE Syrup. Problems in
Optimization of Data Communication Systems, Palo Alto, CA, pp.
108-116, Oct. 1971, (also reprinted in IEEE Trans. Communica-
tions, pp. 539-546; June t972).
[14] E. Raubold and J. Haente, "A method of deadlock-free resource
allocation and flow control in packet networks," in Proc. Thtrd
Int. Conf. Computer Communication, Toronto, Canada, pp. 483-
487; Aug. 1976.
[15] W. Naytot, "A Ioop-free adaptive routing algorithm for packet
switched networks," in Pros. Fourth Data Communications $ym.,
Quebec City, Canada, pp. 7.9-7.14; Oct. 1975.
[ 16 ] A. Segatl, P.M. Merlin, and R. G. Galtager, "A recoverable protocol
for Ioop-free distributed routing," in Pro. Int. Conf. Communica-
tions, Toronto, Canada, voI. 1, pp. 3.5.1-3.5.5; June 1978.
[171 H. Opderbeck andL. Kleinrock, "The influence of control proce-
dures on the performance of packet-switched networks," in Nat.
Telecommunications Conf. Record, San Diego, CA., pp. 810-817;
Dec. 1974.
[ 18] W. Price, "SimuIation of packet-switching networks controlled on
isarithmic principles," in Pros. Third Data Communication Syrup.,
St. Petersburg, FL, pp. 44-49; Nov. I973.
[19] W. Naylot and L. Kleinrock, "On the effect of periodic routing
updates in packet-switched networks," in Nat. Tetecommunica.
tipns Conf. Record, Dallas, TX. nn. 16.2-1-16.2-7; Nov. 1976.
[201 L. Kleinrock and M. GerIa, "On the measured performance of
packet satellite access schemes," in Pros. Fourth Int. Conf. Corn.
purer Communication, Kyoto, Japan, Sept. 1978.
[21 ] F. Tobagi, "Performance anaIysis of packet radio communication
systems," in Nat. Telecommunications Conf. Record, pp. 12.6-2-
12.6-7; Dec. 1977. .
[ 22 ] G. Akavia, "Hierarchical organization of di. tributed packet-switch-
ing communication systems," Ph.D. Dissertation, Computer Sci-
ence Department, Univ. of California, Los Angeles, Mar. 1978.
[23] R. Metsalle and D. Boggs, "Ethernet: Distributed packet switch-
ing for toeaI computer networks," Communications. of the A CM, ..
vol. 19, no. 7; pp. 395-404, JuIy 1976.
[24] L. Kleinrock and-F. 'Karopun, "Data communications through
large packet-switching networks,'"'in Pros. Int. Teletraffic Con-
gress, Sydney, Australia, pp. 521-1-521-10; Nov. 1976.
[25] L. Kleinrock, "Resource alocation in computer systems and
computer communication networks," in Pros. of IFIP Congress
'74, Stockholm, Sweden, pp. 11-18; Aug. 1974.
[261 --, "On flow controI," in Pros. Int. Conf. Communications,
Toronto, Canada pp. 27.2-1 to 27.2-5, June 1978.
[27] V. G. T. Cerf and P. Kitstein, "Issues in packet network intercon-
nection," this issue, pp. 1386-1408.
Is
r to
stem
-----------------------------------------------------------
-----------------------------------------------------------
