Packet Switching

Leonard Kleinrock

On 24 July 1961 MIT accepts Leonard Kleinrock's doctoral dissertation "Information Flow in Large Communication Nets." This work is considered the first paper on packet-switching theory.

The importance of Kleinrock's theory quickly became evident. Indeed, the Internet as we know it today could not function without packet switching. This approach, developed by a series of scientists and engineers in the 1960s, revolutionized the way that digital information was sent along communications lines. Sending data became cheaper and more reliable and flexible than the circuit-switched systems used for telephone communication.

Before the 1970s, almost all data traveled across the world on circuit-switched networks. Telephone exchanges were the major example. Operators sent calls along pre-allocated lines for the length of the conversation. This kind of fixed scheduling did not work well for digital communications. It was wasteful, as data traffic happened in short bursts and used less than ten percent of the bandwidth. It also sharply limited the number of potential users. Only one user could use the transmission line when sending a communication. Still, as one of the key developers of this approach, Lawrence G. Roberts explained in 1978, the economics of packet switching did not make sense before the spread of mass computing: “if lines are cheap, use circuit switching; if computing is cheap, use packet switching.”

The pioneers of packet switching analogized interactive data communication to traditional mail systems, which sent packets of information along whenever the train was leaving or the mail bag was full and sent those packets along a series of sorting and routing decisions. Roberts pointed to the fact that “message, telegraph, and mail systems have historically operated by dynamically allocating bandwidths or space after a message is received, one link at a time, never attempting to schedule bandwidth over the whole source-to-destination path.” With the advent of digital communications, these links would no longer be manual, and could be processed at high speeds.

Leonard Kleinrock first proposed the idea of packet switching in his 1961 MIT doctoral dissertation. The concept was then developed by RAND Corporation researcher Paul Baran. Baran wrote an eleven-volume analysis, “On Distributed Communications,” for the Air Force in August 1964. The Air Force wanted to build a communication system that would not fail if one of its nodes was destroyed. Packet switching had the virtue of being completely survivable because it had no critical central components.

In this early period, J.C.R. Licklider of the Advanced Research Projects Agency (ARPA) of the Department of Defense also developed time-sharing systems. Licklider’s theories on the matter inspired the projects of Lawrence G. Roberts and British researcher Donald Davies.

In 1965, Davies of the National Physical Laboratory designed a store-and-forward packet switching system. In a June 1966 proposal, he coined the term “packet” to describe the 128-byte data blocks that would flow through the system. Only after distributing this research in Britain, however, did Davies learn that Baran had made a similar proposal in 1964. Still, the British declined to adopt his communication system.

In 1966, Lawrence G. Roberts published an influential article, “Towards a Cooperative Network of Time-Shared Computers.” This proposal described a packet-switched system for sending digital communications among a network of computer nodes. ARPA then began work on a pilot program to link computers at universities and research laboratories, which became known as ARPANET. By the end of 1969, the firm of Bolt, Beranek and Newman (BBN) had responded to a request for proposals from ARPA and developed a four-node computer network.

This ARPANET was linked by leased communication lines that sent data at speeds of fifty kilobits per second. Operating on principles of packet switching, it queued up data and subdivided it into 128-byte packets programmed with a destination and address. The computer sent the packets along whichever route would move it fastest to that destination.

Packet switching received its first public demonstration at the Hilton Hotel in Washington, D.C., in October 1972. BBN’s Robert Kahn demonstrated its effectiveness to the engineers attending the first International Conference on Computer Communications by setting up forty active terminals at the hotel, which let participants send messages to dozens of computers across the United States.

Further Reading

The Evolution of Packet Switching, Dr. Lawrence G. Roberts, November 1978