ALOHAnet

ALOHAnet är det första paketkopplade datornätverket som använder trådlös teknologi som sitt åtkomstmedium. Det utvecklades och togs i drift under 1968-1970-talet av en grupp forskare vid University of Hawaii ledd av Norman Abramson som en del av forskningsprojektet THE ALOHA SYSTEM, vars huvudsakliga syfte var att studera möjligheterna för använda radioöverföring som ett alternativ till trådbunden kommunikation. Konceptuella utvecklingar och lösningar som implementerades under detta projekt utgjorde till stor del grunden för sådana teknologier och protokoll som Ethernet , Wi-Fi och cellulära nätverk [1]. År 1973 kombinerades datorcentren vid University of Hawaii, Ames Research Center (NASA), University of Alaska , University of Tohoku , University of Electrical Communications (Tokyo) [sv] till ett nätverk med hjälp av satellitkommunikationskanaler NASA ATS-1 och University of Sydney [2] .

Historik

1968 började professor Norman Abramson vid Stanford University arbeta vid University of Hawaii, där han ledde ett forskarlag som inkluderade Thomas Gaarder , Franklin Kuo , Chu Lin , Shu Lin , Wesley Peterson och Edward Weldon , som började forska om The Aloha System - möjligheten att använda radio för att interagera med användare av stora datorsystem istället för trådbundna anslutningar [1] . Från början var det tänkt att kombinera huvudcampuset vid University of Hawaii, beläget i Manoa Valley - inte långt från Honolulu , med ett college i Hilo och högskolor på öarna Oahu , Kauai , Maui och Hawaii till ett nätverk . Samtliga befann sig på ett avstånd av cirka 30 mil från datacentralen. I framtiden var det meningen att den skulle använda nätverket över hela landet [1] [3] .

Datorcentret på universitetets huvudcampus bestod av en IBM 360/65-dator med 750 KB RAM och flera mindre maskiner. För att interagera med dem planerade collegemaskiner att använda decimeterradiofrekvensbandet som ett dataöverföringsmedium. Utvecklingen av ett experimentellt datornätverk började i september 1968, och ALOHAnet gick live 1971 [1] (ordet " aloha " betyder hej på hawaiiska ) [4] .

ALOHAnet-teknik

I ALOHAnet-nätverket användes en radioanslutning i decimetervågområdet [3] för att ansluta datorer till huvudberäkningscentralen . Två radiokanaler med en bredd på 100 kHz [1] tilldelades med en dataöverföringshastighet på 24 000 baud [3] . En radiokanal med en frekvens på 407,350 MHz [1] användes för att överföra data från terminaler till den centrala datorn [5] i Honolulu, och den andra kanalen med en frekvens på 413,475 MHz [1] användes för att skicka sändningsmeddelanden från central dator till terminaler [5] (för detta installerades nära en sändningsantenn på centraldatorn , och riktade antenner installerades på avlägsna öar som inte tillät att ta emot meddelanden från varandra - stjärnnätstopologin användes i ALOHA-systemet ) [6] .

Eftersom när man försökte sända på samma frekvensband från flera stationer samtidigt, inträffade kollisioner som ledde till förvrängning av den överförda datan, togs ett innovativt beslut att använda metoden för direktåtkomst till kanalen, senare kallad ALOHA random access , som blev en nyckelteknologisk innovation [1] , och även för första gången beslutades att dela upp den överförda informationen i "paket" (704 bitar vardera: 80 8-bitars tecken + 64 kontrollbitar) [7] .

Ren ALOHA

Den första versionen av ALOHA random access kallas även ren ALOHA ( ren ALOHA ) . Med denna metod för kanalåtkomst börjar användardatorer skicka datapaket till centralen omedelbart efter att informationen som ska skickas är tillgänglig. Om sändningen av två eller flera stationer sammanfaller i tid (åtminstone delvis), kan den centrala datorn inte korrekt ta emot data. För att göra det möjligt för avsändare att upptäcka en kollision, skickar värden ut det mottagna datapaketet vid mottagandet. Genom att jämföra det överförda paketet och det mottagna kan avsändaren förstå om hans data togs emot korrekt eller med fel. Om data överfördes felaktigt, väntar avsändaren ett slumpmässigt tidsintervall och försöker sända igen [6] .

Netto ALOHA bandbreddsuppskattning

Bandbreddsuppskattningen för ett rent ALOHA-system bestäms under följande antaganden [6] [7] :

Användardatan som ska överföras anländer till terminalerna slumpmässigt och bildar en Poisson-ström;
Paket som kasseras på grund av överföringsfel återsänds och bildar också en Poisson-ström;
Alla datapaket har samma längd och sänds samtidigt ; $\tau$
Det finns ett oändligt antal fjärrterminaler i nätverket (det vill säga om en viss terminal redan sänder data påverkar detta inte sannolikheten för dataöverföring från andra terminaler).

Under ovanstående antaganden är det totala paketflödet till terminalerna Poisson. Låt det genomsnittliga antalet paket som visas vid alla terminaler under tiden (inklusive de som återsänds) vara lika med . Följaktligen är det genomsnittliga tidsintervallet mellan ögonblicken för mottagande av på varandra följande paket . $\tau$ $G$ ${\frac {\tau }{G))$

Överväg överföringen av någon dedikerad dataram. Paketet tas emot felaktigt om en annan station sände vid början av sin sändning, eller om en annan station började sända före slutet av sändningen. För framgångsrik sändning av vilket som helst allokerat datablock är det således nödvändigt att under tidsintervallet ingen annan station startar sändningen. Sannolikheten för denna händelse är . Det genomsnittliga antalet framgångsrikt överförda paket per gång, det vill säga nätverkets genomströmning , är [6] . $2\tau$ ${\displaystyle \mathbb {P} _{\mathrm {suc} }=e^{-2G))$ $\tau$ ${\displaystyle \lambda _{pure}(G)=G\mathbb {P} _{\mathrm {suc} }=Ge^{-2G))$

Slotted ALOHA

1972 föreslog Lawrence Roberts en annan version av ALOHA-systemet kallad slitsad ALOHA [ 8 ] . Huvudskillnaden mellan slitsad ALOHA och ren ALOHA var idén att dela upp tidsaxeln i diskreta intervall med samma varaktighet , kallade slots. Varje terminal mätte sekventiellt gränserna för slitsarna. För att synkronisera gränserna för luckorna användes en speciell synkroniseringssignal, överförd från sändningsantennen till alla terminaler. När det fanns datapaket som skulle överföras, fördröjde terminalen överföringen till början av nästa lucka. Längden på luckorna valdes så att terminalen under en lucka hann sända sitt datapaket och ta emot bekräftelse på lyckad överföring från centraldatorn [6] . $\tau$

Slotted ALOHA bandbreddsuppskattning

Med ovanstående antaganden bestäms den slitsade ALOHA-genomströmningsuppskattningen enligt följande. Eftersom datapaket sänds uteslutande inom luckagränser, för att flera terminaler ska börja sända samtidigt, måste de ta emot data för att sända inom samma lucka. Sannolikheten för denna händelse är . Då är sannolikheten för att framgångsrikt överföra ett datapaket , och nätverkets genomströmning är [6] . ${\displaystyle \mathbb {P} _{\mathrm {fail} }=1-e^{-G))$ ${\displaystyle \mathbb {P} _{\mathrm {suc} }=e^{-G))$ ${\displaystyle \lambda _{slot}(G)=G\mathbb {P} _{\mathrm {suc} }=Ge^{-G))$

Bandbreddsjämförelse

Följande graf visar genomströmningen av ett rent och slitsat ALOHA-system kontra trafiken som anländer till terminalerna . $G$

Den maximala genomströmningen för ALOHA-systemet bestäms enligt följande:

Erhåller maximal genomströmning för ren och slitsad ALOHA

För ren ALOHA beror genomströmningen på belastningen som:

${\displaystyle \lambda _{pure}(G)=Ge^{-2G))$

Låt oss hitta sådana , där den maximala genomströmningen uppnås: $G$

${\displaystyle G_{pure}^{*}=\arg \max _{G\in \mathbb {R} ^{+}}~{\lambda _{pure}(G)))$ .

$\lambda _{pure}(0)=\lim _{G\to +\infty }{\lambda _{pure}(G)}=0$ .

${\frac {d\lambda _{pure}(G)}{dG}}=e^{-2G}-2Ge^{-2G}$ .

${\Bigl .}{\frac {d\lambda _{pure}(G)}{dG)){\Bigr |}_{G_{pure}^{*}}=e^{-2G_{ pure}^{*}}-2G_{pure}^{*}e^{-2G_{pure}^{*}}=0\Rightarrow G_{pure}^{*}={\frac {1}{2 }}$ .

$\lambda _{pure}(G_{pure}^{*})={\frac {1}{2e))\approx 0,18393972...$ .

För slitsad ALOHA beror genomströmningen på belastningen som:

${\displaystyle \lambda _{slot}(G)=Ge^{-G))$ .

${\displaystyle G_{slot}^{*}=\arg \max _{G\in \mathbb {R} ^{+}}~{\lambda _{slot}(G)))$ .

$\lambda _{slot}(0)=\lim _{G\to +\infty }{\lambda _{slot}(G)}=0$ .

${\frac {d\lambda _{slot}(G)}{dG}}=e^{-G}-Ge^{-G}$ .

${\Bigl .}{\frac {d\lambda _{slot}(G)}{dG)){\Bigr |}_{G_{slot}^{*}}=e^{-G_{ slot}^{*}}-G_{slot}^{*}e^{-G_{slot}^{*}}=0\Rightarrow G_{slot}^{*}=1$ .

$\lambda _{slot}(G_{slot}^{*})={\frac {1}{e}}=2\lambda _{pure}(G_{pure}^{*})\approx 0,36787944...$ .

Användningen av en slitsad ALOHA istället för en ren gjorde det således möjligt att fördubbla den maximala nätverksgenomströmningen. Som framgår av graferna, så länge belastningsvärdet är mindre än det kritiska värdet vid vilket maximivärdet uppnås, växer nätverkets genomströmning med ökad trafik - systemet används inte till 100 %. Men efter att ha överskridit det kritiska belastningsvärdet sjunker systemets genomströmning - för många paket kolliderar och sänds med fel.

För ren ALOHA är det kritiska belastningsvärdet , det vill säga ett datapaket dyker upp i genomsnitt per gång . För en slitsad ALOHA är det kritiska belastningsvärdet , det vill säga en dataram visas i genomsnitt per gång [6] . $G^{*}={\frac {1}{2))$ $2\tau$ $G^{*}=1$ $\tau$

Utveckling och applikation

Uppkomsten av radiorepeaters i ALOHAnet-nätverket gjorde det möjligt att utöka och effektivisera dess struktur [5] . 1973 kopplades ALOHAnet till ARPAnet med hjälp av en satellitlänk [3] .

Som en utveckling av idén om slumpmässig samtidig åtkomst till en kommunikationskanal, som först användes i ALOHA-systemet, skapades CSMA -metoden . Modifieringar av denna metod CSMA/CA och CSMA/CD utgjorde grunden för länkskiktsprotokollen för Ethernet- och Wi-Fi-nätverk [ 1] .

ALOHA random access används i mobila röst- och paketnätverk. I synnerhet när man upprättar en röst-, SMS- eller Internetanslutning, skickas det första paketet av den mobila enheten med hjälp av ALOHA slumpmässig åtkomst. ALOHA random access har också använts i satellitnätverk [1] .

En kraftigt modifierad version av den slitsade ALOHA används vid kommunikation av flera RFID- taggar med en enda läsare [6] .

Anteckningar

↑ 1 2 3 4 5 6 7 8 9 10 Schwartz, Abramson, 2009 .
↑ 2011 Mottagare av C&C-priset . NEC C&C Foundation. Tillträdesdatum: 3 januari 2016. Arkiverad från originalet 4 juni 2015. (obestämd)
↑ 1 2 3 4 Kuo, 1995 .
↑ Semenov Yu.A. Trådlösa (radio)kanaler och nätverk // Telecommunication technologys - Telecommunication technologys. — 2014.
↑ 1 2 3 Binder, Abramson, Kuo et al., 1975 .
↑ 1 2 3 4 5 6 7 8 Tanenbaum, Weatherall, 2012 .
↑ 12 Abramson , 1970 .
↑ Roberts, 1975 .

Litteratur

Abramson N. THE ALOHA SYSTEM (engelska) : Another Alternative for Computer Communications // AFIPS '70 (Fall) : Proceedings of the 17-19 November, 1970, Fall Joint Computer Conference - New York, NY, USA : ACM , 1970 . —S. 281-285. doi : 10.1145/1478462.1478502
Roberts L. ALOHA paketsystem med och utan platser och fånga // SIGCOMM Comput . kommun. Varv. - New York, NY, USA : ACM , 1975. - Vol. 5, Iss. 2. - S. 28-42. — ISSN 0146-4833 ; 1943-5819 - doi:10.1145/1024916.1024920
Binder R. , Abramson N. , Kuo F. F. , Okinaka A. , Wax D. ALOHA Packet Broadcasting: A Retrospect // AFIPS '75 : Proceedings of the National Computer Conference and Exposition 19-22 maj 1975 — New York, NY , USA : ACM , 1975. - P. 203-215. doi : 10.1145/1499949.1499985
Kuo F. F. ALOHA-systemet // SIGCOMM Comput . kommun. Varv. - New York, NY, USA : ACM , 1995. - Vol. 25, Iss. 1. - S. 41-44. — ISSN 0146-4833 ; 1943-5819 - doi:10.1145/205447
Schwartz M. , Abramson N. Alohanet - surfa efter trådlös data (engelska) : History of Communications // IEEE Communications Magazine - IEEE , 2009. - Vol. 47, Iss. 12. - P. 21-25. — ISSN 0163-6804 ; 1558-1896 - doi:10.1109/MCOM.2009.5350363
Tanenbaum E. , Weatherall D. Datornätverk - 5:e upplagan. - St Petersburg. : Peter , 2012. - S. 286-290. — 960 sid. — ISBN 978-5-459-00342-0

Länkar

James Pelkey. ALOHANET och Norm Abramson: 1966 - 1972 // Entrepreneurial Capitalism and Innovation: A History of Computer Communications 1968-1988.
2011 Mottagare av C&C-priset . NEC C&C Foundation. Hämtad: 3 januari 2016. (obestämd)
Aganesov Artur Valerievich. SATELLITKOMMUNIKATIONSNÄTVERKSMODEL BASERAD PÅ RANDOM MULTIPLE ACCESS PROTOKOLL S-ALOHA // Styrsystem, kommunikation och säkerhet. - 2015. - Nr 2 .