Origins of packet switching

On packet switching

The following email exchange occurred in April 2009, and was precipitated by a discussion I had with Jovan Kurbalija from the Diplo Foundation in Geneva. The discussion related to the role of Paul Baran in defining Arpanet, and the extent to which that may have reflected a desire to build a network to avoid nuclear war. To help clarify the role I can record the following exchange.

Note: it seems packet switching, and the related datagram concept (Louis Pouzin), emerged in a number of places at once to anyone who thought deeply enough about how to construct a more reliable networking environment. I would also seem that packet switching had a precursor in the non-digital world in torn tape telegraph messaging. (thanks to Larry Press for pointing that out).

Question (Ian Peter)

From what I have read here and elsewhere, it would appear that both Paul Baran and Donald Davies (via Roger Scantlebury) met at times in the Arpanet design phase with various members of the Arpanet team to explain their similar theories on packet switching. I have also read that it was the Davies design which was adopted, not Baran’s.

Can anyone shed more light on this, who met who, and why if both designs were known Davies was preferred?

Vint Cerf

Bob Kahn was a key player in the design of the IMP and the ARPANET

Paul’s principal conceptual ideas related to packetization (message blocks) and hot-potato routing, I believe Donald Davies had a multi-node idea but implemented only one node  owing to funding limits. He or his team via Roger Scantlebury influenced the ARPANET design be convincing Larry Roberts to use 50 kb/s circuits rather than 2.4 kb/s circuits.

Donald also contributed the term “packet” into the literature.

Robert Kahn


Vint, my comments below are intended to amplify on what you briefly summarized. Im not sure what the context for this is, but many folks wrote about networking over a number of years.

You cited some of them. Kleinrock, Baran, Davies, Licklider to mention four early ones. Baran tried to explain how to build a packet net before it was practical to do so. He started out by postulating the use of broadcast radio stations (like normal AM stations) to hopefully get data from place to place “hopping” from radio station to radio station.

There was no available electronics to do so (vlsi had not been created yet), and only big mainframes would have been available for use at great cost. No discussion of protocols and all that involves. His was a fine conceptual start, but hardly a blueprint to build anything. Donald Davies actually tried to raise funds to build a packet net, but was unable to do so. He ended up outfitting a single minicomputer (which had only shortly come into commercial availability) with multiple terminals to demonstrate the packet concept from one terminal in a room to another.

Kleinrock’s MIT thesis provided interesting analytical approaches to evaluating commodity queuing networks and stimulated many follow-on research projects, out of which came many of the students that went into the field. He also pioneered the field of network measurement (and I presume modeling as well).

Licklider was a wonderful spokesman for the possibilities of networking, but never really a practitioner.

With encouragement from Bob Taylor and Charles Herzfield, Larry Roberts set out to create the first packet net – the ARPANET as it came to be called. He outlined the goals and the trajectory for the project sufficient for someone to figure out how to make happen what he outlined. A packet network (actually it was called a message switching network initially and only later replaced by the packet switching moniker) that consided of nodes connected by “high speed” digital lines to be leased from the (then) telephone company. He called for messages to be broken into packets of up to 1000 bits each, and then routed through the net and reassembled into the original message at the destination. Larry’s background would have likely enabled him to build the network himself, or with a small technical team, but he had managerial responsibilities at DARPA that did not directly lend itself to establishing the required level of technical immersion in-house. So, DARPA issued an RFQ to have a contractor design and build the network. BBN won the contract and that successful initiative created the ARPANET IMPS, which formed the basis for the ARPANET (with 50 Kbps lines from AT&T).

The technical task was to figure out how to build such a device, the IMP, to make such a network come into existence.

I was responsible for the system design of the network (and primarily the design of the IMP). Severo Ornstein was responsible for the hardware design and development, Bill Crowther and Dave Walden for the detailed software implementation. Frank Heart was the BBN executive that had managerial responsibility for the effort. Dave and I did the initial field testing and debugging of the initial 4 node-net on the west coast (+ utah). Larry masterminded the ARPANET project from his position at DARPA. I would say the BBN effort resulted in the first demonstrated proof of concept of a packet switching network and the ARPANET project demonstrated the first example of a computer communication network. In parallel with the IMP and packet net development, the effort to develop protocols and host computer applications proceeded and, in many ways, was the required counterpart to the packet switching network piece which made the network concept useful to real users.

Then there was the plan to interconnect multiple heterogeneous packet networks (and their attached computers cum protocols) which demonstrated the concept of Internetting and led to today’s Internet. But, then again, thats an entirely different story.

Bob

Vint Cerf

(in reply to a question about torn tape telegraph messaging)

Yes of course we did know about “torn tape” and also about message switching in the form of AUTODIN.

If you look at Len Kleinrock’s book that emerged from his dissertation it was about stochastic flow and delay in message switched systems. An ARPANET innovation was to break messages up into “packets” for purposes of transmission to reduce transmission delay which was significant over low speed backbone trunks available at the time.

Also, for purposes of noise resistance, the shorter packets had a higher probability of arriving intact than long messages.

Communication Nets: Stochastic Message Flow and Delay

This text develops a queuing theory model of communications nets, with realistic assessments that will benefit those working with computers and other communications systems. Topics include optimal channel capacity assignment, effect of priority and other queue disciplines, choice of routine procedure, fixed-cost restraint, and design of topological structures. 1964 edition.

Publisher: Dover Publications
ISBN: 0486458806
EAN: 9780486458809
No. of Pages: 209

Vint Cerf (to Roger Scantlebury)

Roger,

Is it your understanding that Donald and the NPL team were unaware of the Baran work at RAND during the period of development of the network at NPL? I don’t think this has to do with anyone fighting over paternity. It is just a question about when the various “packet”  efforts became aware of each other.

For example, your interaction with Larry Roberts in 1967 is the key link that drew ARPA and NPL groups into mutual awareness I think.
I had once thought that you might have drawn Roberts’ attention to Baran’s work but I suppose not, if you were unaware of it in 1967.
In fact, it would be of interest to know when and how you (or Donald) might have learned of it?

Roger Scantlebury

Hi Vint

We referenced Baran’s paper in our 1967 Gatlinburg ACM paper. You  will find it in the References. Therefore I am sure that we
introduced Baran’s work to Larry (and hence the BBN guys).

We were unaware of Baran’s work when we started our own design work in 1965, but were given a copy of his paper by one of our colleagues in the UK Ministry of Defense (in 1966) while we were writing the1967 paper. Clearly Donald and Paul Baran had independently come to a
similar idea albeit for different purposes. Paul for a survivable voice/telex network, ours for a high-speed computer network.

I hope this explains the time-line?.

 

Advertisements

One Response to “Origins of packet switching”

  1. johnnyryan Says:

    This is very, very useful. I am working on a history of the Internet Scantlebury’s and Kahn’s contributions here in particular are invaluable. Thank you – details of my project are at http://johnnyryan.wordpress.com/books/net-history-2010/.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: