Internet history: ARPANET - package

ARPA computer network diagram for June 1967. An empty circle is a computer with access sharing, a circle with a line is a single-user terminal


By the end of 1966, Robert Taylor, for money, ARPA launched a project to link many computers into a single system, inspired by the idea of ​​the " intergalactic network " of Joseph Karl Robnett Liclayder .

Responsibility for the execution of the project Taylor passed into the capable hands of Larry Roberts . In the ensuing year, Roberts made several critical decisions that would later respond to the technical architecture and culture of ARPANET and its followers, in some cases - even for several decades. The first decision on importance, although not in chronology, was to determine the mechanism for routing messages from one computer to another.

Problem

If computer A wants to send a message to computer B, how can this message find a path from one to another? In theory, it is possible to allow each node of a communication network to communicate with everyone else, connecting each node with each physical cable. To communicate with B, computer A will simply send a message via an outgoing cable connecting it to B. Such a network is called fully connected. However, for any significant network size, this approach quickly becomes impractical, since the number of connections increases as the square of the number of nodes (to be exact, as (n ² - n) / 2).
')
Therefore, some method of constructing the route of the message is required, which would send it further to the target upon arrival of the message to the intermediate node. In the early 1960s, two basic approaches to solving this problem were known. The first is the message switching method through storage and transmission. This approach was used by the telegraph system. When a message arrived at an intermediate node, it was temporarily stored there (usually in the form of paper tape) until it was possible to transfer it further to the target, or to another intermediate center closer to the target.

Then a phone appeared, and a new approach was required. A delay of several minutes after each statement made on the phone, which had to be decrypted and transmitted to the destination, would give the impression of a conversation with the interlocutor on Mars. Instead, the phone used circuit switching. The caller started each call by sending a special message indicating who he wants to call. At first they did this by talking to the operator, and then dialing the number that was processed by the automatic equipment on the switch. An operator or equipment installed a dedicated electrical connection between the caller and the called party. In the case of long-distance calls, this could require several iterations connecting the call through several switches. After the connection was established, the conversation itself could begin, and the connection was maintained until one of the parties interrupted it by hanging up.

The digital connection, which was decided to use in the ARPANET to connect computers working under the time-sharing scheme, used the features of both the telegraph and the telephone. On the one hand, data messages were transmitted in separate packets, as in the telegraph, and not in the form of continuous conversations on the phone. However, these messages could be of different sizes for different purposes, from console commands of several characters in length to large data files transferred from one computer to another. If the files were delayed in transit, no one complained about it. But remote interactivity required a quick response, as with a phone call.

One important difference between computer data networks on the one hand, and a telegraph telephone on the other, was sensitivity to errors in the data processed by the machines. A change or loss in the transmission of one character in a telegram, or the disappearance of a part of a word in a telephone conversation, could hardly seriously disrupt the communication of two people. But if the line noise switched a single bit from 0 to 1 in the command sent to the remote computer, this could completely change the meaning of the command. Therefore, each message had to be checked for errors, and re-sent if they were detected. Such repetitions would be too costly for large messages, and the likelihood of errors in them was greater because they were transmitted longer.

The solution to this problem came through two independent events that occurred in 1960, but the one that emerged later was seen first by Larry Roberts and ARPA.

A meeting

In the fall of 1967, Roberts arrived in Gatlinburg, Tennessee, due to the wooded summits of the Great Smoky Mountains, to deliver a document telling about ARPA's plans to deploy the network. He had been working for the Information Technology Office (IPTO) for almost a year, but many of the details of the network design were still very vague, including the solution to the routing problem. In addition to the vague references to blocks and their sizes, the only reference to her in Roberts’s work was a brief and evasive remark at the very end: “It seems necessary to hold the periodically used communication line to get the responses from one-tenth to one second needed for interactive work. This is very costly in terms of network resources, and unless we can make calls faster, message switching and concentration will become very important for network participants. ” Obviously, by that time, Roberts had not yet decided whether to abandon the approach he used in conjunction with Tom Marrill in 1965, that is, to connect computers through a switched telephone network via autodialing.

Coincidentally, another person was present at the same symposium, with a much better thought out solution to the problem of routing in data networks. Roger Scantlebury crossed the Atlantic, arriving at the British National Physical Laboratory of the British National Physical Laboratory (NPL) with a report. Scantlebury took Roberts to the side after his report, and told him about his idea of packet switching . This technology was developed by its head at the NPL, Donald Davis. In the USA, the achievements and the history of Davis are poorly known, although in the fall of 1967 the Davis group from the NPL was at least a year ahead of the ARPA with its ideas.

Davis, like many of the early pioneers of electronic computers, was a physicist by education. He graduated from Imperial College in London in 1943 at the age of 19, and was immediately accepted into a secret nuclear weapons development program, codenamed Tube Alloys . There he led a group of computer people who used mechanical and electrical calculators to quickly issue numerical solutions to problems related to nuclear fusion (its leader was Emil Julius Klaus Fuchs , a German expatriate physicist who by that time had already begun to transmit secrets of nuclear weapons in the USSR ). After the war, from mathematician John Vomersli, he heard about the project that he supervised in the NPL - it was the creation of an electronic computer that had to perform all the same calculations at a much higher speed. The computer designed by Alan Turing was called ACE, the “automatic computing machine.”

Davis seized on this idea, and hired himself at the NPL as quickly as he could. Having contributed to the detailed design and creation of the ACE computer, he remained deeply involved in the field of computers as a research leader in the NPL. In 1965, it happened that he was in the United States at a professional meeting related to his work, and used this opportunity to visit several large computer time-sharing locations to see what all the fuss is about. In the British computing environment, time sharing in the American sense of interactive computer sharing among several users was not known. Instead, their time sharing meant distributing the load on a computer among several batch processing programs (so that, for example, one program works while the other is busy reading from the tape). Then this option will be called multiprogramming.

Davis' travels led him to the Project MAC at MIT, the JOSS Project from the RAND Corporation in California, and to the Dartmouth time-sharing system in New Hampshire. On the way home, one of his colleagues suggested holding a sharing seminar to tell the British community about new technologies that they learned about in the US. Davis agreed, and hosted many of the main figures in the American computing industry, including Fernando José Corbato (the creator of the “compatible time-sharing system” at MIT) and Larry Roberts himself.

During the seminar (or, perhaps, immediately after) Davis was struck by the idea that the time-sharing philosophy can be applied to computer communication lines, and not just to the computers themselves. Time-sharing computers give each user a small amount of processor time, and then switch to another, creating the illusion of having their own interactive computer for each user. Likewise, by cutting each message into pieces of standard size, which Davis called “packages,” one communication channel can be shared among multiple computers or users of one computer. Moreover, this would solve all aspects of data transmission, for which telephone and telegraph switches were poorly adapted. A user working with an interactive terminal, sending short commands and receiving short answers, will not be blocked by transferring a large file, since this transmission will be split into many packets. Any damage in such large messages will affect a single packet that can be easily re-transmitted to complete the message.

Davis described his ideas in an unpublished work from 1966, “A Proposal for a Digital Communication Network”. At that moment, the most advanced telephone networks were on the verge of switching computers, and Davis proposed to embed packet switching into a new generation telephone network, creating a single broadband communications network capable of serving various requests, from simple telephone calls to remote access to computers. By then, Davis was promoted to NPL manager, and he formed a digital communications team led by Scantlebury to implement his project and create a working demo version.

In the year preceding the Gatlinburg conference, the Scantlebury team worked through all the details of creating a packet-switched network. The failure of a single node could be experienced with adaptive routing capable of working with multiple paths to the destination, and the failure of a single packet could be solved by its re-sending. Simulation and analysis said that the optimal packet size would be 1000 bytes - if it is made much smaller, the bandwidth expenses on the metadata in the header will be too large, much more - and the response time for interactive users will increase too often due to large messages .


Scantlebury’s work contained such details as the package format ...


... and analysis of the effect of packet size on network latency.

Meanwhile, the search for Davis and Scantlebury led to the discovery of detailed research work done by another American who had come to a similar idea a few years before. But at the same time, Paul Baran , an electrical engineer from RAND Corporation, did not even think about the needs of computer users with time sharing. RAND was a think tank that worked for the US Department of Defense in Santa Monica, California, created after World War II for long-term planning and analysis of strategic issues for military needs. Baran’s goal was to postpone a nuclear war, creating a very reliable military communications network capable of surviving even a large-scale nuclear attack. Such a network would make a preemptive strike from the USSR less attractive, since it would be very difficult to destroy the ability of the United States to respond to strike at several sensitive points. For this, Baran proposed a system that breaks messages into what he called message blocks that could be independently transmitted over a network of communication nodes with an excess number of connections, and then put together at the end point.

ARPA had access to Baran's volume reports for RAND, but since they were not related to interactive computers, their importance for ARPANET was not obvious. Roberts and Taylor, apparently, did not even notice them. Instead, as a result of one random meeting, Scantlbury presented everything to Roberts on a silver platter: a well-thought-out commutation mechanism, applicability to the task of creating interactive computer networks, reference materials from RAND, and even the name “package”. NPL's job also convinced Roberts that organizing a good bandwidth would require higher speeds, so he updated his plans to communication lines at 50 Kbps. To create an ARPANET, the fundamental part of the routing problem has been resolved.

True, there is another version of the emergence of the idea of ​​packet switching. Roberts later claimed that he already had similar thoughts in his head, thanks to the work of his colleague, Lena Kleinrock, who allegedly described this concept back in 1962, in his doctoral dissertation on communication networks. However, it is incredibly difficult to extract a similar idea from this work, and besides, I could not find any other evidence of this version.

Networks that were not

As we can see, as many as two teams were ahead of ARPA in the matter of developing packet switching, a technology that turned out to be so effective that it now forms the basis of almost all communications. Why is ARPANET the first significant network to use it?

It's all about organizational intricacies. ARPA did not have an official permission to create a communications network, however there were a large number of research centers already available with their computers, a culture of “free” morals, which almost no one looked after, and whole mountains of money. Taylor’s initial request of 1966 for the creation of an ARPANET voiced a figure of $ 1 million, and Roberts continued to spend so much every year from 1969 onwards to create and operate this network. At the same time, for ARPA, such money was a trifle, so none of his superiors were worried about what Roberts was doing with them, as long as it could be at least somehow attracted to the needs of national defense.

Barran in RAND had neither the capacity nor the authority to do anything. His work was purely research and analytical, and it could, if desired, be applied to defense. In 1965, RAND actually recommended its Air Force system, and they agreed on the viability of the project. But its implementation fell on the shoulders of the defense communications agency, and there they were not particularly versed in digital communications. Baran convinced the authorities at RAND that it would be better to take this offer than to allow it to be implemented anyway, and ruin the reputation of distributed digital communication.

Davis as head of the NPL had a far greater power than Baran, but a more limited budget than ARPA, and he did not have a ready-made social and technical network of research computers. He managed to create a prototype of a local packet-switched network (there was only one node, but many terminals) in the NPL in the late 1960s, with a modest budget of £ 120,000 over three years. ARPANET spent about half of this amount annually on the operation and maintenance of each of the many network nodes, excluding the initial investment in hardware and software. The organization capable of creating a large-scale British packet-switched network was British Post, which ran telecommunications networks in the country, except for direct mail services. Davis managed to get some influential officials interested in his ideas about the united digital network of national scale, but it was not in his power to change the direction of movement of such a huge system.

Liklider, combining luck and planning, found an excellent greenhouse where his intergalactic network could bloom. In this case, it cannot be argued that everything, except for packet switching, ran into money. Played the role and execution of the idea. Moreover, the spirit of ARPANET identified several other important decisions at the design stage. Therefore, we will look further at how responsibility was distributed between the computers that sent and received messages, and the network over which they sent these messages.

What else to read

• Janet Abbate, Inventing the Internet (1999)
• Katie Hafner and Matthew Lyon, Where Wizards Stay Up Late (1996)
• Leonard Kleinrock, “An Early History of the Internet,” IEEE Communications Magazine (August 2010)
• Arthur Norberg and Julie O'Neill, Transforming Computer Technology: Information Processing for the Pentagon, 1962-1986 (1996)
• M. Mitchell Waldrop, The Dream Machine: JCR Licklider and the Revolution This Made Computing Personal (2001)