Les mécanismes de base de 802.11 et les propositions de 802.11e pour la QoS

Les mécanismes de base de 802.11 et les propositions de 802.11e pour la QoS

Fady FARAH

Les mécanismes de base de 802.11 et les propositions de 802.11e pour la QoS – FF- July 2003 All rights reserved © 2003, Alcatel2/65

Agenda

> Mode de fonctionnement des WLAN > Mécanismes MAC 802.11> Limites de 802.11 pour la QoS> 802.11e et les nouveaux mécanismes


Mode de fonctionnement des WLAN (1/2)

Mode infrastructure

BSS : Basic Set Services

AP : Access Point


Mode de fonctionnement des WLAN (2/2)

Mode ad hoc

IBSS : Independant BSS


Agenda

> Mode de fonctionnement des WLAN > Mécanismes MAC 802.11> Limites de 802.11 pour la QoS> 802.11e et les nouveaux mécanismes


Mécanismes MAC 802.11 (1/31)

> 2 Fonctions d ’accès• Distributed Coordination Function (DCF)• Point Coordination Function (PCF) seulement en mode

infrastructure> Economie d ’énergie> Fragmentation> Authentification> Cryptage WEP



Distributed Coordination Function (DCF)

> Accès CSMA: Si le canal est libre, émission, sinon attente de libération du canal

> Détection de Collision: mécanisme ACK> Évitement de collision: mécanismes Backoff, RTS/CTS, NAV> Retransmission en cas de collision: Backoff> Inter trames différentes pour accès : DIFS, SIFS> Fonction mandatory




> Mécanisme Backoff avant émission:• Nombre aléatoire N tiré dans une fenêtre [0, CWmin] • N = nb de time slots pendant lesquels le canal doit être libre

=> évite la synchronisation de stations en attente

> Mécanisme de Backoff en cas de retransmission:• CWmin est doublé (sauf s ’il a atteint Cwmax)• N est tiré dans [0, nouveauCWmin]• Le nombre de retransmissions est limité




> Mécanisme NAV:• Chaque station possède Network Allocation Vector qui

contient durée de l ’échange en cours• Toutes trames contiennent un champ durée => mettre à jour

le NAV• Station ne peut émettre que si son NAV est a zéro• NAV est décrémenté dans le temps




> Mécanisme NAV:




> Mécanismes RTS/CTS et nœud caché• Station qui veut émettre envoi Request To Send• Récepteur doit répondre Clear To Send• Toutes les stations à portée de l ’émetteur ou du récepteur

sont prévenues=> elles mettent à jour leur NAV et le problème du nœud

caché est résolu=> permettent détection de collision plus rapide car courtes



Distributed Coordination Function(DCF)

> Mécanisme RTS/CTS et nœud caché

Station1

Station2

Station3

• Station 1 et 3 ne se voient pas

• Chacune croit le canal libre

• Et émet vers 2

Collision

Trame Trame



Station1

Station2

Station3

• Station 1 et 3 ne se voient pas

• Toutes voient Station 2

• Stations 1 et 3 veulent parler à 2

RTS

RTS

• Station1 envoi RTS à 2

• Station3 ne reçoit pas RTS

CTS

• Station2 répond à 1 par CTS

• Station3 reçoit CTS (NAV)

• Le canal est réservé pour 1 et 2





> Mécanismes RTS/CTS et nœud caché




> Inter trames?• Durée pendant laquelle le canal doit être libre • Distributed Inter Frame Space (DIFS) => utilisée avant

backoff pour émission ou ré-émission • Short Inter Frame Space (SIFS) => utilisée avant de répondre

à une station par un ACK

DIFS

SIFS

= 50 µs DSSS

= 10 µs pour DSSS

SIFS donne

une priorité




> Echange en DCF

Station1

Station2

trame3

trame3

Station3 Ack1

DIFS

DIFS

SIFS

DIFS



Point Coordination Function (PCF)

> 2 périodes = 1 super trame• Contention Period (CP) => accès DCF• Contention Free Period (CFP) => accès PCF (AP = PC)

> Interrogation des stations par PC: polling list> Mécanismes identiques à DCF : ACK, NAV, retransmission> Inter trames différentes: PIFS, SIFS> Fonction optionnelle mais seulement en mode avec AP

CFP CP




DCF

PCF

Pendant CPPendant CFP

Option en

mode AP

Base en

mode ad hoc

ou AP




> CFP périodique, débute avec beacon DTIM et durée bornée

NAV NAV

PCF PCFB B

Intervalle sans

contention

Intervalle à

accès libre

occupé

Période de l ’intervalle CFPintervalle CFP raccourci




> Polling list• Inscription sur la polling list lors de l’association avec AP

(stations pollables)• Stations interrogées successivement pendant CFP (AP envoi

trame CF_Poll) selon ordre association• AP peut interroger une station et acquitter données d ’une

autre dans même trame : piggybacking




> Inter trames?• Point Inter Frame Space : utilisée par AP avant envoi beacon

début CFP, pour reprendre le canal pendant CFP (si un ACK est perdu)

• SIFS: utilisée pour chaque envoi de trame pendant CFP=> PIFS permet à AP de démarrer CFP

PIFSSIFS

= 30 µs pour DSSS= 10 µs pour DSSS

PIFS donne

une priorité sur DIFS

DIFS = 50 µs pour DSSS



Point Coordination Function (PCF)> Echange en PCF

SIFSD1+Poll

Da + Ack

Ack+PollSIFS

SIFS SIFSAck

SIFS

B End

CPCFP

NAV

PIFS

Ap voit le medium libre pendant PIFS Ap envoi le beacon de début CFP Les stations mettent à jour NAV AP envoi donnée à station1 et l ’interroge Station1 envoi données à AP et acquitte réception Station2 n’a pas de données à envoyer AP annonce fin CFP, les stations mettent NAV=0

Stations

AP




> Echanges en PCF

SIFSD1+Poll D2+Poll

SIFS Ack

SIFS

B End

PIFS PIFSCP

NAV

CFP

Ap ne reçoit pas ACK de station1 après SIFS,

donc reprend le contrôle du canal après PIFS

et continue son polling

AP

Stations




> Echanges en PCF

Station1

Station2 Station3

APPoll

Data pour station 2

Ack pour station1, Data de station1 et Poll

Ack et Data pour station4

Ack pour station2

et Poll

Station4 non pollable

1 321 2 3

Data de station2Ack

Interrogations

Ack


Mécanismes MAC 802.11 (20/31)Econonomie d ’énergie

> En mode infrastructure• Station PS indique son mode par bit de header Mac et AP

conserve messages pour elle• Station en PS mode => réveil périodique pour recevoir un

beacon TIM (Traffic Information Map) / DTIM (Delivery)• En CP, station peut réclamer ses trames (PS_POLL) si le bitmap

TIM indique du trafic pour elle. • En CFP, reste éveillée jusqu’à réception• Bit More Data entête MAC indique si reste trafic



> En mode infrastructure

DTIM annonce aux stations le trafic broadcast/multicastTIM annonce aux stations trafic unicast

DTIMTIM TIM TIM TIM TIM TIM

DTIM DTIM DTIM

beacons

Début CFP Début CFPCFP CP



Station

Demande si CP Attend si CFP

1Trames attente? 1 0Station PS 1 4 5

TIM=bitmap

A du trafic en attente Pas de trafic en attente

Retourne en PS

AP



> En mode ad hoc• station source conserve messages pour station en PS mode et

lui annonce son trafic lors fenêtres ATIM• ATIM window => après beacons, les stations se réveillent et

attendent ATIM pendant cette fenêtre au max (taille dans beacons)

• Station réveillée doit acquitter ATIM et reste éveillée pour recevoir ses trames (ATIM retransmis par source si pas acquittées)

• Trames broadcast ou multicast => ATIM concernant ces trames sont envoyées avant et ne doivent pas être acquittés (le trafic est envoyé tout de suite après)


Mécanismes MAC 802.11 (24/31)Fragmentation

> Utile si support pas fiable pour longues trames

NAV



Authentification

> Trames authentification request/response> 2 modes:

• open system• shared key

> Element status permet dire si authentifieur accepte ou refuse

> Authentifieur = AP (infrastructure)/station (ad hoc)



Authentification

> Open system

Authentifieur vérifie uniquement que le client est dans le même

mode

AP ou stationAuthentification request1

Authentification response2



Authentification

> Shared key

Authentifieur vérifie que client a la même clé

AP ou stationAuthentification request1

Challenge text string2

Text encrypted with shared key3

Response based on challenge4

WEP key WEP key



Cryptage Wired Equivalent Privacy (WEP)

> Clé symétrique secrète (40 bits, wifi ou 104 bits non standard) combinée à vecteur d’initialisation (IV de 24 bits) différent par trame

> Est indiqué dans l’entête MAC (qui, elle, n’est pas cryptée) par un bit WEP

> Utilisation est recommandée pour un minimum de sécurité



Cryptage Wired Equivalent Privacy (WEP) > Cryptage



Cryptage Wired Equivalent Privacy (WEP) > Décryptage



Cryptage WEP

> Limites du WEP : • Clé statique (pas d ’utilitaire pour changer)• Initialisation Vecteur (24 bits) en clair => seulement 224 graines

pour RC4 car clé statique donc 16.777.216 Sequence Key • Integrity Check Value linéaire donc faible => possibilités de

changer des bits dans données et de changer ICV pour qu ’il soit correct


Agenda

> Mode de fonctionnement des WLAN > 802.11 couche MAC> Limites de 802.11 pour la QoS> 802.11e et les nouveaux mécanismes


Limites de 802.11 pour la QoS (1/2)

Problèmes liés à DCF

> Best Effort => aucune garantie> Pas de priorité pour stations se disputant accès au canal > L ’accès à Contention cause des collisions, des pertes et

engendre des délais variables , ces problèmes augmentent avec le nombre de stations

> Lorsqu’une station prend le canal, elle peut émettre une trame qui peut être de longueur variable => pas de contrôle sur temps d ’occupation


Limites de 802.11 pour la QoS (2/2)

Problèmes de PCF

> Coexistence avec DCF : si au moment de commencer CFP, le canal occupé, on attend et CFP est rétréci => pas d ’accès périodique pour les stations de la polling liste

> Lorsque AP donne la parole, station peut émettre une trame plus ou moins longue => pas de contrôle sur les temps de parole et pas de garantie d ’accès périodique

> Méthode interrogation round robin pas efficace pour différenciation de trafic


Agenda

> Mode de fonctionnement des WLAN > 802.11 couche MAC> Limites de 802.11 pour la QoS> 802.11e et les nouveaux mécanismes


802.11e et les nouveaux mécanismes (1/24)

> 1 seule fonction d ’accès : • Hybrid Coordination Function (HCF)

– Améliorations de DCF => EDCF (pendant CP)– Amélioration de la méthode de Polling (pendant CP ou CFP)

seulement en mode infrastructure

> Direct Link Protocol> Block Acknowledgement Mechanism> Economie d ’énergie

(Etude Basée sur le draft IEEE 802.11e de février 2003)


802.11e et les nouveaux mécanismes (2/24)Hybrid Coordination Function

Mode ad hoc :

EDCF seulement

Mode infrastructure : 2 possibilités

EDCF+Polling

EDCF seulement

(PCF inclus dans polling donc compatibilité 802.11)

Polling EDCF

DCF

Pendant

CFP ou CP

Pendant

CP

HCF

PCF



> 2 types de trafic supportés selon Traffic IDentifier• trafic avec priorités => TID de 0 à 7 (tag 802.1d) • trafic paramétré => TID de 8 à 15 (on parle de TSID)

> 2 méthodes d ’accès au canal:• Accès compétition ou Enhanced DCF => priorités• Polling par AP (mode infrastructure) appelé Hybrid Coordinator

(HC) => trafic paramétré> Opportunités transmission et bursting



> Enhanced DCF• Trafic arrive avec TID de 0 à 7 => définit des Traffic Category

(TC) dans une même station• TC sont mappés dans 4 files : Access Category (AC)• Chaque AC fait DCF avec des paramètres différents

– Inter trames (DIFS en DCF, AIFS[AC] en EDCF)– taille fenêtre backoff (Cwmin[AC], Cwmax[AC])– augmentation de fenêtre backoff propre (Cw x PF[AC])=> permet de garantir un accès suivant les priorités



> Enhanced DCF mapping



> Enhanced DCF : • deux AC dans une même station

AC2 backoff

AC1 backoff

trame

trame

Fin échange précédentCanal libre

AIFS[AC2]<AIFS[AC1], Cwmin[AC2]<Cwmin[AC1]

AC2 prioritaire

AIFS[AC1]

AIFS[AC2]

AIFS[AC2] AIFS[AC1]



> Enhanced DCF• deux AC dans même station• file i prioritaire sur j

AIFS[i]

AIFS[j]0 CW[i] CW[j]

Fenêtres backoffCwmin[i]<Cwmin[j]

Cwmax[i]<Cwmax[j]

Canal occupé

j

i



> Enhanced DCF• En cas de collision entre deux AC dans même station, un

scheduler donne le canal au TC prioritaire et autre TC fait une retransmission

• Les AC se comportent comme des stations virtuelles au sein d’une même station

• Chaque AC est une variante de DCF



> Accès Polling : Négociation trafic• Trafic contient un TID de 8 à 15 => négocier paramètres

requis par l’application • Paramètres : débit, temps supportable entre deux émissions,

délais supportés, longueur nominales trames...• Négociation avec HC (scheduler dans HC) par trames Action • Création flux (logique) pour une application si négociation OK

=> traffic stream (TS)



> création Traffic Stream (uplink/downlink)• TS a une direction => 2 TS pour uplink et downlink (initié par

la station)

SchedulerMAC layer

MAC layer

QoS Station

QoS AP

Trafic with TID=8…15

TSPEC Status

ADDTS request

ADDTS response

TSPEC

Schedule elt



> Accès Polling : • HC fait polling aux instants prévus pendant négociations• Traffic stream => interrogations périodiques • Polling pendant CP ou CFP• Polling de stations non-QoS possible (compatibilité) pendant

CFP• Prise contrôle canal par HC pour polling en utilisant PIFS



> Transmission Opportunities (TXOP)• Période prédéfinie pendant laquelle station a droit émission• Obtenu par accès EDCF => EDCF-TXOP

– durée dépend de AC et est donnée dans les beacons ou probe req• Par Polling des TS => Polled-TXOP (durée dans CF_Poll)• Protégé par NAV et ne doit jamais être dépassé• Si une station n ’a pas de temps dans TXOP ou a fini émission,

envoi trame QoS Null (avec soit queue=0 soit durée = durée nécessaire -> demande TXOP plus long)



> Contention Free Burst (CFB)• mécanisme consistant à émettre plusieurs trames pendant

TXOP (EDCF bursting pour EDCF-TXOP)

EDCF-TXOP

Data1 Data2 Data3

SIFS SIFS SIFS SIFS

AckAck



> EDCF-TXOP et CFB

ACi backoff

Autres stations

Canal libre

NAV

Durée TXOP Limit contenue dans les beacons ou probe response

D1

SIFS

D2

EDCF-TXOP

AIFS[ACi]

SIFS

ACKAP



> EDCF-TXOP et CFB

ACi backoff

Autres stations

Canal libre

NAV

D1 n ’est pas acquitté par HC, retransmission après PIFS

EDCF-TXOP

…...AIFS[ACi] D1 D1

PIFS



> EDCF-TXOP et CFB

AP

Autres stations

Canal libreEDCF-TXOP

D1 et D2 ne sont pas forcément destinés à la même station

Les stations recevant des données devant être acquittées envoient ACK

…...

NAV

Slot

time

PIFS D2

SIFS

D1

ACK

SIFS



> Polled-TXOP et CFB

AP

Station interrogée

Canal libre

Poll

D1

Polled-TXOP

SIFS

ACK

SIFS

Station utilise champs QoS Control de QoS CF_Ack si veut changer ses besoins

SIFS

PIFS D2 +ACK


802.11e et les nouveaux mécanismes (18/24)Direct Link Protocol

> En mode infrastructure, 2 stations peuvent se parler directement (sans passer par AP)

> Initialisation du Direct Stream par une station et passe par AP => gestion Power Saving mode

> Une fois le lien créé, les stations communiquent directement et l’initiateur peut tester ce lien

> Si lien inactif pendant timeout, trafic repasse par AP


802.11e et les nouveaux mécanismes (19/24)Direct Link Protocol

Station1 Station2

APDLP request

-@mac stations,

-capabilities,

-supported rates

DLP request

-@mac stations,

-capabilities,

-supported ratesDLP response

-@mac stations

-capabilities

- supported rates

- status

DLP response

-@mac stations

-capabilities

- supported rates

- status

DLP Probes

Timeout

Si une station ne reçoit rien pendant timeout, direct stream terminé


802.11e et les nouveaux mécanismes (20/24)Block Acknowledgement

> Possibilité d’agréger les ACK pour plusieurs trames > Toutes les trames du bloc sont séparées par SIFS> Lorsque émission terminée, source demande ACK> Initialisation par demande au récepteur qui accepte (dit la

taille des buffers alloués) ou refuse; fin si plus utile, ou après timeout sans réception

> Signalé par Ack policy de header des trames QoS



> Block Ack contient un bitmap qui liste les trames reçues> Toute trame non reçue est réémise> Une station ayant initialisé le mécanisme peut utiliser Ack

normal (indiqué dans champ Ack policy QoS control) puis repasser en mode par bloc

> Block Acknowledgement peut être « immediate » ou « delayed »



> immediate

HC

Originator

Recipient

Data Block

Exchange

TXOP Limit

NAV Reservations

HC

Originator

RecipientAck Policy = Block Acknowledgement

Block AckExchange

TXOP Limit

NAV Reservations



> delayed

HC

Originator

RecipientAck Policy = Block Acknowledgement

Exchange

TXOP Limit

NAV Reservations

NAV Reservations

HC

Originator

Recipient

Data BlockBlock AckExchange

TXOP Limit

NAV Reservations

NAV Reservations


802.11e et les nouveaux mécanismes (24/24)Economie d ’énergie

> mécanismes supplémentaires• Station prévient HC qu ’elle veut faire économie d ’énergie

lors (ré)association ou par trame APSD QoS Action => contiennent wakeup period de la station

• Station PS indique son mode par bit de header Mac et AP conserve messages (avec les priorités et ordre d ’arrivée)

• Station en PS mode => réveil périodique pour recevoir (D)TIM et reste éveillée si message pour elle

• Station ayant un TS reçoit ses trames lors du Service

QUESTIONS ?


802.11e et les nouveaux mécanismes

Hybrid Coordination Function

> TSPEC ?• Nominal/Max MSDU size• Min/Max service interval • Inactivity Interval• Min/Mean/Min PHY/Peak data rate• Delay Bound=> permet au scheduler de HC de calculer un Schedule

element et de répondre oui/non/propose alternative à station

hhhhhhh


802.11e et les nouveaux mécanismes

Hybrid Coordination Function

> Schedule element ?• Min/Max Service Interval• Min TXOP duration• Max TXOP duration• Specification Interval=> indique à station quand elle sera interrogée si un TS est créé

hhhhhhh

Documents

Les mécanismes de base de 802.11 et les propositions de 802.11e pour la QoS