ALOHAnet

În telecomunicații, ALOHA este un protocol de rețea conceput pentru a garanta funcționalitatea accesului multiplu la mediul de transmisie a datelor partajat între mai mulți utilizatori. Protocolul ALOHA este utilizat pentru conexiunile de difuzare , unde mediul de transmisie este, prin urmare, partajat de mai mult de două puncte de conexiune (adică stații capabile să transmită și să primească informații). Acest protocol este de tip multicast și este utilizat la nivel MAC (Media Access Control).

Dezvoltat în anii șaptezeci de Norman Abramson (inițial pentru legături radio) de la Universitatea din Hawaii ( Aloha este de fapt binecunoscutul salut hawaian) pentru a conecta diferitele facultăți „împrăștiate” în jurul insulelor într-o rețea , acest protocol trebuie garantează corectitudinea și eficiența transmisiilor care, având loc pe rețelele partajate de multe stații, suferă numeroase coliziuni.

Există în principal trei tipuri de ALOHA, așa-numitul „pur”, „slotul” și „texturile și sloturile”.

ALOHA pur

Protocolul ALOHA pur (Aloha pur sau pur și simplu ALOHA), nu prevede restricții privind trimiterea datelor și, prin urmare, asupra ocupării benzii . Când o stație are date de transmis, le transmite.

Deoarece fiecare stație acționează independent de celelalte, succesul este determinat exclusiv de non-coliziune cu alte transmisii de către alte stații. Deoarece canalele de difuzare a da posibilitatea de a verifica (feedback - ul) , în cazul în care a transmis cadrul a fost recepționat în mod corect sau în cazul în care coliziuni au avut loc, ascultă stația de transmisie la canal și determină succesul sau eșecul transmisiei. Dacă nu este posibil să ascultați canalul, posturile așteaptă o confirmare ( ack ) de la receptor. Dacă există coliziuni (sau dacă ack-ul nu ajunge într-un timp de așteptare stabilit), cadrele corupte sunt distruse. Acest lucru este indiferent de nivelul corupției datelor; atunci când un cadru a fost afectat de o coliziune, acesta este aruncat. În acest caz, stația expeditorului retransmite cadrul după o așteptare aleatorie și ascultă din nou pe canal (sau așteaptă un ack) până când stabilește că cadrul a fost primit corect.

Figura 1 de mai jos prezintă un exemplu de comunicare folosind ALOHA pur. Stațiile de radiodifuziune își trimit mesajele de-a lungul canalului partajat. Dacă intervalul de timp în care două sau mai multe stații transmit se suprapune, atunci se va produce o coliziune; prin urmare, stațiile implicate nu vor primi niciun ack și, prin urmare, vor trebui să reîncerce transmisia mai târziu.

Pentru a preveni coliziunea de a se repeta la nesfârșit, stațiile implicate ar trebui să încerce retransmisia lor în momente distincte, astfel încât să reducă probabilitatea unor noi suprapuneri între cele două perioade de transmisie. Deoarece stațiile acționează independent, cel mai bun mod de a evita suprapunerea retransmisiilor este ca fiecare stație să aleagă aleatoriu, cu constrângeri adecvate, momentul în care să încerce să retransmită. Acest lucru se face folosind un mecanism de retragere, conform căruia retransmisia se efectuează după o întârziere selectată aleatoriu între 0 și 2 ^ (K-1) * T, unde T este timpul de transmisie al mesajului și K poate depinde posibil asupra numărului de coliziuni care au avut loc deja. Figura 2 de mai jos prezintă perioada de vulnerabilitate pentru Aloha, adică perioada în care un pachet P, cu timp de transmisie egal cu T, este vulnerabil la o coliziune.

Privind Figura 2, putem vedea că dacă o stație începe transmisia în intervalul dintre $t_{0}-T$ ${\ displaystyle t_ {0} -T}$ ${\ displaystyle t_ {0} -T}$ la $t_{0}+T$ ${\ displaystyle t_ {0} + T}$ ${\ displaystyle t_ {0} + T}$ cu siguranță provoacă o coliziune; de aceea perioada de vulnerabilitate este egală cu $2T$ ${\ displaystyle 2T}$ ${\ displaystyle 2T}$ .

Adevărata tranzitată pentru Pure aloha este egal cu: $S=G\cdot e^{-2G}$ ${\ displaystyle S = G \ cdot e ^ {- 2G}}$ ${\ displaystyle S = G \ cdot e ^ {- 2G}}$ unde este $G.$ ${\ displaystyle G}$ $G.$ este numărul mediu de cadre transmise în timpul cadrului în timp ce $S.$ ${\ displaystyle S}$ $S.$ este numărul de cadre transmise cu succes;

Deci, eficiența în cel mai bun caz al Pure ALOHA este de 18,4%, obținută când G este 0,5.

Eficiență maximă pură ALOHA

Să presupunem că avem N noduri care transmit independent unul de celălalt cu probabilitate p între 0 și 1. Numit T timpul necesar transmiterii unui pachet, nodul i transmite un pachet fără coliziuni când începe să-l transmită la momentul de timp $t_{0}$ ${\ displaystyle t_ {0}}$ $t_ {0}$ și niciunul dintre celelalte noduri nu efectuează o transmisie în intervalul de timp $[t_{0}-T,t_{0}+T]$ ${\ displaystyle [t_ {0} -T, t_ {0} + T]}$ ${\ displaystyle [t_ {0} -T, t_ {0} + T]}$ (vezi graficul din paragraful anterior). Prin urmare, probabilitatea transmiterii fără coliziune pentru nodul i este egală cu:
$S(p)=Np\left(1-p\right)^{2(N-1)}$ ${\ displaystyle S (p) = Np \ left (1-p \ right) ^ {2 (N-1)}}$ ${\ displaystyle S (p) = Np \ left (1-p \ right) ^ {2 (N-1)}}$

unde 2 care se înmulțește în exponentul lui (1-p) se datorează tocmai faptului că luăm în considerare probabilitatea ca celelalte stații să nu transmită începe de la $t_{0}-T$ ${\ displaystyle t_ {0} -T}$ ${\ displaystyle t_ {0} -T}$ asta dă $t_{0}+T$ ${\ displaystyle t_ {0} + T}$ ${\ displaystyle t_ {0} + T}$ .

Găsirea eficienței maxime a protocolului ALOHA pur înseamnă găsirea valorii lui p , să o numim $p^{*}$ ${\ displaystyle p ^ {*}}$ $p ^ {*}$ , pentru care S (p) este maximizat și apoi calculați limita pentru N care tinde spre infinit. Situația practică luată în considerare este prezența unor noduri infinite care au întotdeauna date de transmis:

${dS(p^{*}) \over dp^{*}}=N(1-p^{*})^{2(N-1)}-2Np^{*}(N-1)(1-p^{*})^{2(N-1)-1}=0$ ${\ displaystyle {dS (p ^ {*}) \ over dp ^ {*}} = N (1-p ^ {*}) ^ {2 (N-1)} - 2Np ^ {*} (N-1 ) (1-p ^ {*}) ^ {2 (N-1) -1} = 0}$ ${\ displaystyle {dS (p ^ {*}) \ over dp ^ {*}} = N (1-p ^ {*}) ^ {2 (N-1)} - 2Np ^ {*} (N-1 ) (1-p ^ {*}) ^ {2 (N-1) -1} = 0}$

$N(1-p^{*})^{2(N-1)}\left[{{1-p^{*}-2Np^{*}+2p^{*}} \over {1-p*}}\right]=0$ ${\ displaystyle N (1-p ^ {*}) ^ {2 (N-1)} \ left [{{1-p ^ {*} - 2Np ^ {*} + 2p ^ {*}} \ over { 1-p *}} \ dreapta] = 0}$ ${\ displaystyle N (1-p ^ {*}) ^ {2 (N-1)} \ left [{{1-p ^ {*} - 2Np ^ {*} + 2p ^ {*}} \ over { 1-p *}} \ dreapta] = 0}$

$N(1-p^{*})^{2(N-1)}\left[{{1+p^{*}-2Np^{*}} \over {1-p*}}\right]=0$ ${\ displaystyle N (1-p ^ {*}) ^ {2 (N-1)} \ left [{{1 + p ^ {*} - 2Np ^ {*}} \ peste {1-p *}} \ dreapta] = 0}$ ${\ displaystyle N (1-p ^ {*}) ^ {2 (N-1)} \ left [{{1 + p ^ {*} - 2Np ^ {*}} \ peste {1-p *}} \ dreapta] = 0}$

$N(1-p^{*})^{2(N-1)}\left(1+p^{*}-2Np^{*}\right)=0$ ${\ displaystyle N (1-p ^ {*}) ^ {2 (N-1)} \ left (1 + p ^ {*} - 2Np ^ {*} \ right) = 0}$ ${\ displaystyle N (1-p ^ {*}) ^ {2 (N-1)} \ left (1 + p ^ {*} - 2Np ^ {*} \ right) = 0}$

$N\left(1+p^{*}-2Np^{*}\right)=0$ ${\ displaystyle N \ left (1 + p ^ {*} - 2Np ^ {*} \ right) = 0}$ ${\ displaystyle N \ left (1 + p ^ {*} - 2Np ^ {*} \ right) = 0}$

$p^{*}={1 \over {2N-1}}$ ${\ displaystyle p ^ {*} = {1 \ peste {2N-1}}}$ ${\ displaystyle p ^ {*} = {1 \ peste {2N-1}}}$

Înlocuind valoarea $p^{*}$ ${\ displaystyle p ^ {*}}$ $p ^ {*}$ în S (p) și trecând la limita pentru N care tinde spre + $\infty$ ${\ displaystyle \ infty}$ $\ infty$ primesti:

$\lim _{N\to +\infty }{S(p^{*})}=\lim _{N\to +\infty }{N \over {2N-1}}{\left(1-{1 \over {2N-1}}\right)^{2(N-1)}}$ ${\ displaystyle \ lim _ {N \ to + \ infty} {S (p ^ {*})} = \ lim _ {N \ to + \ infty} {N \ peste {2N-1}} {\ left ( 1- {1 \ peste {2N-1}} \ dreapta) ^ {2 (N-1)}}}$ ${\ displaystyle \ lim _ {N \ to + \ infty} {S (p ^ {*})} = \ lim _ {N \ to + \ infty} {N \ peste {2N-1}} {\ left ( 1- {1 \ peste {2N-1}} \ dreapta) ^ {2 (N-1)}}}$

Pentru a simplifica această relație, să schimbăm variabila:

$x=2N-1,\qquad N={{x+1} \over 2},\qquad 2(N-1)=x-1$ ${\ displaystyle x = 2N-1, \ qquad N = {{x + 1} \ over 2}, \ qquad 2 (N-1) = x-1}$ ${\ displaystyle x = 2N-1, \ qquad N = {{x + 1} \ over 2}, \ qquad 2 (N-1) = x-1}$

$\lim _{x\to +\infty }{{x+1} \over {2x}}{x \over {x-1}}\left(1-{1 \over x}\right)^{x}=\lim _{x\to +\infty }{{x+1} \over {2x-2}}\left(1-{1 \over x}\right)^{x}={1 \over {2e}}\approx 18.4\%$ ${\ displaystyle \ lim _ {x \ to + \ infty} {{x + 1} \ over {2x}} {x \ over {x-1}} \ left (1- {1 \ over x} \ right) ^ {x} = \ lim _ {x \ to + \ infty} {{x + 1} \ over {2x-2}} \ left (1- {1 \ over x} \ right) ^ {x} = { 1 \ peste {2e}} \ aproximativ 18,4 \%}$ ${\ displaystyle \ lim _ {x \ to + \ infty} {{x + 1} \ over {2x}} {x \ over {x-1}} \ left (1- {1 \ over x} \ right) ^ {x} = \ lim _ {x \ to + \ infty} {{x + 1} \ over {2x-2}} \ left (1- {1 \ over x} \ right) ^ {x} = { 1 \ peste {2e}} \ aproximativ 18,4 \%}$

Slot ALOHA

Protocolul Slot Aloha (Roberts 1972) adaugă o altă caracteristică protocolului Aloha (din care derivă), și anume împărțirea timpului în intervale discrete numite sloturi. Fiecare post este obligat să-și înceapă difuzarea la începutul unui interval de timp (a se vedea Figura 3 de exemplu). Dacă o stație este gata să transmită într-un anumit moment, trebuie să aștepte în mod necesar începutul următorului slot. Consecința acestei caracteristici este că două transmisii fie se ciocnesc complet în același slot, fie nu se ciocnesc deloc; problema coliziunilor parțiale observată în ALOHA este astfel eliminată.

Așa cum este ilustrat în Figura 4 de mai jos, protocolul Slot Aloha are ca rezultat înjumătățirea perioadei de vulnerabilitate, care în acest caz este egală cu T. Eficiența maximă este în consecință dublată, deci egală cu 36,8%.

Dezavantajul acestui protocol este necesitatea unui mecanism de sincronizare care să indice diferitelor stații când pot începe transmisia.

Eficiență maximă ALOHA SLOTTED

Să presupunem că avem N noduri care transmit independent unul de celălalt cu probabilitate $p$ ${\ displaystyle p}$ $p$ între 0 și 1. Un nod transmite fără coliziuni atunci când este singurul care face o transmisie într-un anumit slot. Prin urmare, probabilitatea transmiterii fără coliziune pentru un nod este egală cu:

$S(p)=Np\left(1-p\right)^{N-1}$ ${\ displaystyle S (p) = Np \ left (1-p \ right) ^ {N-1}}$ ${\ displaystyle S (p) = Np \ left (1-p \ right) ^ {N-1}}$

Găsirea eficienței maxime a protocolului SLOTTED ALOHA înseamnă găsirea valorii $p$ ${\ displaystyle p}$ $p$ , să-i spunem $p^{*}$ ${\ displaystyle p ^ {*}}$ $p ^ {*}$ , pentru care S (p) este maximizat și apoi calculați limita pentru N care tinde spre infinit. Situația practică luată în considerare este prezența unor noduri infinite care au întotdeauna date de transmis:

${dS(p^{*}) \over dp^{*}}=N(1-p^{*})^{N-1}-Np^{*}(N-1)(1-p^{*})^{N-2}=0$ ${\ displaystyle {dS (p ^ {*}) \ over dp ^ {*}} = N (1-p ^ {*}) ^ {N-1} -Np ^ {*} (N-1) (1 -p ^ {*}) ^ {N-2} = 0}$ ${\ displaystyle {dS (p ^ {*}) \ over dp ^ {*}} = N (1-p ^ {*}) ^ {N-1} -Np ^ {*} (N-1) (1 -p ^ {*}) ^ {N-2} = 0}$

$N(1-p^{*})^{N-2}\left[(1-p^{*})-p^{*}(N-1)\right]=0$ ${\ displaystyle N (1-p ^ {*}) ^ {N-2} \ left [(1-p ^ {*}) - p ^ {*} (N-1) \ right] = 0}$ ${\ displaystyle N (1-p ^ {*}) ^ {N-2} \ left [(1-p ^ {*}) - p ^ {*} (N-1) \ right] = 0}$

$N(1-p^{*})^{N-2}\left(1-Np^{*}\right)=0$ ${\ displaystyle N (1-p ^ {*}) ^ {N-2} \ left (1-Np ^ {*} \ right) = 0}$ ${\ displaystyle N (1-p ^ {*}) ^ {N-2} \ left (1-Np ^ {*} \ right) = 0}$

${{N(1-Np^{*})(1-p*)^{N}} \over {(1-p^{*})^{2}}}=0$ ${\ displaystyle {{N (1-Np ^ {*}) (1-p *) ^ {N}} \ over {(1-p ^ {*}) ^ {2}}} = 0}$ ${\ displaystyle {{N (1-Np ^ {*}) (1-p *) ^ {N}} \ over {(1-p ^ {*}) ^ {2}}} = 0}$

$(1-Np^{*})\left(1-p^{*}\right)=0$ ${\ displaystyle (1-Np ^ {*}) \ left (1-p ^ {*} \ right) = 0}$ ${\ displaystyle (1-Np ^ {*}) \ left (1-p ^ {*} \ right) = 0}$

$p^{*}={1 \over N}$ ${\ displaystyle p ^ {*} = {1 \ peste N}}$ ${\ displaystyle p ^ {*} = {1 \ peste N}}$

Înlocuind valoarea $p^{*}$ ${\ displaystyle p ^ {*}}$ $p ^ {*}$ în S (p) și trecând la limita pentru N care tinde spre + $\infty$ ${\ displaystyle \ infty}$ $\ infty$ primesti:

$\lim _{N\to +\infty }{S(p^{*})}=\lim _{N\to +\infty }{N{1 \over N}\left(1-{1 \over N}\right)^{N-1}}=\lim _{N\to +\infty }{{\left(1-{1 \over N}\right)^{N}} \over {1-{1 \over N}}}={1 \over e}\approx 0.368=36.8\%$ ${\ displaystyle \ lim _ {N \ to + \ infty} {S (p ^ {*})} = \ lim _ {N \ to + \ infty} {N {1 \ over N} \ left (1- { 1 \ over N} \ right) ^ {N-1}} = \ lim _ {N \ to + \ infty} {{\ left (1- {1 \ over N} \ right) ^ {N}} \ over {1- {1 \ peste N}}} = {1 \ peste e} \ aproximativ 0,368 = 36,8 \%}$ ${\ displaystyle \ lim _ {N \ to + \ infty} {S (p ^ {*})} = \ lim _ {N \ to + \ infty} {N {1 \ over N} \ left (1- { 1 \ over N} \ right) ^ {N-1}} = \ lim _ {N \ to + \ infty} {{\ left (1- {1 \ over N} \ right) ^ {N}} \ over {1- {1 \ peste N}}} = {1 \ peste e} \ aproximativ 0,368 = 36,8 \%}$

ALOHA cu fanta încadrată

O altă variantă este cea numită Aloha cu fante încadrate. Acest protocol, în plus față de împărțirea timpului în sloturi ca Slot Aloha, îi grupează pe acesta din urmă în cadre, fiecare dintre care va consta din N sloturi. Fiecare stație este permisă să transmită o singură dată într-un cadru, într-un slot selectat aleatoriu din N-ul disponibil. Figura 5 de mai jos prezintă un exemplu al protocolului descris:

Cu protocoalele Aloha și Slotted Aloha discutate mai sus, o stație cu o rată de transmisie prea mare a provocat coliziuni inutile cu potențiale răspunsuri valide de la alte stații din câmpul de citire. Gruparea sloturilor în cadre, împiedicând trimiterea a mai mult de un pachet pe cadru, implică implicit o limitare a ratei maxime de transmisie pentru fiecare stație. Cheltuielile generale de calcul cerute de protocolul Aloha cu fante încadrate pentru sincronizare sunt de același ordin de mărime ca și pentru protocolul Aloha cu fante. În virtutea acestor caracteristici, această variantă este cea care oferă deseori cele mai bune performanțe.

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe ALOHAnet

Portal telematic : accesați intrări Wikipedia care vorbesc despre rețele, telecomunicații și protocoale de rețea