Aloha random access
| Norman Abramson (2009), Scholarpedia, 4(10):7020. | doi:10.4249/scholarpedia.7020 | revision #90956 [link to/cite this article] |
Aloha random access is a widely used technique for coordinating the access of large numbers of intermittent transmitters in a single shared communication channel. In an ALOHA channel each transmitter sharing the channel transmits data packets at random times. In most ALOHA channels the transmitters then rely on some protocol (such as repetition) to handle the case of packets lost due to interference by other packets. An ALOHA channel may also just provide a best effort delivery mechanism and leave it to the receiver to deal with lost packets.
Contents |
History
ALOHA channels were originally analyzed and implemented in the AlohaNet at the University of Hawaii in 1970. The AlohaNet utilized UHF radio channels to connect computer resources on the islands of Oahu, Maui and Hawaii in the state of Hawaii (Abramson, 1970). In 1973 ALOHA was demonstrated in PacNet, a Pacific Ocean experimental satellite network involving NASA, the University of Hawaii and the University of Alaska, Tohoku University and the University of Electro-Communications in Japan, and the University of Sydney in Australia (Abramson, 1985). An ALOHA random access channel was used by Dr. Robert Metcalfe in 1973 as the basis of the Xerox cable-based Alto ALOHA Network later renamed and developed as Ethernet by 3COM (Metcalfe and Boggs, 1976). Since the 1980’s ALOHA has been the primary random access mechanism utilized by mobile telephone networks, satellite data networks, DOCSIS based cable data networks, Ethernet, WiFi and WiMAX.
Operation of an ALOHA Channel
An ALOHA channel provides access to a common communication channel from multiple independent packet transmitters by the simplest of all mechanisms. When each transmitter is ready to transmit its packet, it simply transmits the packet burst without any coordination with other transmitters using the shared channel. If each user of the ALOHA channel is required to have a low duty cycle, the probability of a packet from one user overlapping and thus interfering with a packet from another user is small as long as the total number of users on the shared ALOHA channel is not too large. As the number of users on the shared ALOHA channel increases the number of packet overlaps increase and the probability that a packet will be lost due to an overlap with another packet on the same channel also increases.
The key question of how many such users can share an ALOHA random access channel is dealt with in Section 4.
Throughput of an ALOHA Channel
The start times of the packets in an ALOHA channel may be modeled as a Poisson point process with parameter \(\lambda\) packets/second. If each packet in the channel lasts \(\tau\) seconds, the normalized channel traffic can be defined as
\[\tag{1} G = \lambda \tau \]
If only those packets which do not overlap with any other packet are received correctly, there is packet rate \(\lambda'< \lambda\) defining the rate of occurrence of packets received correctly. Then the normalized channel throughput of the ALOHA channel can be defined as
\[\tag{2} S = \lambda' \tau\]
and the normalized throughput of an ALOHA random access channel is given by (Abramson, 1970)
\[\tag{3} S = G e^{-2G}\]
The maximum value of the normalized throughput of an ALOHA channel is equal to \(\frac{1}{2e}=0.184\) and occurs when the traffic G is equal to 0.5.
It is possible to modify the completely unsynchronized operation of the transmitters on an ALOHA random access channel in order to increase the maximum throughput of the channel. If a synchronized time base is established in the ALOHA channel to define a sequence of slots of the same duration as a packet transmission and each transmitter in the ALOHA random access channel is required to start any packet transmission at the start of a slot, the resulting channel is referred to as a slotted ALOHA channel (Roberts, 1975; Abramson, 1977). In a slotted ALOHA channel any overlap of two or more packets is a complete overlap and the elimination of partial packet overlaps results in an increase of channel throughput in a slotted ALOHA channel. The maximum throughput of a slotted ALOHA channel occurs when the channel traffic is equal to 1.0 and the maximum throughput is equal to 1/e = 0.368 or exactly twice the value for the unslotted ALOHA channel. In practice the use of the slotted ALOHA channel can result in less improvement than this result might indicate or even in a decrease in the channel throughput. If the transmitter packets are not all of the same duration then the loss of throughput due to wasted portions of fixed length slots can be greater than the factor of two improvement promised by slotting (Abramson, 1977).
A wide variety of reservation techniques have been proposed and implemented which can increase the maximum throughput of an ALOHA channel by reserving packet transmission times when the transmitter has a long sequence of packets to transmit (Crowther, 1973). Slotted ALOHA and reservation ALOHA are sometimes referred to as S-Aloha and R-ALOHA respectively.
Beginning in 1990 the connection between spread spectrum code division multiple access (CDMA) and ALOHA random access has been of interest. The combination of these two access technologies for both satellite and terrestrial wireless channels is referred to as Spread ALOHA (Abramson, 1990).
Applications
The first commercial application of ALOHA channels was launched in 1976 by Comsat General in the Marisat maritime satellite communications system. At about the same time Metcalfe working with a group from DEC, Intel and Xerox (the DIX Group) formulated an open Ethernet standard based on the Alto ALOHA network. Since 1983 ALOHA channels have been adopted for use in all major mobile telephone standards (1G, 2G and 3G) as the control channel and then for a variety of packet data channels integrated into these voice networks (e.g. GPRS and UMTS). ALOHA has also been adopted for use in a variety of protocols used in wired networks, CSMA/CD and CSMA/CA in single channel local area networks and DOCSIS for commercial cable networks.
References
[1] Abramson, N. (1970) The ALOHA System – Another Alternative for Computer Communications, AFIPS Conference Proceedings, Vol. 37, pp.281-285, November, 1970.
[2] Abramson, N. (1977) The Throughput of Packet Broadcasting Channels, IEEE Transactions on Communications, Vol. COM-25, No. 1, pp 117-128, January 1977.
[3] Abramson, N. (1985) Development of the AlohaNet, IEEE Transactions on Information Theory, Vol. IT-31, No. 2, pp. 119-123, March 1985.
[4] Abramson, N. (1990), VSAT Data Networks, Proceedings of the IEEE, vol.78, no. 7, pp 1267-1274, July, 1990.
[5] Abramson, N. (2009), The AlohaNet -- Surfing for Wireless Data, IEEE Communications Magazine, vol.47, no. 12, pp 21-25, December, 2009.
[6] Binder, R. et al. (1975), ALOHA Packet Broadcasting – A Retrospect, Proceedings of the National Computer Conference, Vol. 44, pp. 203-215, AFIPS Press.
[7] Crowther, W. et al. (1973), A System for Broadcast Communication: Reservation ALOHA, Proceedings of the 6th HICSS, University of Hawaii, Honolulu, January, 1973.
[8] Metcalfe, Robert M. and Boggs, David R. (1976), Ethernet: Distributed Packet Switching for Local Computer Networks, Communications of the ACM, Vol. 19, No. 7, July 1976.
[9] Roberts, Lawrence G., (1975), ALOHA Packet System with and without Slots and Capture, Computer Communications Review, vol. 5, No. 2, pp. 28-42, April, 1975.
Internal references
- Lajos Hanzo (2008) Global system for mobile communications (GSM). Scholarpedia, 3(8):4115.
- Arkady Pikovsky and Michael Rosenblum (2007) Synchronization. Scholarpedia, 2(12):1459.
See also
- GPRS (General Packet Radio Service)
- EDGE (Enhanced Data Rates for GSM Evolution)
- UMTS (Universal Mobile Telecommunications System)
- WiFi (Wireless Fidelity)
- WiMAX (Worldwide Interoperability for Microwave Access)
- Zigbee
- DOCSIS (Data Over Cable Service Interface Specification)
