Bookmark and Share

The Network of Networks

X.25 connected networks together to great effect - but there was a problem. As with Henry Ford's colour chart for the Model T, you could connect any two networks together as long as they both had X.25 interfaces[1]. If two X.25 hosts communicated across a heterogeneous network including a non-X.25 network, it might well be possible to build a gateway to translate packet formats and maybe even to map different addressing schemes but, if the network were an unreliable one, the end-to-end connection would be rendered unreliable as well. The problem might be addressed by having some host process protocol like the NCP of Arpanet or the ST of Pouzin's network but this was an area, the transport layer of OSI, where X.25 had nothing to offer. Two of the figures that would be most influential in arriving at an alternative had both worked on ARPANET and, in 1972, had both taken up new jobs.

Robert (Bob) Kahn had worked on ARPANET as part of BBN, leaving to join ARPA as a program manager. Vinton (Vint) Cerf had worked with the original IMP installation at UCLA and, upon completion of his doctorate, left to take up an assistant professorship at Stanford University.

Stanford University lies approximately half way between San Francisco and San Jose, at the heart of what became known as Silicon valley, and was another of the first four IMP sites. A very short distance away to the east and north is Palo Alto where two more ARPANET alumni were settling in. They were Robert (Bob) Taylor, who had been IPTO director at ARPA and who had hired Larry Roberts, and Robert Metcalfe who had worked on the installation of an IMP at Harvard as part of his doctoral programme. They were both employed at the Xerox Palo Alto Research Center (PARC). Taylor had moved there in 1970 and recruited Metcalfe in 1972 (Metcalfe 2006 - 2007).

PARC, in the 1970's, was a hotbed of innovation. Many of the things that we take for granted today started at PARC during those years: personal computers with windows, icons and mice, connected by a local area networks, with access to servers through gateways to packet switched networks. When Steve Jobs saw what they had to offer, in 1979, he is reported to have said "Why isn't Xerox marketing this? ... You could blow everybody away!" (Campbell-Kelly and Aspray 1996, 270). They didn't (wholeheartedly) and the probable explanation lies in Xerox's core business - copiers. Having risen from a start-up to a global corporation in the 1960s, a combination of hubris, complacency and loss of patent rights left them highly vulnerable to Japanese competition in the 1970s. In the 1980s, it was all hands to the wheel to save the core business from extinction (Kearns and Nadler 1993). The computer business was underinvested and the winner was Apple.

Metcalfe's role, in PARC, was to find a way to network the personal computers (Altos) together. He would find inspiration in Hawaii. Cerf and Kahn would need to include in their scheme of things the two networking technologies which emerged from Hawaii and Palo Alto.

Packet Radio and Ethernet. In 1968, Norm Abramson, of the University of Hawaii, decided to try and reduce the cost of researchers dialling in to the central computer from locations dispersed among the islands. His idea was to use radio, but emulating multiple users connecting over wired links, by allocating each a separate frequency band, was not a practical option at that time. He chose instead to transmit short packets of information over two shared channels, one in each direction (Gillies and Caillau 2000, 34). A device rather like one of ARPA's IMPs was to handle the traffic in and out of the computer. It was called Menehune after a local leprechaun-like character. Outgoing traffic could be managed in an orderly fashion and presented no problem but incoming traffic, which could be transmitted freely, was always in danger of collision with packets from other terminals. If a packet got through, the Menehune would acknowledge it but if a terminal received no acknowledgement it would send the packet again after a random interval of time had elapsed. The randomness was to try to avoid a second collision between the same two packets. The system worked well and started in 1971 - it was called ALOHANET. It was not difficult to persuade Larry Roberts to get involved with ALOHANET. In due course an IMP was installed in the University of Hawaii and ALOHANET became part of ARPANET.

Soon after joining PARC, Bob Metcalfe happened to read a paper by Abramson during a sleepless, jetlagged night in Washington DC, where he still had ARPA commitments (Metcalfe 2006 - 2007, 22). He persuaded his management to let him spend a month in Hawaii to find out more. When he returned, he resumed responsibility for networking the Altos. A project had been underway to build a "50 megabit per second version of the 50 kilobit per second ARPANET, with little tiny high speed packet switches". This solution resulted in "horrible rats' nests of cables" which Metcalfe found aesthetically displeasing and he resolved to build a "network that didn't have this centralized feature" (Metcalfe 2006 - 2007, 25).

Metcalfe's big idea was to have a single cable into which all the Altos would tap along its length. Such an arrangement is called a bus. Obviously this solution has the same limitations as a single radio channel and that is where Abramson's idea of random retransmission following collision came in. This was Ethernet.

TCP/IP. One of ARPA's unique features was the way in which it was "open to technical ideas from all directions" (Lukasic 2011). Larry Roberts had established the precedent - when he learned of the work of Paul Baran, at the RAND Institute, and Donald Davies, at the National Physical Laboratory (NPL) in the UK, he attempted to draw them into his project. Vint Cerf was to follow in this tradition. In 1974, when he and Bob Kahn published their paper on internetworking (Cerf and Kahn 1974)[2], the acknowledgements included Donald Davies and Roger Scantlebury, his colleague at NPL, Robert Metcalfe of PARC, Louis Pouzin of INRIA, Hubert Zimmerman, a former colleague of Pouzin and originator of the OSI seven layer model, and David Walden of BBN. Gérard Le Lann, of Pouzin's team, came to Stanford on sabbatical in 1974 and, says Cerf,

I remember Bob Metcalfe and Le Lann and I sort of lying down on the floor of the living room in my house in Palo Alto on this giant piece of paper, trying to sketch what the state diagrams were for these protocols (V. Cerf 2007, 14).

Later, Peter Kirstein and his team at University College London would also make significant contributions (Kirstein 2012). The 1974 paper contains most of the ideas that would eventually end up in TCP/IP. Initially the proposal involved a transmission control program (TCP) building on the NCP program in ARPANET - IP would be split out later. In TCP's case, however, it was to address the way in which two host processes would communicate across a diverse collection of linked networks. The notion of a gateway was introduced to translate the protocols of one network into those of the next. The gateway resembled a couple of mini-hosts back-to-back with some kind of translation facility in the middle.

Nowadays, it is more common to refer to gateways as routers although those from Internet Service Providers (ISPs), whose primary function is to connect the ISP's network to a home Ethernet network, may also come with other functions under the covers, such as a mini Ethernet network (hub) and a wireless gateway.

From the outset, it was clear that the basic unit of communication between the networks must be the packet. On the whole, networks did not include the facility to break down messages into packets, as ARPANET could (ARPANET also had a datagram interface) and the broadcast networks, like packet radio and Ethernet, were physically constrained to transmit packets (frames). Because of the different implementations to be found in networks, logically the only practical way to proceed was to treat the aggregate of the networks (Internet) as an unreliable datagram network where packets might or might not arrive at the destination host, with or without errors, in sequence or not.

The duties of breaking messages into packets and reassembling them, sequencing disordered packets, correcting transmission errors and controlling the flow of packets would all fall to TCP, regardless of what the constituent networks were able to contribute (Cerf and Kahn 1974, 4). The TCPs would also be responsible for multiplexing packets from different processes on the host. The contribution of the gateways would simply be to transform packets from one set of protocols to the next. If the packet size mandated by the source network was larger than that of the destination, the gateway would fragment the packets into smaller ones. Reassembly would be left to the destination TCP (Cerf and Kahn 1974, 3). TCP was beginning to look a lot like the station de transport of CYCLADES.

It was also recognised that, although it might be rare, packets might not arrive at their destination. In the case of network congestion, packets might simply be dropped. It was decided to adopt a positive acknowledgement system, like that in Ethernet, where after a certain time lapse, if the acknowledgement has not been received, the TCP would simply retransmit. The number of packets that could be sent without acknowledgement was to be specified by a "sliding window" technique (Cerf and Kahn 1974, 7) which, according to Cerf, "came straight out of discussions with Louis Pouzin and his people at INRIA" (V. Cerf 2007, 14).

The TCP specification was completed in late 1974 or early 1975 and coding started in Stanford, BBN and University College London. From then until 1978, "the protocol gets more and more refined" (Kahn 2006, 47). TCP remained a protocol which was connection-based, like NCP, but around the end of 1977 the need for a user datagram protocol (UDP) was recognised. Nowadays UDP might be appropriate for audio and video streaming. Vint Cerf recalls

IP was split out as you will remember and then layered on top of it was this user datagram protocol, it was split out to handle real time communications, which didn't necessarily benefit from the determination of TCP to retransmit, put things in order, get rid of duplicates and all this other stuff, because it introduced delay. So if you wanted to have a real-time stream where missing something was not as serious as failing to get the most recent stuff ... (V. Cerf 2007, 11)

So, in OSI terms, there were alternative host-host protocols, TCP and UDP, at the transport layer and a node-node protocol, IP, at the network layer.

     

This was the four layer Internet protocol which made its live debut on ARPANET. Fortunately unrestrained growth of ARPANET had not been encouraged - "When we did the TCP/IP conversion from NCP in January of 1983, there were only 400 computers in the network" (V. Cerf 2007, 18).

The Internet protocol layers are shown below with some well-known present-day protocols filling in the application and network access layers. The network access layers contains a variety of protocols including those for mobile phones, wireless and both local and wide area networks. There would need to be an implementation of the IP protocol for each. By the same token, each application would need to interface to TCP - that means submitting data for transmission to the TCP. File transfer (FTP), terminal access (Telnet) and mail (SMTP) had been developed by ARPA but the Web (HTTP) would come later.

An interesting footnote is provided by Cerf and Kahn's proposal for addressing in the 1974 paper. The address of a host was to consist of 8 bits of network address and that of the TCP ( host) within the network by 16 bits. This scheme would allow for 256 networks which, "seems sufficient for the foreseeable future", and 65,536 TCPs (about 17 million total) which "seems more than sufficient for a given network". The addresses were finally 32 bits and used the first 24 flexibly but by 2007 there were 500 million or more machines connected to the Internet and a new Internet protocol (version 6) was about to be implemented to cope with future growth (V. Cerf 2007, 18).

The success of the deployment on ARPANET demonstrated that TCP/IP worked but in order to enter the mainstream it would need to find its way into host computers as a preferred option. How this occurred is the subject of the next chapter.

Notes

1. Today the need for internetworking could not be clearer - an individual household is likely to accomodate ADSL, Ethernet, Wi-Fi and GPRS.

2. A more detailed account of internetworking issues is to be found in Cerf and Kirstein, 1978

Bibliography

Campbell-Kelly, Martin, and William Aspray. Computer: A History of the Information Machine. New York: BasicBooks, 1996.

Cerf, Vinton G, and Robert E Kahn. "A Protocol for Packet Network Intercommunication." IEEE Transactions on Communications 22, no. 5 (May 1974): 627-641.

Cerf, Vinton G, and Peter T Kirstein. "Issues in Packet-Network Interconnection." Proceedings of the IEEE 66, no. 11 (November 1978): 1386-1408.

Cerf, Vinton, interview by Donald Nielson. Oral History of Vinton (Vint) Cerf Mountain View, CA: Computer History Museum, (7 November 2007).

Gillies, James, and Robert Caillau. How the Web was Born: The Story of the World Wide Web. Oxford: Oxford University Press, 2000.

Kahn, Robert, interview by Vinton Cerf. Oral History of Robert Kahn Woodside, CA: Computer History Museum, (30 September 2006).

Kearns, David T, and David A Nadler. Prophets in the Dark: How Xerox Reinvented Itself and Beat Back the Japanese. Harpercollins, 1993.

Lukasic, Stephen J. "Why the ARPANET was Built." IEEE Annals of the History of Computing 33, no. 3 (July-September 2011): 4-21.

Metcalfe, Robert, interview by Len Shustek. Oral History of Robert Metcalfe Mountain View: Computer History Museum, (2006 - 2007).