wiki:Diario/Gnappo

Version 14 (modified by gnappo, 17 years ago) (diff)

Aggiornamento.

  1. Diario di gnappo
    1. 05 Giugno 2007
    2. 09 Giugno 2007
    3. 11 Giugno 2007
    4. 12 Giugno 2007
    5. 13 Giugno 2007
    6. 14 Giugno 2007
    7. 15 Giugno 2007
    8. 19 Giugno 2007
    9. 20 Giugno 2007
    10. 21 Giugno 2007
    11. 22 Giugno 2007
    12. Documenti

Diario di gnappo

05 Giugno 2007

1000 - 1100

Autenticazione su piattaforma trac.

09 Giugno 2007

0930 - 1030 (1h)

Ricerca su Internet:

-> overhead da tenere presenti? ​http://www.ieee-infocom.org/2003/papers/21_01.PDF : si tratta di uno studio di un'anomalia di 802.11b (se in una rete c'e' un client 802.11b lento, questo penalizza gli altri!). Durante la dissertazione viene fatto un calcolo dell'overhead introdotto da 802.11b (circa il 30%). Questa percentuale cresce se ci sono contese (e quindi backoff algorithm). Nel documento sono presenti formule che modellano adeguatamente l'overhead.

-> come valutare il carico in presenza di PCF? Unsolved question.

-> QoS, spunti interessanti?

11 Giugno 2007

1400 - 1845 (4.75h)

-> Diffusione di PCF: sembra che a causa delle carenze di specifiche non sia largamente implementato ( ​A survey of quality of service in IEEE 802.11 networks, la bibbia cap. 9), per tanto il carico potrebbe essere analizzato supponendo di essere in DCF.

-> Attualmente una STA seleziona un BSS un AP in base alla sola potenza del segnale (RSSI) che e' evidentemente insufficiente ai nostri scopi.

​On Access Point Selection in IEEE 802.11 Wireless Local Area Networks (02): innanzitutto mette in luce che se una stazione sceglie di trasmettere ad un rate basso per evitare errori (magari sente un segnale disturbato), si ha un degrado del throughput globale poiche' il protocollo di accesso al mezzo e' fair, e quindi la lumaca puo' occupare il mezzo per tempi considerevoli (visto il basso rate).
La selezione dell'AP e' fatta in base al throughput ottenibile dalla STA (stimabile con una equazione da verificare che tiene conto anche del frame error rate espresso in funzione di SNR). Inoltre lo studio tiene conto anche dell'impatto della STA sul nuovo BSS (vedi sopra). Viene presa in considerazione anche la possibilita' di una selezione dinamica dell'ap che viene fatta ad intervalli di tempo variabili per evitare scan non necessari (tempo di scan 1, 2 secondi). In particolare il periodo aumenta se l'ap candidato rimane sempre lo stesso.

​Improved Access Point Selection (03): mette in luce altri fattori che intervengono nella selezione di un access point, come politiche di filtering (MAC, port), limiti di bandwith o di utilizzo (servizio a pagamento) ecc... Per tanto propone dei test per valutare l'effettiva qualita' di un BSS. Potremmo esplorare anche questa strada.

-> da vedere: ​SyncScan: Practical Fast Handoff for 802.11 Infrastructure Networks

-> poco utile: ​http://people.nokia.net/cedric/Papers/VTC06multiaccess.pdf

12 Giugno 2007

0910 - 1310 (4h)

​Improved Access Point Selection (03): il test che propongono e' il seguente: 

1. trova tutti gli AP disponibili
2. colleziona i beacon
3. per ogni AP "in chiaro"
4.   prova ad ottenere un indirizzo IP (con dhcp)
5.   se ottieni l'IP
6.     stima RTT con il server di riferimento (ping)
7.     testa le porte aperte
8.     stima il bandwidth

Virgil, questo il nome del progetto, e' in fase di sviluppo su piattaforma linux (anche se non sembra reperibile). Utilizza wireless tools (iwlist, iwconfig) per collezionare statistiche e per ogni AP incontrato viene lanciato un pthread incaricato della valutazione della bonta' dell'AP. L'overhead introdotto con questa soluzione non e' cosi' esorbitante considerando il fatto che sono necessari 2,5 secondi solo per un iwlist scan.

​SyncScan: Practical Fast Handoff for 802.11 Infrastructure Networks (05): discute principalmente di quando piazzare i momenti di scan preferendo lo scanning attivo (probe request, probe response) rispetto al passivo per la sua "immediatezza" (non sono costretto ad aspettare un beacon interval). Ci interessa molto marginalmente.

​Decentralized Access Point Selection Architecture for Wireless LANs - Deployability and Robustness - (06): propone un algoritmo di selezione di un AP basato sulla massimizzazione del throughput locale. I fattori che in ultima analisi sembrano incidere di piu' nella determinazione del throughput locale sono il packet error rate (ricavabile in funzione del SNR) e il numero di stazioni connesse all'AP (ottenibile mediante scan). Lo studio assume, pero', che le probabilita' di collisioni siano trascurabili. Inoltre, viene proposto un algoritmo dinamico, dal momento che le condizioni delle reti wireless sono volubili. Nella simulazione si tiene anche conto della concomitanza nella stessa area geografica di nodi che utilizzano RSSI per la selezione e altri che invece utilizzano l'algoritmo proposto. In ogni caso una selezione siffatta incrementa il throughput minimale di tutti i nodi, siano essi dotati o no del nuovo sistema.

-> sia (02) che (06) valutano il packet error rate in funzione di SNR

​Energy-Efficient PCF Operation of IEEE 802.11a Wireless LAN: contiene una sintesi del packet error rate in base a SNR. Fa riferimento a distribuzioni statistiche, e' molto tecnico.

1500 - 1900 (4h)

​An Optimized Load-Balancing Algorithm for Infrastructure Based Short-Range Wireless Networks (09): l'algoritmo di selezione dell'AP si fonda su una relazione pesata tra il numero di ritrasmissioni necessarie per consegnare un pacchetto e il ritardo nella trasmissione. Inoltre, lo studio evidenzia, piuttosto grossolanamente, come le prestazioni degradino notevolmente con l'aumentare dei nodi associati al BSS.

​Client Channel Selection for Optimal Capacity in IEEE 802.11 Wireless Networks (11): lo studio propone un semplice (e, secondo me, non corretto) modello per la valutazione dello stato di un canale. La capacita' di un canale wireless e' fondamentalmente condizionata da due parametri: dalla tecnologia utilizzata (802.11{b,g}) e dalla natura della comunicazione (i.e. onde radio, si pensi ai disturbi di reti overlapped).
Se vi sono N client associati con un access point la capacita' Ca disponibile a ciascun client e cosi' limitata:
Cm >= Ca >= Cm/N dove Cm e' la massima capacita' disponibile nella rete wireless (limitata dagli overhead associati al protocollo, vedi limitazione della tecnologia). Inferiormente e' limitata a Cm/N poiche' la politica di assegnazione del canale dovrebbe essere fair.
Inoltre la capacita' del canale e' anche limitata dal teorema di Shannon (vedi limitazione della comunicazione). Il minimo di queste due valutazioni dovrebbe restituire un capacita' minima "garantita". L'access point con capacita' minima migliore sara' l'access point da selezionare (scelta conservativa).
I parametri per operare questa scelta sono di facile reperibilita': il numero dei nodi associati si ottiene con un semplice scan, la massima capacita' del canale e' disponibile nei beacon mentre la potenza del segnale (per calcolare Shannon) e' direttamente disponibile dall'hardware.
Critica: in tutti questi ragionamenti si suppone, celatamente, che ogni client operi alla medesima bandwidth il che, oltre a non essere realistico, ha anche conseguenze tutt'altro che trascurabili per gli altri nodi in quanto puo' diminuire drasticamente la banda loro disponibile.

​Network Selection Decision in Wireless Heterogeneous Networks: affronta la tematica di selezione di una rete wireless di qualsiasi tipo, per altro a livelli che non ci competono.

​Scalable and Robust WLAN Connectivity Using Access Point Array: per valutare il carico di un AP propone di analizzare i silenzi, poiche' il numero di stazioni associate ad un AP e' un indicatore troppo debole (ci sono studi che lo dimostrano). Un canale e' occupato quando ci sono dati, oppure quando c'e' un silenzio dovuto ad una contesa. Il canale e' libero quando non e' occupato. Da approfondire.

Formattazione del diario.

13 Giugno 2007

0940 - 1140 (2h)

Upload del diario e breve formattazione.

Prosecuzione dello studio del paper 12:
​Scalable and Robust WLAN Connectivity Using Access Point Array (12): per calcolare il tempo libero del canale la stazione deve operare in monitor mode. In particolare dovra' saltare su tutti i canali di interesse e nel frattempo tenere anche traccia del numero di stazioni associate, facilmente ricavabile con un analisi dell'header dei pacchetti. Ovviamente le STA completamente inattive non verranno tracciate ma cio' ha poca importanza dal momento che non generano traffico. Ancora una volta, lo studio si svolge in un contesto in cui la coordinazione d'accesso al mezzo e' distribuita ignorando di fatto quella centralizzata. L' idle time del canale si trova per differenza tra il tempo totale e il tempo in cui il mezzo e' rilevato essere occupato. Tutte le informazioni necessarie al calcolo del tempo in cui il canale e' in uso sono reperibili negli header dei frame (e.g. il transfer rate di ciascuna STA). La valutazione dei silenzi dovuti al backoff e' difficile, se non impossibile e quindi viene scelto un approccio calibrativo.

1500 - 1645 (1.75h)

Punto della situazione con SoujaK.

Prosecuzione dello studio del paper 12:
​Scalable and Robust WLAN Connectivity Using Access Point Array (12): lo studio in generale affronta il problema dell'ottimizzazione di distribuzione di carico su piu' access point, pertanto sono previste politiche di non congestionamento.

​Performance Analysis of the IEEE 802.11 Distributed Coordination Function : da vedere.

14 Giugno 2007

0905 - 1235 (3.50h)

Rilettura del documento 02: conseguenze del multirate in una cella: se in una cella sono presenti una STA operante a 11Mbps e una a 1Mbps il loro throughput e' comparabile! Questo fattore dovrebbe essere tenuto in considerazione.

da vedere: "Evaluation of “Performance Anomaly of 802.11b” paper through simulation results"

"MiFi?: A Framework for Fairness and QoS Assurance for Current IEEE 802.11 Networks With Multiple Access Points": un altro studio di Bejerano, dopo quello analizzato da soujak, caratterizzato dallo stesso rigore formale. Viene subito evidenziato come DCF non si presti a politiche di QoS in particolar modo riferite ad applicazioni RT (Real Time), a differenza di PCF. Per tanto lo studio suppone che gli access point forniscano tale servizio, che ricordo, ai fini del nostro studio, non essere diffuso. Inoltre, si assume che piu' access point che coprono la medesima area passino simultaneamente dal CFP al CP e viceversa, comportandosi idealmente come un singolo access point (il rapporto CFP/CP e' addirittura dinamico). Lo studio quindi s'interroga sull'equa ripartizione degli slot di tempo tra le STA, un problema non risolvibile in tempi polinomiali (a meno che P=NP).
In conclusione, la soluzione prevede delle modifiche sostanziali agli AP lasciando inalterate le STA e 802.11.

"An Empirical Analysis of the IEEE 802.11 MAC Layer Handoff Process": lo studio analizza dettagliatamente il tempo necessario per un handoff (802.11b), proponendo infine delle linee guida per ottimizzare questa funzione. Consultabile solo per riferimenti temporali.

Un po' fuori traccia:
​Techniques to Reduce IEEE 802.11b MAC Layer Handover Time : lo studio cerca di ottimizzare i tempi necessari per la fase di ricerca di un AP e cerca di individuare anche un fattore di scelta di quando effettuare un handover (cambio di AP). I prodotti attualmente in commercio utilizzano il numero di frame non ACK'ed per decidere quando cambiare AP (questo parametro sintetizza, indistinguibilmente, collisione congestione e perdita di segnale). Durante la fase di ricerca degli AP, viene evidenziato un problema: nel caso di piu' BSS sullo stesso canale quanto tempo devo ascoltare per ricevere i beacon di tutti? Con lo scanning attivo si aggira il problema.

Aggiornamento del diario.

15 Giugno 2007

0930 - 1030 (1h)

Creazione indice documenti.

Ricerche su Internet:

​A Study on Dynamic Load Balance for IEEE 802.11b Wireless LAN (16): propone un algoritmo di bilanciamento diviso in tre fasi: coordinazione tra AP (nella quale vengono assegnati canali distinti per evitare noiose interferenze), decisione della STA con quale AP associarsi e scelta del momento in cui cambiare AP. E' interessante osservare che utilizzano il valore RSSI medio delle STA e il numero di STA associate come criteri fondamentali per le due ultime fasi.

1120 - 1200 (1.66h)

​Performance Anomaly of 802.11b (17): e' lo studio che mette in risalto l'anomalia di 802.11b tale per cui una stazione con un basso tasso trasmissivo danneggia tutte le altre che hanno un tasso piu' alto. Rimane da capire se questa anomalia persiste anche in 802.11g, cosa che personalmente reputo probabile dal momento che, a memoria, non vengono introdotte modifiche alla tecnica di assegnazione del mezzo. Nel documento viene derivata una semplice espressione per il calcolo del throughput disponibile, che e' fortemente influenzato dal numero di stazioni che si contendono il mezzo e dopo viene dimostrata l'anomalia.

1411 - 1512 (1.01h) Punto della situazione con sjk: aggiornamenti, chiarimenti e sviluppi futuri.

1700 - 1820 (1.00h) Ricerca di ulteriore documentazione.

19 Giugno 2007

(3h)

​IEEE 802.11e Wireless LAN for Quality of Service (18): il documento si pone l'obiettivo di illustrare le principali novita' introdotte con 802.11e. In particolare vengono evidenziate le differenze con 802.11 per quanto riguarda le politiche di accesso al mezzo. 802.11 fornisce un po' di supporto per QoS grazie a PCF, che pero' soffre principalmente di due problemi: la non predicibilita' dei ritardi dei beacon e il non controllo della durata delle trasmissioni di STA CF-Pollable. Il ritardo di beacon, in generale, si ha quando avvengono delle trasmissioni nell'intorno del TBTT, dal momento che 802.11 consente di inviare frame il cui tempo di consegna puo' sforare il prossimo TBTT. Un ulteriore problema e' rappresentato dalla STA nascosta che potrebbe interferire durante il CFP (e.g. se non sente un beacon).
In 802.11e due nuove modalita' di accesso al mezzo vengono definite: EDCF (Enhanced DCF) e HCF (Hybrid Coordination Function). La prima viene utilizzata durante i CP, mentre la seconda durante CFP e CP. Una STA chiamata HC (Hybrid Coordinator) svolge compiti analoghi al PC.
Con EDCF vengono introdotte le Traffic Categories (TC), che intervengono pesantemente nel calcolo del backoff. In una STA si hanno fino a 8 code di trasmissione e quindi 8 istanze di backoff counter. Idealmente quindi vi sono 8 STA virtuali che concorrono per l'assegnazione del mezzo. Se il backoff counter di una STA virtuale scade in contemporanea ad altri si ha una collisione virtuale risolta da un opportuno scheduler che avvantaggera' la trasmissione a priorita' piu' alta (cfr. TC). HCF estende EDCF, fornendo funzionalita' per un accesso libero da contesa. E' compito dell'HC organizzare i tempi e i modi dei CFP, determinando, tra l'altro, chi deve parlare e per quanto tempo. Inolte l'HC ha anche la facolta' di effettuare del polling durante i periodi con contesa utilizzando interframe space piu' corti rispetto a quelli impiegati con (E)DCF. Al fine di minimizzare le collisioni esiste un meccanismo di prenotazione, basato su TC, della STA presso l'HC.
Dal momento che con EDCF non esiste una coordinazione centralizzata, e' possibile statisticamente ottenere QoS sfruttando le TC. Rimane, pero', il problema di BSS overlapped: e' allo studio un meccanismo di selezione dinamica delle frequenze.

Inizio lettura di ​Characterizing User Behavior and Network Performance in a Public Wireless LAN (19).

20 Giugno 2007

(1h)

Ultimazione lettura di (19): essenzialmente si analizzano i comportamenti e abitudini di utenti 802.11 che nella fattispecie partecipavano ad una conferenza. Lo studio va oltre cio' che ci interessa. Comunque la cosa, secondo me, piu' rilevante e' che in base alle rilevazioni da loro effettuate il carico di un AP non puo' basarsi solamente sul numero di utenti associati ma in realta', come intuibile, dipende dal traffico che ogni singola STA genera. Per altre osservazioni particolari, ma a noi poco utili, rimando alla lettura del documento.

1550 - 1820 (2.5h)

​New Insights from a Fixed Point Analysis of Single Cell IEEE 802.11 WLANs (20): lo studio richiede un background statistico che attualmente non mi appartiene e quindi si fa veramente complesso (alcune parti sono state saltate in tronco). E' la prosecuzione di uno studio precedente di Bianchi che in questa sede viene generalizzato e semplificato (in particolare si parte da equazione con punto fisso). L'ipotesi e' che le STA abbiano sempre una coda di trasmissione piena. Con questa condizione e' possibile capire l'allocazione del canale analizzando i backoff. Si assume anche che i parametri per il calcolo del backoff siano gli stessi per tutti i nodi. A partire da queste ipotesi vengono fornite formule per il calcolo della probabilita' di collisione, il data-rate, il throughput della rete.
Da notare che nel corso dell'analisi si ribadisce come una stazione con basso tasso trasmissivo abbia un impatto negativo in BSS partecipati da stazioni piu' prestanti.

Aggiornamento del diario.

Sistemazione dell'indice dei documenti.

21 Giugno 2007

0920 - 1340 (4.33h)

Aggiornamento del diario (19 e 20 Giugno).

Punto della situazione con soujak: aggiornamenti sul lavoro svolto negli ultimi giorni, sviluppi futuri e individuazione di alcuni parametri di base utili per la determinazione del carico.

Approfondimento dello studio (02): per stimare il throughput ottenibile e l'impatto della STA sul nuovo BSS a cui desidera associarsi, occorrono due valori che, a parer loro, devono essere comunicati dall'AP: il numero di STA associate e il tempo di occupazione del canale da parte delle altre STA. Queste informazioni, a mio parere, si possono carpire abbastanza agevolmente mediante azioni di sniffing.

1500 - 1640 (1.66h)

Incontro con gli altri componenti del gruppo: sviluppi futuri e breve condivisione di conoscenze.

1705 - 1735 (0.5h)

Approfondimento di (09).
Analisi e commenti insieme a soujak su i grafici dello studio di Bejerano precedentemente da lui analizzato.

22 Giugno 2007

0935 - 0955 (0.33h)

Aggiornamento del diario.

1140 - 1320 (2.66h)

Ulteriori appunti su (09): viene definita perdita di efficienza a causa di ritrasmissione di pacchetti il rapporto tra l'utilizzazione del canale nel caso ideale (i.e. senza data-loss e con RSSI massimo) e utilizzazione reale del canale che comprende errori bad CRC, ACK timeout, tempi di backoff e numero di ritrasmissioni (quest'ultimo calcolato in funzione di SNR). Analogamente, la perdita di efficienza dovuta al congestionamento della rete invece e' calcolata come il rapporto tra l'utilizzazione del canale nel caso ottimo e nel caso di congestionamento. Per stimare quest'ultimo fattore si guarda al ritardo di accodamento che va sommato al normale tempo di trasmissione.
La funzione obiettivo per la scelta dell'AP e' il prodotto tra la perdita di efficienza in caso di congestionamento ed in caso di perdita di pacchetti.

Ricerca di documentazione.

1500 - 1800

Lavoro con soujak: mappa mentale sul carico (kdissert), sviluppi futuri.

1815 - 1845

Approfondimento dell'appendice dello studio sjk03.
Metodo per stimare la latenza e il bandwidth in un collegamento tra un nodo X e un nodo Y:
sia p il packet error rate sul canale, t la latenza che intercorre in un scambio di dati con esito positivo (per l'accesso RTS/CTS e' la differenza di tempo tra l'RTS e il primo ACK). Sia b il valore medio iniziale del backoff counter, espresso in unita' di tempo (b=CWMin*SlotSize/2).
L'ammontare di tempo per effettuare il primo tentativo di trasmissione e' pari a b+t TU. Se la trasmissione fallisce (la probabilita' di fallimento ricordo essere p), si raddoppia la finestra di contesa cosicche' il secondo tentativo occupera' 2b+t TU, che sommati al primo tentativo diventano 3b+2t TU. Generalizzando il procedimento, tenendo conto del packet error rate, si ha che la latenza totale l all'iesimo tentativo e' pari a: 

Da scrivere formulaccia generalizzata in funzione del packet error rate.

Si noti che vengono fatte due assunzioni: il frame viene ritrasmesso fin tanto che questo non viene ricevuto dal destinatario e non c'e' limite superiore alla CW. S'intuisce che queste due approssimazioni non sono molto significative, considerando che nella maggior parte dei casi reali un MSDU viene trasmesso in pochi tentativi.
L' error rate del collegamento puo' essere determinato da una STA esterna e passiva semplicemente osservando i numeri di sequenza dei pacchetti (secondo me vale la pena guardare quegli studi in cui l' error rate e' espresso in funzione di SNR in modo tale che la STA possa calcolarlo autonomamente, vedi 02).
La bandwidth del collegamento sara' pari a Sdata/l dove Sdata e' la dimensione dei dati e l la latenza appena calcolata.

Documenti