INWG and the conception of the Internet - Alex McKenzie

From IUWG
Revision as of 23:31, 14 March 2015 by Sysop (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

INWG and the Conception of the Internet: An Eyewitness Account

Alexander McKenzie

1972 was an exciting year in computer networking. The ARPANET, which came to life near the end of 1969, had grown to 29 nodes by August 1972. The National Physical Laboratory in England, under the direction of Donald Davies, had been running a 1-node packet switch interconnecting several NPL computers for several years. The French Research Laboratory IRIA, under the direction of Louis Pouzin, had begun the implementation of a packet-switched system called Cyclades.

In February 1972, Tymnet also issued the first invoice for network access services to the NLM of Bethesda.

In July 1972, three people associated with the ARPANET work at BBN formed a new company, Packet Communications, “to engage in the business of providing communication services for computer to terminal, computer to computer, [and] terminal to terminal information transfer.”1 In November 1971 the European Common Market announced the intention to build a European Informatics Network (EIN) for research and scientific purposes under the direction of Derek Barber from NPL, and planning was underway in 1972. Several national post, telephone, and telegraph (PTT) organizations were beginning to consider building national common-user data networks using packet-switching technology. These included the British Post Office’s Experimental Packet Switched System (EPSS), RCP (French PTT), and a small experimental packet-switched network (PSN) built by the Norwegian PTT during 1971 to 1972 and used for experiments for three months.



Formation of INWG

The people responsible for all these networks converged on the first International Conference on Computer Communication held in Washington D.C. during October 1972. There was a live demonstration of the ARPANET in a ballroom of the conference hotel, which created great excitement.2 And with a push from Larry Roberts of DARPA, a group of network designers met to talk about how all these networks could be interconnected. On 24 October, these designers met to form what they called the International Packet Network Working Group (INWG),3 modeled on the ARPANET NWG, and began the publication of a series of numbered INWG notes modeled on the ARPANET request for comments (RFCs). Larry Roberts volunteered to have the ARPANET Network Information Center (NIC) distribute the notes to INWG members.4 Vint Cerf volunteered to be temporary chairman/secretary. The group divided into two subgroups to consider “Communication System Requirements” and “HOST-HOST Protocol Requirements;” the reports of these subgroups are INWG 1 and INWG 2.

Subgroup 1 agreed that its job was as follows:

  1. To consider what requirements must be met by the packet switching networks to allow convenient communications between computers and terminals when that communication takes place through more than one network.
  2. To consider what recommendations to make on packet-switching networks, and how to provide for acceptance of these recommendations through CCITT and other international organizations […]5

Specific discussions included these questions:

  • Should a network provide a message service (such as ARPANET) or a packet-only service (such as Cyclades)?
  • Should a network provide an interface to a “host” computer, to a simple terminal, or both?
  • Can a packet size that could be handled by all “current” networks be required as “a lower limit for the maximum packet size of future networks” that wish to participate in interconnection?
  • Flow control has aspects that only apply to end-to-end operation and aspects that enable “a network … to protect itself against congestion.” How tightly coupled should these be?

Subgroup 2 agreed to review existing protocols6 by exchanging technical documents with the intent of meeting the following (ordered) set of objectives:

  1. Define which issues must be resolved by HOST-HOST protocol.7
  2. Select a design philosophy.
  3. Design the HOST-HOST protocol.
  4. Agree to implement the protocol design by a certain date.
  5. Make implementation recommendations.

During the next few months, INWG notes included documents from CCITT (study of “packet mode operation” during 1972–1976), Japan (link types), France (French PTT experimental packet network, congestion control, and addressing), UK (congestion control, NPL network documentation, and specifications for EPSS), and US (ARPANET throughput analysis and measurement and IMP flow control mechanisms). Particularly interesting was Pouzin’s observation in INWG 20 that a packet’s source and destination address is not identical to a “network interface address.” “Each communication software [must] be identified individually even if it is necessary to go through a common line or common computer to reach it.” This was a concept that was particularly misunderstood by the PTTs.


Internet Protocol Proposals

The second INWG meeting was held 7–8 June 1973 in New York in conjunction with the American Federation of Information Processing Societies (AFIPS) National Computer Conference. By this time, Pouzin had been instrumental in having INWG be chartered as Working Group 6.1 of the International Federation for Information Processing (IFIP) under Technical Committee (TC) 6, Data Transmission. [CLARIFICATION 2001/04/24 Both Pouzin and Alex Curran were involved. See http://www.historyofcomputercommunications.info/Book/6/6.4-TransmissionControlProtocol%28TCP%2973-76.html.] This sponsorship gave INWG (as IFIP WG 6.1) standing to participate directly in the deliberations of CCITT and ISO, providing technical input on packet networking. At the New York meeting, a small team of engineers8 with implementation experience in ARPANET (US), Cyclades (F), MERIT (US), and NPL (UK) created a first draft of an International Transmission Protocol (ITP). Vint Cerf served as the editor of this document, which was distributed as a set of supplements to INWG 28. An introduction stated:

If we treat the computer communication system of each network as a complicated communication line joining HOSTs and Gateway[s], then the Gateways appear to be international nodes9, joined by 2 or more networks, facilitating communication between HOSTs.

The international transmission protocol (ITP) described herein is intended to:

  1. Be resistant to failures in intermediate constituent networks and gateways.
  2. Be unaffected by the maximum message sizes permitted in constituent networks and by intra- and inter-network timing idiosyncrasies.
  3. Be capable of exactly reconstituting a message stream originating in a foreign HOST.
  4. Provide for high bandwidth and/or low delay transmission.
  5. Require no status information in gateways.
  6. Be relatively easy to implement.
  7. Permit the receiving HOST to control the flow from the sending HOST.

Messages are made up of a fixed length header, containing control and addressing information, an integral number of fixed length elements containing the text of the message, and space for an optional checksum.

It is imagined that between pairs of HOST computers, a single logical connexion is established upon which is multiplexed all communications between these two HOSTs.” A “Transmission Control Program (TCP) [is defined as a] program in a HOST computer which realizes the International Transmission Protocol enabling a collection of messages from processes and terminals associated with one HOST to be multiplexed along a connexion to another HOST in the same or foreign network. The TCP does not address itself to the problem of interprocess … communication. The job of the TCP is merely to take a stream of messages produced by one HOST and reproduce the stream at a foreign receiving HOST without change.

The draft specification described message format, including header fields for source address, destination address, left element ID (sequence number), bit count (of the text portion), element size (bits/element), acknowledgment (of traffic in the reverse direction), and type (user text, ITP control, or TCP status). It described a positive-acknowledgment, timeout, and retransmission scheme to insure reliable transmission, and a sliding window flow control scheme linked to the reliable transmission mechanism. It describes how a gateway can break a message received from a network with a large packet size into smaller pieces for transmission through a subsequent network with a smaller packet size without knowing anything about the message except for its header fields and checksum mechanism. It noted: “Clearly, it is necessary that all networks have the capability of sending a message consisting of the header, checksum, and one element.”

About a month later, Vint Cerf and Bob Kahn distributed INWG 39, which they described as “an attempt to collect and integrate the ideas uncovered at the June 1973 INWG meeting in New York, as well as some ideas which have been worked out since that time by various other people.”10 Gone was the concept that the “TCP does not address … interprocess communication.” Addresses now include a portion that specifies an individual process/port. Each port-to-port association was now separately flow- and error-controlled. Messages are divided into segments by the source TCP, and a checksum is computed for each segment. Gateways did not recompute checksums if they had to break up a segment and so each packet carried a flag field that specified the following:

  • This packet ends a source segment.
  • This segment ends a source message.
  • This message begins an association (synchronize on this sequence number).
  • This message ends an association (deallocate resources).

Because associations begin and end, there were some special problems selecting initial sequence numbers and acknowledging the data that arrives in the packet that ends an association. The “Type” field was omitted because the authors felt that the flag field specifies sufficient ITP control and TCP status information (although the flags are specific to an association).

In October, Pouzin distributed INWG 42, a tutorial titled “Interconnection of Packet Switching Networks” that detailed the concepts that were being discussed in INWG. This paper introduced the term catenet (from concatenated network), defined as “an abstract PSN resulting from the juxtaposition of several PSNs.” Pouzin's view of gateways was summed up in the following quote: “We come to the conclusion that users and gateways cannot assume anything about other networks [in the catenet] but the simplest possible properties. The reason is that the gateways cannot give to networks properties that they do not have. They can only screen out undesirable properties.”

In April 1974, Hubert Zimmermann and Michel Elie, both members of the Cyclades project, distributed INWG 61, titled “Standard Host/Host Protocol for Heterogeneous Computer Networks.” This proposal built on the ideas of INWG 28 and INWG 39, papers that had been circulated within INWG during the second half of 1973, an earlier proposal outline (INWG 43) that they published in November 1973, and the output of a January 1974 INWG meeting in Hawaii. The terminology of this paper differed from INWG 28/39, but the basic assumptions were the same. Both INWG 39 and INWG 61 provided for multiplexing several logical data streams, fragmentation and reassembly of long information units, retransmission and acknowledgment, and both feedback flow control and explicit flow control.

The major conceptual difference between the two proposals was in fragmentation and reassembly. INWG 39 assumed that each logical data stream could be viewed as a stream of 8-bit bytes (octets). The only restriction placed on an individual network regarding packet length was that it be at least long enough to carry the headers and checksum plus at least one octet of text. Hosts and gateways could fragment a message on any octet boundary. In contrast, INWG 61 assumed that every network could carry packets of at least 255 octets plus a “local network header” (if needed). Communication consisted of telegrams with 2 octets of data and letters of up to 128 fragments. All letter fragments (except perhaps the last) were the same length; when the length was combined with Internet headers and checksum there would be exactly 255 octets. The authors argued that fixed-length fragments would greatly simplify implementation. INWG 39 numbered individual octets for flow and error control; INWG 61 numbered letters (and fragments) for this purpose. Furthermore, INWG 61 made error and flow control options, which the application could choose for reliable transmission or omit for potentially lower delay. Finally, INWG 61 hosts were responsible for fragmentation, and no further fragmentation was required at gateways because all networks could carry a full fragment (by definition).

In May 1974, the IEEE Transactions on Communications published “A Protocol for Packet Network Interconnection” by Cerf and Kahn. This was a greatly updated and refined version of INWG 39.

INWG met again on 10–11 August 1974 in Stockholm. The meeting was attended by 32 people from 11 countries. It was reported that the protocol of INWG 61 was in the test stage, and the protocol of INWG 39 (updated) was in the detailed specification stage. It was also reported that plans were being made for experiments with the updated INWG 39 protocol at ARPA supported sites,11 and the INWG 61 protocol was being used for experiments between NPL and Cyclades using a Modula 1 computer at NPL as a gateway. Experiments with the INWG 61 protocol were being planned between Cyclades and EIN when EIN became operational in late 1975 or early 1976.

Synthesis of Competing Proposals

In December 1974 I proposed a synthesis of the two protocols.12 I wrote:

It might be argued that a synthesis of these protocols is counterproductive; that INWG should foster as many different protocol experiments as possible. In my view, however, there are almost no significant differences between the current formulations of these two ideas; thus independent experiments would produce little “light,” although possibly much heat. On the other hand, a synthesis of the two ideas has the potential for enlarging the community of experimenters, and thus increasing the probability of intensive study.

A single protocol design was also consistent with our original objectives, documented in INWG 2. The approach I took was to start with INWG 61, introduce a gateway fragmentation mechanism derived from INWG 39, and “discard any options proposed [in INWG 61] which complicate the gateway fragmentation mechanism without great compensating benefits.” I added the checksum option from INWG 39 and a time stamp field that had been proposed by Tomlinson13 to detect duplicate messages delivered extremely late by the catenet.

In May 1975, following an INWG meeting in Anaheim, California, where the three proposals (and various ideas for modifying them) were discussed, Pouzin and Cerf issued INWG 85 calling for a vote by mail on an End-To-End Protocol to be forwarded to standards bodies. They wrote: “discussions in the Anaheim meeting confirm that there is no major difficult in reaching now an agreement on a common E-E protocol. However, it is also apparent that such an agreement cannot be reached during a typical INWG meeting.” It called for a vote among “all complete proposals” that had been “submitted (in writing) by 1 September 1975.” It stated that only one vote would be accepted from each separate organization represented in the INWG membership, regardless of how many individuals from that organization participated in INWG work.

In July 1975, Cerf (representing INWG 39 and ARPA), Zimmermann (representing INWG 61 and Cyclades), Roger Scantlebury (representing NPL and EIN), and I (designated as output editor) met in London, agreeing to stay in session for as long as it took to produce a single proposal that INWG could vote on or reach the conclusion that we could not agree. In less than a week we had reached an agreement, which was documented in INWG 96.14 This proposal provided for an Internet header of 26 octets and a user text divided into fragments of 216 octets (which it noted to be a common multiple of machine word lengths of 8, 12, 16, 18, 24, 32, 36, and 64 bits­all of which were in use in some machine at that time). Address fields in the header provided for 32 bits of host address and 16 bits of process address. A letter could consist of up to 255 fragments (about 200,000 bits), and each letter carried a 16-bit sequence number for error control. Communication between application processes could be in either lettergram mode or liaison mode. Lettergram mode treated each letter independently (like a postal letter), with the possibility of requesting acknowledgment; Liaison mode treated the association as a bit stream (with the possibility of error and flow control) at the cost of carrying out initialization and termination exchanges of control information. Gateway fragmentation was possible if the source network allowed packets long enough to contain multiple fragments and the sender made use of that capability to send multifragment packets; all networks participating in the catenet were required to carry packets of at least 242 octets (a header plus one fragment).


Synthesis Approved, but Collaboraton Collapses

With the successful formulation of the INWG 96 proposal, the vote called in INWG 85 was changed to a simple yes/no on the question of submitting INWG 96 to CCITT and ISO as the IFIP recommendation for an international standard. A ballot, INWG 102, was circulated on 1 December 1975; returned ballots were required to be postmarked no later than 15 January 1976. The results of the balloting were announced in INWG 109. The vote was 25.8 in favor, 7.5 opposed, and 8.7 abstaining (several organizations internally divided their single vote among several active participants who didn’t agree). Derek Barber, who became INWG chair early in 1976, announced in INWG 111 that he was formally transmitting the accepted proposal to ISO and CCITT.

With the formal vote in favor of the INWG 96 protocol, it was expected that the various research groups within INWG would announce plans to convert to the common protocol and carry out their experiments with it. NPL and Cyclades, the two groups already carrying out internetwork tests, announced plans to convert immediately. EIN, still several months away from initial deployment, also announced their intention to use the INWG 96 protocol. But we were all shocked and amazed when Bob Kahn announced that DARPA researchers were too close to completing implementation of the updated INWG 39 protocol to incur the expense of switching to another design.15

As events proved, Kahn was wrong (or had other motives); the “final” TCP/IP specification was written in 1980 after at least four revisions.16 But whether he was right or wrong didn’t matter; DARPA had a bigger research budget than any of the other research organizations, and for this reason, its protocol choice became dominant over time.

INWG continued work on protocol design and formal specification for another 15 or 20 years17 and then disbanded around the time of the Internet explosion.


Reflections

History is not an experiment that can be run multiple times from different initial conditions, but I have often speculated about what might have been different if DARPA had chosen to adopt the INWG 96 proposal in early 1976.18 I once thought that if the research community were united behind one End-to-End Protocol, we might have avoided most or all of the incredibly wasteful ISO Open Systems Interconnection activity. However, the OSI effort was probably an inevitable clash between computer manufacturers and PTTs, and of both against IBM.19

I also once believed that the Internet might have exploded into the public consciousness five years earlier if European and US research groups had been cooperating. Maybe so, but there really had to be a number of other developments before the Internet explosion took place, including the transition of the US infrastructure from government-owned to privately-owned20 under the masterful direction of Steve Wolff of the US National Science Foundation21 with the funding championed by US Senator Al Gore;22 the widespread adoption of Unix23 as an “open” server OS, with free Internet software developed with DARPA funding;24 the widespread adoption of the personal computer for household use with free Internet software; the development of the hypertext linking protocols by Tim Berners-Lee25 and using the mouse26 for point-and-click computing; the development of a browser with a graphic user interface;27 and the development of a high-performance search engine.28 Once these developments occurred, the Internet explosion was assured, and until they occurred, it was impossible. Perhaps the only historical difference that would have occurred if DARPA had switched to the INWG 96 protocol is that rather than Cerf and Kahn being routinely cited as “fathers of the Internet,” maybe Cerf, Scantlebury, Zimmermann, and I would have been.


References and Notes

  1. Filing with the US Federal Communications Commission (FCC) to become licensed as a common carrier.
  2. K. Hafner & M. Lyon, Where Wizards Stay Up Late, Simon & Schuster, 1996, pp. 176–186.
  3. D. Barber (EIN, UK), B. Barker (BBN, US), V. Cerf (Stanford University, US), W. Clipsham (UK), D. Davies (NPL, UK), R. Despres (PTT, F), V. Detwiler (UBC, CA), F. Heart (BBN, US), A. McKenzie (BBN, US), L. Pouzin (IRIA, F), O. Riml (Bell-Northern Research, CA), K. Samuelson (Stockholm University), K. Sandum, B. Sexton (NPL, UK), P. Shanks (Post Office, UK), C.D. Shepard (Dept. of Communications, CA), J. Tucker (Logica, UK), and B. Wessler (ARPA, US).
  4. This was before online documentation; INWG notes were distributed on paper. To preserve the historical record and make it available to the public, I donated my almost-complete set of INWG notes to the Charles Babbage Institute at the University of Minnesota, Minneapolis, in 1996 when I retired. I used that collection to research this article.
  5. CCITT stands for International Consultative Committee on Telephone and Telegraph. This is an arm of the United Nations and the coordinating body of telecommunications companies. In most countries telephone and data communications are provided by a government monopoly, and therefore governments are members of CCITT; in the US the State Department is the official member body. A few international technical organizations for example, the International Standards Organization are also members.
  6. Specifically noted were the Walden Message-Switching Protocol, ARPA H-H Protocol, NPL High-Level Protocol, CYCLADES Protocol, and EPSS Protocol.
  7. “E.g. flow control; error detection and handling; retransmission and acknowledgment mechanisms; ways to determine current state of process at ‘other’ end of the conversation; message sequencing; synchronization; addressing problems.”
  8. E. Aupperle, V. Cerf, B. Kahn, A. McKenzie, R. Metcalfe, R. Scantlebury, D. Walden, and H. Zimmermann [CORRECTION 2011/04/24: According to recent private correspondence, Kahn did not attend this meeting.]
  9. The reference to “international nodes” reflects the unstated view that each network would be national in scope, with the implication that each nation would have one (or at most a few) networks. This was certainly the CCITT worldview.
  10. They specifically mention that “G. Grossman and G. LeLann made contributions after that meeting.”
  11. University College London, Bolt Beranek and Newman, and Stanford University
  12. INWG 74, “Internetwork Host-to-Host Protocol
  13. R. Tomlinson, well known as the creator of network email, in INWG Protocol note 2 (a separate series of INWG notes), Sept. 1974
  14. Also published in ACM SIGCOMM’s Computer Comm. Rev., vol. 6, no. 1, 1976.
  15. Ironically, in response to a question about changing the Internet architecture at his Turing Lecture in Aug. 2005, Bob said “changing that is much more difficult now, with all of those investments, than it would have been 20 or 30 years ago when basically it was just a big research experiment.” http://www.acm.org/sigcomm/sigcomm2005/webcast.html
  16. RFC 760, also published as Internet Experiment Note (IEN) 128, available online at http://www.faqs.org/rfcs/
  17. I became chair after D. Barber, and C. Sunshine followed me as chair.
  18. It clearly would not have made any difference to the CCITT’s adoption of X.25 in Aug. 1976.
  19. J. Day, Patterns in Network Architecture, Prentice Hall, 2007, pp. 355–358
  20. J. Abbate, “Privatizing the Internet: Competing Visions and Chaotic Events, 1987–1995,” IEEE Annals of the History of Computing, vol. 32, no. 1, 2010, pp. 10–22.
  21. In the face of widespread misunderstanding, and mistrust, of his vision by almost everyone, including me.
  22. Senator Gore created and introduced the High Performance Computing and Communication Act of 1991 (HPCA), which was instrumental in the NSF efforts to make the Internet available “everywhere.”
  23. Unix was created by K. Thompson, D. Ritchie, M.D. Mcllroy, and J. Ossanna at Bell Labs.
  24. The Berkeley System Distribution (BSD) version of Unix was heavily supported by DARPA.
  25. Hypertext was probably invented independently by T. Nelson at Brown University and D. Englebart at Stanford Research Inst., but Berners-Lee deserves credit for developing a network-based version.
  26. Invented by D. Englebart, championed by Xerox PARC, and popularized by the Apple Macintosh.
  27. Mosaic, developed by Marc Andreessen and Eric Bina at the National Center for Supercomputer Applications at the Univ. of Illinois funded by the Gore Bill.
  28. AltaVista, developed by Louis Monier and Michael Burrows at Digital Equipment Corporation's Western Research Laboratory.