ALOHA (protocol)

ALOHA, ook wel bekend als ALOHAnet en ALOHA system,^[1]^[2] was een baanbrekende computernetwerksysteem ontwikkeld aan de Universiteit van Hawaï. ALOHA werd operationeel in juni 1971. Het werd gebruikt bij de eerste openbare demonstratie van een draadloos GPRS-netwerk. Het is een algoritme dat bekendstaat voor het toewijzen van een kanaal met multiple access.

Het ALOHA-protocol gebruikt een nieuwe methode van medium access (ALOHA random access) en een experimentele vorm van Ultrahoge Frequentie (UHF). Dit was nodig omdat de frequentietoewijzingen voor de communicatie van/naar een computer nog niet beschikbaar waren voor commerciële toepassingen. Maar zelfs nog voordat deze frequenties konden worden toegewezen, waren er twee andere media beschikbaar voor toepassing op een ALOHA-kanaal: kabels en satellieten. In de jaren zeventig was ALOHA random access werkzaam in vele netwerken die gebaseerd waren op ethernet, maar ook in satellietnetwerken als Marisat (nu INMARSAT).

Geschiedenis

Een van de eerste computernetwerkontwerpen kent haar oorsprong in het ongerepte Hawaï, in het begin van de jaren zeventig. In dit geval moet 'ongerept' worden gelezen als 'niet in het bezit van een werkend telefoonnet. In die periode trachten onderzoeker Norman Abramson en zijn collega's aan de Universiteit van Hawaï een computernetwerk, door verschillende gebruikers op andere eilanden te verbinden met hun hoofdcomputer. Zonder communicatiemogelijkheid met de verschillende eilanden is dit geen makkelijke opgave. Eigen kabels leggen onder de Stille Oceaan was geen optie, dus zochten ze naar andere mogelijkheden.

De oplossing die ze vonden maakte gebruik van korteafstandsradio's, waarbij elke gebruikersterminal dezelfde upstreamfrequentie gebruikte om frames naar de centrale computer te zenden. Hiertoe behoorde een eenvoudige en elegante methode om het kanaaltoewijzingsprobleem op te lossen. Hoewel het werk van Abramson, dat het ALOHA-systeem wordt genoemd, gebruikmaakte van radio-uitzendingen op aarde, is het basisidee toepasbaar op elk systeem waarin niet-gecoördineerde gebruikers één gemeenschappelijk te gebruiken kanaal hebben.

We kennen twee versies van het ALOHA-protocol:^[3]

Zuiver ALOHA
Slotted ALOHA

Het verschil is dat bij de zuivere versie de tijd continu is. Bij de slotted versie is de tijd verdeeld in discrete tijdslots waarin alle frames moeten passen.

Het ALOHA-protocol

Zuiver ALOHA

Bij zuiver ALOHA worden de frames op willekeurige tijdstippen verzonden.

Het basisprincipe van een ALOHA-systeem is eenvoudig: laat gebruikers zenden als ze data bezitten om te verzenden. Dit heeft als gevolg dat er botsingen optreden omdat meerdere gebruikers op eenzelfde moment hun frames kunnen verzenden. Zenders hebben een manier nodig om te detecteren wanneer ze hun frame mogen verzenden. In het ALOHA-systeem zendt de centrale computer nadat elk station zijn frame naar de eerste computer heeft gestuurd, het frame opnieuw naar alle stations. Een zendstation kan dus luisteren naar de uitzending van de hub om te zien of het frame is doorgekomen. In andere systemen zoals bedrade LAN's, kan de zender tijdens het zenden in de gaten houden of er botsingen optreden.

Als het frame door een botsing vernield is, wacht de zender een willekeurige tijd en verzendt het opnieuw. De wachttijd moet willekeurig zijn omdat de frames anders elke keer zullen botsen. Systemen waarin meerdere gebruikers één gemeenschappelijk kanaal gebruiken op een manier die tot conflicten kan leiden, worden contentiesystemen genoemd.

In het figuur wordt een schets weergegeven van het genereren van frames in een ALOHA-systeem. We hebben alle frames een gelijke lengte gegeven, omdat de capaciteit van een ALOHA-systeem maximaal is als de frames even groot zijn.

Elke keer dat twee frames tegelijk het kanaal proberen te bezetten, treedt er een botsing op en zullen beide beschadigd worden. Zelfs als de eerste bit van een nieuw frame enkel de laatste bit van een bijna voltooid frame overlapt, worden beide frames volledig onbruikbaar en moeten ze later opnieuw verzonden worden. We kunnen de efficiëntie van het ALOHA-kanaal beredeneren door te kijken naar het aantal verzonden frames dat ontsnapt aan een botsing. We bekijken eerst een oneindige verzameling van gebruikers die een station bezitten en frames verzenden (bijvoorbeeld: het typen van een bericht). Een gebruiker is altijd in de toestand 'typend' of 'wachtend'. Aanvankelijk zijn alle gebruikers in de toestand 'typend'. Wanneer een regel af is, houdt de gebruiker op met typen en wacht op antwoord. Het station zendt dan een frame met de regel over het gedeelde kanaal naar de centrale computer en kijkt in het kanaal of de transmissie gelukt is. Zo ja, dan blijft de gebruiker wachten terwijl het station het frame telkens opnieuw verzendt tot de transmissie geslaagd is.

Frametijd

De hoeveelheid tijd aan die nodig is om een normaal frame van vaste lengte te verzenden:

$Frametijd={\frac {framelengte}{bitsnelheid}}$

We gaan er nu van uit dat nieuwe frames die door de stations gegenereerd worden, goed gemodelleerd worden door een verdeling met gemiddeld N frames per frametijd. We bekijken het geheel met een oneindige populatie om ervoor te zorgen dat N niet toeneemt als er gebruikers geblokkeerd worden. Als N > 1, genereert de verzameling gebruikers frames met een hogere frequentie dan het kanaal kan afhandelen en zal bijna elk frame een botsing hebben. Voor een redelijke doorvoer verwachten we 0 < N < 1.

Naast nieuwe frames genereren de stations ook nieuwe transmissies van oude frames die de vorige keer een botsing hebben gehad. We nemen verder aan dat de oude en nieuwe frames gecombineerd, goed gemodelleerd worden door de verdeling, met gemiddeld G-frames per frametijd. Het is duidelijk dat G ≥ N. Bij lage belasting (als N ≈ 0) zijn er weinig botsingen en dus weinig tweede transmissies, zodat G ≈ N. Bij hoge belasting treden er veel botsingen op, dus G > N. Bij elke belasting is de doorvoer, S, de aangeboden belasting G maal de kans dat een transmissie slaagt.

$S=GP_{0'}$

Kwetsbare periode

Kwetsbare periode voor het gearceerde frame.

Een frame krijgt geen botsing als er binnen één frametijd nadat het begonnen is geen ander frame start. Het gearceerde frame zal onbeschadigd aankomen (met t, de tijd is die nodig is om het frame te verzenden) als een andere gebruiker een frame heeft gegenereerd tussen $t_{0}$ en $t_{0}+t$ . Het einde van het vorige frame zal botsen met het begin van het gearceerde frame. In feite werd dit verloop al bepaald voordat de eerste bit werd gezonden, maar omdat in zuiver ALOHA een station niet naar het kanaal luistert voordat het gaat zenden, kan het niet weten dat er al een ander frame onderweg is. Op dezelfde manier zal elk ander frame dat begint tussen $t_{0}+t$ en $t_{0}+2t$ tegen het eind van het gearceerde frame botsen.

De waarschijnlijkheid dat er tijdens een gegeven frametijd k-frames worden gegenereerd, waarin G-frames worden verwacht

$Pr[k]={\frac {G^{k}e^{-G}}{k!}}$

zodat de kans op nul frames $e^{-G}$ is. In een interval met de lengte van twee frametijden is het gemiddelde aantal gegenereerde frames 2G. De kans dat er geen frames worden gestart gedurende de gehele kwetsbare periode is dus $P_{0}=e^{-2G}$ . Gebruikmakend van $S=GP_{0}$ krijgen we volgende uitdrukking:

$S=Ge^{-2G}$

Kwetsbare periode voor het gearceerde frame.

In de figuur zien we het verband tussen het aangeboden verkeer en de doorvoer. De maximale doorvoer treedt op bij $G=0,5$ , met $S={\frac {1}{2e}}$ , wat ongeveer 0,184 is. Met andere woorden: een gebruiksgraad van het kanaal van 18% is het beste waarop we kunnen hopen. Dit resultaat is niet erg bemoedigend, maar gegeven dat iedereen direct frames mag sturen kan ook geen grotere zuiverheid verwacht worden.

Slotted ALOHA

In 1972 publiceerde Roberts een methode om de capaciteit van een ALOHA-systeem te verdubbelen. Zijn voorstel omvatte het verdelen van de tijd in discrete intervallen, waarbij elk interval overeenkomt met één frame. Voor deze aanpak is het nodig dat de gebruikers het eens zijn over de grenzen van de slots. Een manier om synchronisatie te verkrijgen, is een speciaal station aan het begin van elk interval een signaal te laten uitzenden, zoals een klok.

Deze methode van Roberts wordt slotted ALOHA genoemd en is een variant op het zuiver ALOHA van Abramson. Wanneer de gebruiker een regel typt, mag een ander station niets zenden. Het station moet wachten op het begin van het volgende slot. Het continue-time ALOHA-systeem wordt zo veranderd in een discreet-tijdssysteem. De kwetsbare periode wordt zo gehalveerd. De kans dat er geen ander verkeer voorkomt tijdens hetzelfde slot als het testframe, is gelijk aan $e^{-G}$ , zodat:

$S=Ge^{-G}$

De piek van slotted ALOHA valt bij G = 1, met een doorvoer van $S={\frac {1}{e}}$ , dus ongeveer 0,368: dit is tweemaal zoveel als bij zuiver ALOHA. Als het systeem met G = 1 werkt, is de kans op een leeg slot gelijk aan 0,368. Het beste resultaat dat we met slotted ALOHA kunnen bereiken, is 37% lege slots, 37% succesvolle transmissies en 26% botsingen. Bij hogere waarden van G wordt het aantel lege slots kleiner, maar neemt het aantal botsingen exponentieel toe. Om in te zien hoe deze snelle groei van het aantal botsingen bij toenemende G tot stand komt, moeten we de transmissie van het testframe voorstellen. De kans dat het niet in botsing komt is $e^{-G}$ (de kans dat alle andere gebruikers in dat slot niets verzenden). De kans op een botsing bedraagt $1-e^{-G}$ . Ten slotte is de kans dat er voor het verzenden precies k-pogingen nodig zijn (dus, de kans op k - 1 botsingen gevolgd door één succes) is:

$P_{k}=e^{-G}(1-e^{-G})^{k-1}$

Een verwacht aantal transmissies E per getypte regel op een station is dan:

$E=\sum _{k=1}^{\infty }{ke^{-G}(1-e^{-G})^{k-1}}=e^{G}$

Doordat E op exponentiële wijze van G afhangt, kan een kleine verhoging van de kanaalbelasting tot een drastische vermindering van de prestaties leiden.

Slotted ALOHA is opmerkelijk om redenen die in eerste instantie niet voor de hand liggen. Het werd ontwikkeld in de jaren zeventig, vervolgens een paar jaar gebruikt in enkele experimentele systemen en daarna nagenoeg vergeten. Maar door de opkomst van internettoegang via de kabel ontstond het probleem van toegangswijze van een gedeeld kanaal aan verschillende met elkaar concurrerende gebruikers. Om die reden werd de technologie van slotted ALOHA weer even opgehaald.

Bronnen, noten en/of referenties

↑ N. Abramson (1970). Proc. 1970 Fall Joint Computer Conference (PDF) (AFIPS Press).
↑ Frank F. Kuo (1995). "The ALOHA system". ACM Computer Communication Review: 25
↑ Tanenbaum, Andrew S. (2011). 'Computer Networks, Fifth Edition'

[1] N. Abramson (1970). Proc. 1970 Fall Joint Computer Conference (PDF) (AFIPS Press).

[2] Frank F. Kuo (1995). "The ALOHA system". ACM Computer Communication Review: 25

[3] Tanenbaum, Andrew S. (2011). 'Computer Networks, Fifth Edition'

[1]

[2]

[3]