The ARPA computer network diagram from June 1967. An empty circle represents a computer with access splitting, while a circle with a line represents a single-user terminal.
Other articles in the series:
- The History of Relays
- The History of Electronic Computers
- The History of the Transistor
- The History of the Internet
By the end of 1966 with ARPA's funding, a project to connect multiple computers into a single system was launched, inspired by the idea of “» .
Taylor entrusted the responsibility for executing the project to the capable hands of . In the following year, Roberts made several critically important decisions that would later resonate in the technical architecture and culture of ARPANET and its successors, in some cases even for decades. The first decision by importance, though not chronological, was determining the mechanism for routing messages from one computer to another.
The Problem
If computer A wants to send a message to computer B, how does that message find its way from one to the other? In theory, one could allow each node in the network to communicate with all others, connecting each node to every other via physical cables. To communicate with B, computer A would simply send the message down the outgoing cable connecting it to B. This type of network is called fully connected. However, with any significant size of the network, such an approach quickly becomes impractical, as the number of connections increases proportionally to the square of the number of nodes (specifically, as (n² - n) / 2).
Therefore, a method is needed to build a message route that, upon arrival at an intermediate node, would forward it towards its destination. In the early 1960s, two basic approaches were known to solve this problem. The first was the message switching method via 'store and forward.' This approach was used by telegraph systems. When a message arrived at an intermediate node, it was temporarily stored there (usually in the form of a paper tape) until it could be further transmitted to the destination, or to another intermediate center closer to the destination.
Then the telephone appeared, requiring a new approach. A delay of several minutes after each statement made over the phone that needed to be deciphered and delivered to its destination would feel like conversing with someone on Mars. Instead, the telephone used circuit switching. The caller began each call by sending a special message indicating whom they wanted to call. Initially, this was done by conversing with an operator, and later by dialing a number processed by automatic equipment at the switch. The operator or equipment established a dedicated electrical connection between the caller and the called party. For long-distance calls, this could require several iterations connecting the call through multiple switches. Once the connection was made, the conversation could begin, and it would remain active until one party hung up.
The digital communication that was decided to be used in ARPANET to connect computers operated on a scheme of , utilized features of both the telegraph and the telephone. On one hand, data messages were transmitted in separate packets, like on the telegraph, rather than as continuous conversations on the phone. However, these messages could vary in size for different purposes, from console commands a few characters long to large files being transmitted from one computer to another. If files were delayed in transit, nobody complained. But remote interactivity would require quick responses, just like a phone call.
One important distinction between data networks on one side and telephone and telegraph on the other was the sensitivity to errors in the data processed by machines. Changing or losing a single character in a telegram or dropping part of a word during a phone conversation was unlikely to seriously disrupt communication between two people. However, if noise on the line flipped a single bit from 0 to 1 in a command sent to a remote computer, it could completely change the meaning of the command. Therefore, every message needed to be checked for errors, and resent in case any were found. Such retransmissions would be too costly for large messages, and the likelihood of errors in them was greater since they took longer to transmit.
The solution to this problem came about due to two independent events that occurred in 1960, however, the one that emerged later was first noticed by Larry Roberts and ARPA.
Meeting
In the fall of 1967, Roberts arrived in Gatlinburg, Tennessee, from the heavily forested peaks of the Great Smoky Mountains, to deliver a document detailing ARPA's plans for network deployment. He had already been working for nearly a year in the Information Processing Technology Office (IPTO), but many details of the network project were still quite vague, including the routing problem. Aside from vague references to blocks and their sizes, the only mention of it in Roberts' work was a brief and evasive note at the very end: "It seems necessary to keep a periodically used communication line to receive responses within a time frame of one-tenth to one second, which is required for interactive work. This is quite costly in terms of network resources, and unless we gain the ability to call faster, message switching and concentration will become very important for network participants." Clearly, by that time Roberts had not yet decided whether to abandon the approach he had used with Tom Marryott in 1965, namely, connecting computers via the switched telephone network using autodial.
Coincidentally, another person was present at the same symposium, with a much better thought-out idea for solving routing problems in data networks. Roger Scantlebury crossed the Atlantic, arriving from the British National Physical Laboratory (NPL) to present his report. Scantlebury took Roberts aside after his presentation and shared his idea with him. . This technology was developed by his supervisor at NPL, Donald Davies. In the US, Davies' achievements and history are not well known, although in the fall of 1967, Davies' group at NPL was at least a year ahead of ARPA with their ideas.
Davies, like many early pioneers of electronic computers, was educated as a physicist. He graduated from Imperial College London in 1943 at the age of 19, and was immediately recruited into a secret program for developing nuclear weapons codenamed . There, he led a group of people-computers who used mechanical and electrical calculators to quickly provide numerical solutions to problems related to nuclear fusion (his supervisor was , a German expatriate physicist who had already begun passing nuclear weapon secrets to the USSR by that time). After the war, he heard from mathematician John Womersley about a project he was leading at NPL – the creation of an electronic computer that was supposed to perform all the same calculations at a much greater speed. was named ACE, "Automatic Computing Engine."
Davis seized on this idea and joined NPL as quickly as he could. Contributing to the detailed project and creation of the ACE computer, he remained deeply involved in the field of computing machines as a research leader at NPL. In 1965, he happened to be in the USA for a professional meeting related to his work, and took the opportunity to visit several major computer time-sharing sites to see what the fuss was about. In the British computing environment, time-sharing in the American sense of interactive concurrent use of a computer by multiple users was unknown. Instead, their time-sharing meant distributing the computer load among several batch processing programs (so that, for example, one program could run while another was busy reading from tape). Later, this option would be referred to as multiprogramming.
Davis's travels took him to Project MAC at MIT, the JOSS Project from RAND Corporation in California, and the Dartmouth Time-Sharing System in New Hampshire. On the way home, one of his colleagues suggested holding a seminar on sharing to inform the British community about the new technologies they had learned in the USA. Davis agreed and hosted many of the key figures in the American computing field, including (the creator of the 'compatible time-sharing system' at MIT) and Larry Roberts himself.
During the seminar (or perhaps immediately afterward), Davis was struck by the idea that the philosophy of time-sharing could be applied to communication lines as well as to the computers themselves. Time-sharing computers give each user a small slice of processing time and then switch to another user, creating the illusion for each user that they have their own interactive computer. Similarly, by chopping each message into standard-sized pieces that Davis called 'packets', one communication channel could be shared among multiple computers or users of a single computer. Moreover, this would solve all aspects of data transmission for which telephone and telegraph switches were poorly suited. A user working with an interactive terminal, sending short commands and receiving short responses, would not be blocked by the transfer of a large file, as this transfer would be split into many packets. Any damage in such large messages would affect only a single packet, which could easily be retransmitted to complete the message.
Davis described his ideas in an unpublished 1966 paper, 'Proposal for a Digital Communications Network'. At that time, the most advanced telephone networks were on the verge of computerizing switches, and Davis proposed to implement packet switching within a next-generation telephone network, creating a unified broadband communication network capable of serving various demands, from simple phone calls to remote access to computers. By that time, Davis had been promoted to manager of NPL, and he formed a digital communications group led by Scantlebury to carry out his project and create a working demonstration.
In the year leading up to the conference in Gatlinburg, the Scantlbury team worked out all the details of creating a packet-switched network. The failure of a single node could be managed through adaptive routing, which could work with multiple paths to the destination, while the loss of an individual packet could be resolved by resending it. Simulations and analysis indicated that an optimal packet size would be 1000 bytes – making it much smaller would lead to excessive overhead on the bandwidth due to the metadata in the headers, while making it much larger would frequently increase response times for interactive users due to the large messages.
The work of Scantlbury included such details as packet format…
…and the analysis of the impact of packet sizes on network delays.
Meanwhile, the searches by Davis and Scantlbury led to the discovery of detailed research conducted by another American who came to a similar idea a few years before them. However, , an electrical engineer from RAND Corporation, did not really consider the needs of time-sharing computer users. RAND was an analytical center funded by the U.S. Department of Defense in Santa Monica, California, established after World War II for long-term planning and analysis of strategic issues for military needs. Beardsley’s goal was to avert nuclear war by creating a highly reliable military communication network capable of surviving even a large-scale nuclear attack. Such a network would make a preemptive strike by the USSR less appealing, as it would be very difficult to destroy the U.S. capability to retaliate against multiple sensitive points. To achieve this, Beardsley proposed a system that broke messages into what he called message blocks that could be independently transmitted across a network of nodes with redundant connections and then reassembled at the endpoint.
ARPA had access to substantial reports from Baran for RAND; however, since they were not related to interactive computers, their significance for ARPANET was not evident. Roberts and Taylor apparently overlooked them. Instead, during 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 term 'packet'. NPL's work also convinced Roberts that organizing good bandwidth would require higher speeds, so he updated his plans to communication lines of 50 Kbps. The fundamental part of the routing problem for creating ARPANET was resolved.
Indeed, there is another version of how the idea of packet switching originated. Roberts later claimed that he had similar thoughts in his mind, influenced by the work of his colleague, Leonard 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 that work, and I couldn't find any other confirmations of this version.
Networks that never existed
As we can see, two entire teams got ahead of ARPA in developing packet switching, a technology that turned out to be so effective that it is now the foundation of virtually all communications. So why did ARPANET become the first significant network to use it?
It all comes down to organizational intricacies. ARPA did not have an official mandate to establish a communication network; however, there were many existing research centers with their own computers, a culture of 'free' morals, which was practically unchecked, and mountains of funding. Taylor's initial request in 1966 for funding to create ARPANET cited an amount of $1 million, and Roberts continued to spend that much each year from 1969 onwards to create and operate this network. For ARPA, such money was trivial, so none of his superiors were concerned with what Roberts was doing with it, as long as it could somehow be tied to national defense needs.
Behrens had neither the means nor the authority at RAND to do anything. His work was purely research and analytical, and it could, if desired, be applied to defense. In 1965, RAND actually recommended his system to the Air Force, and they agreed on the project's viability. But its implementation fell to the Defense Communications Agency, which was not particularly knowledgeable about digital communications. Behrens convinced his superiors at RAND that it was better to take the proposal than to allow it to be implemented haphazardly, jeopardizing the reputation of distributed digital communication.
Davis, as head of NPL, wielded much more power than Behrens, but had a more limited budget than ARPA, and he lacked an existing social and technical network of research computers. He managed to create a prototype local area network with packet switching (there was only one node, but many terminals) at NPL in the late 1960s, with a modest budget of £120,000 over three years. ARPANET spent about half that amount annually on operating and maintaining each of its numerous network nodes, excluding the initial investments in hardware and software. The British Post Office, which managed telecommunications networks in the country aside from postal communications, was the organization capable of creating a large-scale British packet-switched network. Davis managed to interest several influential officials with his ideas about a unified digital network on a national scale, but changing the direction of such a massive system was beyond his capabilities.
Licklider, by combining luck and planning, found a wonderful greenhouse where his intergalactic network could flourish. However, it cannot be claimed that everything but packet switching boiled down to money. The execution of the idea also played a role. Moreover, the spirit of ARPANET was defined by several other important design decisions. Therefore, we will further examine how the responsibility was distributed between the computers sending and receiving messages and the network over which they sent those messages.
Further reading
- 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: J.C.R. Licklider and the Revolution That Made Computing Personal (2001)
Source: habr.com
