Between Stanford and Cyclades, a transatlantic perspective on the creation of Internet

Date:
Changed on 12/11/2020
How did Arpanet become the Internet? What was the role of the Cyclades project and that of Stanford University in the creation of the Internet? This account is based on the experience and the vision "from the inside" of Gérard Le Lann, who was a member of both teams during the 1970s.

Arpanet 1961 - 1970: The early years

On 29 October 1969, the Arpanet gave its first signs of life, with the first characters sent between two computers. This was the outcome of works that had been funded since 1961 by the US Dpt. of Defense ARPA (Advanced Research Projects Agency), renamed DARPA in 1972. Founding principles (“packet switching”, “adaptive routing”, “store-and-forward”, etc.) appear in the Rand Corporation reports by Paul Baran (which were classified until 1964) and in the Leonard Kleinrock’s PhD thesis (MIT, 1961). Arpanet was built out of Interface Message Processors (IMP), which were the nodes in charge of packet switching and routing. Designed in the mid-1960s, IMPs were built by Bolt Beranek & Newman (BBN), an MIT spin-off.

In 1968, North American and British designers (Donald Davies, UK’s National Physical Lab (NPL) network), had decided on essential features: 

  • packets (also known as blocks and fragments, before being called datagrams, a name invented by Harold Bothner-By, a Norwegian engineer) for the IMP network; every equipment (“host”) was connected to the Arpanet via an IMP, which served as network entry and exit node,
  • messages, for the end-to-end transport level (between connected “hosts”),
  • message fragmentation and reassembly; an entry IMP would break down into packets every message received locally from one of its hosts; an exit IMP would reassemble all of the packets belonging to a given message, prior to delivery to the local destination host; the equivalent of a “virtual circuit” is established between these two IMPs; inside the IMP network, packets would circulate independently from each other, taking different routes if necessary (adaptive routing and “pure datagram” mode); packets arrive at an exit IMP in arbitrary order; packets could become lost or get repeated, and breakdowns in “virtual circuits” could occur,
  • end-to-end reliable and ordered message transport (end-to-end error and flow control); this was the role of the NCP protocol, run by the hosts in order to guarantee that (1) every message sent by E is correctly delivered in full to the intended recipient D, (2) a sequence of messages sent by E is correctly delivered in full and in the order in which they were sent to D, (3) E does not saturate D’s reception capacities; a major restriction of NCP, namely only one message in transit between E and D, would be eliminated with TCP, the successor to NCP.

Arpanet 1970-1972: The beginnings of the transition towards Internet

Various heterogeneous networks were connected to the Arpanet network. For example, in North America, PRNET (Packet Radio Network)—the world’s first packet-switching radio network, and the first Ethernet, from Xerox Parc (Palo Alto). Internationally, through satellite packet-switching links, the NPL network in the UK, via SatNet (implemented by R. Kahn and BBN) and the Norwegian network (the only IMP delivered outside the USA was installed in Oslo).

The goal was to experiment with solutions that would lead to the transition from Arpanet to Internet, as a federation of interconnected heterogeneous networks.

Internet 1972-1983: From birth to deployment

In addition to experiments involving connecting networks to the Arpanet, the transition from Arpanet to Internet was based on revisions and improvements made to its foundational concepts. This was a collective endeavour, conducted by the authors of the famous Request for Comments (RfC), memos from the International Network Working Group (INWG), and flagship publications which led to defining Internet’s core protocols.

It was Vint Cerf and Robert Kahn who wrote the seminal paper: “A Protocol for Packet Network Intercommunication”. This protocol was then modularised, leading to TCP (the Transmission Control Protocol) and UDP (the User Datagram Protocol) at the “transport” level and IP at the “network” level.

At its birth, Internet provided two types of services:

  • The TCP component, for the connection-oriented mode (no message losses, deliveries conformant to the sending order); this is the mode used for most standard services (messaging, file transfers, financial transactions, etc.); the “sliding window scheme”, described in Cerf-Kahn 1974, is the fundamental scheme for regulating message exchanges and for making them reliable (flow control, error control), as well as for speeding up transfer; multiple messages can be in transit between a sending host and a receiving host, thus eliminating propagation delays within networks that are crossed.
  • The IP component, for the connectionless mode, which does not guarantee reliable exchanges, possibly suitable for certain types of applications; those where it mandatory to respect the chronological ordering of messages sent but where losses can be tolerated necessarily include a mechanism for ensuring ordered deliveries which is equivalent to the TCP’s “sliding window scheme”.

The difference between a “packet” and its instantiation under the name “datagram” is quite simple:

  • A datagram is a “universal packet”, the format of which is understood by any network part of Internet
  • Rather than being performed by entry and exit IMPs, message fragmentation and reassembly are “moved up” to the transport level, and run by the hosts themselves.

Towards the end of the 1970s, competition intensified between proponents of TCP/IP and those in favour of alternative solutions, particularly those based on the ISO/OSI layered model and the EEC’s EIN and Euronet initiatives. As these alternative solutions became mired in lengthy international debates (ISO/OSI) and disagreements between France and the UK (EIN vs. Euronet), they were overtaken by DARPA, which threw its full weight behind the adoption of TCP/IP and Internet. On 1st January 1983 (“flag day”), all Arpanet sites (as well as “Arpanet-like” sites) replaced NCP with TCP/IP. In September 1984, the US Defense Communications Agency took the decision to separate Milnet from Arpanet for non-classified applications. This was the start of a successful career for Internet and TCP/IP, paving the way for the Web and a range of innovative companies (e.g. Cisco).

Just as the invention of the combustion engine led to the birth of the automobile industry and its big players, the invention of the Internet has been essential to the rise of the digital industry and its big players. By a curious “return to the future”, some of those giants are from now on partnering with the telecommunications industry, as the owners of submarine optical communications cables. Almost all intercontinental Internet traffic is funnelled through such cables, examples of which include the Marea cable (Facebook and Microsoft) between Virginia and Bilbao in Spain, with a capacity of 160 Terabits/s; and the Dunant cable (Google), between Virginia and Saint-Hilaire-de-Riez (Vendée), which has a capacity of 250 Terabits/s.

The contributions made by Cyclades to the birth of the Internet

The Cyclades project, hosted by IRIA, was launched in 1972, with Louis Pouzin at the helm. It was shut down in 1977 owing to a lack of use and visible technology transfer, despite the involvement of the CII (see Michel Elie’s account). When Cyclades was launched, the North Americans were approximately 10 years ahead, thanks to Arpanet. In a nutshell, this network was a copy of Arpanet, “adapted” to the technology available in France. Mitra-15 minicomputers would serve as IMPs, and Cyclades was connected to Arpanet via a standard telephone line belonging to the PTT (not based on packet-switching). Two contributions from the Cyclades project are referenced in the seminal 1974 paper (references 8 and 11).

Mitranet” (ref. 11) was the English name given to Cigale. Benefiting from the experience gained with Arpanet, this sub network of Cyclades was from the outset based on datagrams, as L. Pouzin himself explained during an interview with the SIF in 2015I had already [1972] opted for the datagram model, because I had studied the experiments carried out at the UK’s National Physical Lab and I was quite familiar with the ARPA's packet network. It was a virtual circuit service, but internally it functionned using datagrams.

cyclades
© Inria / Photo Studio 9
Left to right: Huber Zimmermann, Huber Germain, Ancré Danzin, Charles Hervé Cotten (DGT) and Jacques Maire.

The term closest to “datagram” to appear in a document jointly signed by Cyclades (“lettergram”) can be found in an INWG note with Hubert Zimmermann as a co-author. He never tried to get media attention. Unfortunately, he passed away too soon, before he could get the official recognition he deserves. The same can be said for Donald Davies.

The simulation work on the “sliding window” mechanism (ref. 8) conducted at the University of Rennes between 1972 and 1973 (IRISA was only created in 1975) focused on NCP and the first version of Cyclades’ STST protocol.

The simulation work carried out on NCP and STST helped to understand which were the causes of dysfunctions affecting these two protocols.That is why Gérard Le Lann was invited by Vint Cerf to join his team at Stanford University (1973-1974), where he contributed to the specification of the “sliding window” mechanism, a key component of TCP/IP. His name is listed among the pioneers of the Internet engraved on the “Birth of the Internet” plaque, which was unveiled at Stanford in 2005.

Regulation, reliability and speed of message exchanges between distant sites were central issues which had to be resolved for transitioning towards the Internet. The problems being faced were entirely new. In a nutshell: How to guarantee that asynchronous processes which communicate via channels entailing finite but unknown delays, or infinite delays, used simultaneously by multiple processes, in the presence of failures, always have the same vision of their global state. 

Nowadays, this class of problems is known under the name of “distributed consensus”, which has been a fundamental research area since the mid-1980s. In the general “distributed consensus” problem, one considers n processes, n > 1. In the TCP/IP case, n = 2. Numerous contemporary applications (e.g. distributed databases, clouds, blockchains or cryptocurrencies) rely on algorithms which ensure “distributed consensus”. Another relatively recent trend, called edge computing, was de facto initiated by “extracting” from the physical networks those functionalities which are now available with contemporary hosts (PCs, tablets and smartphones).

It is worth pointing out how quickly, in just two years (1972-1973), IRIA’s contributions were incorporated into the work which led to the transition from Arpanet to Internet.

A great opportunity missed

Parallel to the Cyclades project, the DGT (Direction Générale des Télécommunications) was experimenting with virtual circuits in the RCP project, led by Rémi Després at the CCETT in Rennes. I have always had a great relationship with Rémi Després. Coordinating the two projects would certainly have been fruitful. However, as explained by Philippe Picard who oversaw the launch of the Transpac network in 1978, (see his account) despite good initial intentions, a cooperation between the two projects proved impossible, for a number of reasons.

To conclude, the Internet is the outcome of a collective endeavour. It is worth recalling here the words of Leonard Kleinrock (UCLA), one of the most famous of these pioneers, about the subject of the “folks” involved in this fantastic adventure: “The Internet would have emerged even if none of those folks had ever been born!  It was “in the air” and awaiting the technology to catch up with the vision.”

At the age of 51, Internet has—once again—demonstrated its extraordinary robustness. Internet has been able to cope successfully with a 30% increase in traffic since the first wave of the Covid-19 pandemic.

To dig deeper:

[11] L. Pouzin, “Address format in Mitranet”, Note NIC 14497, INWG 20, Jan. 1973

[8] J.F. Chambon, M. Élie, J. Le Bihan, G. Le Lann, and H. Zimmerman, “Functional specification of the transmission station in the CYCLADES network -- The STST protocol” (in French), I.R.I.A. Tech. Rep. SCH502.3, May 1973.

Gérard Le Lann holds an Engineering Degree and a Ph.D in Computer Science. He started his career at CERN in 1969. In 1972, he joined IRIA (now Inria) as the first researcher seconded to the University of Rennes to set up a team for the Cyclades pilot project. Vint Cerf then invited him to join his team at Stanford University, where he took part in the specification of the TCP protocol. Gérard Le Lann was appointed research director in 1978 and swapped Rennes for Rocquencourt, where he has set up and directed multiple project teams. His research work (on distributed databases and systems; real-time embedded systems and local area networks; and proof-based system engineering) has led to approximately a hundred scientific publications, contracts, patents and industrial transfers (Digital Eqt Corp./USA, the French Navy, Arianespace, etc.). Currently a research director emeritus with Inria, he is working on critical cyber-physical systems and communicating autonomous vehicles, in partnership with a North American company