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

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:

CS (Carrier Sense): le stazioni della rete possono distinguere i canali liberi (idle) da quelli occupati (busy). Problema: stazione nascosta/esposta (che vedremo fra poco)
MA (Multiple Access): le stazioni della rete si scambiano frame attraverso canali condivisi
CD (Collision Detection): protocollo per la rilevazione delle collisioni. Problemi: per molti dispositivi la trasmissione è half-duplex, quindi se trasmettono non possono ricevere (dunque rilevare problemi); le collisioni avvenute nel ricevente potrebbero non essere rilevate dal mittente.

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:

quando la stazione A vuole trasmettere un frame a B gli invia prima una RTS
B gli risponde con una CTS
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:

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
A avvia la procedura di back-off (che vedremo poi)
A invia la RTS
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"
Quando B riceve l’RTS, risponde con un CTS
Ricevuto il CTS, A può cominciare a trasmettere il frame con i dati veri e propri
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
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:

tutte le stazioni che ricevono il frame RTS di una stazione A devono rimanere in silenzio per un tempo che consenta al frame CTS di arrivare ad A, dopodiché potranno ricominciare a trasmettere
tutte le stazioni che ricevono il solo frame CTS (quindi nella portata del ricevente B, ma non di A) devono rimanere in silenzio per il tempo necessario alla trasmissione del frame dati (la cui lunghezza è riportata nel CTS)
le stazioni che ricevono sia il frame RTS che quello CTS (situate nella portata di A e B) applicheranno entrambe le regole

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:

il ricevente invia un ACK se la ricezione del frame dati si è conclusa con successo
dopo la ricezione del CTS, il mittente invia un breve frame DS (Data Send) che contiene la dimensione del frame dati che verrà trasmesso. In questo modo le stazioni fuori dalla portata del mittente non gli manderanno RTS prima che abbia finito
se una stazione rileva un RTS ma non un CTS allora può trasmettere, se invece rileva solo un CTS allora aspetta finché non capta il segnale di ACK

Protocolli MAC

Nello standard 802.11 sono previste due modalità di funzionamento:

la DCF (Distributed Coordination Function) prevede che le stazioni gestiscano in modo distribuito l'accesso al mezzo, in particolare secondo il protocollo CSMA/CA. Facendo riferimento alle architetture wireless che abbiamo citato all'inizio, la DCF è tipica delle reti ad hoc
la PCF (Point Coordination Function) affida all’access point il compito di coordinare tutte le stazioni di cui è responsabile. L'AP interroga ciclicamente le altre stazioni, che possono trasmettere solo quando è il loro turno; dato che l’ordine delle trasmissioni è completamente controllato dalla stazione base, non possono verificarsi collisioni

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:

SIFS (Short InterFrame Space), il minimo intervallo di attesa possibile tra un frame e l'altro della stessa trasmissione, ad esempio tra un frame dati e il segnale di ACK. Notare che solo una stazione è abilitata a rispondere dopo un intervallo SIFS, così che le altre (che devono attendere un periodo più lungo) non possano interrompere la trasmissione in corso
PIFS (PCF InterFrame Space), il minimo intervallo di tempo tra un frame e l'altro in modalità PCF, quindi non a contesa. Deve essere maggiore del SIFS (perché comprende alcune operazioni del Point Coordinator), ma minore del DIFS
DIFS (DCF InterFrame Space), il minimo intervallo di tempo tra un frame e l'altro in modalità DCF, quindi a contesa. E' il più lungo di tutti gli InterFrame Spaces, e più il suo valore è alto e più il traffico è a bassa priorità. Viceversa, più il DIFS è breve e più la priorità aumenta; ciò significa che appena c'è silenzio mi inserisco, a rischio di collisioni.
Trascorso il DIFS, ogni stazione può tentare di acquisire il canale per iniziare una nuova trasmissione; è a questo punto che possono verificarsi le collisioni per accesso contemporaneo, ed infatti la finestra di contesa (slotted back-off window, che vedremo nel prossimo paragrafo) comincia proprio dopo questo intervallo
EIFS (Extended InterFrame Space), usato al posto di DIFS quando ci sono stati degli errori nella trasmissione, sufficientemente lungo da consentire al ricevente di rispondere al frame errato e risincronizzarsi col mittente

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:

prima della prima trasmissione se la stazione rileva che il mezzo è occupato
dopo ciascuna ritrasmissione, per cui è previsto un raddoppio del numero degli slot
dopo una trasmissione che ha avuto successo, per cui è previsto l'azzeramento del numero degli slot

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:

A e B hanno una CW di [0..31]
collidono, quindi la loro CW raddoppia a [0..63]
lo slot casuale scelto da A a 4, mentre quello scelto da B è 60
A aspetta 4, riesce a inviare il suo frame e quindi la sua CW torna ad essere [0..31]
potenzialmente A potrebbe mandare molti altri frame prima che arrivi il turno di B (che magari quando arriva il suo momento collide ancora e tanti saluti)

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