Swappa : Uni / Protocolli avanzati di rete - Appunti del 11 e 12 Maggio
Creative Commons License

Torna alla pagina di Protocolli avanzati di rete


 :: Protocolli avanzati di rete - Appunti del 11 e 12 Maggio ::

Ripassone: Media Access Protocol su reti wireless

Lo standard definito per le reti wireless è l'IEEE 802.11 o Wi-Fi, e si riferisce in particolare al livello fisico e MAC del modello ISO/OSI. Comprende una famiglia di protocolli, di cui tre dedicati alla trasmissione delle informazioni (a, b, g), uno per la sicurezza (i), ed altri come estensioni e miglioramenti dei servizi di base. Il primo protocollo largamente diffuso è stato il b; in seguito si sono diffusi il protocollo a e soprattutto il g.

Lo standard 802.11 gestisce sia reti ad hoc (sprovviste di struttura client-server) che reti ad infrastruttura, queste ultime costituite da una o più celle indipendenti ognuna delle quali è controllata da una stazione base chiamata Access Point (o AP).

Problemi del CSMA/CD

Il canale wireless è un mezzo trasmissivo condiviso, quindi abbiamo bisogno di un meccanismo di controllo e gestione che limiti il numero di interferenze tra i dispositivi che vi accedono. E' possibile applicare lo stesso protocollo usato per ethernet perché tutto funzioni e per limitare il numero di collisioni? Stiamo parlando del CSMA/CD, ovvero:

Vediamo ora qual è il problema della stazione nascosta/esposta.
Consideriamo tre stazioni (A, B e C), di cui sono indicati i raggi d'azione, e con A che sta trasmettendo a B.

Se C sta ascoltando il mezzo lo troverà libero dato che è fuori dal raggio di azione di A, dunque sarà convinto di poter trasmettere a B. Così facendo disturberà però la trasmissione di A, impedendo a B di ricevere sia la sua che quello dell'altro, che saranno costretti a ritrasmettere. Questo è noto come il problema della stazione nascosta.

Consideriamo adesso quattro stazioni (A, B, C e D), di cui sono indicati i raggi d'azione, e con B che sta trasmettendo ad A e C che vuole trasmettere a D.

Se C sta ascoltando il mezzo lo troverà occupato dato che rileverà la trasmissione di B, dunque sarà erroneamente convinto di non poter trasmettere. In realtà D è fuori dalla portata di B, ed A fuori da quella di C, quindi le trasmissioni potrebbero benissimo avvenire parallelamente senza interferenze. Questo è noto come il problema della stazione esposta.

Come risolviamo tutto questo?

CSMA/CA

La Collision Avoidance (CA) permette di prevenire il manifestarsi di collisioni attraverso l'utilizzo di appositi segnali di sincronizzazione: il Request To Send (RTS) e il Clear To Send (CTS). Entrambi i frame contengono il tempo mancante prima della fine della trasmissione, quindi ogni stazione che li riceve potrà impostare il proprio indicatore di Carrier Sensing Virtuale per la durata indicata dai frame. Questo indicatore è chiamato NAV (Network Allocation Vector) ed è un vero e proprio contatore che viene decrementato nel tempo fino ad arrivare a 0: se è diverso da 0 significa che nelle vicinanze qualcuno sta trasmettendo.

Nell'ipotesi in cui ogni stazione abbia lo stesso raggio di azione e che gli RTS e CTS possano essere scambiati in un tempo infinitesimo, il protocollo è il seguente:

  1. quando la stazione A vuole trasmettere un frame a B gli invia prima una RTS
  2. B gli risponde con una CTS
  3. quando A riceve la CTS può iniziare a trasmettere

Nella stragrande maggioranza dei casi la nostra rete non soddisferà le ipotesi stringenti che abbiamo appena enunciato, dunque ci troveremmo nella situazione di non poter garantire la totale assenza di collisioni. Per questo motivo alla Collision Avoidance vengono affiancati i protocolli di Carrier Sensing (CS) e Multiple Access (MA): i primi ridurranno il numero di collisioni dovute a tentativi di accesso contemporaneo al mezzo, i secondi introdurranno il l'acknowledgement a livello di MAC sublayer. Questo secondo punto è molto più semplice di quanto possa sembrare, ovvero prevede la trasmissione di un segnale di ACK da parte del ricevente quando riceve con successo il frame inviatogli dal mittente.
Alla luce di tutte queste innovazioni, vediamo come funziona il protocollo CSMA/CA:

  1. la stazione trasmittente A cerca di determinare lo stato del mezzo valutando il contenuto del NAV ed ascoltando il mezzo. Il canale è considerato libero quando sia il Carrier Sensing Virtuale che quello Reale non rilevano attività. I casi sono due:
    • Se il canale rimane libero per un intervallo di tempo DIFS (che vedremo poi), salta al punto 3
    • Se invece il canale è occupato (o viene occupato durante l’intervallo DIFS), prosegue al punto 2
  2. A avvia la procedura di back-off (che vedremo poi)
  3. A invia la RTS
  4. Se entro un intervallo di tempo ben definito A non riceve il CTS da B, molto probabilmente l’RTS ha colliso con un altro frame. Impareremo che spesso ciò significa che due stazioni hanno scelto lo stesso slot nella finestra di back-off, quindi A prima di ritentare la trasmissione raddoppierà la dimensione di tale finestra, e poi ripeterà tutto dal punto 2. Lo scopo di tale raddoppiamento è quello di adattare la dimensione della finestra al numero di contendenti, in virtù del fatto che le collisioni sono indice di "affollamento"
  5. Quando B riceve l’RTS, risponde con un CTS
  6. Ricevuto il CTS, A può cominciare a trasmettere il frame con i dati veri e propri
  7. Se entro un intervallo di tempo ben definito A non riceve un ACK da B, vuol dire che il frame Dati non è stato ricevuto correttamente, e quindi A deve ritrasmetterlo ripetendo tutta la procedura
  8. Una volta che B ha ricevuto correttamente il frame Dati, risponde con un ACK concludendo il protocollo

Concludiamo il paragrafo con un esempio. Abbiamo quattro stazioni (A, B, C, D), ed A vuole trasmettere a B:

Dal grafico in funzione del tempo capiamo al volo che D è nel raggio di azione di B ma non di A, dato che aggiorna il proprio NAV solo dopo aver ricevuto la Clear To Send inviata da B.

MACA e MACAW

Dimentichiamo quanto detto nell'ultimo paragrafo e facciamo un passo indietro, a quando avevamo scoperto che il protocollo CSMA/CD non è sufficiente per risolvere i problemi di collisione su reti wireless. In particolare, la rilevazione del canale (quindi la Carrier Sense) era problematica dal momento che se il canale è libero (o occupato) per il trasmettitore non è detto che lo sia per il ricevitore.
Possiamo superare entrambi i problemi adottando il protocollo MACA (Multiple Access with Collision Avoidance), nel quale non c'è ascolto del canale e si cerca di prevenire le collisioni piuttosto che rilevarle. Si implementa con le RTS e le CTS che abbiamo già visto, e il comportamento delle stazioni è il seguente:

Questa tecnica non garantisce l'assenza totale di collisioni, però fa si che siano circoscritte ai frame RTS e CTS, che essendo di dimensioni ridotte non influiranno pesantemente sulle trasmissioni.
Un'evoluzione del protocollo MACA è rappresentata dal MACAW (MACA for Wireless), che introduce alcune migliorie:

Protocolli MAC

Nello standard 802.11 sono previste due modalità di funzionamento:

Tutte le stazioni della rete devono supportare DCF, mentre PCF è opzionale e raramente implementato.

IFS

Gli InterFrame Spaces (IFS) sono quei tempi di attesa da lasciare tra un evento di protocollo e l'altro, e che permettono la sincronizzazione tra trasmissioni e la creazione di diversi livelli di priorità a seconda del tipo di traffico.

Nel protocollo 802.11 ne esistono quattro tipi diversi:

Buttiamola sul pratico. Un protocollo che invia video in streaming deve garantire un tasso di recapito costante a livello applicativo, quindi anche a livello 2; per questo motivo dovrei mantenere sempre i SIFS come tempo di attesa, così da garantire alta priorità. Se invece consideriamo un protocollo che gestisce il file sharing, tipicamente si attenderanno intervalli DIFS dal momento che non tutti i pacchetti hanno la stessa priorità.
Breve digressione sullo streaming. Abbiamo appena detto che dovrei garantire un tasso di recapito costante a livello 2, ma nel wireless questo requisito è particolarmente difficile da soddisfare sia per il traffico che per la carica residua delle batterie. Una soluzione consiste nel monitorare le informazioni sulla qualità della rete, e in base ad esse cambiare in run-time la codifica dello streaming; mantengo cioè diverse versioni a diversa qualità e risoluzione dello stesso media, e a seconda della variabilità della rete invio quello più indicata. La fregatura è che devo allungare i tempi di pre-caricamento, il che è rischioso dal momento che poi verrebbe meno il concetto stesso di streaming. A ogni modo, questa tecnica è ancora oggetto di ricerca.

Back-off

La procedura di back-off è stata inserita nelle fasi del protocollo CSMA/CA in cui le collisioni sono più frequenti, e consiste nell’attendere per un tempo casuale (limitato) calcolato con l’algoritmo di binary exponential back-off. L'obiettivo è evitare che tutte le stazioni in attesa che il canale si liberi tentino di acquisirlo contemporaneamente nell'istante in cui questo viene rilasciato.

La procedura base di back-off richiede che ogni stazione scelga un numero casuale compreso tra 0 e un valore CW (Contention Window, la dimensione della finestra di contesa), e aspetti per questo numero di slot prima di accedere al mezzo, effettuando comunque il controllo sulla portante per vedere se qualche altra stazione sta tentando di accedere al mezzo. Lo Slot time è definito infatti in modo tale che la stazione sia sempre capace di determinare se un’altra abbia acceduto al mezzo all’inizio del precedente slot, così da ridurre drasticamente le probabilità di collisione.

Il back-off esponenziale impone invece che ogni volta che la stazione sceglie uno slot per la trasmissione e si verifica una collisione venga esponenzialmente aumentato il valore della CW, così da limitare il rischio che la collisione si ripeta. In particolare, lo standard 802.11 prevede che l'algoritmo di back-off esponenziale debba essere eseguito nei seguenti casi:

Se invece una stazione decide di inviare un frame e rileva che il mezzo è libero per un tempo maggiore di DIFS, allora tutto questo meccanismo non si mette in moto e la trasmissione avviene tranquillamente.

Il rettangolo fucsia dell'immagine sopra contiene il numero casuale di slot che in caso di collisione dovrò attendere per via del meccanismo di back-off.

Ci potremmo chiedere: è fair questa procedura? Riesce ad assicurare una ripartizione (più o meno) equa della banda? Non molto, dipende da quanto sono diversi i valori di back-off scelti dalle stazioni che sono entrate in collisione.
Facciamo un esempio:

Il protocollo a contesa quindi premia il vincitore, ma questo non vuol dire che sia sempre una cosa da evitare: in uno scenario client-server che senso avrebbe avere un client che ha più banda del server??

Ultima nota: il meccanismo di exponential back-off è validato solo a livello di simulazioni, ma non è ancora stato validato a livello di modello (quindi a priori).


Torna alla pagina di Protocolli avanzati di rete

(Printable View of http://www.swappa.it/wiki/Uni/PAR-11e12Maggio)