ALOHAnet


ALOHAnet, also known as the ALOHA System, or simply ALOHA, was a pioneering computer networking system developed at the University of Hawaiʻi. 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, called ALOHA random access, and experimental ultra high frequency for its operation. In its simplest form, later known as Pure ALOHA, remote units communicated with a base station over two separate radio frequencies. Nodes did not wait for the channel to be clear before sending, but instead waited for acknowledgement of successful receipt of a message, and re-sent it if this was not received. Nodes would also stop and re-transmit data if they detected any other messages while transmitting. While simple to implement, this results in an efficiency of only 18.4%. A later advancement, Slotted ALOHA, improved the efficiency of the protocol by reducing the chance of collision, improving throughput to 36.8%.
ALOHA was subsequently employed in the Ethernet cable based network in the 1970s, and following regulatory developments in the early 1980s it became 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 standardization 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 the early 2000s additional ALOHA channels were added to 2.5G and 3G mobile phones with the widespread introduction of General Packet Radio Service, using a slotted-ALOHA random-access channel combined with a version of the Reservation ALOHA scheme first analyzed by a group at BBN Technologies.

History

One of the early computer networking designs, development of the ALOHA network was begun in September 1968 at the University of Hawaii under the leadership of Norman Abramson and Franklin Kuo, along with Thomas Gaarder, Shu Lin, Wesley Peterson and Edward Weldon. 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 first packet broadcasting unit went into operation in June 1971. Terminals were connected to a special purpose terminal connection unit using RS-232 at.
ALOHA was originally a contrived acronym standing for Additive Links On-line Hawaii Area.
The original version of ALOHA used two distinct frequencies in a hub 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 to a single 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, and implementing an acknowledgment/retransmission scheme to deal with collisions. This approach radically reduced the complexity of the protocol and the networking hardware, since nodes do not need to 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.
The Aloha network introduced the mechanism of randomized multiple access, which resolved device transmission collisions by transmitting a packet immediately if no acknowledgement is present, and if no acknowledgment was received, the transmission was repeated after a random waiting time. The probability distribution of this random waiting time for retransmission of a packet that has not been acknowledged as received is critically important for the stability of Aloha-type communication systems. The average waiting time for retransmission is typically shorter than the average time for generation of a new packet from the same client node, but it should not be allowed to be so short as to compromise the stability of the network, causing a collapse in its overall throughput.
Also important was ALOHAnet's use of the outgoing hub channel to broadcast packets directly to all clients on a second shared frequency and using an address in each packet to allow selective receipt at each client node. Separate frequencies were used for incoming and outgoing communications to the hub so that devices could receive acknowledgments regardless of transmissions.

Protocol

Pure ALOHA

The original 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.
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 efficiently use 100% of the capacity of the communications channel. How long a station waits until it retransmits, and the likelihood a collision occurs are interrelated, and both affect how efficiently the channel can be used. This means that the concept of retransmit 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, there is a need to predict its throughput, the rate of transmission of frames. First make a few simplifying assumptions:
  • All frames have the same length.
  • Stations cannot generate a frame while transmitting or trying to transmit. That is, while a station is sending or trying to resend a frame, it cannot be allowed to generate more frames to send.
  • The population of stations attempting to transmit follows a Poisson distribution.
Let refer to the time needed to transmit one frame on the channel, and define frame-time as a unit of time equal to. Let refer to the mean used in the Poisson distribution over transmission-attempt amounts. That is, on average, there are transmission attempts per frame-time.
file:Pure ALOHA.svg|thumb|alt=Graph of 3 frames with respect to time. The earlier green frame overlaps with the yellow frame sent at time t0, which overlaps with the later purple frame.|Overlapping frames in the pure ALOHA protocol. Frame-time is equal to 1 for all frames.
Consider what needs to happen for a frame to be transmitted successfully. Let refer to the time at which it is intended to send a frame. It is preferable to use the channel for one frame-time beginning at, and all other stations to refrain from transmitting during this time.
For any frame-time, the probability of there being transmission-attempts during that frame-time is:
file:Aloha PureVsSlotted.svg|thumb|alt=Throughput vs. Traffic Load of Pure Aloha and Slotted Aloha.|Comparison of Pure Aloha and Slotted Aloha shown on Throughput vs. Traffic Load plot.
The average number of transmission-attempts for two consecutive frame-times is. Hence, for any pair of consecutive frame-times, the probability of there being transmission attempts during those two frame-times is:
Therefore, the probability of there being zero transmission-attempts between and is:
The throughput can be calculated as the rate of transmission attempts multiplied by the probability of success, and it can be concluded that the throughput is:
The maximum throughput is 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.

Slotted ALOHA

An improvement to the original ALOHA protocol was Slotted ALOHA, which introduced discrete time slots and increased the maximum throughput. A station can start a transmission only at the beginning of a time slot, and thus collisions are reduced. In this case, only transmission-attempts within 1 frame-time and not 2 consecutive frame-times need to be considered, since collisions can only occur during each time slot. Thus, the probability of there being zero transmission attempts by other stations in a single time slot is:
the probability of a transmission requiring exactly k attempts 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.

Reservation ALOHA

Reservation ALOHA, or R-ALOHA, is an effort to improve the efficiency of Slotted ALOHA. The improvements with Reservation ALOHA are markedly shorter delays and ability to efficiently support higher levels of utilization. As a contrast of efficiency, simulations have shown that Reservation ALOHA exhibits less delay at 80% utilization than Slotted ALOHA at 20–36% utilization.
The chief difference between Slotted and Reservation ALOHA is that with Slotted ALOHA, any slot is available for utilization without regards to prior usage. Under Reservation ALOHA's contention-based reservation schema, the slot is temporarily considered "owned" by the station that successfully used it. Additionally, Reservation ALOHA simply stops sending data once the station has completed its transmission. As a rule, idle slots are considered available to all stations that may then implicitly reserve the slot on a contention basis.