Achievements
Queueing theory
Kleinrock's best-known and most-significant work is on queueing theory, a major topic of applied mathematics that has applications in many fields. His thesis proposal in 1961, Information Flow in Large Communication Nets, led to a doctoral thesis at MIT in 1962, Message Delay in Communication Nets with Storage, later published as book in 1964, Communication Nets: Stochastic Message Flow and Design. In this work, he researched the configuration and operation of communication networks, considering design parameters such as "channel capacity, effect of priority discipline, choice of routing procedure, and design of topological structure". He analyzed delays in Plan 55-A, a message switching system operated by Western Union for processing telegrams. His thesis went on to apply probability theory to model queueing delays in a generalized communication network.
Donald Davies, in his 1966 paper on packet switching, applied Kleinorck's techniques to show that "there is an ample margin between the estimated performance of the [packet-switched] system and the stated requirement" in terms of a satisfactory response time for a human user. This addressed a key question about the viability of computer networking.
ARPANET
A contemporary from MIT, Larry Roberts, brought Leonard Kleinrock into the ARPANET project informally in early 1967. Roberts 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 retransmission, and computer and user identification." Later that year, Roberts learned about packet switching from a paper written by Davies, presented at the October 1967 Symposium on Operating Systems Principles, and incorporated the concept into the proposal for the ARPANET.
Kleinrock was awarded a contract in 1968 to establish a Network Measurement Center (NMC) to measure and model the performance of the network. His mathematical work studied and influenced the development of the early ARPANET. In addition, Kleinrock managed the software team at UCLA — including Steve Crocker, Jon Postel, and Vint Cerf — who developed the host-host protocol for the ARPANET, the Network Control Program (NCP).
The first message on the ARPANET was sent by a UCLA undergraduate student, Charley Kline, who was supervised by Kleinrock. At 10:30 p.m, on October 29, 1969, from Boelter Hall 3420, the school's main engineering building, Kline transmitted from the university's SDS Sigma 7 host computer to the Stanford Research Institute's SDS 940 host computer. The message text was the word "login"; the "l" and the "o" letters were transmitted, but the system then crashed. Hence, the literal first message over the ARPANET was "lo". About an hour later, having recovered from the crash, the SDS Sigma 7 computer effected a full "login". The first permanent ARPANET link was established on November 21, 1969, between the Interface Message Processor (IMP) at UCLA and the IMP at the Stanford Research Institute. By December 5, 1969, the initial four-node network was established.
Kleinrock used the ARPANET for instant messaging from the U.S. to Larry Roberts in England in 1973, employing the network for a modern every-day use.
Internet
Kleinrock published hundreds of research papers, which ultimately launched a new field of research on the theory and application of queueing theory to computer networks. In this role, he supervised the research of scores of graduate students. He disseminated his research and that of his students to wider audiences for academic and commercial use, and organized hundreds of commercial seminars presented by experts and pioneers in the U.S. and internationally. Many graduate students that Kleinrock supported based their careers on expertise they acquired while working on the ARPANET with him, including several whose later work on internetworking and the Internet protocol suite led to the networking technology employed in the Internet. Kleinrock's work published in the mid-1970s on the performance of the ARPANET, which was discussed at the International Network Working Group, underpinned the development of the Transmission Control Protocol of the Internet protocol suite. His analytic work in the 1970s addressed packet switching networks, packet radio networks, local area networks, broadband networks, nomadic computing, peer-to-peer networks, and intelligent software agents. Kleinrock's theoretical work on hierarchical routing with student Farouk Kamoun remains critical to the operation of the Internet today.
In 1988, Kleinrock was the chairman of a group that presented the report Toward a National Research Network to the U.S. Congress, concluding that "There is a clear and urgent need for a national research network". Although the U.S. did not build a nationwide national research and education network, this report influenced Al Gore to pursue the development of the High Performance Computing Act of 1991, which helped facilitate development of the Internet as it is known today. Funding from the bill was used in the development of the 1993 web browser Mosaic at the National Center for Supercomputing Applications (NCSA), which accelerated the adoption of the World Wide Web.
Packet switching 'paternity dispute'
In 1990, Kleinrock said:
The thing that really drove my own research was the idea of a message switching network, which was a precursor to the packet switching networks. The mathematical tool that had been developed in queueing theory, namely queueing networks, matched perfectly the model of computer networks. Actually, it didn't match perfectly and I had to adjust that model to fit the realities of computer networks. Then I developed some design procedures as well for optimal capacity assignment, routing procedures and topology design.
Beginning in the mid-1990s, Kleinrock sought to be recognized "as the father of modern data networking". By 1997, he claimed priority on the invention of packet switching and to have convinced Larry Roberts to adopt the technique. In 2004, he described his work as:
Basically, what I did for my PhD research in 1961-1962 was to establish a mathematical theory of packet networks which uncovered the underlying principles that drives today's Internet.
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 are disputed by other Internet pioneers, including Robert Taylor, Paul Baran, and Donald Davies. Historians and the U.S. National Inventors Hall of Fame recognize Baran and Davies for independently inventing the concept of digital packet switching used in modern computer networking including the Internet.