Norman Abramson and ALOHAnet

Abstract

Norman Abramson (1932–2020) gave up an established career at Stanford and in 1966 joined the University of Hawaii, partly for the surf. There he led the team that built ALOHAnet, the first wireless packet data network, which went into operation in June 1971 and linked terminals around the Hawaiian islands to the university’s computer over UHF radio. Its central idea was the ALOHA protocol: every terminal transmits whenever it has something to send, and if two transmissions collide, both senders wait a random time and try again. Abramson showed that such a channel could carry at most about 18 percent of its raw capacity; Larry Roberts doubled that in 1972 by dividing time into slots. Random access of this kind became the basis of Ethernet, and every mobile phone still uses an ALOHA channel to announce itself to the network.

Norman Abramson. Image: Norman Abramson, public domain, via Wikimedia Commons.

Boston to Stanford

Norman Abramson was born on 1 April 1932 in Boston. He studied physics at Harvard (BA 1953) and UCLA (MA 1955), worked as a research engineer at Hughes Aircraft, and took a doctorate in electrical engineering at Stanford in 1958 with a thesis on applying the statistical “comparison of experiments” to radar detection and coding. He taught at Stanford from 1955 to 1965 and was a visiting professor at Berkeley before he moved to Hawaii in 1966.

Stanford was one of the best places in the world to work on communication theory, and Abramson later described his move as “a big gamble.” The University of Hawaii in 1966 had little research tradition in engineering. Its attraction, by Abramson’s own account in his oral history for the Computer History Museum, included the ocean: he was a surfer.

Themis

Money for research at a university like Hawaii came from a new Department of Defense programme called Themis, which funded work at what the Pentagon called “second-tier” universities. Abramson formed a team with two colleagues with strong backgrounds in coding theory, Wesley Peterson and Ned Weldon, and later with Franklin Kuo, and they went to the Advanced Research Projects Agency. ARPA’s Information Processing Techniques Office was then funding the ARPANET under Bob Taylor and Larry Roberts.

In 1967 Abramson met Taylor but could not yet say precisely what he wanted to do. The problem was concrete enough. The university’s IBM System/360 sat on Oahu, and its users were scattered over several islands; linking each terminal by leased or dial-up telephone line was expensive, and a dial-up circuit sat idle for most of the time a user was connected. Radio was the obvious medium. The conventional way to share a radio band was to give each user a channel of its own, by frequency or by time slot. In 1969 Abramson told Taylor and Roberts that this seemed “unduly limiting” for interactive computing, where a user typed a line, waited, read the answer and typed again, so that a dedicated channel stood idle almost all the time.

Late in 1969 the Hawaii group made its decision. All terminals would share a single radio channel. Each would send its data in short, high-speed bursts, packets, whenever it had something to send, without coordinating with anyone. If two packets overlapped and were garbled, the central station would not acknowledge them, and each sender, after waiting a random time, would send again.

The Network

The IEEE Milestone plaque for ALOHAnet at Holmes Hall, University of Hawaii at Mānoa. Image: Ron Hashiro, public domain, via Wikimedia Commons.

Development began in September 1968, and ALOHAnet went into operation in June 1971, the first public demonstration of a wireless packet data network. It used two 100-kilohertz channels in the UHF band: a random-access channel at 407.350 MHz on which terminals sent to the centre, and a broadcast channel near 413 MHz on which the centre sent to all terminals, both at 9,600 bits per second. The central station was an HP 2100 minicomputer with 32K words of core memory, which the team named the Menehune, “Hawaiian for IMP” as Kuo put it, after the ARPANET’s Interface Message Processors. It passed traffic to the university’s IBM 360 (later a 370/158) and to ALOHA’s own time-sharing computer, a BCC 500.

A packet consisted of a 32-bit header, a 16-bit header check, up to 80 bytes of data and a 16-bit data check, 704 bits in all; at 9,600 bits per second it took 73 milliseconds to send. Each terminal was connected through a Terminal Control Unit, a box containing the UHF antenna, transceiver, modem, buffer and control logic, which replaced the pair of modems, the dial-up line and the multiplexer port that a conventional connection needed. A later version used an Intel 8080 microprocessor. Because Hawaii’s mountains, high-rise buildings and foliage limited line-of-sight radio, the team built simple store-and-forward repeaters, and two of them extended the network from Oahu to other islands. At its peak about 40 users on Oahu and Maui were connected. Decades later, describing how a mobile phone joins its network, Abramson put it this way: “the very first thing you do is a packet comes from that telephone and the packet says ‘ALOHA.’”

Eighteen Percent

Abramson described the system in “The ALOHA System: Another Alternative for Computer Communications” at the Fall Joint Computer Conference in 1970, and the paper contained the result for which he is best known. If packets of fixed length are sent at random times by many independent users, a packet survives only if no other packet starts within one packet-length before or after it. Working through the probabilities, Abramson showed that the useful throughput of such a channel peaks at 1/(2e), about 0.184 of its raw capacity, when the offered traffic is half a packet per packet-time. Above that, collisions multiply and throughput falls. The Hawaii channel, Kuo calculated, could support between 100 and 500 active teletype users, depending on how much each typed.

Eighteen percent sounds wasteful, but it compared well with the alternative: a dedicated channel per teletype user was busy a much smaller fraction of the time. The analysis also showed where the losses came from. A collision could happen whenever two packets merely overlapped, so on average a packet was exposed for two packet-times.

Larry Roberts, who ran the ARPANET programme at ARPA, saw how to halve the exposure. In a note dated 26 June 1972, ARPA Satellite System Note 8, “ALOHA Packet System With and Without Slots and Capture,” he proposed dividing the channel into time slots one packet long and letting terminals start transmissions only at slot boundaries. Two packets then either collided completely or not at all, and the maximum throughput doubled to 1/e, about 36.8 percent. Roberts also analysed the capture effect, in which the stronger of two colliding signals is often received correctly anyway. The note circulated informally for years and was published in Computer Communication Review only in 1975. Abramson credited Roberts with both results. Will Crowther at BBN added reservation ALOHA in 1973, and Leonard Kleinrock and Fouad Tobagi at UCLA extended the analysis to carrier sense, in which a station listens before it transmits.

Satellites and Ethernet

In 1972 Abramson’s interest moved to satellites, which are broadcast channels by nature. On 17 December 1972 an ARPANET IMP linked ALOHA’s computer to the ARPANET through the Pacific Ocean INTELSAT IV satellite, making Hawaii the first operational satellite node of the ARPA network; the link was rented as a single voice channel, far cheaper than a land line would have been. With NASA’s Ames Research Center and the University of Alaska, the team ran packet broadcasting experiments over NASA’s ATS-1 satellite, whose ground stations used antennas as small as ten feet and electronics costing less than $5,000, against several million dollars for a standard INTELSAT earth station. In 1973 this became PacNet, linking a NASA facility in California with universities in Australia, Japan and the United States.

ALOHAnet itself was a research system. Abramson never tried to commercialize it, because operating a radio data network for the public would have meant years of dealing with the Federal Communications Commission. It ran until 1976.

Its ideas travelled. At Harvard, Bob Metcalfe had written a dissertation that analysed ALOHA’s behaviour under load; at Xerox PARC in 1973 he carried the same random-access idea onto a coaxial cable, added carrier sense and collision detection so that stations stopped transmitting as soon as they heard a collision, and called the result Ethernet (see Bob Metcalfe and Ethernet). ARPA’s packet radio network PRNET and its packet satellite network SATNET drew on the Hawaii experience too (see Vint Cerf and Bob Kahn). ALOHA random access was used in the Marisat maritime satellite system in the 1970s, in the signalling channels of mobile telephone networks from the 1980s, in GSM and in the random-access channels of later mobile standards, and in satellite and RFID systems.

Later Years

Abramson stayed at the University of Hawaii for three decades, as professor of electrical engineering and as chair of the Information and Computer Sciences Department, and consulted on communication, data and satellite networks for the International Telecommunication Union, UNESCO and the UN Development Programme. In his CHM interview he also described ideas he had worked out in the 1970s with Larry Roberts for something like a smartphone. After retiring in the mid-1990s he moved to San Francisco and co-founded Aloha Networks, where he was chief technology officer.

The recognition arrived late and in quantity. He was named an IEEE Fellow in 1980, received the IEEE Koji Kobayashi Computers and Communications Award in 1995, the Information Theory Society’s Golden Jubilee Award in 1998 for “the invention of the first random-access communication protocol,” the Technology Award of Germany’s Eduard Rhein Foundation in 2000, the IEEE Alexander Graham Bell Medal in 2007 and the NEC C&C Prize in 2011. In 2009 he looked back in IEEE Communications Magazine under the title “The ALOHAnet: Surfing for Wireless Data.” “I don’t think any of us thought it would be as important as it turned out to be,” he told IEEE’s The Institute. “It exceeded my wildest expectations.”

ALOHAnet was dedicated as an IEEE Milestone on 13 October 2020, at a ceremony in Holmes Hall that the COVID-19 pandemic had pushed back from June and that Abramson and Kuo joined by video. Abramson died at his home in San Francisco on 1 December 2020, aged 88, of skin cancer that had spread to his lungs.