1

Approches inter-couches pour la QoS dans les réseaux locaux sans fil

Stéphane Lohier

2

1. Solutions « Cross-Layer »Une autre approcheUtilisation d’un plan de contrôleÉchange direct de métriques

2. Amélioration de TCP sur les liens 802.11Perte de signal ou congestion TCP ?Solution : MAC-layer LDA + Cross-layer LDARésultats et synthèse

3. Routage QoS dans les réseaux ad hoc 802.11Cross-layer pour les mesures de délai et de BPRoutage QoS réactif avec AODVÉvaluation de la solution

4. Conclusion et perspectives

Plan

2

3

1. Solutions Cross-Layer

Cross-Layer : les protocoles sont conçus ou utilisés en exploitant les dépendances ou les interactions entre les couches dans le but d’améliorer les performances.

Par opposition au Layering : protocoles conçus séparément, avec un mécanisme « decode and forward ».

Layering suffisant pour les réseaux filaires.

Cross-Layer utile pour les réseaux sans fil :ajustement dynamique des paramètres TCP suivant la qualité du canal ;choix des routes dans un réseau ad hoc suivant la qualité des liens ;adaptation des temps d’accès au support suivant les contraintes des applications temps réel…

4

Cross-Layer : une autre approche

Violation de l’architecture de référence :communication directe entre protocoles non adjacents ;échange de variables entre couches sans passer par un service ;fusion des protocoles de 2 couches adjacentes ;ajustement successif des paramètres des couches inférieures pour améliorer les performances au niveau application.

3

5

Utilisation d’un plan de contrôle

La communication entre les couches peut passer par un plan de contrôle.Exemple : Mesure au niveau MAC de :

STR : Successful Transmission RateCCR : Clear Channel Rate

Exploitation au niveau réseau pour trouver des routes sans collision ni congestion.Exploitation au niveau physique pour ajuster la puissance radio.

6

Échanges directs de métriques

Les interactions entre les couches peuvent être directes.

Exemple 1 : une indication de perte non résolue au niveau MAC est transmise à la couche TCP pour son mécanisme de recouvrement.

Exemple 2 : des mesures de métriques au niveau MAC peuvent servir des décision de routage dans un contexte ad hoc.

4

7

1. Solutions « Cross-Layer »Une autre approcheUtilisation d’un plan de contrôleÉchange direct de métriques

2. Amélioration de TCP sur les liens 802.11Perte de signal ou congestion TCP ?Solution : MAC-layer LDA + Cross-layer LDARésultats et synthèse

3. Routage QoS dans les réseaux ad hoc 802.11Cross-layer pour les mesures de délai et de BPRoutage QoS réactif avec AODVÉvaluation de la solution

4. Conclusion et perspectives

Plan

8

Beaucoup d’applications utilisent TCP sur le dernier lien sans fil (Hot Spot , SOHO…).

TCP conçu pour les réseaux filaires est peu efficace devant les pertes de signal 802.11 :

Les solutions au niveau liaison ne sont pas adaptées à 802.11 (ARQ est un mécanisme de retransmission…).

Les adaptations TCP (Jersey, Westwood…) ne sont pas optimisées pour une couche MAC 802.11 avec un premier niveau de reprise sur erreur.

Les LDA basés sur des temps TCP (RTT, cwnd, inter-arrival) sont prévus pour des pertes ponctuelles et peu persistantes.

Les solutions au niveau de l’AP (Snoop Protocol) imposent des modifications importantes du firmware.

Aucune de ces solutions ne tient compte des interactions MAC-TCP.

Étude d’une solution Cross-Layer.

Préalable : distinction entre perte de signal 802.11 et congestion TCP.

Amélioration de TCP sur les liens 802.11

5

9

Perte de signal ou Congestion TCP ?

Au niveau MAC : une trame de données non acquittée (perte ou collision) est retransmise par l’émetteur.

Le paramètre Retry Limit fixe le nombre maximum de retransmissions.Au delà, la trame est éliminée.

En principe : résolution MAC (locale) avant que TCP (bout en bout) ne soit alerté et n’interprète la perte comme une congestion.

Timeout MAC ≈ 1msTimeout TCP ≈ 1s

802.11b/g

Eth802.11b/g

Emetteur TCPRouteur/AP

RTO = 1 s1 ms

10

Perte PHY / Congestion TCP : mesures

Scénario :Transfert FTP entre 2 stations.Déplacement du récepteur mobile pour provoquer des pertes de signal.Flux UDP 802.11g pour provoquer des interférences sur la transmission 802.11b (en l’absence de trames d’avertissement CTS, un équipement 802.11b ne voit pas les transmissions OFDM).

6

11

Mesures avec déplacement

12

Mesures avec interférences

7

13

Perte PHY / Congestion TCP : analyse

Les mesures montrent :retransmissions MAC inefficaces si la fin de la fenêtre TCP est atteinte avant la restauration du canal ;retransmission TCP inefficace si elle intervient longtemps après la restauration du canal.

Solution :Augmenter dynamiquement la durée de la fenêtre de retransmission (CRD) pour éviter un Timeout TCP.Dès que le canal est restauré, TCP réagit immédiatement après la réception de 3 acquittements dupliqués (Fast Retransmit).Solution efficace pour des durées de perte inférieures au Timeout TCP.

CRD est fonction de différents paramètres au niveau MAC et TCP :

Choix : augmentation du paramètre MAC Retry Limit(configurable sur tous les équipements 802.11).

1 0( 1) ( )

cwnd RL

CST BACKOFFs i

CRD RL T T i+ =

⎡ ⎤= + +⎢ ⎥

⎣ ⎦∑ ∑

14

Perte PHY / Congestion TCP : types de perte

3 causes de perte de segments :Congestions TCP dues au trafic sur les liens ;Ruptures de signal dues aux déplacements ou aux obstacles ;Interférences dues aux autres transmissions dans la bande ISM (802.11, Bluetooth…).

L’augmentation du RL est efficace pour des pertes dues aux ruptures de signal.

Besoin de différentier les types de pertes.

Solution : MAC-Layer LDA + Cross-Layer LDA

8

15

MAC-Layer LDA : principe

Permet de différentier ruptures de signal et congestions.

Basé sur la valeur du SNR mesurée par les stations :

Si le SNR est maximum, la probabilité pour que la perte soit due àune rupture de signal est faible.

Augmentation progressive et dynamique du seuil Retry Limitsuivant SNR.

Augmentation bornée par 3 évènements :Réception d’un acquittement MAC ;Fin de la fenêtre TCP atteinte ;Timeout TCP atteint.

16

MAC-Layer LDA : résultats

Le LDA de niveau MAC et l’adaptation dynamique du Retry Limitpermettent de maintenir le flux pour des durées de perte jusqu’à 0,8 s.

9

17

Cross-Layer LDA : principe

Permet de différentier interférences et congestions.

Basé sur le nombre de retransmissions MAC pour chaque segment TCP :

Lors d’une perte de segment (3 acquittements dupliqués),Si pour un des segments de la fenêtre TCP, le seuil RL est atteint :Alors la perte est due à une interférence.

Le nombre de retransmissions MAC est disponible via la MIB 802.11.

18

Cross-Layer LDA : efficacité

En cas d’interférences, la différentiation est beaucoup plus efficace qu’avec les LDA basés seulement sur des paramètres TCP (plus de 90% des pertes sont identifiées).

10

19

Cross-Layer LDA : efficacité

En cas de congestion, la différentiation est encore plus efficace.

20

Cross-Layer LDA : amélioration de TCP

Le cross-layer LDA permet d’améliorer TCP New Reno :

Lors d’une perte de segment (3 acquittements dupliqués),

Si la perte est due à une congestion :Réaction TCP normale : cwnd = cwnd/2 RTO = 2 x RTO

Si la perte est due à une interférence :Résolution préservée : cwnd = cwnd RTO = RTO

11

21

Cross-Layer LDA : résultats

En cas d’interférences, la solution permet d’améliorer le débit moyen jusqu’à 50%.

22

Solution Cross-layer : synthèse

12

23

1. Solutions « Cross-Layer »Une autre approcheUtilisation d’un plan de contrôleÉchange direct de métriques

2. Amélioration de TCP sur les liens 802.11Perte de signal ou congestion TCP ?Solution : MAC-layer LDA + Cross-layer LDARésultats et synthèse

3. Routage QoS dans les réseaux ad hoc 802.11Cross-layer pour les mesures de délai et de BPRoutage QoS réactif avec AODVÉvaluation de la solution

4. Conclusion et perspectives

Plan

24

Routage QoS dans les réseaux ad hoc 802.11

Objectif : assurer une QoS dans les MANETs.

Cible : réseaux ad hoc fortement dynamiques et de taille limitée.

Pour préserver la réactivité : QoS intégrée au routage.

Utilise les protocoles standards sans les modifier : 802.11 et AODV.

Objectif du routage QoS : trouver une route R vers une destination D avec suffisamment de ressources disponibles pour satisfaire la requête d’une source S.

Pour les métriques de délai et de BP, il faut :

delai(R) = delai(S,A) + … + delai(B,D) < délai requisBP(R) = min {BP(S,A),…,BP(B,D)} > BP requise

Utilisation d’une solution Cross-Layer simple et réactive.

13

25

Routage avec AODV (Ad hoc On demand Distance Vector)

Routage réactif à vecteur de distance (nombre de sauts).Mémorisation temporaire des routes directes et inverses.

Réponse unicastde la destination

Recherche de route par broadcast initié par la source

26

Évaluation du délai de bout en bout

Le délai est évalué sur chaque lien de la route.

Utilisation d’un paramètre d’AODV : Node_Traversal_Time.

ntt mesuré au niveau MAC devient dynamique : nttAB = tTA + dAB

Utilisation des paquets de requête AODV munis d’extensions temporelles :nttAB = Tarrival - Timestamp

Pas de modification du standard : les extensions sont prévues par AODV.

temps de traitement et délais dans les files de A

délai de transmission entre A et B

Timestamp Tarrival

RREQS A B D

nttSA nttAB

tTA dAB

nttBD

Timestamp

14

27

Corrections sur le délai

Correction pour tenir compte de la taille réelle des paquets de données :

Pour tenir compte de la variance des délais, une moyenne pondérée par un facteur d’oubli λ est calculée au fur et à mesure :

( _ _ )' Data length RREQ lengthntt nttThroughput

−= +

0( ) (1 ) . '( )

kn

kntt t ntt t kλ λ

=

= − −∑

28

Évaluation de la BP disponible

Contraintes liées au contexte choisi :Routage réactif ;Bande passante disponible sur un lien et non sur un nœud ;Prise en compte des transmissions dans les zones de voisinage etd’interférence.

Choix d’une estimation au niveau MAC, prenant en compte directement les effets des flux voisins et interférents.

BA

C

FE

G

I1 abwABZone de voisinage de B

Zone d’interférence de B

I2 I3

I4

I5

I6I7

I8

15

29

Éstimation au niveau MAC

BP disponible :_ _

AB BUSY CW CST

Data length Data lengthabw

d T T T= =

+ +

Partie « constante » dépendant de la taille des paquets (tMPDU)

Partie variable liée à l’occupation du canal par les autres flux et à la durée de la fenêtre de contention 3 4CST RTS CTS MPDU SIFS ACK PHYT t t t t t t= + + + + +

30

Corrections sur la BP

Correction sur la longueur des paquets :

Lissage prenant en compte les mesures précédentes réalisées avec les paquets de contrôle et de données :

_' _ _

AB

Data lengthabw

dData length RREQ length

Throughput

=−+

( ) . '( ) (1 ). '( 1)abw t abw t abw tα α= + − −

16

31

Routage QoS avec contrainte de délai1. La source diffuse un RREQ avec une contrainte de délai dans l’extension.2. Soustraction du ntt sur chaque noeud et diffusion tant que la requête est possible.3. La destination répond avec un RREP muni d’une extension « délai ».4. Chaque nœud intermédiaire calcul le délai jusqu’à la destination et mémorise ce

délai dans sa table de routage.5. Une nouvelle requête pourra être traitée directement.

32

Routage QoS avec contrainte de BP

1. La source diffuse un RREQ avec une contrainte de BP.2. Comparaison avec abw sur chaque noeud et diffusion tant que la requête est

possible .3. La destination répond avec RREP muni d’une extension BP.4. Chaque nœud intermédiaire retient la BP minimum disponible jusqu’à la destination.

17

33

Notification de perte de QoS

Mécanisme de notification pour prévenir la source d’une perte de QoS (réactivité).

Activé si nttAB > old_nttAB + QDM (QoS Delay Margin).

Utilise le processus standard d’erreur d’AODV (paquets RERR vers les prédécesseurs).

Même principe si abwAB < old_abwAB - QBM (QoS Bandwidth Margin).

34

Évaluation de la solution de routage QoS

La contrainte de délai est respectée pour quasiment toutes les intensités de trafic.

18

35

Évaluation de la solution de routage QoS

La contrainte de BP est respectée à moins de 6% dans 96% des cas.

36

Évaluation de la solution de routage QoS

Moins de 12% de paquets éliminés en chemin avec la solution QoS.

(Contrainte BP)

19

37

Évaluation de la solution de routage QoS

Surcharge efficace (paquets de contrôle/paquets reçus) inférieure dans un réseau de 50 nœuds avec la solution QoS.

(Contrainte BP)

38

Conclusion et perspectives

Proposition de 2 solutions Cross-Layer :

1. Amélioration des performances de TCP sur le dernier lien sans fil :MAC-Layer LDA + Cross-Layer LDA.Amélioration des algorithmes de recouvrement de pertes.Solution implémentable sans changement du standard 802.11.

2. Routage QoS réactif dans les réseaux ad hoc :Solution complète intégrant extensions AODV, mesure de délai/BP et notification de perte de QoS.Solution performante sur des réseaux ad hoc dynamiques et de taille limitée.Pas de modification des protocoles standards (IETF AODV et IEEE 802.11).Compatible avec les derniers travaux du GT MANET sur le réactif (DYMO).

Perspectives :Optimisation des LDA (augmentation non linéaire de RL, adaptation dynamique de RTO).Estimation de abw (utilisation d’autres paramètres PHY ou MAC 802.11).Approche Cross-Layer pour le routage QoS dans les réseaux de capteurs multimédia.

20

Questions