ALOHAnet

Da Wikipedia, l'enciclopedia libera.

In telecomunicazioni ALOHA è un protocollo di rete atto a garantire le funzionalità di accesso multiplo al mezzo di trasmissione dati condiviso tra più utenti. Il protocollo ALOHA viene utilizzato per connessioni di tipo broadcast, dove quindi il mezzo di trasmissione è condiviso da più di due punti di connessione (ovvero postazioni capaci di trasmettere e ricevere informazioni). Tale protocollo è di tipo multicast ed è utilizzato a livello MAC (Media Access Control, controllo di accesso al mezzo).

Sviluppato negli anni settanta da Norman Abramson (originariamente per collegamenti radio) dell'università delle Hawaii (Aloha è infatti il noto saluto hawaiano) per poter collegare in un network le varie facoltà "sparpagliate" per le isole, questo protocollo deve garantire la correttezza e l'efficienza delle trasmissioni che, avvenendo appunto su reti condivise da molte postazioni, vanno incontro a numerose collisioni.

Esistono principalmente tre tipi di ALOHA, quello cosiddetto "puro", quello "a slot" e quello "a trame e a slot".

ALOHA puro[modifica | modifica sorgente]

Il protocollo ALOHA puro (pure Aloha o semplicemente ALOHA), non prevede vincoli all'invio di dati e quindi all'occupazione della banda. Quando una postazione ha dati da trasmettere, li trasmette.

Poiché ogni stazione agisce indipendentemente dalle altre, il successo è determinato unicamente dalla mancata collisione con altre trasmissioni da parte di altre stazioni. Poiché i canali broadcast danno la possibilità di verificare (feedback) se il frame trasmesso è stato ricevuto correttamente oppure se si sono verificate collisioni, la stazione trasmittente ascolta il canale e determina il successo o l'insuccesso della trasmissione. Qualora non sia possibile ascoltare il canale le stazioni si mettono in attesa di un riscontro (ack) da parte del ricevente. Se ci sono collisioni (o se l'ack non arriva entro un tempo di attesa stabilito), i frame corrotti vengono distrutti. Ciò indipendentemente dal livello di corruzione dei dati; quando un frame è stato interessato da collisione, viene eliminato. In questo caso la postazione mittente reinvia il frame dopo un'attesa casuale e si rimette in ascolto sul canale (o attende un ack) fino a quando non stabilisce che il frame è stato ricevuto correttamente.

La figura 1 sottostante mostra un esempio di comunicazione tramite ALOHA puro. Le stazioni trasmittenti inviano i loro messaggi lungo il canale condiviso. Se l’intervallo di tempo durante il quale due o più stazioni trasmettono si sovrappone, allora si avrà una collisione; quindi le stazioni coinvolte non riceveranno alcun ack e dovranno perciò ritentare la trasmissione in un istante successivo.

Aloha - esempio di collisione parziale.gif

Per evitare che la collisione si ripeta indefinitamente è opportuno che le stazioni coinvolte tentino la loro ritrasmissione in tempi distinti, in modo da ridurre la probabilità di nuove sovrapposizioni fra i due periodi di trasmissione. Poiché le stazioni agiscono indipendentemente, il modo migliore per evitare la sovrapposizione delle ritrasmissioni è che ogni stazione scelga casualmente, con opportuni vincoli, l’istante di tempo in cui provare a ritrasmettere. Ciò si attua utilizzando un meccanismo di back-off, secondo il quale la ritrasmissione viene effettuata dopo un ritardo selezionato casualmente compreso tra 0 e (K-1)T, dove T è il tempo di trasmissione del messaggio e K può eventualmente dipendere dal numero di collisioni già avvenute. Nella figura 2 sottostante è mostrato il periodo di vulnerabilità per Aloha, ovvero il periodo durante il quale un pacchetto P, con tempo di trasmissione pari a T, risulta vulnerabile a una collisione.

Periodo di vulnerabilità in aloha.gif

Osservando la figura 2, possiamo rilevare che se una qualunque stazione inizia la propria trasmissione nell’intervallo compreso tra t0−T a t0+T causa di sicuro una collisione; perciò il periodo di vulnerabilità è pari a 2T.

Il throughput reale per quanto riguarda il Pure ALOHA è pari a: S=G*e^(-2G) dove G=numero medio di trame trasmesse nel tempo di trama S=numero di trame trasmesse con successo Quindi l'efficienza nel caso migliore del Pure ALOHA è pari al 18,4%, raggiunta quando G è pari a 0,5.

Efficienza massima ALOHA puro[modifica | modifica sorgente]

Supponiamo di avere N nodi che trasmettono in modo indipendente gli uni dagli altri con probabilità p compresa tra 0 e 1. Detto T il tempo necessario alla trasmissione di un pacchetto, si ha che il nodo i trasmette un pacchetto senza collisioni quando inizia a trasmetterlo all'istante di tempo t_0 e nessuno degli altri nodi effettua una trasmissione nell'intervallo di tempo [t_0-T, t_0+T] (vedi grafico paragrafo precedente). Quindi la probabilità di trasmissione senza collisioni per il nodo i è pari a:

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

Trovare l'efficienza massima del protocollo ALOHA puro vuol dire trovare il valore di p, chiamiamolo p^*, per il quale sia massimizzata S(p) e poi calcolarne il limite per N che tende a infinito. La situazione pratica considerata è la presenza di infiniti nodi che abbiano sempre dati da trasmettere:

{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

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

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

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

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

Sostituendo il valore di p^* in S(p) e passando al limite per N che tende a +\infty si ottiene:

\lim_{N \to +\infty}{S(p^*)} = \lim_{N \to +\infty}{N \over {2N-1}}{ \left (1-{1 \over {2N-1}} \right )^{2(N-1)}}

Per semplificare tale relazione, effettuiamo il cambio di variabile:

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%

Slotted ALOHA[modifica | modifica sorgente]

Il protocollo Slotted Aloha (Roberts 1972) aggiunge al protocollo Aloha da cui deriva un’ulteriore caratteristica, ovvero quella che il tempo è suddiviso in intervalli discreti chiamati slot. Ogni stazione è vincolata a cominciare la propria trasmissione necessariamente all’inizio di uno slot temporale (come esempio si veda la figura 3). Se una stazione ad un certo istante è pronta a trasmettere dovrà attendere necessariamente l’inizio del successivo slot. La conseguenza di tale caratteristica è che due trasmissioni o collidono completamente all’interno dello stesso slot oppure non collidono affatto; il problema delle collisioni parziali osservato in Aloha risulta in questo modo eliminato.

Slotted aloha.gif

Come illustrato nella figura 4 sottostante, il protocollo Slotted Aloha ha come conseguenza il dimezzamento del periodo di vulnerabilità, che in tal caso è pari a T. L'efficienza massima risulta conseguentemente raddoppiata, pari quindi al 36,8%.

Periodo di vulnerabilità in aloha slotted.gif

Lo svantaggio di questo protocollo è la necessità di un meccanismo di sincronizzazione che indichi alle varie stazioni quando possono cominciare la trasmissione.

Efficienza massima SLOTTED ALOHA[modifica | modifica sorgente]

Supponiamo di avere N nodi che trasmettono in modo indipendente gli uni dagli altri con probabilità p compresa tra 0 e 1. Si ha che un nodo trasmette senza collisioni quando è l'unico ad effettuare una trasmissione in un determinato slot. Quindi la probabilità di trasmissione senza collisioni per un nodo è pari a:

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

Trovare l'efficienza massima del protocollo SLOTTED ALOHA vuol dire trovare il valore di p, chiamiamolo p^*, per il quale sia massimizzata S(p) e poi calcolarne il limite per N che tende a infinito. La situazione pratica considerata è la presenza di infiniti nodi che abbiano sempre dati da trasmettere:

{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

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

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

(1-Np^*) \left(1-p^* \right ) = 0

p^* = {1 \over N}

Sostituendo il valore di p^* in S(p) e passando al limite per N che tende a +\infty si ottiene:

\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%

Framed slotted ALOHA[modifica | modifica sorgente]

Un’ulteriore variante è quella chiamata Framed Slotted Aloha. Tale protocollo, oltre a suddividere come Slotted Aloha il tempo in slot, raggruppa questi ultimi in trame ciascuna delle quali sarà costituita da N slot. A ciascuna stazione è consentito trasmettere una sola volta all’interno di una trama, in uno slot selezionato casualmente fra gli N disponibili. La figura 5 sottostante mostra un esempio del protocollo descritto:

Esempio di protocollo Framed Slotted Aloha.gif

Con i protocolli Aloha e Slotted Aloha illustrati in precedenza, una stazione con un rate di trasmissione troppo alto provocava inutili collisioni con le potenziali risposte valide provenienti dagli altre stazioni nel campo di lettura. Il raggruppamento degli slot in trame, impedendo l’invio di più di pacchetto per trama, impone implicitamente una limitazione al rate massimo di trasmissione per ogni stazione. Il sovraccarico computazionale richiesto dal protocollo Framed Slotted Aloha per la sincronizzazione è dello stesso ordine di grandezza di quello per il protocollo Slotted Aloha. In virtù di queste caratteristiche, tale variante è quella che offre sovente le migliori prestazioni.

Altri progetti[modifica | modifica sorgente]

Telematica Portale Telematica: accedi alle voci di Wikipedia che parlano di reti, telecomunicazioni e protocolli di rete