Packet switching

From Freepedia

In computer networking and telecommunications, packet switching is the now-dominant communications paradigm, in which packets (units of information carriage) are individually routed between nodes over data links which might be shared by many other nodes. This contrasts with the principal other paradigm, circuit switching, which sets up a dedicated connection between the two nodes for their exclusive use for the duration of the communication. Packet switching is used to optimize the use of the bandwidth available in a network, to minimize the transmission latency (i.e. the time it takes for data to pass across the network), and to increase robustness of communication.

Contents

Packets

A packet is a block of data (called a payload) with address and administrative information attached to allow a network of nodes to deliver the data to the destination, e.g., as in IPv6. A packet is analogous to a letter sent through the mail with the address written on the outside.

Packet routing

Packets are routed to their destination through the most expedient route (as determined by some routing algorithm). Not all packets travelling between the same two nodes will necessarily follow the same route. One data connection will usually carry a stream of packets from several nodes. The destination node reassembles the packets into their appropriate sequence. Consequently packets sent between a pair of nodes may arrive in an order different from the order in which they were sent.

Packet switching influenced the development of the Actor model of concurrent computation in which messages sent to the same address may be delivered in an order different from the order in which they were sent.

Packet switching in the Internet

The most well-known use of the packet switching model is the Internet, which is a packet-switched network, running the Internet Protocol layer 3 protocol over a variety of other network technologies. Ethernet, X.25 and Frame relay are international standard layer 2 packet switching networks. Newer mobile phone technologies such as GPRS and i-mode also employ packet switching.

Packet switching is also called connectionless networking, because it is the opposite of circuit switched or connection-oriented networking, although technologies such as MPLS are beginning to blur the boundaries between the two. ATM is another hybrid technology, which uses cell relay instead of packet switching.

Fast packet switching is a packet switching technique that increases the throughput by eliminating overhead.

Controversy over invention of packet switching

There is controversy over the invention of packet switching.

Work at MIT

In Internet Society publication A Brief History of the Internet, Barry M. Leiner, Vinton G. Cerf, David D. Clark, Robert E. Kahn, Leonard Kleinrock, Daniel C. Lynch, Jon Postel, Larry G. Roberts, Stephen Wolff stated

"Leonard Kleinrock at MIT published the first paper on packet switching theory in July 1961 and the first book on the subject in 1964. Kleinrock convinced Roberts of the theoretical feasibility of communications using packets rather than circuits, which was a major step along the path towards computer networking. The other key step was to make the computers talk together. To explore this, in 1965 working with Thomas Merrill, Roberts connected the TX-2 computer in Mass. to the Q-32 in California with a low speed dial-up telephone line creating the first (however small) wide-area computer network ever built. The result of this experiment was the realization that the time-shared computers could work well together, running programs and retrieving data as necessary on the remote machine, but that the circuit switched telephone system was totally inadequate for the job. Kleinrock's conviction of the need for packet switching was confirmed."

Work at RAND

According to Larry Roberts in The Evolution of Packet Switching,

"The first published description of what we now call packet switching was an 11-volume analysis, On Distributed Communications, prepared by Paul Baran of the Rand Corporation in August 1964. This study was conducted for the Air Force, and it proposed a fully distributed packet switching system to provide for all military communications, data, and voice. The study also included a totally digital microwave system and integrated encryption capability. The Air Force's primary goal was to produce a totally survivable system that contained no critical central components. Not only was this goal achieved by Rand's proposed packet switching system, but even the economics projected were superior, for both voice and data transmissions. Unfortunately, the Air Force took no follow-up action, and the report sat largely ignored for many years until packet switching was rediscovered and applied by others."

Baran described two key ideas: first, use of a decentralized network with multiple paths between any two points; and second, dividing complete user messages into what he called message blocks (later called packets) before sending them into the network. This first allowed the elimination of single points of failure, and enabled the network to automatically and efficiently work around any failures. A summary paper describing the entire scheme was published in 1964.

Work at National Physical Laboratory

According to Larry Roberts in The Evolution of Packet Switching,

"Almost immediately after the 1965 meeting, Donald Davies conceived of the details of a store-and-forward packet switching system, and in a June 1966 description of his proposal coined the term "packet" to describe the 128-byte blocks being moved around inside the network. Davies circulated his proposed network design throughout the U.K. in late 1965 and 1966. It was only after this distribution that he discovered Paul Baran's 1964 report.
The first open publication of the NPL proposal was in October 1967 at the A.C.M. Symposium in Gatlinburg, TN. In nearly all respects, Davies' original proposal, developed in late 1965, was similar to the actual networks being built today. His cost analysis showed strong economic advantages for the packet approach, and by all rights, the proposal should have led quickly to a U.K. project. However, the communications world was hard to convince, and for several years, nothing happened in the U.K. on the development of a multi-node packet switching network.
Donald Davies was able, however, to initiate a local network with a single packet switch at the NPL. By 1973 this local network was providing an important distribution service within the laboratory. This project, plus the strong conviction and continued effort by those at NP1. (Davies, Barber, Scantlebury, Wilkinson, and Bartlett), did gradually have an effect on the U.K. and much of Europe."

Davies had begun working with related concepts in 1965, after a conference in the United Kingdom on time-sharing brought up the inadequacies of existing circuit-switched networks. His work was originally carried out independently from Baran's work, although Davies learned of it after he gave a seminar on his ideas at NPL in 1966. Prior to his death, Davies contested the claim that Leonard Kleinrock invented packet switching pointing out that Kleinrock's research was actually in queueing theory, which is a key theoretical underpinning to packet switching. Davies claimed that Kleinrock's published works nowhere prominently mention breaking a user's message up into segments, and sending the segments through the network separately, which he said was the key innovation.

Simultaneous Development

As with many other inventions, it can be said that the research groups developed simultaneously. Thus, the ideas that were to become the ARPANET came from three research centers: MIT, the RAND Corporation, and National Physical Laboratory.

See also

Further reading

  • Katie Hafner, Where Wizards Stay Up Late (Simon and Schuster, 1996) pp 52-67
  • Janet Abbate, Inventing the Internet (MIT Press, Cambridge, 1999) pp. 7-35 (this book gives a detailed description of Davies' work)

Reference

  • Leonard Kleinrock, Information Flow in Large Communication Nets, (MIT, Cambridge, May 31, 1961) Proposal for a Ph.D. Thesis
  • Leonard Kleinrock. Information Flow in Large Communication Nets (RLE Quarterly Progress Report, July 1961)
  • Leonard Kleinrock. Communication Nets: Stochastic Message Flow and Delay (Mcgraw-Hill, New York, 1964)
  • Paul Baran et al., On Distributed Communications, Volumes I-XI (RAND Corporation Research Documents, August, 1964)
  • Paul Baran, On Distributed Communications Networks (IEEE Transactions on Communications Systems, March 1964)
  • D. W. Davies, K. A. Bartlett, R. A. Scantlebury, and P. T. Wilkinson, A digital communications network for computers giving rapid response at remote terminals (ACM Symposium on Operating Systems Principles. October 1967)
  • R. A. Scantlebury, P. T. Wilkinson, and K. A. Bartlett, The design of a message switching Centre for a digital communication network (IFIP 1968)
  • Larry Roberts and Tom Merrill, Toward a Cooperative Network of Time-Shared Computers (Fall AFIPS Conference. October 1966)
  • Lawrence Roberts, The Evolution of Packet Switching (Proceedings of the IEEE, November, 1978)

External links

This article was originally based on material from the Free On-line Dictionary of Computing, which is licensed under the GFDL.
Retrieved from "http://en.freepedia.org/Packet_switching.html"


Views
Personal tools
In other languages
Similar Links