Un meccanismo di comunicazione a priorità per reti …Le reti locali wireless, o LAN wireless,...

I

Facoltà di Ingegneria Corso di Studi in Ingegneria Informatica tesi di laurea

Un meccanismo di comunicazione a priorità per reti wireless Anno Accademico 2004 - 2005 relatore Ch.mo prof. Giorgio Ventre correlatore Ing. Massimo Ficco candidato Gianfranco Fattore matr. 41/3811

II

“Questa montagna è tale, che sempre a cominciar di sotto è grave e quant’uom più va sù e men fa male” Dante Alighieri – Purgatorio IV,88-90.

Sono passate parecchie stagioni da quell’autunno in cui, nella famigerata aula T1

del “biennio di ingegneria, uno spazio vettoriale si alternava ad uno studio di

funzioni. C’era molta ingenuità, nessuno sapeva quello che ci sarebbe aspettato e

ci piaceva carpire le mille legende universitarie che prontamente qualche studente

raccontava durante le pause tra le lezioni. Immaginate un ragazzo appena

maggiorenne, vissuto in un piccolo paesino sotto l’appennino che si trova

catapultato in una grande città e soprattutto nell’ambiente universitario che,

rispetto a quello del liceo di un paesino di montagna, sembrava un gigante. Per

fortuna ho avuto dei compagni di viaggio eccezionali con cui ho condiviso momenti

di vita cittadina e universitaria ricchi di episodi belli e di difficoltà. Per questo mi

piace ricordare Gianluca, Vittore, Carlo e Mauro, “la voce fuori del coro”, come

degli amici fidati che difficilmente potranno cadere nel dimenticatoio, come spesso

si fa con superficialità verso molte persone. Come non ricordare poi gli amici dei

primi anni di studio: Maria e Luigi con i quali ho iniziato ad effettuare la dura

scalata e gli amici che mi hanno accompagnato verso la fine degli studi: Loreto e

Gino che insieme a Vittore, come ad un Giro d’Italia, ci alternavamo alla testa del

gruppo per raggiungere la fatidica “cima Coppi” della laurea. Ovviamente tutto ciò

è stato possibile grazie al supporto morale, alla perseverante pazienza e non solo

(ci vorrebbe un’altra tesi per chiarire bene il concetto) dei miei genitori e di mio

nonno, che come un’ orologio svizzero, mi ha sempre scandito i tempi. Come

posso non ricordare inoltre i miei amici del paese che mi hanno permesso di

evadere dal mio mondo di numeri e bit (e come direbbe Gino di compilazioni del

kernel) e i miei parenti più stretti che mi hanno espresso la loro solidarietà nei

momenti difficili. Al termine di questa dissertazione, forse scontata ma dovuta,

voglio ricordare con un pizzico di malinconia una persona che, come o forse più

dei miei genitori, ha creduto in me e nelle mie scelte e che purtroppo ora non c’è

più. Sicuramente sarebbe stato emozionato più lui che io nel vedermi a discutere

questo lavoro di tesi. Hai visto zio? C’è l’ho fatta!!!!

Bene, ora è giunto il momento di proseguire perché come diceva sempre un mio

professore: ”gli ingegneri non si fermano mai!”

Un meccanismo di comunicazione a priorità per reti wireless

3

Indice

UN MECCANISMO DI COMUNICAZIONE A PRIORITÀ PER RETI WIRELESS ............. I

INDICE...............................................................................................................................................3

INTRODUZIONE..................................................................................................................................5

CAPITOLO 1 LA QUALITÀ DEL SERVIZIO NELLE RETI WIRELESS.........................................................7

1.1 La tecnologia Wireless...................................................................................................................8

1.1.1 Le WLAN......................................................................................................................8

1.1.2 Lo standard IEEE 802.11 ............................................................................................9

1.2 La Quality of Service....................................................................................................................12

1.2.1 La QoS nelle Wireless LAN........................................................................................12

1.2.2 Sintesi delle caretteristiche principali del futuro standard 802.11e ......................15

1.2.3 Wi-Fi Multimedia (WMM) ........................................................................................20

1.3 Il lavoro svolto .............................................................................................................................23

CAPITOLO 2 ACCESS POINT CON SUPPORTO ALLA QUALITÀ DEL SERVIZIO: HOSTAP E HOSTQS........24

2.1 Hostap ..........................................................................................................................................25

2.2 HostQs: Differenziazione del traffico in WLAN ..........................................................................27

2.2.1 Introduzione a HostQs................................................................................................27

2.2.2 QoS dell’IEEE 802.11e: la funzione EDCA ..............................................................29

2.2.3 Differenziazione del traffico a livello LLC ...............................................................30

2.2.4 L’ implementazione di HostQs...................................................................................34

2.2.5 Risultati del test...........................................................................................................36

CAPITOLO 3 L'ARCHITETTURA DI RIFERIMENTO..............................................................................43

3.1 Architettura del sistema ...............................................................................................................44

3.1.1 Scenario........................................................................................................................44

3.1.2 Architettura .................................................................................................................44


4

3.2 Principio di funzionamento..........................................................................................................49

3.3 Esempi di funzionamento.............................................................................................................54

CAPITOLO 4 IL MODULO HOSTQS .....................................................................................................57

4.1 Il kernel ed i moduli .....................................................................................................................58

4.1.1 Kernel space e User space .........................................................................................58

4.1.2 Gestione dei moduli.....................................................................................................60

4.1.3 Struttura dei moduli e loro scrittura ..............................................................................63

4.1.4 Il debugging del modulo ............................................................................................68

4.2 Il modulo queue_mgr.o ................................................................................................................70

4.2.1 Le strutture dati ..........................................................................................................70

4.2.2 Le funzioni del modulo ...............................................................................................75

4.2.3 Lo schema di funzionamento .....................................................................................76

CAPITOLO 5 LE MISURE SPERIMENTALI............................................................................................85

5.1 Il testbed.......................................................................................................................................86

5.2 Le misurazioni..............................................................................................................................88

5.2.1 Individuazione della cella minima .............................................................................88

5.2.2 Verifica del funzionamento del modulo Hostqs originale .......................................93

5.2.3 Verifica del funzionamento del modulo Hostqs modificato ....................................97

5.3 Conclusioni e sviluppo futuro ....................................................................................................101

APPENDICE A.................................................................................................................................102

A.1 L’header file queue_mgr.h .........................................................................................102

A.2 Il file queue_mgr.c.......................................................................................................104

A.3 Il Makefile ....................................................................................................................118

Appendice B: Installazione del software e configurazione del testbed............................................119

B.1 Installazione di HostAP e HostQs ..............................................................................119

B.2 Configurazione del testbed .........................................................................................120

BIBLIOGRAFIA...............................................................................................................................122


5

Introduzione

Il lavoro di tesi proposto si è occupato dello sviluppo di un modulo del kernel detto

“queue_mgr” del sistema operativo Linux atto a gestire un meccanismo di comunicazione a

priorità per reti wireless. Tale lavoro parte da un progetto esistente, denominato “hostqs”,

che si occupa di gestire la QoS in una rete wireless valutando il campo TOS di ogni

pacchetto IP ricevuto. Partendo dall'analisi degli standard esistenti e di quelli in via di

approvazione per introdurre una qualità del servizio su tali reti (802.11b, 802.11e), si passa

ad introdurre un'architettura di riferimento in cui tale modulo software lavora. Si tratta di

un nodo wireless in cui un server di autenticazione gestisce gli accessi degli utenti alla rete

in base a degli identificativi personali ed indipendentemente dal device wireless utilizzato.

L'utente fornirà al sistema il proprio identificativo l'indirizzo MAC del device utilizzato e il

sistema di autenticazione gli fornirà l'accesso alla rete e il tipo di QoS. Il modulo

“queue_mgr” in base al valore di QoS applicherà una politica di scheduling dei pacchetti

associandoli a code con tempi di trasmissione diversi. Per lo sviluppo del software è stato

utilizzato un driver per schede wireless con chipset PrismII, “Hostap”, che trasforma una

semplice scheda wireless in un Access Point.

Il modulo del driver contiene una funzione di trasmissione modificata che invia i pacchetti

di rete non direttamente allo strato MAC ma prima al modulo supplementare che si occupa

della schedulazione delle frame. Successivamente sono state effettuate delle misure su un

testbed allestito ad hoc per verificare effettivamente il funzionamento di tale sistema

software. Sono state effettuate misure sulla capacità di trasmissione della scheda wireless

utilizzata in modalità Hostap: misure di trasmissione (potenza trasmissiva, rapporto

segnale rumore, throughput effettivo), misure di trasmissione del modulo hostqs basato

sull'analisi del campo TOS del pacchetto IP (throughput, jitter) ed infine misure di

trasmissione del modulo queue_mgr sviluppato (throughput, jitter).


6

La tesi è strutturata come segue:

Capitolo 1: Si inquadra il problema della Quality of Service, in particolare su reti

wireless, mettendo in evidenza le differenze che si evincono dalle tecniche

di trasmissione dello standard IEEE 802.11b e della bozza di standard

802.11e. Si illustra a scopo conoscitivo anche l'implementazione da parte

della Wi-Fi Alliance di un programma per l'implementazione della QoS

chiamato WMM (Wi-Fi-certified for Wi-Fi Multimedia).

Capitolo 2: Viene presentata il software Hostap che trasforma una semplice scheda

wireless in un Access Point e il modulo Hostqs originale che basa la

politica di QoS sul particolare valore del campo ToS dell'header Ip di ogni

pacchetto ricevuto, spiegando a livello concettuale l'architettura del

modulo

Capitolo 3: In questo capitolo vengono illustrati i fondamentali aspetti dell'architettura

di riferimento in cui si cala il modulo Hostqs, descrivendo da un punto di

vista concettuale l'interazione tra i vari moduli.

Capitolo 4: In questo capitolo, dopo aver dato brevi cenni di programmazione di

sistema, in particolare di Kernel Module Programming, si riportano le

tappe principali dello sviluppo del modulo queue_mgr illustrando le

principali strutture dati e funzioni realizzate.

Capitolo 5: A conclusione del lavoro di tesi si riportano le principali misurazioni

effettuate atte a mostrare l'effettivo funzionamento del modulo oltre che ad

individuare la dimensione minima e massima di copertura di un nodo

wireless.

Appendici: si riportano i file sorgenti del modulo sviluppato e le configurazioni delle

macchine che fanno parte del testbed realizzato.


7

Capitolo 1 La qualità del servizio nelle reti Wireless

Le tecnologie per la comunicazione senza fili si stanno diffondendo rapidamente in tutto il

mondo. Esse sono utilizzate sia per realizzare reti locali (LAN) di computer mobili, sia per

la comunicazione tra dispositivi di uso comune come telefoni, macchine fotografiche, ecc.

Le reti locali senza fili sono dette Wireless Local Area Network (WLAN) e vengono

utilizzate per fornire connettivitá ad utenti mobili con prestazioni paragonabili alle

soluzioni broadband via cavo che si trovano sul mercato. Le principali tecnologie wireless

si basano sulle specifiche del protocollo IEEE 802.11. In questo capitolo si presenteranno

le tecnologie attuale e quelle in fase di sviluppo per la gestione della QoS nelle wireless

LAN


8

1.1 La tecnologia Wireless

1.1.1 Le WLAN

Le reti locali wireless, o LAN wireless, stanno modificando il mondo delle reti di computer.

Le aziende di tutto il mondo stanno implementando reti wireless indipendenti o in aggiunta

a quelle cablate per aumentare la produttività dei dipendenti, ridurre i costi e superare gli

ostacoli delle connessioni tradizionali. Giunte sul mercato nei primissimi anni novanta,

esse hanno avuto la definitiva svolta con l'approvazione dello standard IEEE 802.11 (1997)

evolutosi in seguito negli standard 811.2a, 811.2b, 802.11g e altre evoluzioni atte a

migliorare la capacità trasmissiva piuttosto che la qualità dei servizi offerti. Gli standard

802.11b e 802.11g definiscono oggi gli standard effettivamente utilizzati per il WLAN

anche se si lavora ancora al fine di ottenere un miglioramento ed un adattamento degli

stessi alle esigenze quotidiane. Tra i vantaggi che rendono così appetibile questa tecnologia

c'è indubbiamente la flessibilità. Infatti si ha un'enorme aumento d'efficienza rispetto ad

una rete cablata. Si scavalcano in questo modo tutti quei problemi riscontrati nella stesura

della stessa. Si pensi ad esempio la realizzazione di una LAN che colleghi due edifici

separati da grossi ostacoli o la stesura della stessa all'interno di una struttura storica. Non ci

sarebbe più bisogno di stendere cavi antiestetici. Si ha inoltre la possibilità di rendere

mobile l'utente collegato. Pertanto se si parla di computer portatili le potenzialità

aumentano. Si immagini l'uso che se ne potrebbe fare all'interno di una struttura sanitaria

quale un ospedale oppure all'interno di un aeroporto, un magazzino. A tutto questo si

aggiungano che i costi di realizzazione sono relativamente bassi. Ovviamente c'è il

rovescio della medaglia e quindi gli svantaggi. Essendo una trasmissione radio fatta ad alta

frequenza, ne presenta tutte le pecche. C'è da considerare fenomeni di attenuazione,


9

interferenza, riflessioni, e sicurezza. A ciò va aggiunto problemi energetici legati al fatto

che spesso vengono usati dispositivi a batteria e compatibilità. Per i primi tre, i problemi

sono identici a quelli riscontrati in una qualsiasi altra trasmissione radio. Ipotizzando un

trasmettitore isotopico (che trasmette nello stesso modo in tutte le direzioni) si ha che il

segnale si propaga e la potenza si spalma istante per istante su sfere concentriche. Questo

porta ad un'attenuazione che è inversamente proporzionale alla distanza percorsa dal

segnale. Quindi se si trasmette ad una potenza bassa, non arriva nulla. Se si trasmette ad

una potenza superiore al necessario, si inficia sulla durata della batteria. Ancora, il segnale

in presenza di ostacoli rimbalza e genera un'onda riflessa. Questa giunge sul ricevitore

contemporaneamente al segnale diretto ed a un'infinità di segnali riflessi (fenomeno delle

riflessioni multiple), specie negli ambienti chiusi. Il risultato è una distorsione del segnale

e nella peggiore delle situazioni, il fenomeno dell'affievolimento profondo. Poi c'è

l'interferenza verso altri dispositivi e la suscettanza nei confronti di disturbi radio. Parlando

invece di compatibilità, il problema nasce dalla presenza di diversi standard. E' ovviamente

preferibile l'uso di access point e schede identiche per poter sfruttare al massimo la rete.

Infine, ma non per ultimo per importanza, il problema della sicurezza. L'informazione

trasmessa diviene alla portata di tutti, pertanto occorre effettuare un criptaggio del

segnale.[1]

1.1.2 Lo standard IEEE 802.11

Il gruppo IEEE 802 [2] può essere visto come una famiglia di standard comprendenti

un'insieme di standard quali:

• 802.2: Logical Link Control

• 802.3: Carrier Sense Multiple Access with Collision Avoidance

• 802.4: Token bus

• 802.5: Token Ring

• 802.6: Distributed Queuing Dual Bus (DQDB)

• 802.9: Unified Integrated Services su Backbone

• 802.11: WLAN

• 802.12: Demand Priority Access Method

• 802.14: Cable TV


10

• 802.15: Wireless Personal Area Networks

• 802.16: Broadband Wireless Access Methods

che riguardano il livello MAC e il livello fisico della pila ISO-OSI.

Figura 0-1.1 La pila ISO-OSI

Lo standard 802.11 si riferisce alle reti wireless. Nello standard originale si focalizza

l'attenzione su tre distinti livelli fisici (infrarosso - trasmissione radio con modulazione

FHSS - Trasmissione radio con modulazione DSSS) e il livello MAC. In seguito si sono

avute due estensioni quali 802.11a e 802.11b. La versione base propone l'uso della banda

di frequenze dei 2.4GHz, la cosiddetta ISM (Industrial, Scientific and Medical band) che è

disponibile a libero uso dei privati, senza la necessità di ottenere concessioni da parte degli

enti pubblici. Nella prima estensione, l’IEEE 802.11a, si ottiene un throughput massimo di

54 Mbps ad una frequenza di lavoro di 5,2 GHz. A causa dell'elevata frequenza usata,

vengono richiesti un maggior numero di AP rispetto allo standard 802.11b. Questo non è

autorizzato in Europa ed è il diretto concorrente dello standard Europeo Hyperlan/2. I

prodotti sono marcati con la sigla "Wi-Fi5". Un problema riscontrato è il seguente: la

frequenza utilizzata è la stessa con cui operano i satelliti, perciò l'utilizzo è permesso

soltanto per gli ambienti chiusi. In questo standard viene utilizzata la tecnologia di

modulazione OFDM con tecniche di modulazione BPSK/QPSK/16 QAM/64 QAM, 8

canali disponibili non overlapping. Nella seconda estensione, la 802.11b, abbiamo invece

un throughput massimo di 11 Mbps, 100 metri di distanza , con tecniche di modulazione

quali:


11

• DBPSK (Differential Binary Phase Shift Keying) per velocità da 1 Mbps

• DQPSK (Differential Quaternary Phase Shift Keying) per velocità da 2 Mbps

• QPSK/CCK (Quaternary Phase Shift Keying with Complementary Code Keying)

per velocità comprese tra 5,5 e 11 Mbps.

Attualmente lo standard 802.11 è in continua evoluzione, grazie alle estensioni che i vari

gruppi di lavoro stanno studiando e proponendo. Una evoluzione dello standard 802.11b è

l'802.11g che presenta un throughput di 54 Mbps ad una frequenza di 2.4 GHz. La tecnica

di modulazione usata è la OFDM (tre canali disponibili non overlapping). Si riporta di

seguito un elenco dei vari gruppi di lavoro dell'IEEE 802.11 per capire in quali campi di

ricerca essi lavorano. [3]

Gruppo di lavoro

Scopo del progetto

802.11a Sviluppare un livello fisico per trasmettere nella banda dei 5GHz.

802.11b Definire uno standard per trasmettere ad un bit rate più alto nella banda dei 2.4GHz.

802.11c Migliorare alcune mancanze nel Management Information Base nello standard 802.11b

802.11d Perfezionare l’interoperabilità tra lo standard IEEE 802.11 e lo standard IEEE 802.1d

802.11e Migliorare il livello MAC dello standard IEEE 802.11 per supportare la Quality of Service (QoS )

802.11f Migliorare l’interoperabilità tra AP di diversi costruttori in un DistributedSystem, standardizzando un protocollo di roaming.

802.11g Aumentare il bit rate in trasmissione delle reti di tipo 802.11b superando i 20Mbps.

802.11h Migliorare il livello MAC e fisico dello standard IEEE 802.11°.

802.11i Migliorare i meccanismi di autenticazione e sicurezza. 802.11j Aumentare il numero di canali nella banda dei 5GHz in

Giappone. 802.11k Definire un Radio Resource Measurement per scambiare

informazioni con i livelli superiori riguardo alle misurazioni sul segnale radio.


12

1.2 La Quality of Service

1.2.1 La QoS nelle Wireless LAN

Gli standard presentati in precedenza, sono stati pensati per un traffico di tipo generico

detto best-effort. Con tale termine individuiamo una certa tipologia di traffico

caratterizzata dal non presentare particolari esigenze in termini di risorse assegnategli.

Esempi di traffico identificabili in tale categoria sono i traffici di trasferimento file (FTP,

File Transfer Protocol), quelli per lo scambio di posta elettronica (SMTP, Simple Mail

Transfer Protocol, POP3, Post Office Protocol), o per la consultazione di pagine web

(HTTP, Hyper Text Transfer Protocol). E' anche vero però che negli ultimi anni si presenta

sempre più l'esigenza di far uso di particolari tipi di traffici che presentano esigenze

nettamente diverse. Sto parlando di traffici di informazioni di tipo audio o video,

interattive o non.

Questo comporta il soddisfacimento da parte della rete, di particolari specifiche in termini

di prestazioni, al fine di garantire la qualità dell'informazione trasmessa. Si introduce

quindi il concetto di QoS (Quality of Service) definito come proprietà della rete di

garantire una certa qualità nel servizio offerto. Il gruppo IEEE 802.11 ha costituito pertanto

un gruppo di lavoro il cui scopo sia la realizzazione di uno standard che garantisca il

soddisfacimento di questa specifica.

Tale gruppo e il 802.11e. Allo stato dell'arte non è ancora stato definisto uno standard, ma

sono stati proposti diversi Draft. Con traffico multimediale si identifica solitamente un tipo

di trasmissione che presenti informazioni di tipo audio o video al proprio interno. Allo

stato attuale, si ha che le applicazioni più diffuse sono: audio streaming, video streaming,

video conference e VoIP (Voice over IP). Queste quattro applicazioni prevedono la

trasmissione di tipo interactive detto anche two-way (VoIP e video conference) nelle quali

in traffico è bidirezionale,


13

Figura 1.2 Traffico two-way

o di tipo non-interactive detto anche one way (streaming audio e video) nelle quali

abbiamo invece un traffico di tipo unidirezionale.

Figura 1.3 Traffico unidirezionale

Appare evidente come queste applicazioni richiedano particolari specifiche alla rete al fine

di garantire una ricezione accettabile verso l'utente destinatario. Le specifiche di cui

occorre tener conto sono sostanzialmente quattro:

• Banda allocata - Occorre fare una differenziazione in termini di traffico trasmesso.

Infatti passiamo da un banda di pochi Kbit/sec per il VoIP fino a Mbit/sec nel caso

di streaming video. Non può pertanto essere pensato una gestione paritaria delle

risorse disponibili pena uno spreco delle stesse.

• Delay - Esso sostanzialmente è il tempo che trascorra tra l'istante in cui il pacchetto


14

è generato all'istante in cui esso è ricevuto dal destinatario. Appare evidente come

ad esso concorrano una serie di fattori quali il ritardo di elaborazione (piccolissimo

ma comunque non nullo), il ritardo di accodamento (i pacchetti vengono conservati

in una coda in attesa di esser trasmessi, usualmente serviti secondo una politica

FIFO - First In First Out), il ritardo di trasmissione (dipendente direttamente dalla

velocità di trasmissione), ed il ritardo di propagazione fisica del segnale trasmesso

(anch'esso piccolissimo). Diventa un fattore a cui occorre fornire una particolare

attenzione nel caso di traffico interattivo pena il rischio di rendere la conversazione

incomprensibile.

• Jitter - Questa quantità esprime la varianza del ritardo di cui prima. Un jitter nullo

è sinonimo di un ugual ritardo da parte dei pacchetti. Jitter elevati significa un

traffico poco fluido.

• Packet loss - Da informazioni circa la quantità di pacchetti persi (oppure corrotti)

durante la trasmissione. I traffici multimediali presentano specifiche abbastanza

stringenti verso questo indice.

Si riporta di seguito una tabella in cui si definiscono, degli indici appena elencati, i valori massimi tollerati in funzione dell'applicazione. [3]

Applicazione Traffico Data-rate [Kbit/sec]

Delay [ms]

Jitter [ms]

Packet-loss [%]

VoIP Two-way

4-64 150 1 3

Streaming Audio

One-way

16-128 10 sec 1 1

Streaming Video

One-way

16-384 10 sec 1

Video Conference

Two-way

16-384 150 1


15

1.2.2 Sintesi delle caretteristiche principali del futuro standard 802.11e Il gruppo di lavoro 802.11e, istituito per apportare modifiche allo standard originale al fine

di garantire il QoS verso tali applicazioni, ha proposto due nuove modalità di trasmissione

che possono essere viste come un'evoluzione delle modalità di trasmissione dell'802.11b.

Per poter comprendere la principale novità introdotta dallo standard 802.11e, l’Enhanced

Distributed Coordination Function (EDCF), occorre richiamare brevemente la Distributed

Coordination Function (DCF) così come viene descritta nello standard 802.11 di base.

[4][5].

Il DCF adotta uno schema listen-before-talk basato sui meccanismi di Carrier Sense

Multiple Access (CSMA) e di Collision Avoidance (CA). In particolare la CSMA consiste

nella verifica da parte di ciascuna stazione della presenza di segnale sulla rete per

assicurarsi che il canale sia libero, dopo di che viene inviato un MAC Service Data Units

(MSDUs).

Con il solo CSMA è però possibile che due stazioni trovino contemporaneamente libero il

canale dando luogo ad una collisione. Per tale ragione la CA prevede una procedura di

backoff preliminare:

ogni stazione che deve effettuare una trasmissione attende per un tempo casuale di durata

minima pari al DCF InterFrame Space (DIFS), che è di 34 us nel 802.11a. Il tempo di

attesa ulteriore deve essere multiplo dello slot-time (9 us nel 802.11a). Ogni stazione

memorizza la propria Contention Window (CW) che mantiene il numero di slot che deve

attendere prima di riprendere a trasmettere. Per segnalare una trasmissione corretta il

ricevitore invia un acknowledgement (ACK). Se la trasmissione fallisce il CW viene

Figura 1.4 Procedura di backoff


16

raddoppiato riducendo così la probabilità di una collisione. Per ridurre l’overhead dovuto

per esempio alla frammentazione di pacchetti di strati superiori e che vengono trasmessi in

sequenza, l’802.11 definisce un meccanismo opzionale di Request-to-Send/Clear-to-Send

(RTS/CTS). In sostanza prima il trasmettitore invia un frame RTS seguito da un CTS

ricevitore. RTS e CTS contengono le informazioni su quanto tempo intercorrerà fra

l’attuale frame di dati (ossia MSDU) e quello successivo. Ciascuna stazione mantiene un

timer, il Network Allocation Vector (NAV), che contiene le informazioni trasmesse dai

frame RTS e CTS. Tra ciascun messaggio scambiato da trasmettitore e ricevitore è previsto

un periodo idle detto Short InterFrame Space (SIFS) fissato a 16 us dal 802.11a. [4]

Lo standard 802.11 di base definisce già una funzionalità per supportare servizi con

scadenze temporali: si tratta della Point Coordination Function (PCF), che consente di

fissare priorità di accesso diverse per le stazioni della rete grazie al coordinamento

garantito da una stazione detta Point Coordinator (PC), tipicamente coincidente con

l’Access Point (AP). Il PCF ha maggiore priorità della funzione DCF esaminato nel

precedente paragrafo e tale priorità è garantita dal fatto che il tempo minimo di attesa del

PCF, detto PCF InterFrame Space (PIFS), è minore del DIFS essendo di soli 25 us

(802.11a); si badi che il PIFS è comunque maggiore del SIFS. Il PCF prevede una

suddivisione del tempo in superframe, che a sua volta è costituito da un Contention Free

Period (CFP) e da Contention Period (CP). Durante il CFP è attivo il PCF, mentre nel CP è

consentito il normale svolgimento del DCF. Il superframe ha inizio con il cosiddetto

beacon frame e contiene le informazioni necessarie per sincronizzare i timer locali delle

stazioni. Il tempo intercorrente fra due beacon frame è in genere regolare e pertanto ogni

stazione è in grado di prevedere l’istante in cui arriverà il prossimo beacon frame detto

target beacon transition time (TBTT). Durante il CFP non ci sono contese per l’accesso

poiché ogni operazione è regolata dal PC effettuando polling su ciascuna stazione. Poiché

anche il PC può inviare dati alle stazioni, il messaggio di polling (CF-Poll) può essere

combinato con il data frame da trasmettere. Similmente la stazione segnalata risponde con

un aknowledgement CF-ACK che può essere combinato con un data frame. Ogni CFP

termina con un CF-End. Durante il CFP ogni stazione, prima di inviare un frame, attende

un tempo pari al SIFS.

Il PCF ha come scopo principale supportare servizi che pongono dei limiti al ritardo

nell’inoltro del frame. Tale obiettivo è stato raggiunto solo parzialmente. Si riportano nel

seguito alcuni dei problemi non risolti.

• Nella precedente discussione si è supposto di poter conoscere con certezza il


17

TBTT, ma il beacon potrebbe essere soggetto ad un ritardo essendo sconosciuta la

durata delle operazioni di polling. Il beacon potrebbe essere quindi trasmesso dopo

il TBTT consentendo alle stazioni che avrebbero dovuto trasmettere entro il TBTT

di superare il bound. Alcune simulazioni di caso peggiore mettono in evidenza la

possibilità di ritardi pari anche a 250 us.

• Se è vero che il polling fornisce garanzie sull’ordine con cui i frame sono trasmessi,

nulla si può dire in merito ai tempi della trasmissione in polling. C’è infatti solo un

limite di 2304 sulle dimensioni del frame, che può raggiungere i 2312 se criptato,

ma il dato può essere frammentato in più frame.

• È possibile che una stazione perda il precedente beacon e quindi non sia in grado di

impostare il TBTT ed anzi non sia neppure al corrente dell’inizio di un CFP. Tale

stazione non sospenderà quindi le operazioni di DFC.

Lo scopo dello standard IEEE 802.11e è sopperire i limiti riscontrati in precedenza per

supportare la QoS. Esso introduce due nuove funzionalità: la Enhanced Distributed

Coordination Function (ECDF) e la Hybrid Coordination Function (HCF). Le stazioni che

supportano 802.11e sono dette enhanced ed appartengono allo stesso QoS-supporting

Basic Service Set (QBSS). Tra queste è possibile prevedere una stazione (tipicamente è

l’AP) che operi come controllore centralizzato e che viene definita Hybrid Coordinator

(HC). Anche nell’802.11e i superframes sono suddivisi in CP e CFP. L’ECDF è attivo

soltanto durante il CP, mentre HCF opera in entrambe le fasi.

Il supporto per la QoS è realizzato introducendo delle classi di servizio, che nello standard

sono denominate Traffic Categories (TCs). La differenziazione del livello di servizio degli

MSDU appartenenti alle diverse TC è implementata attraverso una diversa

parametrizzazione.

In particolare durante il CP ciascuna stazione, dopo aver appurato che il canale è libero,

contende con le altre stazioni la Transmission Opportunity (TXOP) attendendo per un

intervallo di tempo detto Arbitration InterFrame Space (AIFS).

L’AIFS ha durata minima pari al DIFS e può essere aumentato sulla base della TC di

appartenenza. Dopo aver atteso l’AIFS ha inizio il backoff di durata casuale compresa fra

[1, CW+1]; un altro dei parametri dipedenti dalla TC è la durata minima del CW, la

CWmin[TC]. Nel caso in cui il canale risulti occupato il CDF prevede che il CW venga

raddoppiato. L’ECDF invece ricalcola il CW utilizzando il Persistent Factor PF[TC],

dipendente anch’esso dalla TC, secondo la relazione seguente. newCW[TC] >=

((oldCW[TC] + 1) * PF[TC]) + 1 Ponendo PF = 2 si ottiene la stessa relazione prevista dal


18

CDF. Ad ogni modo viene fissato un valore massimo CWmax[TC] per il CW dipendente

dalla TC. Sintetizzando quindi è possibile definire la priorità degli MSDU operando sui

seguenti parametri: AIFS[TC], CWmin[TC], PF[TC] e CWmax[TC] (opzionale).

Un aspetto innovativo dell’ECDF consiste nella possibilità di gestire all’interno di ogni

stazione fino ad 8 code virtuali corrispondenti a diverse TC.

Tale stazione deve quindi implementare una funzionalità di scheduling interna e deve

essere in grado di evitare collisioni virtuali. [6]

Figura 1.5 Categorie di accesso della EDCF

Una caratteristica importante del MAC di IEEE 802.11e è la TXOP, definita come

l’intervallo di tempo in cui una stazione ha il diritto di iniziare la trasmissione. Essa può

essere allocata in due modi: tramite competizione (EDCF-TXOP), come illustrato in

precedenza, o tramite HCF (polled-TXOP).

Figura 1.6 Funzionamento del Contention Free Burst (CFB)


19

La durata di un EDCF-TXOP èlimitata dalla massima TXOP che si può assicurare

ponendo dei limiti sulla TXOP che vengono comunicati dalla stazione che ha assunto il

controllo

della stazione. Una novità molto importante dell’EDCF rispetto al semplice DCF è la

possibilità di introdurre un meccanismo di Contetion Free Burst (CFB) simile a quello

assicurato dal PCF visto in precedenza ma ottenuto in modo distribuito.

Una stazione può infatti entro il limite sulla TXOP può trasmettere anche più di un

pacchetto senza subire contention da parte delle altre stazioni. Questo diventa possibile

poiché il tempo di attesa fra una trasmissione ed un’altra è pari al SIFS e non all’AIFS.

L’assenza di contesa dovrebbe permettere di migliorare le prestazioni complessive della

rete diminuendo le collisioni e tutto senza coordinazione centralizzata. Invece la durata di

un polled-TXOP può essere assicurata invece da un HC una volta che è stata dichiarata nel

poll frame.

HCF estende le regole di accesso di EDCF consentendo al Hibrid Coordinator (HC) di

allocareTXOP. In modo simile al Point Coordinator (PC) del PCF, HC si assicura il canale

attendendo per un tempo compreso tra PIFS e DIFS e dunque inferiore al tempo di attesa

degli altri frame che è comunque maggiore di DIFS. Durante il CP, essendo attive sia

EDCF sia HCF, il TXOP può essere assicurato ad una stazione o dopo una attesa pari ad

AIFS + backoff o tramite un poll frame speciale, il QoS CF-Poll, inviato dal HC dopo una

attesa di PIFS senza backoff. Durante il CFP l’unico modo per assicurate il TXOP è

tramite QoS CF-Poll. Infatti le stazioni non provano ad accedere al canale per tutto il CFP

e pertanto l’unica stazione che ne fa uso è HC. La fine di CFP è definita da un messaggio

di CF-End inviato da HC o tramite le informazioni fissate nel beacon frame. [6]


20

1.2.3 Wi-Fi Multimedia (WMM) Le funzioni realizzate dalla Quality of Service (QoS) stanno affermandosi come un

requisito chiave nelle reti Wi-Fi per supportare le applicazioni multimediali ed una

gestione avanzata del traffico in ogni segmento di mercato: residenziale, enterprise e di

pubblico accesso.

Le tradizionali reti Wi-Fi forniscono uguale possibilità di accesso al mezzo di trasporto

fisico per tutti i dispositivi connessi. Quando il traffico presente supera la banda

disponibile, il troughput per tutti i flussi viene così ridotto, senza tenere in considerazione i

tipi di dato che stanno viaggiando in rete.

Tuttavia, mentre un ritardo di un secondo nell'inviare un job da un computer verso una

stampante non viene percepito dall'utente, una latenza anche inferiore può disturbare

seriamente una chiamata di tipo VoIP o la visione di uno streaming video.

Quindi un accesso senza priorità, di tipo best effort, si coniuga bene con applicazioni di

tipo posta elettronica, FTP, accesso ad Internet, ma non è sicuramente adatto per effettuare

ad esempio streaming di musica o video, traffico vocale o giochi interattivi: tali

applicazioni hanno degli stretti requisiti riguardo al troughput e ai tempi di latenza. Per

questo il traffico proveniente da diverse applicazioni deve essere gestito attraverso

meccanismi di tipo QoS.

La Wi-Fi Alliance per questo ha sviluppato le specifiche WMM (Wi-Fi Multimedia ) ed un

programma che certifica le funzionalità di tipo QoS offerte nelle reti Wi-Fi.Categorie

d'Accesso (AC) WMM definisce quattro categorie di accesso derivate dalla specifica

802.11d, che corrispondono a quattro livelli di priorità.


21

Mentre le quattro AC sono state designate per specifiche tipologie di traffico (voce, video,

best effort e traffico a bassa priorità), le specifiche WMM lasciano il gestore della rete

libero di decidere l'ordine di priorità fra le calssi. WMM specifica inoltre un protocollo di

comunicazione tra l'Access Point (AP) ed i client per specificare le politiche di accesso ai

servizi di QoS e per inviare richieste da parte dei terminali.

La figura 1.6 mostra il comportamento della WMM fra flussi di traffico che si contendono

la banda disponibile. Nel primo grafico viene data priorità allo stream di tipo video rispetto

agli altri. Durante i primi dieci secondi entrambi i traffici hanno abbastanza risorse

disponibili; l'introduzione di un terzo stream fa sì che la domanda di banda superi quella

diponibile. WMM dà allora al traffico video una priorità maggiore in modo che abbia le

risorse necessarie. Nel secondo grafico la WMM non è abilitata e per questo i tre stream

hanno uguale accesso al mezzo di trasporto e vengono penalizzati in ugual misura.

Figura 1.7 comportamento della WMM fra flussi di traffico che si contendono la banda disponibile

WMM è una estensione del meccanismo Distributed Coordination Function (DCF) basato

sul protocollo CSMA/CA il quale fornisce priorità uguale per tutti i dispositivi e si basa

sull'algoritmo di tipo best effort, “listen before talk”. Ogni client calcola un tempo casuale

di backoff ed al termine può trasmettere solo se non vi sono altri utenti che stanno

sfruttando il canale. In questo modo tutti hanno l'opportunità di utilizzare il mezzo di

trasporto fisico, ma in condizioni di alto traffico la rete si sovraccarica e le prestazioni di

tutti i dispositivi degradano in ugual misura. Con le quattro categorie di accesso mostrate

in precedenza, la WMM va incontro all'inadeguatezza del DCF nel supportare traffico


22

multimediale. Gli access point WMM inoltre possono coesistere con dispositivi non

abilitati a gestire la WMM in quanto ai pacchetti da questi generati viene assegnata la

categoria di tipo best effort. Come mostrato in figura 1.7, i pacchetti generati dalle

applicazioni sono suddivisi in quattro code fra loro indipendenti (una per ogni AC). Vi è

poi un meccanismo che evita le collisioni interne il quale si va ad aggiungere all'altro per

risolvere le collisioni esterne e determinare a quale client deve essere garantita

l'opportunità di trasmettere (TXOP).

Figura 1.8 Code indipendenti di WMM

• L'algoritmo per la gestione delle collisioni che è responsabile della prioritizzazione del

traffico è di tipo probabilistico e di basa su due parametri temporali: il minimo intervallo

fra i frame, Arbitrary Inter-Frame Space Number (AIFSN):

• la Contention Window (CW), detta anche attesa casuale di backoff,

• questi valori sono più piccoli all'aumentare della priorità del traffico.

Per ogni AC, il periodo di backoff è calcolato come la somma dell'AIFSN e di un numero

casuale compreso fra zero e CW. Il valore di CW non è costante ma dipende dal tempo.

All'inizio la lunghezza della ContentionWindow dipende da AC: ogni volta che si ha una

collisione tale valore è raddoppiato fino a che non si raggiunge un limite fissato anch'esso

dalla AC. La Access Category con il CW più basso è quella che guadagna il TXOP. Una

volta che il client ha ottenuto la TXOP, questi è autorizzato a trasmettere per un tempo che

dipende dalla AC e dal bit rate consentito dal livello fisico.[7]


23

1.3 Il lavoro svolto Nei capitoli che seguiranno si procederà alla progettazione di un’architettura di rete atta ad

implementare una politica di QoS basata sulla gestione degli accessi alla rete e sulla

gestione dei vari flussi di traffio generati dagli utenti. In particolar modo , dopo aver

illustrato uno schema di principio dell’architettura completa, attraverso la modifica di un

software esistente denominato “Hostqs” [15] e l’utilizzo di un particolare driver per

schede wireless, Hostap [14], si è proceduti ad implementare una differenziazione del

traffico basata sui MAC address di ogni singolo utente.

Si è dovuta quindi effettuare un’analisi preliminare dei software a disposizione (Hostap,

Hostqs) per poi passare alla loro modifica.


24

Capitolo 2 Access Point con supporto della qualità del servizio:HostAP e HostQs

Questo capitolo rappresenta la parte principale per l’acquisizione dello stato dell’arte delle

tecnologie che si sono utilizzate: attraverso uno studio dei software di base HostAP1 e

HostQs2 si può ottenere una prima realizzazione di un Access Point che fornisca un

supporto della qualità del servizio.

Sfortunatamente le regole sulle quali si basa la politica di schedulazione dell’HostQs, o

più precisamente di quella parte dell’HostQs che viene chiamata Queue Manager, non

sono utili alla realizzazione della idea iniziale.

Tuttavia per un buon utilizzo delle strategie da realizzare, si rende necessaria un’analisi

approfondita di questi due elementi chiave.

1 http://hostap.epitest.fi/ 2 http://www.inlab.csp.it/tools/wireless/hostqs/


25

2.1 Hostap

Il progetto di HostAP è formato da tre componenti principali:

• il driver di HostAP che lavora sotto Linux con schede basate su tecnologia

Prism2/2.5/33;

• il demone hostapd per gli Access Point: include funzioni base per l’autenticazione

di sistemi Linux e BSD basate sullo standard IEEE802.11x, identificatori EAP e

autenticazioni per server RADIUS;

• WPA Supplicant per driver di Linux, BSD e Windows.

HostAP è un driver che controlla sotto Linux le schede wireless basate sul chipset Intersil

Prism 2/2.5/3. Il driver supporta la cosiddetta modalità HostAP o Master che controlla i

time critical tasks, cioè le funzioni di gestione dello standard IEEE802.11x per fa sì che un

normale computer agisca come un Access Point, senza alcun aggiunta di ulteriori

firmware.

Inoltre esso fornisce supporti per le operazioni delle normali stazioni BBS e IBBS. Alcune

funzioni (come WPA e RSN) sono supportate solo se il driver viene accompagnato da altri

programmi di utilità quali, hostapd e WPA Supplicant.

Le stazioni con tecnologia Intersil Prism2 supportano il cosiddetto modo HostAP nel quale

si gestiscono quei compiti legati alle temporizzazioni critiche come l’invio di segnali di

controllo e di riconoscimento di frame (beacon e acknowledgement), ma lasciano gli altri

compiti di gestione al driver del computer host.

Oltre a implementare le funzioni di base necessarie a inizializzare e configurare le schede

basate sulla tecnologia Prism2, a inviare e ricevere frame, il driver è anche fornito di un

sistema per raccogliere informazioni di tipo statistico.

Inoltre, esso include un’implementazione delle seguenti funzioni dello standard

IEEE802.11:

3 http://wiki.personaltelco.net/index.cgi/Prism2Card


26

• autenticazione (e deautenticazione)

• associazione (con riassociazione e deassociazione)

• trasmissione di dati tra due stazioni wireless

• controllo dell’energia (PS - Power Saving)

• gestione di frame per il PS con segnalazioni e buffering.

Nel pacchetto di HostAP sono presenti anche altre funzioni per il debugging e il controllo

di strutture dello standard IEEE802.11, come l’accesso alle configurazioni dei record

hardware, ai registri di I/O e alle frames con gli header 802.11.

Quando viene usato anche il demone, la combinazione di HostAP e hostapd permette

funzioni speciali:

• il settaggio della chiave come previsto dall’IEEE802.1x e del WEP (Wired

Encryption Privacy) dinamico;

• l’accounting RADIUS per l’autenticazione IEEE802.11 (nel caso si utilizzi

questo server come supporto);

• l’accesso al sistema;

• e altre funzionalità base dello standard IEEE802.11f.

Hostapd è un demone per Access Point e server di autenticazione che implementa alcune

funzionalità base degli Access Point previste dallo standard IEEE802.11, come

l’autenticazione così come preista dello standard IEEE802.1x/WPA e autenticazione

RADIUS.

Il WPA (Wi-Fi Protected Access) è una tecnologia che ha come scopo la gestione della

sicurezza delle reti wireless attraverso la protezione dei dati (encrypting) e il controllo di

accesso alla rete attraverso un forte controllo sull’utente: l’autenticazione e l’associazione

sono affidati ad un meccanismo di negoziazione di una chiave, mentre il roaming è


27

controllato dal driver wireless.

Sia l’hostapd che il WPA sono disegnati per essere programmi “demone” che vengono

eseguiti in background e agiscono come componenti finali controllando le autenticazioni e

le connessioni wireless.

2.2 HostQs: Differenziazione del traffico in WLAN

La questione del supporto della qualità del servizio (QoS - Quality of Service) nelle attuali

reti locali senza filo (WLAN - Wireless Local Area Network) è affrontata dal software

Queue Manager con un approccio molto innovativo, chiamato HostQs, che mira alla

differenziazione del traffico a seconda di requisiti di QoS lavorando a livello 2, ovvero al

livello LLC.

L’approccio è basato sulla creazione di una coda LLC per ogni categoria di traffico e sulla

schedulazione delle code in accordo con il concetto di connessione virtuale tra le differenti

priorità all’interno della stazione wireless. La frame alla testa della coda LLC che vince la

contesa è consegnata al livello MAC e gestita in base alle regole di questo sottolivello. Il

meccanismo proposto è stato implementato in ambiente Linux su un Access Point Open-

Source usando una scheda basata su un chipset Prism2.

2.2.1 Introduzione a HostQs

Una delle applicazioni più promettenti delle WLAN basate sulla tecnologia IEEE 802.11 è

senza dubbio il supporto di traffico multimediale come ad esempio Voice over IP (VoIP).

In realtà le WLAN potrebbero essere utilizzate con molto successo per trasportare traffico

voce su un’architettura IP se la rete fosse utilizzata solo per questo scopo! Ma nelle

WLAN classiche che trasportano traffico di natura eterogenea nascono molti problemi a


28

causa del limitato grado di sviluppo del supporto QoS che l’attuale tecnologia 802.11b

riesce a fornire.

L’esigenza di servizi con disponibilità di banda garantita ha portato quindi allo sviluppo di

nuovi standard IEEE o almeno a degli abbozzi di standard, come il cosiddetto IEEE

802.11e [35], nel quale si definiscono le procedure MAC per supportare applicazioni LAN

con requisiti di QoS, compreso traffico voce, audio e video su WLAN.

Lo standard IEEE 802.11e introduce una funzione di coordinamento ibrido (HFC -

Hybryd Coordination Function) e specifica poi due schemi di accesso: l’accesso a canale

distribuito migliorato (EDCA - Enhanced Distributed Channel Access) e l’accesso a

canale controllato da HCF (HCCA - HCF Controlled Channel Access) [8]. Un analisi un

po’ più approfondita dei meccanismi di accesso 802.11e possono essere trovati in [9].

Tuttavia non si trovano disponibili implementazioni commerciali né dell’EDCA né del

HCCA e lo studio delle prestazioni si basa soltanto su analisi teoriche e simulazioni. In

particolare in [10] viene presentato uno studio analitico, mentre in [11], [12] e [13] si

possono trovare risultati di simulazione.

L’approccio HostQs non fa parte dell’IEEE 802.11e ma può essere visto come un

miglioramento dell’architettura dello standard IEEE 802.11b che fornisce una

differenziazione del traffico in modo simile a EDCA, ma senza richiedere modifiche al

livello MAC.

L’interpretazione principale di questo approccio è un’architettura che può essere vista

come una soluzione intermedia prima che lo standard 802.11e sia definitivamente e

largamente diffuso: siccome l’approccio HostQs si basa sugli stessi principi dell’EDCA, è

comprensibile come entrambe le soluzioni possano coesistere e allo stesso tempo, poiché

HostQs non apporta modifiche al MAC 802.11b, si garantisce una compatibilità di base.


29

2.2.2 QoS dell’IEEE 802.11e: la funzione EDCA

In questo paragrafo saranno esposte brevemente le caratteristiche principali dell’EDCA;

per ulteriori informazioni si rimanda a [8] e [9].

Così come la funzione di coordinamento distribuito (DCF - Distributed Coordination

Function) presente nell’802.11, anche la funzione EDCA è basata sullo schema

CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) e impiega il

concetto di Inter Frame Space (IFS) come meccanismo di backoff. Le innovazioni

introdotte sono:

• ogni volta che una stazione 802.11e si aggancia a un canale, viene autorizzata a

trasmettere una o più frame in un dato intervallo di tempo chiamato Transmission

Opportunity (TXOP) che è caratterizzato da una durata massima, indicata con

TXOP-limit;

vengono definite categorie di accesso (AC - Access Categories), ognuna delle quali

corrisponde ad un differente livello di priorità e ad un differente insieme di parametri

che vengono usati per la contesa del canale. In particolare una stazione 802.11e che

opera con la funzione EDCA può includere fino a 4 code MAC. Una coda utilizza i

seguenti parametri per accedere al canale:

• spazio tra due frame (AIFS[AC] - Arbitration Inter Frame Space), parametro simile

al DIFS usato dalla DCF;

• la Finestra di Contesa Minima e Massima, Contention Window (CWmin[AC]

,CWmax[AC]);

• il tempo limite TXOP-limit[AC] 4

• Più è alta la priorità di una AC, più sono piccoli i parametri AIFS[AC], CWmin[AC]

,CWmax[AC]; più è grande TXOP-limit[AC], maggiore risulta la capacità della

categoria di accesso. In ogni caso i valori di CWmin[AC] e CWmax[AC] devono

4 Il valore di AIFS deve essere grande almeno quanto l’intervallo DIFS; l’unica eccezione è rappresentata nel caso di un AP che può usare un AIFS grande anche µs.


30

essere scelti con molta cura per evitare situazioni di alta probabilità di collisioni nei

flussi di traffico che appartengono alla stessa AC;

• all’interno di ogni stazione 802.11e, uno schedulatore risolve le collisioni virtuali

tra le code AC, ovvero tra le varie istanze CSMA/CA, abilitando alla trasmissione

sempre la coda associata alla priorità più alta.

2.2.3 Differenziazione del traffico a livello LLC

Come già precedentemente sottolineato, l’obiettivo principale della implementazione di un

nuovo meccanismo di differenziazione del traffico è realizzata attraverso uno schema di

priorità simile a quello che lo standard IEEE 802.11e introdurrebbe se dovesse gestire un

traffico molto eterogeneo, mantenendo comunque una compatibilità di base con le WLAN

esistenti.

I punti cardine del sistema sono:

• nessuna modifica introdotta al livello MAC: per questo motivo il protocollo

CSMA/CA è applicato come nello standard IEEE 802.11b; le modifiche sono

limitate al livello LLC;

• la differenziazione del traffico è basata sull’inserimento delle frame di differenti

categorie di traffico in differenti code; tale divisione delle frame viene effettuata in

base ad un etichetta che nella soluzione proposta è rappresentata dal valore del

campo ToS (Type of Service).

Sebbene le priorità possano essere forzate usando un qualsiasi algoritmo già esistente

(round robin, EDF, ecc.), la scelta di emulare EDCA ha portato ad un supporto delle

priorità attraverso contese e collisioni virtuali tra le code LLC.


31

Figura 2.1: Il ToS nel pacchetto IP

In figura 2.2 è rappresentato un disegno concettuale del nuovo livello LLC e delle sue due

componenti principali, le code di traffico e lo schedulatore delle collisioni. Le diverse

frame vengono accodate in accordo con le indicazioni dei livelli superiori: in questa

implementazione è stato usato lo standard DiffServ nel campo ToS del pacchetto IP.

Ogni coda di traffico i-ma ha una particolare priorità che è espressa dai valori di quantità

chiamate Finestra Minima e Finestra Massima di Contesa Virtuale (VCWmin,i ,VCWmax,i -

Minimum, Maximum Virtual Contention Window).


32

Figura 2.2: Schema del sistema delle code del livello LLC introdotto da HostQs

Le code di traffico sono poi servite in accordo all’ordine stabilito da una contesa virtuale

tra differenti Finestre di Connessione Virtuali VCWi : ad ogni coda di traffico i-ma viene

associato un numero intero tra 0 e VCWi che rappresenta il tempo di backoff per la coda i-

ma, tempo che sarà indicato con tb,i . La coda con il tempo di backoff più piccolo, che sarà

indicato con tb,min , vince la contesa virtuale e viene quindi servita per prima: la frame in

cima a tale coda sarà perciò la prima ad essere trasferita al livello MAC una volta scaduto

il timer di backoff, cioè non appena trascorso il tempo tb,min . Allo stesso istante in tutte le

altre code, il valore tb,i viene decrementato di una quantità che corrisponde esattamente a

tb,min e ci si prepara ad un nuovo processo di contesa. La coda vincitrice quindi genera un


33

altro tempo di backoff il cui valore è tra zero 0 e VCWi e la nuova contesa può iniziare.

Se in due code diverse il timer di backoff scade allo stesso istante, la coda a trasferire la

prima frame al MAC è quella con la priorità nominale più alta, mentre la coda perdente (o

le code perdenti) che partecipavano alla collisione virtuale generano un altro tempo di

backoff dove però la nuova Finestra di Connessione Virtuale è più grande e il suo valore

cresce in maniera esponenziale secondo la relazione:

1*2 += oldnew VCWVCW

Di conseguenza viene generato un flusso da inviare al MAC e l’ordine delle frame risulta

lo stesso di quello che sarebbe stato rispettato da una stazione wireless 802.11e.

Successivamente le frame vengono trasmesse (o sarebbe meglio dire che cercano di essere

trasmesse) con spaziatura temporale che ricorda quella del sistema di backoff orientato alle

priorità adottato nello standard 802.11e.

Ovviamente con questo metodo a fianco alla struttura dei tempi di backoff imposta al

MAC si introduce un ulteriore backoff, ma questa sovrapposizione è necessaria per

forzare la stessa priorità tra le varie stazioni wireless della WLAN: in questo modo il

traffico con bassa priorità accede al canale in media con un tempo più lungo del normale

periodo di backoff.

In seguito si vedrà che il backoff addizionale viene richiesto solo se più di una stazione

implementa la differenziazione di traffico allo strato LLC, nel qual caso il traffico con

bassa priorità viene egualmente penalizzato.


34

2.2.4 L’ implementazione di HostQs

L’architettura di seguito proposta è stata implementata su un sistema Linux facente uso di

una scheda di rete dotata di una tecnologia particolare5. Il sistema è fornito quindi di un

driver capace di supportare la cosiddetta funzionalità HostAP [11], cioè ha la capacità di

gestire le funzioni dello standard IEEE 802.11 in modo tale da trasformare un normale

computer portatile fornito di una scheda di rete wireless in un potente Access Point senza

richiedere l’utilizzo di alcun firmware ulteriore.

Oltre a comportarsi come un Access Point, la funzionalità HostAP supporta anche la

possibilità di gestire le normali operazioni sulle stazioni di una sottorete semplice o BSS

(Basic Service Set).

Nella modalità HostAP, il firmware si occupa della gestione dei compiti basati sui

cosiddetti tempi critici come ad esempio l’invio di segnali e la richiesta di conferme di

avvenuta ricezione delle frame (in gergo dette acknowledgement o ack), lasciando gli altri

compiti di gestione al computer host. Questo driver implementa inoltre le funzionalità

base necessarie per inizializzare e configurare una scheda basata su tecnologia Prism2, per

mandare e ricevere frame e per raccogliere informazioni di tipo statistico. Inoltre, esso

include l’implementazione di molte funzioni IEEE 802.11 come l’autenticazione (e la

deautenticazione), l’associazione (la reassociazione e la deassociazione) di una utente

mobile, la trasmissione dati tra due stazioni wireless, il controllo della potenza (PS -

Power Saving) e buffering di segnali e di frame per le stazioni PS.

HostQs è stato implementato attraverso la modifica del codice originale del driver HostAP

e l’aggiunta di un modulo supplementare che si occupa di frame allo strato LLC (figura

5.2). Il modulo del driver contiene una funzione di trasmissione modificata che invia i

pacchetti di rete non direttamente allo strato MAC ma prima al modulo supplementare la

cui funzione di accodamento è rappresentata attraverso Macro del kernel. La funzione di

trasmissione originale è mantenuta nel driver sotto un nome diverso e rappresentata

anch’essa attraverso Macro del kernel in modo da permettere che possa essere utilizzata

5 scheda di rete dotata di chipset basato su tecnologia Intersil’s Prism2/2.5/3.


35

dal modulo supplementare per la spedizione dei pacchetti.

Il modulo supplementare conserva i pacchetti in code separate, dipendentemente dai loro

valori del ToS; un elemento separato risolve la contesa virtuale e schedula le frame

secondo il risultato della contesa virtuale. Quando dei pacchetti devono essere spediti, il

modulo utilizza la funzione di trasmissione originale implementata nel driver di HostAP,

così i messaggi vengono spediti nello stesso ordine in cui erano stati accodati dallo strato

superiore.

Le code di traffico implementate con priorità decrescente sono le seguenti :

• traffico in tempo reale (ad esempio chiamate VoIP)

• applicazioni di streaming multimediale

• dati best effort (trasferimento file, navigazione web, ecc.)

• e i valori di VCW che vi sono stati assegnati sono mostrati in tabella 2.1.

La realizzazione è stata ottimizzata in modo da poter essere lanciata anche su terminali

lenti: nelle prove eseguite è stato usato un sistema operativo Linux versione 2.4.22

installato su un Pentium III da 450 MHz con 256 MB RAM.

Una implementazione Open-Source di HostQs è disponibile su rete [12].

Tabella 2.1: Impostazione del VCW


36

2.2.5 Risultati del test

In figura 2.3 è mostrata la configurazione di rete utilizzata per il test.

Figura 2.3: Scenario del test

Il nodo di HostQs è configurato come un Access Point per una BSS che include alcune

stazioni wireless indicate con WS (Wireless Stations). HostQs raccoglie traffico da un

sintetizzatore di voce, da un generatore di streaming video e da un generatore di traffico

TCP. Quindi spedisce le frame alle varie WS dopo aver stabilito le priorità attraverso il

meccanismo della contesa virtuale.

Le priorità sono assegnate in ordine decrescente a voce, video e dati rispettivamente; in

tabella 5.1 sono stati riportati i valori scelti per le rispettive VCWmin e VCWmax. Le

stazioni wireless accedono al canale usando i criteri dello standard IEEE 802.11b senza

alcun miglioramento e senza alcuna priorità sul traffico. Così la differenziazione di traffico

e l’impostazione delle priorità è realizzata solamente dalla direzione di downstreaming, in

altre parole il blocco avviene tra Queue Manager e il driver HostAP, ma solo nella fase di


37

invio dei dati diretti alle WS.

La fonte di voce sintetica proveniente dal server voce è pensata per emulare un flusso di

traffico che potrebbe essere generato da VoIP codificato attraverso vo-coder G.711 a 64

Kbps senza nessuna funzione di rivelazione di voce VAD (Voice Activity Detection). Lo

streaming video è di tipo Unicast, scorre con una frequenza di 350 Kbps ed è generato da

un server Fenice, un progetto Open-Source studiato appunto per applicazioni di questo

tipo[13]. Alcuni esperimenti comprendono anche interferenza di traffico UDP, generato

sinteticamente nella direzione di downstream. La valutazione delle prestazioni relative alla

qualità della voce è operata da elementi come Agilent VQT e PESQ [14].

PESQ (Perceptual Evaluation of Speech Quality) è un tool di misurazione che può predire

i risultati di un test di ascolto su sistemi di telefonia basandosi su un modello sensoriale

che confronta il segnale originale, e perciò non processato, col il segnale degradato dalla

rete o da un elemento della rete. La qualità che alla fine ne risulta è analoga a una “qualità

media soggettivamente testata”, cioè misurata con prove empiriche; il valore che si dà a

questa grandezza si indica con l’acronimo MOS (Mean Opinion Score).

I risultati di PESQ sono calibrati usando un database molto complesso di test soggettivi

che dà alla qualità media soggettivamente testata una valutazione da 1 a 4.5. La qualità

eccellente è indicata con valori tra 3.2 e 4.5, quella mediocre è rappresentata da valori di

PESQ tra il 2.5 ed il 3.2, quella cattiva infine ottiene valori inferiori a 2.5.

La valutazione della prestazione di traffico video è operata direttamente dai client video,

in termini di percentuale di pacchetti video perduti.

Come nota finale, si riporta l’osservazione che l’uso di HostQs in una situazione dove la

BSS è formata da stazioni wireless che non offrono un supporto di qualità del servizio, ha

suggerito una semplificazione nell’algoritmo di schedulazione di HostQs stesso. Infatti c’è

effettivamente un piccolo svantaggio nell’usare un meccanismo supplementare di gestione

dei tempi di backoff nello strato LLC poiché ogni WS usa una scheda gestita dai criteri di

IEEE 802.11b: il traffico al livello di HostQs sarebbe perciò inutilmente ritardato e i

relativi pacchetti verrebbero retrocessi per abbassare le priorità rispetto al traffico

proveniente dalle stazioni wireless, senza tener conto delle effettive priorità interne.


38

Analogamente l’uso di HostQs in un’architettura che non supporta qualità del servizio ha

poco senso in termini di AIFS (Arbitration Inter Frame Space), cioè lo spazio tra due

frame. Per questo motivo, lo strato LLC dell’HostQs è autorizzato a inoltrare

immediatamente le frame al livello MAC quando la contesa è risolta, senza aspettare il

tempo di backoff.

Le contese virtuali divengono così semplicemente un algoritmo di ordinazione all’interno

del blocco HostQs, sebbene abbiano l’importantissima proprietà di fornire un’ordinazione

simile a quella della funzione EDCA dello standard 802.11e.

Nella tabella 2.2 è mostrata una valutazione preliminare: lo scopo è riportare delle scelte di

CWmin e CWmax col relativo throughput ottenuto da due flussi UDP con diverse priorità

che usano quei CW.

Ai due flussi corrispondono diversi valori del ToS nell’header IP; questi valori del ToS

sono quindi elencati secondo tre categorie di accesso diverse, una alta indicata con H, una

media indicata con M e infine una bassa indicata con L; il ToS pari a 6 indica una priorità

alta, pari a 5 per una priorità media, pari al valore nullo per una priorità bassa.

Tabella 2.2: Throughput dei flussi UDP per differenti valori di CW,

ovvero per priorità alta (H), media (M) e bassa (L)

I throughput della tabella misurati in Mbps evidenziano che:

• è possibile ottenere delle priorità scalabili, cioè gradi diversi di priorità. Infatti da

un’analisi più accurata dei valori risulta che nella metà superiore della tabella si


39

nota una differenza di throughput molto grande tra flussi con priorità alta e i flussi

con priorità bassa; nella metà inferiore della tabella invece la differenza di

throughput tra i flussi con priorità alta e i flussi con priorità media è molto ridotta;

• CWmin è il parametro dominante, mentre il sistema è insensibile alle variazioni del

valore di CWmax. Si osservi infatti che nella seconda riga della tabella 5.2 è stato

cambiato solo un valore rispetto alla prima riga: il CWmin è stato ridotto da un

valore 3 ad un valore nullo; per la relativa categoria di accesso bassa (indicata con

L) questo equivale a dare una priorità molto bassa a tutti i flussi di quella categoria,

come del resto ci si poteva aspettare.

Si noti poi che nella terza riga della tabella 2.2 invece, l’unico valore ad essere stato

variato risulta il CWmax della categoria di accesso alta, ridotta da un valore di 1023 a un

valore di 511: la risposta del sistema in termini di throughput risulta assolutamente

invariata!

Il successivo insieme di risultati si riferisce ad un singolo flusso VoIP con rumore di fondo

crescente che interferisce con traffico UDP.

Figura 2.4. PESQ come funzione del traffico UDP formato da un flusso VoIP e traffico interferente


40

La figura 2.4 mostra il PESQ rilevato per tale flusso visto come funzione del traffico

globale offerto alla WLAN. Le due curve della figura riportano le prestazioni del flusso

VoIP con e senza il supporto delle priorità. Si vede chiaramente che nel caso in cui

vengano applicati solamente i normali criteri di gestione del traffico dello standard IEEE

802.11b senza il supporto delle priorità, la qualità del flusso VoIP comincia a degradarsi

appena dopo i 4 Mbps di traffico offerto e che prima dei 5 Mbps la qualità scende molto al

di sotto di livelli accettabili. L’ultimo insieme di risultati delle figure 2.5, 2.6 e 2.7

mostrano le prestazioni di una WLAN che trasporta un singolo flusso VoIP e 1, 2 o 3

streaming video concorrenti, considerati di nuovo come una funzione di traffico UDP

interferente. È interessante osservare che nel caso in cui vengano applicati solamente i

normali criteri di gestione del traffico IEEE 802.11 senza il supporto delle priorità, sia

VoIP che i flussi di video incontrano una degradazione della qualità approssimativamente

della stessa consistenza che si riscontra fra i 4.5 Mbps e 5 Mbps, dipendentemente dal

numero di video concorrenti. Al contrario il traffico che ha precedenza, cioè quello voce e

video, sebbene con priorità diverse, mantiene lo stesso livello di QoS indipendentemente

dal carico della rete.


41

Figura 2.5: PESQ e percentuale di perdita di pacchetti video come funzione del traffico UDP

interferente formato da un flusso VoIP, uno streaming video e traffico interferente


interferente formato da un flusso VoIP, due streaming video e traffico interferente


42


interferente formato da un flusso VoIP, tre streaming video e traffico interferente


43

Capitolo 3 L'architettura di riferimento

Nel seguente capitolo è illustrato lo schema concettuale dell’architettura di riferimento in

cui il software sviluppato nel presente lavoro di tesi si cala. Oltre allo schema di principio,

vengono illustrati anche i principali scenari di funzionamento del sistema, illustrando per

ogni componente la modalità di funzionamento e l’interazione con gli altri componenti

dell’infrastruttura


44

3.1 Architettura del sistema

3.1.1 Scenario L'idea base su cui si fonda la struttura dell'architettura in esame è quella di garantire agli

“utenti mobili” ed ai propri device di muoversi liberamente all'interno di una vasta area in

cui essa agisce, fornendo loro connessioni che gli permettono la fruizione di diversi servizi

locate o remoti (stampanti, web server,...). Il concetto del “muoversi liberamente” si

riferisce alla capacità che dovrebbe avere ciascun utente abilitato di accedere ai servizi

indipendentemente dal device. Si vuol fare in modo che ciascun utente che abbia acquisito

il diritto di accesso alla suddetta architettura di riferimento lo possa fare con qualsiasi

device in suo possesso che abbia connettività wireless senza doversi preoccupare di averlo

preventivamente registrato, come accade per i correnti sistemi di identificazione.

3.1.2 Architettura Nel suddetto scenario l'architettura che si propone è basata su un sistema di autenticazione,

autorizzazione e accesso ai servizi che utilizza un “numero d'identificazione d'utente”

registrato su un “embedded badge”. Tale numero d'identificazione servirà al gestore degli

accessi dell'architettura di riferimento per gestire gli utenti nel sistema.

In figura 3.1 è riportato uno scenario realistico dell'architettura di riferimento.

Figura 3.0-2 L’architettura proposta


45

Ogni nodo dell'architettura può essere visto come un dominio di autenticazione per

dispositivi mobili NAD (Nomadic Authentication Domains).

All'interno di ogni nodo è presente un Authentication Domain Agent (ADA) e vari

dispositivi mobili.

L'idea è quella di dotare di un dispositivo Bluetooth ogni dispositivo mobile in modo che

attraverso di esso si riesca a comunicare ad un access point Bluetooth presente sull' ADA.

In questo modo l'utente fornisce la propria chiave di identificazione al sistema di

autenticazione in modo da accedere all'infrastruttura di rete.

Tale chiave oltre a permettere l’accesso al sistema contiene anche l’informazione

necessaria al sistema per garantire una politica di qualità del servizio assegnata all’utente.

Infatti, attraverso di essa, il sistema accederà ad una tabella in cui è memorizzata la classe

di QoS, assegnata preventivamente all’utente, innescando i meccanismi necessari alla

gestione della politica .

All'interno dell'architettura di riferimento si può individuare due lati, un lato utente formato

dai seguenti elementi:

• dispositivi mobili (notebooks, laptops, PDAs e qualsiasi dispositivo dotato di

possibilità di connessione wireless 802.11b)

• embedded badges, nello specifico un'unità Bluethooth sulla quale è registrata la

chiave di identificazione dell'utente.

Nel momento in cui c'è una richiesta di comunicazione da parte del dispositivo

mobile esso si occupa di comunicare con un Access Point Bluetooth del dispositivo

ADA in modo da effettuare l'autenticazione.

Il secondo lato è che si occupa della fruizione dei servizi e del collegamento alla “wired

network” formato dall' Autentication Domain Agent.

L'ADA può essere visto come un sistema composto da tre moduli che interagiscono tra di

loro. In figura 3.2 è riportato lo schema di principio di un'unità ADA.


46

Figura 3.2: Schema di principio di un'unità ADA

Il primo modulo dell'ADA è il “Gestore degli accessi” che si occupa dell'autenticazione

degli utenti del sistema. Esso è composto dai seguenti moduli:

• Access Point Bluetooth

• Gestore dell'Access Point Bluetooth: ha il compito di gestire il trasferimento delle

informazioni tra l'access point e il “gestore delle autenticazioni”. In pratica ha il

compito di acquisire e trasmettere al gestore delle autenticazioni la chiave di

identificazione dell'utente e l'indirizzo MAC del dispositivo che dovrà partecipare

alla comunicazione con la rete.

• Gestore delle autenticazioni: ha il compito verificare se l'utente è registrato o meno

al sistema. In pratica una volta ricevuto l'identificativo dell'utente consulta la

tabella delle registrazioni e se tale identificativo è presente si appresta ad


47

aggiornare la tabella di priorità del traffico “hostqs”. Oltretutto invia un segnale di

“refresh table” al modulo di gestione della QoS. Alla fine fornirà il via libera al

DHCP server per fornire un indirizzo IP valido al dispositivo col MAC validato e

invierà al gestore dell'Access Point Bluetooth il comando per trasmettere all'utente

il segnale di “connessione avvenuta con successo”. In caso di mancata validazione

del dispositivo invierà al gestore dell'Access Point Bluetooth il comando per

trasmettere il segnale di “connessione fallita”.

• Tabella degli accessi: è una tabella in cui sono registrati gli utenti abilitati ad

entrare nella rete wireless e di relativi “Id. number”. Tale tabella sarà letta dal

“gestore delle autenticazioni”. Il popolamento della tabella non è trattato poiché

nel presente lavoro di tesi non è stato affrontato lo sviluppo del modulo del

“gestore degli accessi”, ma si può facilmente intuire che essa possa essere anche

formata da più tabelle fisiche casomai gestite da un LDAP server.

Il secondo modulo dell'ADA è l'elemento “hostqs” che si occupa della gestione della

trasmissione a priorità nella rete wireless. Tale modulo non si occupa della gestione del

traffico di rete tra dispositivi wireless all'interno della stessa sottorete, bensì solo del

traffico tra rete wired e rete wireless (ipotizzando che il maggior flusso di traffico venga

richiesto ad Internet e quindi provenga da una wired Backbone ). Esso è composto dai

seguenti moduli:

• queue_mgr: è il modulo del sistema operativo che si occupa della gestione delle

priorità. Quando viene caricato esso memorizza in una tabella dinamica (hash table)

la tabella di priorità ed ogni volta che riceve un pacchetto da trasmettere verifica se

l'indirizzo MAC del destinatario è presente o meno in tabella. Se l'indirizzo è

presente legge il valore associato di QoS e associa il pacchetto alla coda di

trasmissione relativa. Le code di trasmissione sono schedulate dallo schedulatore,

implementato all'interno del modulo, il quale provvede a trasmettere al driver

sottostante i pacchetti da trasmettere secondo una politica precisa illustrata nel

prossimo capitolo. Tale modulo si interfaccia direttamente con l'infrastruttura di

rete del kernel. In particolare accede al buffer di rete presente in memoria dove

vengono accodati i pacchetti ricevuti.


48

• Tabella di priorità “hostqs”: è un file residente in memoria di massa che ha il

compito di memorizzare gli indirizzi MAC e la QoS associata. Viene popolato e

aggiornato dal “gestore delle autenticazioni”. Non è trattata la politica di

aggiornamento degli elementi all'interno del file poiché non è argomento del

presente lavoro di tesi lo sviluppo del “gestore degli accessi”, ma è facilmente

ipotizzabile che tale meccanismo sarà basato su una tecnica basata su time outs

scaduti i quali si procederà ad aggiornamento della topologia di rete,attraverso

un'interrogazione di tutti i dispositivi presenti nella rete wireless locale.

• Hostap driver : è il driver che pilota la scheda wireless, opportunamente modificato

per poter supportare il modulo queue_mgr. In questo modo come già visto nei

capitoli precedenti è possibile trasformare una scheda wireless basata su chipset

PrismII in un “Access Point”.

Il terzo modulo dell'ADA è un server DHCP che, opportunamente modificato, associa

indirizzi IP validi ai wireless device che sono stati correttamente autenticati. Il “gestore

delle autenticazioni” sarà l'ente che configurerà le politiche del server in modo da abilitare

i device degli utenti ad accedere alla rete.


49

3.2 Principio di funzionamento

Di seguito sono riportati diversi Activity Diagram [17] [18] che illustrano i meccanismi di

funzionamento dei vari componenti del sistema software.

Nel diagramma 3.1 si illustra il ruolo dell'utente, mettendo in evidenza il processo di

connessione alla rete.

Diagramma 3.1: Activity Diagram utente


50

Nel diagramma 3.2 si evidenzia il ruolo dell'embedded badge nella gestione della

comunicazione tra utente e gestore degli accessi:

Diagramma 3.2: Activity Diagram Embedded Badge


51

Nel diagramma 3.3 si evidenzia il ruolo del Gestore dell'Access Point Bluetooth nella

gestione della comunicazione tra periferiche Bluetooth e Gestore delle Autenticazioni:

Diagramma 3.3: Activity Diagram Gestore dell'AP Bluetooth


52

Nel diagramma 3.4 si evidenzia il ruolo del Gestore delle Autenticazioni e l'interazione tra

il Gestore dell'Access Point Bluetooth e il modulo queue_mgr:

Diagramma 3.4: Activity Diagram Gestore delle Autenticazioni


53

Nel diagramma 3.5 si evidenzia il ruolo del modulo queue_mgr e l'interazione tra il

Gestore delle Autenticazioni e il driver HostAP:

Diagramma 3.5: Activity Diagram queue_mgr


54

3.3 Esempi di funzionamento

Nel presente paragrafo vengono riportati a titolo di esempio alcuni Sequence Diagram [18]

[19] che illustrano le possibili evoluzioni del sistema di autenticazione, rimandando al

capitolo successivo la trattazione in dettaglio del meccanismo di comunicazione a priorità

del modulo queue_mgr.

I seguenti diagrammi inoltre non hanno lo scopo di illustrare in dettaglio i protocolli di

comunicazione dei diversi moduli (sincronizzazione, timeouts, gestione concorrente delle

risorse), bensì vogliono illustrare l'evoluzione del sistema e lo scambio di messaggi tra i

vari moduli da un punto di vista puramente concettuale, non avendo affrontato al momento

il progetto logico di tutta l'architettura.

Nel diagramma 3.5 si evidenzia il meccanismo di connessione con il Sitema di

Autenticazione e l'assegnazione dell'indirizzo IP all'utente

Diagramma 3.5:Sequence Diagram che illustra il meccanismo di connessione avvenuta con successo


55

Il diagramma 3.6 analogamente al precedente mostra il meccanismo di connessione con il

Sitema di Autenticazione e l'assegnazione dell'indirizzo IP all'utente ma in questo caso

avviene anche il refresh della tabella “hostqs” e l'hash table nel modulo queue_mgr

Diagramma 3.6: Sequence Diagram che illustra il meccanismo di connessione avvenuta con successo, refresh della tabella Hostqs e dell'hash table di queue_mgr


56

Nel diagramma 3.7 si riporta invece il fallimento del tentativo di connessione da parte

dell'utente al sistema.

Diagramma 3.7: Sequence Diagram che illustra il meccanismo di connessione rifiutata dal sistema


57

Capitolo 4 Il modulo Hostqs

Il presente capitolo si propone di illustrare i procedimenti adottati per lo sviluppo del

modulo Hostqs dell'Architettura di Riferimento.

Nella prima parte del capitolo sono illustrati i principali meccanismi e strutture dati alla

base del kernel del sistema operativo Linux interessati dallo sviluppo del modulo software

“queue_mgr”.

Vengono oltretutto riportati cenni alla cosiddetta “Linux Kernel Module Programming”,

visto che la programmazione di sistema differisce in molti aspetti dalla programmazione

dal lato utente.

Successivamente sono illustrati i principali passi dello sviluppo del modulo e le tecniche

utilizzate per l'implementazione del meccanismo a priorità. Per mostrare meglio le

principali modifiche apportate al software preesistente, sono riportati i principali segmenti

di codice inserito o modificato ad hoc, mettendone in mostra le loro principali funzionalità.


58

4.1 Il kernel ed i moduli

4.1.1 Kernel space e User space

Il concetto base di un sistema unix-like è quello di un nucleo del sistema (il cosiddetto

kernel) a cui si demanda la gestione delle risorse essenziali (la CPU, la memoria, le

periferiche) mentre tutto il resto, quindi anche la parte che prevede l’interazione con

l’utente, deve venire realizzato tramite programmi eseguiti dal kernel e che accedano alle

risorse hardware tramite delle richieste a quest ultimo. Fin dall’inizio Unix si presenta

come un sistema operativo multitasking, cioè in grado di eseguire contemporaneamente

più programmi, e multiutente, in cui è possibile che più utenti siano connessi ad una

macchina eseguendo più programmi “in contemporanea” (in realtà, almeno per macchine

a processore singolo, i programmi vengono eseguiti singolarmente a rotazione). I kernel

Unix più recenti, come Linux, sono realizzati sfruttando alcune caratteristiche dei

processori moderni come la gestione hardware della memoria e la modalità protetta. In

sostanza con i processori moderni si può disabilitare temporaneamente l’uso di certe

istruzioni e l’accesso a certe zone di memoria fisica. Quello che succede è che il kernel è il

solo programma ad essere eseguito in modalità privilegiata, con il completo accesso

all’hardware, mentre i programmi normali vengono eseguiti in modalità protetta (e non

possono accedere direttamente alle zone di memoria riservate o alle porte di input/output).

Una parte del kernel, lo scheduler, si occupa di stabilire, ad intervalli fissi e sulla base di

un opportuno calcolo delle priorità, quale “processo” deve essere posto in esecuzione (il

cosiddetto preemptive scheduling). Questo verrà comunque eseguito in modalità protetta;

quando necessario il processo potrà accedere alle risorse hardware soltanto attraverso delle

opportune chiamate al sistema che restituiranno il controllo al kernel.

Uno dei concetti fondamentali su cui si basa l’architettura dei sistemi Unix è quello della

distinzione fra il cosiddetto user space, che contraddistingue l’ambiente in cui vengono

eseguiti i programmi, e il kernel space, che è l’ambiente in cui viene eseguito il kernel.

Ogni programma vede sé stesso come se avesse la piena disponibilità della CPU e della

memoria ed è, salvo i meccanismi di comunicazione previsti dall’architettura,

completamente ignaro del fatto che altri programmi possono essere messi in esecuzione dal

kernel. Per questa separazione non è possibile ad un singolo programma disturbare l’azione


59

di un altro programma o del sistema e questo è il principale motivo della stabilità di un

sistema unix-like nei confronti di altri sistemi in cui i processi non hanno di questi limiti, o

che vengono per vari motivi eseguiti al livello del kernel. Pertanto deve essere chiaro a chi

programma in Unix che l’accesso diretto all’hardware non può avvenire se non all’interno

del kernel; al di fuori dal kernel il programmatore deve usare le opportune interfacce che

quest ultimo fornisce allo user space [20] .

Come accennato le interfacce con cui i programmi possono accedere all’hardware vanno

sotto il nome di chiamate al sistema (le cosiddette system call ), si tratta di un insieme di

funzioni che un programma può chiamare, per le quali viene generata un’interruzione del

processo passando il controllo dal programma al kernel. Sarà poi quest’ultimo che (oltre a

compiere una serie di operazioni interne come la gestione del multitasking e l’allocazione

della memoria) eseguirà la funzione richiesta in kernel space restituendo i risultati al

chiamante. In figura 4.1 è riportato uno schema di principio di quanto accennato sopra.

Figura 4.1:Schema di massima della struttura di interazione fra processi, kernel e dispositivi in Linux.

Normalmente ciascuna di queste chiamate al sistema viene rimappata in opportune

funzioni con lo stesso nome definite dentro la Libreria Standard del C, che, oltre alle

interfacce alle system call, contiene anche tutta la serie delle ulteriori funzioni definite dai

vari standard, che sono comunemente usate nella programmazione.

Questo è importante da capire perché programmare in Linux significa anzitutto essere in

grado di usare le varie interfacce contenute nella Libreria Standard del C, in quanto né il


60

kernel, né il linguaggio C, implementano direttamente operazioni comuni come

l’allocazione dinamica della memoria, l’input/output bufferizzato o la manipolazione delle

stringhe, presenti in qualunque programma [20].

4.1.2 Gestione dei moduli

Una delle caratteristiche più significative del kernel Linux è la modularità, che permette,

tutte le volte che si richiede una funzionalità mancante, di tentare, prima di restituire un

errore, il caricamento del modulo che la provvede. I moduli del kernel sono porzioni dello

stesso kernel che possono essere caricate in memoria quando se ne presenta la necessità e

scaricate subito dopo. I moduli del kernel Linux sono quello che in altri sistemi viene

definito driver.

Questo comporta la configurazione del relativo supporto nel kernel e la compilazione come

moduli delle varie funzionalità che si vogliono utilizzare in questo modo; inoltre occorre

anche l’installazione di una serie di programmi in user space che permettono di gestire

questa funzionalità: il pacchetto modutils.

Nelle vecchie versioni del kernel la gestione dei moduli era fatta attraverso un apposito

demone, kerneld, che riceveva le richieste dal kernel ed eseguiva il caricamento dei

moduli. A partire dalla serie 2.4.x il meccanismo è stato realizzato con un apposito

sottosistema del kernel, detto kmod. Il meccanismo si basa una apposita funzione interna al

kernel-2.4.x che prende come parametro una stringa indicante il modulo che si vuole

caricare (ma con questa si possono anche richiedere funzionalità generiche) e crea un

processo temporaneo interno al kernel che consente di invocare un apposito programma in

user space il quale si incarica di tutte le operazioni necessarie al caricamento del modulo.

Questo è di norma modprobe ma si può specificare un qualunque altro programma sia

attraverso l’interfaccia del sysctl sia scrivendolo direttamente in

/proc/sys/kernel/modprobe. Il programma fondamentale per l’uso dei moduli è insmod, che

si incarica di caricare un modulo all’interno del kernel, leggendolo dal disco, effettuando la

risoluzione dei simboli, e collegandolo al codice del kernel.

Il comando prende come parametro il nome del modulo, e per trovare il file il comando

cerca il corrispondente file oggetto sotto la directory /lib/modules/‘uname -r‘, a meno che

non si sia usata la variabile di ambiente MODPATH o una diversa opzione nel file di

configurazione /etc/modules.conf per indicare una directory diversa. Se il modulo li


61

prevede possono essere ulteriormente specificati dei parametri nella forma

parametro=valore dove il parametro dipende dal modulo (la lista dei parametri disponibili

per ciascun modulo si può ottenere tramite il comando modinfo), ed il valore può essere

una stringa o un numero intero, quest’ultimo specificabile sia in forma decimale (17), che

ottale (021), che esadecimale (0x11). Si tenga presente che insmod consente di inserire nel

kernel solo un modulo alla volta, e per farlo ha bisogno di risolvere tutti i simboli necessari

al modulo stesso, se alcuni di questi non sono presenti nel kernel, ma in altri moduli, il

comando fallirà con un errore di “unresolved symbol”.

Come norma di sicurezza il comando non carica i moduli se i relativi file non

appartengono all’amministratore, onde evitare che il contenuto di un modulo possa essere

sovrascritto in caso di compromissione dell’utente cui appartiene, con la conseguente

possibilità di far eseguire direttamente al kernel il codice che si vuole; questo

comportamento può essere disabilitato con l’opzione -r (ad uso principalmente degli

sviluppatori). Inoltre insmod di norma controlla che la versione del kernel corrente e quella

del modulo combacino, in questo modo si evita di caricare moduli che appartengano a

kernel diversi; anche questo comportamento può essere disabilitato con l’opzione -f. Si

tenga presente però che in questo caso viene evitato soltanto il controllo sulla versione del

kernel, il controllo sull’uso dei nomi dei simboli non può essere evitato, questo significa

che se si sono compilati i moduli con il supporto per il versionamento (che crea dei nomi di

simboli contenenti una checksum) non sarà comunque possibile utilizzarli.

Come accennato insmod consente di inserire un modulo solo quando tutti i simboli di cui

questo ha bisogno possono essere referenziati; questo comporta che se alcuni di questi

sono definiti da un altro modulo, si avrà un problema di dipendenze. Per ovviare a questo

problema c’è un secondo comando, modprobe, che permette di risolvere anche tutte le

dipendenze, trovare quali sono gli altri moduli che servono per poterne utilizzare uno, e

caricare preventivamente anche questi.

Il meccanismo con cui modprobe è in grado di risolvere le dipendenze si basa sul

contenuto del file modules.dep che si trova nella directory in cui sono installati i moduli.

Questo viene di norma prodotto in fase di installazione degli stessi (tramite il comando

depmod) ed ha un formato del tipo: /lib/modules/2.4.29/kernel/fs/vfat/vfat.o:

/lib/modules/2.4.29/kernel/fs/fat/fat.o che assomiglia a quello di un Makefile, dove per

ciascun modulo viene indicato la lista degli altri da cui dipende.

Come insmod anche modprobe effettua la ricerca dei moduli da caricare fra quelli

compilati per il kernel corrente, nella directory /lib/modules/‘uname -r‘, dove questi


62

vengono installati. In genere i moduli vengono poi suddivisi in ulteriori sottodirectory;

questa suddivisione cambia a seconda della versione del kernel. Ad esempio a partire dal

kernel 2.4.x i moduli sono installati sotto la directory kernel, e all’interno di questa

suddivisi per categorie: nel caso avremo fs per il supporto dei filesystem, driver per il

supporto delle periferiche, net per il supporto dei protocolli di rete, crypto per gli algoritmi

di crittografia. A loro volta i moduli installati sotto drivers sono suddivisi per tipologia di

hardware.

La potenza di modprobe è che il comando, oltre alla risoluzione automatica delle

dipendenze, è in grado anche di caricare più moduli in contemporanea e, sfruttando la

suddivisione delle sottodirectory appena illustrata, anche uno fra tutti quelli che forniscono

una certa funzionalità. Di norma infatti modprobe prevede come argomento il nome (o i

nomi) dei moduli da caricare, (da indicare senza l’estensione .o finale), se invece si

specifica l’opzione -t si indica di trattare il parametro successivo come un pattern di

ricerca all’interno della directory dei moduli, in questo caso il comando tenterà di caricare

in sequenza tutti i moduli il cui pathname corrisponde al pattern, fermandosi al primo che

viene caricato con successo. Questo consente ad esempio di chiedere il caricamento del

driver di una scheda di rete (senza dover specificare quale) con un comando del tipo:

modprobe -t drivers/net \* dato che in questo caso verranno provati tutti i moduli presenti

in quella directory. Specificando anche l’opzione -a la stessa operazione verrà eseguita per

tutti i moduli della lista senza fermarsi al primo che è stato caricato con successo. Con

l’opzione -l invece si avrà la lista dei moduli che corrispondono. Infine, con l’opzione -r si

può richiedere la rimozione dell’intera pila di moduli caricati in dipendenza dal modulo

specificato (sempre che nel frattempo non siano stati utilizzati).

Un comando essenziale per il funzionamento di modprobe è depmod che crea il file

modules.dep che identifica le dipendenze fra i vari moduli passati come argomenti sulla

riga di comando.È grazie a questo file che è possibile determinare quali sono i moduli che

contengono i simboli necessari per poter poi caricare una altro modulo, così da poter

effettuare il caricamento di tutti i moduli nella giusta sequenza.

In genere il comando viene sempre invocato senza argomenti e con l’opzione -a, dato che

in tal caso esegue il calcolo delle dipendenze con i moduli presenti in tutte le directory

specificate in modules.conf. Con l’opzione -A il calcolo viene effettuato controllando

preventivamente i tempi dei file, aggiornando modules.dep solo se qualcosa è cambiato.

Una volta che i moduli non sono più utilizzati possono essere rimossi con il comando

rmmod, che prende come parametro il nome di un modulo.


63

Ovviamente perché il comando abbia successo il modulo in questione non deve essere in

uso, né contenere simboli usati da un altro modulo (cioè non devono esserci altri moduli

che dipendano da esso). Se però si usa l’opzione -r il comando esegue una rimozione

ricorsiva, cercando di rimuovere anche i moduli che dipendono dal modulo indicato

(diventa così possibile effettuare l’operazione inversa di modprobe). L’uso dell’opzione -a

attiva invece l’autoclean, marca cioè i moduli inutilizzati come “ripulire” e rimuove i

moduli che erano già stati marcati come tali. In questo modo si può compiere l’operazione

in due passi diminuendo la probabilità di rimuovere moduli temporaneamente inutilizzati.

Il comportamento del comando modprobe, e con esso dell’intero meccanismo di

caricamento automatico dei moduli, che viene realizzato attraverso questo programma, è

determinato dal file di configurazione /etc/modules.conf. Qui si possono specificare una

serie di direttive che permettono di controllare sia le modalità con cui vengono caricati i

moduli, che le directory dove effettuare le ricerche. Il formato del file prevede anche la

presenza di direttive condizionali e l’uso di variabili, con sintassi analoga a quella della

shell, ma queste funzionalità non sono molto usate.

4.1.3 Struttura dei moduli e loro scrittura

Nel mondo Unix, moduli come il driver di rete e altri driver complessi appartengono al

kernel (infatti si parla di “sottosistema di rete”), e il nome di “device driver” è riservato

allo strato software di più basso livello, che controlla direttamente l'hardware. Tali

periferiche appartengono ai seguenti tre gruppi:

• Periferiche a carattere: Tali periferiche possono essere considerate dei file, per il

fatto che possono venire lette o scritte. La console (il video e la tastiera) e le porte

seriale e parallela sono esempi di periferiche a carattere. L'accesso avviene tramite

files come /dev/tty0 o /dev/cua0. Una periferica a carattere di solito può solo venire

letta o scritta sequenzialmente.

• Periferiche a blocchi: Storicamente si trattava di dispositivi che potevano essere

letti o scritti solamente in dimensioni multiple della dimensione del blocco: spesso


64

512 o 1024 bytes. Si tratta delle periferiche sulle quali è possibile montare un

filesystem; le periferiche a blocchi più importanti sono i dischi. Si accede

globalmente a tali periferiche tramite files come /dev/hda1. I blocchi di un

dispositivo vengono immagazzinati nel “buffer cache” per migliorare l'efficienza

nell'accesso “casuale”. Unix solitamente offre dei device a carattere (“raw”)

associati ai device a blocchi, ma Linux non lo fa.

.

• Interfaccie di rete: Le interfaccie di rete non ricadono nell'astrazione del file.

Anche le interfaccie sono identificate da un nome (come eth0 o plip1), ma non

vengono mappate nell'albero dei files. Tale mappatura sarebbe possibile, in teoria,

ma non sarebbe comoda né per il programmatore né per la performance ottenuta:

un'interfaccia di rete può solo trasferire dei pacchetti di dati, e l'astrazione del file in

/dev non gestisce efficientemente il trasferimento di dati strutturati.

Quello che manca nella descrizione fatta finora è che il kernel agisce anche come se fosse

una libreria per i device drivers: i driver possono richiedere servizi al kernel. Un modulo,

per esempio, sarà in grado di chiamare funzioni per l'allocazione di memoria, l'accesso al

filesystem, e così via.

Un modulo è un segmento di codice che si registra all'interno del kernel come device

driver, viene chiamato dal kernel per comunicare con la periferica in questione e a sua

volta invoca altre funzioni del kernel per svolgere il suo compito. I moduli utilizzano

un'interfaccia ben definita tra il kernel vero e proprio e il driver. L'uso di un'interfaccia

precisa semplifica la scrittura di nuovi moduli, e aiuta a tenere più pulito il sorgente del

kernel.

Il modulo deve essere compilato come codice oggetto (senza invocare il linker: deve

essere un file .o), e poi caricato nel kernel corrent tramite il comando insmod. Tale

programma è un “run-time linker”, che risolve i simboli non definiti nel modulo

utilizzando la tabella dei simboli del kernel. Questo vuol dire che un modulo è simile ad un

programma convenzionale in linguaggio C: si possono chiamare funzioni che non vengono

definite, come di solito si chiama printf() e fopen() dall'interno di un programma


65

applicativo. A differenza dei programmi normali, però, si può contare solo su un insieme

minimo di funzioni esterne, che sono poi le funzioni “pubbliche” dichiarate dal kernel.

Il comando insmod metterà i corretti indirizzi del kernel nel codice compilato del modulo

ogni qualvolta il modulo invoca una funzione del kernel, ed inserirà infine il modulo

all'interno del kernel corrente. In caso di dubbi se una funzione del kernel sia pubblica o

no, si può cercare il suo nome nel file /usr/src/linux/kernel/ksyms.c (ma alcune vengono

dichiarate altrove, in particolare nelle versioni più recenti), oppure nella tabella di run-time

in /proc/ksyms. Una buona parte dei meccanismi di base del kernel sono dichiarati nei file

di header sotto forma di macro o funzioni “inline”, soprattutto per quanto riguarda le

primitive di gestione degli accessi concorrenti come semafori, spinlock e operazioni

atomiche. Questo codice, unitamente alle informazioni relative alle strutture dati, viene a

far parte di ogni file oggetto che ne fa uso. Se un file oggetto contiene il codice di un

modulo, esso potrà essere collegato solo con un kernel che usa strutture dati e funzioni

uguali, cioè quello i cui header sono stati usati per compilare il modulo. Inoltre, poiché

alcune strutture dati e alcune funzionalità vengono istanziate in modo diverso a seconda di

come è stato configurato il kernel, un modulo, nella sua forma compilata, può addirittura

essere incompatibile con la stessa versione di kernel, se configurata diversamente.[21]

A questo punto è opportuno mostrare come scrivere correttamente un modulo. Di solito si

inizia il sorgente includendo gli header necessari, e già qui ci troviamo di fronte ad alcuni

vincoli: bisogna sempre definire il simbolo __KERNEL__ prima di includere qualsiasi file,

a meno che tale simbolo non sia già stato definito nel Makefile; inoltre si possono solo

includere header appartenenti alle gerarchie linux/* e asm/*. Certamente si può anche

includere un header specifico del driver in questione, ma non bisogna mai includere dei

files di libreria, come stdio.h o sys/time.h.

Dopo l'inclusione degli header, si arriva al codice vero e proprio. Prima di parlare delle

funzionalità specifiche di un driver (cioè della parte più importante), vale la pena di

sottolineare che esistono due specifiche funzioni che devono essere definite perché un

modulo possa essere caricato nel kernel:

• int init_module (void);

• void cleanup_module (void);


66

La prima funzione si occupa dell'inizializzazione del modulo: ricerca dell'hardware e

registrazione del nuovo driver all'interno delle tabelle del kernel; la seconda ha invece il

compito di rilasciare le risorse usate dal modulo e di cancellare il driver dalle tabelle del

kernel. Se queste funzioni non sono definite, insmod si rifiuta di caricare il modulo.

In figura 4.2 è illustrato come un modulo viene collegato al kernel.

Figura 4.2: Collegamento di un modulo al kernel

La funzione di inizializzazione ritorna zero se va tutto bene e un valore negativo in caso di

errore. La funzione di pulizia ritorna void perché viene solo invocata quando si è sicuri che

il modulo può essere rimosso dal kernel: ogni modulo tiene un contatore di utilizzo, e

cleanup_module() viene solo chiamata quando tale contatore è a zero. I driver a carattere, e

anche quelli a blocchi, devono registrarsi all'interno di un vettore di puntatori del kernel;

questo passo è fondamentale perché un driver possa essere usato. Dopo l'esecuzione di

init_module(), il driver è parte effettiva del kernel, ma non può essere invocato se non ha

reso disponibili le sue funzionalità. Linux, come la maggior parte dei sistemi Unix,

mantiene un array di device drivers, e ciascuno di essi è identificato da un numero,

chiamato “major number”. Tale numero non è altro che l'indice del driver all'interno del


67

vettore di tutti i drivers. L'altro compito importante di init_module() è l'allocazione di tutte

le risorse di cui il driver ha bisogno per operare correttamente. Di solito un driver richiede

memoria, porte di I/O e linee in interrupt [22].

Nel kernel la funzione che si occupa dell'allocazione di memoria è kmalloc() e si usa

esattamente come se fosse malloc(), tranne per il fatto che occorre specificare un secondo

argomento, il cosidetto “allocation flag”. Gli allocation flags più usati sono i seguenti:

• GFP_KERNEL: quando è settato tale flag significa che l'allocazione di memoria

(effettuata internamente chiamando get_free_pages che è il sorgente relativo al

prefisso GFP_ ) è fatta a favore del processo che è in esecuzione nel kernel space.

In altre parole significa che la funzione chiamante sta effettuando una system call a

favore di un processo. Se si usa il suddetto flag significa che la kmalloc() può porre

il processo in esecuzione nello stato di “sleep” in attesa che venga allocata una

pagina di memoria dai meccanismi di gestione della memoria posti ad un livello più

basso.

• GFP_ATOMIC: quando è riportato tale flag significa che ci si aspetta che la

kmalloc() venga chiamata al di fuori del contesto del processo in esecuzione.

Questo tipo di chiamata può avvenire, per esempio, se si hanno gestori delle

interuzioni, code di tasks oppure timers del kernel. Quando GFP_ATOMIC è

usato, kmalloc() può usare anche l'ultima pagina libera e nel caso in cui non ne

trova di disponibili fa fallire l'allocazione.

I flag che possono essere usati come argomenti di kmalloc() sono innumerevoli e sono

definiti in un header del kernel <linux/mm.h>

L'allocazione di porte di I/O, invece è una cosa strana: le porte ci sono e basta usarle,

inoltre il processore non protegge l'uso delle porte tramite segmentazione o altre tecniche.

Il problema qui sta nel fatto che scrivere su porte di I/O relative ad altri dispositivi

potrebbe far cadere il sistema. Linux implementa per le porte la stessa politica che viene

usata per la memoria: L'unica vera differenza sta nel fatto che il processore non genera

della eccezioni in caso di accesso non autorizzato alle porte. La registrazione delle porte,

come quella della memoria, inoltre aiuta il kernel a mantenere pulita la gestione della

macchina [23].


68

4.1.4 Il debugging del modulo

Di fondamentale importanza sono le tecniche ed il supporto per il debugging da utilizzare

nella programmazione dei moduli software. “Supporto per il debugging” di solito significa

la presenza di codice aggiuntivo per stampare messaggi dall'interno del driver. L'uso di

printk() è una scelta funzionale per il debugging, in quanto le alternative sono quella di far

funzionare un debugger sul kernel corrente, monitorare in /dev/mem e altre tecniche

estremamente di basso livello. La funzione printk() è l'equivalente nel kernel space della

funzione printf(), ma per quanto riguarda il suo funzionamento non è esattamente uguale.

Se si desidera un logging meno intrusivo (cioè solo nel file dei messaggi, tramite syslogd),

bisogna far precedere la stringa di formato da KERN_DEBUG. KERN_DEBUG e altri

simboli simili sono stringhe, che vengono concatenate dal compilatore alla stringa di

formato. Questo significa che non bisogna mettere una virgola tra KERN_DEBUG e il

formato della stampa. Tutti questi simboli sono definiti e documentati in linux/kernel.h.

L'altra cosa da ricordare è che printk() non supporta la stampa di valori in virgola mobile,

che non si usano all'interno del kernel. Bisogna ricordare che syslogd scrive sul file dei

messaggi il più presto possibile, al fine di salvare i messaggi su disco in caso di imminente

caduta del sistema. Questo significa che un modulo contentente troppe chiamate a printk()

sarà decisamente più lento, e riempirà velocemente il disco.

Quasi tutti gli errori dei moduli causano la generazione di un messaggio di “Oops”. Un

“Oops” è la risposta del kernel ad una eccezione generata dal kernel stesso. In altre parole,

gli “Oops” sono l'equivalente dei “Segmentation Fault” nelle applicazioni, ma senza

generare un core file. Di solito un “Oops” causa la distruzione immediata del processo nel

cui contesto è avvenuto l'errore, unitamente alla stampa di alcune linee di informazione di

basso livello nel file dei messaggi (e sulla console). La maggior parte degli “Oops” sono

causati dall'utilizzo di puntatori nulli.

Questa maniera di gestire i disastri è abbastanza amichevole: quasi tutte le altre vesioni di

Unix in questi casi si piantano generando un “kernel panic”. Questo non vuol dire che

Linux non si pianta mai; bisogna aspettarsi di piantare il sistema quando ci sono errori

nelle funzioni che operano al di fuori del contesto di un processo, come durante la gestione

di interrupt e nelle azioni controllate dal timer di sistema.


69

L'informazione limitata, e quasi incomprensibile, che viene inclusa nel messaggio di

“Oops” rappresenta lo stato del processore al momento dell'errore, e può essere usata per

capire dove stia l'errore. Esiste uno strumento chiamato “ksymoops”, che è in grado di

stampare informazioni più leggibili del messaggio di “Oops” stesso, a patto di avere una

mappa del sistema a portata di mano: la mappa è quello che rimane in

/usr/src/linux/System.map dopo una compilazione del kernel. Se si capisce davvero il

contenuto di un “Oops”, si può usarlo come si vuole, per esempio chiamando “gdb”

automaticamente per disassemblare la funzione responsabile dell'errore. Se invece non si

capisce né l'“Oops” né l'output di “ksymoops”, conviene aggiungere qualche printk al

codice, ricompilare e riprodurre l'errore.[23]


70

4.2 Il modulo queue_mgr.o

4.2.1 Le strutture dati

Come illustrato nei capitoli precedenti il modulo queue_mgr deve gestire varie strutture

dati per implementare la politica di scheduling. La prima struttura dati che è riportata di

seguito è la _scheduler_data.

struct _scheduler_data{

struct sk_buff_head queues[NQUEUE];

u32 cw[NQUEUE];

u32 timer[NQUEUE];

u32 dropped[NQUEUE];

spinlock_t queue_size_lock;

spinlock_t access_to_scheduler;

u32 queue_size[NQUEUE];

struct sk_buff *skb;

#ifdef QUEUE_MGR_SIZE

unsigned long size[NQUEUE];

#endif

struct _scheduler_data *scheduler_data;

struct tq_struct *scheduler_task;

};

Tale struttura, già presente nel modulo Hostqs, originale è utilizzata dallo schedulatore per

tener memoria dello stato della trasmissione, infatti nella struttura sono riportati il numero

di code, la lunghezza di ogni coda, le dimensioni delle finestre di trasmissione, i vari

timeouts, la struttura skbuff del kernel, che illustreremo in seguito, e i meccanismi di

accesso alle code e allo schedulatore.


71

Il modulo queue_mgr che si è modificato, ha tra le proprie prerogative quella di caricare in

memoria la tabella hostqs. La struttura introdotta nella modifica è un hash table, tale scelta

è stata effettuata per diversi motivi: le tabelle hash sono strutture dati che permettono di

memorizzare arbitrari insiemi di oggetti, fornendo un accesso molto efficiente agli

elementi memorizzati. Supportano un insieme ristretto di metodi, quali inserzione, ricerca,

cancellazione. Godono delle seguenti proprietà:

1. riescono ad avere un tempo medio di accesso costante che le rende veloci in pratica;

2. il costo nel caso pessimo è lineare, ma questo è un evento altamente improbabile;

3. i relativi metodi sono semplici da programmare;

4. non richiedono che sugli oggetti memorizzati sia definito un ordinamento totale;

5. non utilizzano algoritmi ricorsivi.

La struttura di hash table utilizzata è del tipo array di liste a puntatori, dove ogni elemento

della lista riporta le informazioni sul MAC address e QoS di un singolo utente, ovvero

memorizza una singola riga della tabella hostqs. L’implementazione della struttura dati è

riportata di seguito :

typedef struct _list_t_ { //linked list

unsigned char *mac;

unsigned int qos;

struct _list_t_ *next;

} list_t;

typedef struct _hash_table_t_ {

int size; /* dimensione della tabella*/

list_t **table; /* elementi della tabella */

} hash_table_t;


72

La struttura più ampiamente utilizzata in questo modulo è una struttura interna del kernel

appartenente all’ interfaccia di rete [24].

struct sk_buff { /* These two members must be first. */ struct sk_buff *next; struct sk_buff *prev; struct sk_buff_head *list; struct sock *sk; struct timeval stamp; struct net_device *dev; struct net_device *real_dev; union { struct tcphdr *th; struct udphdr *uh; struct icmphdr *icmph; struct igmphdr *igmph; struct iphdr *ipiph; struct ipv6hdr *ipv6h; unsigned char *raw; } h; union { struct iphdr *iph; struct ipv6hdr *ipv6h; struct arphdr *arph; unsigned char *raw; } nh; union { struct ethhdr *ethernet; unsigned char *raw; } mac; struct dst_entry *dst; struct sec_path *sp; char cb[48]; unsigned int len, data_len, mac_len, csum; . . . . . . . . . . atomic_t users; unsigned char *head, *data, *tail, *end; };

Tutte le comunicazioni fra gli strati dello stack di rete, sono eseguite passando singole strutture

skbuff, che contengono un insieme di puntatori in una singola area di memoria continua, che

rappresenta un buffer dentro al quale i pacchetti di rete possono essere costruiti. I dati validi in

un skbuff non necessitano di cominciare all'inizio del buffer dello skbuff e non devono

necessariamente andare fino alla fine. Il codice di rete può aggiungere o togliere dati da


73

entrambi gli estremi del pacchetto, sin tanto che il risultato può ancora essere contenuto in uno

skbuff. Questa possibilità è particolarmente importante sui microprocessori moderni dove

gli aumenti di velocità della CPU hanno ampiamente superato le prestazioni della memoria

centrale: l'architettura dello skbuff permette flessibilità nella manipolazione degli header e

dei checksum dei pacchetti, evitando ogni copia dei dati non necessaria.[24]

L’altra struttura d’interesse è la struttura dei files [24] e contiene, tra le altre informazioni,

il modo con cui il file è stato aperto (f_mod), la posizione all’interno del file alla quale si

sta operando (f_pos), il puntatore all’inode del file (f_inode), il puntatore alle operazioni

per il dispositivo al quale il file appartiene (f_op):

struct file {

union {

struct list_head fu_list;

struct rcu_head fu_rcuhead;

} f_u;

struct dentry *f_dentry;

struct vfsmount *f_vfsmnt;

const struct file_operations *f_op;

atomic_t f_count;

unsigned int f_flags;

mode_t f_mode;

loff_t f_pos;

struct fown_struct f_owner;

unsigned int f_uid, f_gid;

struct file_ra_state f_ra;

unsigned long f_version;

void *f_security;

void *private_data;

. . . . . . . . . . . . . . . . . . . . . . . . . . .

};

La variabile f_op è un puntatore alla struttura file_operations. Tale struttura e' una “jump

table” (una serie di puntatori a funzione), e ogni campo della struttura si riferisce ad una

delle possibili operazioni che vengono effettuate su un file (open(), read(), ioctl() eccetera).

Di seguito è riportata parte della suddetta struttura:

struct file_operations {

struct module *owner;


74

loff_t (*llseek) (struct file *, loff_t, int);

ssize_t (*read) (struct file *, char __user *, size_t, loff_t );

ssize_t (*aio_read) (struct kiocb *, char __user *, size_t,loff_t);

ssize_t (*write) (struct file *, const char __user *,

size_t,loff_t );

ssize_t (*aio_write) (struct kiocb *, const char __user *, size_t,

loff_t);

int (*readdir) (struct file *, void *, filldir_t);

unsigned int (*poll) (struct file *, struct poll_table_struct *);

int (*ioctl) (struct inode *, struct file *, unsigned int,

unsigned long);

long (*unlocked_ioctl) (struct file *, unsigned int,unsigned long);

long (*compat_ioctl) (struct file *, unsigned int, unsigned long);

int (*mmap) (struct file *, struct vm_area_struct *);

int (*open) (struct inode *, struct file *);

int (*flush) (struct file *);

int (*release) (struct inode *, struct file *);

int (*fsync) (struct file *, struct dentry *, int datasync);

int (*aio_fsync) (struct kiocb *, int datasync);

int (*fasync) (int, struct file *, int);

int (*lock) (struct file *, int, struct file_lock *);

ssize_t (*readv) (struct file *, const struct iovec *,unsigned

long, loff_t *);

ssize_t (*writev) (struct file *, const struct iovec *,unsigned

long, loff_t *);

ssize_t (*sendfile) (struct file *, loff_t *, size_t, read_actor_t,

void *);

ssize_t (*sendpage) (struct file *, struct page *, int, size_t,

loff_t *, int);

unsigned long (*get_unmapped_area)(struct file *, unsigned long,

unsigned long, unsigned long, unsigned long);

int (*check_flags)(int);

int (*dir_notify)(struct file *filp, unsigned long arg);

int (*flock) (struct file *, int, struct file_lock *);

};


75

4.2.2 Le funzioni del modulo

Di seguito sono riportate le dichiarazioni delle funzioni utilizzate nel modulo, illustrandone

le principali funzioni.

int start_xmit (struct sk_buff *skb, struct net_device *dev)

hash_table_t * load_table (const char *fread)

hash_table_t * create_hash_table (int size)

unsigned int hash (hash_table_t *hashtable, unsigned char *mac)

list_t * lookup_row (hash_table_t *hashtable, unsigned char *mac)

int add_row (hash_table_t *hashtable, unsigned char *mac, unsigned int qos)

void free_table (hash_table_t *hashtable)

unsigned int htoi (char s[])

int hexalpha_to_int (int c)

void from_call_back_driver (void)

void queue_up_skb (struct sk_buff *skb, struct net_device *dev)

void scheduler (void *ptr)

int init_module ()

void cleanup_module ()

La funzione start_xmit() è utilizzata dal modulo quando c’è una frame da trasmettere. Se il

canale di trasmissione rigetta la frame per motivi di flow-control allora la funziona ritorna

il valore “0” e si deve ritentare la trasmissione, altrimenti in caso di successo ritorna il

valore “1”.

La funzione load_table(), sviluppata in questo lavoro di tesi, ha il compito di caricare le

informazioni contenute nel file hostqs

In una tabella dinamica implementata come un hash table. Se il caricamento riesce ritorna

la tabella popolata altrimenti assegna alla tabella un valore nullo.

Le funzioni create_hash_table(), hash(), lookup_row(), add_row(), free_table(), anch’esse

introdotte in questo lavoro, gestiscono la tabella dinamica effettuando le operazioni di

inserimento cancellazione e ricerca secondo la tecnica che basa il calcolo dell’indice di

hash secondo l’algoritmo di Corner.


76

Si è resa necessaria anche l’introduzione della funzione htoi(), supportata dalla funzione

hexalpha_to_it(), utilizzata trasformare il MAC address memorizzato nel file hostqs dalla

tradizionale notazione esadecimale in una stringa di sei unsigned char, che è il metodo di

memorizzazione di tali indirizzi da parte del kernel.

La funzione from_call_back_driver() si occupa dell’innesto del modulo nel sistema. In

effetti non è implementata come funzione ma nel modulo è riportata la sua sequenza di

codice. Non ne viene approfondita l’implementazione poiché tale trattazione esula dal

presente lavoro di tesi.

Le funzioni queue_up_skb(), scheduler() si occupano della schedulazione vera e propria

classificando la prima il tipo di pacchetti ed assegnandoli la priorità, la seconda invece

gestendo la schedulazione e quindi la tecnica di trasmissione.

Infine, come per ogni modulo sono presenti le funzioni init_module() e cleanup_module()

che si occupano del caricamento e rimozione del modulo.

4.2.3 Lo schema di funzionamento

Come descritto in precedenza quando si carica il modulo nel kernel con il comando

insmod, esso non farà altro che richiamare la funzione init_module(). È utile a questo punto

studiare il comportamento di tale funzione o meglio vedere i passi elaborativi che compie

ed il risultato finale quando finisce la sua esecuzione. Per meglio affrontare questa analisi è

utile osservare il Call Graph [25] relativo ad essa illustrato in figura 4.3:

Figura 4.3 Call Graph della funzione init_module()


77

La funzione init_module() effettua quattro operazioni fondamentali, la prima di queste è

l’innesto nel kernel effettuato con la funzione from_callback_driver( ) e l’innesto nel

modulo Hostap :

/* inizializzazione collegamento col driver*/

queue_mgr_new_skb = queue_up_skb; /* innesto in hostap*/

pointer_to_driver = from_call_back_driver; /innesto nel kernel */

atomic_set(&queue_mgr_present,1);

Osservando la figura 4.4 si capisce che si è andato a posizionare tra il MAC layer del

driver Hostap e il Network layer del kernel.

Figura 4.4 Innesto di queue_mgr nel sistema


78

La seconda operazione che viene effettuata, introdotta in questo lavoro, è il caricamento

del file hostqs nella tabella dinamica. Nel modulo viene dichiarata una variabile globale di

tipo _hash_table_t in modo che possa essere accessibile da tutti i moduli. L’operazione di

inizializzazione è effettuata dalla funzione load_table():

const char *table=kmalloc(20, GFP_ATOMIC);

table="/etc/hostqs";

table_qos=load_table(table); /*carica la tabella */

Oltretutto è interessante analizzare il codice della funzione suddetta per vedere come la

tecnica di accesso ai file nel kernel space è diversa dalla tecnica utilizzata normalmente

nello user space. Mentre quest’ultima può usare le funzioni della libreria standard del C, la

tecnica di programmazione nel kernel space non ha a disposizioni tali funzioni essendo

esse stesse sviluppate a partire dal kernel.

hash_table_t *load_table (const char *fread )

{

int length_read,ins,h,i;

unsigned int qos;

char c[2], buffer[20];

unsigned char *mac=kmalloc(ETH_ALEN,GFP_ATOMIC);

hash_table_t *qos_hash_table;

int size_of_table = 255;

struct file * table = NULL;

mm_segment_t orig_fs;

qos_hash_table = create_hash_table(size_of_table);

table = filp_open(fread, O_RDONLY, 00);

if (!table || !table->f_op || !table->f_op->read)

{

printk("WARNING: File object is a null pointer!!!\n");

}

printk("g\n");

table->f_pos = 0;

orig_fs = get_fs();

set_fs(KERNEL_DS);


79

while ((length_read = table->f_op->read(table, buffer,

sizeof(buffer), &table->f_pos)) >0)

{

h=0;

i=0;

while(i<sizeof(buffer)-4)

{

c[0]=buffer[i];

c[1]=buffer[i+1];

i=i+3;

mac[h]=htoi(c);

h++;

}

qos=(unsigned int) buffer[18]-'0';

ins = add_row(qos_hash_table,mac,qos);

}

/* Rilascia il file pointer. */

put_filp(table);

return qos_hash_table;

}

Si può notare come l’accesso al file è regolato dalla struttura file presentata

precedentemente. Dopo aver effettuato l’apertura del file hostqs in sola lettura, le

operazione di lettura compiute sul file vengono effettuate utilizzando il campo f_op della

suddetta struttura che è un puntatore ad una struttura contenente le funzioni che possono

operare sul file. Questo modo di operare è una dei concetti più articolati implementati nella

struttura del kernel ed è un primo approccio alle tecniche di programmazione ad oggetti

che nel kernel sono scarsamente utilizzate. L’accesso al file avviene in modo sequenziale

ed ogni volta che viene effettuata una lettura la funzione f_op->read(), oltre a leggere i dati

che gli sono richiesti, mette all’interno della variabile f_pos la posizione di lettura corrente

del file, in questo modo ad una successiva operazione di lettura la unzione f_op->read()

partirà da dove aveva lasciato.Nella funzione load_table() vengono utilizzate tutte le

funzioni di gestioe dell’hash table nonché le funzioni di conversione del MAC address dal

formato esadecimale a quello di unsigned char. Nella figura 4.5 si mostra il Call Graph

della suddetta funzione.


80

Figura 4.5 Call Graph della funzione load_table()

Un ulteriore sguardo va dato alla funzione create_hash_table() poiché in tale funzione è

chiaramente osservabile l’utilizzo della funzione kmalloc() per l’allocazione della memoria

nel kernel space

hash_table_t *create_hash_table(int size)

{

hash_table_t *new_table;

int i;

if (size<1) return NULL; /* invalid size for table */

/* Attempt to allocate memory for the table structure */

new_table = kmalloc(sizeof(hash_table_t),GFP_ATOMIC);

if(new_table == NULL)

return NULL;

/* Attempt to allocate memory for the table itself */

new_table->table = kmalloc(sizeof(list_t *) * size,GFP_ATOMIC);

if (new_table->table==NULL)

return NULL;

/* Initialize the elements of the table */

for(i=0; i<size; i++) new_table->table[i] = NULL;

/* Set the table's size */

new_table->size = size;

return new_table;

}


81

Si può notare come il secondo argomento della kmalloc() sia il flag GFP_ATOMIC .Tale

flag viene usato oltre per il fatto che stiamo lavorando in kernel space ma anche per

velocizzare l’assegnamento da parte del sistema di memoria libera.

La funzione fondamentale in questo modulo è svolta dalla funzione queue_up_skb(). Essa

ha il compito di filtrare i pacchetti che riceve dallo strato di rete e di assegnare la QoS ad

ogni pacchetto. Tale funzione presente nel modulo queue_mgr originale è stata modificata

nella parte relativa alla lettura delle informazioni dalla struttura skbuff (il buffer di rete del

kernel), implementando la lettura del MAC address del destinatario e utilizzando la

funzione di ricerca nell’hash table lookup_row per verificare la presenza o meno del MAC

in tabella, procedendo poi all’assegnazione del valore di QoS.

Di seguito sono riportati alcuni frammenti di codice della suddetta funzione con le

modifiche apportate evidenziate in rosso.

void queue_up_skb(struct sk_buff *skb, struct net_device *dev)

{

int queue,qos;

//unsigned char *dest_add;

list_t *riga=NULL;

#ifdef QUEUE_MGR_DEBUG

#endif

if(skb!=NULL)

{

skb->dev=dev;

/*verifica se è un header ip */

if(*((u16 *)(skb->data + 12)) != __constant_htons(ETH_P_IP))

{

/* non IP frame are sent with max priority */

atomic_inc(&queue_mgr_pkt_cnt);

if(start_xmit(skb,dev)!=0)

{

atomic_dec(&queue_mgr_pkt_cnt);

}

queue = -1;

}


82

else if(*((u16 *)(skb->data +12))==__constant_htons(ETH_P_CONTROL))

/* Card specific control frames (campo type frame ethernet) */

{



{


}

queue = -1;

}

else

{

riga=lookup_row(table_qos,skb->data);

printk("\n riga->qos: %u",riga->qos);

if (riga!=NULL)

qos=riga->qos;

else

qos=0;

switch (qos)

{

case 0: queue=0; break;



case 3:



{


}

queue = -1;

break;

}

. . . . . . . . . . . . . . . . . . . . .

La funzione analizza l’header file del pacchetto ricevuto, se il pacchetto non è un

pacchetto IP (ma è bensì un pacchetto di controllo o di scoperta della rete) viene mandato

con la massima priorità, altrimenti viene letto l’indirizzo MAC del destinatario.A questo


83

punto viene controllato se esso è presente in tabella, se lo è viene assegnato alla coda

rappresentativa del proprio QoS, altrimenti gli viene assegnata priorità minima.

Il numero di code sono come visto in precedenza quattro, o meglio sono implementate solo

tre code mentre i pacchetti urgenti non si fermano in coda bensì passano direttamente allo

strato di rete inferiore. Tale meccanismo nel codice è gestito dal costrutto case presente.

Dopo che è stata effettuata la classificazione dei pacchetti viene invocato la funzione

scheduler() che si occupa di gestire la trasmissione. L’implementazione della suddetta

funzione non cambia rispetto al progetto hostqs originario.Quando il modulo non è più

necessario esso può essere rimosso e per fare ciò il comando rmmod che si occupa della

procedura di rimozione invoca la funzione cleanup_module() all’interno del modulo.

Figura 4.6 Call Graph della funzione cleanup_module()

Anche tale funzione ha dovuto subire delle modifiche rispetto al modulo queue_mgr

originale, essendosi resa necessaria l’introduzione della funzione free_table(), la quale

libera la memoria allocata in precedenza da create_hash_table(). Dopo aver liberato la

memoria dedicata all’hash table la cleanup_module() e rilascia le risorse allocate dalla

struttura _scheduler_data.

Di seguito è riportato l’implementazione realizzata della funzione free_table() nella quale

si usa la funzione kfree() che è l’analoga nel kernel space della funzione free(). Essa

dealloca la memoria riservata alle strutture dati da kmalloc().

void free_table(hash_table_t *hashtable)

{

int i;


84

list_t *list, *temp;

if (hashtable==NULL) return;

for(i=0; i<hashtable->size; i++) {

list = hashtable->table[i];

while(list!=NULL) {

temp = list;

list = list->next;

kfree(temp->mac);

kfree(temp);

}

}

kfree(hashtable->table);

kfree(hashtable);

}


85

Capitolo 5 Le misure sperimentali

Il presente capitolo mostra i risultati sperimentali ottenuti operando varie misure sul

sistema. È stato allestito un “testbed ad hoc” per testare la capacità reale di schedulazione

del modulo realizzato. Sono state effettuate dapprima misure di potenza sulla scheda in

modalità Hostap, in modo da poter valutare la dimensione massima e minima di una

singola cella wireless (si è voluto vedere la copertura dalla scheda). Successivamente sono

state effettuate misure sulla scheda wireless in modalità Hostap su cui è stato innestato il

modulo Hostqs originale in modo da poter valutare l’effettivo funzionamento dello

scheduler in esso implementato. L’ultima campagna di misurazione è stata effettuata sul

modulo Hostqs qui modificato in modo da valutare l’effettiva schedulazione dei pacchetti

in base all’indirizzo MAC del destinatario.

Alla fine sono riportate le conclusioni tratte dal presente lavoro di tesi e le possibili

evoluzioni e sviluppi futuri.


86

5.1 Il testbed

Il testbed installato ha il compito di ricreare un ambiente in cui utenti mobili richiedono

servizi alla rete wired LAN attraverso l’Access Point. Il testbed è composto da quattro

macchine, due collegate tra loro attraverso rete LAN tradizionale e una di esse che funge da

Access Point è collegato alle altre due macchine attraverso una Wireless LAN del tipo

802.11b. Di seguito sono riportate le caratteristiche tecniche dei componenti del testbed.

Il dispositivo che funge da Access Point è stato realizzato con un sistema Embedded

Barebone dotato di scheda wireless dotata di chipset PrismII, con le seguenti

caratteristiche tecniche:

• Processore VIA C3 ad 1GHz Fanless

• 512 Mbyte Ram e 40 Gbyte di HDD

• Scheda wireless Compaq WL100 con chipset PrismII

• Sistema Operativo Slackware Linux 10.1 con kernel 2.4.29 [26]

• Modulo Hostap + Hostqs [14] [15] e Hostqs modificato

Il dispositivo collegato all’AP attraverso la wired LAN funge da generatore di traffico ed è

anch’esso un dispositivo Embedded Barebone con le stesse caratteristiche hardware del

precedente ma con diverso sistema software, infatti esso ha le seguenti caratteristiche

tecniche:

• Processore VIA C3 ad 1GHz Fanless

• 512 Mbyte Ram e 40 Gbyte di HDD

• Sistema Operativo Ubuntu Linux 5.01 con kernel 2.6.9 [27]

• NLANR/DAST Iperf 2.0.1 - The TCP/UDP Bandwidth Measurement Tool[28]

• The Linux Wireless Extension and the Wireless Tools 27 [29]

I sistemi mobile sono due Notebook entrambi dotati del software di misurazione della

Bandwidth e uno di essi anche di un software di misura della potenza trasmessa dall’ AP.

Il primo sistema mobile ha le seguente caratteristiche:


87

• Toshiba Satellite con CPU Pentium III 650 MHz

• RAM 256 Mbyte e HDD con 30 Gbyte

• Sistema Operativo Debian Linux con kernel 2.4.26 [30]

• Scheda wireless PCMCIA Toshiba con chipset ORINOCO



Il secondo sistema mobile invece presenta le seguenti caratteristiche tecniche:

• Asus L3D con CPU Athlon XP-M 2400+

• RAM 512 Mbyte e HDD con 40 Gbyte

• Sistema Operativo Ubuntu Linux 5.01 con kernel 2.6.10 [27]

• Scheda wireless PCMCIA Belkin con driver Windows utilizzati dal software

ndiswrapper [31] [32]



• Software “misure” per la misura di potenza di schede wireless [33]

Il testbed è schematizzato come segue in figura 5.1:

Figura 5.1 Testbed


88

5.2 Le misurazioni

5.2.1 Individuazione della cella minima I test sono stati condotti presso il laboratorio ITEM del CINI (Consorzio Interuniversitario

Nazionale per l’Informatica) di Napoli. In particolare sono state effettuate due campagne di

misurazione, una all’interno della struttura ed una all’esterno. All’interno della struttura

erano presenti interferenze costituite da end-point wireless, dalla centralina elettrica, inoltre

la struttura topologica del laboratorio presenta limiti strutturali che attenuano la potenza del

segnale (pareti divisorie). All’esterno del laboratorio ITEM sono presenti fonti di

interferenza causati dai compressori per i condizionatori d’aria. La figura 5.2 mostra una

piantina rappresentativa dell’interno del laboratorio:

Figura 5.2 Piantina rappresentativa del laboratorio ITeM

Il driver Hostap permette di usare l’opzione delle Wireless Extension che permettono di

regolare la potenza del dispositivo wireless di rete.


89

Le misurazioni sono state fatte facendo variare la potenza trasmissiva della scheda con

chipset PrismII e facendo variare gradualmente la distanza tra i dispositivi. Le misure per

ogni fissato valore di potenza trasmissiva e di distanza tra i dispositivi è stata ripetuta cento

volte in modo da poter considerare un valor medio affidabile della potenza ricevuta dal

dispositivo client.

Consideriamo dapprima le misure di potenza ricevuta effettuate all’intero della struttura.

Nel diagramma 5.1 è riportato la variazione di potenza trasmissiva all’interno dell’edificio

su una distanza di 15 metri e ad una variazione di potenza che va dai 15 dBm ai 0 dBm

mentre nel diagramma 5.2 è riportato il rapporto Segnale-Rumore della stessa misurazione.

valori medi della potenza del segnale all'interno

-80

-70

-60

-50

-40

-30

-20

-10

0

0 0,5 1 1,5 2 2,5 3 3,5 4 4,5 5 5,5 6 6,5 7 7,5 8 8,5 9 9,5 10 10,5 11 11

,5 12 12,5 13 13

,5 14 14,5 15

metri

dBm

15dBm12dBm9dBm6dBm3dBm0dBm

Diagramma 5.1 Variazione della potenza trasmissiva all’interno del laboratorio


90

Rapporto S/N misura interna

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

0 0,5 1 1,5 2 2,5 3 3,5 4 4,5 5 5,5 6 6,5 7 7,5 8 8,5 9 9,5 10 10,5 11 11

,5 12 12,5 13 13

,5 14 14,5 15

metri

S/N

15 dbm12 dbm9 dbm6 dbm3 dbm0 dbm

Diagramma 5.2 Rapporto segnale rumore delle misurazioni all’interno

Come si può osservare al variare della distanza la potenza diminuisce anche se in maniera

oscillante a causa delle interferenze presenti all’interno dell’edificio. Osservando il

diagramma del rapporto S/N si può notare come non si raggiunga mai il valore unitario,

quindi a qualsiasi potenza si setta la scheda wireless si riuscirà sempre a trasmettere.

L’unica cosa che è d’obbligo osservare è come per potenze uguali o inferiori ai 12 dBm il

segnale inizia a perdere chiarezza (S/N>0.5) a distanze superiori ai tre metri.

Sono riportati di seguito le misure effettuate all’esterno del laboratorio. Nel diagramma 5.3

è riportato l’andamento medio della potenza al variare della distanza e della potenza

trasmissiva dell’Access Point, mentre nel diagramma 5.4 è riportato il rapporto S/N.

Per valutare meglio la portata della scheda è stata effettuata anche una misurazione del

throughput medio tra i due dispositivi.

Il traffico generato dal software Iperf in modalità client è di tipo UDP ed è trasmesso ad un

rate pari a 10Mbps. Tale traffico è ricevuto dal secondo dispositivo che partecipa alla

misurazione attraverso il software Iperf in ascolto in modalità server. Nel diagramma 5.5 è

riportata quindi la misura del throughput.


91

potenza_segnale

-160

-140

-120

-100

-80

-60

-40

-20

00 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 34 36 38

metri

DB

m

-15dbm-10dbm-5dbm0dbm5dbm10dbm15dbm

Diagramma 5.3 Variazione della potenza trasmissiva all’esterno del laboratorio

Rapporto Segnale Rumore

0

0,2

0,4

0,6

0,8

1

1,2

1,4

1,6

1,8

0 5 10 15 20 25 30 35 40

metri

S/N


Diagramma 5.4 Rapporto segnale rumore delle misurazioni all’esterno


92

Throughput medio

0

1000

2000

3000

4000

5000

6000

7000

0 5 10 15 20 25 30 35 40

metri

kbits

/sec


Diagramma 5.5 Throughput medio di trasmissione all’esterno

Dai diagrammi riportati è facile ricostruire delle possibili celle di lavoro. All’interno

dell’edificio in pratica non ci sono limiti trasmessivi, l’unico problema è che il segnale ha

dei valori di potenza poco stabili per valori di potenza bassi essendo l’interno ricco di

interferenze. Le misure all’esterno invece individuano una cella massima ed una cella

minima. È d’obbligo chiarire come mai nel diagramma del throughput all’altezza dei 22

metri c’è un picco di trasmissione al ribasso. Tale picco è dovuto alla presenza nel luogo di

misurazione di compressori per condizionatori che generano notevole interferenze. Non è

stato possibile effettuare misure in un altro luogo per problemi logistici.

La cella minima che può coprire l’Access Point ha un raggio pari ai 22 metri per una

potenza di trasmissione della scheda pari a -15dBm come si può osservare dal diagramma

del throughput mentre la cella massima è pari a 36 metri. Infatti nonostante il fatto che per

valori di potenza elevati il rapporto S/N non raggiunge mai il valore unitario, dal

diagramma del throughput si evince che al superamento dei 36 metri si ha un throughput

nullo per qualsiasi valore di potenza di trasmissione dell’AP.


93

5.2.2 Verifica del funzionamento del modulo Hostqs originale Tali misurazioni sono state effettuate nel testbed descritto in precedenza, utilizzando il

software Iperf sulla postazione definita nella figura 5.1 come “Iperf client”.

In realtà su tale macchina sono state lanciate due istanze di Iperf in modalità client ognuna

delle quali genera un traffico pari a 10 Mbps.

Il software Iperf permette di settare il campo ToS di ogni pacchetto IP trasmesso. Anche

in questo caso il traffico generato è di tipo UDP e le misurazioni sono state effettuate su un

intervallo di 120 secondi.

Il modulo Hostqs associa i pacchetti alle code di trasmissione in base al valore del ToS. Le

code implementate sono quattro mentre si possono settare otto valori diversi di ToS, quindi

il sistema associa alla stessa coda due valori di ToS contigui secondo la seguente tabella:

VALORE DEL TOS CODA TRASMISSIVA

0x0 Trasmissione diretta

0x2 Trasmissione diretta

0x4 2 priorità alta

0x6 2 priorità alta

0x8 1 priorità media

0xa 1 priorità media

0xc 0 priorità bassa

0xe 0 priorità bassa

Sono state effettuate misure per tutte le combinazioni di ToS e tutte mostrano il corretto

funzionamento del modulo Hostqs. Di seguito si riportano alcuni diagrammi significativi

che mostrano la differenziazione del traffico al variare del valore di ToS. Per valori uguali

di Tos o appartenenti a classi contigue si sono riscontrate comunque delle variazione di

throughput, questo è dovuto alle differenti capacità prestazionali delle macchine. A parte

questa discrepanza, quando si impone un valore di ToS tale da inviare i pacchetti con ToS

differente in code differenti, il sistema schedula correttamente e così come si può evincere

dai diagrammi.


94

Nei diagrammi 5.6 e 5.7 vengono riportati i valori di throughput di due classi contigue di

traffico ( si consulti la tabella precedentemente riportata), mentre negli altri diagrammi,

fissato un valore di ToS a 0x60 si mette in evidenza la variazione del throughput al variare

degli altri valori di ToS da 0x00 a 0xe0.

0x60_0x60

0

500

1000

1500

2000

2500

3000

3500

4000

4500

1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101

105

109

113

117

secondi

kbps 5001_0x60

5002_0x60

Diagramma 5.6

0x60_0x40

0

500

1000

1500

2000

2500

3000

3500

4000

4500

1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101

105

109

113

117

secondi

kbps 5001_0x60

5002_0x40

Diagramma 5.7


95

Nella Diagramma 5.8 si osserva come il traffico a ToS 0x00 ha un throughput maggiore

del traffico con ToS 0x60.

0x60_0x20

0

1000

2000

3000

4000

5000

6000

1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101

105

109

113

117

secondi

kbps 5001_0x60

5002_0x00

Diagramma 5.8

Nei diagrammi 5.9 e 5.10 si osserva invece come il traffico a ToS pari a 0x80 e 0xe0 ha un

throughput inferiore a quello con ToS pari a 0x60:

0x60_0x80

0

1000

2000

3000

4000

5000

6000

1 6 11 16 21 26 31 36 41 46 51 56 61 66 71 76 81 86 91 96 101 106 111 116

secondi

kbps 5001_0x60

5002_0x80

Diagramma 5.9


96

ox60_0xe0

0

1000

2000

3000

4000

5000

6000

1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101

105

109

113

117

121

secondi

kbps 5001_0x60

5002_0xe0

Diagramma 5.10


97

5.2.3 Verifica del funzionamento del modulo Hostqs modificato A questo punto si riportano i risultati delle misurazioni del modulo Hostap modificato.

Per ogni misurazione vengono modificati i valori di QoS assegnati alle schede wireless

registrate. In particolare sono state registrate solo le due schede facenti parte del testbed.

Per il resto la tecnica di misurazione adottata è analoga alla precedente. Sono riportati i

diagrammi che riportano i valori di jitter oltre ai diagrammi del throughput. L’associazione

dei pacchetti alle code avviene secondo lo schema riportato nella seguente tabella:

QOS CODA

0 0 bassa priorità

1 1 media priorità

2 2 alta priorità

Pacchetti di servizio Trasmissione diretta

Nei diagrammi successivi si può osservare come il modulo osserva correttamente tale

tabella effettuando bene il meccanismo a priorità di trasmissione dei pacchetti.

Throughput_10Mbps_2x0

0

1000

2000

3000

4000

5000

6000

1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101

105

109

113

117

Secondi

Kbp

s belkin_qos_2orinoco_qos_0

Diagramma 5.11


98


0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101

105

109

113

117

Secondi

Kbp

s orinoco_qos_1belkin_qos_1

Diagramma 5.0-32


0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101

105

109

113

117

secondi

Kbp

s orinoco_qos_0belkin_qos_1

Diagramma 5.13

Relativamente ai diagrammi sopra riportati si inseriscono i diagrammi che riportano lo

jitter delle stesse misurazioni. Come era prevedibile per throughput più elevati si osservano

valori di jitter minori.


99

Jitter_10Mbps_2x0

0

2

4

6

8

10

12

14

16

18

20

1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101

105

109

113

117

Secondi

Mill

isec

.

belkin_qos_2orinoco_qos_0

Diagramma 5.14

Jitter_10Mbps_1x1

0

2

4

6

8

10

12

1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101

105

109

113

117

Secondi

Mill

isec

.


Diagramma 5.15


100

Jitter_10Mbps_0x1

0

1

2

3

4

5

6

7

8

9

10

1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101

105

109

113

117

Secondi

Mill

isec

.


Diagramma 5.16


101

5.3 Conclusioni e sviluppo futuro

Il presente lavoro di tesi ha cercato di implementare una politica di QoS su una tecnologia

di rete esistente come la 802.11b seguendo le direttive della bozza dell’imminente standard

802.11e, oltretutto si è tentato di descrivere la struttura logica di tutto il sistema di

trasmissione. Infatti l’obiettivo di tale lavoro di tesi è stato quello di dimensionare la cella

in cui lavora la scheda wireless che funge da AP in modo tale che si potesse conoscere

l’area effettiva di copertura, progettare una architettura di rete che permettesse l’accesso

alla rete agli utenti, fornendogli una connessione indipendente dai dispositivi usati grazie

all’utilizzo di un embedded badge che contiene la chiave di accesso alla rete, ed infine

progettare e sviluppare un modulo software, in particolare un modulo del kernel linux che

operi una schedulazione dei pacchetti ricevuti. Tale modulo schedala i pacchetti e li

assegna a coide di trasmissione con priorità differenti.

Effettivamente tale schedulazione software ha avuto un buon risultato, osservando le

misurazioni effettuate, e la tecnologia Hostap permette di trasformare una qualsiasi scheda

Wireless PCMCIA in un AP potendo così estendere in maniera poco costosa i nodi

wireless.

Un successivo sviluppo di tale lavoro sarà l'implementazione di tutta l'architettura di

autenticazione e accesso al nodo wireless in cui queue_mgr lavora. Bisognerà sviluppare il

meccanismo di comunicazione tra utente mobile e sistema per effettuare l'autenticazione

iniziale, in particolare l’embedded badge e la comunicazione bluetooth, oltretutto

bisognerà sviluppare il gestore degli accessi che andrà a popolare il file hostqs, che viene

utilizzato dal modulo queue_mgr per fornire la QoS, e l'archivio in cui il gestore degli

accessi verificherà se un utente avrà o non la facoltà di accedere alla rete.


102

Appendice A Il codice del software sviluppato

A.1 L’header file queue_mgr.h /* queue_mgr.h Copyright (C) 2004 by Stefano Annese, Luca Seoli CSP http://www.csp.it Politecnico di Torino - Networks Group http://www.tlc-networks.polito.it This file is part of Queue Manager. Queue Manager is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. See README and COPYING for more details. Queue Manager is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Queue Manager; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #include <linux/if_ether.h> /* Definizioni delle costanti per Ethernet IEEE 802.3 interface. */ #ifndef QUEUE_MGR #define QUEUE_MGR #define QUEUE_MGR_VER "1.0.0" #define ALPHA 4/* = 1/(CAMPIONI in MEMORIA) * ORDINE */ #define ORDINE 100


103

#define MIN_DLC_LEN 24 /* 4 di ctrl, 6+6+6 di indirizzi, 2 di seq ctrl */ #define De6 1000000 /* 10e6 */ #define RATE 1250000 /*Byte/sec*/ #define THRESHOLD 3 #define QUEUE_TRESHOLD 4000 #define MAX_CW 1024 #define SLEEP_ON_TX 1 #define SLEEP_ON_EMPTY_QUEUE 2 #define SLEEP_ON_FULL_QUEUE 3 #define NQUEUE 3 u32 default_min_cw[] = {31,15,3}; u32 default_max_cw[] = {1023,255,7}; u32 max_queue_size[] = {400000,400000,50000}; struct _scheduler_data{ struct sk_buff_head queues[NQUEUE]; u32 cw[NQUEUE]; u32 timer[NQUEUE]; u32 dropped[NQUEUE]; spinlock_t queue_size_lock; spinlock_t access_to_scheduler; u32 queue_size[NQUEUE]; struct sk_buff *skb; #ifdef QUEUE_MGR_SIZE unsigned long size[NQUEUE]; #endif struct _scheduler_data *scheduler_data; struct tq_struct *scheduler_task; }; /* definizione della struttura di albero in cui viene memorizzata la tabella di qos */ enum Tag_Bool {FALSE = 0, TRUE =1}; typedef enum Tag_Bool Boolean; typedef struct _list_t_ { //linked list unsigned char *mac; unsigned int qos; struct _list_t_ *next; } list_t; typedef struct _hash_table_t_ { int size; /* dimensione della tabella*/ list_t **table; /* elementi della tabella */ } hash_table_t; #endif


104

A.2 Il file queue_mgr.c /* queue_mgr.c Copyright (C) 2004 by Stefano Annese, Luca Seoli CSP http://www.csp.it Politecnico di Torino - Networks Group http://www.tlc-networks.polito.it This file is part of Queue Manager. Queue Manager is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. See README and COPYING for more details. Queue Manager is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Queue Manager; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #define QUEUE_MGR_SIZE /* #define QUEUE_MGR_DEBUG */ /* Standard in kernel modules */ #ifndef EXPORT_SYMTAB #define EXPORT_SYMTAB #endif #include <linux/kernel.h> #include <linux/module.h> #include <linux/skbuff.h> #include <linux/timer.h> #include <linux/spinlock.h> #include <linux/version.h> #include <linux/if_ether.h> #include <linux/tqueue.h>


105

#include <linux/delay.h> #include <linux/interrupt.h> #include <linux/netdevice.h> #include <linux/random.h> #include <linux/time.h> /* inizio modifica gianf */ #include <stdio.h> //#include <string.h> #include <linux/file.h> #ifndef ENOENT #include <linux/errno.h> #endif /*fine modifica gianf */ /* Deal with CONFIG_MODVERSIONS */ #if CONFIG_MODVERSIONS==1 #define MODVERSIONS #include <linux/modversions.h> #endif /* In 2.2.3 /usr/include/linux/version.h includes a * macro for this, but 2.0.35 doesn't - so I add it * here if necessary. */ #ifndef KERNEL_VERSION #define KERNEL_VERSION(a,b,c) ((a)*65536+(b)*256+(c)) #endif #if LINUX_VERSION_CODE >= KERNEL_VERSION(2,2,0) #include <asm/uaccess.h> #endif /* #include "hostap_h/hostap_wlan.h" */ #include "queue_mgr.h" #define DEBUG_2 #define TRUE 1 #define FALSE 0 #define HWADDR(addr)\ ((unsigned char *)&addr)[0], \ ((unsigned char *)&addr)[1], \ ((unsigned char *)&addr)[2], \ ((unsigned char *)&addr)[3], \ ((unsigned char *)&addr)[4], \ ((unsigned char *)&addr)[5] #define IP_TOTAL_LENGHT(ptr) \ ((u16)*(ptr + ETH_HLEN + 2)<<8 | (u16)*(ptr + ETH_HLEN + 3)) #define TX_COMPLETE_WAIT_DELAY 10 /* us */ static struct _scheduler_data *scheduler_data; static atomic_t stop_scheduling; static int go_scheduling; static hash_table_t *table_qos; /* tabella dinamica da creare in memoria */ extern void (*pointer_to_driver)(void); extern int start_xmit(struct sk_buff *skb, struct net_device *dev); extern void (*queue_mgr_new_skb)(struct sk_buff *, struct net_device *);


106

extern atomic_t queue_mgr_present; extern atomic_t queue_mgr_pkt_cnt; extern wait_queue_head_t hostap4queue_mgr_wait_q; /*definizioni delle funzioni che operano sulla struttura dinamica (albero binario) che memorizza la tabella */ extern hash_table_t *load_table (const char *fread); /*caricamento della tabella da parte del modulo */ extern hash_table_t *create_hash_table(int size); extern unsigned int hash(hash_table_t *hashtable, unsigned char *mac); extern list_t *lookup_row(hash_table_t *hashtable, unsigned char *mac); extern int add_row(hash_table_t *hashtable, unsigned char *mac,unsigned int qos); extern void free_table(hash_table_t *hashtable); extern unsigned int htoi(char s[]); extern int hexalpha_to_int(int c); // extern int delete_row(hash_table_t *hashtable, unsigned char *mac); attualmente non usata /* fine delle definizioni della struttura dinamica */ MODULE_AUTHOR("CSP, Stefano Annese & Luca Seoli"); MODULE_DESCRIPTION("Support for QoS extension for " "Intersil Prism2-based 802.11 wireless LAN " "cards (PC Card) Hostap driver" "Aironet PC 4800 "); MODULE_SUPPORTED_DEVICE("Intersil Prism2-based WLAN cards (PC Card), Aironet PC 4800"); #ifdef MODULE_LICENSE MODULE_LICENSE("GPL"); #endif u32 loops, start_time; void from_call_back_driver(void) { spin_lock(&scheduler_data->access_to_scheduler); if(go_scheduling==2) { queue_task(scheduler_data->scheduler_task, &tq_immediate); mark_bh(IMMEDIATE_BH); } spin_unlock(&scheduler_data->access_to_scheduler); return; } void queue_up_skb(struct sk_buff *skb, struct net_device *dev) { printk(KERN_DEBUG"\nInizio queue_up_skb"); int queue,qos; //unsigned char *dest_add; list_t *riga=NULL;


107

#ifdef QUEUE_MGR_DEBUG printk(KERN_DEBUG "queue_up_skb\n"); #endif if(skb!=NULL) { printk(KERN_DEBUG"\n primo if"); skb->dev=dev; if(*((u16 *)(skb->data + 12)) != __constant_htons(ETH_P_IP)) //verifica se Ã¨ un header ip { printk(KERN_DEBUG"\n secondo if"); /* non IP frame are sent with max priority */ atomic_inc(&queue_mgr_pkt_cnt); if(start_xmit(skb,dev)!=0) { atomic_dec(&queue_mgr_pkt_cnt); } queue = -1; } else if (*((u16 *)(skb->data + 12)) == __constant_htons(ETH_P_CONTROL)) /* Card specific control frames (campo type frame ethernet) */ { printk(KERN_DEBUG"\n else if"); atomic_inc(&queue_mgr_pkt_cnt); if(start_xmit(skb,dev)!=0) { atomic_dec(&queue_mgr_pkt_cnt); } queue = -1; } else { printk(KERN_DEBUG"\n else modificato"); /* Inizio modifica*/ riga=lookup_row(table_qos,skb->data); printk("\n riga->qos: %u",riga->qos); if (riga!=NULL) qos=riga->qos; else qos=0; printk(KERN_DEBUG"\n prima del case"); switch (qos) { case 0: queue=0; break; case 1: queue=0; break; case 2: queue=1; break; case 3: queue=1; break; case 4: queue=2; break; case 5: queue=2; break; case 6: case 7: atomic_inc(&queue_mgr_pkt_cnt); if(start_xmit(skb,dev)!=0) { atomic_dec(&queue_mgr_pkt_cnt); }


108

queue = -1; break; } /* fine modifica */ printk(KERN_DEBUG"\n dopo del case"); } if (queue >=0) { if (scheduler_data->queue_size[queue] < max_queue_size[queue]) { spin_lock(&scheduler_data->queue_size_lock); scheduler_data->queue_size[queue] += skb->len; spin_unlock(&scheduler_data->queue_size_lock); skb_queue_tail(&(scheduler_data->queues[queue]),skb); } else { dev_kfree_skb(skb); scheduler_data->dropped[queue]++; } spin_lock(&scheduler_data->access_to_scheduler); if(( go_scheduling == 0 )&&( go_scheduling != 2 )) { go_scheduling = 1; queue_task(scheduler_data->scheduler_task, &tq_immediate); mark_bh(IMMEDIATE_BH); } spin_unlock(&scheduler_data->access_to_scheduler); } } } void scheduler(void *ptr) { struct _scheduler_data *scheduler_data; u16 i,aux; u8 is_pkt2send = FALSE; u8 min_index[NQUEUE], collision; static u8 collision_solver=0; u16 min_timer, random_timer; loops ++; #ifdef QUEUE_MGR_SIZE static unsigned long time = 0; #endif if(ptr!=NULL) { scheduler_data = (struct _scheduler_data *)ptr; #ifdef QUEUE_MGR_SIZE /* queue size dimensions exponential smoothing */ for(i=0; i<NQUEUE; i++) { if (scheduler_data->queues[i].qlen*ORDINE > scheduler_data->size[i]) scheduler_data->size[i] += scheduler_data->queues[i].qlen*ALPHA ; else if (scheduler_data->size[i] >= ALPHA)


109

scheduler_data->size[i] -= scheduler_data->queues[i].qlen == 0 ? ALPHA : scheduler_data->queues[i].qlen*ALPHA ; if((jiffies-time)>5*HZ) { time = jiffies; printk(KERN_DEBUG); for(i=0; i<NQUEUE; i++) { printk("coda %d: %d(%3lu.%02lu) ", i, scheduler_data->queues[i].qlen, (scheduler_data->size[i])/ORDINE, (scheduler_data->size[i])%ORDINE); } printk(" pkt_cnt: %d\n",atomic_read(&queue_mgr_pkt_cnt)); } } #endif if (scheduler_data->skb == NULL) { #ifdef QUEUE_MGR_DEBUG printk(KERN_DEBUG "scheduler: skb == NULL pkt_cnt: %d\n",atomic_read(&queue_mgr_pkt_cnt)); #endif min_timer = MAX_CW; for(i=0; i<NQUEUE; i++) { if (!skb_queue_empty(&(scheduler_data->queues[i]))) { is_pkt2send = TRUE; /* if timer is 0 it is random generated */ if (scheduler_data->timer[i] == 0) { get_random_bytes(&random_timer, sizeof(random_timer)); random_timer = random_timer & scheduler_data->cw[i]; scheduler_data->timer[i] = random_timer; } /* minimum timer search => TXOP */ if (scheduler_data->timer[i] < min_timer) { collision = 0; min_timer = scheduler_data->timer[i]; min_index[collision] = i; } else if(scheduler_data->timer[i] == min_timer) { min_index[++collision] = i; } }/* end if queue is not empty */ }/* end for i<NQUEUE */ if (is_pkt2send == TRUE) { if (collision == 0) { /* pkt extraction */


110

if(scheduler_data->timer[min_index[0]] == min_timer) { scheduler_data->skb = skb_dequeue(&(scheduler_data->queues[min_index[0]])); scheduler_data->cw[min_index[0]] = default_min_cw[min_index[0]]; spin_lock(&scheduler_data->queue_size_lock); scheduler_data->queue_size[min_index[0]] -= scheduler_data->skb->len; spin_unlock(&scheduler_data->queue_size_lock); } else printk(KERN_DEBUG "Queue_mgr: Bug -> timer!=min_timer extracting packet\n"); } else { /* collision>0 */ /* cw is doubled if collision is detected */ collision_solver = 0; for (i=0; i <= collision; i++) { aux = min_index[i]; /* search for queue with higher priority */ if (min_index[i] > collision_solver) collision_solver = min_index[i]; scheduler_data->cw[aux] = (scheduler_data->cw[aux] << 1) + 1; scheduler_data->cw[aux] = scheduler_data->cw[aux] > default_max_cw[aux] ? default_max_cw[aux] : scheduler_data->cw[aux]; } /* pkt extraction */ if (scheduler_data->timer[collision_solver] == min_timer) { scheduler_data->skb = skb_dequeue(&(scheduler_data->queues[collision_solver])); scheduler_data->cw[collision_solver] = default_min_cw[collision_solver]; spin_lock(&scheduler_data->queue_size_lock); scheduler_data->queue_size[collision_solver] -= scheduler_data->skb->len; spin_unlock(&scheduler_data->queue_size_lock); } else printk(KERN_DEBUG "Queue_mgr: Bug -> random choose after collision failed\n"); }/* end collision>0 */ /* decreasing all the timer by min_timer.. just like time flow ! */ for(i=0; i<NQUEUE; i++) if (scheduler_data->timer[i] > 0) { scheduler_data->timer[i] -= min_timer; if (scheduler_data->timer[i]<0) { printk(KERN_DEBUG "Queue_mgr: Bug -> found timer < 0\n"); scheduler_data->timer[i]=0; } } }/* end ispkt2send */


111

else {/* coda software EMPTY */ spin_lock(&scheduler_data->access_to_scheduler); go_scheduling = 0; spin_unlock(&scheduler_data->access_to_scheduler); return; } }/* end skb == NULL */ if (scheduler_data->skb != NULL) { #ifdef QUEUE_MGR_DEBUG printk(KERN_DEBUG "scheduler: skb != NULL pkt_cnt: %d\n",atomic_read(&queue_mgr_pkt_cnt)); #endif if (atomic_read(&queue_mgr_pkt_cnt) < THRESHOLD) { atomic_inc(&queue_mgr_pkt_cnt); if(start_xmit(scheduler_data->skb,scheduler_data->skb->dev)!=0) { atomic_dec(&queue_mgr_pkt_cnt); } scheduler_data->skb = NULL; } else { /* if pkt_cnt>THRESHOLD *//* coda hardware FULL */ spin_lock(&scheduler_data->access_to_scheduler); go_scheduling = 2; spin_unlock(&scheduler_data->access_to_scheduler); return; } }/* end if skb!=null */ else if (is_pkt2send == TRUE) printk(KERN_DEBUG "Queue_mgr: Bug -> pkt not extracted\n"); queue_task(scheduler_data->scheduler_task, &tq_immediate); mark_bh(IMMEDIATE_BH); }/* end if ptr!=NULL */ } /*implementazioni delle funzioni per l'uso della struttura dinamica */ hash_table_t *create_hash_table(int size) { hash_table_t *new_table; int i; if (size<1) return NULL; /* invalid size for table */ /* Attempt to allocate memory for the table structure */ new_table = kmalloc(sizeof(hash_table_t),GFP_ATOMIC); if(new_table == NULL) return NULL; /* Attempt to allocate memory for the table itself */ new_table->table = kmalloc(sizeof(list_t *) * size,GFP_ATOMIC);


112

if (new_table->table==NULL) return NULL; /* Initialize the elements of the table */ for(i=0; i<size; i++) new_table->table[i] = NULL; /* Set the table's size */ new_table->size = size; return new_table; } unsigned int hash(hash_table_t *hashtable, unsigned char *mac) { unsigned int hashval; int k=0; /* we start our hash out at 0 */ hashval = 0; while( k<6){ hashval = *mac + (hashval << 5) - hashval; mac++; k++; } printk("\nhashval= %u",hashval % hashtable->size); return hashval % hashtable->size; } list_t *lookup_row(hash_table_t *hashtable, unsigned char *mac) { list_t *list; unsigned int hashval = hash(hashtable, mac); /* Go to the correct list based on the hash value and see if str is * in the list. If it is, return return a pointer to the list element. * If it isn't, the item isn't in the table, so return NULL. */ for(list = hashtable->table[hashval]; list != NULL; list = list->next) { if (strcmp(mac, list->mac) == 0) return list; } return NULL; } int add_row(hash_table_t *hashtable, unsigned char *mac,unsigned int qos) { printk("m1\n"); list_t *new_list; list_t *current_list; printk("m2\n"); unsigned int hashval = hash(hashtable, mac); printk("m3\n"); /* Attempt to allocate memory for list */ new_list = kmalloc(sizeof(struct _list_t_),GFP_ATOMIC); new_list->mac=kmalloc(ETH_ALEN,GFP_ATOMIC); printk("m4\n");


113

if (new_list==NULL) return 1; printk("m5\n"); /* Does item already exist? */ current_list = lookup_row(hashtable, mac); printk("m6\n"); /* item already exists, don't insert it again. */ if (current_list != NULL) return 2; printk("m7\n"); /* Insert into list */ strncpy(new_list->mac,mac,ETH_ALEN); printk("m8\n"); new_list->qos = qos; printk(" %u %u %u\n",mac[0],mac[1],new_list->qos); new_list->next = hashtable->table[hashval]; hashtable->table[hashval] = new_list; printk("m9\n"); return 0; } void free_table(hash_table_t *hashtable) { int i; list_t *list, *temp; if (hashtable==NULL) return; /* Free the memory for every item in the table, including the * strings themselves. */ for(i=0; i<hashtable->size; i++) { list = hashtable->table[i]; while(list!=NULL) { temp = list; list = list->next; kfree(temp->mac); kfree(temp); } } /* Free the table itself */ kfree(hashtable->table); kfree(hashtable); } hash_table_t *load_table (const char *fread ) { printk("a\n"); /*modifica gianf */ int length_read,ins; unsigned int qos; int iter=0; int h, i; char c[2]; printk("b\n"); unsigned char *mac=kmalloc(ETH_ALEN,GFP_ATOMIC); char buffer[20]; printk("c\n"); hash_table_t *qos_hash_table; int size_of_table = 256; struct file * table = NULL;


114

mm_segment_t orig_fs; printk("d\n"); qos_hash_table = create_hash_table(size_of_table); printk("e\n"); table = filp_open(fread, O_RDONLY, 00); printk("f\n"); if (!table || !table->f_op || !table->f_op->read) { printk("WARNING: File object is a null pointer!!!\n"); } printk("g\n"); table->f_pos = 0; orig_fs = get_fs(); set_fs(KERNEL_DS); printk("h\n"); while ((length_read = table->f_op->read(table, buffer, sizeof(buffer), &table->f_pos)) >0) { h=0; i=0; while(i<sizeof(buffer)-4) { c[0]=buffer[i]; c[1]=buffer[i+1]; i=i+3; mac[h]=htoi(c); h++; } printk("Iterazione n%d\n",iter); printk("k\n"); printk("l %u %u %u %u %u %u %u\n",mac[0],mac[1],mac[2],mac[3],mac[4],mac[5],(unsigned int) buffer[18]-'0'); qos=(unsigned int) buffer[18]-'0'; printk("m\n"); ins = add_row(qos_hash_table,mac,qos); //inserisce una riga della tabella nell'hash_table printk("n\n"); iter++; } /* Release the file object pointer. */ printk("o\n"); put_filp(table); printk("p\n"); return qos_hash_table; } int hexalpha_to_int(int c) { char hexalpha[]="aAbBcCdDeEfF"; int i; int answer=0; for (i=0;answer == 0 && hexalpha[i] !='\0' ; i++) { if(hexalpha[i] == c) answer = 10 + i/2; }


115

return answer; } unsigned int htoi(char s[]) { unsigned int answer=0; int i =0; int valid=1; int hexit; while(i<2) { if(s[i] ==':') { i++; } answer=answer*16; if (s[i]>='0' && s[i]<='9') { answer=answer +s[i]-'0'; } else { hexit=hexalpha_to_int(s[i]); if (hexit == 0) valid = 0; else answer=answer+hexit; } i++; } if (!valid) answer=0; return answer; } /*fine implementazione delle funzioni di gestione della struttura albero */ /* Initialize the module */ int init_module() { int i; printk("Inizio modulo\n"); const char *table=kmalloc(20, GFP_ATOMIC); table="/etc/hostqs"; printk("Inizio modulo+2 istruzioni\n"); table_qos=load_table(table); /*carico la tabella */ printk("dopo load_table\n"); /*fine modifica gianf */ struct tq_struct *scheduler_task;


116

scheduler_data = (struct _scheduler_data *)kmalloc(sizeof(struct _scheduler_data),GFP_ATOMIC); if (scheduler_data == NULL) { printk(KERN_DEBUG "Queue Manager: init_module() - kmalloc failed\n"); return -ENOMEM; } memset(scheduler_data, 0, sizeof(struct _scheduler_data)); scheduler_task = (struct tq_struct *)kmalloc(sizeof(struct tq_struct), GFP_ATOMIC); if (scheduler_task == NULL) { printk(KERN_DEBUG "Queue Manager: init_module() - kmalloc failed\n"); return -ENOMEM; } memset(scheduler_task, 0, sizeof(struct tq_struct)); loops = 0; start_time = jiffies; atomic_set(&stop_scheduling,0); atomic_set(&queue_mgr_pkt_cnt,0); go_scheduling = 0; for(i=0; i<NQUEUE; i++) { skb_queue_head_init(&(scheduler_data->queues[i])); scheduler_data->cw[i] = default_min_cw[i]; } spin_lock_init(&scheduler_data->queue_size_lock); spin_lock_init(&scheduler_data->access_to_scheduler); scheduler_data->scheduler_data = scheduler_data; scheduler_data->scheduler_task = scheduler_task; scheduler_task->routine = scheduler; scheduler_task->data = (void *)scheduler_data; /* avvio di scheduler task NOTA: va fatta QUA!!, dopo aver inizializzato tutto, ma prima che sia su il collegamento col driver*/ queue_task(scheduler_task, &tq_immediate); mark_bh(IMMEDIATE_BH); /* inizializzazione collegamento col driver*/ queue_mgr_new_skb = queue_up_skb; pointer_to_driver = from_call_back_driver; atomic_set(&queue_mgr_present,1); printk("Ste's Queue Manager is at ver = %s Now=%lu.\n", QUEUE_MGR_VER, jiffies); printk("Luca's queue_mgr-upgrade for airo PCMCIA card\n"); printk("CW_min: %d %d %d; CW_max: %d %d %d\n", default_min_cw[0], default_min_cw[1], default_min_cw[2],


117

default_max_cw[0], default_max_cw[1], default_max_cw[2]); /* If we return a non zero value, it means that init_module failed and * the kernel module can't be loaded */ return 0; } /* Cleanup - undid whatever init_module did */ void cleanup_module() { u8 i; struct sk_buff *skb; atomic_set(&queue_mgr_present,0); queue_mgr_new_skb=NULL; /* aggiungere un controllino nel driver!!!!!!! */ atomic_set(&stop_scheduling,1); for(i=0; i<NQUEUE; i++) { while(!skb_queue_empty(&(scheduler_data->queues[i]))) { /* Manda i pacchetti rimasti nelle code usando la funzione del driver realmente demandata a questo. Nel dirver originale la prism2_tx ï¿½ la hard_xmit e fa tutto nel driver modificato si limita a cercare il queue manager e a mandargli i pkt, la funzione che realmente esegue l'invio ï¿½ora real_prism2_tx. */ skb = skb_dequeue(&(scheduler_data->queues[i])); if (skb != NULL) start_xmit(skb,skb->dev); else printk(KERN_DEBUG "Bug -> shutting down module, found null skb"); } printk("\nSte & Luca's Queue Manager: queue %d dropped %u pkts\n", i, scheduler_data->dropped[i]); } kfree(scheduler_data->scheduler_task); kfree(scheduler_data); free_table(table_qos); printk("Ste & Luca's Queue Manager: %u loops in %lu ms\n",loops, (jiffies - start_time)*1000/HZ); printk("Ste & Luca's Queue Manager is going down. Are you sure you don't need me any more?\n");


118

A.3 Il Makefile # Makefile for queue_mgr KERNEL_PATH=/usr/src/linux-$(shell uname -r) HOSTAP_PATH=modified-hostap include $(KERNEL_PATH)/.config INCLUDES=-I$(KERNEL_PATH)/include MODVERSION=-DMODVERSIONS -include /usr/src/linux-$(shell uname -r)/include/linux/modversions.h MODFLAGS := -Wall -DMODULE -D__KERNEL__ -DLINUX CC = gcc STD1 = -DEXPORT_SYMTAB ALL = queue_mgr.o all:$(ALL) queue_mgr.o: queue_mgr.c queue_mgr.h /usr/include/linux/version.h @echo @echo "creazione di queue_mgr.o" $(CC) $(INCLUDES) $(MODFLAGS) -c -g $(MODVERSION) $(STD1) queue_mgr.c -o queue_mgr.o install: cp queue_mgr.o /lib/modules/$(shell uname -r)/ depmod -ae #crea il file /etc/hostqs touch /etc/hostqs clean: @rm *.o


119

Appendice B: Installazione del software e configurazione del testbed

B.1 Installazione di HostAP e HostQs

Per installare Hostqs bisogna prendere la il file queue_mgr_1.0.tar.gz da me realizzato e

seguire le istruzioni di installazione consigliate dal file README di cui si riportano

brevemente i passi principali:

• decompattare la cartella di HostAP:

tar -xzf hostap-driver-0.2.0.tar.gz

• patchare l’HostAP per farlo funzionare con il supporto della qualità del servizio:

patch -p0 <hostap-add-queue_mgr-support.patch

• selezionare la cartella e installare HostAP:

cd hostap-driver-0.2.0

make

make install

• a questo punto ritornare nella cartella precedente e installare HostQs:


120

cd..

make

make install

Questa procedura installerà il driver hostap, il modulo queue_mgr e il file hostqs, che rappresenta la tabella con i MAC address e la QoS, nella cartella /etc.

B.2 Configurazione del testbed Inanzitutto bisogna configurare la macchina su cui è in esecuzione Hostqs come un router, per fare ciò basta lanciare lo script netconf.sh così strutturato come utente root:

#! /bin/sh

ifconfig eth0 up

ifconfig eth0 add 192.168.1.254

ifconfig eth0:0 netmask 255.255.255.0

ifconfig wlan0 up

iwconfig wlan0 essid hostqs

ifconfig wlan0 add 192.168.2.254

ifconfig wlan0:0 netmask 255.255.255.0

route add -net 192.168.1.0 netmask 255.255.255.0 dev eth0

route add -net 192.168.2.0 netmask 255.255.255.0 dev wlan0

echo 1 > /proc/sys/net/ipv4/ip_forward

Sucessivamente è necessario configurare le restanti macchine. La macchina su cui è in

funzione il generatore di Traffico Iperf in modalità client va configurato come segue:


121

ifconfig eth0 up



route add -net 192.168.1.0 netmask 255.255.255.0 dev eth0

route add -net 192.168.2.0 netmask 255.255.255.0 gw 192.168.1.254

Le macchine su cui Iperf è in modalità server (gli utenti mobili) devono avere

rispettivamente le seguenti configurazioni:

ifconfig eth0 up





ifconfig wlan0 up






122

Bibliografia

[1] WiFi, http://en.wikipedia.org/wiki/WiFi

[2] 802.x standard family, http://www.ieee802.org/

[3] http://www.techtown.it/public/team/marcy/Wireless.html

[4] S. Mangold, S. Choi, P. May, O. Klein, G. Hiertz, L. Stibor, “IEEE 802.11e Wireless

LAN for Quality of Service”

[5] S. Park, D. Kim, K. Kim, S. Choi, S. Hong, “ Collaborative QoS Architecture between

DiffServ and 802.11e Wireless LAN. In IEEE VTC’03-Spring, 2003”

[6] D. Gu, J. Zhang, “QoS Enhancement in IEEE802.11 Wireless Local Area Networks”

IEEE Communications Magazine, 2003.

[7] Andrea Alfieri, Dario Lodi Rizzino, Francesco Zanichelli, “Simulazione Del Modello

Enhanced Distributed Coordination Function (Edcf) Tramite Ns-2”,

http://www.ce.unipr.it/~alfieri/

[8] IEEE 802.11 WG, Supplemento alla Parte II dedicata al livello Wireless Medium

Access Control (MAC) e al livello Fisico (PHY) Specifications: MAC Enhancements

for Quality of Service, IEEE 802.11e Draft 5.0, Luglio 2003

[9] S. Mangold, S. Choi, G. R. Hiertz, O. Klein, B. Walke, “Analysis of IEEE 802.11e for

QoS Support in Wireless LANs,” IEEE Wireless Communications Mag., Dicembre

2003, pp. 40–50.

[10] G. Bianchi, I. Tinnirello, “Analysis of Priority Mechanisms Based on Differentiated

Inter Frame Spacing in CSMA-CA,” IEEE VTC-Fall, Orlando, FL, Ottobre 2003

[11] A. Grilo, M. Nunes, “Performance evaluation of IEEE 802.11e,” IEEE PIMRC’02,

Lisboa, Portugal, Settembre 2002


123

[12] S. Choi, J. del Prado, S. Shankar N, S. Mangold, “IEEE 802.11e Contention-Based

Channel Access (EDCF) Performance Evaluation,” IEEE ICC 2003, Anchorage,

Alaska, Maggio 2003

[13] A. Lindgren, A. Almquist, O. Schel´en, “Quality of Service Schemes for IEEE 802.11

Wireless LANs - An Evaluation,” MONET, Special Issue on PerformanceEvaluation

of Qos Architectures in Mobile Networks, Vol 8, No 3, Giugno 2003, pp. 223–35.

[14] Hostap driver, http://hostap.epitest.fi/

[15] http://www.inlab.csp.it/tools/wireless/hostqs/

[16] ITU-T Recommendation P.862

[17] http://www.gnome.org/projects/dia/

[18] http://www.uml.org/

[19] www.magicdraw.com/

[20] Simone Piccardi, Guida alla Programmazione in Linux , http://gapil.firenze.linux.it/

[21] Alessandro rubini, I moduli del kernel, febbraio 2004,

http://www.linux.it/~rubini/docs/modules26/modules26.html

[22] Peter Jay Salzman, Ori Pomerantz , The Linux Kernel Module Programming Guide,

http://www.tldp.org/LDP/lkmpg/2.4/html/index.html

[23] Alessandro Rubini, Jonathan Corbet,Linux Device Drivers, Second Edition,

O’Reilly, June 2001

[24] http: //www.kernel.org/pub/linux/kernel/v2.4/

[25] http://www.doxygen.org/

[26] Slackware linux, www.slackware.org

[27] Ubuntu Linux, www.ubuntu.org

[28] dast.nlanr.net/Projects/Iperf/

[29] Wireless Extensions

http://www.hpl.hp.com/personal/Jean_Tourrilhes/Linux/Tools.html

[30] Debian Gnu/Linux, www.debian .org

[31] ndiswrapper.sourceforge.net/

[32] www.belkin.com/

[33] D. Bruscino, Valutazione sperimentale di API di programmazione per IEEE 802.11 ,

tesi di laurea A. A. 2003-2004

Un meccanismo di comunicazione a priorità per reti …Le reti locali wireless, o LAN wireless,...

Documents

Transcript of Un meccanismo di comunicazione a priorità per reti …Le reti locali wireless, o LAN wireless,...