Gestion agrégée de la bande passante pour IEEE 802.16 WiMAX 

HCF : une fonction d’accés au médium avec QoS

HCF (Hybrid Coordination Function) est utilisée uniquement dans ce que le standard appelle un réseau QoS (c’est le réseau où le point d’accès met en place un HC-Hybrid Coordinator). La modification IEEE 802.11e (802.11e 05) a introduit cette nouvelle méthode ainsi que d’autres mécanismes afin d’apporter certaines propriétés QoS au niveau de l’accès. HCF introduit des modifications à DCF et PCF ainsi qu’un certain nombre de mécanismes et de types de trames permettant la mise en place de transferts avec qualité de service pendant la CP et la CFP. HCF introduit la notion d’opportunité de transmission (TXOP) qu’une QoS-STA peut obtenir en utilisant l’une des méthodes d’accès d’HCF : la méthode d’accès avec contention EDCA (Enhanced Distributed Channel Access) ou la méthode d’accès par scrutation (HCF Controlled Channel Access). L’obtention d’un TXOP peut permettre l’envoi d’une ou plusieurs trames. Si TXOP vaut 0, une seule trame données peut être envoyée par opportunité de transmission.

EDCA

EDCA (représentée par la figure 1.3) apporte à l’accès par contention de 802.11 la différenciation. La méthode définit quatre catégories d’accès (AC) qui ont des propriétés différentes à l’accès. Une proposition de correspondance est établie entre la valeur UP (User Priority définie par 802.1D) et les 4 ACs, elle est détaillée dans le tableau 1.1

HCCA

HCCA est une implémentation d’un accès par scrutation. Il met en place des améliorations par rapport à PCF. La division de la supertrame en CP et CFP cesse d’être importante lorsque la fonction HCCA est employée. Cette division continue à exister afin de permettre aux nonQoS STA de fonctionner dans un réseau QoS. Cependant, HCCA permet au HC d’intervenir durant une CP ou une CFP pour mettre en place une scrutation. L’accès du HC pour ce genre de procédure se faisant avec une temporisation PIFS qui est inférieure aux AIFS, cet accès devient ainsi plus prioritaire que les accès par EDCA. La scrutation est mise en place grâce à une connaissance supposée du HC de l’état des files des stations au sein de la BSS.
Durant la CP, une QSTA peut accéder au médium si elle y parvient par EDCA, ou si elle yest explicitement invitée par un paquet CF-POLL envoyé par le HC. Le HC peut accéder au médium afin de scruter les QSTA (envoie d’un paquet CF-POLL) suite à une période PIFS d’inactivité du médium. Durant la CFP, les QSTA ne peuvent accéder au médium à moins qu’elles y soient explicitement invitées par un paquet CF-POLL envoyé par le HC. Le HC peut s’accorder un TXOP pour un envoi sur la voie descendante ou peut envoyer un paquet de scrutation CF-POLL suite à une période PIFS d’inactivité du médium.
Un paquet CF-POLL contient une valeur TXOPLimit, indiquant à la station scrutée la durée d’utilisation du médium à ne pas dépasser.

Les mécanismes supplémentaires de QoS

Le standard (80211 07) présente différents mécanismes, complémmentaires à HCF, permettant d’offrir une QoS pour l’accès 802.11. L’essentiel de ces mécanismes fut introduit par la modification IEEE 802.11e (802.11e 05). Nous en exposons certains dans ce paragraphe, celui qui nous intéresse étant essentiellement le contrôle d’admission.

Le contrôle d’admission

Un cadre pour le contrôle d’admission a été mis en place par la modification 802.11e. Ce cadre concerne l’accès par HCF avec ou sans contention (par EDCA ou par HCCA). Le contrôle d’admission servira à la gestion et la régulation de la bande passante disponible. Une QSTA souhaitant avoir des garanties de QoS (sur les délais d’accès, sur les débits ou sur le taux de pertes par exemple) devra passer par le contrôle d’admission. Les algorithmes de contrôle d’admission ne sont pas définis par le standard, le choix de l’algorithme utilisé est laissé à l’équipementier. Le standard définit cependant un cadre et un certain nombre de règles que les algorithmes devront respecter.
Pour EDCA Le point d’accès peut annoncer les ACs qui sont soumises au contrôle d’admission (en réglant le champs ACM – Admission Control Mandatory dans les annonces des paramètres EDCA des ACs). Il est à noter que ce champs doit rester statique, le choix des ACs soumises à un contrôle d’admission doit rester le même tout au long de la vie de la BSS. Si une AC est soumise au contrôle d’admission, alors toutes les ACs qui sont de plus haute priorité le sont aussi. Lorsqu’ une QSTA souhaite utiliser une AC soumise au contrôle d’admission pour un nouveau flux, la QSTA envoie une requête ADDTS (ADD Traffic Stream) précisant l’AC utilisée, le sens du flux (montant, descendant ou bidirectionel) et la spécification du nouveau flux (TSPEC). En réponse à une requête ADDTS, l’AP renvoie une réponse ADDTS précisant si le nouveau flux est accepté ou refusé. Les règles de prise de décision d’ac- 16 Chapitre 1. État de l’art cepter ou de refuser un nouveau flux (autrement dit, l’algorithme de contrôle d’admission) n’est pas spécifié par le standard. Un exemple d’algorithme est donné en annexe du standard , cet exemple n’est pas obligatoire. Si un flux se voit refuser l’accès, il doit soit utiliser une AC de moindre priorité, non soumise au contrôle d’admission soit renégocier l’admission en spécifiant un nouveau TSPEC. Lorsque le flux arrive à sa fin d’activité, la QSTA envoie à l’AP un message DELTS (DELete Traffic Strem) le lui signalant. À chaque EDCAF sont associéesdeux variables qui devront être mises à jour par l’EDCAF. Ces variables sont admitted_time (représentant le temps médium que le contrôle d’admission a accordé à cette AC) et used_time (représentant le temps médium consommé par l’EDCAF). L’EDCAF est contrainte de respecter la limite spécifiée par la variable admitted_time. Si les conditions du réseau se dégradent emmenant la station à réduire son débit physique, les EDCAF des AC soumises au contrôle d’admission se doivent de continuer à respecter la contrainte admitted_time, une nouvelle demanded’admission peut être envoyée afin de palier au manque de bande passante induit.
Pour HCCA Le contrôle d’admission au niveau de HCCA est essentiel pour que HCCA puisse fournir un service avec une qualité de service paramétrée. Le contrôle d’admission est dans le cas de HCCA couplé à une politique d’ordonnancement qui assurera la qualité de service demandée. La procédure d’ajout ou de suppression de flux est identique à celled’EDCA. L’algorithme de contrôle d’admission n’est pas spécifié dans le standard mais des règles d’usage sont fixées. Un HC ayant accepté un nouveau flux ne peut en aucun cas le modifier ni l’annuler sans qu’il y ait eu expressément une demande de la part de la QSTA concernée. Le but de HCCA est d’offrir des garanties à des flux (en considérant que le réseau évolue dans un environnement contrôlé), il est donc important que le contrôle d’admission etl’algorithme d’ordonnancement y veillent.

Autres mécanismes de QoS introduits par IEEE 802.11e

Block ACK Cette procédure optionnelle permet d’améliorer l’utilisation du médium. En effet, elle permet à une station d’envoyer plusieurs paquets sans que ceux-là soient acquittés individuellement. Le bloc de paquets pourra être acquitté à la fin de l’envoi du bloc ou dans un TXOP ultérieur. L’utilisation du réseau s’en trouve ainsi améliorée.
Direct Link Protocol Si DLP (Direct Link Protocol) est activé au sein d’une BSS, les QSTA peuvent communiquer directement sans avoir à passer nécessairement par l’AP. DLP permet d’améliorer l’utilisation de la bande passante.
Respect des échéances D’autres modifications ont été introduites par IEEE 802.11e permettant d’améliorer le respect des échéances en contraignant les durées d’accès des stations :
– Les stations utilisant le médium sont contraintes de respecter le TBTT annoncé par le paquet Beacon. Une station voulant accéder au médium doit vérifier que la transmission entamée (jusqu’à la réception éventuelle du ACK) ne doit pas dépasser le TBTT annoncé. Le CFP ne sera, par conséquent, pas retardé par les stations accédant au médium.
– Chaque accès au médium se fait dans la limite de l’opportunité de transmission (TXOP) accordée. La valeur du TXOP est fixée par le HC.

IEEE 802.11 17

Revue de la littérature

Depuis le début du processus de standardisation de 802.11, beaucoup de travaux de recherche se sont intéressés à différents aspects de ce standard, dans la volonté de l’évaluer et d’en améliorer la performance. Nous nous intéresserons dans cette revue de la littérature aux travaux récents qui ont eu pour objet les améliorations du standard IEEE 802.11 se rapportant à la qualité de service (essentiellement celles apportées par la modification IEEE 802.11e (802.11e 05)).
Certains des travaux présentés ci-dessous n’ont pas forcément de rapport direct avec la contribution de cette thèse, ils ont cependant apporté une brique à la réflexion et méritent donc pour cette raison d’être cités. Ainsi, étant donnée la nature large de cette revue de littérature, le placement de nos travaux par rapport à la littérature se fera dans les chapitres présentant nos contributions. Il est possible de diviser les travaux en plusieurs catégories :
– Les travaux sur l’évaluation de la performance des techniques d’accès du standard.
L’évaluation de performances a été réalisée, soit avec des modèles analytiques, soit avec la simulation, soit sur des plateformes de test.
– Les travaux sur les aspects cross-layering.
– Les travaux sur les mécanismes de QoS, couvrant à la fois des travaux sur l’amélioration du schéma d’accès, des travaux sur l’ordonnancement ou des travaux sur le contrôle d’admission. Certains autres travaux sont allés jusqu’à proposer des architectures de QoS pour IEEE 802.11.

Travaux sur l’évaluation de performances

Plusieurs modèles analytiques ont été réalisés avec comme principal but l’analyse de performances de 802.11. À commencer par (Bianchi 00) qui proposa l’un des premiers modèles pour DCF. Vinrent ensuite (Kong 04), (Wang 05a), (Engelstad 05), (Clifford 06), (Sharma 06), (Wu 06) entre autres travaux qui proposèrent des modèles d’EDCA et analysèrent ses performances. Nous présenterons quelques uns de ces modèles dans le paragraphe 2.1.
D’autres travaux d’analyse de performances ont utilisé des outils de simulation. (Mangold 02) analyse l’équité d’EDCA dans un environnement avec chevauchement de BSS. (Mangold 03) est l’un des premiers papiers à proposer une analyse complète par simulation de HCF. Ce papier montre l’amélioration qu’apporte HCF du point de vue de la QoS par rapport aux schémas d’accès classiques. Il compare aussi les performances d’EDCA à celles d’HCCA dans différentes conditions réseau. (Garg 03) évalue la performance de EDCA et de HCCA et étudie la possibilité d’un changement des paramètres d’accès d’EDCA.
Plus récemment, (Ng 05) et (Dangerfield 06) ont réalisé une étude sur plateforme de test de IEEE 802.11e avec des applications TCP ou Voix sur IP.

Intégration dans un réseau hybride

À un autre niveau, (Chen 05) propose une méthode pour décider dynamiquement de la durée des sous-trames montantes et descendantes en mode TDD réduisant ainsi le gaspillagede bande passante. (Mukul 06) propose un système d’ordonnancement et un système de requête adaptatif permettant d’assurer un meilleur service au flux rtPS. (Delicado 08) propose et analyse une modification du système de requêtes afin de réduire la période montante où l’accès se fait avec contention.

Travaux sur le Cross Layering

Les études sur les aspects Cross Layering se sont intéressés aux couches supérieures et aux couches inférieures à la couche MAC. (Alexander 06) propose une manière d’intégrer les mécanismes QoS de 802.16 dans une architecture avec une couche session basée sur SIP afin de permettre un meilleur transport de la voix sur 802.16. (Yahiya 08) propose un système intégrant des informations du niveau physique pour assurer la satisfaction de contraintes dedélai des flux contraints.

Intégration dans un réseau hybride

D’autres travaux se sont intéressés aux réseaux hybrides sans fil, l’intégration des mécanismes permettant de fournir une qualité de service aux applications utilisant ce genre de réseau. (Nie 05) donne un algorithme de prise de décision pour le handoff entre réseaux coexistants sans fil employant des technologies différentes. (Soundararajan 07) propose une solution pour réduire les délais que subit les applications voix sur IP en traversant un réseau hybride 802.11
– 802.16. (Takizawa 07) se concentre plutôt sur la ressource radio qui devient difficile à gérer dans un environnement où divers réseaux sans fil coexistent. (Ali-Yahiya 08) propose une architecture générale pour l’interconnexion de réseaux sans fil basés sur le standard IEEE 802.21 et qui permet une mobilité transparente pour les utilisateurs.

Modélisation de la vue comportementale globale réduite

Modèle intermédiaire

Le modèle intermédiaire que nous présentons dans la figure 2.23 représente essentiellement le comportement Binary Exponential Backoff : composante principale de l’évitement de collision dans CSMA/CA. Nous présentons ce modèle intermédiaire pour deux raisons : en premier, le modèle détaille les différentes étapes de collision que pourrait subir un paquet en cours de sa transmission. Ceci permettra une éventuelle étude à ce niveau. La seconde raison, qui est plutôt une raison de présentation et de compréhension, est que le modèle intermédiaire correspond au schéma que nous présentions dans la figure 2.1, ceci permettra au lecteur de remettre chacun des modèles ou des blocs réduits dans le contexte du comportement d’une catégorie d’accès EDCA.
Dans la figure 2.23, les états ( j, −2, A) (avec 1 ≤ j ≤ m + h) représentent les états où une période AIFS est décomptée suite à une collision, avant la reprise d’une tentative de transmission. L’état (0, −2, A) représente le début de la première tentative de transmissiond’un paquet. Les états ( j, −2, 1) (avec 0 ≤ j ≤ m + h) représentent les différentes étapes de Backoff . Celles-ci sont suivies soit par une collision (transition vers l’état ( j + 1, −2, A)) ou par une transmission avec succès (représentée par l’état (−1, −1, dTs e)). Si l’état de Backoff (m + h, −2, 1) est suivi d’une collision, le paquet est rejeté. Nous avons introduit un nouvel état (m + h, −1, 0) représentant cette situation où le paquet est rejeté. La transition entre les états (−1, −1, dTs e) ou (m + h, −1, 0) et l’état (0, −2, A) représente la décision prise par la fonction d’accès d’entamer la transmission d’un nouveau paquet suite respectivement à une transmission avec succès ou à un rejet de paquet. Les différents temps de séjours et probabilités de transition utilisés dans ce graphe sont : – T A représente la durée de la première période A.

Présentation de l ’algorithme

Le fonctionnement général de l’algorithme de contrôle d’admission est le suivant : l’algorithme fonctionnera au niveau d’une entité centrale qui aura pour charge de protéger les flux actifs, cette entité peut être le point d’accès par exemple. À l’arrivée d’un nouveau flux, un calcul sera effectué afin de savoir si ce nouveau flux peut être admis ou non, l’algorithme se pose à ce niveau deux questions distinctes : est ce que le flux aura ce qu’il a demandé s’il est admis ? et est-ce qu’en l’admettant, la qualité perçue par les flux déjà admis ne sera pas dégradée ? Ceci est ce que nous appellerons par la suite le processus de décision. Ce processus sera formalisé. Afin de pouvoir répondre à ces questions, l’algorithme construit une vue de l’état du réseau (débit maximal de chaque AC active du réseau). Cette vue sera déduite, dans notre proposition, en couplant deux aspects :
1. Le modèle réduit que nous avons présenté précédemment est un premier élément. Ce modèle permettra à l’algorithme de calculer le débit maximal que peut atteindre une catégorie d’accès EDCA lorsqu’elle est placée dans un certain contexte réseau.
2. Le deuxième aspect est la connaissance qu’aura l’algorithme de contrôle d’admission de l’état du réseau. Le contexte réseau que le modèle utilise est représenté par des mesures faites de l’état du réseau ainsi que des estimations effectuées en se basant surces mesures. Les mesures concerneront la probabilité d’occupation du médium ainsi que des probabilités de collisions des files.

Table des matières
Liste des figures 
Introduction 
1 État de l ’art 
1.1 IEEE 802.11
1.1.1 Introduction aux standards IEEE 802.11
1.1.2 La couche physique
1.1.3 La couche MAC
1.1.4 DCF
1.1.5 PCF
1.1.6 HCF : une fonction d’accés au médium avec QoS
1.1.7 Les mécanismes supplémentaires de QoS
1.1.8 Revue de la littérature
1.2 IEEE 802.16
1.2.1 Introduction aux standards IEEE 802.16
1.2.2 La couche physique
1.2.3 La technique d’accès
1.2.4 QoS pour IEEE 802.16 : la gestion de la bande passante montante
1.2.5 Travaux autour de la QoS pour IEEE 802.16
2 Un modèle du schéma d’accès de IEEE 802.11e EDCA 29
2.1 Sur des modèles analytiques existants
2.1.1 Le modèle de DCF présenté par Bianchi
2.1.2 De DCF vers EDCA
2.2 Notre proposition : un modèle du comportement d’une AC EDCA intégrant la collision virtuelle
2.2.1 Vue comportementale d’une AC
2.2.2 Un modèle en blocs : bases de la modélisation
2.2.3 Détail des blocs
2.2.4 Construction du modèle général
2.2.5 Comparaison qualitative au modèle de Kong et al
2.2.6 Utilisation du modèle
2.3 Réduction du modèle
2.3.1 Les règles de Beizer
2.3.2 Première phase de réduction : par bloc
2.3.3 Modèle de la tentative d’accès j
2.3.4 Modélisation de la vue comportementale globale réduite
2.3.5 Le modèle réduit
2.3.6 Métriques dérivées du modèle réduit
2.4 La problématique de la gestion des collisions virtuelles : proposition d’une stratégie
2.4.1 Contexte
2.4.2 Description du problème
2.4.3 Propositions de modification
2.4.4 Analyse
Conclusion
3 Un contrôle d’admission hybride pour IEEE 802.11e EDCA 
3.1 Présentation de l’algorithme
3.1.1 L’algorithme
3.1.2 Mesures et estimations
3.2 Analyse et évaluation
3.2.1 Une catégorie d’accès par station
3.2.2 Plusieurs catégories d’accès par station
3.3 Amélioration de l’algorithme
3.3.1 Information supplémentaire sur l’état du médium
3.3.2 Correction d’estimation
3.3.3 Analyse des modifications
3.3.4 Conclusions
3.4 Implémentation de l’algorithme
3.4.1 Contexte : l’architecture EuQoS
3.4.2 Contexte : les composants matériels
3.4.3 Intégration du contrôle d’admission
3.4.4 Bilan
Conclusion
4 Gestion agrégée de la bande passante pour IEEE 802.16 WiMAX 
4.1 Notre proposition
4.1.1 Définition des moyens
4.1.2 L’algorithme de contrôle d’admission
4.1.3 Construction dans les SS des requêtes agrégées
4.1.4 Répondre dans la BS aux requêtes agrégées : les allocations
4.1.5 Allocation de slots par la SS aux flux
4.1.6 Ajout de flexibilité : les politiques d’anticipation
4.2 Sur le comportement de type serveur Latency Rate-LR de la proposition
4.2.1 Les serveurs de type LR
4.2.2 Démonstration
4.2.3 Propriétés des algorithmes d’ordonnancement de type LR
4.2.4 Lien de notre proposition avec les serveurs LR
4.3 Analyse
4.3.1 Contexte de l’analyse
4.3.2 Scénarios de simulation
4.3.3 Résultats et interprétation
Conclusions et perspectives 
Conclusion générale 
A Calcul de la matrice des probabilités en régime stationnaire
A.1 Le bloc backoff
A.2 Les blocs « Résultats d’une tentative de transmission »
A.2.1 Le bloc transmission avec succès
A.3 Le bloc collision
A.4 Le bloc AIFS
A.5 Récapitulatif total
A.5.1 Le bloc backoff
A.5.2 Le bloc transmission avec succès
A.5.3 Le bloc collision
A.5.4 Le bloc AIFS
A.6 Équation d’harmonie
A.6.1 Le bloc backoff
A.6.2 Le bloc AIFS
A.6.3 Le bloc collision
A.6.4 Le bloc Transmission avec succès
A.6.5 La somme générale
Bibliographie

Lire le rapport complet