In telecommunications, packet switching is a method of grouping data into short messages in fixed format, i.e., packets, that are transmitted over a telecommunications network. Packets consist of a header and a payload. The header directs the packet to its destination, where the payload is extracted and used by an operating system, application software, or higher-layer protocols. Packet switching is the primary basis for data communications in computer networks worldwide.
During the early 1960s, American engineer Paul Baran developed a concept he called distributed adaptive message block switching as part of a research program at the RAND Corporation, funded by the United States Department of Defense. His proposal was to provide a fault-tolerant, efficient method for communication of voice messages using low-cost hardware to route the message blocks across a distributed network. His ideas contradicted then-established principles of pre-allocation of network bandwidth, exemplified by the development of telecommunications in the Bell System. The new concept found little resonance among network implementers until the independent work of British computer scientist Donald Davies at the National Physical Laboratory beginning in 1965. Davies developed the concept for data communication using software switches in a high-speed computer network and coined the term packet switching. His work inspired numerous packet switching networks in the decade following, including the incorporation of the concept into the design of the ARPANET in the United States and the CYCLADES network in France. The ARPANET and CYCLADES were the primary precursor networks of the modern Internet.
Concept
A simple definition of packet switching is:
Packet switching allows delivery of variable bit rate data streams, realized as sequences of short messages in fixed format, i.e. packets, over a computer network which allocates transmission resources as needed using statistical multiplexing or dynamic bandwidth allocation techniques. As they traverse networking hardware, such as switches and routers, packets are received, buffered, queued, and retransmitted (stored and forwarded), resulting in variable latency and throughput depending on link capacity and traffic load on the network. Packets are normally forwarded by intermediate network nodes asynchronously using first-in, first-out buffering, but may be forwarded according to some scheduling discipline for fair queuing, traffic shaping, or for differentiated or guaranteed quality of service, such as weighted fair queuing or leaky bucket. Packet-based communication may be implemented with or without intermediate forwarding nodes (switches and routers). In case of a shared physical medium (such as radio or 10BASE5), the packets may be delivered according to a multiple access scheme.
Packet switching contrasts with another principal networking paradigm, circuit switching, a method which pre-allocates dedicated network bandwidth specifically for each communication session, each having a constant bit rate and latency between nodes. In cases of billable services, such as cellular communication services, circuit switching is characterized by a fee per unit of connection time, even when no data is transferred, while packet switching may be characterized by a fee per unit of information transmitted, such as characters, packets, or messages.
A packet switch has four components: input ports, output ports, routing processor, and switching fabric.
History
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.. "the first paper on time-shared computers by C. Strachey at the June 1959 UNESCO Information Processing conference". 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 coined the term packet switching, and proposed building a commercial nationwide data network in the UK. 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). More significantly, Roger Scantlebury ... presents the design for a packet-switched network. This is the first Roberts and Taylor have heard of packet switching, a concept that appears to be a promising receipe for transmitting data through the ARPAnet. 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", thus inventing what came to be known as the end-to-end principle. Davies proposed that a local-area network should be built at the laboratory to serve the needs of NPL and prove the feasibility of packet switching. After a pilot experiment in early 1969, 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. "As well as the packet switched network actually built at NPL for communication between their local computing facilities, some simulation experiments have been performed on larger networks. A summary of this work is reported in . The work was carried out to investigate networks of a size capable of providing data communications facilities to most of the U.K. ... Experiments were then carried out using a method of flow control devised by Davies called 'isarithmic' flow control. ... The simulation work carried out at NPL has, in many respects, been more realistic than most of the ARPA network theoretical studies."
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 retransmission, 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,"Pioneer: Donald Davies", Internet Hall of Fame "America’s Advanced Research Project Agency (ARPA), and the ARPANET received his network design enthusiastically and the NPL local network became the first two computer networks in the world using the technique." 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, applied Kleinrock'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. pp. III-40-1 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, Kleinrock sought input from Baran and proposed to retain Baran and RAND as advisors. 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.