ALOHAnet, also known as the ALOHA System, or simply ALOHA, was a pioneering computer
networking system developed at the University of Hawaii. ALOHAnet became operational in
June, 1971, providing the first public demonstration of a wireless packet data network.
The ALOHAnet used a new method of medium access and experimental ultra high frequency for
its operation, since frequency assignments for communications to and from a computer
were not available for commercial applications in the 1970s. But even before such frequencies
were assigned there were two other media available for the application of an ALOHA channel – cables
and satellites. In the 1970s ALOHA random access was employed in the widely used Ethernet
cable based network and then in the Marisat satellite network.
In the early 1980s frequencies for mobile networks became available, and in 1985 frequencies
suitable for what became known as Wi-Fi were allocated in the US. These regulatory developments
made it possible to use the ALOHA random-access techniques in both Wi-Fi and in mobile telephone
networks. ALOHA channels were used in a limited way
in the 1980s in 1G mobile phones for signaling and control purposes. In the late 1980s, the
European standardisation group GSM who worked on the Pan-European Digital mobile communication
system GSM greatly expanded the use of ALOHA channels for access to radio channels in mobile
telephony. In addition SMS message texting was implemented in 2G mobile phones. In the
early 2000s additional ALOHA channels were added to 2.5G and 3G mobile phones with the
widespread introduction of GPRS, using a slotted-ALOHA random-access channel combined with a version
of the Reservation ALOHA scheme first analyzed by a group at BBN.
Overview One of the early computer networking designs,
development of the ALOHA network was begun in 1968 at the University of Hawaii under
the leadership of Norman Abramson and others. The goal was to use low-cost commercial radio
equipment to connect users on Oahu and the other Hawaiian islands with a central time-sharing
computer on the main Oahu campus. 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 packets to the
hub on the "inbound" channel. If data was received correctly at the hub, a short acknowledgment
packet was sent to the client; if an acknowledgment was not received by a client machine after
a short wait time, it would automatically retransmit the data packet after waiting a
randomly selected time interval. This acknowledgment mechanism was used to detect and correct for
"collisions" created when two client machines both attempted to send a packet at the same
time. ALOHAnet's primary importance was its use
of a shared medium for client transmissions. Unlike the ARPANET where each node could only
talk directly to a node at the other end of a wire or satellite circuit, in ALOHAnet all
client nodes communicated with the hub on the same frequency. This meant that some sort
of mechanism was needed to control who could talk at what time. The ALOHAnet solution was
to allow each client to send its data without controlling when it was sent, with an acknowledgment/retransmission
scheme used to deal with collisions. This approach radically reduced the complexity
of the protocol and the networking hardware, since nodes do not need negotiate "who" is
allowed to speak.. This solution became known as a pure ALOHA, or random-access channel,
and was the basis for subsequent Ethernet development and later Wi-Fi networks. Various
versions of the ALOHA protocol also appeared later in satellite communications, and were
used in wireless data networks such as ARDIS, Mobitex, CDPD, and GSM.
Also important was ALOHAnet's use of the outgoing hub channel to broadcast packets directly
to all clients on a second shared frequency, using an address in each packet to allow selective
receipt at each client node. The ALOHA protocol
Pure ALOHA
The first version of the protocol was quite simple:
If you have data to send, send the data If, while you are transmitting data, you receive
any data from another station, there has been a message collision. All transmitting stations
will need to try resending "later". Note that the first step implies that Pure
ALOHA does not check whether the channel is busy before transmitting. Since collisions
can occur and data may have to be sent again, ALOHA cannot use 100% of the capacity of the
communications channel. How long a station waits until it transmits, and the likelihood
a collision occurs are interrelated, and both affect how efficiently the channel can be
used. This means that the concept of "transmit later" is a critical aspect: the quality of
the backoff scheme chosen significantly influences the efficiency of the protocol, the ultimate
channel capacity, and the predictability of its behavior.
To assess Pure ALOHA, we need to predict its throughput, the rate of transmission of frames.
First, let's make a few simplifying assumptions: All frames have the same length.
Stations cannot generate a frame while transmitting or trying to transmit.
The population of stations attempts to transmit according to a Poisson distribution.
Let "T" refer to the time needed to transmit one frame on the channel, and let's define
"frame-time" as a unit of time equal to T. Let "G" refer to the mean used in the Poisson
distribution over transmission-attempt amounts: that is, on average, there are G transmission-attempts
per frame-time.
Consider what needs to happen for a frame to be transmitted successfully. Let "t" refer
to the time at which we want to send a frame. We want to use the channel for one frame-time
beginning at t, and so we need all other stations to refrain from transmitting during this time.
For any frame-time, the probability of there being k transmission-attempts during that
frame-time is:
The average amount of transmission-attempts for 2 consecutive frame-times is 2G. Hence,
for any pair of consecutive frame-times, the probability of there being k transmission-attempts
during those two frame-times is:
Therefore, the probability of there being zero transmission-attempts between t-T and
t+T is:
The throughput can be calculated as the rate of transmission-attempts multiplied by the
probability of success, and so we can conclude that the throughput is:
Vulnerable time=2*T. The maximum throughput is 0.5/e frames per
frame-time, which is approximately 0.184 frames per frame-time. This means that, in Pure ALOHA,
only about 18.4% of the time is used for successful transmissions.
Another simple and mathematical way to establish the equation for throughput in Pure ALOHA
is as follows: Consider what needs to happen for frames to
be transmitted successfully. Let T represents the frame time. For simplicity we assume that
the contention begins at t=0. Then if exactly one node sends during interval t=0 to t=T
and no node tries between t=T to t=2T, then the frame will be transmitted successfully.
Similarly during all next time intervals t=2nT to t=(2n+1)T, exactly one node sends and during
t=(2n+1)T to t=(2n+2)T no node tries to send where n=1,2,3, ..., then the frames are successfully
transmitted. But in pure ALOHA, the nodes begin transmission whenever they want to do
so without checking that what other nodes are doing at that time. Thus sending frames
are independent events, that is, transmission by any particular node neither affects nor
is affected by the time of start of transmission by other nodes. Let G be the average number
of nodes that begin transmission within period T. If a large number of nodes are trying to
transmit, then by using Poisson distribution, the probability that exactly x nodes begin
transmission during period T is
Therefore the probability that during any particular period from t=2nT to t=(2n+1)T,
exactly one node will begin transmission is
And the probability that during any particular period t=(2n+1)T to t=(2n+2)T, no node will
begin transmission is
But for successful transmission of a frame, both the events should occur simultaneously.
That is during period t=2nT to t=(2n+1)T, exactly one node begins transmission and during
t=(2n+1)T to t=(2n+2)T no node begins transmission. Hence the probability that both the independent
events will occur simultaneously is
This is the throughput. By throughput we mean the probability of successful transmission
during minimum possible period. Therefore the throughput in pure ALOHA,
Similarly for slotted ALOHA, a frame will be successfully transmitted, if exactly one
node will begin transmission at the beginning of any particular time slot. But the probability
that one node will begin during any particular time slot is
This is the throughput in slotted ALOHA. Thus,
Slotted ALOHA
An improvement to the original ALOHA protocol was "Slotted ALOHA", which introduced discrete
timeslots and increased the maximum throughput. A station can send only at the beginning of
a timeslot, and thus collisions are reduced. In this case, we only need to worry about
the transmission-attempts within 1 frame-time and not 2 consecutive frame-times, since collisions
can only occur during each timeslot. Thus, the probability of there being zero transmission-attempts
in a single timeslot is:
the probability of k packets is:
The throughput is:
The maximum throughput is 1/e frames per frame-time, which is approximately 0.368 frames per frame-time,
or 36.8%. Slotted ALOHA is used in low-data-rate tactical
satellite communications networks by military forces, in subscriber-based satellite communications
networks, mobile telephony call setup, set-top box communications and in the contactless
RFID technologies. Other protocol
The use of a random-access channel in ALOHAnet led to the development of carrier sense multiple
access, a "listen before send" random-access protocol that can be used when all nodes send
and receive on the same channel. The first implementation of CSMA was Ethernet. CSMA
in radio channels was extensively modeled. The AX.25 packet radio protocol is based on
the CSMA approach with collision recovery, based on the experience gained from ALOHAnet.
ALOHA and the other random-access protocols have an inherent variability in their throughput
and delay performance characteristics. For this reason, applications which need highly
deterministic load behavior sometimes used polling or token-passing schemes instead of
contention systems. For instance ARCNET was popular in embedded data applications in the
1980 network. Design
Network architecture Two fundamental choices which dictated much
of the ALOHAnet design were the two-channel star configuration of the network and the
use of random accessing for user transmissions. The two-channel configuration was primarily
chosen to allow for efficient transmission of the relatively dense total traffic stream
being returned to users by the central time-sharing computer. An additional reason for the star
configuration was the desire to centralize as many communication functions as possible
at the central network node, minimizing the cost of the original all-hardware terminal
control unit at each user node. The random-access channel for communication
between users and the Menehune was designed specifically for the traffic characteristics
of interactive computing. In a conventional communication system a user might be assigned
a portion of the channel on either a frequency-division multiple access or time-division multiple
access basis. Since it was well known that in time-sharing systems [circa 1970], computer
and user data are bursty, such fixed assignments are generally wasteful of bandwidth because
of the high peak-to-average data rates that characterize the traffic.
To achieve a more efficient use of bandwidth for bursty traffic, ALOHAnet developed the
random-access packet switching method that has come to be known as a pure ALOHA channel.
This approach effectively dynamically allocates bandwidth immediately to a user who has data
to send, using the acknowledgment/retransmission mechanism described earlier to deal with occasional
access collisions. While the average channel loading must be kept below about 10% to maintain
a low collision rate, this still results in better bandwidth efficiency than when fixed
allocations are used in a bursty traffic context. Two 100 kHz channels in the experimental
UHF band were used in the implemented system, one for the user-to-computer random-access
channel and one for the computer-to-user broadcast channel. The system was configured as a star
network, allowing only the central node to receive transmissions in the random-access
channel. All user TCUs received each transmission made by the central node in the broadcast
channel. All transmissions were made in bursts at 9600 bit/s, with data and control information
encapsulated in packets. Each packet consisted of a 32-bit header and
a 16-bit header parity check word, followed by up to 80 bytes of data and a 16-bit parity
check word for the data. The header contained address information identifying a particular
user so that when the Menehune broadcast a packet, only the intended user's node would
accept it. The Menehune
The central node communications processor was an HP 2100 minicomputer called the Menehune,
which is the Hawaiian language word for “imp”, or dwarf people, and was named for its similar
role to the original ARPANET Interface Message Processor which was being deployed at about
the same time. In the original system, the Menehune forwarded correctly received user
data to the UH central computer, an IBM System 360/65 time-sharing system. Outgoing messages
from the 360 were converted into packets by the Menehune, which were queued and broadcast
to the remote users at a data rate of 9600 bit/s. Unlike the half-duplex radios at the
user TCUs, the Menehune was interfaced to the radio channels with full-duplex radio
equipment. Remote units
The original user interface developed for the system was an all-hardware unit called
an ALOHAnet Terminal Control Unit, and was the sole piece of equipment necessary to connect
a terminal into the ALOHA channel. The TCU was composed of a UHF antenna, transceiver,
modem, buffer and control unit. The buffer was designed for a full line length of 80
characters, which allowed handling of both the 40- and 80-character fixed-length packets
defined for the system. The typical user terminal in the original system consisted of a Teletype
Model 33 or a dumb CRT user terminal connected to the TCU using a standard RS-232C interface.
Shortly after the original ALOHA network went into operation, the TCU was redesigned with
one of the first Intel microprocessors, and the resulting upgrade was called a PCU.
Additional basic functions performed by the TCU's and PCU’s were generation of a cyclic-parity-check
code vector and decoding of received packets for packet error-detection purposes, and generation
of packet retransmissions using a simple random interval generator. If an acknowledgment was
not received from the Menehune after the prescribed number of automatic retransmissions, a flashing
light was used as an indicator to the human user. Also, since the TCU's and PCU’s did
not send acknowledgments to the Menehune, a steady warning light was displayed to the
human user when an error was detected in a received packet. Thus it can be seen that
considerable simplification was incorporated into the initial design of the TCU as well
as the PCU, making use of the fact that it was interfacing a human user into the network.../
Later developments In later versions of the system, simple radio
relays were placed in operation to connect the main network on the island of Oahu to
other islands in Hawaii, and Menehune routing capabilities were expanded to allow user nodes
to exchange packets with other user nodes, the ARPANET, and an experimental satellite
network. More details are available in and in the technical reports listed in the Further
Reading section below. References
Further reading Stallings, William. Data and computer communications.
MacMillan. pp. 296–302. ISBN 0-02-415451-2. R. Metcalfe, Xerox PARC memo, from Bob Metcalfe
to Alto Aloha Distribution on Ether Acquisition, May 22, 1973.
R. Binder, ALOHAnet Protocols, ALOHA System Technical Report, College of Engineering,
The University of Hawaii, September, 1974. R. Binder, W.S. Lai and M. Wilson, The ALOHAnet
Menehune – Version II, ALOHA System Technical Report, College of Engineering, The University
of Hawaii, September, 1974. N. Abramson, The ALOHA System Final Technical
Report, Advanced Research Projects Agency, Contract Number NAS2-6700, October 11, 1974.
N. Abramson "The Throughput of Packet Broadcasting Channels", IEEE Transactions on Communications,
Vol 25 No 1, pp117–128, January 1977. M. Schwartz, Mobile Wireless Communications,
Cambridge Univ. Press, 2005. K. J. Negus, and A. Petrick, History of Wireless
Local Area Networks in the Unlicensed Bands, George Mason University Law School Conference,
Information Economy Project, Arlington, VA., USA, April 4, 2008.
External links Dynamic Sharing of Radio Spectrum: A Brief
History Funding a Revolution: Government Support for
Computing Research ALOHA to the Web, Norman Abramson, HICCS Distinguished