Overview
One of the early computer networking designs, the ALOHA network was created at the University of Hawaii in 1970 under the leadership of Norman Abramson and others. The idea was to use low-cost ham radio-like systems to create a computer network linking the far-flung campuses of the University. The original version of ALOHA used two distinct frequencies in a hub/star configuration, with the hub machine broadcasting packets to everyone on the "outbound" channel, and the various client machines sending data to the hub on the "inbound" channel. Data received was immediately re-sent, allowing clients to determine whether or not their data had been received properly. Any machine noticing corrupted data would wait a short time and then re-send the packet. This mechanism was also used to detect and correct for "collisions" created when two client machines both attempted to send a packet at the same time.
Like the ARPANET group, ALOHA was important because it used a shared medium for transmission. This revealed the need for more modern contention management schemes such as CSMA/CD, used by Ethernet. Unlike the ARPANET where each node could only talk to a node on the other end of the wire, in ALOHA all nodes were communicating on the same frequency. This meant that some sort of system was needed to control who could talk at what time. ALOHA's situation was similar to 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. Because data was sent via a teletype the data rate usually did not go beyond 80 characters per second. When two stations tried to talk at the same time, both transmissions were garbled. Then data had to be manually resent. ALOHA proved that it was possible to have a useful network without solving this problem, and this sparked interest in others, most significantly Bob Metcalfe and other researchers working at Xerox PARC. This team went on to create the Ethernet protocol.
The ALOHA protocol
The Aloha protocol is an OSI layer 2 protocol for LAN networks with broadcast topology.
The first version of 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 critical aspect is the later concept. What is later? The quality of the backoff scheme chosen significantly influences the efficiency of the protocol and the predicatibility of its behavior.
The difference between Aloha and Ethernet on a shared medium is that Ethernet uses CSMA/CD: It uses a jamming signal to notify all computers connected to the channel that a collision occurred, forcing computers on the network to reject their current packet or frame.
Pure Aloha had a maximum throughput of about 18.4%. This means that about 81.6% of the total available bandwidth was essentially wasted due to losses from packet collisions. The basic throughput calculation involves the assumption that the aggregate arrival process follows a Poisson distribution with an average number of arrivals of 2G arrivals per 2X seconds. Therefore, the lambda parameter in the Poisson distribution becomes 2G. The mentioned peak is reached for G = 0.5 resulting in a maximum throughput of 0.184, i.e. 18.4%.
An improvement to the original Aloha protocol was Slotted Aloha, which introduced discrete timeslots and increased the maximum throughput to 36.8%. A station can send only at the beginning of a timeslot, and thus collisions are reduced. In this case, the average number of aggregate arrivals is G arrivals per 2X seconds. This leverages the lambda parameter to be G. The maximum throughput is reached for G = 1.
It should be noted that Aloha's characteristics are still not much different from those experienced today by Wi-Fi, and similar contention-based systems that have no carrier sense capability. There is a certain amount of inherent inefficiency in these systems. For instance 802.11b sees about a 2-4 Mbit/s real throughput with a few stations talking, versus its theoretical maximum of 11 Mbit/s. It is typical to see these types of networks' throughput break down significantly as the number of users and message burstiness increase. For these reasons, applications which need highly deterministic load behavior often use token-passing schemes (such as token ring) 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.
Because Listen before send (CSMA - Carrier Sense Multiple Access), as used in the Ethernet, works a lot better than Aloha for all cases where all the stations can hear each other, Slotted Aloha is used on low bandwidth tactical Satellite communications networks by the US Military, subscriber based Satellite communications networks, and contactless RFID technologies.