PROCEEDINGS OF THE IEEE, VOL. 66, NO. 11, NOVEMBER 1978 1307
The Evolution of Packet Switching
LAWRENCE G. ROBERTS,
Invited Paper
Abttract-Ovet the pat decade data communication ha Inm revolu-
tionized by ß radically new tchnoioglr calhd !rocket vitchin$. In
1968 sll interactive data communication networks
cult witched, the uune u me telephone network.
percent or more of'"-"wlau--us,-
trOiti-- inexpensive en , tt dramßtie. fly more
cost-effective to completely rexlesi communicslions networks, intro-
ducing the concept of pket switching where the transm'mio trend-
width is dymuniclly 11ocated, permitling many users to shoe the same
transmission line previoudy vequied fo one umr. Pscket switching
has been so successful, not only in improving the economics of dat.
communications but in enhancing reliability and functionsl flexibility
ß s well, thßt in t978 virtually sil new data networks being built
throughout the world re baed on packet switching. An open ques-
tion at this time is how long will it take tot voice communications to
be revolutionized -- well by packet switching technology. In order to
better understand both the past and future evoinlion of this fast mov-
ing technology, this pßper examines in detail the history and trends of
pßcket switching.
HERE HAVE ALWAYS been two fundamental and
competing approaches to communications: pre-alloca-
tion and dynamic-allocation of transmission bandwidth.
The telephone, telex, and TWX networks are circuit-switched
systems, where a fixed bandwidth is ptßallocated for the dura-
tion of a call. Most radio usage also involves ptßallocation of
the spectrum, either permanently or for single call. On the
other hand, message, telegraph, and mail systems have histori-
cally operated by dynamically allocating bandwidths or space
after a message is received, one link at a time, never attempting
to schedule bandwidth over the whole source-to-destination
path. Before the advent of computers, dynamic-allocation sys-
tems were necessarily limited to nonreal time communications,
since many manual sorting and muting decisions were required
along the path of each message. However, the rapid advances
in computer technology over the last two decades have not only
removed this limitation but have even made feasible dynamic-
allocation communications systems that are superior to
ptßallocation systems in-connect time, reliability, economy
and flexibility. This n[?munications technology, called
"packet switching." divi_'ds theinput flow of information into
small segments, or packets7;,qf data which move through the
network in a manner similar to the handling of mail but at im-
mensely higher speds. Although the œust packet-switching
network was developed and tsted less than ten years ago,
packet systems already offer substantial economic and perfor-
mance advantages over conventional systems. has re-
suited in rapid worldwide acceptance of packet switching for
low-speed interactive data communications networks, both
public and private.
Manmcript rechted May t 1, 1978;rvtd May 22, 1978.
. The author is with Telenet Communlcatiom Corporation, Washins-
ton, D4 20036.
A question remains, however. Will dynamic-allocation tech-
niques like packet switching generally replace circuit switching
and other preallocation techniques for bigix-speed data and
voice communication? The history of packet switching so far
indicates that further applications are inevitable. The follow-
ing examination of the primary technological and economic
trade-offs involved in the gr,owth of the packet switching com-
munications industry should help to trace the development of
the technology toward these further applications.
EARLY HISTORY
Packet switching technology was not really an invention, but
a reapplication of the basic dynamic-allocation techniques
used for over a century by the mail, telegraph, and torn paper
tape switching systems. A packet switched network only al-
locates bandwidth when a block of data is ready to be sent,
and only enough for that one block to travel over end network
link at a time. Depending on the nature of the data traffic
being transferred, ithe packpt-switching approach 'is 3-100
times more efficient than preallocation techniques in reducing
the wastage of available transmission bandwidth resources. To
do this, packet systems require both processing power and
buffer storage resources at each switch in the network for each
packet sent. The resulting economic tradeoff/ s/mple: if lines
are cheap, use circuit switching; if computing is cheap, use
packet switching. Although today this seems obvious, before
packet switching had been demonstrated technically and proven
economical, the tradeoff was never recognized, let along
analyzed.
In the early 1960's, preallocation was so clearly the proven
and accepted technique that no communications nginecr ever
seriously considered reverting to what was considered an obso-
lete technique, dynamic-allocation. Such techniques had been
proven both uneconomic and unresponsive 20-80 years pre-
viously, so why reconsider them? The very fact that no great
technological breakthrough was required to implement packet
switching kas another factor weighing aga/nst its acceptance
by the engineering community;
What was requied was the total teevaluation of the perfor-
mance and economics of dynamic-allocation systems, and their
application to an entirely different task. Thus, it remained for
outsiders to the communications industry, computer profes-
sionals, to develop packet switching in response to a problem
for which they needed a better answer: communicatin$ data to
and from computers..
THE PIONEERS
Rand
The first published da.ription of what we now call packet
switching was 'an I l-volume analysis, On Distributed Com-
munications, prepared by Paul Baran of the Rand Corporation
0018-9219/78/I I00-1307500.75 ¸ 1978 IEEE
-----------------------------------------------------------
1308
PROCEEDINGS OF THE IEEE, VOL. 66, NO. IF. NOVEMBER 1978
in August 1964 {ll. This study was conducted for the Air
, Force, and it proposed a fully distributed packet switching sys-
tem to provide for all military communications, data, and
voice. The study also included a totally digital microwave sys-
tem and integrated encryption capability. The Air Force's
primary goal was to produce a totally survivable system that
contained no critical central components. Not only was this
goal achieved by Rand's proposed packet switching system,
but even the economics projected were superior, for both
voice and data transmissions. Unfortunately, the Air Force
took no follow-up action, and the report sat largely ignored
for many years until packet switching was rediscovered and ap-
plied by others.
ARPA I
Also in the 1962-1964 period, the Advanced Research Pro-
jects Agency (ARPA),-finder the direction of J. C. R. Licklider
(currently at M.I.T.), sponsored and substantially furthered
the development of time-sharing computer systems. One of
Licklider's strong interests was to link these time-shared com----
puters together through a widespread computer network. AI-!
though no actual work was done on the communication sys-{
tern at that time, the discussions and interest Licklider
spawned had an important motivating impact on the initiators[
of the two first actual network projects: Donald Davies and I
me.
As previously indicated, the development of packet switch-
ing was primarily the result of identifying the need for a
radically new communications system. Licklider's strong in-
terest in anti.perception of the importance of the problem
encouraged many people in the computer field to consider it
seriously for the first time. It was in good part due to this
influence that I decided, in November 1964, that computer
networks were an important problem for which a new com-
munications system was required [2]. Evidently Donald
Davies of the National Physical Laboratory (NPL)in the United
Kingdom had been seized by the same conviction, partially as
a result of a seminar he sponsored in autumn 1965, which I
attended with many M.I.T. Project MAC people. Thus, the
interest in creating a new communications system grew out of
the development of time-sharing and Licklider's special inter-
est in the 1964-1965 period.
National Physical Laboratory
Almost immediately after the 1965 meeting, Donald Davies
conceived of the details of.a store-and-forward packet switch-
ing system, and in a J, une)7!-_666 description of his proposal
coined the term "packt'--'ribe the 128-byte blocks be-
ing moved around inside lhnetwork. Davies circulated his
proposed network design throughout the U.K. in late 1965
and 1966. It was only after this distribution that he discov-
ered Paul Baran's 1964 report.
The first open publication of the NPL proposal was in Oc-
tober 1967 at the A.C.M. Symposium in Gatllnburg, TN [3].
In nearly all respects, Davies' original proposal, developed in
late 1965, was similar to the actual networks being built to-
day. His cost analysis showed strong economic advantages for
the packet approach, and by all rights, the proposal should
have led quickly to a U.K. project. However, the communi-
cations world was hard to convince, and for several years,
nothing happened in the U.K. on the development of a multi-
node packet switching network.
Donald Davies was able, however, to initiate a local network
with a single packet switch at the NPL. By 1973 thi local net-
work was providing an important distribution .service within
the laboratory [41, [51. This project, plus the strong con-
viction and continued effort by those at NPL (Davies, Barber,
Scantlebury, Wilkinson, and Bartlett), did gradually have an
effect on the U.K. and much of Europe.
ARPA H
In January 1967, I joined ARPA and assumed the manage-
ment of the computer research programs under its sponsor-
ship. ARPA was sponsoring computer research at leading
universities and research labs in the U.S. These projects and
their computers provided an ideal environment for a pilot net-
work project; consequently, during 1967 the ARPANET was
planned to link these computers together.
The pan was published in June 1967. The design consisted
of a packet switching network, using minicomputers at each
computer site as the packet switches and interfacing device, in-
terconnected by leased lines. By coincidence, the first pub-
ilsfed document on the ARPANET was also presented at the
A.C.M. Symposium in Gatlinburg, TN, in October 1967 [6]
along with the NPL plan. The major differences between the
designs were the potposed net line speeds, with NPL suggesting
1.5 Mbit/s lines. The resulting discussions were one factor-lead-
ing to the ARPANET using 50-kbit/s lines, rather than the
lower speed lines previously planned [ 7 ]o
During 1968, a request for proposal was let for_the
ARPANET packet switching equipment and the operation of
the network. The RFP was awarded to Bolt Beranek and New-
man, Inc. (BBN) in Cambridge, MA, in January 1969. Signif-
icant aspects of the 'network's internal operation, such as
routing, flow control, software design, and network control
were developed by. a BBN team consisting of Frank Heart,
Robert Kahn, Scvero Ornstein, William Crowther, and David
Walden [8], [91, [ 10]. By December 1969. four nodes of the
net had been installed and were operating effectively. The net-
work was expanded rapidly thereafter to support 23:host com-
puters by April 1971,62 hosts by June 1974, and'Tlal"h'sts by
lrch '
The ARPANET utilized minicomputers at every node to be
served by the network, interconnected in a fully distributed
fashion by 50-kbit/s leased lines. Each minicomputer took
blocks of data from the computers and terminals connected
to it, subdivided them into 128 byte packets, and added a
header specifying destination and source addresses; then, based
on a dynamicall_ uable, the minicomputer
sent the packet. over whichever free line was currently tho
fastest route toward the destination. Upon receiving a pa
