Chapter 4 - Networking: Vision and Packet Switching 1959 - 1968
4.7 Planning the ARPANET: 1967-1968
In 1966, Robert (Bob) W. Taylor succeeded Sutherland as Director of the IPTO. Taylor completely subscribed to Licklider’s vision of an Intergalactic Network. Furthermore, he faced the essence of the problem every day in his office: he had three different computer terminals because he needed access to three different computers. Taylor remembers:
By late ‘65, early ‘66, there were a number of ARPA sponsored research groups that had built for themselves, and were using in their own work, some of the first time-sharing systems. So, it occurred to me, sort of taking off from this tongue and cheek ‘Intergalactic Network’ phrase of Licklider’s, that the next thing to do was obvious, and that is – if we had singular communities who could interactively communicate through a time-sharing system that they were all members of, why couldn’t we have clusters of communities interact, members of one community could interact with members of another community, as though they might be sharing a single time-sharing system.
In February 1966, influenced by the experiments conducted by Roberts and Marill at Lincoln Labs, Taylor decided the time had come for ARPA to focus on interconnecting existing, and planned, time-sharing systems into an ARPA scientific community. Not having the money to launch a new project, he approached Charles Hertzfeld, Director of ARPA.12 He remembers explaining to Hertzfeld:
There are certain experts in certain fields who sit in California, and there are other experts in that same field who sit in Massachusetts or someplace else, and if we can make this work, we can have a medium through which they can work cooperatively, and so we get amplification of ideas. Another advantage of tackling this problem is that we might be able to achieve some fail-soft characteristics in any collection of computing that the Defense Department would especially be interested in.’
So, that discussion probably lasted 15 minutes, and he immediately was excited about it, and he said: ‘You’ve got the money. How much do you need to get started?’ I gave him a number, and he pulled it out of another one of his ARPA projects, and said: ‘Go.’“13
Taylor next needed a program manager. His first choice was Roberts. Roberts, however, wanted nothing to do with becoming a program manager or of moving to Washington. Unable to think of anyone as qualified as Roberts, Taylor kept asking and Roberts kept declining. Taylor remembers the ruse that won the day:
In September or October of ‘66, it dawned on me that ARPA supported 51%, or thereabouts, of all of Lincoln Lab’s work. So I went to see Hertzfeld and I said: ‘Charley, is it still true that ARPA supports 51% or more of Lincoln Lab,’ and he said: ‘Yeah.’ I said: ‘Well, you know this network project that I’m trying to get off the ground?’ He said: ‘Yeah.’ I said: ‘Well, there’s a guy at Lincoln Lab that I want to be the program manager for it and I can’t get him to come down here. His name is Larry Roberts. I’d like for you to call the Director of Lincoln Lab and tell him that it would be in Lincoln Lab’s best interest and Larry Roberts’ best interest if the Director of Lincoln Lab encouraged Larry Roberts to come down to Washington and be the program manger for this project.’ Charley said: ‘Sure,’ and he picked up the phone with me in his office, and he called the Director of Lincoln Lab and had a short conversation and he hung up the phone, and about a month later Larry accepted the job. In Christmas of that year, he came down with his family and they stayed at my house over the holidays because they didn’t have a place to live yet. I blackmailed him into fame.
With Roberts aboard as program manager, Taylor began visiting various ARPA contractors, explaining the purpose of the network in an effort to generate support. Not wanting to give others access to their computers, most of the contractors resisted the concept. It became very clear that the challenge of bringing into being the world’s first computer communication system would involve more than just technology.
With his legendary intensity, Roberts tackled the challenges of bringing into being a network to interconnect the ARPA community. To him, the concept of communications by exchanging messages or packets seemed neither strange nor novel. It was simply a logical extension of how computers communicated internally – exchanging blocks of data.
Roberts remembers the beginnings of building a computer network:
All of us in computing were clearly not going to go after it on a circuit switched basis. We were all thinking in blocks. That’s the way computers worked. So we approached it very differently than the communications people. We thought in terms of: “How can we do this such that it will be a functionally useful service for the computers?” I got together groups and committees of the ARPA people and started working on it.
He first focused on how to build a packet network; fully realizing that there also existed the challenge of how computers would communicate across the intended peer-like network, and that the two were dependent, locked in some unseen co-evolution.
After numerous conversations, Roberts concluded his first major decision had to be the network topology: how to link the computers together. A topology of interconnecting every computer to every other computer didn’t make sense, based on the results of his experiment at Lincoln Labs and the absurdity of projecting hundreds of computers all interconnected to each other. The number of connections would explode as the square of the number of computers. A shared network, however, entailed solving the problem of switching when using a packet, or message block, architecture. To explore the questions of packet size and contents, Roberts requested Frank Westervelt of the University of Michigan write a position paper on the intercomputer communication protocol including “conventions for character and block transmission, error checking and re transmission, and computer and user identification.”14
Two alternative architectures for a shared network emerged: a star topology or a distributed message switched system. A star topology, or centralized network, would have one large central switch to which every computer was connected. It represented the least development risk because it was well understood. However, it was also known to perform poorly given lots of small messages – the precise condition of packet messaging. On the other hand, a distributed message switching system as proposed by Baran and Davies, had never been built, but held the theoretical advantage of performing best given lots of small messages.15 With a choice needing to be made, the upcoming annual meeting of ARPA contractors seemed an ideal time to air the issues and reach a decision.
Wesley Clark remembers the discussion:
Towards the end of the meeting it became clear to me what the problem was. So I slipped a note to Taylor stating ‘I know what to do.’ Taylor probably didn’t look at my message until after the meeting. It was fairly obvious to me to put the communication functions in a separate, smaller computer outside the computer ‘network.’
After the meeting, Taylor, Roberts, Clark and Dave Evans shared a taxi to the airport and discussed the network topology decision. Taylor remembers:
Larry, prior to this taxi ride, was thinking of a network controller in a centralized sense; something in the center of the country, a large machine, that would control the network, and I was nervous about that. I talked to Licklider and to Wes about it, separately, and Larry wasn’t irrevocably wedded to the idea, but that was his model at the time. In the cab to the airport after this meeting, I got Wes talking about it. Whether he had sorted it all out prior to that cab ride or whether he sorted it out based spontaneously in the conversation in that cab, I don’t know. But he said: “Why have a central control. Why not have small machines?
I think it was fairly obvious. I think somebody else would have come to it with a little more time. Let those little computers talk to one another and serve as terminals to which the big machines would talk. In a sense, that took the big machines outside the network. The concept up to that point was that the network was the big machines plus all the interconnections, and my sudden realization at the meeting was that you wanted the machines outside the network, not inside it. Larry or Bob asked me how to get these little small computers built and I said I thought there was only one person who could do that job in the country, namely Frank Heart.
Back in Washington, Roberts and his staff studied Clark’s suggestion and concluded that the idea of a separate computer located at each site handling the network functions was an ingenious solution. In addition to its technical merits, it allowed the network to be designed and built independently of host computer hardware and software, greatly simplifying project management. The small computers, to be called interface message processors (IMP’s), together with the telephone lines and the modems would constitute the message-switching, communications network, or “Subnet” (or subnet.) (See Diagram 4.7.0 The Subnet and Hosts.)
Diagram 4.7.0 The Subnet and Hosts
Roberts understood a deep and important dilemma of the emerging network. Computers wanted to communicate in message sizes very much larger than ideal for a packet network. This meant an IMP would receive a message from its Host computer that it would have to parse into packets that in turn would traverse the subnet. The packets would then have to be reassembled into the message before being usable by the Host and, most likely, even before being delivered to the Host. Realistically, that implied that the IMPs would have to store packets before forwarding them. Such a network had never been designed, much less built.
All of us thought, clearly, in those days, about computer switching rather than circuit switching; some sort of computerized switching. You got the traffic in and you put it out. It could have been that we put it out block for block as fast as it came in; it could have been that we stored the whole message and forwarded it. What we concluded was that you wanted to not store the whole message and forward it, and you couldn’t have a perfect virtual cut-through where you sent every block immediately synchronously because it might interfere with the next message. So you had to do it in some smaller breakdown, which is like a packet, or whatever, which, of course, is the size lump you’re in anyway, because you’ve got to put sum checks on it every interval. So, there wasn’t any question about packets – and clearly Donald gave it the name – that we had to be in that sort of size. Now and then, each one of us in the world would derive what length that ought to be ultimately for sum check, because of errors, and that was around the thousand-bit area then, with error rates that were in existence then.
Roberts sought help from Leonard Kleinrock his former officemate from MIT, now on the faculty of UCLA.16 Even though Kleinrock was not working on network queuing theory at the time, in his Ph.D. thesis, he had shown that a large store-and-forward could work, despite the delays introduced by store-and forward. In 1964, Dover Publications had published his thesis as a book; the same year RAND had published Baran’s work. Kleinrock reflects, saying the ideas in “Communication Nets: Stochastic Message Flow and Delay” “lay fallow in the scientific literature because it was, in some sense, before it’s time. Nobody believed these networks could be built. It drew upon ideas from classical military communications networks.”
During this period, Roberts was also coming to the opinion that a limited experiment would not be very meaningful: a network of many nodes had to be created if the network was going to be useful for serious purposes. But that introduced the problem of how to convince that many more potential computer sites to devote the resources to the network, as opposed to their existing priorities. Licklider comments:
I have the strong impression that Larry thought there was no little experiment that would be very helpful; that he had to have a network with many nodes – a dozen anyway and probably 100 – and that it had to be used for serious purposes, and that his problem was – what he had to excel at as a manager was actually getting this whole ARPA community to make ten or fifteen percent of everybody’s effort to get the network to go. He though he was in a good position, that he had not only the people who could build it, but enough people to use it, if he could only get them really focused and interested. I believe I was director of Project MAC at that time, and I loved the network. I had trouble with my people about it. They didn’t like it, but I said: “I estimate as a minimum, ten percent of our effort is going to be the network. It’ll just happen that way,” and partly that was promotion on my part and partly it was true belief, but most of the others were much more interested in what they were doing than Larry’s network.
In 1967, Taylor began giving more responsibilities to Roberts, hoping that Roberts would succeed him as director of IPTO. It meant Roberts had less and less time for the network project. To compensate, Roberts recruited Barry Wessler from the University of Utah to be his assistant. (Wessler would not actually join IPTO until early 1968.)
Then, in another important community event that caused historical course-corrections, came the ACM Symposium on Operating System Principles in Gatlinburg, TN, October 1-4, 1967. Roberts presented a paper: “Multiple Computer Networks and Intercomputer Communications.” In it he lamented the deficiencies of dial-up telephone circuits, yet nevertheless concluded that the communication links between IMPs would be 2400 bit/second dial-up circuits.17 That constraint would not last very long, however, for another speaker, Roger Scantlebury, presented a paper authored by Davies, Bartlett, Scantlebury and Wilkinson, describing a local network being developed at NPL based on Davies’ ideas and employing much higher speed circuits.18 (On returning to the U. K. after the Gatlinburg conference, Scantlebury reported: “It would appear then that the ideas in the NPL paper at the moment are more advanced than any proposed in the USA”19 20 )
Roberts took the findings of the NPL team seriously, later describing how they influenced his thinking: “The NPL paper clearly impacted the ARPANET in several ways. The name “packet” was adopted, a much higher speed was selected (50 Kilobit/second vs 2.4 Kilobit/second) for internode lines to reduce delay and generally the NPL analysis helped confirm the concept of packet switching.”21
Also at Gatlinburg, Roberts and Baran finally found time to talk. Roberts remembers:
The RAND work was very detailed, since it covered the whole network including microwave and one valuable analysis on routing. The hot potato routing algorithm was a useful starting point for the ARPANET routing design.”22
He knew that in addition to the advantages of having the communities linked, they would have to figure out how to make heterogeneous systems communicate.
Taylor remembers the amount to have been about $1 million.
ARPANET Completion Report
“Star systems perform satisfactorily for large blocks of traffic, but the central switch saturates very quickly for small message sizes….. (The) alternative to the Star, suggested by the RAND Study “On Distributed Communications,” is a fully distributed message switched system. Such a system has a switch or store and forward center at every node in the network. Each node has a few transmission lines to other nodes; messages are therefore routed from node to node until reaching their destination. “The ARPA Network, Roberts and Wessler.
Before moving to California to join the faculty of UCLA in 1963, Kleinrock added to the long list of computer scientist who spent time at Lincoln Labs.
“Current automatic dialing equipment requires about 20 seconds to obtain a connection and a similar time to disconnect. Thus, the response time is much too long assuming a call is made only after a message arrives and that the line is disconnected if no other messages arrive soon. It has proven necessary to hold a line which is being used intermittently to obtain the one-tenth to one second response time required for interactive work. This is very wasteful of the line and unless faster dial up times become available, message switching and concentration will be very important to network participants.” Multiple Computer Networks and Intercomputer Communications, Roberts
“A digital communications network for computers giving rapid response at remote terminals,” D.W.Davies, K.A. Bartlett, R.A. Scantlebury, P.T. Wilkinson, ACM Symp. Operating Systems Problems, Oct. 1967. Shortly after Davies lecture in June 1966, Davies and Derek Barber decided it was necessary to build a model ‘interface unit’ and use it as a local network within NPL. To study issues introduced in a ‘multi-interface’ network such as routing, flow control and congestion, they decide to use simulation. In August of 1966, when Davies became Superintendent of the newly named Computer Science Division, he authorized two teams, one to work on each project.
A Personal View of the Origins of Packet Switching, Davies
The NPL Data Communication Network will not become operational until June 1973.
The ARPANET & Computer Networks, Roberts
“The first time we really sat down and talked about the network in detail was at the Gatlinburg conference.” Roberts interview with author.