Internet History: ARPANET - package

ARPA computer network diagram for June 1967. An empty circle - a computer with shared access, a circle with a dash - a terminal for one user


Towards the end of 1966, Robert Taylor, with money from ARPA, launched a project to connect many computers into a single system, inspired by the idea of Joseph Carl Robert Liklider's “ intergalactic network ” . Taylor transferred responsibility for the execution of the project to the capable hands of Larry Roberts . In the following year, Roberts made several critical decisions that will subsequently be echoed in the technical architecture and culture of ARPANET and its followers, in some cases even for several decades. The first decision in 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 be found from one to another? In theory, it is possible to allow each node of the communication network to communicate with all the others, by connecting physical nodes to each node with each other. To communicate with B, computer A simply sends a message over the outgoing cable connecting it to B. This 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 precise, as (n ² - n) / 2).

Therefore, a certain method of constructing a message route is required, which, upon arrival of the message at an intermediate node, would send it further to the target. In the early 1960s, two basic approaches to solving this problem were known. The first is the method of switching messages 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 a paper tape) until it became possible to transfer it further to the target, or to another intermediate center closer to the target.

Then the phone appeared, and a new approach was required. A delay of several minutes after each statement made over the phone, which had to be decrypted and transmitted to the destination, would give a feeling of conversation with an interlocutor located on Mars. Instead, the phone used circuit switching. The caller began each call by sending a special message indicating who he wants to call. At first, they did this by talking with the operator, and then dialing a number processed by automatic equipment on the switch. The operator or equipment established 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,

The digital communication, which it was decided to use in ARPANET to connect computers that worked according to 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 on a 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 several characters long, to large files with data 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, like a phone call.

One important difference between computer data networks on the one hand, and a telephone with a telegraph on the other, was the sensitivity to errors in data processed by machines. A change or loss during 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 noise on the line 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 resent if they were found. Such repetitions would be too costly for large messages, and the likelihood of errors in them was more, since they were transmitted longer.

The solution to this problem came thanks to two independent events that happened in 1960, however, those that appeared later were noticed first by Larry Roberts and ARPA.

A meeting

In the fall of 1967, Roberts arrived in Gatlinburg, Tenn., From behind the forested peaks of Great Smoky Mountains, to deliver a document telling about ARPA's plans to deploy the network. He had been working at the Information Processing Technology Office (IPTO) for almost a year, but many of the details of the network design were still quite vague, including the solution to the routing problem. In addition to vague references to the blocks and their sizes, the only reference to it in Roberts' work was a brief and evasive remark at the very end: “It seems necessary to keep a periodically used communication line to receive responses from one tenth to one second necessary for interactive work. This is very expensive in terms of network resources, and unless we can call 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 with Tom Marrill in 1965, that is, connecting computers through a dial-up telephone network using auto-dialing.

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

Davis, like many of the early pioneers of electronic computers, was a physicist by training. He graduated from Imperial College in London in 1943 at the age of 19, and was immediately admitted to a secret nuclear weapons development program, code-named Tube Alloys . There, he led a group of computer scientists 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 then had already begun to pass on the secrets of nuclear weapons to the USSR). After the war, from mathematician John Womersley, he heard about the project that he led in the NPL - it was the creation of an electronic computer that was supposed to perform all the same calculations at a much faster speed. Developed by Alan Turing, the computer was called ACE, "automatic computing machine."

Davis seized on this idea, and hired on the NPL as fast as he could. Contributing to the detailed design and creation of the ACE computer, he remained deeply involved in the field of computers as a research leader in 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-based locations with time sharing to see what all the fuss was about. In the British computing environment, time sharing in the American sense of interactive computer sharing between multiple users was not known. Instead, their time sharing meant the distribution of computer load between several batch processing programs (so that, for example, one program works, while the other is busy reading from the film). Then this option will be called multiprogramming.

Davis's wanderings led him to Project MAC at MIT, the JOSS Project from 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 workshop to tell the British community about the new technologies that they had learned about in the United States. Davis agreed, and hosted many of the major figures in the American computing field, including Fernando Jose Corbato (creator of the "compatible time-sharing system" at MIT) and Larry Roberts himself.

During the seminar (or, possibly, immediately after), Davis was struck by the idea that the philosophy of time sharing can be applied to the communication lines of computers, 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 for each user the illusion of having his own interactive computer. Likewise, by cutting each message into pieces of standard size, which Davis called “packets,” one communication channel can be shared between multiple computers or users of the same computer. Moreover, this would solve all aspects of data transmission for which telephone and telegraph switches were poorly adapted. Interactive terminal user sending short commands and receiving short responses will not be blocked by the transfer of a large file, since this transfer will be split into many packets. Any damage in such large messages will affect a single packet that can easily be retransmitted to complete the message.

Davis described his ideas in an unpublished work from 1966, "An Offer for a Digital Communications Network." At that time, the most advanced telephone networks were on the verge of computerization of switches, and Davis proposed to integrate packet switching into a new generation telephone network, creating a single broadband communication network capable of handling various requests, from simple phone calls to remote access to computers. By then, Davis had been promoted to NPL manager, and he formed a digital communications team led by Scantlebury to implement his project and create a working demo.

In the year leading up to the Gatlinburg conference, the Scantlebury team worked out all the details of creating a packet-switched network. One node could fail through adaptive routing, capable of working with several paths to the destination, and a single packet could be resolved by resending it. Simulation and analysis said that the optimal packet size would be 1000 bytes — if you make it much smaller, then the line throughput costs for the metadata in the header will be too large, much longer — and the response time for interactive users will increase too often due to large messages .


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


... and an analysis of the effect of packet sizes on network delays.

Meanwhile, Davis and Scantlebury searches led to the discovery of detailed research work done by another American who came up with a similar idea several years before them. But at the same time Paul Beran, an electrical engineer at RAND Corporation, never thought about the needs of computer users with time sharing. RAND was a think tank funded by the US Department of Defense in Santa Monica, California, created after World War II to long-term plan and analyze strategic issues for the military. Beran’s goal was to delay a nuclear war by creating a very reliable military communications network that could survive 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 hit several sensitive points in response. For this, Beran proposed a system that breaks down messages into what he called message blocks,

ARPA had access to Baran’s voluminous reports for RAND, but since they weren’t connected to interactive computers, their importance to ARPANET was not obvious. Roberts and Taylor, apparently, were never noticed. Instead, as a result of a chance meeting, Scantlebury presented everything to Roberts on a silver platter: a well-thought-out switching mechanism, applicability to the task of creating interactive computer networks, reference materials from RAND, and even the name “package”. NPL’s work also convinced Roberts that it would require higher speeds to get good bandwidth, so he updated his plans to 50 kbps links. To create ARPANET, the fundamental part of the routing problem was solved.

True, there is another version 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, Len Kleinrock, who allegedly described this concept back in 1962, in his doctoral dissertation on communication networks. However, it is incredibly difficult to extract such an idea from this work, and besides, I could not find any other evidence for this version.

Networks that were not

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

It's all about organizational subtleties. ARPA did not have official permission to create a communication network, but there were a large number of research centers with their own computers, a culture of "free" morals that almost no one looked at, and mountains of money. Taylor’s initial request from 1966 for funds to create ARPANET announced 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, such money was a trifle for ARPA, so none of its bosses was worried about what Roberts was doing with them, as long as it could at least somehow be pulled to the needs of the national defense.

Baran at RAND had neither the ability nor the authority to do anything. His work was purely research and analytical, and it could be applied to defense if desired. In 1965, RAND actually recommended its Air Force system, and they agreed with 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. Beran convinced the RAND authorities that it would be better to pick up this offer than to let him realize it anyhow and ruin the reputation of distributed digital communications.

Davis, as the head of the NPL, had much more power than Baran, but a more limited budget than the ARPA, and he did not have a ready-made social and technical network from research computers. He managed to create a prototype 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 each year 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 operated telecommunications networks in the country, except for direct mail.

Liklider, combining luck and planning, found a beautiful greenhouse where his intergalactic network could flourish. At the same time, it cannot be argued that everything, except packet switching, rested on money. The role and execution of the idea also played. Moreover, the spirit of ARPANET was also determined by several other important decisions at the design stage. Therefore, we will further examine how responsibility was distributed between the computers that sent and received messages and the network through 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 That Made Computing Personal (2001)