Invention and development . The concept of switching small blocks of data was invented independently by
Paul Baran at the
RAND Corporation during the early 1960s in the US and
Donald Davies at the
National Physical Laboratory (NPL) in the UK in 1965. In the late 1950s, the
US Air Force established a
wide area network for the
Semi-Automatic Ground Environment (SAGE) radar defense system. Recognizing vulnerabilities in this network, the Air Force sought a system that might survive a
nuclear attack to enable a response, thus diminishing the attractiveness of the first strike advantage by enemies (see
Mutual assured destruction). In the early 1960s, Baran invented the concept of
distributed adaptive message block switching in support of the Air Force initiative. The concept was first presented to the Air Force in the summer of 1961 as briefing B-265, later published as RAND report P-2626 in 1962, and finally in report RM 3420 in 1964. The reports describe a general architecture for a large-scale, distributed, survivable communications network. The proposal was composed of three key ideas: use of a
decentralized network with multiple paths between any two points; dividing user messages into
message blocks; and delivery of these messages by
store and forward switching. Baran's network design was focused on high-speed
digital communication of voice messages using hardware switches that were low-cost electronics.
Christopher Strachey, who became
Oxford University's first Professor of Computation, filed a
patent application in the United Kingdom for
time-sharing in February 1959. In June that year, he gave a paper "Time Sharing in Large Fast Computers" at the
UNESCO Information Processing Conference in Paris where he passed the concept on to
J. C. R. Licklider. Licklider (along with
John McCarthy) was instrumental in the development of time-sharing. After conversations with Licklider about time-sharing with remote computers in 1965, Davies independently invented a similar
data communication concept. His insight was to use short messages in fixed format with high data transmission rates to achieve rapid communications. He went on to develop a design for a hierarchical, high-speed
computer network including
interface computers and
communication protocols. He gave a talk on the proposal in 1966, after which a person from the
Ministry of Defence (MoD) told him about Baran's work.
Roger Scantlebury, a member of Davies' team, presented their work (and referenced that of Baran) at the October 1967
Symposium on Operating Systems Principles (SOSP). At the conference, Scantlebury proposed packet switching for use in the
ARPANET and persuaded
Larry Roberts the economics were favorable to
message switching. Davies had chosen some of the same parameters for his original network design as did Baran, such as a packet size of 1024 bits. To deal with packet permutations (due to dynamically updated route preferences) and
datagram losses (unavoidable when fast sources send to a slow destination), he assumed that "all users of the network will provide themselves with some kind of error control", the
NPL Data Communications Network began service in 1970. Davies was invited to Japan to give a series of lectures on packet switching. The NPL team carried out
simulation work on datagrams and
congestion in networks on a scale to provide data communication across the United Kingdom.
Larry Roberts made the key decisions in the
request for proposal to build the
ARPANET. Roberts met Baran in February 1967, but did not discuss networks. He asked
Frank Westervelt to explore the questions of message size and contents for the network, and to 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." Roberts revised his initial design, which was to connect the
host computers directly, to incorporate
Wesley Clark's idea to use
Interface Message Processors (IMPs) to create a
message switching network, which he presented at SOSP. Roberts was known for making decisions quickly. Immediately after SOSP, he incorporated Davies' concepts and designs for packet switching to enable the data communications on the network, and sought input from Baran. A contemporary of Roberts' from
MIT,
Leonard Kleinrock had researched the application of
queueing theory in the field of
message switching for his doctoral dissertation in 1961–62 and published it as a book in 1964. Davies, in his 1966 paper on packet switching, This addressed a key question about the viability of computer networking. Larry Roberts brought Kleinrock into the ARPANET project informally in early 1967. Roberts and Taylor recognized the issue of response time was important, but did not apply Kleinrock's methods to assess this and based their design on a
store-and-forward system that was not intended for
real-time computing. After SOSP, and after Roberts' direction to use packet switching, The ARPANET working group assigned Kleinrock responsibility to prepare a report on software for the IMP. In 1968, Roberts awarded Kleinrock a contract to establish a Network Measurement Center (NMC) at
UCLA to measure and model the performance of packet switching in the ARPANET. it was the first wide-area packet-switched network with distributed control. The UCLA NMC and the BBN team also investigated network congestion. The Network Working Group, led by
Steve Crocker, a graduate student of Kleinrock's at UCLA, developed the host-to-host protocol, the
Network Control Program, which was approved by Barry Wessler for ARPA, after he ordered certain more exotic elements to be dropped. In 1970, Kleinrock extended his earlier
analytic work on message switching to packet switching in the ARPANET. The ARPANET was demonstrated at the
International Conference on Computer Communication (ICCC) in Washington in October 1972. However, fundamental questions about the design of packet-switched networks remained. Roberts presented the idea of packet switching to communication industry professionals in the early 1970s. Before ARPANET was operating, they argued that the router buffers would quickly run out. After the ARPANET was operating, they argued that packet switching would never be economic without the government subsidy. Baran had faced the same rejection and thus failed to convince the military to construct a packet switching network in the 1960s. It was the first to implement the end-to-end principle of Davies, and make the host computers responsible for the reliable delivery of data on a packet-switched network, rather than this being a service of the network itself. His team was thus first to tackle the highly-complex problem of providing user applications with a reliable
virtual circuit service while using a
best-effort service, an early contribution to what will be the
Transmission Control Protocol (TCP).
Bob Metcalfe and others at
Xerox PARC outlined the idea of
Ethernet and the
PARC Universal Packet (PUP) for internetworking. In May 1974,
Vint Cerf and
Bob Kahn described the
Transmission Control Program, an internetworking
protocol for sharing resources using packet-switching among the nodes. The specifications of the TCP were then published in (
Specification of Internet Transmission Control Program), written by Vint Cerf,
Yogen Dalal and Carl Sunshine in December 1974. The
X.25 protocol, developed by
Rémi Després and others, was built on the concept of
virtual circuits. In the mid-late 1970s and early 1980s, national and international
public data networks emerged using X.25 which was developed with participation from France, the UK, Japan, USA and Canada. It was complemented with
X.75 to enable internetworking. In the late 1970s, the monolithic Transmission Control Program was layered as the Transmission Control Protocol (TCP), atop the
Internet Protocol (IP). Many
Internet pioneers developed this into the
Internet protocol suite and the associated Internet architecture and governance that emerged in the 1980s. Leonard Kleinrock carried out theoretical work at UCLA during the 1970s analyzing throughput and delay in the ARPANET. Kleinrock published hundreds of research papers, which ultimately launched a new field of research on the theory and application of queuing theory to computer networks. His work on
hierarchical routing with student
Farouk Kamoun became critical to the operation of the Internet. Packet switching was shown to be optimal in the
Huffman coding sense in 1978. For a period in the 1980s and early 1990s, the network engineering community was polarized over the implementation of competing protocol suites, commonly known as the
Protocol Wars. It was unclear which of the Internet protocol suite and the
OSI model would result in the best and most robust computer networks. Complementary
metal–oxide–semiconductor (
CMOS)
VLSI (very-
large-scale integration) technology led to the development of high-speed
broadband packet switching during the 1980s1990s.
The "paternity dispute" In the 1978 special edition of the
Proceedings of the IEEE on packet switching, Bob Kahn, the guest editor, wrote that "analysis has had little direct impact on the network design problem". In Roberts' paper on "Packet Switching Economics" for the L.M. Ericsson prize for research in data communications in 1982, he referenced only Davies' 1967 paper for SOSP, not the work of Baran or Kleinrock. Kleinrock's paper for the same prize was titled "Packet Switching Principles". In Roberts' 1986 conference paper on "The ARPANET & Computer Networks", he also cites Baran's 1964 paper and one of his own papers from 1966; but only references Kleinrock's work from the 1970s, which addressed the ARPANET. This paper was republished on the web by Roberts in 1995. Roberts began to claim, in the late 1990s, that, by the time of the October 1967 SOSP, he already had the concept of packet switching in mind (although not yet named and not written down in his paper published at the conference, which a number of sources describe as "vague"), and that this originated with his old colleague, Kleinrock, who had written about such concepts in his Ph.D. research in 1961-2. In 1997, along with seven other
Internet pioneers, Roberts and Kleinrock co-wrote "Brief History of the Internet" published by the
Internet Society. In it, Kleinrock is described as having "published the first paper on packet switching theory in July 1961 and the first book on the subject in 1964". Many sources about the history of the Internet began to reflect these claims as uncontroversial facts. This became the subject of what
Katie Hafner called a "paternity dispute" in The New York Times in 2001. The disagreement about Kleinrock's contribution to packet switching escalated after a statement made on Kleinrock's profile on the UCLA Computer Science department website sometime in the 1990s. Here, he was referred to as the "Inventor of the Internet Technology". The webpage's depictions of Kleinrock's achievements provoked anger among some early Internet pioneers. The dispute over
priority became a public issue after Donald Davies posthumously published a paper in 2001 in which he denied that Kleinrock's work in the early 1960s was related to packet switching, stating "I can find no evidence that he understood the principles of packet switching". Davies also described ARPANET project manager
Larry Roberts as supporting Kleinrock, referring to Roberts' writings online and Kleinrock's UCLA webpage profile as "very misleading".
Walter Isaacson wrote that Kleinrock's claims "led to an outcry among many of the other Internet pioneers, who publicly attacked Kleinrock and said that his brief mention of breaking messages into smaller pieces did not come close to being a proposal for packet switching". The reignited debate caused other former BBN employees to make their concerns known, including Alex McKenzie, who followed Davies in disputing that Kleinrock's work was related to packet switching, stating "... there is nothing in the entire 1964 book that suggests, analyzes, or alludes to the idea of packetization". Former
IPTO director
Bob Taylor also joined the debate, stating that "authors who have interviewed dozens of Arpanet pioneers know very well that the Kleinrock-Roberts claims are not believed". Walter Isaacson notes that "until the mid-1990s Kleinrock had credited [Baran and Davies] with coming up with the idea of packet switching". He was called on to defend his position over subsequent decades. A paper published in the journal
Internet Histories in 2019 supported Kleinrock's view; the author interviewed Kleinrock and Roberts, and did not interview Scantlebury. In 2023, Kleinrock acknowledged that his work published in the early 1960s was about message switching and claimed he was thinking about packet switching. Primary sources and historians recognize Baran and Davies for independently inventing the concept of digital packet switching used in modern computer networking including the ARPANET and the Internet. Kleinrock has received many awards for his ground-breaking
applied mathematical research on packet switching, carried out in the 1970s, which was an extension of his pioneering work in the early 1960s on the optimization of message delays in communication networks. However, Kleinrock's claims that his work in the early 1960s originated the concept of packet switching and that his work was a source of the packet switching concepts used in the ARPANET have affected sources on the topic, which has created methodological challenges in the historiography of the Internet. ==Connectionless and connection-oriented modes==