The ARPANET and Computer Network

The ARPANET & Computer Networks
Lawrence G. Roberts
NetExpress Inc.
In 1964 only large mainframe computers existed, each with its own separate set of
users. If you were lucky the computer was timeshared, but even then you could not go far
away since the terminals were hardwired to it or connected by local phone line. Moreover,
if you wanted data from another computer you moved it by tape and you could forget wanting
software from a different type of computer. Thus, most users were tied by their computer
and terminal to a very restricted enviornment.
Today, in 1985, your terminal could well be a microcomputer networked with a very
large, worldwide collection of other computers. You can obtain data and software from all
these computers relatively easily with room for improvement) or, where convenient, use the
software and data on its home computer by remote access, computer to computer.
This change, which has occurred over the past 20 years, is in part a massive and
evolutionary change in computer technology, and in part a modest and revolutionary change
in communications technology. The revolution in communications started with an experiment
in computer networking, the ARPANET, and grew into a communications revolution called
packet switching. Today virtually all the world is linked by packet switched
communications service so that any terminal can access almost any computer in the woI']d.
This packet switched data network has grown up Independent of the telephone network, but
over the next 20 years the basic fabric supporting all switched services (data, telephone
and video) appear likely to become converted to packet switching, completing the
revolution.
l{tstory of Network Concepts
Going back to examine the history of computer networks, the first event for me took
place in November 1964 at the Second Congress on the Information System Sciences in Hot
Springs, Virginia. In informal discussions with J. C. R. Licklider, F. Corbato, and A.
Perlis, I concluded that the most important problem in the computer field before us at
that time was computer networking; the ability to access one computer from another easily
and economically to permit resource shaing. That was a topic in which Licklider was very
interested and his enthusiasm infected me. My interest was more toward the networking and
communications issues rather than the computer language and comparability issues which
were foremost in Lick's mind. For at least the prior year, Ltcklider, who was then
running the ARPA IPT Office (then called Command & Control Research), had been pursuing
the concept of the "Intergalactic Computer Network," trying to define the problems and
benefits resulting from computer networking. In any case, that Hot Springs discussion
convinced me that I should change my carrier ob3ectives to concentrate on computer
networking and the related communications problems.
One year later, in 1965,' a second important meeting took place at MIT. Donald Davies
from the National Physical Laboratory in the U.K. was at MIT to give a seminar on tlme
sharing. Licklider, Davies, and I discussed networking and the inadequacy of data
communication facilities for both time sharing and networking. Davies reports that
shortly after this meeting he was struck with the concept that a store and forward system
for very short messages (now called packet switching) was the ideal communication system
for interactive systems. His wrote about his ideas in a document entitled "Proposal for
Development of a National Communication Service for On-Line Data Processing" which
envisioned a communications network using trunk lines from 100K bits/sec in speed to 1.5
megabtts/sec (T1), message sizes of 128 bytes and a switch which could handle up to 10,OO0
messages/sec (Historical note: this took 20 years to accomplish). Then in June 1966,
Davies wrote a second internal paper, "Proposal for a Digital Communication Network" in
which he coined the word packet, a small sub part of the message the user wants to send,
and also introduced the concept of an "interface computer" to sit between the user
equipment and the packet network. His design also included the concept of a Packet
Assembler and Disassembler (PAD) to Interface character terminals, today a common element
of most packet networks.
As a result of distributing his 1965 paper, Donald 'Davies was given a copy of an
Permission to copy without fee all or part of this material is granted publication and its date appear, and notice is given that copying is by
provided that the copies are not made or distributed for direct permission of the Association for Computing Machinery. To copy
commercial advantage, the ACM copyright notice and the title of the otherwise, or to republish, requires a fee and/or specific permission.
¸ 1986 ACM-0-8979 I- 176-8- 1/86-0051 $00.75
51
------------------------------<page break>-----------------------------
internal Rand report, "On Distributed Communications" by Paul Baran of the Rand
Corporation, which had been written in August 1964 (1). Baran's historical paper also
described a short message switching network using T1 trunks and a 128 byte message size
but was oriented toward providing extremely reliable communications for secure voice and
data in a military environment. In all, there were 11 reports written for the Air Force
in the Rand Memorandum group, of which a couple were classified and unfortunately the
others were very sparcely publ.ished in the scientific press, 'thus their impact on the
actual development of packet switching was mainly supportive, not sparking its development
- that happened independently at Rand, NPL and ARPA.
The First Network Experiment
Convinced that computer networking was important, the first task was to set up a test
environment to determine where the problems were, Thus, in 1966, I set up two computer
networks between Lincoln Laboratory's TX-2 computer and System Development Corporation's
Q-32 computer using a 1200 bps dial channel (high speed those days). Each computer was
operating in time-sharing mode and permitted any program to dial the other computer,log-
in, and run programs much as it would execute a subroutine call. The experiment showed
that there was no problem getting the computers to talk to each other and use resources on
the other computer time-sharing operating systems made that easy. The real problem
uncovered was that dial communications based on the telephone network were too slow and
unreliable to be operationally useful. This work, jointly authored with Tom Marill, was
published in the AFIPS FJCC proceedings, Nov. 1966 (2). The lesson learned - a new data
communications network is needed in order to successfully network computers.
ARPANET Development
The chance to develop and build a major computer network experiment based on radically
new communications technology came within a few months. I was asked to take over .the
responsibility of the ARPA Information Processing Techniques (IPT) office and manage and
build its programs. 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 an experimental network project: consequently, the ARPANET was planned
durin G 1967 with the aid of these researchers to link these projects' computers together.
One task was to develop an computer interface protocol acceptable to all 16 research
groups. A second task was to design a new communications network technology to support 35
computers at 16 g]tes with 500,000 packets/day traffic. The initial plan for the ARPANET
wa published in October 1967 at the ACM Symposium on Operating System Principles in
Gatlinburg Tennesgee (3). The reasons given at that time for establishing a computer
network were:
A. Load Sharing: Send program and data to remote computer to balance load.
B. Message Service: Electronic mail service (mailbox service).
C. Data Sharing: Remote access to data bases.
D. Program Sharing: Send data, program remote, e.g. Supercomputer.
E. Remote Service: Log-in to remote computer, use its programs and data.
The communications network design was that of the now conventional packet network:
Interface Message Processors (IMP's) at each node ineconnected by leased
telecommunication lines providing a stor e and forward service on very short messages. The
main difference from later packet nets was that the IMP's were located at the computer
sites and connected by a short parallel cable rather than a communications line interface.
Also presented at the Gatlinburg Symposium was Donald Davies's first open publication
on the NPL packet network concepts presented by Roger Scantlebury, "A Digital
Communication Network for Computers Giving Rapid Response at Remote Terminals." (4) It
detailed the concept of a high level packet net with high capacity nodal switches and
interface computers in front of mainframe computers. This was the first time that either
Davies or I knew anything about the work of each other since our 1965 contact. The NPL
paper clearly impacted the ARPANET in several ways. The name "packet" was adopted, much
higher speed was selected (50 Kilobit/sec vs. 2.4 Kllobit/sec) for internode lines to
reduce delay and generally the NPL analysis helped confirm the concept of packet
switching.
Another confirmation of the basic concepts came from finally being able to read the
Rand reports on distributed communications. The Rand work was very detailed, since it
covered the whole network including microwave and one valuable analysis on routing. Their
hot-potato routing algorithum was a useful starting point for the ARPANET routing design.
During 1968, a request for proposal was let for the ARPANET packet switching IMP
equipment and the operation of the packet network. The RFP was awarded to Bolt Beranek
and Newman Inc. of Cambridge, Massachussetts, in in January 1969. The RFP specified the
general packetswitching concept, packet size, and interface protocol so that bidders could
not totally change the system concept, to circuit or message switching for example. The
two largest computer companies to receive the RFP no bid it because they didnt have mini-
computers with which to make an economic bid. BBN bid the Honywell 516 mini-computer which
was ideal for the task in 1969. Significant 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, Severo 0rnstein, William Crowther, and
David Walden. By December 1969 four nodes of the net had been installed and were
operating effectively.
52
------------------------------<page break>-----------------------------
The first set of detailed papers covering the ARPANET were published in May 1970 at
the AFIPS SJCC. (5-9) These papers reported the motivation and economics (5), the
detailed design of the IMP (6), the network delay analysis and experience (?), the
'topological design programs and results (8), and the host-to-host protocol (9). These
papers showed the world for the first time that packet switching works, that it is
economic and that it is reliable and virtually error free. They also provided a complete
description of how a working network was designed. As such these papers were the
technical and motivational basis for many other network experiments around the world.
The ARPANET utilized minicomputers at every node to be served by the network,
interconnected in a fully distributed fashion by 50 KB 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 dynamically updated routing table the minicomputer sent the packet over
whichever free line was currently the fastest route toward the destination. Upon
receiving a packet, the next minicomputer would acknowledge it and repeat the routing
process independently. Thus, one important characteristic of the ARPANET was its
completely distributed, dynamic routing algorithm on a packet-by-packet basis, based on a
continuous evaluation within the network of the least delay paths, considering both line
availability and queue lengths.
The technical and operational success of the ARPANET quickly demonstrated to a
generally skeptical world that packet switching could be organized to provide an efficient
and highly responsive interactive data communications facility. Fears that packets would
loop forever and that very large buffer pools would be required were quickly allayed.
Since the ARPANET was a public pro3ect connecting many major universities and research
institutions, the implementation and performance details were widely published. (10, 11,
12, 13, 14). The work of Leonard Kleinrock and his associates at UCLA on the theory and
measurement of the ARPANET has been of particular importance in providing a firm
theoretical and practical understanding about the performance of packet networks.
The ARPANET was first demonstrated publicly at the first International Conference on
Computer Communications (ICCC) in Washington, D.C. in October 1972. Robert Kahn of BBN
oganized the demonstration installing a complete ARPANET node at the conference hotel,
with about 40 active terminals permitting access to dozens of computers all over the U. S.
This public demonstration was, for many (if not most) of the ICCC attendees, proof that
packet switching really worked. At this time, it was difficult for many experienced
professionals to accept the fact that a collection of computers, wideband circuits, and
minicomputer switching nodes (equipment totaling well over 100 pieces) could all function
together reliably. The ARPANET demonstration lasted for three days and clearly displayed
its reliable operation in public. The network provided highly reliable service to
thousands of attendees during the entire duration of the conference.
Industry Reception
From the first time I distributed a description of packet switching outside the
computer research community (the 1967 paper) until about 1975, the communication
industry's reaction was generally negative since this was such a radically different
approach. In some of the initial technical speeches I gave, communications professlonals
reacted with considerable anger and hostility, usually saying I did not know what I was
talking about since I did not know all their Jargon vocabulary. The most common technical
flaw suggested (before the ARPANET was built) was that the buffers would quickly and
catastrophically run out. After the ARPANET was operating successfully, their pitch
changed to be that packet switching would never be economic without the government
subsidy. Paul Baran reported the same reaction to his papers when he presented them; this
reaction was the major reason his proposals never moved the military. Donald Davies
reported a somewhat less angry response from the British Post Office, more one of mild
interest but no serious consideration.
I learned a major lesson from that experience; paople hate to chnge the basic
postulates upon which considerable knowledge has been built. In the case of packet
switching, the first postulate to change was the statistical nature of the traffic - data
versus voice. The second Was that computing was expensive. Some people find it is
impossible to consider such a major Jolt to their memory organization - they avoid it with
putdowns if possible, if not with anger. Other people are more willing to reconsider, but
for everyone it requires considerable effort. Those of us proposing packet switching all
came from the computing field and did not need to change lots of prior concepts and
knowledge. Many of those in the communications field still have not accepted packet
switching. (The fight is heating up again as voice packet switching starts to be
considered.)
ARPANET Growth
As soon as the first four nodes were brought up and tested in December 1969 the
network grew very rapidly. One year later, in December 19'70, the network had grown to 10
nodes and 19 host computers