Intelecommunications,packet switching is a method of groupingdata into short messages in fixed format, i.e.,packets, that are transmitted over atelecommunications network. Packets consist of aheader and apayload. The header directs the packet to its destination, where the payload is extracted and used by anoperating system,application software, orhigher-layer protocols. Packet switching is the primary basis fordata communications incomputer networks worldwide.
During the early 1960s, American engineerPaul Baran developed a concept he calleddistributed adaptive message block switching as part of a research program at theRAND Corporation, funded by theUnited States Department of Defense. His proposal was to provide afault-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 ofpre-allocation of network bandwidth, exemplified by the development of telecommunications in theBell System. The new concept found little resonance among network implementers until the independent work of British computer scientistDonald Davies at theNational Physical Laboratory beginning in 1965. Davies developed the concept for data communication using software switches in a high-speed computer network and coined the termpacket switching. His work inspired numerous packet switching networks in the decade following, including the incorporation of the concept into the design of theARPANET in the United States and theCYCLADES network in France. The ARPANET and CYCLADES were the primary precursor networks of the modernInternet.
A simple definition of packet switching is:
Therouting and transferring of data by means of addressed packets so that achannel is occupied during thetransmission of the packet only, and upon completion of the transmission the channel is made available for the transfer of othertraffic.[5][6]
Packet switching allows delivery ofvariable bit rate data streams, realized as sequences of short messages in fixed format, i.e.packets, over acomputer network which allocates transmission resources as needed usingstatistical multiplexing ordynamic bandwidth allocation techniques. As they traversenetworking hardware, such asswitches androuters, packets are received, buffered, queued, and retransmitted (stored and forwarded), resulting in variable latency andthroughput depending on link capacity and traffic load on the network. Packets are normally forwarded by intermediate network nodes asynchronously usingfirst-in, first-out buffering, but may be forwarded according to some scheduling discipline forfair queuing,traffic shaping, or for differentiated or guaranteedquality of service, such asweighted fair queuing orleaky 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 or10BASE5), the packets may be delivered according to amultiple 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 ascellular 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.[7]
-en.svg)
The concept of switching small blocks of data was invented independently byPaul Baran at theRAND Corporation during the early 1960s in the US andDonald Davies at theNational Physical Laboratory (NPL) in the UK in 1965.[1][2][3][11]
In the late 1950s, theUS Air Force established awide area network for theSemi-Automatic Ground Environment (SAGE) radar defense system. Recognizing vulnerabilities in this network, the Air Force sought a system that might survive anuclear attack to enable a response, thus diminishing the attractiveness of the first strike advantage by enemies (seeMutual assured destruction). In the early 1960s, Baran invented the concept ofdistributed adaptive message block switching in support of the Air Force initiative.[12][13][14] The concept was first presented to the Air Force in the summer of 1961 as briefing B-265,[15] later published as RAND report P-2626 in 1962,[8] and finally in report RM 3420 in 1964.[9] The reports describe a general architecture for a large-scale, distributed, survivable communications network. The proposal was composed of three key ideas: use of adecentralized network with multiple paths between any two points; dividing user messages intomessage blocks; and delivery of these messages bystore and forward switching.[12][16] Baran's network design was focused on high-speeddigital communication of voice messages using hardware switches that were low-cost electronics.[17][18][19]
Christopher Strachey, who becameOxford University's first Professor of Computation, filed apatent application in the United Kingdom fortime-sharing in February 1959.[20][21] In June that year, he gave a paper "Time Sharing in Large Fast Computers" at theUNESCO Information Processing Conference in Paris where he passed the concept on toJ. C. R. Licklider.[22][23] Licklider (along withJohn McCarthy) was instrumental in the development of time-sharing. After conversations with Licklider about time-sharing with remote computers in 1965,[24][25] Davies independently invented a similardata communication concept.[26] His insight was to use short messages in fixed format with high data transmission rates to achieve rapid communications.[27] He went on to develop a design for a hierarchical, high-speedcomputer network includinginterface computers andcommunication protocols.[28][29][14] He coined the termpacket switching, and proposed building a commercial nationwide data network in the UK.[30][31] He gave a talk on the proposal in 1966, after which a person from theMinistry of Defence (MoD) told him about Baran's work.[32]
Roger Scantlebury, a member of Davies' team, presented their work (and referenced that of Baran) at the October 1967Symposium on Operating Systems Principles (SOSP).[33][34][35][36][37] At the conference, Scantlebury proposed packet switching for use in theARPANET and persuadedLarry Roberts the economics were favorable tomessage switching.[38][39][40][41][42][43] 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) anddatagram 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",[33] thus inventing what came to be known as theend-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 apilot experiment in early 1969,[44][45][46][47] theNPL Data Communications Network began service in 1970.[48] Davies was invited to Japan to give a series of lectures on packet switching.[49] The NPL team carried outsimulation work on datagrams andcongestion in networks on a scale to provide data communication across the United Kingdom.[47][50][51][52][53]
Larry Roberts made the key decisions in therequest for proposal to build theARPANET.[54] Roberts met Baran in February 1967, but did not discuss networks.[55][56] He askedFrank 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."[57] Roberts revised his initial design, which was to connect thehost computers directly, to incorporateWesley Clark's idea to useInterface Message Processors (IMPs) to create amessage switching network, which he presented at SOSP.[58][59][60][61] Roberts was known for making decisions quickly.[62] Immediately after SOSP, he incorporated Davies' concepts and designs for packet switching to enable the data communications on the network,[40][63][64][65] and sought input from Baran.[66]
A contemporary of Roberts' fromMIT,Leonard Kleinrock had researched the application ofqueueing theory in the field ofmessage switching for his doctoral dissertation in 1961–62 and published it as a book in 1964.[67] Davies, in his 1966 paper on packet switching,[28] 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 satisfactoryresponse time for a human user.[68] This addressed a key question about the viability of computer networking.[69] Larry Roberts brought Kleinrock into the ARPANET project informally in early 1967.[70] 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 astore-and-forward system that was not intended forreal-time computing.[71] After SOSP, and after Roberts' direction to use packet switching,[63] Kleinrock sought input from Baran and proposed to retain Baran and RAND as advisors.[72][73][74] The ARPANET working group assigned Kleinrock responsibility to prepare a report on software for the IMP.[75] In 1968, Roberts awarded Kleinrock a contract to establish a Network Measurement Center (NMC) atUCLA to measure and model the performance of packet switching in the ARPANET.[72]
Bolt Beranek & Newman (BBN) won the contract to build the network. Designed principally byBob Kahn,[76][77] it was the first wide-area packet-switched network with distributed control.[54] 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.[78][79] The UCLA NMC and the BBN team also investigated network congestion.[76][80] The Network Working Group, led bySteve Crocker, a graduate student of Kleinrock's at UCLA, developed the host-to-host protocol, theNetwork Control Program, which was approved by Barry Wessler for ARPA,[81] after he ordered certain more exotic elements to be dropped.[82] In 1970, Kleinrock extended his earlieranalytic work on message switching to packet switching in the ARPANET.[83]
The ARPANET was demonstrated at theInternational Conference on Computer Communication (ICCC) in Washington in October 1972.[84][85] However, fundamental questions about the design of packet-switched networks remained.[86][87][88][89]
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.[10]
TheCYCLADES network was designed byLouis Pouzin in the early 1970s to studyinternetworking.[90][91][92] 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.[93] His team was thus first to tackle the highly-complex problem of providing user applications with a reliablevirtual circuit service while using abest-effort service, an early contribution to what will be theTransmission Control Protocol (TCP).[94]
Bob Metcalfe and others atXerox PARC outlined the idea ofEthernet and thePARC Universal Packet (PUP) for internetworking.[95]
In May 1974,Vint Cerf andBob Kahn described theTransmission Control Program, an internetworkingprotocol for sharing resources using packet-switching among the nodes.[96] The specifications of the TCP were then published inRFC 675 (Specification of Internet Transmission Control Program), written by Vint Cerf,Yogen Dalal and Carl Sunshine in December 1974.[97]
TheX.25 protocol, developed byRémi Després and others, was built on the concept ofvirtual circuits. In the mid-late 1970s and early 1980s, national and internationalpublic data networks emerged using X.25 which was developed with participation from France, the UK, Japan, USA and Canada. It was complemented withX.75 to enable internetworking.[98]
In the late 1970s, the monolithic Transmission Control Program was layered as the Transmission Control Protocol (TCP), atop theInternet Protocol (IP). ManyInternet pioneers developed this into theInternet protocol suite and the associated Internet architecture and governance that emerged in the 1980s.[99][100][101][102][103][104]
Leonard Kleinrock carried out theoretical work at UCLA during the 1970s analyzing throughput and delay in the ARPANET.[83][105][106] Kleinrock published hundreds of research papers,[107][108] which ultimately launched a new field of research on the theory and application of queuing theory to computer networks.[109][110] His work onhierarchical routing with studentFarouk Kamoun became critical to the operation of the Internet.[111][112]
Packet switching was shown to be optimal in theHuffman coding sense in 1978.[113][114]
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 theProtocol Wars. It was unclear which of the Internet protocol suite and theOSI model would result in the best and most robust computer networks.[115][116][117]
Complementarymetal–oxide–semiconductor (CMOS)VLSI (very-large-scale integration) technology led to the development of high-speedbroadband packet switching during the 1980s–1990s.[118][119][120]
In the 1978 special edition of theProceedings of the IEEE on packet switching, Bob Kahn, the guest editor, wrote that "analysis has had little direct impact on the network design problem".[121] In Roberts' paper on "Packet Switching Economics" for the L.M. Ericsson prize for research in data communications in 1982, he referenced only Davies' 1967 paper for SOSP, not the work of Baran or Kleinrock.[122] Kleinrock's paper for the same prize was titled "Packet Switching Principles".[123] In Roberts' 1986 conference paper on "The ARPANET & Computer Networks", he also cites Baran's 1964 paper and one of his own papers from 1966; but only references Kleinrock's work from the 1970s, which addressed the ARPANET.[124] This paper was republished on the web by Roberts in 1995.[125]
Roberts began to claim, in the late 1990s, that, by the time of the October 1967 SOSP, he already had the concept of packet switching in mind (although not yet named and not written down in his paper published at the conference, which a number of sources describe as "vague"), and that this originated with his old colleague, Kleinrock, who had written about such concepts in his Ph.D. research in 1961-2.[60][38][61][126][127] In 1997, along with seven otherInternet pioneers, Roberts and Kleinrock co-wrote "Brief History of the Internet" published by theInternet Society. In it, Kleinrock is described as having "published the first paper on packet switching theory in July 1961 and the first book on the subject in 1964".[128] Many sources about the history of the Internet began to reflect these claims as uncontroversial facts. This became the subject of whatKatie Hafner called a "paternity dispute" in The New York Times in 2001.[129]
The disagreement about Kleinrock's contribution to packet switching escalated after a statement made on Kleinrock's profile on the UCLA Computer Science department website sometime in the 1990s. Here, he was referred to as the "Inventor of the Internet Technology".[130] The webpage's depictions of Kleinrock's achievements provoked anger among some early Internet pioneers.[131] The dispute overpriority became a public issue after Donald Davies posthumously published a paper in 2001 in which he denied that Kleinrock's work in the early 1960s was related to packet switching, stating "I can find no evidence that he understood the principles of packet switching". Davies also described ARPANET project managerLarry Roberts as supporting Kleinrock, referring to Roberts' writings online and Kleinrock's UCLA webpage profile as "very misleading".[132][133]Walter Isaacson wrote that Kleinrock's claims "led to an outcry among many of the other Internet pioneers, who publicly attacked Kleinrock and said that his brief mention of breaking messages into smaller pieces did not come close to being a proposal for packet switching".[131]
Davies' paper reignited a previous dispute over who deserves credit for getting the ARPANET online between engineers atBolt, Beranek, and Newman (BBN) who had been involved in building and designing the ARPANET IMP on the one side, and ARPA-related researchers on the other.[78][79] This earlier dispute is exemplified by BBN'sWill Crowther, who in a 1990 oral history described Paul Baran's packet switching design (which he calledhot-potato routing), as "crazy" and non-sensical, despite the ARPA team having advocated for it.[134] The reignited debate caused other former BBN employees to make their concerns known, including Alex McKenzie, who followed Davies in disputing that Kleinrock's work was related to packet switching, stating "... there is nothing in the entire 1964 book that suggests, analyzes, or alludes to the idea of packetization".[135]
FormerIPTO directorBob Taylor also joined the debate, stating that "authors who have interviewed dozens of Arpanet pioneers know very well that the Kleinrock-Roberts claims are not believed".[136] Walter Isaacson notes that "until the mid-1990s Kleinrock had credited [Baran and Davies] with coming up with the idea of packet switching".[131]
A subsequent version of Kleinrock's biography webpage was copyrighted in 2009 by Kleinrock.[137] He was called on to defend his position over subsequent decades.[138] A paper published in the journalInternet Histories in 2019 supported Kleinrock's view;[139] the author interviewed Kleinrock and Roberts, and did not interview Scantlebury.[140] In 2023, Kleinrock acknowledged that his work published in the early 1960s was about message switching and claimed he was thinking about packet switching.[141] Primary sources and historians recognize Baran and Davies for independently inventing the concept of digital packet switching used in modern computer networking including the ARPANET and the Internet.[1][2][40][142][143]
Kleinrock has received many awards for his ground-breakingapplied mathematical research on packet switching, carried out in the 1970s, which was an extension of his pioneering work in the early 1960s on the optimization of message delays in communication networks.[83][144] 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 have affected sources on the topic, which has created methodological challenges in the historiography of the Internet.[129][131][133][138] Historian Andrew L. Russell said "'Internet history' also suffers from a ... methodological, problem: it tends to be too close to its sources. Many Internet pioneers are alive, active, and eager to shape the histories that describe their accomplishments. Many museums and historians are equally eager to interview the pioneers and to publicize their stories".[145]
Packet switching may be classified intoconnectionless packet switching, usingdatagrams, andconnection-oriented packet switching, usingvirtual circuits. Examples of connectionless systems areEthernet,IP, and theUser Datagram Protocol (UDP). Connection-oriented systems includeX.25,Frame Relay,Multiprotocol Label Switching (MPLS), and TCP.
In connectionless mode each packet is labeled with a destination address, source address, and port numbers. It may also be labeled with the sequence number of the packet. This information eliminates the need for a pre-established path to help the packet find its way to its destination, but means that more information is needed in the packet header, which is therefore larger. The packets are routed individually, sometimes taking different paths resulting inout-of-order delivery. At the destination, the original message may be reassembled in the correct order, based on the packet sequence numbers. Thus avirtual circuit carrying abyte stream is provided to the application by atransport layer protocol, although the network only provides a connectionlessnetwork layer service.
Connection-oriented transmission requires a setup phase to establish the parameters of communication before any packet is transferred. Thesignaling protocols used for setup allow the application to specify its requirements and discover link parameters. Acceptable values for service parameters may be negotiated. The packets transferred may include a connection identifier rather than address information and the packet header can be smaller, as it only needs to contain this code and any information, such as length, timestamp, or sequence number, which is different for different packets. In this case, address information is only transferred to each node during the connection setup phase, when the route to the destination is discovered and an entry is added to the switching table in each network node through which the connection passes. When a connection identifier is used, routing a packet requires the node to look up the connection identifier in a table.[citation needed]
Connection-oriented transport layer protocols such asTCP provide a connection-oriented service by using an underlying connectionless network. In this case, the end-to-end principle dictates that the end nodes, not the network itself, are responsible for the connection-oriented behavior.
In telecommunication networks, packet switching is used to optimize the usage ofchannel capacity and increaserobustness.[61] Compared tocircuit switching, packet switching is highly dynamic, allocating channel capacity based on usage instead of explicit reservations. This can reduce wasted capacity caused by underutilized reservations at the cost of removing bandwidth guarantees. In practice,congestion control is generally used in IP networks to dynamically negotiate capacity between connections. Packet switching may also increase the robustness of networks in the face of failures. If a node fails, connections do not need to be interrupted, as packets may be routed around the failure.
Packet switching is used in theInternet and mostlocal area networks. The Internet is implemented by theInternet Protocol Suite using a variety oflink layer technologies. For example, Ethernet and Frame Relay are common. Newermobile phone technologies (e.g.,GSM,LTE) also use packet switching. Packet switching is associated with connectionless networking because, in these systems, no connection agreement needs to be established between communicating parties prior to exchanging data.
X.25, the internationalCCITT standard of 1976, is a notable use of packet switching in that it provides to users a service offlow-controlledvirtual circuits. These virtual circuits reliably carry variable-length packets with data order preservation.DATAPAC in Canada was the first public network to support X.25, followed byTRANSPAC in France.[146]
Asynchronous Transfer Mode (ATM) is another virtual circuit technology. It differs from X.25 in that it uses small fixed-length packets (cells), and that the network imposes noflow control to users.
Technologies such as MPLS and theResource Reservation Protocol (RSVP) create virtual circuits on top of datagram networks. MPLS and its predecessors, as well as ATM, have been called "fast packet" technologies. MPLS, indeed, has been called "ATM without cells".[147] Virtual circuits are especially useful in building robust failover mechanisms and allocating bandwidth for delay-sensitive applications.
Thislist of packet-switched networks is divided into three overlapping eras: early, isolated, networks before the introduction ofX.25; the X.25 era when manypostal, telephone, and telegraph (PTT) companies providedpublic data networks with worldwide reach; and the modernInternet era, which initiallycompeted with theOSI model.
The work ofDonald Davies in the late 1960s ondata communication andcomputer network design became well known in the United States, Europe and Japan. This was the "cornerstone" that inspired numerous packet switching networks in the decade following. (Full article...)
Historians credit seminal insights to Welsh scientist Donald W. Davies and American engineer Paul Baran
Paul Baran, an engineer celebrated as the co-inventor (along with Donald Davies) of the packet switching technology that is the foundation of digital networks
The 1960 challenge was to build a network such that a significant subset of the network could survive a military attack. [Baran] told us he knew he could design a solution once he realized that, 'given redundant paths, the reliability of the net work could be greater than the reliability of the parts.' ... In his first draft dated Nov. 10, 1965, Davies forecast today's 'killer app' for his new communication service: 'The greatest traffic could only come if the public used this means for everyday purposes such as shopping... People sending enquiries and placing orders for goods of all kinds will make up a large section of the traffic... Business use of the telephone may be reduced by the growth of the kind of service we contemplate.'
Essentially all the work was defined by 1961, and fleshed out and put into formal written form in 1962. The idea of hot potato routing dates from late 1960.
As Kahn recalls: ... Paul Baran's contributions ... I also think Paul was motivated almost entirely by voice considerations. If you look at what he wrote, he was talking about switches that were low-cost electronics. The idea of putting powerful computers in these locations hadn't quite occurred to him as being cost effective. So the idea of computer switches was missing. The whole notion of protocols didn't exist at that time. And the idea of computer-to-computer communications was really a secondary concern.
Baran had put more emphasis on digital voice communications than on computer communications.
Paul Baran ... focused on the routing procedures and on the survivability of distributed communication systems in a hostile environment, but did not concentrate on the need for resource sharing in its form as we now understand it; indeed, the concept of a software switch was not present in his work.
{{cite book}}:ISBN / Date incompatibility (help). "the first paper on time-shared computers by C. Strachey at the June 1959 UNESCO Information Processing conference".Mathematicians had already developed methods of analysing traffic jams - 'queueing theory' ... - but it needed new a insight to solve the problem of how to avoid bottle-necks between computers.
all users of the network will provide themselves with some kind of error control ... Computer developments in the distant future might result in one type of network being able to carry speech and digital messages efficiently.
Roger Scantlebury ... from Donald Davies' team ... presented a detailed design study for a packet switched network. It was the first Roberts had heard of it. ... Roberts also learned from Scantlebury, for the first time, of the work that had been done by Paul Baran at RAND a few years earlier.
It was a seminal meeting as the NPL proposal illustrated how the communications for such a resource-sharing computer network could be realized.
[Scantlebury said] We referenced Baran's paper in our 1967 Gatlinburg ACM paper. You will find it in the References. Therefore I am sure that we introduced Baran's work to Larry (and hence the BBN guys).
they lacked one vital ingredient. Since none of them had heard of Paul Baran they had no serious idea of how to make the system work. And it took an English outfit to tell them. ... Larry Roberts paper was the first public presentation of the ARPANET concept as conceived with the aid of Wesley Clark ... Looking at it now, Roberts paper seems extraordinarily, well, vague.
Scantlebury and his companions from the NPL group were happy to sit up with Roberts all that night, sharing technical details and arguing over the finer points.
The NPL group influenced a number of American computer scientists in favor of the new technique, and they adopted Davies's term "packet switching" to refer to this type of network. Roberts also adopted some specific aspects of the NPL design.
the ARPA network is being implemented using existing telegraphic techniques simply because the type of network we describe does not exist. It appears that the ideas in the NPL paper at this moment are more advanced than any proposed in the USA
Roger actually convinced Larry that what he was talking about was all wrong and that the way that NPL were proposing to do it was right. I've got some notes that say that first Larry was sceptical but several of the others there sided with Roger and eventually Larry was overwhelmed by the numbers.
Larry Roberts presented a paper on early ideas for what was to become ARPAnet. This was based on a store-and-forward method for entire messages, but as a result of that meeting the NPL work helped to convince Roberts that packet switching was the way forward.
The system first went 'live' early in 1969
The first packet-switching network was implemented at the National Physical Laboratories in the United Kingdom. It was quickly followed by the ARPANET in 1969.
Leonard Kleinrock: Donald Davies ... did make a single node packet switch before ARPA did
The 1967 Gatlinburg paper was influential on the development of ARPAnet, which might otherwise have been built with less extensible technology. ... Davies was invited to Japan to lecture on packet switching.
The feasibility studies continued with an attempt to apply queuing theory to study overall network performance. This proved to be intractable so we quickly turned to simulation.
He decided to use packet switching as the underlying technology of the Arpanet; it remains central to the function of the internet. And it was Dr. Roberts's decision to build a network that distributed control of the network across multiple computers. Distributed networking remains another foundation of today's internet.
Oops. Roberts knew Baran slightly and had in fact had lunch with him during a visit to RAND the previous February. But he certainly didn't remember any discussion of networks. How could he have missed something like that?
On Tuesday, 28 February 1967 I find a notation on my calendar for 12:00 noon Dr. L. Roberts.
Roberts' proposal that all host computers would connect to one another directly ... was not endorsed ... Wesley Clark ... suggested to Roberts that the network be managed by identical small computers, each attached to a host computer. Accepting the idea, Roberts named the small computers dedicated to network administration 'Interface Message Processors' (IMPs), which later evolved into today's routers.
W. Clark's message switching proposal (appended to Taylor's letter of April 24, 1967 to Engelbart)were reviewed.
Thus the set of IMP's, plus the telephone lines and data sets would constitute a message switching network
Roberts bought the idea and presented a some what vague paper about it at the ACM SIGOPS Symposium on Operating System Principles held in Gatlinburg, Tennessee in late 1967
Roberts was already becoming known as the fastest man in the Pentagon. ... And not for nothing was Larry Roberts known as the fastest man in the Pentagon. By the time they got to the airport, the decision had been made .... Once again, the fastest man in the Pentagon made his decision without hesitation
In 1965, Davies pioneered new concepts for computer communications in a form to which he gave the name "packet switching." ... The design of the ARPA network (ArpaNet) was entirely changed to adopt this technique.
Baran proposed a "distributed adaptive message-block network" [in the early 1960s] ... Roberts recruited Baran to advise the ARPANET planning group on distributed communications and packet switching.
Baran proposed a "distributed adaptive message-block network" [in the early 1960s] ... Roberts recruited Baran to advise the ARPANET planning group on distributed communications and packet switching. ... Roberts awarded a contract to Leonard Kleinrock of UCLA to create theoretical models of the network and to analyze its actual performance.
We propose that a working group of approximately four people devote some concentrated effort in the near future in defining the IMP precisely. This group would interact with the larger group from the earlier meetings from time to time. Tentatively we think that the core of this investigatory group would be Bhushan (MIT), Kleinrock (UCLA), Shapiro (SRI) and Westervelt (University of Michigan), along with a kibitzer's group, consisting of such people as Baran (Rand), Boehm (Rand), Culler (UCSB) and Roberts (ARPA).
BARAN: On Tuesday, 31 October 1967 I see a notation 9:30 AM to 2:00 PM for ARPA's (Elmer) Shapiro, (Barry) Boehm, (Len) Kleinrock, ARPA Network. On Monday, 13 November 1967 I see the following: Larry Roberts to abt (about?) lunch (time?). Art Bushkin = 1:00 PM. Here. Larry Roberts IMP Committee. On Thursday, 16 November 1967 I see 7 PM Kleinrock, UCLA - IMP Meeting.
Kahn, the principal architect
Significant aspects of the network's internal operation, such as routing, flow control, software design, and network control were developed by a BBN team consisting of Frank Heart, Robert Kahn, Severo Omstein, William Crowther, and David Walden
Although there was considerable technical interchange between the NPL group and those who designed and implemented the ARPANET, the NPL Data Network effort appears to have had little fundamental impact on the design of ARPANET. Such major aspects of the NPL Data Network design as the standard network interface, the routing algorithm, and the software structure of the switching node were largely ignored by the ARPANET designers. There is no doubt, however, that in many less fundamental ways the NPL Data Network had and effect on the design and evolution of the ARPANET.
Arpanet had its deficiencies, however, for it was neither a true datagram network nor did it provide end-to-end error correction.
In fact, CYCLADES, unlike ARPANET, had been explicitly designed to facilitate internetworking; it could, for instance, handle varying formats and varying levels of service
In addition to the NPL Network and the ARPANET, CYCLADES, an academic and research experimental network, also played an important role in the development of computer networking technologies
In the early 1970s Mr Pouzin created an innovative data network that linked locations in France, Italy and Britain. Its simplicity and efficiency pointed the way to a network that could connect not just dozens of machines, but millions of them. It captured the imagination of Dr Cerf and Dr Kahn, who included aspects of its design in the protocols that now power the internet.
Two significant packet networks preceded the TCP/IP Internet: ARPANET and CYCLADES. The designers of the Internet borrowed heavily from these systems, especially CYCLADES ... The first end-to-end research network was CYCLADES, designed by Louis Pouzin at IRIA in France with the support of BBN's Dave Walden and Alex McKenzie and deployed beginning in 1972.
The original ARPANET design had made data integrity part of the IMP's store-and-forward role, but Cyclades end-to-end protocol greatly simplified the packet switching operations of the network. ... The idea was to adopt several principles from Cyclades and invert the ARPANET model to minimise international differences.
The authors wish to thank a number of colleagues for helpful comments during early discussions of international network protocols, especially R. Metcalfe, R. Scantlebury, D. Walden, and H. Zimmerman; D. Davies and L. Pouzin who constructively commented on the fragmentation and accounting issues; and S. Crocker who commented on the creation and destruction of associations.
In mathematical modelling use is made of the theories of queueing processes and of flows in networks, describing the performance of the network in a set of equations. ... The analytic method has been used with success by Kleinrock and others, but only if important simplifying assumptions are made. ... It is heartening in Kleinrock's work to see the good correspondence achieved between the results of analytic methods and those of simulation.
Vint noted that UCLA's internet work is primarily theoretical research on throughput and delay analysis. This work is headed by L. Kleinrock.
Leonard Kleinrock's work became the basic reference in queuing theory for computer networks ... On Kleinrock's influence, see Frank, Kahn, and Kleinrock 1972, p. 265; Tanenbaum 1989, p. 631.
Hierarchical addressing systems for network routing have been proposed by Fultz and, in greater detail, by McQuillan. A recent very full analysis may be found in Kleinrock and Kamoun.
The hierarchical approach is further motivated by theoretical results (e.g., [16]) which show that, by optimally placing separators, i.e., elements that connect levels in the hierarchy, tremendous gain can be achieved in terms of both routing table size and update message churn. ... [16] KLEINROCK, L., AND KAMOUN, F. Hierarchical routing for large networks: Performance evaluation and optimization. Computer Networks (1977).
Then in June 1966, Davies wrote a second internal paper, "Proposal for a Digital Communication Network" In which he coined the word packet,- a small sub part of the message the user wants to send, and also introduced the concept of an "Interface computer" to sit between the user equipment and the packet network.
It is more difficult to establish at this time, however, whether Larry intended to switch the fragments as independent packets in the ARPAnet before he heard of the NPL work; certainly he now claims that this was always his intention.
The above description of how packet-switching came to be is the most widely-accepted one. However, there is an alternative version. Roberts claimed in later years that by the time of the Gatlinburg symposium, he already had the basic concepts of packet-switching well in mind, and that they originated with his old colleague Len Kleinrock, who had written about them as early as 1962, as part of his Ph.D. research on communication nets. It requires a great deal of squinting to extract anything resembling packet-switching from Kleinrock's work, however, and no other contemporary textual evidence that I have come across backs the Kleinrock/Roberts account.
{{citation}}: CS1 maint: multiple names: authors list (link)The Internet is really the work of a thousand people," Mr. Baran said. "And of all the stories about what different people have done, all the pieces fit together. It's just this one little case that seems to be an aberration.
I can find no evidence that he understood the principles of packet switching.
Leonard Kleinrock and Lawrence (Larry) Roberts, neither of whom were directly involved in the invention of packet switching ... Dr Willis H. Ware, Senior Computer Scientist and Research at the RAND Corporation, notes that Davies (and others) were troubled by what they regarded as in appropriate claims on the invention of packet switching
{{cite journal}}: CS1 maint: multiple names: authors list (link)...there were all sorts of crazy ideas about, and most of them didn't make any sense. There was this 'hot potato' routing which somebody was advocating, which was just crazy.
He developed the mathematical theory of data networks, the technology underpinning the Internet, while a graduate student at MIT in the period from 1960-1962. In that work, he also modeled the packetization of messages and solved for a key performance gain that packetization provides.
Aside from the technical problems of interconnecting computers with communications circuits, the notion of computer networks had been considered in a number of places from a theoretical point of view. Of particular note was work done by Paul Baran and others at the Rand Corporation in a study "On Distributed Communications" in the early 1960's. Also of note was work done by Donald Davies and others at the National Physical Laboratory in England in the mid-1960's. ... Another early major network development which affected development of the ARPANET was undertaken at the National Physical Laboratory in Middlesex, England, under the leadership of D. W. Davies.
