Packet switching
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, 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. In case of a shared physical medium, 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 in the UK in 1965.In the late 1950s, the US Air Force established a wide area network for the Semi-Automatic Ground Environment 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. 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 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 told him about Baran's work.
Roger Scantlebury, a member of Davies' team, presented their work at the October 1967 Symposium on Operating Systems Principles. 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 and datagram losses, 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.
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 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, applied Kleinrock's techniques to show that "there is an ample margin between the estimated performance of the 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. 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 at UCLA to measure and model the performance of packet switching in the ARPANET.
Bolt Beranek & Newman won the contract to build the network. Designed principally by Bob Kahn, it was the first wide-area packet-switched network with distributed control. The BBN "IMP Guys" independently developed significant aspects of the network's internal operation, including the routing algorithm, flow control, software design, and network 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 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 packet switching would never be economic without the government subsidy. Baran had faced the same rejection and thus failed to convince the military into constructing a packet switching network in the 1960s.
The CYCLADES network was designed by Louis Pouzin in the early 1970s to study internetworking. 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.
Bob Metcalfe and others at Xerox PARC outlined the idea of Ethernet and the PARC Universal Packet 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 , 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, atop the Internet Protocol. 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 VLSI technology led to the development of high-speed broadband packet switching during the 1980s1990s.