Protocol Wars

In the late 1960s and early 1970s, the pioneers of packet switching technology built computer networks providing data communication, that is the ability to transfer data between points or nodes. As more of these networks emerged in the mid to late 1970s, the debate about communication protocols became a "battle for access standards". An international collaboration between several national postal, telegraph and telephone (PTT) providers and commercial operators led to the X.25 standard in 1976, which was adopted on public data networks providing global coverage. Separately, proprietary data communication protocols emerged, most notably IBM's Systems Network Architecture in 1974 and Digital Equipment Corporation's DECnet in 1975.

The United States Department of Defense (DoD) developed TCP/IP during the 1970s in collaboration with universities and researchers in the US, UK, and France. Internet Protocol version 4 (IPv4) was released in 1981 and was made the standard for all DoD computer networking. By 1984, the international reference model OSI model, which was not compatible with TCP/IP, had been agreed upon. Many European governments (particularly France, West Germany, and the UK) and the United States Department of Commerce mandated compliance with the OSI model, while the US Department of Defense planned to transition from TCP/IP to OSI.

Meanwhile, the development of a complete Internet protocol suite by 1989, and partnerships with the telecommunication and computer industry to incorporate TCP/IP software into various operating systems, laid the foundation for the widespread adoption of TCP/IP as a comprehensive protocol suite. While OSI developed its networking standards in the late 1980s, TCP/IP came into widespread use on multi-vendor networks for internetworking and as the core component of the emerging Internet.

Early computer networking

Packet switching vs circuit switching

Computer science was an emerging discipline in the late 1950s that began to consider time-sharing between computer users and, later, the possibility of achieving this over wide area networks. In the early 1960s, J. C. R. Licklider proposed the idea of a universal computer network while working at Bolt Beranek & Newman (BBN) and, later, leading the Information Processing Techniques Office (IPTO) at the Advanced Research Projects Agency (ARPA, later, DARPA) of the US Department of Defense (DoD). Independently, Paul Baran at RAND in the US and Donald Davies at the National Physical Laboratory (NPL) in the UK invented new approaches to the design of computer networks.

Baran published a series of papers between 1960 and 1964 about dividing information into "message blocks" and dynamically routing them over distributed networks. Davies conceived of and named the concept of packet switching using high-speed interface computers for data communication in 1965–1966. He proposed a national commercial data network in the UK, and designed the local-area NPL network to demonstrate and research his ideas. The first use of the term protocol in a modern data-communication context occurs in an April 1967 memorandum A Protocol for Use in the NPL Data Communications Network written by two members of Davies' team, Roger Scantlebury and Keith Bartlett.

Licklider, Baran, and Davies all found it hard to convince incumbent telephone companies of the merits of their ideas. AT&T held a monopoly on communication infrastructure in the United States, as did the General Post Office (GPO) in the United Kingdom, which was the national postal, telegraph and telephone service (PTT). They both believed speech traffic would continue to dominate and continued to invest in traditional telegraphic techniques. Telephone companies were operating on the basis of circuit switching, alternatives to which are message switching or packet switching.

Bob Taylor became the director of the IPTO in 1966 and set out to achieve Licklider's vision to enable resource sharing between remote computers. Taylor hired Larry Roberts to manage the programme. Roberts brought Leonard Kleinrock into the project; Kleinrock had applied mathematical methods to study communication networks in his doctoral thesis. At the October 1967 Symposium on Operating Systems Principles, Roberts presented the early "ARPA Net" proposal, based on Wesley Clark's idea for a message switching network using Interface Message Processors (IMPs). Roger Scantlebury presented Davies' work on a digital communication network and referenced the work of Paul Baran. At this seminal meeting, the NPL paper articulated how the data communication for such a resource-sharing network could be implemented.

Larry Roberts incorporated Davies' and Baran's ideas on packet switching into the proposal for the ARPANET. The network was built by BBN. Designed principally by Bob Kahn, it departed from the NPL's connectionless network model in an attempt to avoid the problem of network congestion. The service offered to hosts by the network was connection oriented. It enforced flow control and error control (although this was not end-to-end). With the constraint that, for each connection, only one message may be in transit in the network, the sequential order of messages is preserved end-to-end. This made the ARPANET what would come to be called a virtual circuit network.

Datagrams vs virtual circuits

Packet switching can be based on either a connectionless or connection-oriented mode, which are different approaches to data communication. A connectionless datagram service transports data packets between two hosts independently of any other packet. Its service is best effort (meaning out-of-order packet delivery and data losses are possible). With a virtual circuit service, data can be exchanged between two host applications only after a virtual circuit has been established between them in the network. After that, flow control is imposed to sources, as much as needed by destinations and intermediate network nodes. Data are delivered to destinations in their original sequential order.

Both concepts have advantages and disadvantages depending on their application domain. Where a best effort service is acceptable, an important advantage of datagrams is that a subnetwork may be kept very simple. A counterpart is that, under heavy traffic, no subnetwork is per se protected against congestion collapse. In addition, for users of the best effort service, use of network resources does not enforce any definition of "fairness"; that is, relative delay among user classes.

Datagram services include the information needed for looking up the next link in the network in every packet. In these systems, routers examine each arriving packet, look at their routing information, and decide where to route it. This approach has the advantage that there is no inherent overhead in setting up the circuit, meaning that a single packet can be transmitted as efficiently as a long stream. Generally, this makes routing around problems simpler as only the single routing table needs to be updated, not the information for every virtual circuit. It also requires less memory, as only one route needs to be stored for any destination, not one per virtual circuit. On the downside, there is a need to examine every datagram, which makes them (theoretically) slower.

On the ARPANET, the starting point in 1969 for connecting a host computer (i.e., a user) to an IMP (i.e., a packet switch) was the 1822 protocol, which was written by Bob Kahn. Steve Crocker, a graduate student at the University of California Los Angeles (UCLA) formed a Network Working Group (NWG) that year. He said "While much of the development proceeded according to a grand plan, the design of the protocols and the creation of the RFCs was largely accidental." Under the auspices of Leonard Kleinrock at UCLA, Crocker led other graduate students, including Jon Postel, in designing a host-host protocol known as the Network Control Program (NCP). They planned to use separate protocols, Telnet and the File Transfer Protocol (FTP), to run functions across the ARPANET. After approval by Barry Wessler at ARPA, who had ordered certain more exotic elements to be dropped, the NCP was finalized and deployed in December 1970 by the NWG. NCP codified the ARPANET network interface, making it easier to establish, and enabling more sites to join the network.

Roger Scantlebury was seconded from the NPL to the British Post Office Telecommunications division (BPO-T) in 1969. There, engineers developed a packet-switching protocol from basic principles for an Experimental Packet Switched Service (EPSS) based on a virtual call capability. However, the protocols were complex and limited; Davies described them as "esoteric".

Rémi Després started work in 1971, at the CNET (the research center of the French PTT), on the development of an experimental packet switching network, later known as RCP. Its purpose was to put into operation a prototype packet switching service to be offered on a future public data network. Després simplified and improved on the virtual call approach, introducing the concept of "graceful saturated operation" in 1972. He coined the term "virtual circuit" and validated the concepts on the RCP network. Once set up, the data packets do not have to contain any routing information, which can simplify the packet structure and improve channel efficiency. The routers are also faster as the route setup is only done once; from then on, packets are simply forwarded down the existing link. One downside is that the equipment has to be more complex as the routing information has to be stored for the length of the connection. Another disadvantage is that the virtual connection may take some time to set up end-to-end, and for small messages, this time may be significant.

TCP vs CYCLADES and INWG vs X.25

Davies had conceived and described datagram networks, done simulation work on them, and built a single packet switch with local lines. Louis Pouzin thought it looked technically feasible to employ a simpler approach to wide-area networking than that of the ARPANET. In 1972, Pouzin launched the CYCLADES project, with cooperation provided by the French PTT, including free lines and modems. He began to research what would later be called internetworking; at the time, he coined the term "catenet" for concatenated network. The name "datagram" was coined by Halvor Bothner-By. Hubert Zimmermann was one of Pouzin's principal researchers and the team included Michel Elie and Gérard Le Lann, among others. While building the network, they were advised by BBN as consultants. Pouzin's team was the first to tackle the highly-complex problem of providing user applications with a reliable virtual circuit while using a best-effort service. The network used unreliable, standard-sized, datagrams in the packet-switched network and virtual circuits for the transport layer. First demonstrated in 1973, it pioneered the use of the datagram model, functional layering, and the end-to-end principle. Le Lann proposed the sliding window scheme for achieving reliable error and flow control on end-to-end connections. However, the sliding window scheme was never implemented on the CYCLADES network and it was never interconnected with other networks (except for limited demonstrations using traditional telegraphic techniques).

Louis Pouzin's ideas to facilitate large-scale internetworking caught the attention of ARPA researchers through the International Network Working Group (INWG), an informal group established by Steve Crocker, Pouzin, Davies, and Peter Kirstein in June 1972 in Paris, a few months before the International Conference on Computer Communication (ICCC) in Washington demonstrated the ARPANET. At the ICCC, Pouzin first presented his ideas on internetworking, and Vint Cerf was approved as INWG's Chair on Steve Crocker's recommendation. INWG grew to include other American researchers, members of the French CYCLADES and RCP projects, and the British teams working on the NPL network, EPSS and the proposed European Informatics Network (EIN), a datagram network. Like Baran in the mid-1960s, when Roberts approached AT&T about taking over the ARPANET to offer a public packet-switched service, they declined.

Bob Kahn joined the IPTO in late 1972. Although initially expecting to work in another field, he began work on satellite packet networks and ground-based radio packet networks, and recognized the value of being able to communicate across both. In Spring 1973, Vint Cerf moved to Stanford University. With funding from DARPA, he began collaborating with Kahn on a new protocol to replace NCP and enable internetworking. Cerf built a research team at Stanford studying the use of fragmentable datagrams. Gérard Le Lann joined the team during the period 1973-4 and Cerf incorporated his sliding windows scheme into the research work.

Also in the United States, Bob Metcalfe and others at Xerox PARC outlined the idea of Ethernet and the PARC Universal Packet (PUP) for internetworking. INWG met in Stanford in June 1973. Zimmermann and Metcalfe dominated the discussions. Notes from the meetings were recorded by Cerf and Alex McKenzie, from BBN, and published as numbered INWG Notes (some of which were also RfCs). Building on this, Kahn and Cerf presented a paper at a networking conference at the University of Sussex in England in September 1973. Their ideas were refined further in long discussions with Davies, Scantlebury, Pouzin and Zimmerman. Most of the work was done by Kahn and Cerf working as a duet.

Peter Kirstein put internetworking into practice at University College London (UCL) in June 1973, connecting the ARPANET to British academic networks, the first international heterogeneous computer network. By 1975, there were 40 British academic and research groups using the link.

The seminal paper, A Protocol for Packet Network Intercommunication, published by Cerf and Kahn in 1974 addressed the fundamental challenges involved in interworking across datagram networks with different characteristics, including routing in interconnected networks, and packet fragmentation and reassembly. The paper drew upon and extended their prior research, developed in collaboration and competition with other American, British and French researchers. DARPA sponsored work to formulate the first version of the Transmission Control Program (TCP) later that year. At Stanford, its specification, RFC 675, was written in December by Cerf with Yogen Dalal and Carl Sunshine as a monolithic (single layer) design. The following year, testing began through concurrent implementations at Stanford, BBN and University College London, but it was not installed on the ARPANET at this time.

A protocol for internetworking was also being pursued by INWG. There were two competing proposals, one based on the early Transmission Control Program proposed by Cerf and Kahn (using fragmentable datagrams), and the other based on the CYCLADES transport protocol proposed by Pouzin, Zimmermann and Elie (using standard-sized datagrams). A compromise was agreed and Cerf, McKenzie, Scantlebury and Zimmermann authored an "international" end-to-end protocol. It was presented to the CCITT by Derek Barber in 1975 but was not adopted by the CCITT nor by the ARPANET.

The fourth biennial Data Communications Symposium later that year included presentations from Davies, Pouzin, Derek Barber, and Ira Cotten about the current state of packet-switched networking. The conference was covered by Computerworld magazine which ran a story on the "battle for access standards" between datagrams and virtual circuits, as well as a piece describing the "lack of standard access interfaces for emerging public packet-switched communication networks is creating 'some kind of monster' for users". At the conference, Pouzin said pressure from European PTTs forced the Canadian DATAPAC network to change from a datagram to virtual circuit approach, although historians attribute this to IBM's rejection of their request for modification to their proprietary protocol. Pouzin was outspoken in his advocacy for datagrams and attacks on virtual circuits and monopolies. He spoke about the "political significance of the [datagram versus virtual circuit] controversy," which he saw as "initial ambushes in a power struggle between carriers and the computer industry. Everyone knows in the end, it means IBM vs. Telecommunications, through mercenaries."

After Larry Roberts and Barry Wessler left ARPA in 1973 to found Telenet, a commercial packet-switched network in the US, they joined the international effort to standardize a protocol for packet switching based on virtual circuits shortly before it was finalized. With contributions from the French, British, and Japanese PTTs, particularly the work of Rémi Després on RCP and TRANSPAC, along with concepts from DATAPAC in Canada, and Telenet in the US, the X.25 standard was agreed by the CCITT in 1976. X.25 virtual circuits were easily marketed because they permit simple host protocol support. They also satisfy the INWG expectation of 1972 that each subnetwork can exercise its own protection against congestion (a feature missing with datagrams).

Larry Roberts adopted X.25 on Telenet and found that "datagram packets are now more expensive than VC packets" in 1978. Vint Cerf said Roberts turned down his suggestion to use TCP when he built Telenet, saying that people would only buy virtual circuits and he could not sell datagrams. Roberts predicted that "As part of the continuing evolution of packet switching, controversial issues are sure to arise." Pouzin remarked that "the PTT's are just trying to drum up more business for themselves by forcing you to take more service than you need."

Common host protocol vs translating between protocols

Internetworking protocols were still in their infancy. Various groups, including ARPA researchers, the CYCLADES team, and others participating in INWG, were researching the issues involved, including the use of gateways to connect between two networks. At the National Physical Laboratory in the UK, Davies' team studied the "basic dilemma" involved in interconnecting networks: a common host protocol requires restructuring existing networks that use different protocols. To explore this dilemma, the NPL network connected with the EIN by translating between two different host protocols, that is, using a gateway. Concurrently, the NPL connection to the EPSS used a common host protocol in both networks. NPL research confirmed establishing a common host protocol would be more reliable and efficient.

The CYCLADES project, however, was shut down in the late 1970s for budgetary, political and industrial reasons and Pouzin was "banished from the field he had inspired and helped to create".

DoD model vs X.25/X.75 vs proprietary standards

The design of the Transmission Control Program incorporated both connection-oriented links and datagram services between hosts. A DARPA internetworking experiment in July 1977 linking the ARPANET, SATNET and PRNET demonstrated its viability. Subsequently, DARPA and collaborating researchers at Stanford, UCL and BBN, among others, began work on the Internet, publishing a series of Internet Experiment Notes. Bob Kahn's efforts led to the absorption of MIT's proposal by Dave Clark and Dave Reed for a Data Stream Protocol (DSP) into version 3 of TCP in January 1978 written by Cerf, now at DARPA, and Jon Postel at the Information Sciences Institute of the University of Southern California (USC). Following discussions with Yogen Dalal, Bob Metcalfe and John Shoch at Xerox PARC, in Version 4 of TCP, first drafted in September 1978, Postel split the Transmission Control Program into two distinct protocols, the Transmission Control Protocol (TCP) as a reliable connection-oriented service and the Internet Protocol (IP) as connectionless service. For applications that did not want the services of TCP, an alternative called the User Datagram Protocol (UDP) was added in order to provide direct access to the basic service of IP. Referred to as TCP/IP from December 1978, Version 4 was made standard for all military computer networking in March 1982. It was installed on SATNET and adopted by NORSAR/NDRE in March and Peter Kirstein's group at UCL in November. On January 1, 1983, known as "flag day", TCP/IP was installed on the ARPANET. This resulted in a networking model that became known as the DoD internet architecture model (DoD model for short) or DARPA model.

The Coloured Book protocols, developed by British Post Office Telecommunications and the academic community at UK universities, gained some acceptance internationally as the first complete X.25 standard. First defined in 1975, they gave the UK "several years lead over other countries" but were intended as "interim standards" until international agreement was reached. The X.25 standard gained political support in European countries and from the European Economic Community (EEC). The EIN, which was based on datagrams, was replaced with Euronet, which used X.25. Peter Kirstein wrote that European networks tended to be short-term projects with smaller numbers of computers and users. As a result, the European networking activities did not lead to any strong standards except X.25, which became the main European data protocol for fifteen to twenty years. Kirstein said his group at University College London was widely involved, partly because they were one of the groups with the most expertise, and partly to try to ensure that the British activities, such as the JANET NRS, did not diverge too far from the US. The construction of public data networks based on the X.25 protocol suite continued through the 1980s; international examples included the International Packet Switched Service (IPSS) and the SITA network. Complemented by the X.75 standard, which enabled internetworking across national PTT networks in Europe and commercial networks in North America, this led to a global infrastructure for commercial data transport.

Computer manufacturers developed proprietary protocol suites such as IBM's Systems Network Architecture (SNA), Digital Equipment Corporation's (DEC's) DECnet, Xerox's Xerox Network Systems (XNS, based on PUP) and Burroughs' BNA. By the end of the 1970s, IBM's networking activities were, by some measures, two orders of magnitude larger in scale than the ARPANET. During the late 1970s and most of the 1980s, there remained a lack of open networking options. Therefore, proprietary standards, particularly SNA and DECnet, as well as some variants of XNS (e.g., Novell NetWare and Banyan VINES), were commonly used on private networks, becoming somewhat "de facto" industry standards. Ethernet, promoted by DEC, Intel, and Xerox, outcompeted MAP/TOP, promoted by General Motors and Boeing. DEC was an exception among the computer manufactures in supporting the peer-to-peer approach.

In the US, the National Science Foundation (NSF), NASA, and the United States Department of Energy (DoE) all built networks variously based on the DoD model, DECnet, and IP over X.25.