ALOHA network

One of the early computer networking designs, the ALOHA network was created at the University of Hawaii (go figure) under the leadership of Norman Abramson. Like the ARPANET group, the ALOHA network was built with DARPA (Defense Advanced Research Projects Agency) funding. Also, similar to the ARPANET group, the ALOHA network was built to allow people in different locations to get access to the main computer systems. But while the ARPANET did this across leased phone lines, the ALOHA network did it across packet radio.

The ALOHA network was significant for a couple of reasons: One, the ALOHA network used a shared medium for transmission. As a product of this, the ALOHA protocol showed the need for more modern contention management schemes like those used by Ethernet, such as CSMA/CD. Unlike the ARPANET where each node could only talk to a node on the other end, in ALOHA everyone was using the same frequency. This meant that some sort of system for system for controlling who could talk when was needed. ALOHA's situation was similar to the same issues faced by modern Ethernet (non-switched) and Wi-Fi networks.

This shared transmission medium system generated interest by others. ALOHA's scheme was very simple. Becauase data was sent via a teletype the data rate usually did not go beyond 80 characters a second. When a station tried to talk at the same time as another the information got garbled across the radio, preventing either from talking. Then data had to be manually resent. Yet, while ALOHA did not solve this problem, it sparked interest in others. The most significant of these being Bob Metcalfe and other researchers working at the renowned Xerox PARC. This team would create one of the most critical technologies in modern networking, Ethernet.

The ALOHA protocol

in laymen's terms...

The protocol was basic:

If you have data to send, send the data
If the message collides with another transmission, try resending later

Many people have made a study of the protocol. The real kicker here is the later concept. What is later? Determining a good backoff scheme for the protocol also determines much of the total efficiency of the protocol, and how deterministic its behavior will be (how predictable will the protocol change as load changes). Modern Ethernet uses CSMA/CD.

ALOHA had about a 18.4% max throughput. This means that 81.6% of the total available bandwidth is basically being wasted due to stations trying to talk at the same time. (Sort of like a grade school classroom at recess) Slotted ALOHA was an improvement upon this, which gave the stations a discrete amount of time slots which they could use. This improved efficiency to about 36.8%

It should be noted that ALOHA's characteristics are still not much different than those experienced today by Ethernet, Wi-Fi and similar contention based systems. There is a certain amount of inherent inefficiency in these systems. For instance 802.11b sees about a 2-4 Mbps real throughput with a few stations talking, versus its theoritical maximum of 11 Mbps. It is typical to see these type network's throughput breakdown significantly as the number of users and message burstiness increase. For these reasons, applications which need highly deterministic load behavior often use token passing (like Token ring) schemes instead of contention systems. For instance ARCNET is very popular in embedded applications. Nonetheless, contention based systems also have significant advantages, including ease of management and speed in initial communication.

References:

http://www.nap.edu/readingroom/books/far/ch7.html
http://www.postech.ac.kr/cse/hpc/research/webcache/book/overview/history.htm
http://www.laynetworks.com/ALOHA%20PROTOCOL.htm
http://mars.mcs.kent.edu/ksuthesis/node19.html

Follow up information:

Original Work: N. Abramson, The Aloha System - Another Alternative for Computer Communications, Proceedings of Fall Joint Computer Conference, AFIPS Conference, 1970
http://www.isoc.org/internet/history/brief.shtml