Editing ALOHAnet (section)

== Protocol ==

=== Pure ALOHA ===
[[file:Pure ALOHA1.svg|thumb|alt=Graph of frames being sent from 4 different stations according to the pure ALOHA protocol with respect to time, with overlapping frames shaded to denote collision.|Pure ALOHA protocol. Boxes indicate frames. Shaded boxes indicate frames that have collided.]]

The original version of the protocol (now called Pure ALOHA, and the one implemented in ALOHAnet) 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 (successful) transmission of frames.<ref name="tann">{{Cite book |last=Tanenbaum |first=A. S. |url=https://archive.org/details/computernetworks00tane_2 |title=Computer Networks |publisher=Prentice Hall PTR |year=2003 |isbn=9780130661029 |author-link=Andrew S. Tanenbaum |url-access=registration |via=The Internet Archive}}</ref> 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 (both new transmission and retransmissions) follows a [[Poisson distribution]].

Let {{Math|T}} refer to the time needed to transmit one frame on the channel, and define ''frame-time'' as a unit of time equal to {{math|T}}. Let {{math|G}} refer to the mean used in the Poisson distribution over transmission-attempt amounts. That is, on average, there are {{math|G}} 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 {{Math|t}} 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 {{Math|t}}, and all other stations to refrain from transmitting during this time.

For any frame-time, the probability of there being {{Math|k}} transmission-attempts during that frame-time is:

<math>\frac{G^k e^{-G}}{k!}</math>

[[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 {{math|2G}}. Hence, for any pair of consecutive frame-times, the probability of there being {{Math|k}} transmission attempts during those two frame-times is:

:<math>\frac{(2G)^k e^{-2G}}{k!}</math>

Therefore, the probability (<math>Prob_{pure}</math>) of there being zero transmission-attempts between {{math|t-T}} and {{math|t+T}} (and thus of a successful transmission for us) is:

:<math>Prob_{pure}=e^{-2G}</math>

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 (<math>S_{pure}</math>) is:

:<math>S_{pure}=Ge^{-2G}</math>

The maximum throughput is {{math|0.5/e}} frames per frame-time (reached when <math>G=0.5</math>), 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 ===
[[file:Slotted ALOHA.svg|thumb|alt=Graph of frames being sent from 8 different stations according to the slotted ALOHA protocol with respect to time, with frames in the same slots shaded to denote collision.|Slotted ALOHA protocol. Boxes indicate frames. Shaded boxes indicate frames which are in the same slots.]]

An improvement to the original ALOHA protocol was Slotted ALOHA, which introduced discrete time slots and increased the maximum throughput.<ref>{{Cite journal |last=Roberts |first=Lawrence G. |author-link=Lawrence Roberts (scientist) |date=April 1975 |title=ALOHA Packet System With and Without Slots and Capture |journal=Computer Communications Review |volume=5 |issue=2 |pages=28–42 |doi=10.1145/1024916.1024920|s2cid=3062884 }}</ref> 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:

<math>Prob_{slotted} = e^{-G}</math>

the probability of a transmission requiring exactly k attempts is (k-1 collisions and 1 success):<ref name="tann" />

<math>Prob_{slotted} k =  e^{-G} ( 1 - e^{-G} )^{k-1}</math>

The throughput is:

<math>S_{slotted}=Ge^{-G}</math>

The maximum throughput is ''1/e'' frames per frame-time (reached when ''G'' = 1), which is approximately 0.368 frames per frame-time, or 36.8%.

Slotted ALOHA is used in low-data-rate tactical [[communications satellite|satellite communications networks]] by military forces, in subscriber-based satellite communications networks, mobile telephony call setup, [[Switched video|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.<ref>{{cite web |url=http://www.laynetworks.com/Aloha%20Simulation%20Validation.htm |title=Aloha Simulation Validations - Computer Science - Provided by Laynetworks.com |website=www.laynetworks.com |url-status=dead |archive-url=https://web.archive.org/web/20030801201425/http://www.laynetworks.com/Aloha%20Simulation%20Validation.htm |archive-date=2003-08-01}} </ref>

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 protocol|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 (utilize) the slot on a contention basis.

=== Packet Reservation Multiple Access ===

Packet reservation multiple access (PRMA) is an implicit reservation scheme.
Some fixed number of slots form a frame.
After each frame, the satellite broadcasts the status of each slot from the previous frame, which indicates the reservation status of the corresponding slots of the next frame.
All ground stations wishing to transmit compete exactly like slotted ALOHA during any "free slot" of that next frame (i.e., either no one transmitted in that slot of the previous frame, or there was a collision when multiple ground stations transmitted in that slot of the previous frame).
If exactly one ground station happens to transmit during a "free slot", that ground station succeeds in reserving that slot of a frame -- the corresponding slot is implicitly reserved in all future frames.
From then on, the satellite broadcasts that that particular ground station has reserved that slot of the frame, and that ground station can continue transmitting with a guaranteed data rate during that slot of the frame; other ground stations are careful *not* to transmit during that slot of the frame, so there are no collisions during reserved slots.
When a ground station with a reserved slot has nothing to send, it simply stops transmitting, which gives up its reservation; the satellite notices its reserved slot is idle in one frame, and broadcasts that fact, which indicates that that slot will be a "free slot" in the next frame.<ref>
Alex Brand; Hamid Aghvami.
[https://www.google.com/books/edition/Multiple_Access_Protocols_for_Mobile_Com/NWvzGU12vh0C "Multiple Access Protocols for Mobile Communications: GPRS, UMTS and Beyond].
2002.
p. 77.
</ref><ref name="ppgk" >
Syed Imran Patel, Dr. M. Prasad, Dr. Ankur Goyal, Shivkant Kaushik
[https://www.google.com/books/edition/Wireless_Networks_and_Mobile_Computing/OPXJEAAAQBAJ "Wireless Networks and Mobile Computing"].
2021.
p. 33.
</ref>

Maximum channel efficiency for slotted ALOHA is 36%; PRMA improves maximum channel efficiency to 80%.<ref name="ppgk" />

=== Demand Assigned Multiple Access ===
{{main | Demand Assigned Multiple Access }}

Demand assigned multiple access (DAMA), also called reservation ALOHA, is an explicit reservation scheme often used in satellite communications.
DAMA alternates between two phases: During the reservation phase of a frame, DAMA acts like slotted ALOHA for some fixed number of short slots, except instead of ground stations sending complete packets, ground stations only send short requests for later transmission. The satellite collects all the successful requests (i.e., the ones not destroyed by collision) and sends them back as a reservation list assigning specific ground stations to specific TDM slots. During the TDM phase of a frame, the ground stations obey the reservation list and each one only transmits during the long TDM slot(s) reserved for it.
Collisions may occur during the reservation phase, but not during the TDM phase.<ref name="ppgk" /><ref>
Ramjee Prasad; Marina Ruggieri.
[https://www.google.com/books/edition/Technology_Trends_in_Wireless_Communicat/DmA0d_B8dZcC "Technology Trends in Wireless Communications"].
2003.
p. 44.
</ref>

Maximum channel efficiency for slotted ALOHA is 36%; DAMA improves maximum channel efficiency to 80%.<ref name="ppgk" />

=== Mobile Slotted Aloha ===
{{main | Mobile Slotted Aloha }}

=== Other protocols ===

The use of a random-access channel in ALOHAnet led to the development of [[carrier-sense multiple access]] (CSMA), a ''listen before send'' random-access protocol that can be used when all nodes send and receive on the same channel.  CSMA in radio channels was extensively modeled.<ref>{{Cite journal |last1=Kleinrock |first1=Len |author-link=Len Kleinrock |last2=Tobagi |first2=Fouad A. |author-link2=Fouad Tobagi |year=1975 |title=Packet switching in Radio Channels: Part I – Carrier Sense Multiple Access Modes and their Throughput-Delay Characteristics |url=http://my.fit.edu/~kostanic/Wirelesss%20Data%20Communication%20Networks/Materials/Lecture%206%20Kleinrock%20and%20Tobagi%20-%20Part1.pdf |journal=IEEE Transactions on Communications |volume=23 |issue=COM–23 |pages=1400–1416 |citeseerx=10.1.1.475.2016 |doi=10.1109/tcom.1975.1092768 |s2cid=5879608 |access-date=2017-11-01 |archive-date=2017-08-09 |archive-url=https://web.archive.org/web/20170809064027/http://my.fit.edu/~kostanic/Wirelesss%20Data%20Communication%20Networks/Materials/Lecture%206%20Kleinrock%20and%20Tobagi%20-%20Part1.pdf |url-status=dead }}</ref> The [[AX.25]] packet radio protocol is based on the CSMA approach with collision recovery,<ref>{{cite web|title=AX.25 Link Access Protocol for Amateur Packet Radio|url=http://www.tapr.org/pdf/AX25.2.2.pdf|publisher=[[Tucson Amateur Packet Radio]] |pages=39 |year=1997|access-date=2014-01-06}}</ref> based on the experience gained from ALOHAnet. A variation of CSMA, [[CSMA/CD]] is used in early versions of [[Ethernet]].

ALOHA and the other random-access protocols have an inherent variability in their throughput and delay performance characteristics. For this reason, applications that need highly deterministic load behavior may use [[Master/slave (technology)|master/slave]] or [[token-passing]] schemes (such as [[Token Ring]] or [[ARCNET]]) instead of [[Contention (telecommunications)|contention systems]].