CAPITOLO 1
Introduzione al problema
1.1 Unfairness nelle Wireless LAN
In ambiente wireline esistono varie tecniche per raggiungere determinati requisiti di fairness. Algoritmi come l’HTB (Hierarchical Token Bucket) e CBQ (Class Based Queuing) riescono a suddividere il traffico in classi e far si che ciascuna classe non ecceda nell’utilizzo delle risorse del canale. In ambiente wireless la ripartizione delle risorse del canale non è ancora così efficiente in quanto, a causa di problematiche specifiche dell’ambiente wireless, gli algoritmi sviluppati per reti cablate non sono in questo caso applicabili. I principali problemi di una rete wireless sono causati dalle variazioni della qualità (e quindi capacità) del canale radio. Inoltre le stazioni mobili possono trovarsi in posizioni differenti rispetto all’Access Point e quindi rilevare qualità del canale diverse tra loro. Le garanzie che si potevano ottenere in ambiente wireline
del canale radio. Sperimentalmente si trova che, anche applicando un algoritmo che in ambiente wireline offre garanzie di fairness, quando si lavora in ambiente wireless, e una stazione si va a trovare in diverse condizioni di canale, la ripartizione del throughput non è più quella desiderata. Si verifica infatti un effetto spiacevole, noto come “anomalia” delle reti 802.11b, che rende impossibile garantire un throughput fissato anche a stazioni che si trovano in condizioni di canale buono. In pratica quando due stazioni in posizione buona stanno utilizzando il canale e una di queste si allontana, finendo col trovasi in una condizione di canale peggiore, oltre a diminuire il proprio throughput, anche quello della stazione in posizione buona si diminuisce di circa la stessa quantità.
Per chiarire meglio come si manifesta il problema appena descritto è stata effettuata una prova sperimentale in laboratorio utilizzando un computer impostato come sorgente di traffico UDP verso due stazioni mobili. La connessione wireless è stata realizzata tramite un Access Point della Lucent Technologies. Sono stati disattivati tutti i meccanismi di scheduling in modo che i pacchetti venissero accodati in modalità FIFO (First In First Out). Durante la prova una delle due stazioni mobili configurate come ricevitori è stata allontanata e poi avvicinata di nuovo dall’Access Point. Alla fine della prova è stato graficato il goodput misurato alle due stazioni insieme al rapporto segnale rumore. Il risultato è mostrato in figura 1.1. Inizialmente le due stazioni sono entrambe in posizione buona ottengono ciascuna il 50% del goodput totale. Si può notare che all’allontanamento della stazione Russel sia il goodput associato alla stazione che si è allontanata, sia quello della stazione Escher rimasta in posizione fissa calano fino a raggiungere zero. La differenza di SNR in posizione buona è dovuto al fatto che le due stazioni
0 1e+06 2e+06 3e+06 4e+06 0 10 20 30 40 50 60 70 80 90 0 10 20 30 40 50 60 70 80 90 Rate (bit/sec) SNR (dB) Tempo (s) Russel Escher Russel - SNR Escher - SNR
Figura 1.1 – Anomalia della 802.11b: prova con due stazioni con flussi UDP accodamento FIFO
1.2 Lo scheduler channel-aware
Il problema appena descritto sta nell’algoritmo di scheduling utilizzato che non è channel-aware. Presenteremo un algoritmo di scheduling, realizzato a livello LLC, che riesce a risolvere il problema in questione, permettendo alle stazioni in posizione buona di ricevere la parte di throughput che gli spetta. Lo scenario di riferimento che abbiamo utilizzato in questo lavoro è costituito da una stazione fissa, utilizzata come sorgente dei dati, e due o più stazioni mobili riceventi. I flussi utilizzati sono flussi UDP in
downlink verso le stazioni, l’architettura che analizzeremo è così
rappresentata in figura 1.2.
Tutti gli scheduling in ambiente wireline falliscono in ambiente wireless in quanto considerano che due stazioni, alle quali viene trasmessa la stessa quantità di dati, occupino la stessa porzione di risorse del canale. Questa ipotesi viene meno in ambiente wireless in quanto una stazione in posizione cattiva richiederà molto più tempo per trasmettere la stessa quantità di dati che non una in posizione buona. La soluzione al problema sta proprio nel osservare il tempo impiegato nella trasmissione, infatti due stazioni utilizzano le stessa porzione di risorse del canale se occupano quest’ultimo nella stessa quantità. É infatti impensabile che una stazione richieda garanzie su 1Mbps di throughput se questa si trova in una posizione dove 1Mbps corrisponde alla capacità massima trasmissiva, in quanto occuperebbe il 100% del canale, e le altre stazioni, pur in posizione buona, non potrebbero essere servite correttamente.
L’obbiettivo che ci poniamo è realizzare un algoritmo di scheduling che sia channel-aware e quindi che reagisca il più rapidamente possibile alle variazioni del canale in modo da adattarsi all’ambiente wireless. Per raggiungere questo obbiettivo bisogna tenere conto che, oltre a realizzare un algoritmo che sfrutti informazioni legate allo stato del canale in un determinato istante, riesca ad agire sull’invio dei pacchetti nel più breve tempo possibile. Sfortunatamente l’hardware non ci viene in aiuto, infatti, all’interno della scheda di rete utilizzata, è presente un buffer che effettua un accodamento delle trame, in arrivo dal sistema operativo, prima della loro trasmissione. Questo accodamento, mostrato in figura 1.3, è di tipo FIFO (First In First Out) e quindi, non solo non è channel-aware, ma non fornisce nessuna caratteristica di Qualità del Servizio.
STA 1
Access Point
STA 2 Flussi
UDP
operativo ci troviamo in una situazione dove la decisione su quale deve essere la prossima trama da trasmettere si rifletterà sul canale dopo aver passato il ritardo introdotto dal buffer. Detto questo l’architettura che andremo a realizzare dovrà cercare di scavalcare il buffer hardware in modo che quest’ultimo non influenzi il normale funzionamento dello scheduler.
Oltre ad ottenere uno scheduler channel-aware vogliamo soddisfare requisiti di fairness e quindi ripartire equamente le risorse del canale. Dobbiamo a questo punto definire cosa si intende per risorse del canale. Le risorse del canale coincidono, in effetti, con il tempo utilizzato per la trasmissione. Se una stazione impiega più tempo vuol dire che questa utilizza più risorse trasmissive, sottraendole alle altre stazioni. Il nostro scheduler sarà quindi basato sui tempi. Se riuscissimo a conoscere il tempo impiegato da una stazione e informare la disciplina di scheduling indicando quale stazione ha trasmesso e per quanto tempo, sarebbe possibile effettuare la decisione sulla trama successiva da trasmettere sfruttando questa informazione che dipende, oltre che dalla lunghezza della trama in termini di byte trasmessi, anche dal numero di ritrasmissioni e dal tipo di modulazione utilizzata sul canale, nelle condizioni attuali. Un meccanismo di questo tipo sarebbe un meccanismo effettivamente channel-aware e time-based.
Hardware Scheda WLAN Scheduler
(Sistema Operativo)
buffer FIFO
É proprio su questo obbiettivo che ha stata pensata l’architettura dello scheduler proposto. Lo scheduler è scomponibile in due moduli che scambiano informazioni tra loro come indicato in figura 1.4. Un modulo consiste in una disciplina di scheduling inserita all’interno del Linux Traffic Control che effettua l’accodamento dei pacchetti destinati alle varie stazioni e prende le decisioni su quale deve essere
Traffic Control Driver Hostap Hardware Livelli superiori (IP) Trama Dati Trama Dati Trama Dati Trasmissione Eventi Tx/TxExc Tempi di utilizzo Stato Buffer Hardware Disciplina di scheduling
Monitor Eventi
all’interno del driver della scheda di rete (driver HostAP) che controlla le trasmissioni e il buffer hardware gestendo gli eventi scatenati dalla scheda di rete. Lo scheduler prende i pacchetti provenienti da stazioni diverse e li accoda in code separate. Ad ogni stazione vengono associate, oltre alla coda dove memorizzare i pacchetti in uscita, una serie di informazioni che indicano se la coda è vuota o piena e per quanto tempo la stazione ha utilizzato il canale per la trasmissione. In base ai tempi di utilizzo del canale viene deciso da quale coda estrarre il pacchetto per la trasmissione. Lo scheduler realizzato è quindi uno scheduler time-based e channel-aware e le ripartizioni di throughput non sono più ottenute come ripartizioni sul rate, che perde di significato, ma su ripartizioni sul tempo.
