Amélioration de la qualité WiFi maillé
Amélioration de la qualité WiFi maillé
THÈSE
Jury
Ces travaux ont été encadrés par le LIRMM, Laboratoire d’Informatique de Robo-
tique et de Microélectronique de Montpellier, Unité mixte de recherche CNRS et de
l’Université Montpellier II. Je remercie la direction de ce laboratoire de m’avoir permis
de faire ces travaux de recherche.
J’exprime ma gratitude à mon co-encadrant David ANDREU qui m’a fait découvrir
les réseaux de Petri, en cours, en stage et enfin en thèse ! Merci pour ces multiples
réunions qui ont largement fait avancer ce travail, pour ces lectures, relectures, rerelec-
tures et corrections, ainsi que pour tous ces conseils. Merci d’avoir toujours été présent
pour m’aider au niveau scientifique mais aussi administratif.
vii
viii
et la gestion d’une société à partir de sa création jusqu’à aujourd’hui. Elle m’a aussi
permis de parcourir la France pour goûter à la daube de marcassin, visiter le Croisic et
les Prairies du Lac... Je remercie aussi tous les employés : Christophe papa du hotspot,
Cyril et Guilhem installateurs d’hotspots, Yoël acheteur de pièce d’hotspot, PH, David,
Simone... et tous les nombreux autres, pour leurs bonnes humeurs et pour ce travail en
osmose dans une bonne ambiance.
Merci à mes amis et cousins de Ceilhes : Benjamin, Fabrice, Marco, Popo, les
membres du foyer ainsi que tous les autres pour les quelques fêtes cet été qui m’ont
permis de me reposer et d’être plus performant sur la rédaction de ce manuscrit.
Remerciements vii
Introduction 1
2 Etat de l’art 25
2.1 Solutions orientées couche physique . . . . . . . . . . . . . . . . . . . . . 25
2.1.1 Le WiFi maillé sur plusieurs canaux . . . . . . . . . . . . . . . . 25
ix
x Table des matières
Conclusion 157
Bibliographie 164
Glossaire 171
Résumé 176
xii Table des matières
Introduction
Contexte
Le WiFi est une certification délivrée par la WiFi Alliance [All11]. Ce consortium
assure le respect de la norme de réseau sans fil, ratifiée il y a une dizaine d’années par
IEEE sous la référence 802.11. Cet ensemble de protocoles de communication est présent
aujourd’hui sur de nombreux équipements informatiques. Il est grandement exploité
comme réseau d’entreprise ou domestique afin d’éviter de déployer des câbles. Cette
technologie se met aussi en place dans les lieux publics (aéroports, gares, hôtels...) afin de
permettre aux utilisateurs d’ordinateurs portables d’accéder à Internet lorsqu’ils sont en
déplacement. Dans ce cas, le service WiFi est apporté par des hotspots auxquels l’accès
est souvent payant. De plus, des téléphones mobiles WiFi permettent de transporter de
la voix sur Internet à moindre coût.
Pour des applications à temps critique telles que la vidéo ou la téléphonie, une
qualité de service doit être assurée. C’est pourquoi une annexe nommée 802.11e a été
ajoutée en 2005. Des études ont montré l’efficacité de ces nouvelles fonctionnalités sur
des communications audio et vidéo.
Osmozis, société innovante créée fin 2005, est opérateur de télécommunication. Son
objectif est le déploiement d’accès Internet sans fil sur de grandes surfaces, telles que
les campings, résidences de vacances, ports de plaisance ou parcs d’exposition. Cette
société a déjà installé et exploite plusieurs milliers d’équipements en service permettant
notamment aux estivants, en vacances dans un mobilhome, qui n’ont que la télévision,
la piscine, la plage et le soleil, d’avoir un accès Internet.
Cependant, l’utilisation classique du WiFi se limite à une centaine de mètres en
extérieur ou une cinquantaine de mètres en intérieur autour d’un émetteur central appelé
point d’accès. Ces éléments peuvent être connectés entre eux en filaire afin d’étendre le
réseau. Mais cette contrainte nécessite de creuser des tranchées pour les connecter en
réseau alors que ces grands espaces vont jusqu’à plusieurs dizaines d’hectares.
Dans ce contexte, le WiFi maillé est utilisé. En effet, il permet d’établir les liens
entre chaque point d’accès en WiFi afin que chacun d’eux relaye les paquets jusqu’à
leurs destinations. Cette annexe nommée 802.11s est en cours de normalisation. Dans
ce cas, la qualité de service est affectée lors des multiples relais de paquets par chaque
point d’accès du chemin déterminé car une contrainte établie par la société Osmozis est
que chaque hotspot n’ait qu’une interface WiFi et communique donc sur le même canal.
Il est donc nécessaire d’améliorer la qualité de service des transmissions, surtout quand
il s’agit de communications audio ou vidéo. Pour ceci, les propositions d’amélioration
1
2 Introduction
doivent pouvoir être appliquées sur le matériel utilisé. C’est pourquoi les leviers sur
lesquels nous jouerons doivent être concrets.
Lors d’expérimentations, il est aisé de se rendre compte de la baisse de la qualité de
service, mais la mise en évidence des problèmes de communication nécessite l’enregistre-
ment et l’analyse des transmissions radio au niveau de tous les nœuds qui sont parfois
éloignés. De plus, ces enregistrements doivent être synchronisés temporellement. Enfin,
l’environnement peut varier et comparer des résultats à des moments différents peut
laisser un doute sur un changement d’état de celui-ci. C’est pourquoi nous optons pour
un processus de recherche "Modélisation, Simulation, Amélioration". Les outils exis-
tants n’étant pas adéquats, nous proposons un nouveau simulateur, utilisant les réseaux
de Petri comme formalisme de modélisation et de simulation. L’évolutivité de celui-ci
permet des raffinements successifs en fonction des points sur lesquels l’étude doit être
approfondie.
Objectifs
Ce manuscrit a tout d’abord pour objectif de décrire les réseaux WiFi maillés avec les
éléments à améliorer. Ceci est présenté dans une première partie. Après une description
du fonctionnement, une section métrologie permet d’exposer les différentes mesures qui
reflètent la qualité de service. Ce chapitre se termine par une approche expérimentale
qui démontre d’une part l’altération de la qualité de service causée par ce type de réseau,
mais aussi la difficulté de recherche et de compréhension des causes de cette altération
en utilisant des prototypes.
Ensuite, la deuxième partie propose un état de l’art qui permet dans un premier
temps de faire une synthèse des problèmes rencontrés dans la littérature et d’étudier la
faisabilité de leurs solutions par rapport à nos contraintes. Ainsi, à partir de cette étude,
nous nous positionnons en exprimant les problèmes pris en compte et les leviers dispo-
nibles. Une recherche de simulateurs est exposée pour dresser une synthèse de l’existant.
Au regard de ce bilan et de nos choix, la mise au point d’un nouveau simulateur basé
Introduction 3
sur un modèle formel évolutif permet de répondre à nos besoins. Elle est suivie d’une
recherche de joueurs de réseau de Petri, formalisme de modélisation qui nous avons
choisi. Enfin, une dernière étude porte sur la littérature où le réseau de Petri est utilisé
pour modéliser une communication WiFi.
Un des objectifs de ce manuscrit est la description du modèle de réseau WiFi maillé.
Celui-ci est présenté dans la troisième partie qui se termine par une validation de ce
modèle.
Enfin, la quatrième partie présente la première analyse, suivie d’une première amé-
lioration proposée à l’aide de ce simulateur. En observant en détail les files d’attentes
des nœuds intermédiaires, nous remarquons que la saturation et l’encombrement de
celles-ci provoquent de fortes baisses de qualité de service. Une approche automatique
et réseaux permet alors de palier à ce problème.
4 Introduction
Chapitre 1
5
6 Le WiFi maillé, des principes au terrain
1.1.2 Topologie
La norme 802.11 définit deux topologies : le mode infrastructure, présenté figure 1.2,
où un AP joue le rôle d’élément central entre les STA afin de synchroniser toutes les
stations, et le mode ad-hoc, présenté figure 1.3, où chaque STA dialogue directement
avec les autres.
Avec du WiFi maillé [HDM+ 10], chaque MAP permet à la fois de fournir un accès
au réseau pour une station comme le ferait un point d’accès standard, mais aussi de se
connecter à d’autres points d’accès. Deux points d’accès peuvent établir un lien WDS
s’ils peuvent communiquer directement entre eux. Pour ceci, la puissance du signal WiFi,
dépendante entre autre de la distance, doit permettre à des paquets d’être transmis d’un
point d’accès à un autre, avec un nombre limité de paquets erronés ou perdus. Le débit
physique utilisé sur ce lien est lui aussi dépendant de la qualité du lien.
8 Le WiFi maillé, des principes au terrain
Comme présenté sur la figure 1.4, de proche en proche, tous les points d’accès
peuvent être connectés au même réseau WiFi maillé. De cette manière, si une sta-
tion peut se connecter à un MAP, elle pourra communiquer avec tout le réseau. Si un
MAP est connecté à Internet, la station le pourra également.
Lorsqu’un nœud émet une trame, celle-ci ne sera reçue que par les nœuds étant dans
une zone à proximité. En effet, la possibilité de réception dépend du rapport signal sur
bruit. La puissance du signal WiFi diminue en fonction de la distance et de la présence
d’obstacle ; et le bruit dépend de l’environnement dans lequel d’autres appareils peuvent
utiliser le canal radio.
Par exemple sur la figure 1.5, lorsque le nœud M P1 émet, le nœud M P2 peut avoir
une probabilité de 95% de recevoir correctement le paquet, alors que le nœud M P3
peut avoir une probabilité de 40%, et le nœud M P4 ne détectera jamais de paquet de
ce nœud. Le nœud émetteur devra choisir un débit physique adapté au lien. Dans cet
exemple, si le paquet est destiné à M P2 , M P1 pourra choisir un débit physique de 54
M bit.s−1 , ou un débit plus faible s’il est destiné à M P3 .
Pour définir une topologie, nous devons donc considérer d’une part si deux nœuds
sont à portée, et d’autre part, s’ils sont à portée, une probabilité de succès de transmis-
sion ainsi qu’un débit physique. De plus, il est possible dans des cas particuliers qu’une
transmission ait une probabilité de succès et un débit physique d’un nœud M P1 à un
nœud M P2 , et une autre probabilité et un autre débit du nœud M P2 vers le nœud
M P1 . En effet, une asymétrie peut être due à un environnement bruité.
La communication 9
1.2 La communication
Lorsqu’un paquet transite entre une station et un point d’accès, trois champs d’adresse
sont utilisés dans l’entête du paquet : BSSID, nœud source, nœud destination.
Afin d’être relayé, un paquet qui transite sur le réseau WiFi maillé contient 4 adresses
MAC identifiant les acteurs de ce relais de paquet. Le nœud source est celui qui est à
l’origine de l’introduction de ce paquet dans le réseau maillé WiFi, c’est l’émetteur
d’origine. Le transmetteur est celui qui est en train d’émettre le paquet (donc potentiel-
lement un nœud intermédiaire). Le receveur (aussi potentiellement intermédiaire) est
le nœud qui doit recevoir le paquet. Enfin, le destinataire est le dernier récepteur du
paquet.
Dans un réseau maillé, il peut y avoir plusieurs possibilités de chemins entre deux
nœuds. Ce choix ressemble au choix de routage dans un réseau IP avec des boucles.
Le terme "route" étant utilisé au niveau de la couche réseau, nous utiliserons le terme
"chemin" pour spécifier par quels nœuds sont relayés des paquets quand la réémission
se fait au niveau de la couche liaison.
De nombreux algorithmes de choix de chemin existent. Des protocoles sont proac-
tifs comme DSDV (Destination Sequenced Distance Vector) [URKRZ+ 08] ou OLSR
(Optimized Link State Routing) [DRFM08]. Ceux-ci sont adaptés à des petits réseaux.
D’autres protocoles sont réactifs comme DSR (Dynamic Source Routing) [RD09] ou
AODV (Ad Hoc On-Demand Vector) [SL09]. Ceux-là sont adaptés à des grands ré-
seaux. En effet, un tel algorithme doit pouvoir reconfigurer les chemins si un nœud
tombe en panne ou si la qualité d’un lien est modifiée.
La sélection de la méthode de choix de chemin ouvre de grandes perspectives de
recherche et de nombreux travaux ont amené des améliorations sur le sujet. Ceci pourrait
être automatisé et reconfigurable. Cependant, les nœuds de type point d’accès sont fixes
et les stations des clients ne se déplacent que très peu. Nous considèrerons donc la
topologie comme étant fixe. De plus, nous ne gèrerons pas les pannes d’un nœud. C’est
pourquoi, dans cette étude, nous spécifierons les chemins de manière statique.
10 Le WiFi maillé, des principes au terrain
La norme 802.11 définit deux modes d’accès à la couche liaison : DCF (Distributed
Coordination Function) et PCF (Point Coordination Function). La méthode d’accès
PCF propose une approche centralisée par un contrôleur nommé PC (Point Coordina-
tor). Celui-ci définit une division temporelle du canal WiFi afin de garantir un temps
de parole à chaque STA. Cependant, PCF n’est pas utilisé car les performances sont
faibles lorsque le réseau contient beaucoup de STA. De plus, le PC doit être écouté de
tous les nœuds, et il est probable qu’aucun nœud ne soit capable de jouer ce rôle dans
un réseau maillé étendu.
La méthode d’accès DCF est basée sur CSMA/CA (Carrier Sense Multiple Access
with Collision Avoidance). Celle-ci prévoit que lorsqu’un élément du réseau veut émettre
un paquet, il écoute le canal et attend qu’il soit libre. Contrairement à CSMA/CD
(Carrier Sense Multiple Access with Collision Detection) que la norme Ethernet uti-
lise, une interface sans fil ne peut pas écouter le canal et émettre en même temps. Le
CSMA/CD permet de détecter et de signaler une collision entre deux paquets émis alors
que CSMA/CA nécessite des accusés de réception pour approuver la bonne transmission
du paquet.
Lorsque qu’un élément du réseau WiFi veut émettre un paquet, il attend que le
canal soit libre. Pour ceci, il va écouter le canal pendant une durée nommée IFS (Inter
Frame Space). L’unité de cette durée est le nombre de aSlotTime (20µs). Pendant cette
attente, s’il détecte une transmission, il va attendre la fin et à nouveau écouter pendant
une durée de IFS. Comme présenté sur la figure 1.7, plusieurs durées sont possibles :
– SIFS (Short IFS) est la plus courte. Elle est utilisée avant les paquets de contrôle
ACK (accusé de réception), avant CTS, ou avant un paquet suivant un dialogue
RTS, CTS.
– PIFS (PCF IFS) est utilisée dans le cas de la méthode d’accès PCF.
– DIFS (DCF IFS) précède l’émission d’un paquet sans RTS/CTS, ou d’un RTS.
– EIFS (Extended IFS) remplace DIFS si le dernier paquet reçu est une collision ou
s’il n’est pas reçu correctement.
– AIFS[AC] (Arbitration IFS) est défini dans la norme 802.11e. Il s’agit d’un tableau
définissant une durée pour chaque classe de qualité de service définie dans la
section suivante. La valeur correspondante au type du paquet va remplacer DIFS.
– Si AIFS est utilisé est si le dernier paquet n’est pas reçu correctement, la durée
EIFS - DIFS + AIFS[AC] est utilisée.
L’accès à la couche physique 11
Si une transmission a été détectée pendant cette durée, l’émetteur compte à nouveau
ce délai dès la fin de la transmission.
Si ce délai ne suit pas immédiatement une transmission, le paquet est émis sans
attendre. Sinon, le nœud attend un nouveau délai nommé Backoff ou période de conten-
tion. En effet, si le médium est libre, il est très improbable que deux nœuds décident
d’émettre exactement au même moment. Par contre, si le médium est occupé, il est fort
probable que deux nœuds se synchronisent sur la fin de la transmission, attendent le
même délai IFS, et émettent au même moment. Ceci produit alors une collision. C’est
pourquoi ce délai aléatoire est introduit.
Le temps de Backoff est un nombre entier tiré aléatoirement entre 0 et CW (Conten-
tion Window) de constante aSlotTime (20µs). Les constantes CWmin et CWmax sont
définies pour chaque classe de qualité de service définie dans la section suivante. Lors
de la première tentative d’émission, la valeur CW est égale à CWmin . En cas d’échec de
transmission du paquet, une nouvelle tentative d’émission est programmée. A chaque
nouvelle tentative, CW est élevé au carré, moins 1, jusqu’à CWmax . Si une transmission
est reçue pendant ce délai, le processus est mis en pause, le temps de backoff attendu est
mémorisé, et le reste du temps sera attendu après un temps IFS succédant la prochaine
tentative d’émission. De cette manière, si le médium est souvent occupé, un paquet a
de plus en plus de chance d’être émis s’il n’a pas encore été émis.
peut donc émettre. Les autres nœuds ayant détecté une transmission, ils attendent la
fin avant de recommencer ce processus.
Dans la figure 1.9, les nœuds 1 et 4 ont tiré le plus petit temps de backoff. Ils
émettent ensemble, ce qui produit une collision. Les paquets devront donc être réémis.
A la suite de ces délais, le paquet est émis. Le récepteur répond avec un ACK (accusé
de réception) qu’il émet après avoir attendu un délai de SIFS. Si le ACK n’est pas reçu,
une nouvelle émission est tentée. Il peut y avoir jusqu’à 4 tentatives. Au cas où un
accusé de réception serait perdu, tout nœud mémorise les identifiants des paquets reçus
afin de ne pas utiliser de paquet en double.
Depuis 2005, l’annexe 802.11e [IEE05] ajoute à la norme WiFi une gestion de qualité
de service sur la couche MAC. Ceci est nécessaire pour les applications à temps critiques
comme la téléphonie, ou le transport de vidéo (streaming). Cette évolution est aussi
appelée WMM (Wireless MultiMedia) ou WME (Wireless Multimedia Extention).
Tout d’abord, une classification de paquet est mise en place. Dans l’entête 802.11, un
champ supplémentaire est spécifié afin de caractériser la qualité de service à appliquer
au paquet. Il peut être un des quatre types suivants :
– VO : Vo-Ip (voix sur IP)
– VI : Video (vidéo)
– BE : Best Effort (au mieux)
– BK : BackGround (arrière plan)
Par défaut, ce paramètre est défini en fonction du paramètre TOS (Type Of Service)
de l’entête IP (défini par la norme 802.1d). Par exemple, la consultation de page web
sera en BK alors que la téléphonie sera en VO. Cette classification permet tout d’abord
de prioriser l’émission de paquet suivant l’ordre de priorité : VO, VI, BE, BK.
Une nouvelle méthode d’accès nommé EDCA (Enhanced Distributed Channel Ac-
cess) permet que les paquets d’une classe plus élevée aient plus de chance d’être priori-
taires par rapport à d’autres paquets si deux nœuds venaient à vouloir émettre en même
temps. En effet, pour chaque classe de qualité de service, un nouveau temps intertrame
AIFS est défini et remplace le seul DIFS. De même, les constantes permettant de cal-
culer les périodes de contention CWmin et CWmax sont définies en fonction de la classe
de QoS. Ces délais seront plus faibles pour les paquets prioritaires.
1.4.1 Introduction
1.4.2 Le débit
1.4.3 La latence
La latence est le délai entre le dépôt dans la queue d’émission d’un paquet et la
réception du paquet dans un autre nœud. Ceci peut aussi être appelé le retard. Le RTT
(Round Trip Time) est le temps d’aller-retour d’un paquet. Il peut être mesuré avec
l’utilitaire "ping" qui permet d’émettre un paquet à un destinataire qui va répondre.
Le nœud source va pouvoir mesurer le temps entre le moment où il a émis le paquet, et
le moment où il a reçu la réponse.
1.4.4 La gigue
La gigue J est la moyenne des variations de délai entre deux paquets successifs.
Cette valeur est importante pour qualifier une communication audio. Elle est notamment
définie dans la RFC 1889 qui normalise le protocole RTP (Real Time Protocol). Pour
un paquet i, le délai Di est calculé à partir de Ri qui est la date d’arrivée du paquet
i, et Si qui est la date d’envoi du paquet i. La date d’envoi Si peut être calculée à
partir de Ti qui est le numéro d’échantillon contenu dans le paquet RTP. Par exemple,
en utilisant le codec audio G.711, la fréquence d’échantillonnage F est de 8000Hz.
Si = TFi (1.1)
Di = (Ri − Ri−1 ) − (Si − Si−1 ) (1.2)
|Di |−Ji−1
Ji = Ji−1 + 16 (1.3)
Le pilote permet de créer plusieurs interfaces logiques de type point d’accès, WDS, client
ou ad-hoc.
Lors des tests 1, 2 et 3, l’option WMM est désactivée. Cette option active la com-
patibilité avec la norme de qualité de service 802.11e. Cette option est activée lors des
tests 4, 5 et 6.
Analyse par expérimentation 17
Lors de toutes les expérimentations, le client SIP établit une connexion RTP. Pour
les tests 1 et 4, seule cette connexion RTP est établie. Pour les tests 2 et 5, un client
HTTP télécharge un fichier sur le serveur. Pour les tests 3 et 6, deux clients HTTP
téléchargent un fichier sur le serveur.
Pour chacun de ces tests, une mesure de ping est mise en place afin de mesurer le
temps aller/retour à partir du serveur jusqu’au client SIP.
De même, la connexion RTP transitant entre le nœud 3 et le client SIP est capturée
par l’interface "espion" du serveur. A partir de cette capture, les graphes de gigue sont
présentés pour chaque test.
1.5.3 Résultats
Les figures 1.12, 1.13 et 1.14 montrent que le délai de traversée du réseau augmente
en fonction de l’utilisation du canal lorsque WMM n’est pas activé. En effet, en ajoutant
une communication HTTP (figure 1.13, puis deux comunications HTTP (figure 1.14),
les mesures de RTT augmentent. De même lorsque le RTT est activé, les figures 1.15,
1.16 et 1.17 montrent le même phénomène.
L’impact de WMM est faible lorque le canal est peu utilisé. En effet, les figures 1.12
et 1.15 se ressemblent. Ceci est expliqué car lorsque le canal est peu utilisé, les paquets
sont relayés immédiatement avec WMM activé ou non.
Cependant, avec une communication HTTP, les figures 1.13 et 1.16 montrent une
amélioration du RTT lorsque WMM est activé. En présence de deux communications
HTTP, les figures 1.14 et 1.17 montrent que le RTT est très important avec ou sans
WMM.
20 Le WiFi maillé, des principes au terrain
De même que le RTT, les figures 1.18, 1.19 et 1.20 montrent que la gigue de la com-
munication audio augmente lorsque le canal est utilisé avec WMM désactivé. Lorsque
WMM est activé sur les figures 1.21, 1.22 et 1.23, la gigue augmente aussi quand le
canal devient chargé. Sur les figures 1.18 et 1.21, la gigue est faible car le réseau est peu
utilisé. Avec une communication HTTP, WMM améliore sensiblement la gigue sur les
figures 1.19 et 1.22. Lorsque le canal est très chargé, les figures 1.20 et 1.23 montrent
que la gigue est importante avec ou sans WMM.
Le nombre de paquets correctement transmis peut être mesuré. Dans ces conditions
expérimentales, la taille d’un paquet correctement transmis ainsi que le débit physique
auquel il a été transmis est disponible. Les temps intertrames peuvent être déduits en
fonction de la nature du paquet. Cependant, les périodes de contention, les collisions et
les erreurs de transmissions ne peuvent pas être détectées et donc comptabilisées dans
la partie "canal utilisé".
Cette expérimentation montre que, dans ce petit réseau maillé, des transmissions
vocales qui nécessitent de la qualité de service sont dégradées par des grosses trans-
missions de données concurrentes. En effet, l’écoute des communications audio était
dégradée lorsque la mesure de la gigue était élevée pendant le test.
De plus, l’activation de la norme de qualité de service 802.11e n’améliore que faible-
ment la qualité audio lorsque le réseau est chargé.
Analyse par expérimentation 23
1.5.5 Conclusion
Cette expérimentation permet de voir que le RTT reste correct sur un réseau WiFi
maillé lorsqu’il y a peu de communication. De plus, l’activation de WMM améliore le
RTT et la gigue d’une communication audio en présence d’un trafic moyen. Avec un
trafic très important, nous pouvons constater de nombreuses pertes et réémissions, avec
WMM activé ou non.
L’enregistrement de tout ce qu’il se passe sur la fréquence radio utilisée par le WiFi
permettrait de comprendre précisément les problèmes de communication. Il serait né-
cessaire d’utiliser plusieurs analyseurs vectoriels synchronisés temporellement, et posi-
tionnés judicieusement pour avoir toutes les informations, et tous les évènements d’une
transmission. Cette méthode nécessitant plusieurs matériels très performants, elle n’a
pas pu être mise en œuvre.
De plus, cette expérimentation utilise des nœuds positionnés à proximité, ce qui
signifie que chacun reçoit le signal de tous les autres. Afin d’expérimenter des communi-
cations avec certains nœuds qui ne se captent pas, de grandes surfaces sont nécessaires.
Cependant, l’expérimentation reste une bonne méthode pour mesurer réellement l’im-
pact des améliorations sur les leviers identifiés.
Dans cette thèse, nous cherchons à améliorer la qualité de service. L’expérimentation
précédente montre que celle-ci n’est pas optimale pour du transport de communications
audio ou vidéo. Cependant, l’utilisation de réseau maillé étant en plein essor, des travaux
ont déjà été effectués dans ce domaine. C’est pourquoi nous pouvons poursuivre cette
étude par un état de l’art sur l’amélioration de la qualité de service du WiFi maillé.
24 Le WiFi maillé, des principes au terrain
Chapitre 2
Etat de l’art
Le WiFi maillé est une nouvelle méthode qui permet le développement d’un réseau
étendu. Ce domaine intéresse de nombreux chercheurs car couvrir de grandes surfaces
tout en conservant une qualité de service acceptable pose de nombreux problèmes. C’est
pourquoi nous commencerons par dresser un état de l’art des recherches en cours. Celles-
ci vont présenter les problèmes rencontrés, ainsi que des solutions qui ont été proposées.
25
26 Etat de l’art
Les simulations montrent des débits corrects pour les stations du point d’accès
connecté à Internet, mais des débits progressivement plus faibles pour les nœuds sui-
vants (AP1 : 566 Kbit.s−1 , AP2 : 61 Kbit.s−1 , AP3 : 9 Kbit.s−1 ). Les auteurs [BCG05]
indiquent que ce phénomène est dû au problème du terminal caché. En effet, la simula-
tion montre un remplissage des files d’attente d’émission du nœud AP2. Lorsqu’une file
est pleine, les nouveaux paquets à empiler sont perdus. De nombreux paquets de AP3
sont donc perdus. Le nœud AP2 a moins de chance de gagner la période de contention
d’une part parce que ce nœud reçoit à la fois AP1 et AP3, et d’autre part car lorsqu’il
détecte un paquet mal reçu, il attend un délai intertrame plus important nommé EIFS,
et il détecte beaucoup de collisions entre AP1 et AP3. Les auteurs proposent donc une
nouvelle gestion de la file d’attente nommée QMMN (Queue Management in Multi-
hop Networks). L’idée principale de cette proposition est premièrement de limiter les
flux provenant des nœuds proches car ils vont rapidement remplir les files d’attente, et
deuxièmement de prioriser les flux qui arrivent plus lentement parce qu’ils ont traversé
plusieurs nœuds. Chaque nœud va donc mémoriser, pour chaque source, le nombre de
paquets en queue, et le délai moyen entre chaque arrivée de paquet. Des simulations
avec le logiciel NS-2 [NS-11a], montrent que cette gestion de la file d’attente améliore
Solutions protocolaires pour le WiFi maillé 27
le débit des transmissions issues des nœuds ayant effectués plus de sauts.
Ils présentent un exemple de topologie en chaîne, figure 2.2, avec les nœuds 0, 1, 2,
3, 4, 5, 6 où un nœud central 3 est reçu de ses voisins 2 et 4, et perturbe les nœuds
1 et 5. Les nœuds 0 et 6 ne sont pas affectés par une émission du nœud 3. Leurs
modèles analytiques ainsi que leurs simulations avec le simulateur réseau NS-2 mettent
en évidence que le problème du terminal caché joue fortement sur les réémissions TCP
et donc le débit de bout en bout.
Ce même problème est présenté dans [XG06]. Pour ceci, les auteurs proposent une
méthode permettant d’améliorer la qualité de service de flux vidéos au travers d’un
réseau maillé WiFi. Ils présentent tout d’abord un moniteur de liens au niveau de la
couche MAC permettant de mesurer la capacité du lien ainsi que les débits de chaque
flux vidéo transitant par ce nœud. La bande passante disponible peut alors être calculée.
Ce moniteur estime aussi la congestion sur un nœud en calculant le délai moyen entre
la réception d’un paquet et sa réémission. A partir de ces données, les débits des flux
des caméras sont diminués ou augmentés afin d’optimiser la congestion sur les nœuds.
La publication [TCCYMC06] présente une amélioration de la qualité de service sur
un réseau maillé WiFi, à base de jeton. Leur proposition est basée sur une topologie en
chaîne uniquement, avec un nombre de nœuds connu comme présenté sur la figure 2.3.
La problématique suivante est présentée figure 2.4 : pour que la communication entre
les nœuds 3 et 4 réussisse, les nœuds 2 et 5 ne doivent pas émettre. De plus, si un paquet
est émis par le nœud 1, le nœud 2 sera occupé à répondre par un accusé de réception et
de même pour les nœuds 5 et 6. Enfin, si le nœud 3 répond au nœud 2, il peut y avoir
collision avec le nœud 1 qui répond au nœud 0. En résumé, lorsque le nœud 3 émet, les
Solutions protocolaires pour le WiFi maillé 29
nœuds 0 à 6, qui ont jusqu’à trois sauts d’écart, ne doivent pas émettre pour éviter des
collisions.
A partir de ces limitations, les auteurs proposent une méthode d’accès basée sur le
TDMA (Time Division Multiple Access) nommé TDS (Token Based Scheduling). Les
groupes de nœuds pouvant émettre au même moment sans risque de collision pourront
successivement émettre. Afin de valider leurs travaux, les auteurs utilisent le simulateur
Glomosin. Les résultats montrent une diminution des délais moyens d’arrivée des pa-
quets, ainsi qu’une amélioration des débits lorsque le réseau comporte plus de 7 nœuds.
L’activation des paquets de contrôle RTS/CTS peut aider à résoudre ce problème du
noeud caché. Cependant, dans [JYM07], les auteurs identifient un problème avec l’uti-
lisation ces paquets de contrôle, qu’ils nomment PPC (Persistent Pseudo-Clearance).
Ce problème apparaît essentiellement en présence de deux paires de nœuds suivant la
topologie ci-dessous.
Dans cette topologie figure 2.5, les nœuds ne voient que leurs voisins. X reçoit Y.
Y reçoit X et B. B reçoit Y et A, et A reçoit B. Le scénario posant problème est le
suivant. A émet un RTS à B. Celui-ci répond CTS. Y ne reçoit pas ce CTS suite à
une interférence. A émet alors son paquet. Si à ce moment là X émet un RTS à Y, les
paquets sont perdus car les CTS qu’ils émettent perturbent la transmission du paquet
30 Etat de l’art
(figure 2.6).
Les auteurs proposent une solution en utilisant des paquets MRTS (Multicast RTS).
Ces paquets contiennent la liste de nœuds voisins. Chaque nœud voisin répond un CTS
dans l’ordre de la liste. Ainsi, un nœud voisin du voisin ne tentera pas d’émettre un RTS,
et le CTS qui aura été répondu ne perturbera pas le paquet voulant être émis par le
nœud d’origine. Le simulateur NS-2 est utilisé pour valider les améliorations proposées
par ce mécanisme. Les résultats montrent une diminution du nombre de paquets perdus.
De nombreuses topologies mettent en évidence ce problème du nœud caché. Les au-
teurs de [RAGK08] proposent une modélisation des interactions entre deux flux dans un
réseau WiFi maillé. Le modèle de propagation est basé sur SINR (Signal to Interference
Noise Ratio). Dans ce modèle, un paquet ne peut être reçu correctement que si le rap-
port entre le signal et la somme des bruits est plus grand qu’un seuil nommé Capture
Threshold. Le premier flux transite du nœud source S1 au nœud destination S2, et le
second va du nœud source S2 au nœud destination D2. Les interactions modélisées sont
classées en 10 catégories (figure 2.7).
l’autre source car les nœuds sources ne se captent pas. Dans ce cas, D1 reçoit
correctement les données alors que D2 reçoit des collisions.
– SCSI (Senders Connected Symmetric Interference) - Figure 2.7 b) : La catégorie
représente le cas où les deux émetteurs se captent. La méthode d’accès CSMA/CA
empêche un émetteur de décider d’émettre si l’autre est déjà en transmission. Les
seules collisions inévitables, à faible probabilité, seraient dues à un tir de période de
contention identique, ce qui pourrait entraîner une collision d’accusé de réception.
– SIS (Symmetric Incomplete State - Figure 2.7 c) : Cette catégorie représente deux
nœuds sources qui ne se captent pas alors que les deux destinataires reçoivent les
deux nœuds sources. De nombreuses collisions peuvent se produire car un émetteur
ne sait pas si l’autre émet.
– IDIS (Interfering Destination Incomplete State - Figure 2.7 d) : Cette catégorie
décrit la topologie pour laquelle il n’y a pas d’interférence entre une source et la
destination de l’autre flux. Seules les deux destinations peuvent créer une collision
entre les accusés de réception.
– SCAI (Senders Connected Asymmetic Interference) : Cette catégorie représente
deux émetteurs qui sont à portée, et S1 qui détecte une transmission de D2 mais
sans comprendre le paquet. Dans ce cas, S1 observe un temps intertrame EIFS
plus long car il a détecté une erreur de transmission.
Ces différentes catégories montrent plusieurs topologies qui font apparaître le problème
du nœud caché, qui a pour conséquence soit la perte de paquet, soit la perte d’accusé
de réception.
Ce problème est aussi adressé dans [LPSY09]. En effet, les auteurs proposent une
modélisation mathématique puis une expérimentation d’un réseau WiFi maillé de 6
nœuds en extérieur. Afin de moins être perturbées par l’environnement, les interfaces
radios sont configurées sur des canaux 5 GHz suivant la norme 802.11a.
La topologie utilisée est présentée dans la figure 2.8, et seuls les nœuds reliés peuvent
communiquer entre eux. Les liens sont symétriques et le rapport signal sur bruit est de
l’ordre de 9 à 22 dB, ce qui est relativement faible. Sur chaque paire de nœud AE, CD
et BF, trois flux sont mis en place :
– un flux TCP à 512 Kbit.s−1 avec des paquets de 1500 octets en priorité BE (Best
Effort),
– un flux UDP à 28 Kbit.s−1 avec des paquets de 200 octets en priorité VI (Video),
– un flux UDP à 64 Kbit.s−1 avec des paquets de 100 octets en priorité VO (Vo-IP).
32 Etat de l’art
Pour chaque communication, les débits minimum, moyen et maximum, le délai de bout
en bout, le jitter et le taux de paquets perdus sont mesurés. Les résultats de l’expéri-
mentation montrent que les flux vidéo et voix sur ip ont un taux de perte et un jitter
acceptables. Cependant, les communications TCP ont un débit très faible. Ceci est dû
d’une part à la classification 802.11e qui priorise les paquets VI et VO, et d’autre part
au problème du terminal caché qui augmente la probabilité de collision. En conclu-
sion, les auteurs suggèrent une nouvelle méthode d’accès qui serait normalisée dans la
norme de WiFi maillé 802.11s. Celle-ci, nommée MCCA (Mesh Coordinated Channel
Access) permettrait aux nœuds maillés de réserver des temps d’accès à la couche radio
de manière périodique pour les applications nécessitant de la qualité de service.
du nœud caché n’apparaît pas car tous les nœuds connaissent à l’avance le moment où
ils ont le droit de parler. Les performances de cette solution sont meilleures qu’avec du
WiFi standard, cependant tous les nœuds du réseau doivent implémenter ce protocole
pour préserver cette qualité de service.
2.3 Positionnement
Cette première partie de l’état de l’art nous a permis d’identifier les problèmes
connus sur un réseau WiFi maillé et quelques propositions de solutions soit radio soit
protocolaires. Nous pouvons résumer ces problèmes dans une première partie. Mal-
heureusement, les améliorations proposées précédemment ne sont pas compatibles avec
notre approche. En effet, une contrainte imposée initialement est de rester compatible
avec des stations qui respectent la norme et pourraient se connecter sur ces nœuds.
Ainsi, une nouvelle méthode d’accès comme TDS présenté dans [TCCYMC06], ainsi
que de nouveaux paquets de contrôle comme M-RTS présentée dans [JYM07] et R-RTS
présentée dans [SPK+ 07] ne serait pas efficaces avec des stations ne respectant pas amé-
liorations. De plus, une autre contrainte initiale est de n’utiliser qu’une interface radio
dans un nœud, ce qui nous limite dans l’utilisation de plusieurs canaux. Cependant,
nous avons pu identifier des leviers sur lesquels nous pouvons agir. Ceci va être présenté
dans une seconde partie.
être perdu, ce qui entraînera une nouvelle émission du paquet. [RAGK08] présente les
topologies où il peut y avoir des collisions entre des nœuds cachés.
Les paquets de contrôle RTS/CTS prévus dans la norme 802.11 ont pour objectif
de régler ce problème. Cependant, dans un réseau WiFi maillé, un nœud central qui
reçoit tous les autres nœuds n’existe pas forcément. [JYM07] montre qu’une mauvaise
réception d’un paquet de contrôle peut entraîner une succession de collisions. De plus,
ce mécanisme induit des délais de contrôle supplémentaires.
Lors de notre étude, il est important de considérer une topologie où ce problème
apparaît, car cette situation peut entraîner des pertes de paquets. De plus, l’activation
de RTS/CTS est un levier qui peut améliorer les transmissions dans certains cas.
[Link] Influence des pertes de paquet WiFi sur une connexion TCP
La perte, suite aux multiples tentatives de réémission, d’un paquet TCP transmis
sur un lien maillé WiFi, impacte l’ensemble d’un réseau maillé. Ceci est présenté dans
[LKC05]. En effet, si un paquet n’est pas reçu par son destinataire, un accusé de ré-
ception TCP ne sera pas envoyé, le paquet sera retransmis à partir de sa source, et
le réseau maillé sera à nouveau sollicité. Ainsi, de nombreuses pertes de paquet TCP
vont entraîner de nombreuses retransmissions, et donc un trafic plus important. Nous
pouvons dons nous soucier de la même façon des pertes de paquets sur un flux UDP
qui dégrade la qualité de service, et des pertes de paquet sur un flux TCP qui entraîne
des retransmissions de la couche transport.
2.3.4 Simulation
L’approche que nous allons retenir est la simulation. Celle-ci permettra d’évaluer
l’action des leviers identifiés sur de nombreuses topologies, tout en maîtrisant les in-
terférences dues à l’environnement. De plus, les scénarii seront enregistrés, et une vue
macroscopique des évènements pourra être analysée.
Notons que le recours à la simulation est à double objectif :
– avant déploiement, chercher la position de chaque nœud, les liens à utiliser entre
eux, et le paramétrage offrant la meilleure qualité de service,
– en post-déploiement, chercher à améliorer la qualité de service en actionnant les
leviers à partir d’une topologie existante et des mesures réalisées sur le terrain.
36 Etat de l’art
[Link] NS-2
Le logiciel NS "Network Simulator" [NS-11a] est gratuit et open source. Il a été
conçu pour simuler des réseaux à partir d’évènements discrets. L’utilisateur peut définir
des modules en C++. L’interaction entre les différents éléments, la configuration du si-
mulateur et la programmation temporelle d’évènements sont décrits en TCL. Lors d’une
simulation, ce logiciel fournit un fichier animation exploitable avec l’utilitaire NAM qui
va afficher la topologie, les flux, ainsi que les évènements qui se sont produits lors de la
simulation. Une analyse en détail de cette animation peut aider à la validation du réseau
modélisé sous NS. Ce logiciel fournit aussi des fichiers exploitables par XGraph permet-
tant de tracer des courbes représentant les performances à analyser. Enfin, il fournit
aussi des fichiers de log, à partir desquels une application développée par l’utilisateur
peut extraire d’autres informations.
De nombreux protocoles et modules ont déjà été développés et mis à disposition par
la communauté. Cependant, l’objectif initial de ce logiciel est la simulation des couches
hautes du modèle OSI sur des réseaux filaires. Des couches physiques sans fil ont été
développées par différents contributeurs, avec des manières différentes de programmer
et ne peuvent pas toujours être personnalisées sans en modifier les sources [MSK+ 10].
De plus, la modélisation d’une couche physique radio correspondant au WiFi maillé est
complexe. En effet, l’émission d’un nœud ne doit être reçue que par certains nœuds qui
sont à portée et plusieurs utilisations du canal radio sont possibles au même instant
sur des nœuds éloignés. Ce simulateur a été créé initialement pour simuler des réseaux
filaires où les problèmes de propagation et de collision sont différents. L’utilisation de
cet outil nécessiterait de revoir la couche radio ainsi que la répétition des paquets par
les nœuds relais, c’est pourquoi nous ne l’utiliserons pas.
Cependant, aujourd’hui, de nombreux contributeurs ont permis à ce simulateur
d’évoluer, ce qui nous permettrait de l’utiliser. Par exemple, [BMG+ 10] améliore la
couche physique pour permettre de simuler plus des réseaux maillés, avec différentes
technologies dans la même simulation.
[Link] NS-3
Le successeur du NS-2 est NS-3 "Network Simulateur 3" [NS-11b]. Ce logiciel est
aussi gratuit et open source. Contrairement à son prédécesseur, il est écrit uniquement
en C++, ce qui simplifie le développement de nouveaux modules. De plus, il utilise des
logiciels automatisant la documentation, ce qui permet une prise en main plus facile
Simulateurs existants 37
du logiciel. La simulation de réseaux filaires et non filaires a été prévue dès l’origine du
projet. C’est pourquoi le code est plus intuitif et plus évolutif.
Des études ont utilisé ce simulateur dans le cadre des réseaux maillés comme [YJSHYB+ 11]
qui propose un algorithme de routage orienté session, et [GGFK10] qui propose un pro-
tocole de multicast. Cependant, ce simulateur est récent et ne permettait pas notre
étude au moment où nous cherchions un simulateur.
[Link] OMNET++
OMNET++ [Var11] est un simulateur à évènements discrets. Il a tout d’abord été
conçu pour simuler les communications sur un réseau [VH08], mais son architecture
permet la simulation de systèmes plus complexes [Var01]. Ce logiciel est libre pour les
universités et applications à but non lucratif, il est soumis à licence pour les entreprises.
Son environnement de développement est basé sur la plateforme du logiciel Eclipse. Ses
modules sont développés en C++. Cependant, ce logiciel n’implémente que la couche
physique 802.11b, et non des débits plus élevés proposés par la norme 802.11a ou 802.11g.
De plus, il n’implémente pas de réseau sans fil maillé, ni de réseau ad-hoc qui aurait
pu servir de base pour développer un réseau maillé. C’est pourquoi nous ne retiendrons
pas cette solution.
[Link] QualNet
La société Scalable Network Technologies commercialise le logiciel QualNet [nt11].
Il permet de simuler des réseaux filaires et sans fil. Son architecture est divisée en
trois couches. Tout d’abord, la première couche est le noyau qui est un ordonnanceur
à évènement discret. Ensuite, des bibliothèques de modèles sont disponibles. Enfin, la
troisième couche est l’interface utilisateur. Celle-ci est composée de différents outils
permettant de décrire les scénarii, d’obtenir les animations ou des analyses.
38 Etat de l’art
[Link] Bilan
Afin de comparer les actions des leviers configurés dans le modèle, un joueur de
réseau de Petri est nécessaire. Ce joueur doit permettre de valider la modélisation, et
de simuler des transferts de données dans le but de comparer les performances et la
qualité de service en fonction de différentes actions sur les leviers. Voici donc les joueurs
de réseaux de Petri que nous avons analysés.
[Link] Möbius
Le projet Möbius [SKGR11] est hébergé par l’Université de l’Illinois aux Etats-Unis.
Il a été développé à partir de 2001, et est devenu le successeur de UltraSAN [OQDS06].
C’est un joueur de réseau de Petri à objet, temporisé, stochastique et hiérarchisé. Ce
simulateur permet de modéliser des systèmes complexes à évènements discrets. Les
éléments de bases sont les places, les transitions, et les portes d’entrée et de sortie des
transitions. Il existe deux types de places. Les places "standard" ne peuvent contenir que
des jetons banalisés alors que les places "extended" peuvent contenir des objets. Chaque
jeton est soit banalisé soit un objet. Les portes d’entrée des transitions exécutent des
tests sur ces objets, et des méthodes sur ces objets sont définies dans les portes de sortie
des transitions. L’utilisation de ce logiciel est donc lourde lorsque l’utilisation d’objet
n’est pas nécessaire. Pour chaque modèle, un code en C++ est généré puis exécuté. Les
primitives "Rep" et "Join" permettent de créer des instances de modèles et de dupliquer
ces instances.
[MPV06] a utilisé cet outil pour modéliser un réseau WiFi dans le but d’analyser la
qualité de service apportée par la norme 802.11e. Le modèle ainsi créé est simple sur un
aspect réseau de Petri. Mais, la définition des objets, ainsi que leurs utilisations dans
les portes d’entrée et de sorties sont complexes. La modélisation est donc difficile à lire
et à concevoir. Nous avons utilisé cet outil dans un premier temps, mais l’évolutivité
d’une telle modélisation est limitée.
[Link] GreatSPN
[Link] CPN-Tools
2.6 Conclusion
Ce chapitre nous a permis dans un premier temps de mettre en avant les problèmes
traités dans la littérature à propos des réseaux WiFi maillés. Ces problèmes sont dus
au partage du canal radio entre les différents nœuds du réseau qui ne sont pas tous à
portée. De plus, en fonction de la topologie, le problème du nœud caché peut apparaître.
La qualité de service et le débit utile sont affectés, ce qui impacte les communications
audio et vidéo sur un tel réseau.
A partir de ces problèmes et des difficultés à utiliser l’approche expérimentale, nous
optons pour la simulation. C’est pourquoi ce chapitre a décrit les principaux simulateurs
utilisés en réseau. Cependant, ils ne sont pas adaptés à notre problématique. Ainsi, nous
avons décidé d’utiliser le formalisme des réseaux de Petri, exécuté par lŠintermédiaire
dŠun joueur. Il permet la modélisation d’un réseau WiFi maillé, mais permet aussi une
forte évolutivité. Nous pouvons alors raffiner à mesure à la vue du détail nécessaire pour
observer des problèmes et tester des améliorations à apporter.
Nous avons ensuite exposé et comparé différents joueurs de réseaux de Petri per-
mettant de simuler un ensemble de flux, sur une topologie donnée, au travers du modèle
représentant le réseau WiFi maillé.
Le chapitre suivant est consacré à la description de ce modèle de réseau WiFi maillé
à partir de réseaux de Petri, ainsi qu’à sa validation.
42 Etat de l’art
Chapitre 3
De la modélisation à la validation
du simulateur
3.1 Introduction
Pour améliorer la qualité de service des flux sur un réseau maillé WiFi, il est néces-
saire de comprendre comment fonctionnent les mécanismes d’accès de la norme 802.11
et d’analyser ce qu’il se passe lorsque plusieurs points d’accès utilisent ce même canal de
communication. C’est pourquoi une modélisation, puis une simulation du modèle peut
permettre d’identifier les situations de dégradation de la QoS et de mettre en avant des
mécanismes à améliorer.
Ensuite, ce simulateur permet d’évaluer les actions portées sur des leviers qui peuvent
modifier la qualité de service. Ces actions peuvent être portées sur les leviers de certains
nœuds, et de manière différente en fonction de la topologie. Cependant, ces leviers de-
vront être modifiables sur le matériel utilisé afin de pouvoir apporter les améliorations
sur le terrain. De plus, les améliorations apportées devront rester compatibles avec les
transmissions d’autres nœuds présents dans la même installation et que nous ne pouvons
pas modifier.
Tout d’abord, nous allons présenter l’objectif de la modélisation et le formalisme
utilisé qui est le réseau de Petri. Ensuite, nous allons spécifier la granularité du modèle
requise par notre objectif et définir les limites d’utilisation de celui-ci. Enfin, le modèle
sera présenté, module par module. Cependant, avant d’exploiter le simulateur, il est
nécessaire de le valider, afin de s’assurer de sa conformité aux phénomènes réels et
ainsi, obtenir des résultats qualitativement cohérents. La pertinence des conclusions
tirées de la simulation en dépend.
Le formalisme de modélisation doit permettre de modéliser un réseau maillé WiFi.
Au regard de notre objectif, il doit donner des résultats qualifiant la qualité de service.
De plus, il doit permettre de détailler toutes les étapes du scénario simulé afin de mettre
en avant les phénomènes significatifs pour l’amélioration de la QoS.
43
44 De la modélisation à la validation du simulateur
[Link] Place
Une place est définie par un nom (p_conf_icmp dans l’exemple de la figure 3.1) et la
couleur des jetons qu’elle accepte (PAQUETSIMPI ). Elle peut aussi avoir un marquage
initial (3,sa=1, da=8, ac=BK, typ=ICMP_RQ, length=500, data=0) et le nombre de
jetons qu’elle contient à cet instant de la simulation (1). Il s’agit en l’occurrence de la
description de l’initialisation des paquets ICMP à travers le marquage initial du modèle.
[Link] Transition
Une transition est présentée sur la figure 3.2. Elle a au minimum un nom (t_emission).
Elle peut aussi avoir une condition qui porte sur les jetons entrants, et une tempori-
sation (@+1). Cette temporisation signifie que le jeton sera disponible dans la place
suivante au temps courant plus 1 unité de temps. Ceci correspond au modèle de réseau
de Petri T-Temporisé.
[Link] Arc
Un arc est présenté figure 3.3. Un arc entrant relie une place à une transition.
Sa fonction de filtrage associée permet d’affecter à des variables les valeurs du jeton
candidat au tir. Si le texte contient des constantes, elle permet de filtrer seulement
46 De la modélisation à la validation du simulateur
les jetons qui contiennent une valeur égale à la constante. Un arc sortant relie une
transition à une place. Sa fonction associée peut permettre de générer et/ou modifier
un ou plusieurs jetons déposés dans la place cible à laquelle l’arc est relié.
Les transitions ayant un double contour, comme présenté figure 3.4, enferment un
sous-réseau de Petri du nom de la macro transition. Les macro transitions permettent
une description hiérarchisée. Les places liées par des arcs à ce type de transitions seront
présentes à la fois dans ce modèle et dans le sous modèle.
Une place marquée In dans un sous réseau est une place d’entrée. Un exemple est
présenté figure 3.5. Cela signifie que cette place existe dans le modèle parent, et que
les jetons ne font que rentrer dans cette place. Lorsque la place à laquelle elle est reliée
dans le modèle parent est marquée, celle-ci le sera aussi.
Une place marquée Out dans un sous réseau est une place de sortie (figure 3.6). Les
jetons qui y seront placés seront disponibles dans la place du réseau parent avec laquelle
elle est liée.
Structuration du modèle 47
Une place marquée I/O dans un sous réseau est une place d’entrée/sortie (figure
3.7). Les jetons peuvent entrer ou sortir de cette place qui est commune avec une place
du modèle parent.
La transmission, sur un réseau WiFi maillé, peut être exprimée sur un plan topolo-
gique ; chaque nœud a une position déterminée et ne peut communiquer qu’avec certains
autres nœuds (figure 3.8). L’aspect coloré du formalisme de réseau de Petri que nous
avons choisi permet de modéliser le comportement d’un nœud à partir de la structure
du modèle et de représenter plusieurs nœuds à partir du marquage du modèle. De cette
manière, le nombre de nœuds est donc facilement configurable. Chacun d’eux peut être
une station ou un point d’accès. Ceci est aussi configurable.
La topologie est donc décrite par des jetons colorés, ce qui facilite la mise en place de
différentes simulations. Le modèle est donc évolutif au sens de la topologie réseau qu’il
représente. Ceci est important dans notre cas car le simulateur doit être exploitable sur
différentes installations déployées ou à déployer par l’entreprise.
La transmission peut aussi être décomposée en fonction de la pile protocolaire, en
suivant les couches du modèle TCP/IP. Pour une transmission qui doit aller d’un nœud
1 à un nœud 5 (figure 3.9) et devant être relayée par les nœuds 2, 3 et 4, les paquets
sont encapsulés à chaque traversée de couche sur le nœud 1, chaque nœud intermédiaire
48 De la modélisation à la validation du simulateur
Le modèle est donc explicitement structuré selon ces couches. Afin de détailler da-
vantage la couche liaison de données, elle est divisée en sous couche MAC et LLC. La
sous couches MAC modélise les mécanismes propres à la norme WiFi, avec les méca-
nismes d’accès au médium, alors que la sous couche LLC est utilisée pour la répétition
de paquet, et le choix des chemins.
Les couches Réseau et Transport ne sont pas modélisées en détail car un paquet
aura un nœud source et un nœud destination identifié au niveau MAC. Les notions
d’adresses IP et de routage ne sont pas utiles dans le cadre de notre étude, néanmoins
le modèle pourrait être enrichi si besoin est.
Enfin, deux applications permettant de générer des données ICMP et UDP seront
implémentées. Un premier module nommé ICMP permet de générer des requêtes pé-
riodiquement. Quand une requête atteint sa destination, une réponse est émise vers la
source de la requête. Ainsi, le RTT peut être mesuré au travers du réseau maillé. Ce
protocole permet tout d’abord de valider le fonctionnement du modèle, car un paquet
simple est facile à suivre. De plus, ICMP permet de mesurer le RTT en même temps
que d’autres transmissions transitent sur le réseau maillé.
Un second module générant des paquets est inscrit dans l’architecture du simulateur,
il s’agit du module UDP. Comme le protocole du même nom, celui-ci permet de générer
des paquets en spécifiant :
– le nombre,
– la date de mise en file d’attente d’émission,
– la classe de qualité de service,
– la taille,
– les nœuds sources et destination.
Ainsi, différents types de trafic peuvent être générés avec ce module, qu’il soit périodique
ou sporadique, représentant de la voix sur ip ou du téléchargement.
Structuration du modèle 49
Chaque nœud étant singularisé par une couleur différente, il n’est nécessaire de
représenter qu’un seul modèle comportemental pour chaque couche, et celui-ci sera
utilisé pour tous les nœuds grâce au principe du repliage et de la coloration. Ainsi, à
partir de la figure 3.10, nous obtenons le modèle replié présenté figure 3.11.
Au regard de l’influence du protocole MAC sur les échanges entre nœuds, le modèle
MAC est le plus complexe. Il est aussi divisé en plusieurs modules :
– Beacon permet la diffusion périodique de beacon pour les nœuds de type point
d’accès.
– AccessCategories modélise les quatre files d’attente de la norme 802.11e : VO
(Voix), VI (Vidéo), BE (Best Effort), et BK (Background).
– Ifs impose aux paquets les délais intertrames correspondants.
– Contention décrit le tir ou non de période de contention ainsi que sa durée puis
temporise le paquet en conséquence. De plus, il surveille l’utilisation du canal
radio et réinitialise l’émission si une transmission est en cours comme le présente
le mécanisme CSMA/CA.
– RecvAck gère les réceptions d’accusé de réception et décide de réémettre un paquet
qui n’a pas été acquitté.
– MACReceive décrit la réception de paquet. En effet, ceci impacte le prochain délai
intertrame. Ensuite, il ignore les paquets qui ne sont pas destinés à ce nœud. Puis
il achemine les RTS, CTS et ACK au module ACKRTSCTS. Enfin, il propose les
paquets de données à la couche LLC.
– SendWithSIFS permet d’émettre des paquets de contrôle à la suite d’un temps
intertrame SIFS.
– ACKRTSCTS gère l’utilisation des paquets de contrôle RTS/CTS s’ils sont acti-
vés, ainsi que l’émission d’accusé de réception.
Granularité 51
3.3 Granularité
La granularité d’un modèle dans le temps et dans l’espace est fonction de ce que l’on
souhaite observer et valider. Cette granularité a des conséquences sur la pertinence et sur
la confiance que nous pouvons avoir sur les résultats ainsi que sur leur exploitation dans
la mesure où la granularité retenue définit le domaine de validité du simulateur ainsi que
les niveaux d’observation et de contrôle. Par exemple, un modèle à gros grain pourrait
masquer certains phénomènes ou ne pas offrir les leviers sur lesquels une amélioration
potentielle pourrait être exploitée. Cette granularité a été étudiée sur les différentes
couches protocolaires qu’encapsule le simulateur.
3.4 Description
3.4.1 Configuration de la topologie d’une installation WiFi maillé
La topologie du réseau maillé WiFi doit être une entrée du modèle. En effet, le
nombre de nœuds, ainsi que les caractéristiques des liens entre chaque nœud vont jouer
un rôle majeur dans la qualité d’une communication sur ce réseau. Cependant, dans un
cas réel, nous devons adapter la topologie au terrain car il n’est pas possible d’implanter
des points d’accès n’importe où, ou de couper des arbres qui affaiblissent la qualité de
transmission.
Trois places permettent de configurer la topologie étudiée dans le simulateur.
Ceci déclare la présence de huit nœuds dans le réseau. Les nœuds 1 à 6 sont des
points d’accès, et les nœuds 7 et 8 sont des stations. Tous les nœuds ont la valeur rts
à 2000, ce qui indique que le RTS/CTS n’est activé que pour les paquets faisant plus
de 2000 octets. Ensuite, la valeur AIFS contient 2 pour toutes les classes de qualité
de service du paquet pour les points d’accès et 7 pour toutes les classes de trafic des
stations. Enfin, CWmin et CWmax sont identiques pour tous les nœuds et ont des valeurs
différentes en fonction de la classe de qualité de service du paquet.
54 De la modélisation à la validation du simulateur
Cette configuration est accessible et regroupée ici, car ce sont des leviers réels qui
pourront être modifiés dans le pilote WiFi des prototypes lors d’expérimentations.
Figure 3.13 – Disposition des nœuds avec les rapports signal sur bruit
Cette matrice de rapports signal sur bruit permet de calculer les débits physiques
utilisés entre chaque nœud, ainsi que la matrice d’atteignabilité au sens topologique.
En effet, la probabilité de succès de transmission entre deux nœuds dépend d’une
part de la puissance de réception et d’autre part des perturbations de l’environnement.
Cette matrice d’atteignabilité spécifiant les probabilités de succès de transmission entre
chaque nœud synthétise ces paramètres car l’objet de cette étude ne porte pas sur la
qualité des communications radio mais sur son impact en terme de transmission de
paquets. Cette probabilité est appliquée à chaque transmission de paquet pour chaque
récepteur afin de générer des pertes et des retransmissions.
Description 55
Nœud récepteur
1 2 3 4 5 6 7 8
1 0 33 1 0 1 0 0 0
2 35 0 16 6 18 0 0 0
3 1 16 0 19 29 3 20 0
4 0 6 18 0 9 34 20 20
Nœud émetteur
5 1 17 29 8 0 2 40 0
6 0 0 3 35 4 0 0 40
7 0 0 20 20 40 0 0 0
8 0 0 0 20 10 40 0 0
Lorsqu’un nœud veut émettre, il vérifie qu’il ne capte aucun signal radio. Il vérifie
donc qu’aucune station où la probabilité le concernant est strictement supérieure à 0
n’est en train d’émettre. De même si deux émetteurs envoient un paquet à un même
récepteur, le paquet est marqué comme ayant subi une collision (le paquet ne sera pas
lisible).
Le tableau 3.4 présente un exemple de marquage de p_list_atteign qui est calculé
dans le modèle Network pour la topologie de la figure 3.13.
Nœud récepteur
1 2 3 4 5 6 7 8
1 0 95 58 0 58 0 0 0
2 95 0 91 73 93 0 0 0
3 58 91 0 94 95 64 95 0
4 0 73 93 0 82 95 95 95
Nœud émetteur
5 58 92 95 79 0 61 95 0
6 0 0 64 95 67 0 0 95
7 0 0 95 95 95 0 0 0
8 0 0 0 95 85 95 0 0
La première ligne signifie que lorsque le nœud 1 émet, le nœud 2 a une probabilité de
95 % de recevoir correctement le paquet et que les nœuds 3 et 5 ont une probabilité de 58
% de recevoir correctement le paquet. Les nœuds 4, 6, 7 et 8 n’ont aucune chance de le
recevoir. De plus, qu’il y ait collision ou non, et que le paquet soit transmis correctement
ou non, les nœuds 2, 3 et 5 voient leur canal radio comme étant occupé.
Network, figure 3.14). Ce tableau à deux dimensions renseigne par quel nœud receveur
il faut émettre ou relayer un paquet en fonction du destinataire.
Nœud destinataire
1 2 3 4 5 6 7 8
1 1 2 2 2 2 2 2 2
2 1 2 3 3 3 3 3 3
3 2 2 3 4 5 4 5 4
4 3 3 3 4 3 6 3 6
Nœud source
5 3 3 3 3 5 3 7 3
6 4 4 4 4 4 6 4 8
7 5 5 5 5 5 5 7 5
8 6 6 6 6 6 6 6 8
La deuxième ligne signifie que lorsque le nœud 2 doit émettre ou relayer un paquet
au nœud 1, il lui envoie directement. Pour émettre ou relayer au nœud 3, il lui envoie
aussi directement. Par contre, pour émettre ou relayer un paquet aux nœuds 4 à 8, il
doit envoyer au nœud 3.
Ce modèle présenté figure 3.14 est le modèle de plus haut niveau. Il permet d’as-
sembler les autres modules UDP, ICMP, LLC, MAC et Radio. Ces sous modèles seront
raffinés de manière à modéliser les mécanismes de la norme 802.11, et notamment les
mécanismes liés à la qualité de service.
Nous pouvons voir sur la partie gauche la configuration de la topologie, sur la partie
droite la configuration des transmissions, et sur la partie centrale les différents sous
modèles impliqués.
La configuration de la topologie ne se fait que dans ce modèle. Elle est ensuite propa-
gée à travers l’initialisation des sous modèles. De cette manière, ceux-ci sont initialisés
à partir du modèle de plus haut niveau et il n’y a qu’un seul endroit où modifier cette
configuration.
Description 57
UDP, ICMP, LLC, MAC, et Radio. Dans ces sous modèles, il est nécessaire d’initialiser
certaines places et de transmettre la configuration. Par exemple, les places complémen-
taires modélisant les files d’attente sont initialisées à ce moment là. De plus, le tir de
t_conf_host incrémente un entier initialisé à 1 dans la place p_ord. Ceci permet d’or-
donner le tir des jetons correspondants aux nœuds pour faciliter le développement du
modèle.
Enfin, le tir de t_powers copie la configuration des rapports signal sur bruit, initia-
lisés dans la place p_powers, dans la place p_list_power pour qu’ils soient disponibles
dans le sous modèle Radio. En effet, ce module transmet les paquets aux nœuds concer-
nés par la transmission. De plus, cette matrice est transformée par la fonction DEBIT
afin de créer un tableau de débit dans les places p_list_debit et p_list_rtscts_debit.
Celles-ci seront disponibles dans le sous modèle MAC qui définit le temps d’utilisation
du canal radio en fonction de la taille du paquet, et implémente le mécanisme RTS/CTS.
De même, la matrice de rapports signal sur bruit est transformée en matrice d’atteigna-
bilité par la fonction ATTEIGN dans la place p_list_atteign qui sera disponible dans
le sous modèle Radio.
Cette configuration est détaillée dans la partie Configuration de la topologie de la
simulation.
La configuration du trafic à injecter sur le réseau se fait dans la place p_conf_icmp
pour le modèle ICMP et dans la place p_conf_udp pour le modèle UDP. Le contenu
de ces places sera détaillé dans les sous modèles correspondants.
Sur la partie centrale de ce modèle, nous pouvons voir les différentes macro transi-
tions qui représentent les couches Radio, MAC, LLC, ICMP et UDP.
Du module Radio au module MAC :
La macro transition modélisant Radio est connectée à la macro transition MAC par
l’intermédiaire de trois places :
– p_r_send permet à MAC d’envoyer des paquets à Radio,
– p_r_receive permet à Radio d’envoyer des paquets à MAC,
– p_radio permet à MAC de savoir, pour chaque récepteur, si le médium radio est
occupé par un autre émetteur à chaque instant au niveau de chaque nœud.
En effet, la méthode d’accès CSMA/CA modélisée dans la couche MAC doit avoir
connaissance de la présence d’un signal, pour savoir s’il peut démarrer une transmission.
Du module MAC au module LLC :
De même, trois places permettent de connecter le module LLC au module MAC :
– p_l_send permet à LLC d’envoyer des paquets à la couche MAC,
– p_l_receive permet à la couche MAC d’envoyer des paquets à la couche LLC,
– p_l_e_comp est une place complémentaire à la place p_l_send qui permet de
limiter le nombre de paquets en attente d’émission dans la couche MAC car la
taille des buffers d’émission n’est pas infinie.
Du module LLC aux modules ICMP et UDP :
Les deux places p_send et p_receive sont connectées à la macro transition LLC et
permettent respectivement d’envoyer et de recevoir des paquets. La place p_comp est
une place complémentaire à la place p_send.
Les modèles ICMP et UDP sont directement connectés à ces deux places p_send
et p_receive de manière à émettre et recevoir des paquets. ICMP peut émettre des
paquets ICMP de requête périodiquement comme le ferait le programme ping, et côté
Description 59
récepteur, d’émettre des réponses dès la réception de la requête. De même, UDP peut
générer des paquets ponctuellement, qui sont relayés d’un nœud à un autre, avec des
caractéristiques de qualité de service, des tailles de paquets et des dates de départ des
paquets qui peuvent être différents.
De nouveaux modules pourront être implémentés et connectés à ces places si d’autres
manières de générer du trafic sont nécessaires selon les scénarii à étudier sur ces topo-
logies.
Cette étape, présentée figure 3.15, permet la création d’une liste des identifiants de
tous les nœuds dans la place p_list_host. Lors de l’initialisation, les jetons identifiant
chaque nœud de la place p_init_host, fournis par le modèle Network, permettent des
tirs de la transition t_init_host. La place p_list_host acceptant des jetons de couleur
LISTINT est initialisée avec un jeton nil. Cette couleur correspond à une liste d’entiers
et le jeton nil signifie une liste vide. A chaque tir de la transition t_init_host, l’identifiant
du nœud est ajouté à la liste de la place p_list_host. De plus, un jeton (h, 0) est généré
pour initialiser la place p_radio qui accepte la couleur INTH. Cette couleur est une
composition de l’identifiant du nœud avec un entier. Elle permet, pour chaque nœud
de compter le nombre de fois où le récepteur radio reçoit un signal WiFi à un instant
donné. Lors qu’il n’y a plus de jeton dans p_init_host, le jeton de la place p_list_host
contient les identifiants de tous les nœuds, et p_radio contient un jeton (h, 0) pour
chaque nœud.
[Link] 2ème étape : lorsqu’un paquet doit être émis, il est dupliqué pour
chaque nœud pouvant le recevoir
Cette étape est présentée figure 3.16.
Lorsqu’un nœud émet un paquet, tous les nœuds qui sont à portée doivent recevoir
ce paquet. Cette étape permet de dupliquer le paquet pour tous ces nœuds. La place
d’entrée/sortie p_list_atteign est présente dans le modèle parent, et contient la matrice
d’atteignabilité configurée initialement. La place d’entée p_r_send accepte des jetons
de couleur PAQUETH. Cette couleur est une composition de la couleur HOST qui
identifie un nœud, et de la couleur PAQUET. Celle-ci est une structure qui contient
tous les paramètres contenus dans le paquet :
– sa de couleur HOST : l’identifiant du nœud source
– ta de couleur HOST : l’identifiant du transmetteur
– ra de couleur HOST : l’identifiant du receveur
– da de couleur HOST : l’identifiant du destinataire
– ac de couleur AC : spécifiant la classe de qualité de service du paquet
Description 61
Comme présenté sur la figure 3.17, chaque jeton de la place p_send correspond à
une occupation de canal WiFi pour un nœud qui peut recevoir le paquet à émettre. Pour
chacun de ces jetons, la transition t_occupation va incrémenter l’entier qui correspond au
nœud récepteur de la place p_radio. Ceci permet d’informer le modèle parent Network
62 De la modélisation à la validation du simulateur
Figure 3.18 – Modèle Radio - 4ème étape - gestion des interactions entre paquets
La figure 3.18 présente les interactions entre paquets dans la couche Radio.
Afin de détecter et signaler des interactions entre des paquets, la place p_wait mémo-
rise tous les paquets en cours d’émission. Celle-ci est remplie lors du tir de t_occupation
par un jeton de couleur PAQUETSTATEH. Cette couleur est une composition des cou-
leurs HOST, PAQUET, BOOL et BOOL. Elle permet de stocker dans un jeton le nœud
auquel le paquet est destiné, le paquet en cours de transmission, un premier booléen
qui indique si le paquet a subi une collision, et un second booléen qui indique que le
paquet est émis à un nœud qui est en train d’émettre, ce qui ne lui permettra pas de
recevoir le paquet.
Tous les paquets en cours d’émission sont dans la place p_wait pour la durée de
leur transmission. A chaque nouvelle arrivée dans cette place, les conditions de tir des
transitions t_lost, t_collision et t_not_collision sont testées.
Perte de paquet si le receveur est en cours d’émission :
La transition t_lost sera tirée s’il existe deux jetons dans la place p_wait, dont le
récepteur du premier est le même que l’émetteur du second. Ce cas signifie qu’un nœud
aurait un paquet à recevoir alors qu’il est en cours d’émission. Le paquet qui aurait dû
être reçu est donc marqué comme lost.
Collision :
La transition t_collision consulte la matrice de rapports signal sur bruit contenue
dans la place p_list_power et elle est tirée s’il existe deux jetons dans la place p_wait,
dont les récepteurs sont identiques, et que la valeur absolue de la différence des rapports
signal sur bruit de ces deux paquets est inférieure au seuil défini, soit 10 dB dans cet
Description 63
exemple. En effet, il n’y a collision que si deux paquets reçus ont des rapports signal
sur bruit proches.
Perte de paquet si le receveur est en cours de réception :
De même, la transition t_not_collision consulte la matrice de rapport signal sur
bruit, et elle est tirée s’il existe deux jetons dans la place p_wait, ayant le même receveur,
et l’écart de niveau de réception est supérieur au seuil. Dans ce cas, le paramètre lost
du paquet le plus faible est marqué, ce paquet sera perdu, et la transmission de l’autre
paquet ne subira pas de collision.
Chaque tir de ces trois transitions t_lost, t_collision et t_not_collision est enre-
gistré afin d’établir des statistiques à la fin de la simulation.
La figure 3.21 présente le modèle Radio, assemblé avec les modules décrits précé-
demment.
Les interactions entre les modules du modèle MAC sont présentées figure 3.22.
Lors de l’émission d’un paquet, celui-ci est envoyé dans le sous modèle AccessCa-
tegories. Celui-ci stocke les paquets dans 4 files de type FIFO correspondantes aux 4
classes de qualité de service définies dans la norme 802.11e. Lorsque aucun paquet n’est
en émission par ce nœud et que le canal radio est libre, un paquet est dépilé afin d’être
passé au sous modèle Ifs. Celui-là attend pendant un délai intertrame qui est dépendant
de la classe de qualité de service du paquet, du succès de réception du dernier paquet
reçu, et de la configuration du nœud.
Ensuite, si le canal radio est toujours libre, le paquet passe dans le sous modèle
Contention. Il attend alors pendant une période de contention tirée aléatoirement entre
des valeurs dépendantes du nombre de réémissions du paquet et de la configuration du
nœud. Si pendant cette durée, le canal radio est encore libre, le paquet est transmis
au modèle ACKRTSCTS qui va se charger de mettre en place le mécanisme RTS/CTS
si nécessaire et de transmettre le paquet au modèle parent afin d’accéder à la couche
Radio. De plus, il est dupliqué dans la place RecvAck et un compteur (timeout) est
lancé afin d’attendre un accusé de réception.
Pour les nœuds de type AP (point d’accès), le sous modèle Beacon envoie des paquets
périodiquement en diffusion. Ce type d’émission est défini par la norme 802.11 et sert à
informer les stations voisines de la présence d’un point d’accès. Les paquets générés sont
directement transmis au sous modèle Ifs afin de suivre le processus décrit précédemment.
Lorsqu’un paquet est reçu par l’interface radio, il est transmis au sous modèle MA-
CReceive. Tout d’abord, il ignore les paquets qui ne sont pas destinés à ce nœud et ceux
qui ont des erreurs de transmission. Ensuite, les paquets de type beacon sont transmis
au sous modèle Beacon. Les paquets de type accusé de réception sont transmis au sous
modèle RecvAck de manière à éviter la réémission de paquet. Si l’accusé de réception
n’est pas reçu à temps, ce sous modèle transmet une nouvelle fois le paquet à la couche
Ifs pour effectuer une nouvelle émission. Ce processus est fait un nombre de fois défini
par la norme si l’accusé n’est toujours pas reçu. En cas d’échec, le paquet est perdu. Si
le paquet est de type RTS ou CTS, il transmis au modèle ACKRTSCTS.
Description 67
des paquets p_l_send ne contient pas de paquet. Enfin, la place p_init_mac mémori-
sera la configuration pour le modèle MAC.
Le modèle MAC utilise le sous modèle AccessCategories pour classifier les paquets
en 4 files d’attente. Ceci est défini par la norme 802.11e, et intégré aux pilotes WiFi. La
configuration des nœuds est transmise à ce sous modèle par la place p_init_ac. Ceci
est présenté figure 3.24.
Comme décrit précédemment, la place p_l_e_comp est initialisée avec un jeton
de couleur HOST 25/07/2011 pour chaque nœud. Cette place de sortie vers le modèle
parent Network est une place complémentaire à la place d’entrée p_l_send. Elle permet
de limiter à 1 jeton par nœud le marquage de la place p_l_send et donc d’empêcher
l’entrée de nouveaux paquets dans les files du sous modèle AccessCategories.
De même, la place p_ready est initialisée par un jeton de couleur HOST pour chaque
nœud. Ainsi, lorsqu’il n’y a pas de paquet en cours d’émission ou en attente d’accusé
de réception pour un nœud donné, le jeton de couleur HOST correspondant au nœud
est tiré par la macro transition AccessCategories, et un jeton de couleur PAQUETH
contenant le paquet est déposé dans la place p_em1 afin d’être transféré aux étapes
suivantes. En même temps, un jeton de couleur INTH <h,0> est déposé dans la place
p_nb_try. Ce jeton va permettre de compter le nombre de réémissions de ce paquet.
L’initialisation de ce module est présentée figure 3.25. Les deux places p_next_in et
p_next_out permettent de conserver l’ordre des paquets dans chaque file, et p_log_cnt
permet de tracer le remplissage des tampons d’un nœud. Lors de l’initialisation, la
place d’entrée p_init_host contient un jeton de couleur CONFH pour chaque nœud.
Lors du tir de la transition t_init_host, les places p_next_in, p_next_out et p_log_cnt
reçoivent un jeton de couleur INTACH pour chaque nœud, et chaque classe de qualité
de service. Cette couleur est une composition des couleurs HOST, AC, INT. (AC étant
une énumération des 4 classes : VO, VI, BE et BK.)
De même, lors de l’initialisation, la place p_comp_empty reçoit autant de jetons
que de paquets pouvant être stockés dans la FIFO. C’est cette place qui limite la taille
des files d’attente.
Lorsque le modèle MAC fait passer un paquet dans la place d’entrée p_in comme
70 De la modélisation à la validation du simulateur
présenté figure 3.26, le paquet est mis en file d’attente si la pile n’est pas pleine. Pour
ceci, un jeton est déposé dans la place complémentaire p_l_e_comp pour permettre
l’arrivée d’un nouveau paquet.
Pour limiter le nombre de paquets dans chaque file d’attente, la place complémen-
taire p_comp_empty contient autant de jetons que de places libres pour chaque classe
de qualité de service et pour chacun des nœuds. Le tir de t_in retire un jeton de couleur
ACH correspondant au nœud et à la qualité de service en cours. Si la file est pleine, la
place p_comp_empty ne contient aucun jeton correspondant au nœud et à la classe de
qualité de service, la transition t_in n’est pas franchissable, et aucun nouveau paquet
de cette classe de qualité de service pour le nœud en cours ne peut rentrer.
De plus, le tir de cette transition numérote les paquets afin que l’ordre d’entrée soit
respecté, grâce à la place p_next_in qui mémorise le numéro à affecter au prochain
jeton pour la classe de qualité de service et pour le nœud en question.
Enfin, lors de ce tir, les places p_log_cnt et p_log_o permettent d’archiver l’entrée
du paquet en file d’attente dans le but de mesurer le temps d’attente d’un paquet avant
d’être émis.
jeton de couleur ACH correspondant à une place dans la pile est déposé dans la place
p_comp_empty pour permettre une nouvelle entrée dans la file d’attente.
Lorsqu’un paquet est sélectionné, il est déposé dans la place p_one. La transition
t_out est franchissable et dépose un jeton contenant le paquet dans la place de sortie
p_out afin d’être mis en émission. De plus, l’entier contenu dans le jeton correspondant
au nœud et à la qualité de service du paquet mis en émission est incrémenté pour
mémoriser le numéro du prochain paquet à émettre. Le tir de t_out entraîne aussi la
décrémentation de l’entier correspondant à la file d’attente dans la place p_log_cnt, et
le dépôt d’un jeton dans la place p_log_o afin de permettre un nouvel enregistrement
de l’état du tampon dans le but de tracer l’évolution de la file d’attente.
Pour choisir le jeton à émettre dans la place p_buffer, la transition t_sel doit sé-
lectionner le jeton le plus ancien dans la pile correspondant à la classe de qualité de
service de plus forte priorité. L’ordre des priorités, défini par la norme 802.11e, est :
– VO (Vo-Ip),
– VI (Vidéo),
– BE (Best Effort)
– BK (Background).
Cette transition consulte donc les places p_next_in et p_next_out afin de déter-
miner si des paquets sont présents dans chaque file, ainsi que l’entier le plus ancien
correspondant au paquet à sélectionner. Ces deux arcs de consultation identifient les
variables suivantes aux entiers correspondants aux classes de qualité de service :
– n01 : paquet de classe VO le plus récent
– n11 : paquet de classe VI le plus récent
– n21 : paquet de classe BE le plus récent
– n02 : paquet de classe VO le plus ancien
– n12 : paquet de classe VI le plus ancien
– n22 : paquet de classe BE le plus ancien
– n32 : paquet de classe BK le plus ancien
La variable ac correspond à la classe de qualité de service du paquet correspondant
au jeton tiré dans p_buffer, et n correspond à l’entier associé au paquet. La condition
associée au tir de la transition t_sel est valide si un de ces 4 cas se présente (car ces 4
cas sont séparés par un opérateur ORELSE ).
– 1er cas : Si un paquet de classe de qualité de service VO est présent, il est tiré
en priorité. Pour sélectionner le paquet le plus ancien de cette file, n devra être
égal à n02 qui correspond au prochain numéro de classe VO à émettre.
– 2ème cas : Cette condition correspond au tir d’un paquet de classe VI. Le tir d’un
paquet de cette classe ne peut se faire que si [(n01=n02)], ce qui signifie que la file
de classe VO est vide. La condition [(n=n12)] permet de sélectionner le paquet
le plus ancien de la file VI.
– 3ème cas : Pour qu’un paquet de classe BE soit tiré, il faut que [(n01=n02)] ce
qui signifie que la file correspondant à la classe VO est vide, et que [(n11=n12)]
ce qui signifie que la file de la classe VI est aussi vide. La condition [(n=n22)]
permet de sélectionner le paquet le plus ancien dans la file BE.
– 4ème cas : Cette condition correspond au tir d’un paquet de classe BK. Dans ce
cas, les trois autres files doivent être vides. En effet, les conditions [(n01=n02)],
[(n11=n12)] et [(n21=n22)] vérifient que les files de classes VO, VI et BE sont
72 De la modélisation à la validation du simulateur
De cette manière les paquets sont priorisés suivant leurs classes de qualité de service,
et sur une même classe, l’ordre des paquets est préservé.
La macro transition Ifs permet au paquet d’attendre que le canal radio soit libre et
que le nœud n’ait pas reçu de paquet de contrôle RTS ou CTS l’empêchant d’émettre,
puis d’attendre la durée de la période intertrame comme le spécifie CSMA/CA. Son
initialisation est présentée figure 3.30.
Figure 3.30 – Modèle Ifs - 1ère étape - entrée du paquet et vérification du canal radio
Lorsqu’un paquet arrive dans ce sous modèle par la place d’entrée p_in, il attend
que la transition t_wait soit franchissable. En effet, cette transition consulte les places
d’entrée/sortie p_radio et p_rtscts_lock qui contiennent respectivement l’état du canal
radio de chaque nœud et l’état du mécanisme de blocage RTS/CTS. Il faudra que ces
deux places autorisent une émission pour le nœud courant.
Lors du tir de t_wait, le paquet est copié dans la place p_ifs afin d’attendre le délai
intertrame et dans p_ifs_save pour vérifier l’état du canal radio. La transition t_occ est
franchissable si la place p_radio indique que le nœud reçoit au moins un paquet, ou que
la place p_rtscts_lock indique que le nœud a reçu un RTS ou un CTS. Son tir déplace
le paquet de p_ifs_save dans la place p_occ et dans la place p_in afin de réinitialiser
le délai intertrame. La présence d’un paquet dans p_occ entraîne sa suppression après
le délai d’attente.
Description 75
Comme présenté dans la figure 3.31, un paquet présent dans la place p_ifs entraîne
la temporisation du temps intertrame. Le tir de la transition t_aifs consulte la place
p_init_host qui contient la configuration du nœud courant afin de lire le délai cor-
respondant à la classe de qualité de service du paquet. Celui-ci sera acheminé avec le
paquet dans la place p_aifs.
Ensuite, la place d’entré/sortie p_last_pk est consultée. Elle indique si le dernier
paquet reçu l’a été correctement ou a été altéré par le canal ou par une collision. S’il a
été correct, le tir de t_last_pk_ok déplacera le paquet dans la place p_temp. S’il a été
altéré, le tir de t_last_pk_bad déplace le paquet dans la place p_temp en modifiant le
délai. Celui-ci est augmenté du temps EIFS-DIFS comme spécifié dans la norme 802.11
à la suite d’un problème de transmission.
Dans ces deux cas, le paquet est présent dans la place p_temp avec le temps à
attendre. La transition temporisée t_temp applique ce délai et le paquet est déposé
dans la place p_end.
Pour finir, la figure 3.32 présente que si le canal radio n’est pas occupé et si aucun
paquet de contrôle RTS ou CTS n’a été reçu, une copie du jeton est disponible soit
76 De la modélisation à la validation du simulateur
dans p_ifs_save et la transition t_out déplace le paquet dans la place de sortie p_out
afin de passer en émission, soit le paquet est supprimé par la transition t_del car la
transition t_occ a déjà copié le paquet en entrée du modèle pour attendre un nouveau
délai intertrame. En effet, si une transmission est détectée pendant l’attente du délai
intertrame, celui-ci est réinitialisé, et redémarre à la fin de la transmission.
Cette macro transition Contention a pour but d’attendre un délai aléatoire. La figure
3.35 présente son initialisation.
78 De la modélisation à la validation du simulateur
Lorsqu’un jeton contenant un paquet se trouve dans la place p_em4, c’est que le
canal est libre et que les délais intertrames se sont écoulés. Le paquet est alors transmis
à la macro transition ACKRTSCTS qui gère l’émission des paquets de contrôle RTS et
CTS si nécessaire. Voici les liens entre ce module et le modèle MAC :
– les places p_list_rtscts_debit et p_list_debit permettent d’assigner dans le jeton
paquet la durée d’émission en fonction de la taille du paquet, et de configurer les
données contenues dans les paquets RTS et CTS.
– le contenu de la place p_rtscts_lock est mis à jour afin d’empêcher un paquet
d’être émis si le canal radio est réservé.
– la place p_wait_ack permet d’indiquer pour quel paquet un accusé de réception
est attendu. Ceci sera développé dans les parties suivantes.
– le paquet est déposé dans la place p_r_em s’il doit être émis, sinon le paquet est
dans la place p_em1 pour être réinjecté dans le processus d’émission.
– la place p_recv_rtscts permet de transmette les paquets reçus de type RTS et
CTS
– la place p_send_sifs permet d’émettre des paquets par la macro transition Send-
WithSIFS qui attend un délai intertrame court.
Les macro transitions ACKRTSCTS et SendWithSIFS peuvent déposer le paquet
à émettre dans la place p_r_em pour être transmis au modèle parent par la place de
sortie p_r_send afin qu’il soit passé à la couche Radio.
A l’arrivée d’un paquet dans la place d’entrée p_em_in, comme présenté figure 3.40,
soit le paquet est émis directement, soit un dialogue RTS/CTS précède le paquet.
– Si la taille du paquet est inférieure au seuil rtsth qui est défini dans la configuration
du nœud émetteur, le mécanisme RTS/CTS n’est pas utilisé, et le paquet doit être
émis directement. Dans ce cas, la transition t_without_rts déplace le paquet en
émission dans la place de sortie p_em_out pour être transmis à la couche Radio.
Le paquet est copié dans la place p_ack afin qu’un accusé de réception soit attendu
par ce paquet.
– Si la taille du paquet est supérieure ou égale au seuil, la transition t_with_rts crée
un paquet RTS contenant la durée de réservation du canal. Celle-ci est la somme
de la durée d’émission du paquet, de la réponse CTS, de l’accusé de réception et
de 3 SIFS. Ce RTS est déposé dans la place de sortie p_em_out afin qu’il soit
transmis à la couche Radio. De plus, le paquet est copié dans les place p_wait
et p_wait_cts afin de déclencher un timer en attente du paquet CTS. Le jeton
contenu dans la place complémentaire p_wait_comp est retiré pour mémoriser
l’état d’attente de CTS.
Comme présenté figure 3.41, suite à l’émission d’un RTS, la transition temporisée
t_wait attend la durée d’émission du RTS ainsi qu’un délai intertrame SIFS. Ensuite,
si le CTS est reçu, il est présent dans la place p_recv_cts, et la transition t_send_pkt
permet l’émission du paquet suite la réservation réussie du canal radio. Cependant, un
délai intertrame SIFS doit être attendu entre le CTS et le paquet. C’est pourquoi le
paquet est déposé dans la place de sortie p_sifs_out. Le modèle MAC transmet le
paquet dans la macro transition SendWithSIFS avant de le transmettre à la couche
Radio.
84 De la modélisation à la validation du simulateur
Si le CTS n’est pas reçu, ce qui arrive si le RTS ou le CTS n’a pas été transmis
correctement, la transition t_timeout est franchie et le paquet est déplacé dans la place
de sortie p_timeout qui va permettre de redémarrer le processus d’émission pour ce
paquet, avec le délai intertrame et la période de contention.
Lorsqu’un RTS ou un CTS est reçu dans la couche MAC, celui-ci est transmis dans
la place d’entrée p_recv_rtsctspkt. De même, la couche MAC copie les paquets reçus
dans ce module car c’est elle qui va générer l’accusé de réception. Ceci est présenté
figure 3.42.
– Si le paquet est un CTS destiné au nœud, la transition t_recv_cts le déplace
dans la place p_recv_cts pour permettre l’émission de paquet décrite dans le
paragraphe précédent.
– Si le paquet est un RTS destiné au nœud, la transition t_recv_rts crée un paquet
CTS annonçant la durée de réservation du canal à partir de la durée contenue
Description 85
dans la RTS à laquelle est soustraite la durée du CTS et un SIFS. Ce CTS est
déposé dans la place de sortie p_sifs_out afin qu’il soit transmis à la couche Radio
après un délai intertrame SIFS.
– Si un paquet qui n’est ni un RTS, ni un CTS est reçu, la transition p_recv_pkt
crée un accusé de réception dans la place de sortie p_sifs_out pour qu’il soit émis
après un délai intertrame SIFS.
– La réception de RTS ou de CTS non destiné au nœud courant, correspond à une
demande de réservation de canal. Dans ce cas, la transition t_recv_ext_rtscts
modifie la place d’entrée/sortie p_cts_lock afin d’interdire l’émission. En effet,
cette place est commune avec les modules Ifs et Contention. Ensuite la transition
temporisée t_rtscts_wait attend la durée contenue dans le paquet RTS ou CTS,
puis la transition t_cts_end libère la réservation de canal radio.
Ainsi, la figure 3.43 présente l’ensemble de la macro transition ACKRTSCTS qui
permet l’émission d’accusé de réception et la gestion de la réservation de canal radio
par le mécanisme RTS/CTS.
Le paquet qui doit être émis se présente par la place d’entrée p_send_sifs. Si le canal
est libre, et qu’il n’est pas réservé, ce qui est représenté par la consultation des places
p_radio et p_rtscts_lock, la transition t_in est franchie et permet la temporisation de
la transition t_wait pour la durée SIFS. Ensuite, si le canal est toujours libre et pas
réservé, la transition t_out dépose le paquet à la place p_r_em afin qu’il soit transmis
à la couche Radio pour être émis.
Si le canal est occupé, ou s’il est réservé par le mécanisme RTS/CTS, le paquet est
déplacé dans la place p_busy. Il est ensuite supprimé pour ne pas être émis en même
temps qu’une autre transmission ou pendant que le médium est réservé par un autre
nœud.
Lorsqu’un nœud reçoit un paquet, un jeton arrive dans la place p_r_receive. Celui-
ci provient du module Radio et contient le nœud receveur, le paquet et deux booléens
renseignant sur l’état du paquet. Le premier booléen est à vrai si le paquet est altéré
ou a subi une collision, et le second est à vrai si le paquet a été reçu au moment où le
nœud concerné émettait. Ce jeton est injecté dans le module MACReceive qui aiguille
les paquets reçus.
Cette macro transition peut déposer des jetons dans les places suivantes :
– Si le paquet est correct et destiné au nœud courant, il est transféré à la couche
LLC par la place de sortie p_l_reveive.
– Si le paquet est du broadcast, destiné à tous les nœuds, il est déposé dans la place
p_recv_all.
– Les accusés de réception reçus, destinés au nœud en cours, sont déposés dans la
place p_recv_ack.
– Les RTS, CTS, ainsi qu’une copie des paquets sont déposés dans la place p_recv_rtsctspkt,
pour être transmis au module ACKRTSCTS.
– La place p_last_pk doit contenir l’état du dernier paquet reçu pour définir le délai
intertrame des prochains paquets à émettre. Elle est mise à jour par ce module.
Ensuite, le paquet est aiguillé, ce qui est présenté sur la figure 3.47. Les transitions
supportant cet aiguillage sont :
– t_all déplace le paquet destiné à tous les nœuds dans la place p_recv_all. Ceci
est un cas particulier, car il ne peut pas y avoir d’accusé de réception.
– t_rtscts sélectionne les RTS et les CTS dans la place p_recv_rtsctspkt pour être
transmis au module ACKRTSCTS afin de réserver le canal radio.
– t_not_dest supprime les paquets reçus non destinés au nœud courant.
– t_ack sélectionne les accusés de réception et les déplace dans p_recv_ack.
Si aucune de ces transitions n’est tirée, le paquet est un paquet de données et la transi-
tion t_pkt le déplace dans p_pkt. Cette transition calcule la durée que mettra l’accusé
de réception pour arriver à son destinataire. Cette durée est calculée à partir de la taille
du paquet lue dans le paquet et du débit lu dans la place p_list_debit.
Figure 3.48 – Modèle MACReceive - 3ème étape - Suppression des paquets reçus en
double
Enfin, la figure 3.48 décrit la fin du parcours des paquets dans le module MACRe-
ceive. Avant d’accéder au module LLC, le paquet attend le délai correspondant à la
durée de l’accusé de réception calculé précédemment afin de ne pas être répété au nœud
suivant avant que l’accusé de réception ne soit émis.
Pour finir, si l’identifiant du paquet est déjà présent dans la place p_already, la
transition t_already ignore ce paquet. Sinon, la transition t_out ajoute l’identifiant
dans cette place, et délivre le paquet au module LLC par la place de sortie p_l_receive.
90 De la modélisation à la validation du simulateur
qu’un accusé de réception doit être attendu pour un paquet. Si RecvAck n’a pas reçu
d’accusé de réception dans le délai prévu, ce module replace le paquet en émission dans
la place p_em1. En cas d’accusé de réception correct, ce module supprime le compteur
de réémissions de la place p_nb_try, et indique dans la place p_ready que le nœud peut
débuter une nouvelle émission.
Une copie du paquet émis arrive dans la place d’entrée p_paquet_in avec un entier
indiquant combien de temps l’accusé de réception doit être attendu. Si le paquet n’est
pas un paquet de diffusion, la transition t_wait_ack copie le paquet dans la place
p_wait pour que la transition t_wait attende le délai prévu. Le paquet est aussi copié
dans la place p_wait_ack en attente de l’accusé de réception correspondant. De plus,
la transition p_wait_ack indique que le nœud est en attente d’accusé de réception en
prenant le jeton dans la place p_comp_wait_ack.
Si un accusé de réception n’est pas reçu suite à la transition temporisée t_wait, la
transition t_timeout réinitialise ce module et dépose le paquet dans la place p_timeout
pour qu’il soit réémis. L’évènement associé au tir de cette transition est enregistré afin
de retracer et de comptabiliser les échecs d’émission.
Si un accusé est reçu par la place d’entrée p_ack_in alors qu’un paquet est en
92 De la modélisation à la validation du simulateur
attente, la transition t_ack_ok est tirée, ce qui signifie que le paquet a été acquitté.
Ceci permet :
– la suppression du compteur de réémissions dans la place p_nb_essai. En effet,
celui sera recréé lors de la prochaine émission
– la création d’un jeton pour le nœud en cours dans la place p_ready. Ceci indique
que le nœud a terminé une émission et est disponible pour la suivante.
– la suppression du paquet dans la place p_wait_ack et le dépôt dans la place
p_cancel_timeout pour réinitialiser le modèle à la fin de l’émission.
Cet évènement est aussi enregistré pour indiquer les acquittements de paquets.
Si un accusé de réception est reçu alors que nœud ne l’attendait pas, la transition
t_old_ack permet de l’ignorer.
Chaque nœud de type point d’accès émet périodiquement des paquets en diffusion,
nommés beacons, pour indiquer qu’il est présent. Lorsqu’un beacon doit être émis, ce
module prend le jeton indiquant que le nœud n’est pas en cours d’émission dans la place
p_ready, et dépose le paquet de type beacon généré dans la place p_em2 pour qu’il
soit émis. Ce module est initialisé avec la configuration de tous les nœuds afin d’activer
l’émission de beacon pour les points d’accès seulement.
La place p_recv_all permet de transmettre à ce module les paquets de type beacon
reçus.
Pour chaque nœud de type point d’accès, la transition t_first crée un jeton iden-
tifiant le nœud associé au nombre de beacons à émettre. En effet, nous spécifions ce
nombre pour que la simulation s’arrête au bout d’un temps défini. Cette transition est
temporisée avec une durée aléatoire afin que tous les nœuds, démarrant la simulation
en même temps, ne soient pas synchronisés. Ceci permet de se rapprocher de la réalité
où il est très improbable que tous les nœuds démarrent strictement au même moment.
Ensuite, la transition t_beacon génère un identifiant de nœud périodiquement pour
chaque nœud dans la place p_send. La fréquence est spécifiée par la constante BEA-
CONTIME. Par défaut, celle-ci est configurée à 100ms. Cependant, ceci peut être un
levier car cette fréquence peut être configurée dans le matériel que nous utilisons.
Ainsi, la transition t_send génère un beacon si la place d’entrée p_ready indique
que le nœud n’est pas en cours d’émission. Le paquet généré est déposé dans p_b_send
pour être émis par le modèle parent MAC.
Les parties du modèle MAC présentées précédemment sont assemblées sur la figure
3.54. Ce modèle émet les paquets fournis par le modèle LLC et lui transmet les paquets
reçus.
94 De la modélisation à la validation du simulateur
La figure 3.55 présente le transit d’un paquet des modules application au module
MAC.
Description 95
Les couches applications ICMP et UDP fournissent des paquets de couleur PA-
QUETSIMP. Cette couleur est une composition de :
– sa : identifiant du nœud source
– da : identifiant du nœud destination
– ac : classe de qualité de service de ce nœud
– data : identifiant du nœud
– typ : type du paquet (UDP ou ICMP)
– length : taille du paquet
Dans cette structure, nous n’avons pas les identifiants des nœuds intermédiaires trans-
metteur et receveur, car le rôle de ce module est de les configurer.
Le paquet est fourni par les couches supérieures via la place d’entrée p_send. Le
tir de t_send n’est possible que si la place complémentaire p_l_e_comp est marquée.
Ceci indique que la file d’attente du module MAC n’est pas pleine. Ce tir détermine le
prochain nœud qui doit recevoir le paquet en consultant la matrice de chemin contenue
dans la place p_list_chemin. De plus, il indique dans la place complémentaire p_comp
que le paquet de la place p_send a bien été consommé, et qu’un nouveau paquet peut
être pris en compte. La place p_id incrémente un entier pour compter le nombre de
paquets introduits dans le réseau maillé.
Ensuite, la transition t_em est tirée pour transmettre le paquet au module MAC.
Celle-ci archive l’évènement indiquant qu’un paquet est transmis au module MAC pour
être émis.
96 De la modélisation à la validation du simulateur
Comme le présente la figure 3.56, le module MAC fournit les paquets reçus, ayant
comme receveur le nœud en cours dans la place d’entrée p_l_receive. La transition
t_recv est tirée et archive l’évènement indiquant qu’un paquet est fourni par le module
MAC. Le paquet est déposé dans la place p_recv.
Si le paquet n’est pas destiné au nœud en cours, il doit être répété pour être acheminé
jusqu’à sa destination. Si la place complémentaire p_l_e_comp est marquée, ce qui
indique que la file d’attente du module MAC n’est pas pleine, la transition t_repetition
consulte la matrice de chemin pour indiquer le prochain receveur, et le paquet est placé
en émission dans la place p_em.
Si la transition t_repetition ne peut pas être tirée car la file d’attente du modèle
MAC est pleine, le paquet reste dans p_recv. Si un second paquet arrive dans cette
place, la transition t_buffer est tirée pour supprimer ce second paquet. Ceci interdit
aux paquets d’être en attente dans le modèle LLC.
Figure 3.57 – Modèle LLC - 3ème étape - Réception de paquet pour le nœud courant
La figure 3.58 présente le modèle LLC complet. Celui-ci ne permet des relais de
paquet qu’en suivant une matrice de chemin configurée de manière statique. Cependant,
98 De la modélisation à la validation du simulateur
faire évoluer ce module pour implémenter des chemins dynamiques est possible sans
toucher aux autres parties du modèle.
La réception de paquet est présentée sur la figure 3.60. Ils arrivent dans la place
d’entrée p_receive. La transition t_recv filtre les paquets UDP, et lit la date de la
génération du paquet dans la place p_wait. Les dates de départ et d’arrivée sont déposées
dans la place p_stock. Si un paquet n’est pas arrivé au bout de 100 secondes, la transition
t_clear est tirée, ce qui enregistre une date d’arrivée de 0 dans la place p_stock.
La transition t_stat archive les dates de départ et d’arrivée des paquets dans un
fichier dans l’ordre de création des paquets afin de permettre d’établir des statistiques
de transmissions.
De même que le modèle UDP, le modèle ICMP permet de générer des paquets.
Cependant, il permet de mesurer le délai aller/retour des paquets.
La configuration du flux à générer est faite dans le modèle parent Network. La figure
3.62 présente la génération de paquets. Les paquets se présentent dans la place d’entrée
p_init_icmp. La transition t_init sépare le type du paquet dans la place p_init2, et le
nombre de paquets à émettre dans la place p_cout.
La fréquence d’émission de ce type de paquet est configurable au niveau de la transi-
tion t_new. Cette transition est tirée pour chaque requête à émettre, toutes les 100 ms
dans cet exemple. La place p_cnt, modifiée à chaque tir de t_new, permet d’individuali-
ser le champ data de chaque paquet. Ensuite, la transition t_send permet de transférer
le paquet à émettre au module LLC par la place p_send, si la place p_comp indique
que LLC peut mettre en file d’attente les paquets dans le modèle MAC. De plus, la
transition t_send copie le paquet en le datant dans la place p_wait afin d’archiver les
dates d’émission de ces paquets ICMP.
Description 101
La réponse aux requêtes ICMP est présentée sur la figure 3.63. Lorsque ce paquet
est arrivé à son destinataire, il se présente dans la place p_receive. C’est alors une
requête ICMP. La transition t_reply génère alors une réponse dans la place p_send
en inversant source et destination, et en spécifiant le type de paquet ICMP_RP pour
indiquer que c’est une réponse. Cette transition n’est franchissable que si les couches
inférieures peuvent mettre ce paquet en file d’attente, selon la place complémentaire
p_comp.
102 De la modélisation à la validation du simulateur
La figure 3.64 présente l’arrivée d’une réponse ICMP. Dans ce cas, la transition
t_recv date cette arrivée, lit la date de départ dans la place p_wait, et dépose ces dates
dans la place p_stock. Lorsque le compteur d’émission p_cnt est à 0, la transition t_end
permet d’attendre 100 secondes que toutes les réponses arrivent. Ensuite, la transition
t_clear indique les paquets qui ont été perdus dans la place p_stock en spécifiant une
date d’arrivée de 0.
La transition t_stat archive alors dans l’ordre des générations de paquets les dates
de départ et d’arrivée de paquets.
Ce module permet de mesurer le RTT entre plusieurs nœuds, avec ou sans autre
transmission concurrente. Cependant, une première utilité est de valider ce modèle avec,
dans un premier temps, la simulation d’une communication simple.
3.5 Validation
Il est nécessaire de valider que le simulateur est conforme aux spécifications initiales,
et donc de vérifier que la modélisation effectuée correspond bien au comportement
attendu. C’est pourquoi, dans un premier temps, nous pouvons énumérer les mécanismes
implémentés dans le modèle afin de présenter par la suite la méthode de validation
de leurs comportements dans le modèle. Ensuite, nous montrerons que le modèle met
correctement en œuvre ces différents mécanismes, dont certains constituent des leviers
sur lesquels nous allons agir pour estimer leur contribution à la gestion de la QoS.
De multiples simulations ont été effectuées, mais nous n’en présenterons que certaines
dont les scénarii permettent de valider les différents mécanismes énumérés.
Cette méthode d’accès au médium définit que lorsqu’un nœud veut émettre, il doit
attendre que le canal radio soit libre. De plus, un nœud ne pourra pas détecter
d’erreur de transmission lorsqu’il émettra car il ne peut pas écouter le canal radio.
Le récepteur devra donc émettre un accusé de réception afin d’acquitter le paquet
reçu.
– MM3 : Temporisation d’un temps intertrame
La méthode d’accès du WiFi définit que le nœud émetteur doit vérifier que le
canal soit libre pendant une durée appelée temps intertrame. Cette durée dépend
de plusieurs paramètres. Ce délai est défini d’une part pour chaque classe de
qualité de service et type du nœud émetteur (point d’accès ou station), et d’autre
part en fonction de la bonne réception du dernier paquet.
– MM4 : Temporisation d’une période de contention
Si le paquet attend que le canal soit libre pour être émis, après avoir attendu la du-
rée intertrame, il tire une durée de période de contention. La norme 802.11 définit
que le nœud tire aléatoirement une durée décrite dans le chapitre modélisation.
– MM5 : Suppression de paquet reçu en double
Si un accusé de réception est perdu, l’émetteur du paquet ne sait pas que le
receveur a bien reçu le paquet. Il va donc réémettre. La norme 802.11 prévoit
de ne pas transmettre à la couche supérieure les doublons. Il doit cependant les
acquitter de manière à éviter une nouvelle émission.
– MM6 : Retransmission si l’accusé de réception n’est pas reçu
Si un nœud ne reçoit pas d’accusé de réception à la suite d’un envoi de paquet, il
doit réémettre. Si ce scénario se produit plus du nombre maximum de réémissions
autorisées, le paquet ne doit plus être réémis.
– MM7 : Utilisation conditionnée de paquet de contrôle RTS/CTS
Si la taille du paquet à émettre est supérieure au seuil d’activation de ce méca-
nisme, un paquet de contrôle RTS devra être émis avant d’émettre le paquet afin
de réserver le médium. Celui-ci devra contenir la durée pendant laquelle il réserve
le canal WiFi.
– MM8 : Réponse d’un CTS à un RTS
Les nœuds respectant la norme 802.11 doivent répondre un CTS si un RTS leur
est destiné.
– MM9 : Blocage de l’émission en cas de réception de RTS ou CTS
Les nœuds recevant des paquets de contrôle RTS ou CTS ne doivent plus émettre
de paquet, à l’exception du nœud qui doit répondre le CTS à la suite d’un RTS,
et du nœud devant transmettre le paquet à la suite du CTS.
– MM10 : Emission périodique de beacon
Un nœud de type point d’accès doit diffuser périodiquement des paquets pour
signaler sa présence à des stations voulant s’y connecter.
L’objectif ici est de valider l’implémentation (partielle) du protocole ICMP sur lequel
nous allons nous appuyer pour effectuer des mesures sur l’architecture étudiée.
– MI1 : Emission périodique de paquet
Ce protocole doit émettre périodiquement des requêtes ICMP afin qu’elles soient
acheminées à travers le réseau. La date d’émission doit être mémorisée afin de
pouvoir calculer le RTT (Round Trip Time - temps aller-retour)
– MI2 : Réponse aux requêtes ICMP
Lorsqu’une requête ICMP est reçue par le modèle de ce protocole, une réponse
doit être émise à son expéditeur.
– MI3 : Mémorisation des RTT
A chaque réception de réponse ICMP, le RTT doit être calculé par rapport à
la date de l’émission de la requête. Cette valeur doit être mémorisée afin d’être
rapportée à la fin de la simulation.
Le cas d’un camping permet de relever plusieurs problèmes. Tout d’abord, des arbres
permettent aux vacanciers d’avoir de l’ombre, mais altèrent aussi les communications
radio sur la bande de fréquence de 2,4 GHz. De plus, le relief du terrain qui ne peut
être lisible sur la carte affaiblit aussi certaines communications. Ainsi, des erreurs de
communications dues à l’environnement ou au problème du nœud caché apparaissent.
La figure 3.66 présente la position des bornes sur un plan, ainsi que le niveau de
réception des liens mesuré entre chaque nœud ainsi que le débit physique réellement uti-
lisé en pratique. Les nœuds 1 à 6 sont des points d’accès maillés aux positions indiquées
sur le plan, et les nœuds 7 et 8 sont des stations respectivement proches des bornes 5
et 6. Le tableau 3.6 présente les différents nœuds avec leurs paramètres. De plus, cette
topologie permet de renseigner les matrices de rapports signal sur bruit (table 3.7) et
de chemins (table 3.8) qui pourront être intégrées dans le simulateur.
Nœud récepteur
1 2 3 4 5 6 7 8
1 0 33 1 0 1 0 0 0
2 35 0 16 6 18 0 0 0
3 1 16 0 19 29 3 20 0
4 0 6 18 0 9 34 20 20
Nœud éméteur
5 1 17 29 8 0 2 40 0
6 0 0 3 35 4 0 0 40
7 0 0 20 20 40 0 0 0
8 0 0 0 20 10 40 0 0
Nœud destinataire
1 2 3 4 5 6 7 8
1 1 2 2 2 2 2 2 2
2 1 2 3 3 3 3 3 3
3 2 2 3 4 5 4 5 4
4 3 3 3 4 3 6 3 6
Nœud source
5 3 3 3 3 5 3 7 3
6 4 4 4 4 4 6 4 8
7 5 5 5 5 5 5 7 5
8 6 6 6 6 6 6 6 8
Les simulations effectuées par notre logiciel fournissent des fichiers texte reportant
les évènements. Ceci est difficilement exploitable. Ces traces sont donc converties sous
forme graphique par un script conçu à cet effet.
Ces graphes représentent ce qu’il s’est passé lors d’une simulation au cours du temps.
Le temps est donc en abscisse en microseconde. En ordonnée, chaque ligne correspond
à un nœud du réseau. La légende est présentée figure 3.67.
Validation 109
– Détection de signal
La surface correspondante à un nœud qui est dans une zone où se propage un signal
sera grisée. Ceci permet de voir quels nœuds sont influencés par une émission.
– Emission
Le trait noir épais signifie qu’un nœud est en train d’émettre.
– IFS puis période de contention : Les deux traits précédant une émission repré-
sentent successivement le temps d’attente intertrame, puis la durée de la période
de contention.
– Réception altérée
Cette croix peut être présente à la fin d’une transmission pour chaque receveur.
Sa présence signifie que la réception a échoué suite au tir aléatoire de la décision.
– Accusé de réception reçu : Ce symbole précise qu’un nœud a reçu l’accusé de
réception qui lui était destiné, ce qui acquitte la transmission.
– Détection de collision
Lorsqu’un récepteur reçoit deux paquets à la fois, il y a collision. Ce symbole
apparaît lorsqu’un paquet est marqué comme ayant reçu une collision.
– Collision
Lorsque deux paquets sont en collision, la surface correspondante au nœud qui
reçoit plusieurs paquets en même temps est en gris foncé.
– Délai d’attente d’accusé de réception dépassé
Ce symbole définit qu’un accusé de réception n’a pas été reçu dans le délai imparti
par le nœud qui a émis le paquet.
– Paquet reçu en même temps qu’une émission
Si deux nœuds voisins décident d’émettre au même moment, ils ne pourront pas
recevoir le paquet de l’autre car ils sont en émission. Ce symbole, situé en début
d’émission indique la perte d’un paquet à cause de ce mécanisme.
– Paquet reçu en double
Si un nœud reçoit deux fois le même paquet, la norme 802.11 prévoit de ne délivrer
que le premier paquet à la couche supérieure. Ce symbole indique que ce paquet
est en double, et qu’il ne sera pas acheminé à la couche supérieure.
110 De la modélisation à la validation du simulateur
Afin d’effectuer seulement une requête ICMP, les modules UDP et Beacon sont
désactivés. En effet, un jeton contenant l’entier 0 initialisera la place p_count du modèle
Beacon, et la place p_conf_udp du modèle Network sera vide. Le modèle ICMP est
configuré en plaçant le jeton suivant dans la place p_conf_icmp du modèle Network :
– Source : Nœud 1
– Destination : Nœud 8
– Classe de qualité de service : BK (background)
– Type de paquet : ICMP_RQ (Requête ICMP)
– Taille du paquet : 500 octets.
– Identifiant du paquet ICMP : 0
Le graphe généré à partir des traces enregistrées lors de cette simulation est présenté
sur la figure 3.68. Nous allons détailler ce graphe pour mettre en évidence que les
différents mécanismes mis en jeu ont été modélisés correctement.
Figure 3.69 – Première partie du graphe généré lors d’un échange ICMP
Au temps 0, le nœud AP1 doit émettre la requête ICMP vers STA8. La couche
LLC consulte la matrice de chemins pour connaître le prochain receveur : il s’agit de
AP2, comme le définit le mécanisme ML1. Après avoir vérifié que le canal radio soit
libre, comme le spécifie le CSMA/CA (MR2 et MM7), il attend la durée d’un temps
intertrame pour station tel que défini par MM3. Ensuite, il va tirer aléatoirement une
période de contention dans l’intervalle [ 0 ; 4 ] comme le prévoit le mécanisme MM4. La
valeur 3 a été tirée, ce qui correspond à un délai de 60 µs.
Ensuite, le nœud AP1 peut émettre le paquet, ce qui est représenté par le trait
désigné par Emission. L’entier 0 au dessus du trait d’émission indique la valeur du
champs data du paquet. Les nœuds AP1, AP2, AP3 et AP5 sont grisés comme cela est
défini par le mécanisme MR1, pour indiquer qu’ils sont dans une zone détectant cette
transmission. Donc, la couche Radio a bien consulté la matrice d’atteignabilité puisque
les autres nœuds ne perçoivent pas cette transmission ; en effet, la configuration définit
que seuls ces nœuds sont dans la zone de réception de AP1. Notons que les nœuds AP3
et AP5 ont aussi reçu le paquet, ce qui est représenté par le fond grisé. Cependant, ils
ne donnent pas suite car ils n’étaient pas concernés par ce paquet. De plus, la croix au
niveau de AP5 indique que ce nœud n’a pas reçu le paquet correctement car la réception
a été altérée par l’environnement.
En réponse à ce paquet, le nœud AP2 qui a correctement reçu le paquet de AP1,
attend un délai intertrame d’une durée SIFS définie dans la norme (MM3), puis émet
112 De la modélisation à la validation du simulateur
Le nœud AP2 ayant correctement reçu ce paquet, il doit le réémettre à AP3 afin qu’il
soit acheminé vers son destinataire. La couche LLC a consulté la matrice de chemins
comme défini par le mécanisme ML3. Il attend donc un délai intertrame puis une période
de contention. Le délai intertrame est plus court dans le cas d’un point d’accès que dans
le cas d’une station tel que spécifié par le mécanisme MM3. La période de contention est
tirée aléatoirement comme le définit le mécanisme MM4. Ensuite, le nœud AP2 émet le
paquet. La transmission dure plus longtemps car le débit physique de ce lien est configuré
plus lent mais elle se déroule correctement et le nœud AP3 reçoit le paquet. Celui-ci
émet le paquet à AP4 mais lors de cette transmission le tir aléatoire du mécanisme
MR5 indique que le paquet reçu par le nœud AP3 a été altéré. Ceci est indiqué par
la croix sur la ligne de AP4. Vu qu’il n’a pas reçu correctement le paquet, il ne va
pas émettre un accusé de réception. Le délai d’attente d’accusé de réception du nœud
AP2 est écoulé (MM6), ce qui est représenté par le symbole "délai d’attente d’accusé
de réception dépassé", et le paquet est alors réémis par le nœud AP3.
Le paquet est ensuite acheminé jusqu’au nœud STA8, selon les mêmes mécanismes
que ceux que nous venons de valider. Les nœuds AP5 et STA7 n’ont pas été sollicités
car ils ne sont pas impliqués dans le chemin allant du nœud 1 au nœud 8.
La réponse par le nœud STA8 à la requête ICMP provenant du nœud AP1 est
disponible sur la figure 3.70.
Une fois la requête ICMP reçue, le nœud STA8 doit alors émettre sa réponse au
nœud AP1, tel que défini par le mécanisme MI2. L’émission du nœud STA5 valide
que la couche LLC (mécanisme ML2) a bien délivré le paquet à la couche ICMP du
destinataire.
Cette simulation met en œuvre les mécanismes MR1, MR2, MR5, MM1, MM2, MM3,
MM4, MM6, ML1, ML2, ML3 et MI2 implémentés dans le modèle. Leurs fonctionne-
ments correspondent à la norme 802.11 et/ou aux spécifications initiales représentées
sur notre modèle.
Validation 113
Figure 3.70 – Seconde partie du graphe généré lors d’un échange ICMP
Lors de cette simulation, nous utiliserons d’une part des requêtes ICMP, et d’autre
part des émissions UDP. Le modèle Beacon sera désactivé en initialisant la place p_count
par un jeton contenant l’entier 0.
Les paramètres des paquets ICMP sont identiques à la simulation précédente à
la différence que nous émettrons 3 requêtes ICMP. Ces paquets ayant pour classe de
qualité de service BK, ils auront la priorité la moins importante. La temporisation de la
transition t_new est de 10000 µs. Ceci signifie qu’une requête ICMP sera émise chaque
10ms, et que la première partira à la date 10 ms.
Trois émissions UDP sont programmées pour cette simulation. La place p_conf_udp
du modèle UDP contiendra les paquets suivants :
– à la date 26000 µs, émission d’un paquet UDP de classe VI (vidéo), et de taille
1500 octets allant du nœud 1 au nœud 5.
114 De la modélisation à la validation du simulateur
– à la date 34000 µs, émission d’un paquet UDP de classe VI (vidéo), et de taille
1500 octets allant du nœud 1 au nœud 5.
– à la date 39000 µs, émission d’un paquet UDP de classe VO (voix), et de taille
1000 octets allant du nœud 2 au nœud 4.
Cette date étant la date de mise en émission, le paquet sera placé dans la file d’attente
correspondante à la classe du paquet et ne sera émis que lorsque le canal sera libre.
Le graphique 3.71 nous permet de valider la mise en file d’attente périodique des
requêtes ICMP, décrite par le mécanisme MI1. En effet, chaque flèche sous le graphe
indique une date à laquelle est programmée la mise en file d’attente de paquet. La
première requête ICMP est émise à la date 10000 µs. Le canal étant occupé à la date
20000 µs, la seconde est émise légèrement plus tard. De même pour la troisième, elle
n’est émise qu’un peu après 30000 µs. De plus, les paquets UDP sont bien émis aux
dates demandées, ce qui permet de valider le mécanisme MU1.
Validation 115
Figure 3.73 – Echanges ICMP et UDP zoomée peu après la date 30000 µs
Afin de valider les priorités des classes de file d’attente, le paquet numéro 7 de
type UDP et de classe de qualité de service VO (voix, classe la plus prioritaire) est
mis en file d’attente à la date 29000 µs sur la figure 3.73. Ce paquet a été acheminé
jusqu’au nœud AP2, tout comme le paquet ICMP numéro 2. Ces deux paquets sont
donc en concurrence, et c’est le paquet UDP de classe VO qui est émis en priorité. Le
mécanisme MMI est donc validé.
Nous pouvons constater sur le graphique 3.74 la présence de dialogue RTS CTS
118 De la modélisation à la validation du simulateur
Lors de cette simulation, nous activons l’émission périodique de beacon par les points
d’accès.
Seul le module Beacon est activé et initialisé avec l’entier 4 dans la place p_count
du modèle Beacon. Celui-ci spécifie le nombre de paquets à émettre pour chaque point
d’accès. Sur le terrain, un point d’accès émettrait ce type de paquet tant qu’il est allumé,
mais nous limitons ce module avec une valeur faible afin de rendre plus lisible le résultat
de cette simulation.
De même, les modules UDP et ICMP sont désactivés pour faciliter la lecture des
résultats.
3.5.8 Conclusion
Cette validation permet d’assurer que le modèle correspond bien à la norme 802.11,
avec une granularité connue pour chaque module. Ainsi, les simulations permettent de
détailler les transmissions sur un réseau WiFi maillé et de mettre en avant des situations
affectant la qualité de service. Des modifications pourront être apportées via certains
leviers, et de nouvelles simulations permettront d’observer une amélioration ou une
dégradation de la qualité de service.
De plus, l’évolutivité de ce modèle pourra permettre d’une part de modéliser plus
en détail les parties où la granularité sera déterminée comme insuffisante, et d’autre
part de modéliser d’autres leviers, dès lors qu’ils pourront être appliqués sur le matériel
utilisé.
Le simulateur et ses modèles sous-jacents ayant été validés, il est désormais possible
d’exploiter le simulateur, dans son domaine de validité, en ayant confiance dans la
pertinence des résultats générés.
120 De la modélisation à la validation du simulateur
Chapitre 4
Exploitation du simulateur
4.1 Introduction
Cet outil nous permet de simuler des transmissions au travers d’un réseau maillé
dans le but de trouver des actions permettant l’amélioration de la qualité de service.
121
122 Exploitation du simulateur
L’altimétrie ainsi que les zones boisées ou non boisées ne sont pas représentées sur
ce plan. Cependant, les rapports signal sur bruit et les débits physiques sont indiqués.
C’est pourquoi le lien 2-3 est plus faible que le lien 1-2 alors qu’ils paraissent à la même
distance.
Tous ces nœuds communiquent sur le même canal dans le but de faire apparaître
les problèmes présentés précédemment. En effet, le nœud 1 ne capte pas le nœud 4. Les
paquets émis par ceux-ci peuvent donc entrer en collision.
4.2.2 Résultats
Dans un premier temps, nous gardons les valeurs par défaut et nous injectons un
flux classique dans le but d’observer la qualité de service.
Sur cette topologie est configurée un flux de 1000 paquets de 1500 octets allant du
nœud 1 au nœud 4. Ce flux est de type UDP, et remplit le buffer d’émission du nœud 1.
Lorsque ce nœud a l’opportunité d’émettre, les paquets sont relayés par les nœuds 2 et 3
jusqu’au nœud 4. Il n’y a pas d’accusé de réception au niveau Transport ou Application.
Seul les accusés de réception de la couche Liaison seront émis comme le prévoit la norme
802.11.
La courbe 4.2 correspond au nœud 2. Nous pouvons constater qu’elle croit jusqu’à
atteindre le maximum. L’arrivée à ce seuil, qui correspond à la taille de la file d’attente,
révèle des pertes de paquets par la couche LLC qui supprime les paquets quand la
couche MAC ne peut pas les accueillir. Ceci est confirmé par le tableau 4.1 qui présente
le nombre de paquets perdus à cause d’une file d’attente pleine.
Figure 4.3 – Etat des files d’attente des nœuds 3 et 4 avec un flux 1-4
Table 4.1 – Nombre et cause des pertes sur chaque lien pour la simulation 1-4
à cause d’un manque de place dans la file d’attente, il est immédiatement perdu.
Le flux injecté allant du nœud 1 au nœud 4, les liens 2-1, 3-2 et 4-3 ne transportent
que les accusés de réception, c’est pourquoi les nombres de pertes comptabilisées sont
plus faibles que sur les autres liens.
Suite à un problème de transmission de type collision, paquet perdu ou erreur radio,
la couche MAC 802.11 prévoit des réémissions, alors qu’en cas de pertes dues à un
dépassement de la capacité de la file d’attente, le paquet est perdu et aucune réémission
n’est prévue.
Parmi les traces générées par le simulateur, le compteur de paquets reçus au niveau
UDP indique que 307 paquets sur 1000, soit 31 %, n’ont pas été reçus. De plus, le débit
au niveau de la couche UDP est de 2067 Kbit.s−1 , le délai moyen est de 838 ms avec un
écart type de 242 ms. L’écart type correspond la gigue dans le cas d’une transmission
de voix sur IP. Cette valeur reflète la qualité audio.
Ce fort taux de pertes est principalement dû à la saturation des files d’attentes. En
effet, seulement 1 paquet a été perdu à cause de collisions, receveurs en émission et
erreurs radio.
Figure 4.5 – Etat des files d’attente des nœuds 2 et 3 avec un flux 1-6
Figure 4.6 – Etat des files d’attente des nœuds 2, 3 et 4 avec un flux 1-6
Enfin, l’état de la file d’attente du nœud 4, présent sur la courbe noire de la figure
Simulation dans une configuration de référence 127
4.6, retransmet ses paquets au rythme où il les reçoit vers le nœud 6 et l’état de sa
file d’attente reste peu rempli. Les courbes grises rapellent l’état des files d’attente des
nœud 2 et 3.
Le tableau 4.2 présente le nombre et les raisons des pertes de paquet.
Table 4.2 – Nombre et cause des pertes sur chaque lien pour la simulation 1-6
Dans cette simulation, les traces indiquent que 201 paquets sur 1000 (20 %) n’ont pas
été reçus au niveau de la couche UDP du destinataire. L’ajout d’un nœud supplémentaire
dans la transmission a diminué le taux de pertes de paquets dû à la saturation des files
d’attente. De plus, le débit UDP est de 1813 Kbit.s−1 . Le délai moyen est de 1399 ms
et l’écart type de 435 ms. Le débit et le délai sont moins bon que lors de la simulation
précédente, et peut être expliqué d’une part par l’ajout d’une étape à la transmission, ce
qui allonge la durée du transfert, mais aussi parce que 10 % de paquets supplémentaires
ont réussi à arriver à destination.
[Link] Discussion sur les différences constatées entre les flux 1-4 et 1-6
– Si le nœud tire une valeur strictement inférieure à celles tirées par les autres
nœuds, il gagne la période de contention, et vu qu’il est le seul, le paquet est
émis correctement. Par exemple, le nœud 1 de la figure 4.7 émet son paquet avec
succès.
– Si le nœud a perdu car il n’a pas la valeur minimum et qu’il n’y a pas de collision,
il ne va pas émettre. C’est le cas du nœud 3 sur la figure 4.7.
– Si le nœud tire le minimum, mais que d’autres nœuds l’ont tiré aussi, il va donc
émettre en même temps que les autres nœuds ayant tirés la même valeur. Les
émissions rentrent donc en collision et ce n’est que l’absence d’accusé de réception
qui va indiquer cette collision. Le prochain délai intertrame est AIFS - DIFS +
EIFS. Par exemple, sur la figure 4.8, le nœud 1 produit une collision avec le nœud
2.
– Si plusieurs autres nœuds tirent le minimum. Le nœud a perdu et ne va pas
émettre, mais les autres nœuds rentrent en collision. Celle-ci est détectée, et le
prochain délai intertrame est AIFS - DIFS + EIFS, comme par exemple le nœud
3 dans 4.8.
En se plaçant au niveau du nœud 3, le canal radio est partagé entre les 5 nœuds 1,
2, 3, 4 et 6. Si ces 5 nœuds, ayant ces mêmes paramètres, ont des paquets à émettre, le
tableau 4.4 montre que la probabilité qu’une collision se produise est de 52 %. De plus,
la probabilité d’émettre correctement lors de la première tentative est de 9%.
Afin de ralentir l’injection de flux au niveau du nœud 1, nous pouvons augmenter
son temps intertrame AIFS de 2 à 3. Le tableau 4.5 indique que les nœuds 2 et 3 ont
une probabilité plus importante de réussir une émission alors que la probabilité de gain
du nœud 1 passe donc de 21 % à 7 %. Donc, cette action sur les leviers permettent de
favoriser le relais de paquets, ce qui devrait limiter dès lors le phénomène de saturation
dans les files d’attente des nœuds concernés.
130 Exploitation du simulateur
Un autre levier est le paramètre CWmin . Dans le tableau 4.6, ce paramètre qui avait
la valeur 3 est modifié à la valeur 4 pour le nœud 1. De même que l’action sur le levier
précédent, mais de manière moins importante, le nœud 1 a une priorité plus faible que
les autres.
Figure 4.9 – Evolution de la file d’attente du nœud 2 avec un flux 1-4 et modification
du paramètre AIFS sur le nœud source
Figure 4.10 – Evolution des files d’attente des nœuds 2 et 3 avec un flux 1-4 et modi-
fication du paramètre AIFS sur le nœud source
132 Exploitation du simulateur
Table 4.7 – Nombre et cause des pertes sur chaque lien pour la simulation avec un flux
1-4 et modification du paramètre AIFS sur le nœud source
Cette même modification du levier AIFS est appliquée sur un flux transitant du
nœud 1 au nœud 6.
Ralentissement de l’injection de flux au niveau de la source du trafic 133
Figure 4.11 – Evolution de la file d’attente du nœud 2 avec un flux 1-6 et modification
de AIFS
L’état de la file d’attente du nœud 2 est présenté sur la figure 4.11. Dans ce cas, elle
reste faible avec un remplissage allant jusqu’à 20 paquets. La taille de la file n’est donc
pas atteinte, et aucune perte de paquet n’est due à un dépassement de la capacité du
buffer sur ce nœud.
Figure 4.12 – Evolution des files d’attente des nœuds 2 et 3 avec un flux 1-6 et modi-
fication du paramètre AIFS sur le nœud source
Figure 4.13 – Evolution des files d’attente des nœuds 2, 3 et 4 avec un flux 1-6 et
modification du paramètre AIFS sur le nœud source
Table 4.8 – Nombre et cause des pertes sur chaque lien pour la simulation avec un flux
1-6 et modification du paramètre AIFS sur le nœud source
Le tableau 4.8 indique bien qu’aucune perte de paquet n’est due à une saturation
de file d’attente.
Dans cette simulation, seulement 5 paquets sur 1000 (5 %) n’ont pas été acheminés
à la couche UDP du destinataire. Ces pertes ne sont pas dues à une saturation de files
d’attente, mais à des problèmes radios. Le débit mesuré au niveau de la couche UDP
est de 1935 Kbit.s−1 , ce qui est mieux que lors de la simulation ayant les leviers aux
valeurs par défaut qui était de 1813 Kbit.s−1 .
Le délai moyen est de 735 ms avec un écart type de 175 ms. Ces résultats sont
nettement meilleurs à ceux mesurés avec les valeurs par défaut (délai moyen de 1399 ms
avec un écart type de 435 ms).
L’action sur ce levier est donc très positive dans ce cas, car le taux de perte est
divisé par 4 sans impact conséquent sur le débit applicatif.
Ralentissement de l’injection de flux au niveau de la source du trafic 135
Figure 4.14 – Evolution de la file d’attente du nœud 2 avec un flux 1-4 et modification
du paramètre CWmin sur le nœud source
La figure 4.14 présente l’état de la file d’attente du nœud 2. Dans ce cas, elle arrive
à saturation au bout d’une seconde, ce qui entraîne des pertes de paquets.
Figure 4.15 – Evolution des files d’attente des nœud 2 et 3 avec un flux 1-4 et modifi-
cation du paramètre CWmin sur le nœud source
La file d’attente de la borne 3 reste peu remplie, comme nous pouvons le constater
sur la courbe noire de la figure 4.15.
Le tableau 4.9 montre que l’action sur ce levier provoque moins de pertes dues à
une file d’attente pleine qu’avec la valeur par défaut présenté sur le tableau 4.1.
136 Exploitation du simulateur
Table 4.9 – Nombre et cause des pertes sur chaque lien pour la simulation 1-4 avec
modification du paramètre CWmin sur le nœud source
Sur cette simulation, 251 paquets sur 1000 (25 %) ont n’ont pas été reçu au niveau
de la couche UDP. Nous pouvons constater une sensible amélioration par rapport à
la simulation ayant les leviers aux valeurs par défaut, pour laquelle le taux de perte
était de 31 %. De plus, le débit est de 2052 Kbit.s−1 , ce qui est proche du débit de la
simulation initiale (2067 Kbit.s−1 ). Enfin, le délai moyen est de 848 ms avec un écart
type de 258 ms alors que nous avons un délai moyen de 838 ms avec un écart type de
242 ms. L’amélioration ne réside donc que dans la diminution des pertes de paquets.
Figure 4.16 – Evolution de la file d’attente du nœud 2 avec un flux 1-6 et modification
du paramètre CWmin sur le nœud source
La file d’attente du nœud 2, présentée sur la figure 4.16, semble augmenter très
progressivement, mais n’atteint pas le plafond car tous les paquets ont été émis. Aucun
Ralentissement de l’injection de flux au niveau de la source du trafic 137
Figure 4.17 – Evolution des files d’attente des nœuds 2 et 3 avec un flux 1-6 et modi-
fication du paramètre CWmin sur le nœud source
Cependant, la courbe noire de la figure 4.17 montre que la file d’attente du nœud 3
est saturée au bout de 3 secondes. Ceci arrive plus tard que lors de la simulation avec
les paramètres par défaut présenté sur la figure 4.5, mais des pertes persistent.
Figure 4.18 – Evolution des files d’attente des nœuds 2, 3 et 4 avec un flux 1-6 et
modification du paramètre CWmin sur le nœud source
Enfin, la file d’attente du nœud 4, présentée par la courbe noire de la figure 4.18,
reste à un niveau très faible indiquant qu’elle émet les paquets au rythme où elle les
reçoit.
Le tableau 4.10 confirme que moins de paquets sont perdus à cause de files d’attente
pleines malgré une saturation sur le nœud 3.
Le nombre de paquets perdus au niveau de la couche UDP est de 93 sur 1000, soit 9
%. Ces pertes sont dues en majorité à un dépassement de file d’attente au niveau d’un
138 Exploitation du simulateur
Table 4.10 – Nombre et cause des pertes sur chaque lien pour la simulation 1-6 avec
modification du paramètre CWmin sur le nœud source
nœud intermédiaire (nœud 3), mais aussi 7 paquets ont été perdus à cause de problèmes
radio. Ceci est mieux qu’avec les valeurs par défaut configurées sur les leviers (20 %),
mais moins performant que l’action sur le levier AIFS (1 %). De plus, le débit mesuré
au niveau de la couche UDP est de 1805 Kbit.s−1 , ce qui est sensiblement identique au
débit mesuré avec les valeurs par défaut, soit 1813 Kbit.s−1 .
Le délai moyen est de 1198 ms avec un écart type de 430 ms. Ceci est aussi meilleur
qu’avec les valeurs par défaut (1399 ms de moyenne et un écart type de 435 ms), et
aussi moins bon que l’action sur AIFS.
Le tableau 4.11 indique que les pertes de paquets au niveau des files d’attente n’ont
lieu qu’au niveau du nœud 2. De plus, la file d’attente du nœud 3 n’arrive pas à satu-
ration dans ces simulations.
Nous pouvons constater que les pertes de paquets au niveau UDP sont dues pour la
majorité au dépassement de capacité des files d’attente.
Ralentissement de l’injection du flux au niveau de la source et du premier relais 139
Le tableau 4.12 résume les résultats des simulations pour lesquelles les flux sont
configurés du nœud 1 au nœud 6. Il indique de même que le dernier nœud relais réémet
les paquets au rythme où il les reçoit. De plus, les pertes de paquets au niveau UDP
correspondent aux pertes dues au dépassement de file d’attente sur les autres nœuds.
Dans ce cas, le levier CWmin réduit de 11 % le taux de pertes, et le levier AIFS
élimine presque totalement les pertes au niveau de la couche UDP (seulement moins de
1 %). Grâce aux actions sur ces leviers, la qualité de service est donc améliorée car le
nombre de pertes, le délai et l’écart type (reflétant la gigue) sont plus faibles.
L’action menée sur le paramètre AIFS du premier nœud n’évite la saturation des
files d’attente que dans le cas d’un flux 1-6. En effet, l’action sur le flux 1-4 est bénéfique
mais n’est pas suffisante. Notre étude doit donc être menée sur l’intégralité du chemin,
à savoir les nœuds relais entre source et destination. Dans ce but, nous allons étudier
l’impact d’une action portant sur le nœud injecteur et sur le premier relais.
Figure 4.19 – Evolution de la file d’attente du nœud 2 avec un flux 1-4 et modification
du paramètre AIFS sur les nœud 1 et 2
La courbe de la figure 4.19 révèle que la saturation sur le nœud 2 est toujours
présente.
Figure 4.20 – Evolution des files d’attente des nœud 2 et 3 avec un flux 1-4 et modifi-
cation du paramètre AIFS sur les nœud 1 et 2
L’état de la file d’attente du nœud 3 est présenté en noir sur la courbe de la figure
4.20 et celui du nœud 2 est rappelé en gris. Le nœud 3 n’accumule que peu de paquet
dans sa file d’attente.
Les pertes de paquets au niveau des files d’attente n’ont lieu qu’au niveau du nœud
2, comme indiqué sur le tableau 4.14. Ceci est identique aux simulations précédentes
avec un flux 1-4. Cependant, la saturation n’a lieu qu’à la date 2,5 secondes (figure
4.19), alors qu’elle n’a eu lieu qu’à 2 secondes dans la simulation où seul le paramètre
Ralentissement de l’injection du flux au niveau de la source et du premier relais 141
Table 4.13 – Nombre et cause des pertes sur chaque lien pour la simulation 1-4 avec
modification du paramètre AIFS sur les nœuds 1 et 2
AIFS du nœud 1 est modifié (figure 4.9). Le nombre de paquets perdus est donc moins
important.
Le tableau 4.14 permet de comparer les simulations réalisées avec un flux allant de
1 à 4. Nous pouvons constater que le nombre de pertes a diminué, mais est toujours à 9
%. De même, le débit a augmenté à 2137 Kbit.s−1 , le délai moyen a diminué à 800 ms,
et l’écart type a diminué à 253 ms. Les performances et la qualité de service sont donc
meilleures, mais le nombre de pertes reste toujours trop important pour être acceptable.
142 Exploitation du simulateur
Figure 4.21 – Evolution de la file d’attente du nœud 2 avec un flux 1-6 et modification
du paramètre AIFS sur les nœud 1 et 2
La figure 4.21 présente l’état de la file d’attente du nœud 2. Celle-ci reste peu remplie,
et aucune perte n’est due à une saturation.
Figure 4.22 – Evolution des files d’attente des nœuds 2 et 3 avec un flux 1-6 et modi-
fication du paramètre AIFS sur les nœud 1 et 2
La courbe noire de la figure 4.22 indique que la file d’attente du nœud 3 reste aussi
très peu remplie.
Ralentissement de l’injection du flux au niveau de la source et du premier relais 143
Figure 4.23 – Evolution des files d’attente des nœuds 2, 3 et 4 avec un flux 1-6 et
modification du paramètre AIFS sur les nœud 1 et 2
Enfin, la file d’attente du nœud 4, présentée sur la courbe noire de la figure 4.23, est
toujours proche de 0. Cette simulation ne révèle aucune perte de paquet à cause d’un
remplissage de file d’attente.
Table 4.15 – Nombre et cause des pertes sur chaque lien pour la simulation 1-6 avec
modification du paramètre AIFS sur les nœuds 1 et 2
Ceci est confirmé par le tableau 4.15 où aucune perte de paquet à cause d’un buffer
plein n’est indiquée.
Cette simulation ne révèle aucune perte de paquet au niveau de la couche UDP.
En effet, toutes les pertes de paquets au niveau radio n’ont pas entraîné de perte aux
niveaux supérieurs grâce aux réémissions. De plus, le débit UDP est à 2032 Kbit.s−1 ,
ce qui est meilleur que lors des simulations précédentes avec ce type de flux. Le délai
moyen est de 630 ms, et l’écart type à 127 ms. La qualité de service est donc meilleure.
144 Exploitation du simulateur
être vidée plus rapidement que les autres nœuds. Mais nous avons constaté les mauvais
résultats si une valeur minimale est fixée à ce paramètre sur tous les nœuds.
C’est pourquoi, diminuer ce levier uniquement lorsque la file d’attente en a besoin,
peut permettre à une file d’attente de rester à un niveau peu élevé, tout en laissant les
autres nœuds faire de même quand leurs files d’attente sont dans le même état.
Ceci correspond à un système avec en entrée l’état de la file d’attente, et en sortie
la commande à appliquer sur le paramètre AIFS. Ainsi le système bouclé peut observer
l’efficacité de sa commande et réguler l’état de la file d’attente vers une valeur faible,
mais pas nulle, de manière à laisser le paramètre AIFS augmenter pour laisser la parole
aux autres nœuds.
Ce mécanisme peut être appelé régulation de trafic.
˙ i (n) = 0
Bd (4.3)
Rmin,i si Ri (n) < Rmin,i
Ri (n) = Rmax,i si Ri (n) > Rmax,i (4.4)
Ri (n) si Rmin,i ≤ Ri (n) ≤ Rmax,i
Une fois ce mécanisme implanté dans le simulateur, nous pouvons observer son effet
avec ces valeurs initiales de paramètres.
Le nœud 1, injectant des paquets, a sa file d’attente pleine. Ce mécanisme n’est donc
pas activé sur ce nœud et la valeur de AIFS est fixée à 5 dans un premier temps.
Dans cette simulation, les valeurs suivantes sont configurées pour tous les nœuds à
l’exception du nœud 1 :
– α = 0,05
– β = 0,001
– R(0) = 4
– Bd = 20
– T e = 50 ms
– Rmin = 2
– Rmax = 7
Le paramètre AIFS du nœud 1 est fixé à 5.
Figure 4.25 – Evolution de la file d’attente du nœud 2 avec un flux 1-4 et régulateur
de trafic
La figure 4.25 présente l’état de la file d’attente du nœud 2. Nous pouvons constater
que la courbe n’arrive pas à saturation, mais oscille autour de la valeur désirée Bd (20).
L’état de la file d’attente du nœud 3 est décrit sur la courbe noire de la figure 4.26.
Celle-ci n’arrive pas non plus à saturation et tend aussi à osciller autour de la valeur
20, comme la courbe grise rappelant l’état de la file d’attente du nœud 2.
148 Exploitation du simulateur
Figure 4.26 – Evolution des files d’attente des nœud 2 et 3 avec un flux 1-4 et régulateur
de trafic
Le tableau 4.17 indique qu’aucun nœud n’a perdu de paquets à cause d’une satura-
tion de la file d’attente conformément aux courbes précédentes.
Table 4.17 – Nombre et cause des pertes sur chaque lien pour la simulation 1-4 avec
régulateur de trafic
Le débit est de 2156 Kbit.s−1 , ce qui correspond aux simulations précédentes. Ce-
pendant, aucune perte de paquet n’est due au buffer plein, et seulement 0,3 % des
paquets ont été perdus au niveau UDP (contre 9 % dans la meilleure des simulations
précédentes). Le délai moyen est de 775 ms avec un écart type de 169 ms. Ce reflet de
la qualité de service est aussi amélioré.
Ce mécanisme supprime les pertes de paquets au niveau d’un dépassement de ca-
pacité des files d’attente dans le cas d’un flux allant du nœud 1 au nœud 4, tout en
améliorant la qualité de service. Nous pouvons maintenant jouer sur les nouveaux leviers
contrôlant ce système afin de choisir les meilleures valeurs.
Le tableau 4.18 récapitule les différentes étapes permettant d’affiner les valeurs de
ces paramètres. La simulation nommée S1 correspond à la simulation précédente.
Les simulations S2 et S3 jouent sur la valeur AIFS du nœud 1. Nous retenons
la valeur 4 utilisée dans la simulation S2 car les performances sont très sensiblement
Régulation du trafic par l’utilisation du levier AIFS 149
supérieures au niveau du débit et de l’écart type. Une valeur trop faible présentée par
la simulation S3 introduit à nouveau des pertes dues aux files d’attente pleines.
Le nombre de paquets présent dans le buffer désiré (Bd) est affinée par les simulations
S4 et S5. La valeur 5 est conservée car elle permet d’améliorer le délai et l’écart type.
Le gain α est réglé à partir des simulations S6 et S7. Nous retenons la valeur 0,04 qui
améliore le débit, le délai et l’écart type. La valeur plus faible utilisée dans la simulation
S6 a un effet négatif sur la qualité de service.
Table 4.18 – Résultats de simulations avec flux 1-4 permettant d’optimiser le régulateur
de trafic
Figure 4.27 – Evolution de la file d’attente du nœud 2 avec un flux 1-4 et régulateur
de trafic optimisé
– α : 0,04
– β : 0,001
– R(0) : 4
– Bd : 5
– T e : 50 ms
– Rmin = 2
– Rmax = 7
La figure 4.27 représente l’état de la file d’attente du nœud 2. Celui-ci est régulé et
reste à un niveau faible.
Figure 4.28 – Evolution des files d’attente des nœud 2 et 3 avec un flux 1-4 et régulateur
de trafic optimisé
Table 4.19 – Nombre et cause des pertes sur chaque lien pour la simulation 1-4 avec
régulateur de trafic optimisé
Régulation du trafic par l’utilisation du levier AIFS 151
Table 4.20 – Récapitulatif des simulations 1-4 sans puis avec régulateur de trafic opti-
misé
Ceci est confirmé par le tableau 4.19 qui indique qu’aucune perte n’a lieu à cause
d’un dépassement de capacité des files d’attente.
Le tableau 4.20 rappelle les valeurs obtenues sans et avec ce mécanisme de régulation,
et montre le gain de qualité de service apporté.
Il est important de vérifier que ce mécanisme n’affecte pas les performances obtenues
précédemment avec un flux allant du nœud 1 au nœud 6. C’est pourquoi nous allons
utiliser les paramètres du système déterminés à partir d’un flux 1-4 sur une nouvelle
simulation utilisant un flux 1-6.
Figure 4.29 – Evolution de la file d’attente du nœud 2 avec un flux 1-6 avec régulateur
de trafic optimisé
Figure 4.30 – Evolution des files d’attente des nœuds 2 et 3 avec un flux 1-6 avec
régulateur de trafic optimisé
L’état de la file d’attente du nœud 3 est présenté par la courbe noire de la figure
4.30. De même que dans le nœud 2 rappelé en gris, cette courbe reste à des valeurs
faibles.
Figure 4.31 – Evolution des files d’attente des nœuds 2, 3 et 4 avec un flux 1-6 avec
régulateur de trafic optimisé
Enfin, la courbe noire de la figure 4.31 présente l’état de la file d’attente du nœud
4. Tout comme les autres simulations impliquant le nœud 6, cette file d’attente reste
presque vide.
Régulation du trafic par l’utilisation du levier AIFS 153
Table 4.21 – Nombre et cause des pertes sur chaque lien pour la simulation 1-6 avec
régulateur de trafic optimisé
Le tableau 4.21 présente le bilan des pertes lors de simulation et ne fait apparaître
aucune perte due à une file d’attente pleine.
Lors de cette simulation, le débit est de 1979 Kbit.s−1 et le délai moyen de 656 ms
avec un écart type de 124 ms.
Table 4.22 – Récapitulatif des simulations 1-6 sans puis avec régulateur de trafic
Le tableau 4.22 rappelle les résultats obtenus sans et avec régulateur. Ceux-ci sont
bien meilleurs que sans action sur ces nœuds, mais très sensiblement inférieur à une
action sur le nœud injecteur et sur le premier relais. Cependant, la qualité de service
apportée est tout à fait suffisante pour du transport de voix sur ip ou de vidéo.
cesseur dépend de la direction du flux. En effet, dans nos premières simulations, nous
n’avons pris en compte qu’un seul flux. Pour généraliser en considérant plusieurs flux
de classes différentes, il est important de compter les paquets dans une file d’attente en
fonction du nœud vers lequel ils doivent être émis, et de la classe de qualité de service
associée.
Ceci nécessite la création de nouveaux paquets de contrôle, permettant à chaque
nœud d’informer ses voisins de l’état de sa file d’attente, et de propager l’état des files
d’attente de ses voisins. La fréquence de transmission de ces nouveaux paquets doit être
peu élevée pour que ces paquets n’altèrent pas les performances du réseau. De plus, ce
paquet doit être priorisé par rapport à la file d’attente, car s’il est injecté en queue,
l’information qu’il contient peut être obsolète.
La transmission du nombre de paquets dans la file d’attente peut être périodique et
donc systématique quel que soit l’état de la pile comme nous l’avons testé. Dans ce cas,
cette information peut être incluse dans un nouveau champ d’un paquet de contrôle
Beacon. En effet, la norme 802.11 permet d’ajouter des informations supplémentaires
dans ce paquet mais aussi d’en modifier la fréquence de transmission. Cette transmission
peut aussi être évènementielle et ne se déclencher que lors du franchissement de certains
seuils sur l’état de la file d’attente. Plusieurs seuils modifiant l’action du régulateur sont
envisageables. Ainsi, ceci peut nous amener à une régulation floue.
Tout ceci pourra être simulé dans une étude ultérieure grâce à ce simulateur dans
le but de qualifier la qualité de service apportée par ce mécanisme.
4.6 Conclusion
Ce chapitre a décrit les premières exploitations de ce simulateur sur une topologie
de référence représentant un cas réel. Ces simulations sont axées sur le remplissage et la
saturation des files d’attente sur les nœuds relayant les paquets lorsqu’un nœud source
doit transmettre un grand nombre de paquets. Sur certains relais, la file d’attente se
remplit car le nombre de paquets reçus est plus important que le nombre de paquets
émis. Ainsi la file d’attente peut arriver à saturation et les nouveaux paquets arrivant
sont perdus. D’une part, les pertes de paquets affectent énormément la qualité de service,
mais de plus, le délai de transmission varie et augmente si un paquet attend au niveau
d’un nœud. Ainsi, une communication audio ou vidéo traversant ce réseau WiFi maillé
est de mauvaise qualité.
Ceci est le premier problème nuisant à la qualité de service, observé lors des simu-
lations. En effet, la maîtrise et l’évolutivité de l’outil de simulation permettent d’ap-
profondir un problème en analysant des compteurs et des évènements, dans ce cas le
niveau de remplissage des files d’attente. Des pistes d’actions ont d’abord été trouvées
à partir de l’identification des leviers CWmin et AIFS ainsi que la qualification de leurs
influences. Nous avons ensuite agi sur le paramètre le plus performant, AIFS, de ma-
nière statique sur le nœud source, puis sur les deux premiers nœuds, et observé quelques
améliorations.
Une solution plus performante a été finalement apportée à ce problème à partir
d’une étude du domaine de l’automatique. Une loi de commande, de type Proportionnel
Dérivé, a été implémentée dans le modèle. Celle-ci contrôle dynamiquement le levier
Conclusion 155
AIFS à partir du niveau de remplissage des files d’attente Bm, agissant localement sur
chaque nœud. Elle a permis d’apporter de fortes améliorations en terme de qualité de
service.
Une évolution de cette loi de commande pourrait intégrer l’état des files d’attente des
voisins, voire de l’ensemble des éléments du réseau. De nouveaux moyens de transmettre
ces informations seraient à mettre en place entre chaque nœud.
Ce problème a été résolu sur cette topologie donnée, avec un flux unidirectionnel,
mais il serait nécessaire d’analyser l’impact de ce mécanisme sur des topologies plus
importantes et plus compliquées, avec des flux différents. De plus, ce mécanisme devra
être implémenté sur le matériel pour apprécier les améliorations sur le terrain.
De nombreux axes de recherche sont ouverts maintenant que nous avons créé ce
simulateur. Une exploitation plus approfondie est nécessaire, et pourrait faire apparaître
d’autres situations où la qualité de service est à améliorer.
156 Exploitation du simulateur
Conclusion
Les communications audio et vidéo sont de plus en plus fréquentes au travers d’In-
ternet et elles nécessitent une forte qualité de service, permettant une qualité sonore
et une image correcte. Le développement de ce nouveau moyen de transport qui est le
WiFi maillé permet d’apporter de l’accès Internet dans de grandes surfaces telles que les
campings et résidences de vacances. Cependant, la répétition de paquets, sur un même
canal radio par chacun des nœuds présents sur le chemin utilisé, altère la qualité de
service des communications transportées. Ceci a été observé lors d’expérimentations.
Un état de l’art a présenté les problèmes et les solutions proposées dans la littéra-
ture. Ceux-ci ont révélé des problèmes de partage du canal radio ainsi que le problème
du nœud caché. Ils entraînent une baisse du débit utile et de la qualité de service des
communications. Malheureusement, les solutions proposées ne peuvent pas être implé-
mentées sur notre architecture car elles nécessitent des modifications du protocole WiFi
alors qu’une contrainte que nous avons est de rester compatible avec le matériel des
clients.
L’étude expérimentale ne permet pas d’observer de manière microscopique les pro-
blèmes de transports altérant la qualité de service. En effet, afin de tout observer, il
faudrait avoir connaissance de ce que chaque nœud émet et reçoit de manière synchro-
nisée temporellement, tout en maîtrisant l’environnent radio. Ceci étant difficilement
réalisable, nous nous sommes orientés vers une étude par simulation.
Ce mémoire de thèse présente un simulateur, créé dans le but de comprendre et d’agir
sur les problèmes liés à cette méthode de transport. Celui-ci est basé sur les réseaux
de Petri colorés temporisés stochastiques et hiérarchisés, formalisme de modélisation
permettant une forte évolutivité et un raffinement successif du modèle en fonction des
problèmes à étudier. Il permet de simuler différents flux réseaux au travers d’un réseau
WiFi maillé dont la topologie est configurable. Cette modélisation a été validée à partir
de la description et des mesures de liens effectués sur un cas réel.
Une première exploitation du simulateur sur cette topologie de référence a permis
d’observer un remplissage des files d’attente d’émission de certains nœuds présents sur le
chemin de communication. Ainsi la saturation de celles-ci entraîne des pertes de paquets,
et la gigue mesurée sur un tel réseau est détériorée. Ces deux impacts provoquent une
mauvaise qualité de service. Après avoir identifié les leviers permettant de contrôler
le remplissage de ces files d’attente, nous avons pu jouer sur ceux-ci et observer une
amélioration. Enfin, nous avons mis en place une loi de commande du domaine de
l’automatique permettant de jouer automatiquement et dynamiquement sur ces leviers
en fonction du remplissage des files d’attente. Cette loi, implémentée dans le modèle,
157
158 Conclusion
Perspectives
Une première perspective serait d’implémenter cette amélioration sur le matériel
que nous utilisons. Nous pourrons alors mesurer son impact de manière quantitative
directement sur le terrain, mais aussi tester des communications audio et vidéo et de
fait apprécier l’amélioration apportée.
Cet outil pourrait être utilisé pour déterminer le meilleur déploiement des nœuds sur
le terrain. Lors de notre étude, nous avons pris une installation existante pour l’étudier.
A l’inverse, le choix entre les différentes possibilités de positionnement des nœuds sur
une nouvelle installation pourrait être fait après simulation. Ainsi, la qualité du réseau
pourrait être optimisée, et connue à l’avance.
Ensuite, cette amélioration devra être testée sur d’autres exemples d’implantation de
nœuds sur le terrain, afin d’observer l’impact qu’elle aura. Cette recherche s’étant limitée
à une topologie donnée, les améliorations pourraient être plus ou moins importantes.
Une autre perspective serait la mise en place d’un mécanisme de régulation global
collaboratif entre chaque nœud. En effet, chacun d’eux pourrait transmettre à ses voisins
l’état de sa file d’attente, ils pourraient alors anticiper les paquets qui leur arriveraient
ainsi que l’impact que leurs émissions auraient sur les autres nœuds. En fonction de
ces facteurs, les nœuds pourraient automatiquement et dynamiquement adapter leurs
leviers dans le but de limiter l’impact négatif sur la qualité de service. La transmission
de ces informations peut être périodique à une fréquence à déterminer. Si celle-ci est
trop élevée, le canal radio est beaucoup utilisé avec ces paquets de contrôle. Si elle est
trop faible, la réaction sera lente. La transmission périodique de ces informations peut
être transportée dans les Beacons. Cette communication peut aussi être évènementielle.
Ainsi, l’état de la file d’attente sera connu des voisins si un seuil est dépassé. Plusieurs
seuils peuvent aussi être déterminés et associés à différents niveaux d’action sur le levier
AIFS. L’utilisation de notre simulateur pourra permettre d’évaluer les améliorations de
qualité de service avec ces mécanismes.
De plus, maintenant qu’un outil est créé, de nouvelles simulations pourraient être
faites sur d’autres topologies, avec des flux différents avec pour objectif de trouver
d’autres causes d’altération de la qualité de service. Ceci permettrait à terme d’avoir un
ensemble de lois de commande et d’adaptations des leviers qui garantiraient de bonnes
performances quelle que soit la topologie du terrain sur lequel serait installé un réseau
de WiFi maillé.
Enfin, de nouveaux modèles pourront être implémentés dans cet outil évolutif. Par
exemple, la couche TCP permettrait d’évaluer les conséquences de pertes de paquets au
niveau liaison de donnée, ce qui entraînerait des réémissions au niveau TCP. L’utilisation
Conclusion 159
161
162 Bibliographie
[IEE99c] IEEE. 802.11b higher-speed physical layer extension in the 2.4 ghz band.
IEEE Computer Society LAN MAN Standards Committee. 802.11, 1999.
[IEE03] IEEE. 802.11g further higher data rate extension in the 2.4 ghz band.
IEEE Computer Society LAN MAN Standards Committee. 802.11, 2003.
[IEE05] IEEE. 802.11e medium access control (mac) quality of service enhan-
cements. IEEE Computer Society LAN MAN Standards Committee.
802.11, 2005.
[IEE09] IEEE. 802.11n enhancements for higher throughput. IEEE Computer
Society LAN MAN Standards Committee. 802.11, 2009.
[IEE11] IEEE. 802.11s wireless lan (wlan) mesh basic service set. IEEE Com-
puter Society LAN MAN Standards Committee. 802.11, 2011.
[JAB08] Issam JABRI. Gestion dynamique des topologies sans fils. PhD thesis,
Université Henri Poincaré, Nancy I, 2008.
[JR05] Zhu Jing and S. Roy. 802.11 mesh networks with two-radio access points.
Communications ICC IEEE International Conference on, 5 :3609–3615,
Mai 2005.
[JYM07] Zhang Jian, Chen Yuanzhu, and I. Marsic. Persistent pseudo-clearance
problem in ieee802.11 mesh networks and its multicast based solu-
tions. Local and Metropolitan Area Networks LANMAN 2007. 15th IEEE
Workshop on, pages 1–6, Juin 2007.
[KJCV06] P. Kyasanur, So Jungmin, C. Chereddi, and N.H. Vaidya. Multichannel
mesh networks : challenges and protocols. Wireless Communications
IEEE, 13 :30–36, Avril 2006.
[KRR+ 09] A. Kandhalu, A. Rowe, R. Rajkumar, Chingchun Huang, and Chao-
Chun Yeh. Real-time video surveillance over ieee 802.11 mesh networks.
Real-Time and Embedded Technology and Applications Symposium 15th
IEEE, Avril 2009.
[LKC05] X. Li, P.-Y. Kong, and K.-C. Chua. Analysis of tcp throughput in ieee
802.11 based multi-hop ad hoc networks. Computer Communications
and Networks ICCCN 2005 Proceedings. 14th International Conference
on, pages 297–302, Oct 2005.
[LPSY09] A. Lyakhov, I. Pustogarov, A. Safonov, and M. Yakimov. Starvation
effect study in ieee 802.11 mesh networks. Mobile Adhoc and Sensor
Systems MASS ’09. IEEE 6th International Conference on, pages 651–
656, Oct 2009.
[MPV06] R. Moraes, P. Portugal, and F. Vasques. A stochastic petri net model for
the simulation analysis of the ieee 802.11e edca communication protocol.
Emerging Technologies and Factory Automation, pages 38–45, Sept 2006.
[MSK+ 10] S. Mehta, N. Sulatan, H. Kabir, N. Ullah, and Kwak K. S. Network and
system simulation tools for next generation networks : A case study.
Modelling, Simulation and Identification, Aout 2010.
Bibliographie 163
165
166 Table des figures
4.1 Nombre et cause des pertes sur chaque lien pour la simulation 1-4 . . . . 125
4.2 Nombre et cause des pertes sur chaque lien pour la simulation 1-6 . . . . 127
4.3 Gain de période de contention de 3 nœuds avec la même configuration . 129
4.4 Gain de période de contention de 5 nœuds avec la même configuration . 130
4.5 Gain de période de contention de 3 nœuds avec modification de AIFS . 130
4.6 Gain de période de contention de 3 nœuds avec modificationd de CWmin 130
4.7 Nombre et cause des pertes sur chaque lien pour la simulation avec un
flux 1-4 et modification du paramètre AIFS sur le nœud source . . . . . 132
4.8 Nombre et cause des pertes sur chaque lien pour la simulation avec un
flux 1-6 et modification du paramètre AIFS sur le nœud source . . . . . 134
4.9 Nombre et cause des pertes sur chaque lien pour la simulation 1-4 avec
modification du paramètre CWmin sur le nœud source . . . . . . . . . . 136
4.10 Nombre et cause des pertes sur chaque lien pour la simulation 1-6 avec
modification du paramètre CWmin sur le nœud source . . . . . . . . . . 138
4.11 Récapitulatif des simulations 1-4 . . . . . . . . . . . . . . . . . . . . . . 138
4.12 Récapitulatif des simulations 1-6 . . . . . . . . . . . . . . . . . . . . . . 139
4.13 Nombre et cause des pertes sur chaque lien pour la simulation 1-4 avec
modification du paramètre AIFS sur les nœuds 1 et 2 . . . . . . . . . . 141
4.14 Récapitulatif des simulations 1-4 en incluant la simulation modifiant le
premier relais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
169
170 Liste des tableaux
4.15 Nombre et cause des pertes sur chaque lien pour la simulation 1-6 avec
modification du paramètre AIFS sur les nœuds 1 et 2 . . . . . . . . . . 143
4.16 Récapitulatif des simulations 1-6 en incluant la simulation modifiant le
premier relais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.17 Nombre et cause des pertes sur chaque lien pour la simulation 1-4 avec
régulateur de trafic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
4.18 Résultats de simulations avec flux 1-4 permettant d’optimiser le régula-
teur de trafic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.19 Nombre et cause des pertes sur chaque lien pour la simulation 1-4 avec
régulateur de trafic optimisé . . . . . . . . . . . . . . . . . . . . . . . . . 150
4.20 Récapitulatif des simulations 1-4 sans puis avec régulateur de trafic optimisé151
4.21 Nombre et cause des pertes sur chaque lien pour la simulation 1-6 avec
régulateur de trafic optimisé . . . . . . . . . . . . . . . . . . . . . . . . . 153
4.22 Récapitulatif des simulations 1-6 sans puis avec régulateur de trafic . . . 153
Glossaire
ACK Acknowledge, Trame qui indique que la trame précédente est reçue
correctement
ADSL Asymmetric Digital Subscriber Line, Téchnologie de communication
utilisant la ligne téléphonique
AIFS Arbitration IFS, Temps intertrame présenté dans la norme de qualité
de service IEEE 802.11e
AIS Asymmetric Incomplete State, Catégorie d’interaction entre nœud
proposé par [RAGK08]
AODV Ad Hoc On-Demand Vector, Protocole de routage adapté au réseaux
mobiles
AP Access Point, Point d’accès dans un réseau IEEE 802.11 de type
infrastructure
BE Best Effort, Classe de qualité de service proposée dans la norme
IEEE 802.11e meilleure que BG
BK Background, Classe de qualité de service proposée dans la norme
IEEE 802.11e de plus faible priorité
BSS Basic Service Set, Ensemble de stations associées aux points d’accès
d’un même réseau
BSSID Basic Service Set Identifier, Identifiant d’un BSS
CMT Clustered Multi-channel Two-radio, Approche multicanal proposée
par [JR05]
CSMA/CA Carrier Sense Multiple Access with Collision Avoidance, Méthode
d’accès basée sur l’accusé de réception
CSMA/CD Carrier Sense Multiple Access with Collision Detection, Méthode
d’accès basée sur la détection de collision
CTS Clear To Send, Paquet de contrôle permettant de réserver le médium
pendant un temps donné
CW Contention Window, Période de contention tiré aléatoirement dans
une fenêtre donnée
DCF Distributed Coordination Function, Méthode de transmission où un
nœud attend que le médium soit libre pour parler
DIFS DCF IFS, Temps intertrame lors de transmission DCF
DS Distribution System, Système de distribution sans fil permettant
d’interconnecter un BSS
171
172 Glossaire