Thèses de l'INSA de Lyon | Les Thèses de l'INSA de …theses.insa-lyon.fr/publication/2007ISAL0046/these.pdfrecherches sur les r´eseaux ad hoc ont suscit´e un tel engouement qu’un

N d’ordreAnnee 2007

These

De l’apport d’une evaluation precisedes ressources pour la Qualite de Servicedes reseaux ad hoc bases sur IEEE 802.11

Presentee devantL’Institut National des Sciences Appliquees de Lyon

pour obtenirLe grade de docteur

ParCheikh SARR

A soutenir le 17 Juillet 2007 devant la Commission d’examen

Composition du Jury

K. Al Agha - Professeur (Universite Paris-Sud)- RapporteurC. Chaudet - Maıtre de conference (ENST Paris)G. Chelius - Charge de recherche (INRIA) - Co-Directeur de theseB. Ducourthial - Maıtre de conference (UTC)E. Fleury - Professeur (INSA Lyon)I. Guerin Lasous - Professeur (UCBL/LIP) - Co-Directrice de theseT. Noel - Professeur (Universite Louis Pasteur)- Rapporteur

Table des matieres

1 Presentation de 802.11 91.1 Le protocole IEEE 802.11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.1.1 Fonctionnement general . . . . . . . . . . . . . . . . . . . . . . . . . 101.1.2 Description du protocole d’acces au medium . . . . . . . . . . . . . . 11

1.1.2.1 Mecanisme d’acces CSMA/CA . . . . . . . . . . . . . . . . 131.1.2.2 Retransmissions et backoff exponentiel . . . . . . . . . . . . 141.1.2.3 Mecanisme du RTS/CTS . . . . . . . . . . . . . . . . . . . 141.1.2.4 Zones de communication . . . . . . . . . . . . . . . . . . . . 15

1.2 Synthese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2 Routage ad hoc et qualite de service 182.1 Generalites sur les reseaux ad hoc . . . . . . . . . . . . . . . . . . . . . . . . 182.2 Le routage dans les reseaux ad hoc . . . . . . . . . . . . . . . . . . . . . . . 192.3 La qualite de service dans les reseaux ad hoc . . . . . . . . . . . . . . . . . . 22

3 Etat de l’art sur les techniques d’evaluation de la bande passante residuelle 253.1 La bande passante residuelle ou disponible . . . . . . . . . . . . . . . . . . . 253.2 Evaluation de la bande passante residuelle dans les reseaux filaires . . . . . . 263.3 Evaluation de la bande passante residuelle dans les reseaux sans fil . . . . . . 28

3.3.1 Les techniques intrusives . . . . . . . . . . . . . . . . . . . . . . . . . 283.3.2 Les techniques passives . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.4 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4 Une technique d’evaluation de la bande passante residuelle : ABE 344.1 Une estimation precise de la bande passante residuelle . . . . . . . . . . . . . 34

4.1.1 Estimation de la bande passante residuelle d’un nœud . . . . . . . . 354.1.2 Estimation de la bande passante residuelle d’un lien : une premiere

approche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.1.2.1 Prise en compte de la synchronisation des periodes d’inactivite 364.1.2.2 Prise en compte des collisions . . . . . . . . . . . . . . . . . 414.1.2.3 Prise en compte du backoff . . . . . . . . . . . . . . . . . . 454.1.2.4 Formule d’evaluation de la bande passante residuelle . . . . 474.1.2.5 Comparaison avec QOLSR . . . . . . . . . . . . . . . . . . . 48

2

4.1.3 Estimation de la bande passante residuelle d’un lien : complements . 494.2 Version protocolaire d’ABE . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.3 Controle d’admission dans ABE . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3.1 Decouverte de route . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.3.2 Maintenance de route . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.3.3 Contention intra flux . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.4 Limitations du protocole ABE . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5 Evaluation des performances d’ABE 575.1 Environnement de travail : le simulateur NS-2 . . . . . . . . . . . . . . . . . 575.2 Resultats de simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.2.1 Un premier scenario simple . . . . . . . . . . . . . . . . . . . . . . . 585.2.2 Topologies aleatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . 605.2.3 Evaluation du cout du mecanisme . . . . . . . . . . . . . . . . . . . . 695.2.4 Precision de l’evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 70

5.3 Synthese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6 Co-existence de trafics privilegies et Best Effort 746.1 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

6.1.1 Approches existantes . . . . . . . . . . . . . . . . . . . . . . . . . . . 756.1.2 Synthese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

6.2 Presentation du protocole DRBT . . . . . . . . . . . . . . . . . . . . . . . . 786.2.1 Idees utilisees dans DRBT . . . . . . . . . . . . . . . . . . . . . . . . 786.2.2 Estimation de la bande passante residuelle . . . . . . . . . . . . . . . 806.2.3 Regulation du debit des flux Best Effort . . . . . . . . . . . . . . . . 80

6.2.3.1 Reduction du debit des flux Best Effort . . . . . . . . . . . 816.2.3.2 Augmentation du debit des flux Best Effort . . . . . . . . . 84

6.2.4 Synthese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 856.3 Evaluation des performances de DRBT . . . . . . . . . . . . . . . . . . . . . 85

6.3.1 Un premier scenario simple : les 2 paires . . . . . . . . . . . . . . . . 856.3.2 Topologies aleatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . 866.3.3 Taux d’acceptation des flux QoS . . . . . . . . . . . . . . . . . . . . . 89

7 Estimation du delai moyen 927.1 Etat de l’art sur les techniques d’evaluation du delai . . . . . . . . . . . . . . 927.2 Synthese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 947.3 Estimation du delai moyen dans les reseaux ad hoc . . . . . . . . . . . . . . 95

7.3.1 Hypotheses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 957.3.2 Delai dans la file d’attente des nœuds . . . . . . . . . . . . . . . . . . 967.3.3 Delai sur le medium radio . . . . . . . . . . . . . . . . . . . . . . . . 98

7.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997.5 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

7.5.1 Precision de l’estimation du delai de bout-en-bout . . . . . . . . . . . 102

7.5.1.1 Stations cachees . . . . . . . . . . . . . . . . . . . . . . . . 1027.5.1.2 Chaıne de transmission . . . . . . . . . . . . . . . . . . . . . 103

7.5.2 Topologies aleatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . 1047.5.3 Taux d’acceptation des paquets QoS . . . . . . . . . . . . . . . . . . 104

7.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

4

Introduction generale

Sujet de These

L’essor des technologies sans fil offre aujourd’hui de nouvelles perspectives dans le do-maine des telecommunications. L’evolution recente des moyens de communication sans filpermet la manipulation de l’information par des unites de calculs portables accedant aureseau via une interface de communication sans fil. Ces environnements mobiles offrent unegrande flexibilite d’emploi, en particulier ils permettent la mise en reseau de sites pour les-quels le cablage serait trop onereux ou complexe a deployer, voire meme impossible.

On peut distinguer plusieurs types de reseaux sans fil parmi lesquels les reseaux cellulairesdestines a la telephonie mobile tel que le GSM [1] et l’IS95 [2] dits de deuxieme generation quifirent leur apparition dans les annees 90. Au debut des annees 2000, cet essor des reseaux sansfil s’est poursuivi avec l’apparition des reseaux locaux sans fil ainsi que l’arrivee de nouvellestechnologies. Les equipements sans fil se dotent alors d’interface radio pouvant communiquersur des distances de l’ordre de quelques metres (Bluetooth [3]), ou sur des distances pouvantaller de quelques dizaines a quelques centaines de metres (IEEE 802.11 [4]), offrant une cou-verture radio plus consequente. Les debits de ces nouvelle technologies peuvent desormaisatteindre des dizaines de megabits par seconde, favorisant l’emergence d’applications mul-timedia dans ces reseaux.

Dans un reseau local sans fil base sur la norme IEEE 802.11, on distingue principalementdeux modes de communication. Dans le premier cas, les transmissions de donnees passent parun point fixe appele point d’acces et ce meme si deux mobiles communicants sont a portee decommunication. Cette entite particuliere joue le role de pont a l’interieur du reseau sans filet souvent de passerelle vers un reseau filaire externe. Chaque point d’acces administre unezone geographique et assure eventuellement la liaison vers d’autres reseaux. Dans le secondmode de communication, chaque mobile ou nœud du reseau a la possibilite de communiquerdirectement avec ses voisins sans intermediaire. Un nœud peut se connecter, se deplacer ouse deconnecter du reseau a tout moment. Il n’y a donc aucune infrastructure fixe a prioriet les mobiles n’ont aucune connaissance de leur environnement. Si chaque nœud d’un telreseau a la possibilite de router des paquets emis par d’autres nœuds, il devient possible decommuniquer au-dela de sa distance d’emission. On parle alors de reseau ad hoc.

Le caractere fortement dynamique des reseaux ad hoc necessite l’implementation de pro-tocoles de routage plus complexes que ceux des reseaux fixes ou avec point d’acces. Les

5

recherches sur les reseaux ad hoc ont suscite un tel engouement qu’un groupe de travail al’IETF1, le groupe MANET [5] (Mobile Ad hoc NETworks), a ete cree en 1996 afin destandardiser des protocoles de routage.

Dans les reseaux filaires, un bon nombre de protocoles actuellement utilises fonctionnentcorrectement et les debits obtenus sur ces reseaux permettent de realiser des operationscomplexes sous reserve du respect de certaines contraintes. En effet, une application dediffusion video par exemple necessite l’assurance d’obtenir et de conserver tout au long dela transmission une bande passante minimale tandis qu’une application audio a besoin degaranties sur le delai de transmission et la gigue.

Pour les reseaux ad hoc, certains travaux ont recemment ete menes dans le butd’optimiser le processus de routage en instaurant une certaine Qualite de Service. Lesprotocoles proposes dans ce cas prennent principalement en compte les problemes lies a lafiabilite de la transmission ou a la dynamicite de l’environnement, occultant tres souventune evaluation precise des ressources restantes a travers le reseau. Le medium radio parexemple est soumis a des contraintes. En particulier, un signal radio doit, pour etre decode,etre percu avec suffisamment de puissance au niveau du recepteur. Il faut d’autre part qu’ilne soit pas brouille par d’autres transmissions simultanees. Ceci se traduit par un seuildu rapport signal sur bruit en-deca duquel il n’est pas possible de decoder un paquet defacon fiable. L’effet de plusieurs signaux parasites s’ajoutant, une transmission de donneespeut contribuer a en gener une autre bien au-dela de la portee d’un simple emetteur. Cephenomene de brouillage pose un probleme lorsqu’il s’agit d’offrir des garanties a un flux dedonnees. En effet, le debit d’emission d’un nœud, et donc sa capacite a router les paquetsdans le cas d’un reseau ad hoc, est directement fonction de son environnement et varie aucours du temps. Compte tenu de cette contrainte, il est difficile d’assurer une garantie debande passante ou de delai sans connaıtre precisement le volume de donnees que les nœudsauront a transmettre. Des lors, il semble indispensable de pouvoir estimer correctementles ressources disponibles dans son environnement radio avant d’accepter une requete dequalite de service, sous peine de ne pouvoir assurer le service promis.

La plupart des protocoles de qualite de service proposes pour les reseaux ad hoc supposentque cette quantite de ressources disponibles est connue ou facile a estimer. Or, les contraintesprecitees complexifient cette estimation. Cette these etudie les mecanismes necessaires pourevaluer la quantite de ressources disponibles dans un reseau ad hoc et faciliter ainsi le supportde la qualite de service pour ces reseaux. Il s’agit plus precisement d’offrir aux applications desgaranties sur la qualite des flux en tenant compte des contraintes liees a la nature des reseauxad hoc (ressources limitees, interferences radio, medium partage, etc.). Ces garanties passentau prealable par une estimation precise des ressources residuelles (bande passante residuelle,delai moyen), longtemps negligee ou supposee connue par bon nombre de publications. Nousnous interessons principalement a deux metriques qui nous semblent primordiales : la bandepassante disponible et le delai moyen de bout-en-bout.

1Internet Engineering Task Force

6

Organisation du document et contributions

L’objectif de cette these est de proposer des mecanismes permettant d’evaluer les res-sources disponibles dans un reseau ad hoc multi-saut.

Le premier chapitre presente brievement les mecanismes de fonctionnement du protocolede niveau MAC que nous avons considere : la norme IEEE 802.11. Cette norme s’est imposeecomme la technologie sans fil de facto pour les reseaux locaux sans fil. Notre approche se basedonc sur celle-ci. De plus, il nous semble difficile de proposer une estimation des ressourcesindependante du protocole sans fil sous-jacent. Par consequent, pour mettre au point unprotocole d’evaluation des ressources precis, il est necessaire de bien connaıtre la technologiesans fil sur laquelle le protocole propose va se reposer. L’etude de cette norme dans cechapitre va permettre la mise en place de protocoles de qualite de service fortement adaptesa la methode d’acces au medium.

Le deuxieme chapitre presente les reseaux ad hoc ainsi que les principaux problemesgeneralement rencontres dans ce type de reseau. Nous discutons egalement des differentesclassifications des solutions de qualite de service jusqu’alors rencontrees dans la litterature.Nous expliquons pourquoi nous nous concentrons sur le routage avec qualite de service.

Le troisieme chapitre presente un etat de l’art sur les differentes techniques d’evaluationde la bande passante disponible utilises dans les protocoles de qualite de service pour lesreseaux ad hoc. Nous finissons ce chapitre en expliquant pourquoi il est encore necessaire detravailler sur ce sujet.

Le quatrieme chapitre presente ABE (Available Bandwidth Estimation), un protocole dereservation de bande passante pour les reseaux ad hoc. La principale contribution d’ABEest de proposer des mecanismes qui permettent d’estimer de facon fiable la bande passanteresiduelle de l’ensemble des liens radio d’un reseau ad hoc. Ces mecanismes concernent laprise en compte de la synchronisation necessaire des periodes de silence d’un emetteur et d’unrecepteur a portee radio sur un lien, l’amelioration de l’estimation des collisions dans le reseauet une meilleure integration du scenario des stations cachees dans l’evaluation. Tous cesmecanismes participent a la consommation de la bande passante et il est important de bien lesquantifier lors de l’estimation. Ainsi, a chaque instant, la bande passante residuelle de tous lesliens radio du reseau est connue. Cette connaissance facilite la phase de controle d’admissiondes flux. Le processus de routage, utilise dans ABE, est fortement inspire d’AODV. Il permetde trouver des routes a la demande en fonction des specifications des couches applicatives.Le chapitre suivant est consacre a l’evaluation des performances d’ABE.

Dans un reseau ad hoc, nous pouvons etre en presence de trafics au mieux ou Best Effortqui consomment une part non negligeable de la bande passante. Par consequent, les flux dequalite de service ne peuvent etablir des routes offrant la bande passante desiree, une partiede celle-ci etant occupee par ces transmissions Best Effort. Dans le sixieme chapitre, nousproposons un protocole appele DRBT (Dynamic Regulation of Best Effort Traffic) capablede degrader le debit des flux non privilegies afin d’augmenter le taux d’acceptation des flux

7

avec qualite de service. Cette degradation necessite au prealable une estimation de la bandepassante residuelle specifique aux flux QoS. Pour ce faire nous partons du protocole ABEauquel nous rajoutons un mecanisme de differenciation des flux dans l’evaluation de la bandepassante residuelle.

Le septieme chapitre presente un protocole de reservation de delai pour les reseaux adhoc. La principale contribution est d’estimer le delai moyen de bout-en-bout des flux. Cedelai peut se decomposer en deux composantes principales :

– Le delai de buffering dans la file d’attente des nœuds .– Le delai de transmission sur le medium radio.

Les principaux mecanismes developpes dans ABE ont ete etendus afin d’estimer le delai debout-en-bout des flux QoS. Le protocole DEAN (Delay Estimation in Ad Hoc Network) ainsimis en place repose sur une correlation entre delai et bande passante residuelle.

Enfin, le huitieme et dernier chapitre conclut cette these. Avant de rentrer dans le cœurdu document, il est important de noter que toutes les solutions proposees dans cette thesereposent sur une version de 802.11 non modifiee.

8

CHAPITRE

1 Presentation de 802.11

La mise en place de reseaux sans fil multi-sauts necessite l’utilisation d’une technologiesans fil qui permet aux mobiles a portee de communication de dialoguer. Le role de cettetechnologie est de permettre aux mobiles d’acceder au canal radio, de gerer cet acces concur-rentiel afin d’eviter le monopole du canal radio par certaines stations et de communiquer.

Dans la seconde moitie des annees 90, plusieurs technologies sans fil on vu le jour, laissantentrevoir des nouvelles perspectives pour l’utilisation des ces reseaux.

Elaboree sous la tutelle de l’E.T.S.I. (European Telecommunications Standards Institute),Hiperlan1 est une norme europeenne. Elle offre a l’origine un debit de 20Mbps, mais laversion la plus recente (Hiperlan2) permet d’atteindre des debits de l’ordre de 54Mbps. Sonoriginalite reside dans le fait qu’Hiperlan (versions 1 et 2) exploite la gamme de frequenceautour des 5GHz utilisable sans aucune autorisation specifique. Cela permet aujourd’huison exploitation pour un usage local, sous certaines conditions de limitation de puissancedes emetteurs. Neanmoins, peu d’equipements Hiperlan ont penetre le marche commercial.

Bluetooth a comme objectif de faire disparaıtre les cables entre divers equipementsnumeriques (peripheriques d’ordinateurs tels que claviers, souris, imprimantes, modems,...).Les reseaux Bluetooth ont ete developpes pour permettre la realisation de reseaux personnels(PAN : Personnal Area Network). Les reseaux Bluetooth sont construits de maniere centra-lisee. Un maıtre elu controle toutes les transmissions des autres stations appelees esclavesformant ainsi un piconet. Les esclaves ne peuvent emettre des paquets que s’ils y ont eteinvites par le maıtre. Ce dernier doit donc les interroger regulierement pour savoir s’ils ontdes donnees a envoyer. Les equipements bluetooth ont une portee limitee, de l’ordre du metreet des debits assez modestes combines a une faible consommation d’energie.

Plus recemment, la technologie WIMAX pour Worldwide Interoperability for MicrowaveAccess a vu le jour bien qu’elle soit encore en phase de tests. Egalement connue sous ladesignation d’IEEE 802.16, le WIMAX est un standard de transmission sans fil a haut debit.Fonctionnant a 70 Mbps, il est prevu pour connecter les points d’acces WIFI a un reseau defibres optiques, ou pour relayer une connexion partagee a haut debit vers de multiples utilisa-teurs. Avec une portee theorique de 50 km, il devrait permettre, a terme, le developpement dereseaux metropolitains reposant sur un unique point d’acces, contrairement aux architecturesbasees sur de nombreux points d’acces WIFI.

Cependant, la norme qui semble actuellement s’imposer au niveau mondial est la normeIEEE 802.11 [6]. Elle a connu un tel succes que son appellation commerciale est devenue

9

CHAPITRE 1. PRESENTATION DE 802.11

le WIFI pour Wireless Fidelity. Le WIFI est promulgue par un consortium appele le Wi-Fialliance, charge de maintenir l’interoperabilite entre les equipements repondant a la norme802.11.

Dans ce chapitre nous allons detailler la norme IEEE 802.11 et plus specifiquement leprotocole d’acces au medium. Nous nous interessons plus particulierement a cette normecar c’est la technologie que nous utilisons dans la suite de nos travaux. De plus, nous nousconcentrons sur le protocole d’acces au medium car comme nous le verrons, ce protocole a unimpact important sur les techniques d’evaluation de ressources que nous cherchons a mettreen place.

1.1 Le protocole IEEE 802.11

1.1.1 Fonctionnement general

Le protocole 802.11 est une norme etablie par l’IEEE qui decrit plusieurs couches phy-siques ainsi qu’une couche LLC et MAC pour les reseaux locaux sans fil. L’architecture encouche de 802.11 (figure 1.1) rappelle celle de 802.3, le celebre Ethernet [7]

Fig. 1.1 – Architecture en couche de 802.11

Les quatre couches physiques constituant la norme definissent differents codages afin detransmettre de maniere fiable les donnees en multiplexant plusieurs canaux de transmission.

– La technique FHSS (Frequency Hopping Spread Spectrum) ou etalement de spectrepar saut de frequence consiste a diviser la bande de frequence en 75 canaux d’unelargeur de 1Mhz chacune, puis de transmettre en utilisant une combinaison de canauxconnue de toutes les stations de la cellule. La transmission se fait ainsi en emettantsuccessivement sur un canal puis sur un autre pendant une courte periode de temps(d’environ 400 ms).

– La technique DSSS (Direct Sequence Spread Spectrum) ou etalement de spectre asequence directe transmet chaque bit en utilisant 11 changements d’etat du signal.

10


Ainsi, l’emission de chaque bit correspond a la transmission d’une sequence de 11 bitsappelee sequence de Barker. La bande de frequence est alors divisee en 14 canaux d’unelargeur de bande de 22Mhz.

– La technique OFDM (Orthogonal Frequency Division Multiplexing ) divise sur un grandnombre de porteuses le signal numerique a transmettre. Pour que les frequences desporteuses soient les plus proches possibles et ainsi transmettre le maximum d’infor-mation, l’OFDM utilise des porteuses orthogonales entre elles. Par consequent, dansun canal de transmission avec des chemins multiples ou certaines frequences serontdetruites, le systeme sera en mesure de recuperer l’information perdue sur d’autresfrequences porteuses. Ce principe permet de limiter l’interference entre symboles.

– La norme IEEE 802.11 propose egalement une alternative a l’utilisation des ondesradio par le biais de la lumiere infrarouge. Les transmissions se font de maniereunidirectionnelle ou par reflexion.

Dans la premiere version de 802.11, la bande de frequences utilisees etait celle des900MHz. Avec les differentes extensions, d’autres bandes de frequences ont commence a etreexploitees. C’est ainsi que les bandes de frequences dediees au monde industriel, medicalet scientifique, plus communement appele bande ISM situee autour des 2,4GHz (de 2,4 a2,495GHz) sont utilisees pour les versions de 802.11 (1999), 802.11b et 802.11g. Les bandesde frequences autour des 5GHz sont egalement utilisees pour les versions 802.11a et 802.11n(802.11n peut aussi bien fonctionner avec la bande des 2,4GHz qu’avec celle des 5GHz).

Les debits possibles varient entre 1 et 54Mbps suivant les techniques de modulation etles eventuelles extensions de la norme. Cependant la nouvelle norme 802.11n, en cours destandardisation, permet d’entrevoir des debits de l’ordre de 100Mbps. Les portees prevuesvarient de quelques dizaines a quelques centaines de metres en fonction des debits et del’environnement.

Les techniques de codage de ces differentes couches physiques utilisent plusieurs canauxde transmission. Cependant, la plupart des protocoles pour reseaux ad hoc n’utilisent qu’ununique canal pour communiquer. Meme si cette solution pose essentiellement des problemesd’interferences, elle facilite tout de meme la conception des protocoles pour ces reseaux.Cette norme cible deux contextes d’utilisation :

– Le mode infrastructure (figure 1.2(a)) ou les stations de base assurent la couvertured’une certaine zone et prennent en charge les communications entre mobiles dans cettezone.

– Le mode ad hoc (figure 1.2(b)) qui permet les communications entre mobiles sansintervention d’une station de base ou d’autres mobiles exterieurs. Ce mode ne permetque les transmissions entre mobiles a portee de communication.

1.1.2 Description du protocole d’acces au medium

Au-dessus de la couche physique, la couche MAC de la norme IEEE 802.11 definit deuxmodes d’acces au medium :

11


(a) Mode infrastructure (b) Mode ad hoc

Fig. 1.2 – Mode ad hoc et infrastructure de la norme IEEE 802.11

– Le mode PCF (Point Coordination Function) ou la station de base gere les communi-cations entre les mobiles se trouvant dans sa zone de couverture. Une station ne peutemettre que si elle est autorisee par cette derniere.

– Le mode DCF (Distributed Coordination Function) est base sur une ecoute permanentedu medium par les stations desirant emettre. La plupart des cartes 802.11 proposeessur le marche utilisent ce mode d’acces au canal radio, lequel s’inspire tres fortementdu protocole d’acces au medium MACAW [8]. Nous allons decrire son fonctionnementdans la suite de ce chapitre car c’est le mode d’acces que nous considerons dans toutce travail.

Dans le mode DCF, les transmissions s’effectuent en mode diffusion ou broadcast, d’unestation vers plusieurs recepteurs ou en mode point a point ou unicast, d’une station vers ununique recepteur. Dans ce dernier cas, en cas de transmission reussie, le recepteur renvoiea l’emetteur une trame d’acquittement (ACK) afin d’indiquer a ce dernier que la tramede donnees a ete recue correctement. Les trames envoyees en mode diffusion ne sont pasacquittes, du fait de la generation de plusieurs acquittements simultanes, ce qui entraineraıtdes collisions potentielles sur les acquittements ainsi qu’une surcharge du reseau.

La norme definit egalement trois variables temporelles ou IFS (Inter Frame Space) quicaracterisent le temps s’ecoulant entre l’envoi des trames.

– Le SIFS pour Short Inter Frame Space est utilise pour separer l’instant de receptiondes donnees et l’envoi d’un acquittement correspondant. C’est le plus petit ecart entredeux trames et il y a toujours, au plus, une seule station pour transmettre a cet instant.Cette valeur est fixee par la couche physique et est calculee de facon a laisser le tempsa la station emettrice de commuter en mode reception pour pouvoir decoder le paquetentrant. Sa valeur est de 10 µs dans 802.11b.

12


– Le DIFS (DCF Inter Frame Space) est le temps d’attente d’une station voulant com-mencer une nouvelle transmission. Sa valeur est de 50 µs.

– Enfin, l’EIFS (Extended Inter Frame Space) est defini par la norme de la manieresuivante : ”L’EIFS doit etre utilise par la DCF a chaque fois que la couche physiqueindique a la couche MAC qu’une transmission a commence et qu’elle ne resulte pasen une reception correcte de la trame MAC avec une valeur FCS correcte”. Il n’estactuellement pas clair si cette partie de la norme est correctement implantee dans lescartes sans fil du marche et tres souvent, la communaute considere que l’EIFS estutilise quand une station percoit un signal qu’elle ne peut decoder. Elle differe alors satransmission d’un temps egal a EIFS, afin de ne pas provoquer de collision avec cettecommunication en cours. Sa valeur est de 364 µs.

1.1.2.1 Mecanisme d’acces CSMA/CA

Le mecanisme d’acces DCF implemente un algorithme CSMA/CA pour Carrier SenseMultiple Acces with Collision Avoidance dont le but est d’eviter les collisions. Un mecanismede type CSMA fonctionne comme suit : une station voulant emettre ecoute le support detransmission, et si ce dernier est occupe (une autre station est en train d’emettre), alorsla station differe sa transmission. Si le support redevient libre, la station est autorisee atransmettre. Ces types de protocoles sont tres efficaces quand le support n’est pas surcharge,puisqu’il autorise les stations a emettre avec un minimum de delai. Cependant il y a toujoursun risque pour que des stations emettent en meme temps et engendrent des collisions.

Il est donc necessaire de pouvoir eviter au maximum ces collisions. Le mecanisme du ba-ckoff est utilise dans ce but. Il repose sur le tirage aleatoire, dans un intervalle appele fenetrede contention, d’un nombre appele backoff, par une station desirant acceder au medium. Cenombre est compris entre 0 et une valeur maximale correspondant a la taille de la fenetre decontention et notee initialement CWmin. La station devra ainsi attendre en plus du DIFS,une duree supplementaire equivalente au backoff multiplie par la duree d’un slot, le slotcorrespondant a l’unite de temps du standard. Dans le mode DSSS de 802.11b, le slot corres-pond a une duree de 20µs. Lorsque le support est libre, les nœuds decrementent leur backoffd’une unite a chaque slot. La premiere station atteignant la valeur 0 emet ses informationssur le canal radio.

Si pendant la decrementation du backoff une nouvelle transmission est detectee, ladecrementation du backoff est interrompue et ne pourra reprendre qu’en cas de liberationdu canal radio.

La figure 1.3 decrit un exemple d’acces concurrentiel au canal radio lors d’une trans-mission par deux stations A et B a portee de communication radio. Les stations A et Bsouhaitent emettre chacune une trame a la meme date. Apres une duree d’attente communeDIFS, la station A qui choisit le plus petit backoff accede au canal et transmet sa trame.Pendant cette duree d’emission, le nœud B ne peut acceder au canal qu’il voit occupe. Apresla reception de l’acquittement correspondant au niveau du nœud A, indiquant que la trans-mission s’est deroulee correctement, le nœud B peut alors effectuer sa transmission apresavoir decremente son backoff restant.

13


Fig. 1.3 – Exemple d’acces au canal par deux stations concurrentes

1.1.2.2 Retransmissions et backoff exponentiel

Dans l’exemple precedent, les transmissions se deroulent sans collision et chaque trameest correctement acquittee. Ce n’est pas toujours le cas et il peut y avoir des collisions quidoivent etre detectees, pour que la couche MAC puisse retransmettre le paquet sans avoira repasser par les couches superieures, engendrant alors des delais significatifs. La detectiondes collisions est indiquee par l’absence de reception d’un acquittement au bout d’un timeoutet provoque la retransmission de la trame jusqu’au succes ou jusqu’a atteindre un nombremaximal de retransmissions autorisees. Dans ce dernier cas, la trame est detruite.

A chaque nouvelle retransmission, le protocole 802.11 double la valeur de la taille de lafenetre de contention afin de reduire le risque de collision. Cette progression est bornee parune valeur maximale CWmax. Lorsqu’une trame est recue correctement, ou rejetee, la fenetrede contention est ramenee a sa valeur initiale.

1.1.2.3 Mecanisme du RTS/CTS

Nous avons vu que le mecanisme CSMA/CA cherche a eviter au maximum les collisionspar l’ecoute du canal et en introduisant un delai aleatoire supplementaire avant une emission.Cependant, il existe une famille de configurations pour lesquelles ce mecanisme est inadapte :il s’agit du probleme des nœuds caches [9] ou deux emetteurs qui ne peuvent pas s’entendreveulent atteindre un meme recepteur comme represente au niveau de la figure 1.4

Les stations emettrices A et B etant totalement desynchronisees, aucun de ces deuxemetteurs ne detectent l’activite de l’autre et chaque station croit que le canal est libre. Dansce cas, les emissions des stations A et B provoquent des collisions au niveau du recepteur B.

Afin de remedier a ce probleme, 802.11 propose un mecanisme utilisant des paquets decontrole appeles RTS (Requet To Send) et CTS (Clear To Send). Un mobile voulant emettreenvoie au prealable au recepteur une requete d’emission RTS. A ce paquet RTS, le recepteur,

14


Fig. 1.4 – Une situation de stations cachees

si le canal radio est disponible, va repondre par un paquet CTS qu’il diffuse a son voisinage,autorisant l’emetteur a transmettre. L’intervalle de temps separant la reception du RTSet l’emission du CTS correspondant est egal a SIFS afin d’empecher l’interruption de cetechange par une autre trame. Ces deux types de paquets contiennent des informations quipermettent la reservation du canal pour la duree de la transmission de donnees correspon-dante. Un mobile qui recoit un CTS sait qu’une station va emettre et doit donc attendre.Le mobile qui a envoye le RTS et recevant le CTS correspondant sait que le canal lui aete reserve et qu’il peut emettre. Ce principe de reservation du canal par l’envoi de petitspaquets de controle est appele detection de porteuse virtuelle ou Virtual Carrier Sense. Laperiode de reservation est stockee dans le vecteur d’allocation du reseau (NAV - NetworkAllocation Vector).

Ce mecanisme permet de reduire l’impact des collisions sans toutefois les supprimerentierement. Il peut arriver que des paquets RTS emis en meme temps par les nœuds A etB entrent en collision au niveau du recepteur C ou que le paquet CTS subisse une collision.

1.1.2.4 Zones de communication

La qualite du signal radio en reception va directement caracteriser la precision dudecodage des informations recues. La transmission du signal radio dans l’air est un mecanismecomplexe affecte par divers phenomenes :

– Plus la puissance d’emission est grande, plus la zone de couverture radio l’est aussi.Cependant comme nous l’avons vu precedemment la puissance des equipements estreglementee. En France, l’ART1 limite la puissance d’emission des mobiles WIFI a100mW.

1Autorite de regulation des telecommunications

15


– Les signaux radio subissent un affaiblissement en fonction de la distance et du milieutraverse. Pour une bonne comprehension des signaux recus, ces signaux doivent etrerecus avec une puissance superieure a une puissance minimale, cette derniere etantfonction du debit d’emission.

– D’autres perturbations du signal en reception proviennent des signaux environnantsemis simultanement dans la meme bande de frequence, empechant un decodage desinformations. Ainsi le SINR (Signal to Interference and Noise Ratio) representant lerapport entre la puissance du signal recu et la somme des puissances des communica-tions interferentes est donne par la formule :

SINR =Pr∑

Psignauxinterferents

Ce SINR, qui donne une indication sur la qualite du signal, doit etre superieur a unevaleur seuil pour que les cartes 802.11 puissent decoder proprement le signal recu. Parexemple, selon les donnees du constructeur Orinoco [10], il faut un SINR ≥ 7 dB pourun debit de 2 Mb/s.

Fig. 1.5 – Zones de communication et de detection de porteuse

La norme 802.11 definit pour tout mobile deux zones radio. Une zone dite de communi-cation dans laquelle tout nœud recepteur est capable de decoder proprement le signal envoyepar la source. Une zone dite de detection de porteuse (figure 1.5) dans laquelle le recepteur nepeut decoder proprement le signal envoye par la source bien que le mecanisme de detectionde porteuse detecte une activite sur le medium. Ceci signifie que tout nœud non a portede communication d’une source mais se trouvant dans la zone de detection de porteuse decette source ne pourra emettre en meme temps que celle-ci. Le partage du medium radiose fait donc aussi bien dans la zone de communication que dans la zone de detection deporteuse. Cette derniere remarque est importante des lors que l’on s’interesse a l’evaluationdes ressources disponibles.

16


1.2 Synthese

L’utilisation d’un protocole tel que IEEE 802.11, initialement prevu pour des reseaux avecstation de base, pose certains problemes lors d’une migration vers un environnement ad hoc.Par exemple, dans [11], les auteurs mettent en exergue le fait que les paquets utilises afin dedecouvrir les mobiles voisins sont emis a un debit de 2Mb/s. Par consequent, ils sont recusa des distances plus grandes que celles des paquets de donnees emis a 11Mb/s, ce qui peutgenerer des informations erronees sur le voisinage effectif des mobiles. De plus, les collisionssur les paquets de diffusion, qui vehiculent generalement des informations importantes sur latopologie, ne sont pas detectees lorsque le reseau devient dense. Il existe aussi des topologiespour lesquelles on constate une inequite d’acces engendree par le mecanisme CSMA/CAde 802.11. Les auteurs de [12] presentent les performances du protocole 802.11b pour destopologies simples presentant des inegalites d’acces au medium radio. En depit de toutesces contraintes, les protocoles ad hoc proposes doivent pouvoir s’adapter aux specificites de802.11 car la migration vers une autre technologie de niveau MAC ne semble pas etre la voieenvisagee dans un futur proche.

Dans ce chapitre, nous avons expose les principaux mecanismes utilises par la norme IEEE802.11. La comprehension de ces mecanismes est importante pour faciliter l’evaluation desressources dans un contexte ad hoc. En effet, cette estimation est tres fortement dependantede la methode d’acces au canal radio. Il paraıt donc primordial lorsqu’on veut assurer desgaranties a une application de pouvoir identifier les trafics susceptibles d’etre en concurrenceavec les emetteurs de ces flux privilegies. Les mecanismes a mettre en place doivent etre enmesure de collecter et de maintenir des informations fiables qui refletent l’etat du reseau.Dans toute la suite de nos travaux, 802.11 en mode DCF est utilise comme protocole d’accesau medium. Aucune modification de ce protocole n’est effectuee par la suite.

17

CHAPITRE

2 Routage ad hoc et qualite deservice

La recherche dans le domaine des reseaux ad hoc s’est d’abord concentree sur la concep-tion de protocoles de routage. Les reseaux ad hoc introduisent de nombreuses contraintesliees essentiellement au medium radio et a la mobilite inherente des utilisateurs. Ainsi, leprocessus de routage vers des destinataires mobiles devient une tache ardue et d’autant pluscomplexe dans le cas ou l’expression de certaines contraintes qualite de service sont rajouteesau niveau des transmissions.

Dans ce chapitre, nous exposons quelques generalites sur les reseaux ad hoc afin decomprendre les phenomenes susceptibles de perturber le processus de routage avec QoS. Nouspresentons ensuite les mecanismes et les problemes lies au routage et enfin nous discutonsbrievement des approches proposees pour mettre en place de la qualite de service dans uncontexte ad hoc.

2.1 Generalites sur les reseaux ad hoc

Les reseaux ad hoc sont des reseaux sans fil et sans infrastructure fixe, ou chaque nœudpeut aussi bien jouer le role d’emetteur (initiateur de la communication), de routeur (relayagedes informations vers d’autres mobiles) que de destinataire (reception et traitement desinformations). Les reseaux ad hoc sont auto-organises ce qui implique que la connectivite doitetre preservee autant que possible en cas de changement de topologie (suite a l’apparition, ladisparition ou aux mouvements de certains nœuds) sans intervention humaine. Ainsi, la seulepresence des terminaux equipes d’une carte d’interface sans fil suffit a creer et maintenir unreseau ad hoc.

Vers le debut des annees 1970, les reseaux ad hoc ont ete concus principalement pour desapplications militaires. Cependant, avec le developpement de l’Internet et la democratisationdes equipements sans fil, les possibilites d’utilisation de ces reseaux semblent beaucoup plusetendues. Les applications que l’on entrevoit actuellement vont des reseaux de capteurssouvent dedies a la surveillance de l’environnement aux reseaux vehiculaires en passant parles reseaux mailles, reseaux sans fil fixes qui permettent par exemple d’etendre un accesInternet sans cablage.

Le medium ou canal radio, partage par tous les nœuds, est une ressource rare qui constitueun des points critiques des reseaux ad hoc. La nature meme du canal radio pose un certainnombre de problemes :

18

CHAPITRE 2. ROUTAGE AD HOC ET QUALITE DE SERVICE

– Une attenuation rapide du signal en fonction de la distance qui induit l’impossibilitepour l’emetteur de detecter une collision au moment de l’emission. L’environnementpeut aussi deteriorer un signal a cause des phenomenes d’attenuation et de reflexionou de chemins multiples.

– Les interferences : les liens radio n’etant pas isoles, une communication entre deuxmobiles peut interferer sur d’autres communications rendant le decodage des informa-tions parfois impossible.

– Liens bidirectionnels : les liens radio ne sont pas toujours bidirectionnels. Ainsi unmobile peut recevoir des donnees de la part d’un autre mobile sans que la reciproquesoit vraie. Ce phenomene pose un probleme dans le processus de decouverte de route carlorsqu’un chemin est cree, les informations de reponse ne peuvent pas toujours emprun-ter le chemin inverse, necessitant la construction d’une nouvelle route. Ce phenomenepose aussi un probleme des lors qu’on utilise des echanges point-a-point avec 802.11puisque ces echanges ne peuvent fonctionner que sur des liens bidirectionnels.

– La puissance du signal est reglementee par l’ART et donc limitee.– Un faible debit par rapport a un equivalent filaire.– L’energie : les applications relatives aux reseaux sans fil tirent leur autonomie des

batteries et les differentes operations (emettre, recevoir des donnees, ecouter le supportradio) consomment de l’energie non negligeable.

– Une faible securite : le canal radio n’etant pas isole, il est tres facile a l’aide d’uneantenne espionne d’ecouter les informations qui circulent sur le canal d’autant plus qu’ilest partage. Les solutions se trouvent donc au niveau d’un cryptage par l’emetteur.

– La mobilite des utilisateurs inherente a ces reseaux peut se reveler un facteur contrai-gnant car generant des modifications de topologies.

– La versatilite du medium physique qui change rapidement entraıne une instabilitedes transmissions radio.

2.2 Le routage dans les reseaux ad hoc

Une des grandes problematiques des reseaux ad hoc est la mise en place de politiques deroutage. La legislation en vigueur impose une limitation de la puissance des transmissionsradio, ce qui reduit la portee des mobiles. De ce fait, dans un reseau ad hoc, il est frequentque deux mobiles desirant communiquer soient hors de portee l’un de l’autre. Afin de per-mettre ces communications, les mobiles d’un reseau ad hoc doivent etre capable d’acheminerles informations vers leur destinataire, relaye par des mobiles intermediaires, c’est a dire d’ef-fectuer un routage des donnees. Cette these n’est pas consacree aux protocoles de routage adhoc, mais pour tester les techniques d’evaluation de ressources proposees ici, il nous a semblepertinent de les integrer dans des protocoles de routage avec qualite de service, comme nousle verrons par la suite. C’est pourquoi, une courte section de ce chapitre est consacree auxprotocoles de routage ad hoc.

La gestion de l’acheminement de donnees ou le routage consiste a assurer une strategiequi doit permettre a n’importe quel moment, la connexion entre n’importe quelle paire

19


de nœuds appartenant a un reseau. La diffusion est utilisee afin d’inonder le reseau etles informations sont alors relayees de proche en proche par les mobiles intermediaires.Evidemment, ce mode de fonctionnement consomme une quantite non negligeable de bandepassante. La plupart des protocoles de routage utilises ont ete concus afin d’optimiser cettediffusion. Dans [13], les auteurs mettent en relief certaines contraintes introduites par lesreseaux ad hoc et qui perturbent ce processus de routage. La prise en compte des contraintesspecifiques precitees rend cette conception plus complexe que dans le monde filaire.

Les protocoles de routage dans les reseaux ad hoc sont generalement classes en quatregrandes categories :

1. Les protocoles de routage proactifs maintiennent a jour une table de routage, desorte que lorsqu’une application desire envoyer des donnees, la route est immediatementconnue. Ces protocoles ont l’avantage de la disponibilite immediate des routes verstous les nœuds du reseau. Au niveau de la table de routage, chaque nœud stocke pourchaque destination, l’identite du mobile a contacter. La mise a jour de cette table deroutage necessite l’echange regulier de messages de controle, consommant une part nonnegligeable des ressources radio meme en l’absence de trafic. Comme dans les reseauxfilaires, deux principales methodes sont utilisees : le routage par vecteur de distance etle routage par etat de lien.– Le routage par etat de lien consiste a diffuser periodiquement aux mobiles voisins

l’etat de la liaison qui les separe. De cette facon, chaque mobile est capable de dresserune carte de l’etat du reseau et par consequent de choisir la route la plus approprieepour un message donne. Un des avantages de ce type de protocole est sa capacite apouvoir facilement trouver des routes alternatives en cas de rupture de lien.

– Le routage par vecteur de distance permet a chaque nœud de diffuser a ses voisinsla distance qui les separe (en nombre de sauts). Les seules informations conserveessont la liste des nœuds du reseau et l’identite du prochain mobile par lequel passerpour atteindre la destination. Le mobile emetteur choisit la route la plus courte ennombre de sauts vers le destinataire.

L’inconvenient des protocoles proactifs reside dans le cout du maintien des informationsde topologie et de routage meme en absence de trafic de donnees ce qui implique uneconsommation continue de la bande passante. Comme exemple de protocoles de routageproactifs, nous pouvons citer OLSR [14] et DSDV [15] qui constituent respectivementles versions sans fil des protocoles OSPF [16, 17] et RIP [18]. Nous pouvons egalementciter TBRPF [19].

2. Les protocoles de routage reactifs restent inactifs tant qu’aucune application nesollicite l’envoi de donnees. Ceci permet d’economiser de la bande passante et del’energie. La procedure de decouverte de route n’est enclenchee que lorsqu’un nœud sou-haite envoyer des paquets vers un destinataire pour lequel aucune route n’est connue.Une demande de route explicite vers ce destinataire est alors propagee a travers lereseau. Cette inondation surcharge localement le reseau puisque tous les nœuds at-teints doivent repeter la requete. Si le reseau est mobile, le processus de reconstruction

20


de route engendre de nouvelles inondations. En consequence, le delai des paquets peutaugmenter tres rapidement. Le principal avantage est de ne generer du trafic que sinecessaire mais cela implique une inondation du reseau couteuse en ressources.

Source

F

Dest.

D

C

E

A

B

rreq (1)

rreq (1)

rreq (2)

rreq (3)

rreq (4)

rreq (3)rreq (2)

rrep (1)

rrep (2)

rrep (3)

rrep (4)

rreq (2)

rreq (4)

Fig. 2.1 – Recherche de route dans AODV

AODV [20] fait partie de la famille des protocoles reactifs. Lorsqu’une application desiretrouver une route vers un destinataire, AODV inonde le reseau avec des paquets RouteRequest (RREQ). Chaque nœud traverse par un paquet de RREQ stocke des informa-tions sur le numero de sequence du paquet, l’adresse des nœuds source et destinationainsi que l’adresse du nœud precedent. Lorsque ces paquets de RREQ arrivent a ladestination, un paquet de reponse Route Reply (RREP) est envoye suivant le chemininverse vers le nœud emetteur (voir figure 2.1). Ce paquet permet, au niveau de chaquenœud, de mettre a jour le saut suivant pour la route construite. On parle de routagepar sauts. Nous pouvons egalement citer DSR [21] comme protocole de routage reactif.

3. Les protocoles de routage hybrides combinent les approches reactive et proactive.Le principe est de connaıtre le voisinage de maniere proactive jusqu’a une certainedistance (deux ou trois sauts par exemple), et lorsqu’une application cherche a envoyerdes donnees a un nœud hors de cette zone, une recherche reactive est enclenchee. Unezone de routage est definie pour chaque nœud et inclut l’ensemble des mobiles quisont a une distance (en terme de sauts) inferieure a une valeur fixee representant lerayon de routage. Grace a cette combinaison, le reseau est partage en plusieurs zoneset la recherche de route en mode reactif est amelioree. A la reception d’une requete derecherche reactive, un nœud a la possibilite d’indiquer immediatement si la destinationest dans son voisinage ou non. ZRP [22] est le protocole hybride le plus connu, maisnous pouvons egalement citer comme exemple CEDAR [23] et CBRP [24].

4. Les protocoles de routage geographiques se basent sur des informations concer-nant la position des mobiles afin d’ameliorer le processus de routage. Un systeme de

21


localisation est donc mis en place afin de connaıtre a un instant donne la positiondes mobiles. Le GPS est actuellement le systeme de localisation le plus utilise memesi d’autres algorithmes proposent de calculer la position des mobiles a l’aide d’autresparametres comme par exemple la puissance du signal. Une fois que la position du mo-bile destinataire est evaluee, la diffusion des messages de recherche de route peut etreorientee vers une direction precise, reduisant considerablement le trafic de decouvertede route. Un exemple de protocole geographique est le protocole LAR (Location-AidedRouting) [25].

Tous ces protocoles cites precedemment sont sans qualite de service, c’est-a-dire que leurobjectif est de trouver une route vers un mobile destinataire sans tenir compte de l’etatdes ressources a travers le reseau. Pour certaines applications qui voient le jour, comme parexemple la diffusion de video ou la telephonie sur IP, les protocoles de routage precedentsne sont pas toujours en mesure d’assurer les contraintes demandees par ces applications. Ilsemble donc necessaire de s’orienter vers d’autres approches, comme par exemple la mise enplace de qualite de service.

2.3 La qualite de service dans les reseaux ad hoc

Le terme Qualite de Service ou QoS a largement ete utilise pour definir de nombreuxconcepts sans toutefois converger vers un consensus. La RFC 2386 [26] definit la QoS commeun ensemble de garanties a assurer, par le reseau, pour le transport d’un trafic d’une sourcevers une destination. Nous retiendrons cette definition et plus formellement nous definissonsla Qualite de Service comme l’ensemble des mecanismes mis en œuvre dans un reseau afin desatisfaire les besoins explicites des applications lors de l’acheminement des flux de donnees.

Les mecanismes classiques de qualite de service dans les reseaux filaires sont totalement oupartiellement inadaptes dans un environnement ad hoc. En effet, la plupart des ces methodesreposent sur la connaissance d’informations precises quant a l’etat du reseau (la bande pas-sante utilisee, le delai, la gigue de phase, etc.). Dans un contexte sans fil, ces informationssont difficiles a evaluer notamment a cause des phenomenes propres aux transmissions sans fil(versatilite du lien radio, interferences, attenuation du signal, etc.) et peuvent etre ameneesa varier tres rapidement, en fonction de la mobilite.

Un etat de l’art sur la QoS dans les reseaux ad hoc, a ete propose dans [27], classifiantles solutions de QoS en quatre grandes categories :

– Les modeles de QoS definissent des architectures globales dans lesquelles des garantiespeuvent etre fournies.

– Les protocoles d’acces au medium cherchent a ajouter des fonctionnalites aux couchesbasses du modele OSI1 afin de pouvoir offrir des garanties.

– Les protocoles de routage avec qualite de service recherchent les routes ayant suffisam-ment de ressources disponibles pour satisfaire une requete.

1Open Systems Interconnection

22


– Les protocoles de signalisation cherchent a offrir des mecanismes de reservation deressources independants du protocole de routage sous-jacent.

Cette classification tres souvent utilisee, permet d’identifier les differentes briques amettre en œuvre pour assurer une certaine qualite de service. Dans [28], les auteurs proposentune classification differente : ils distinguent les approches de qualite de service statistiquedes approches avec garanties quantitatives. Dans les approches de qualite de service statis-tiques, l’idee est d’offrir plus de ressources aux trafics prioritaires compares aux trafics moinsprioritaires, sans neanmoins assurer de garanties quantitatives. La norme IEEE 802.11e [29],fait partie de cette approche. Dans un contexte ad hoc, l’ordre des priorites reste neanmoinsdifficile a respecter de part la difficulte de reporter des politiques locales de voisinage envoisinage. Pour des applications strictes comme la diffusion de video, les approches avecgaranties quantitatives nous semblent plus appropriees.

Parmi les approches avec garanties quantitatives, les auteurs de [28] distinguent les ap-proches a posteriori des approches a priori. Les approches a posteriori peuvent etre baseessur n’importe quel protocole de routage et ne cherchent qu’a reguler l’environnement afind’offrir des garanties aux applications le necessitant. A l’oppose, les approches a priori vontse baser sur un routage avec qualite de service. Le principe du routage avec qualite de serviceest de rechercher un chemin entre deux nœuds satisfaisant certaines contraintes. Plusieursmetriques peuvent etre utilisees telles que le delai, la bande passante, la gigue ou encore letaux de perte.

Il m’a semble que l’approche du routage avec qualite de service permettait d’offir uncontrole plus fin que celui offert par les approches a posteriori. Par consequent, je me suisconcentre sur cette approche.

Un tres grand nombre de protocoles de routage de QoS ont ete proposes. On retrouvela dichotomie classique entre protocoles reactifs et proactifs. Ainsi, le routage avec qualitede service ajoute en general a ces protocoles de routage usuels un controle d’admission afinde selectionner parmi les routes disponibles celles qui satisfont les contraintes specifiees parl’application. Le controle d’admission est une etape tres importante dans le routage QoS : ils’agit plus precisement de determiner si les conditions du reseau permettent de transmettreles flux avec les garanties requises. L’admissibilite des flux est faite en fonction de deuxparametres :

– La quantite de ressources exigee par l’application : les applications doivent etre en me-sure de quantifier leur besoin en terme de ressources, comme par exemple la quantitede bande passante dont elles ont besoin. Ceci fait apparaıtre une specificite du routageavec QoS : l’eligibilite d’une route doit etre determinee flux par flux et non plus des-tination par destination. Il est tout a fait envisageable d’utiliser des routes differentespour des flux ayant des contraintes differentes. Le routage par flux permet par ailleursd’assurer un controle plus fin des ressources du reseau. On peut par exemple imagi-ner decomposer un flux en plusieurs petits sous-flux, chacun empruntant une routedifferente.

23


– L’estimation des ressources residuelles ou disponibles le long des chemins qui doit etreconnue a priori avant l’envoi des flux QoS. C’est un point critique et beaucoup deprotocoles de routage QoS se concentrent davantage sur la partie routage que sur lapartie estimation des ressources residuelle. Cette estimation des ressources est rendueplus complexe dans un contexte ad hoc ou contrairement aux reseaux filaires, les liensentre mobiles sont versatiles, peu fiables, et partages inequitablement.

Pour resumer, le routage avec QoS est un processus d’etablissement et de maintenancedes routes satisfaisant un ensemble de criteres quant a la qualite de la transmission desdonnees. Nous pensons que le point critique de ce processus reste l’estimation des ressourcesdisponibles a travers le reseau car la precision du controle d’admission depend fortement decette estimation.

Certains protocoles de routage supposent que cette estimation est connue et ne reposepas sur une technique d’evaluation des ressources specifiques. C’est le cas par exemple duprotocole CEDAR [23]. D’autres protocoles en revanche proposent leur propre techniqued’evaluation des ressources. Ces differentes techniques font l’objet du chapitre suivant.

24

CHAPITRE

3 Etat de l’art sur les tech-niques d’evaluation de labande passante residuelle

De nombreux protocoles de routage ad hoc avec QoS utilisent leur propre techniqued’evaluation des ressources disponibles. La majorite de protocoles se concentrent sur le pa-rametre de bande passante qui est une metrique tres importante dans les reseaux ad hoc.En effet, la bande passante est tres limitee dans les reseaux sans fil et son partage est trescomplique, plus particulierement dans les reseaux ad hoc. De plus, ce parametre a un impactsur les autres parametres du reseau comme par exemple le delai ou le taux de perte. Maıtriserles debits dans le reseau permet de limiter la congestion et par consequent d’ameliorer lesdelais de transmission et les taux de pertes. Par consequent, les techniques d’evaluation dela bande passante residuelle sont fondamentales et ont constitue le cœur de mon travail.

Les techniques d’evaluation de la bande passante disponible peuvent se subdiviser endeux grandes categories :

– Les techniques dites intrusives basees sur l’envoi de paquets de controle afin d’estimerla bande passante residuelle le long d’un chemin.

– Les techniques dites passives qui utilisent des informations locales (comme par exemplele taux d’utilisation du canal). Les messages Hello que l’on retrouve dans la plupart desprotocoles de routage classiques et qui permettent la mise a jour des informations devoisinage sont generalement utilises afin d’echanger les informations de bande passante.

Avant de dresser un etat de l’art sur les principales techniques d’evaluation de la bandepassante residuelle dans les reseaux filaires et sans fil, nous definissons la notion de bandepassante residuelle ainsi que les problemes lies a l’estimation de cette metrique dans lesreseaux ad hoc.

3.1 La bande passante residuelle ou disponible

La bande passante residuelle ou disponible entre deux mobiles peut se definir comme ledebit maximal qui peut etre emis entre deux nœuds sans degrader aucun des flux dejapresents dans le reseau. Cette notion est differente de la capacite qui represente juste ledebit maximal d’emission entre deux mobiles.

Lors de la mise en place d’un protocole de reservation de bande passante, l’estimation decette bande passante disponible doit etre la plus precise possible quels que soient les trafics

25

CHAPITRE 3. ETAT DE L’ART SUR LES TECHNIQUES D’EVALUATION DE LABANDE PASSANTE RESIDUELLE

existants et de la topologie, afin de choisir les routes susceptibles d’offrir aux applications QoSles garanties desirees. Neanmoins, la bande passante residuelle est une metrique difficilementquantifiable dans un environnement ad hoc multi-saut pour les raisons suivantes :

– Lorsque n emetteurs a portee de communication sont en competition pour l’accesau medium, la bande passante utilisable au niveau application par chaque emetteurn’est pas egal a la bande passante qu’obtiendrait un seul emetteur divisee par n.En effet, avant d’emettre, chaque nœud doit s’assurer que le canal radio a ete librependant un certain temps aleatoire. Lorsque plusieurs emetteurs sont en concurrence,ces attentes ont lieu en parallele, ce qui permet de reduire globalement le surcout duprotocole d’acces au medium. Toutefois, on ne peut augmenter indefiniment le nombred’emetteurs sans risquer de collisions. Dans ce cas, les delais sont a nouveau allongescar le protocole 802.11 retransmet les paquets perdus.

– Le medium etant partage et la topologie multi-saut, la perception de la bande passanteutilisee et disponible est differente d’un mobile a un autre. Par consequent, en plus dela bande passante qu’il consomme, un mobile doit avoir une estimation de la bandepassante consommee par les mobiles voisins avec lesquels il partage le medium. Celasuppose une connaissance exacte du voisinage, ce qui n’est pas toujours le cas.

– Dans un reseau ad hoc, il y a egalement un partage de la bande passante dans la zonede detection de porteuse de 802.11 comme nous l’avons decrit dans le chapitre 1.

– Le phenomene des stations cachees tend aussi a diminuer le debit des communications.Cette situation provoque des collisions au niveau du recepteur qui voit son debit chuter.

Par consequent, la bande passante residuelle est une metrique complexe a evaluer carelle doit prendre en compte aussi bien les caracteristiques des transmissions voisines, queles phenomenes physiques dus au medium radio sous-jacent et a la technologie d’acces aumedium (802.11 dans notre cas).

3.2 Evaluation de la bande passante residuelle dans les

reseaux filaires

Les techniques utilisees pour evaluer la bande passante residuelle dans les reseaux filairessont essentiellement intrusives.

Jain et Dovrolis dans [30] ont mis au point une technique appelee Pathload afin d’estimerla bande passante residuelle le long d’un chemin. Periodiquement des paquets de controlesont envoyes par les stations sources vers les stations destinataires afin d’evaluer la bandepassante disponible le long de ces chemins. Pour chaque paquet de controle envoye de bouten bout, le delai de transmission est mesure. L’observation effectuee est que le delai de cespaquets de controle augmente lorsque le debit (R) du flux est superieur a la valeur de la bande

26


passante residuelle notee A. En faisant varier la valeur de R, et en procedant de maniereiterative et dichotomique, on peut estimer la valeur de A. La difficulte est de determinera partir de quelle valeur le delai augmente de maniere assez significative pour en deduireune approximation de la bande passante residuelle. Les iterations se poursuivent jusqu’a unevaleur ε qui mesure la precision definie a l’avance par l’utilisateur et telle que :

R(n) < A < R(n + 1) et |R(n + 1)−R(n)| < ε avec R(n) etant le debit du nieme paquet

Les auteurs comparent par la suite la precision de l’estimation de la bande passante residuelleobtenue avec Pathload, avec celle obtenue grace a MRTG [31] (Multi Router Traffic Grapher),un outil permettant de surveiller la charge de la circulation des donnees qui transitent surun reseau filaire. Les experimentations aboutissent a une estimation de Pathload presentantun taux d’erreur moyen de l’ordre de 2% sur plusieurs simulations.

Carter et Crovella [32] experimentent une technique appelee cprobe. Les paquets decontrole utilises sont constitues de paquets ICMP (Internet Control Message Protocol)vehiculant generalement des messages de controle et d’erreur dans un reseau filaire. La sourceenvoie un train de paquets ICMP echo vers la destination. Lorsque la machine destinataireou serveur recoit ces paquets ICMP echo, elle repond en envoyant des paquets de reponseICMP reply. Les temps d’inter-arrivee de ces paquets ICMP sont mesures pour en deduirela valeur de la bande passante residuelle le long du chemin.

Dans [33] les auteurs proposent un modele theorique appele TOPP (Train of Packet Pair)qui introduit deux nouveaux concepts : le concept de Proportionnal Share qui represente laproportion de bande passante que le lien va pouvoir offrir a un nouveau flux entrant en nedegradant que legerement les flux deja presents et celui de Surplus Bandwith qui est uneborne inferieure de la bande passante residuelle. Cette technique TOPP est basee sur lememe principe que Pathload. Cependant, la fonction d’augmentation du debit de la sourceest lineaire. Parallelement, les auteurs prennent en compte un autre facteur important :le nombre de liens congestionnes. Les experimentations montrent qu’au-dela de deux lienscongestionnes, les mesures de bande passante residuelle ne sont plus assez precises.

Dans [34], les auteurs proposent un resume detaille des differentes techniques d’evaluationde la bande passante residuelle dans le monde filaire. Ils mettent en relief trois grandescategories :

– Les techniques VPS (Variable Packet Size) mesurent le RTT (Round Trip Time) entrela source et la destination en fonction de la taille du paquet de controle envoye. CeRTT est calcule en fonction de la valeur contenue dans le champ TTL du datagrammeIP. Cette technique peut sous-estimer la bande passante residuelle car elle ne tient pascompte du temps passe dans les couches basses.

– Les techniques PPP (Packet Pair Probing) mesurent la dispersion entre paires de pa-quets de meme taille envoyes de la source vers la destination et de la destination versla source. La valeur mesuree correspond davantage a la capacite qu’a la bande passanteresiduelle.

– Les techniques SLoPS (Self-Loading Periodic Streams) mesurent le bande passanteresiduelle de bout en bout en monitorant le delai de paquets de controle de taille

27


identique.

3.3 Evaluation de la bande passante residuelle dans les

reseaux sans fil

Dans le monde filaire, les methodes utilisees pour estimer la bande passante residuellese sont revelees efficaces en partie. Par contre, elles ne sont pas directement adaptables aun environnement ad hoc dans lequel la problematique devient beaucoup plus complexe.Certains travaux ont vu le jour dans le monde sans fil, presentant aussi bien des techniquesintrusives que passives.

3.3.1 Les techniques intrusives

DietTOPP [35] est basee sur le meme principe que TOPP [33], mais a ete concu pourdes environnements sans fil. Un train de paquets de controle est envoye du nœud source versle nœud destinataire avec un debit initial dmin et du nœud destinataire vers le nœud source.Lorsque ce train de paquets de controle a ete totalement acheminee, le debit d’emissionest progressivement augmente d’une valeur δi jusqu’a atteindre une valeur maximale dmax

pour laquelle on observe une egalite entre le debit du nœud source et du nœud recepteur.Cette valeur dmax represente la bande passante residuelle. Cette technique, faisant partiede la famille des Packet Pair Probing, l’inconvenient est que la valeur mesuree corresponddavantage a la capacite qu’a la bande passante residuelle comme explique precedemment.

Afin d’estimer la bande passante residuelle d’un nœud vers ses voisins, les auteurs de [36]proposent de considerer une taille de paquet standard et de saturer le medium avec cettetaille de paquet afin de calculer la capacite de chaque lien. Cette capacite mesuree estconsideree comme la bande passante disponible, ce qui ne correspond pas a la notion definieprecedemment.

Dans [37], les auteurs mettent en relief le fait que le delai des paquets, superieur a unevaleur theorique maximale, permet d’estimer une utilisation du medium et d’en deduirela bande passante residuelle. L’inconvenient majeur de cette technique est que la valeurtheorique maximale ne prend pas en compte les eventuelles retransmissions imposees par lanorme IEEE 802.11 en cas de collision et la periode de contention qui peut etre tres eleveedans des topologies presentant des inequites d’acces.

Toutes ces techniques sont intrusives car elles utilisent des paquets de controle envoyes debout en bout pour estimer la bande passante residuelle le long d’un chemin. Une consomma-tion importante de la bande passante et un impact non negligeable sur les trafics de donneessont les deux inconvenients majeurs de ces techniques.

28


3.3.2 Les techniques passives

Chaudet et Guerin Lassous ont propose BRuIT [38, 39] (Bandwith Reservation under In-Terferences) qui prend en compte la notion de zone de detection de porteuse dans l’evaluationde la bande passante disponible. En effet, avec les protocoles de type CSMA/CA, deux nœudsqui sont en zone de detection de porteuse partagent l’acces au medium et donc la bande pas-sante meme s’ils ne sont pas capable de communiquer directement. Par consequent, chaquemobile doit etre en mesure d’estimer l’occupation du medium due aux mobiles dans sa zonede detection de porteuse. BRuIT approxime cette zone de detection de porteuse par le voi-sinage a deux sauts. Periodiquement, chaque nœud fournit des informations sur la quantitede bande passante qu’il utilise pour router un flux, ainsi que sur celle utilisee par ses voi-sins, en envoyant des messages Hello. Chaque mobile peut donc estimer la bande passanteconsommee dans son voisinage a deux sauts et en deduire sa bande passante residuelle. Leprincipal inconvenient de cette methode est que l’approximation de la zone de detection deporteuse par le voisinage a deux sauts n’est pas toujours vrai.

Fig. 3.1 – Voisinage dans la zone de detection de porteuse

Considerons l’exemple de la Figure 3.1. Le nœud B qui se trouve dans la zone de detectionde porteuse du nœud A ne peut etre atteint par le voisinage a deux sauts, car il n’y a pas denœuds intermediaires pour router ses informations de bande passante vers le nœud A : c’estle phenomene des nœuds brouilleurs. Identifier l’ensemble de ses brouilleurs potentiels estindispensable pour une bonne estimation de la bande passante residuelle. Dans [40], Chaudeta montre que pour une distribution geometrique aleatoire et une connaissance du voisinage aun, deux ou trois sauts, on manque respectivement dans le pire des cas jusqu’a 70, 50 et 45%des ses brouilleurs. De plus, BRuIT peut parfois sous-estimer la bande passante residuellecar il ne tient pas compte de la synchronisation possible des flux voisins.

Dans [41], Yang et Kravets ont propose CACP (Contention Aware Control Protocol).Le but est, comme dans BRuIT, d’estimer la bande passante residuelle des nœuds dans lazone de detection de porteuse. Dans un premier temps, la bande passante residuelle localeest calculee en utilisant les periodes de temps libre au niveau du medium. Dans un secondtemps, pour estimer la bande passante dans la zone de detection de porteuse, trois methodesdifferentes sont proposees : l’utilisation des messages Hello dans un voisinage a deux sauts

29


comme dans BRuIT ; l’augmentation de la puissance d’emission des emetteurs de telle sorteque le signal puisse etre decode par l’ensemble des nœuds dans la zone de detection deporteuse ; enfin la reduction du seuil de sensibilite des recepteurs. Les auteurs mettent enrelief le probleme de la contention intra flux deja etudie dans [42]. En effet, l’emission desdonnees par un mobile va consommer de la bande passante au niveau d’un certain nombrede liens en amont et en aval. Par consequent il est important d’identifier, de maniere precise,le nombre de mobiles qui seront en contention lors de l’emission d’un meme flux QoS.

QoS-AODV [43] utilise une metrique appelee BWER (Bandwidth Efficicency Ratio) afind’estimer la bande passante residuelle au niveau de chaque nœud. Cette metrique exprimele ratio entre le nombre de paquets transmis et recus. QoS-AODV utilise les messages Hellopour collecter les informations de bande passante des mobiles dans son voisinage a un saut.Finalement, la bande passante residuelle d’un mobile est egale au minimum de la bandepassante residuelle estimee par ce mobile et de celle des mobiles dans son voisinage a unsaut.

Dans AAC [44], chaque mobile estime sa bande passante utilisee en additionnant lataille des paquets percus durant une periode fixe. Cette taille des paquets est deduite del’occupation du medium, ce qui permet de prendre en compte les mobiles dans la zone dedetection de porteuse. La bande passante residuelle est le minimum de la bande passanteresiduelle des mobiles se trouvant dans la zone de detection de porteuse de l’emetteur etdu recepteur. De la meme maniere que CACP, AAC propose aussi la prise en compte de lacontention intra-flux.

Dans QOLSR [45], la bande passante residuelle est fonction du taux d’utilisation du canalradio note u. Ainsi, pour un lien i −→ j, la bande passante residuelle sur ce lien notee B(i−→j),est donnee par la formule :

B(i−→j) = u×BpE(i,j)

BpE(i,j) etant le ratio entre la taille du paquet considere, et son temps de service incluantd’eventuels retransmissions en cas de collision. L’inconvenient de cette methode est quel’occupation du medium percue n’est pas forcement la meme entre l’emetteur et le recepteuret que par consequent l’occupation du medium sur le lien i −→ j ne correspond pas al’occupation du medium sur une des extremites de ce lien.

Un des auteurs de QOS-OLSR [46] evalue la bande passante residuelle en presence duphenomene des interferences. Cette evaluation se deroule en trois etapes :

– Dans la premiere etape, l’auteur evalue la bande passante consommee par un flux fpris isolement, sur un nœud se trouvant dans la zone de communication de f .

– Dans la deuxieme etape, la bande passante consommee par le flux f au niveau d’unnœud se trouvant dans la zone de detection de porteuse est evaluee.

– Enfin, dans la troisieme et derniere etape, l’auteur evalue la proportion de bande pas-sante perdue a cause de collisions en presence de stations cachees.

L’auteur specifie que la probabilite qu’un paquet entre en collision une deuxieme fois avecle meme nœud cache est negligeable car cela suppose que les deux nœuds tirent des backoffsproches dans une fenetre de contention plus grande. Ceci est vrai dans le cas du scenario

30


classique des stations cachees (figure 1.4), mais dans des scenarios de stations cachees plusgeneraux (que nous verrons dans la suite de cette these), cette assertion est erronee car lesdeux emetteurs caches n’ont pas necessairement un recepteur commun.

3.4 Motivations

Comme nous l’avons vu precedemment, les techniques intrusives ne sont pas totalementsatisfaisantes car elles consomment une quantite non negligeable de bande passante qui peutaffecter le debit des flux de donnees. Dans [47], les auteurs mettent en relief le fait que labande passante consommee par les paquets de controle peut occuper une part significativedu trafic total dans le reseau.La majorite des techniques passives fournissent davantage une estimation par nœud que parlien et l’approximation de la zone de detection de porteuse au voisinage a deux sauts peutparfois entraıner des evaluations erronees. Cependant, il est indispensable d’avoir une esti-mation precise de la bande passante residuelle sur un lien afin de router les flux QoS dans debonnes conditions. Pour fournir une estimation precise, certaines considerations doivent etreprises en compte. Premierement, pour qu’une communication puisse s’effectuer, le mediumdoit etre libre aussi bien au niveau de l’emetteur que du recepteur. Par consequent, la bandepassante residuelle sur un lien depend de la synchronisation des periodes de temps libresde l’emetteur et du recepteur. La connaissance du recouvrement de ces periodes de tempslibre augmente la precision de l’estimation. Cette notion de synchronisation n’est pas prise encompte dans les techniques passives presentees dans la section precedente. Deuxiemement, lapresence de collisions degrade de maniere significative le debit des communications. Or, dansles techniques precedentes, soit les collisions ne sont pas prises en compte dans l’evaluationsoit les hypotheses utilisees dans le calcul des probabilite de collision sont approximatives.

Fig. 3.2 – Inequite d’acces au medium

Considerons l’exemple decrit au niveau de la figure 3.2. Cette configuration presentee dans[8] est une situation qui entraıne une inegalite en termes de debit. En effet, les emetteurs

31


A et C etant totalement desynchronises, les emissions du nœud C provoquent des collisionsau niveau du recepteur B. Ainsi, la bande passante residuelle sur le lien (A, B) est d’autantplus faible que le nombre de collisions au niveau du recepteur B augmente.

Supposons que nous ayons un flux sur le lien (C,D), et que nous voulons estimer la bandepassante residuelle sur le lien (A,B). Les simulations sont realisees sous le simulateur NS2. Lacourbe representee par ”Bande passante residuelle reelle” du lien (A,B) correspond au debitmaximum que l’on peut faire passer sur ce lien (obtenue par simulation). Les estimationsfaites par BRuIT, CACP ou AAC sont identiques car elles correspondent simplement a ladifference entre la capacite du medium radio et la bande passante consommee par le lien(C,D) (nous sommes respectivement dans des environnements a 2 et 11Mb/s soit des debitsmaximum reels d’environ 1,6 et 5Mb/s). Elles sont representees au niveau des figures 3.3(a)et 3.3(b) par la courbe etiquetee par ”Bande passante residuelle estimee” en fonction dudebit d’emission du lien (C,D).

0

200

400

600

800

1000

1200

1400

1600

0 200 400 600 800 1000 1200 1400 1600

Déb

it en

(kb

/s)

Débit du lien C−>D (kb/s)

Bande passante résiduelle du lien A−>BBande passante résiduelle estimée du lien A−>B

Bande passante résiduelle estimée du lien A−>B avec QOLSR

(a) Capacite de 2 Mb/s

0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000

Déb

it en

(kb

/s)


Bande passante résiduelle du lien A−>BBande passante résiduelle estimée du lien A−>B

Bande passante résiduelle estimée du lien A−>B avec QOLSR

(b) Capacite de 11Mb/s

Fig. 3.3 – Bande passante residuelle du lien (A,B) en fonction du debit sur le lien (C,D)

La courbe representee par ”Bande passante residuelle estimee avec QOLSR” donne unemeilleure evaluation que BRuIT, CACP ou AAC mais neanmoins surestime toujours la bandepassante residuelle reelle.

On remarque donc que plus le debit du lien (C,D) augmente, plus la bande passanteresiduelle reelle devient plus petite que la bande passante residuelle estimee avec lesdifferentes methodes. L’explication de cette difference se trouve au niveau des collisions quiapparaissent au niveau du recepteur en B. Ces collisions degradent de maniere significativele debit du lien (A,B) et doivent etre prises en compte pour raffiner l’estimation. BRuIT,CACP ou AAC ne les prennent pas en compte tandis que QOLSR les estime de maniereimprecise. Par consequent il est indispensable de mettre au point un mecanisme de predictionplus precis du nombre moyen de collisions au niveau du recepteur. On peut noter quenous n’avons pas teste ici QOS-OLSR. Ceci est lie au fait que le code n’est pas disponibleen ligne d’une part et que d’autre part la methode d’estimation ne se base pas sur une

32


ecoute du medium et est relativement compliquee a implementer. Neanmoins, l’hypotheserealisee pour calculer la probabilite de collision est tres simplifiee (plus simplifiee que dansQOLSR) et nous pensons qu’elle ne peut mener qu’a une surestimation de la bande passanteresiduelle reelle.

En plus des collisions, il est aussi important de considerer des temps d’accessupplementaires tels que le DIFS, l’EIFS et le backoff, rajoutes par le protocole 802.11,consommant ainsi une proportion de la bande passante residuelle.

En resume, des solutions ont ete proposees afin d’estimer la bande passante residuelle dansdes environnements sans fil ad hoc. Cependant, le point faible demeure encore l’estimationde la bande passante residuelle qui est fortement dependante des specificites des reseaux adhoc. Proposer un protocole de routage avec QoS revient a prendre en compte l’ensemble descontraintes (collisions, backoff, etc.) limitant cette bande passante disponible, dans le but derendre l’estimation plus precise.

Dans le chapitre suivant, nous presentons pour notre solution, les mecanismes mis enplace pour estimer la bande passante residuelle d’un lien tout en tenant compte des aspectsprecites afin de rendre cette estimation la plus precise possible.

33

CHAPITRE

4 Une technique d’evaluationde la bande passanteresiduelle : ABE

Dans ce chapitre nous presentons ABE pour Available Bandwdith Estimation, un proto-cole de reservation de bande passante base sur le standard IEEE 802.11. L’apport majeur duprotocole ABE reside dans l’estimation de la bande passante residuelle des liens radio. Cetteestimation permanente et distribuee facilite aux applications le choix des routes pouvantsatisfaire leurs contraintes en terme de bande passante. ABE adopte une approche proactivepour l’estimation des ressources qui est mise a jour periodiquement et une approche reactivepour la recherche de route. Ainsi a partir des informations collectees le long d’une route, ABEest en mesure de predire si une route est capable de fournir assez de bande passante pourune application donnee. La validation du fonctionnement de notre protocole a ete effectueepar simulation.

4.1 Une estimation precise de la bande passante

residuelle

Le but de cette section est de presenter en detail la methode mise en place pour estimer labande passante residuelle d’un lien en tenant compte des preconisations faites dans les para-graphes precedents. A partir de ces preconisations et du fonctionnement du protocole IEEE802.11, nous avons identifie quatre phenomenes pouvant avoir un impact sur l’estimation dela bande passante residuelle.

– Le mecanisme de detection de porteuse empeche a deux mobiles, se trouvant dans cettezone, d’emettre simultanement. Par consequent, un mobile partage de la bande pas-sante avec l’ensemble des emetteurs se trouvant dans sa zone de detection de porteuse.

– Pour qu’une transmission s’etablisse correctement, le canal doit etre libre aux alentoursdes mobiles emetteur et recepteur. La valeur de la bande passante residuelle dependdonc de la synchronisation des periodes de temps libre entre ces deux entites.

– A chaque collision, les paquets de donnees concernes sont retransmis, reduisant ainsila bande passante de disponible.

– Finalement, en cas de collision, le mecanisme du backoff exponentiel double la taillede la fenetre de contention. Ce surplus de temps a un impact sur la valeur de la bandepassante residuelle.

34

CHAPITRE 4. UNE TECHNIQUE D’EVALUATION DE LA BANDE PASSANTERESIDUELLE : ABE

Un lien radio est compose de deux nœuds a portee de communication. Dans notre pro-position nous combinons trois approches :

– Une approche d’ecoute temporelle afin d’estimer localement la bande passanteresiduelle en monitorant l’activite du canal radio. Cette approche ne permet d’esti-mer que la bande passante residuelle des nœuds, mais permet de prendre en compte labande passante consommee dans la zone de detection de porteuse.

– Une evaluation probabiliste de la synchronisation des periodes de temps libres desmobiles aux extremites du lien. L’approche probabiliste semble la plus a meme d’ap-proximer la synchronisation reelle d’un lien qui est difficile a prevoir.

– Une estimation de la probabilite de collision sur le lien considere ainsi que le mecanismedu backoff exponentiel.

Les deux derniers points necessitent l’echange d’informations de bande passante entreles mobiles. Cet echange est realise, non a l’aide des paquets de controle envoyes de bouten bout, mais grace aux paquets Hello que l’on retrouve habituellement dans la plupartdes protocoles de routage. Par consequent, leur utilisation n’entraınera pas un surplus detrafic au niveau du reseau. Ainsi, nous considerons notre methode d’estimation de la bandepassante residuelle comme passive et non intrusive.

4.1.1 Estimation de la bande passante residuelle d’un nœud

Lorsqu’un nœud desire emettre des donnees, il rentre en phase de contention avec lesautres emetteurs se trouvant dans son voisinage. Ainsi, un emetteur potentiel doit evaluer laproportion de temps d’inactivite du medium pour determiner ses chances d’acces au canal.

Considerons un nœud s quelconque du reseau durant une periode de mesure composeede ∆ unites de temps. Nous utilisons les notations suivantes :

– Tidle(s) est la duree totale pendant laquelle le mobile s n’emet pas de donnees et percoitle canal comme libre. Cela signifie que les mecanismes de detection de porteuse et devirtual carrier sensing indique que le canal est dans le mode libre.

– τs est pourcentage d’inactivite du canal percue par s.– Bs est la bande passante residuelle au niveau du nœud s.– Cmax est la capacite du medium.Pendant une periode d’observation composee de ∆ unites de temps, le nœud s ecoute

l’activite du medium et en deduit sa periode globale d’inactivite du medium. (figure 4.1).Les nœuds ne considerent que les periodes d’inactivite du canal superieures a un DIFS,

qui represente la duree d’attente minimale pour qu’une communication puisse demarrer.Par definition, nous avons :

τs =Tidle(s)

∆

Il est important de noter que cette ecoute permanente du medium permet de prendreen compte la bande passante utilisee par les mobiles dans la zone de detection de porteuse.Estimer la bande passante consommee par un mobile se trouvant dans la zone de detection

35


Fig. 4.1 – Occupation medium percue par le nœud s

de porteuse sera d’autant plus difficile que le signal ne pouvant etre decode proprement, cer-taines informations sur cette communication (comme par exemple, l’identite de l’emetteurdu paquet, la taille du paquet), utiles au calcul de la bande passante residuelle, ne pour-ront etre exploitees de prime abord. Cependant, il est interessant de remarquer que toutsignal dont la valeur de la puissance est superieure au seuil de detection de porteuse, bloquel’emission du nœud qui ecoute. Par consequent, le mobile est en mesure d’estimer la dureed’occupation du medium provenant d’un signal en zone de detection de porteuse. Or, c’estla seule information necessaire afin d’estimer la bande passante residuelle d’un nœud. On endeduit donc que la bande passante residuelle du nœud s est bornee :

Bs ≤ τs × Cmax

A ce stade, on constate encore une surestimation de la bande passante residuelle car cettepremiere methode ne prend pas en compte le backoff et les collisions qui peuvent survenir ala reception. Pour etre plus precis, il faut donc considerer l’etat des liens dans le reseau.

4.1.2 Estimation de la bande passante residuelle d’un lien : unepremiere approche

La seule connaissance de la distribution de l’occupation du medium au niveau des mo-biles emetteur et recepteur est insuffisante afin de predire la bande passante residuelle dulien considere. Notre methode doit prendre en compte la synchronisation de ces periodesd’inactivite du medium au niveau de l’emetteur et du recepteur. Pour cela, on effectue uneestimation probabiliste du recouvrement de ces periodes de temps libre a partir de l’occupa-tion medium au niveau de l’emetteur et du recepteur.

4.1.2.1 Prise en compte de la synchronisation des periodes d’inactivite

Considerons un lien radio compose de deux nœuds voisins (dans la meme zone de com-munication) s et r. Nous utilisons les notations suivantes :

– δ represente une unite de temps.– τm = ∆

δest le nombre d’unites de temps pendant une periode de mesure.

36


– τs (resp. τr) est le ratio entre le nombre d’unites de temps pendant lequel le mediumest libre au niveau de s (resp. r) et de ∆, comme decrit dans le paragraphe precedent.

– Bs (resp. Br) est la bande passante residuelle estimee au niveau du nœud s (resp. r).– B(s,r) est la bande passante residuelle reelle du lien (s, r), c’est a dire le debit maximum

d’emission pour lequel, le debit des communications voisines n’est pas degrade. Notreestimation doit donc etre la plus proche possible de cette valeur.

– b(s,r) est la bande passante residuelle estimee du lien (s, r) lorsque le mecanisme desRTS/CTS est desactive.

Lorsque la bande passante residuelle du nœud s est nulle (Bs = 0), ce dernier ne peutacceder au canal qu’il voit toujours occupe. De maniere analogue, lorsque le medium estsature au niveau du recepteur (Br = 0), les emissions de s vont systematiquement provoquerdes collisions au niveau du recepteur r et la communication ne pourra s’etablir. De manieretriviale, nous pouvons etablir que :

B(s,r) ≤ min (Bs, Br).

Introduire dans le reseau un flux dont le debit est superieur a min (Bs, Br), va necessairementsaturer le medium aux alentours de s et/ou r. Dans les reseaux sans fil, la perception del’etat du medium (occupe ou inoccupe) est relative a la position notamment a cause del’attenuation des signaux dans l’air. Pour qu’une communication puisse s’etablir correc-tement, le medium doit etre percu comme libre simultanement aussi bien au niveau del’emetteur que du recepteur. En conclusion, la bande passante d’un lien depend de la syn-chronisation des periodes de temps libre entre l’emetteur et le recepteur.

t

occupé

libre

occupé

libre

Δ

δ

Fenêtres de communicationBande passante inutilisablepour le lien

Émetteur

Récepteur

Fig. 4.2 – Pire cas : desynchronisation totale entre emetteur et recepteur

Au niveau de la figure 4.2, les periodes de temps libre des nœuds emetteur et recepteurson totalement desynchronisees. Lorsque le medium est libre au niveau du recepteur, alorsil est percu comme occupe au niveau de l’emetteur et vice-versa. Comme consequence, labande passante residuelle du lien (s, r) est donc nulle, tandis qu’on obtient l’egalite B(s,r) =min (Bs, Br) dans le meilleur des cas comme represente au niveau de la figure 4.3.

37


t

Émetteur

occupé

libre

Δ

δ


occupé

libre

Récepteur

Fig. 4.3 – Meilleur cas : synchronisation totale entre emetteur et recepteur

Dans un reseau ad hoc, la gestion des communications n’etant pas centralisee, il est peutprobable que les communications soient synchronisees. Dans le cas general, il est necessaired’estimer la probabilite de recouvrement des periodes d’inactivite du medium pour pouvoiren deduire la bande passante residuelle du lien (s, r).

t

occupé

libre

occupé

libre

Δ

δ


Émetteur

Récepteur

Fig. 4.4 – Cas general : synchronisation partielle entre emetteur et recepteur

Pour qu’une communication puisse s’etablir le medium radio doit etre libre au moinspendant la duree d’un DIFS, pour que l’emetteur puisse acceder au canal. Le medium doitetre libre le temps de transmettre l’integralite du paquet de donnee (TDATA), plus la receptionde l’acquittement correspondant.

Si l’on considere une distribution uniforme de l’occupation du medium durant la periodede mesure ∆, il est possible de calculer la duree E(l(r,s)) avant que les nœuds s et r ne soientsynchronises et par consequent, avant que la communication ne puisse s’etablir. Connaissantτs, τr et τm, nous notons par p(i, j, k) la probabilite que :

– la premiere synchronisation arrive a l’unite de temps i

38


– le medium autour de l’emetteur est reste libre pendant j unites de temps avant lasynchronisation

– le medium autour du recepteur est reste libre pendant k unites de temps avant lasynchronisation

Ainsi, p(i, j, k) =

(ij

).(

i−jk

).(

τm−i−1τs−j−1

).(

τm−i−1τr−k−1

)(τmτs

).(

τmτr

) .

A partir de cette expression, nous pouvons deduire la probabilite P(l(s,r) = i) que lapremiere synchronisation arrive a une unite de temps donnee en examinant toutes les valeurspossibles de j et k.

P(l(s,r) = i) =

min(τs−1,i−1)∑j=max(0,τs−(τm−i))

min(τr−1,i−1−j)∑k=max(0,τr−(τm−i))

p(i, j, k)

D’ou la valeur E(l(r,s)) avant que la premiere synchronisation ne s’etablisse :

E(l(s,r)) =

min(τm,2.τm−(τs+τr))∑i=0

i.P (l(s,r) = i)

La communication ne peut s’etablir que si le medium est physiquement libre au niveaudes emetteur et recepteur. L’exemple d’une telle situation est represente sur la figure 4.4.Toujours en considerant une distribution uniforme de l’occupation du medium, la bandepassante residuelle estimee du lien (s, r) peut etre evaluee par les formules suivantes :

P(b(s,r) = i) =(τsi ).(τm−τs

τr−i )

(τmτr

)

=⇒ b(s,r) = Cmax ×min(τs,τr)∑

i=0

i.P (b(s,r) = i)

b(s,r) = Cmax × τs × τr (4.1)

Il faut noter que cette estimation peut etre raffinee des lors que les nœuds extremitesd’un lien sont en mesure de determiner leur voisinage commun. En effet, si deux nœuds ontdes voisins communs qui emettent alors le medium va etre occupe en meme temps pour cesdeux nœuds et il n’y a plus independance des distributions des temps d’occupation de cesdeux nœuds. Lorsque cela est possible (i.e. lorsque nous sommes en mesure de determiner lesvoisins communs qui ont emis), nous prenons alors en compte la dependance des distributionsdans l’estimation.

39


Pour illustrer l’importance de l’estimation de la synchronisation des periodes de tempslibres entre l’emetteur et le recepteur, considerons le scenario de la figure 4.5. Les commu-nications sont representees par les fleches et les nœuds en zone de detection de porteusesont relies par des tirets. Les simulations realisees sous le simulateur NS-2 a 2 et 11Mb/s,impliquent des debits applicatifs reels de 1,6 et 5Mb/s.

Nous cherchons donc a evaluer la bande passante residuelle sur le lien (C, D), a partirde la synchronisation des periodes d’inactivite du medium entre ces nœuds C et D. Cettevaleur evolue en fonction du debit du lien (E, F ), le debit du lien (A, B) etant constant etutilisant 50% de la capacite du medium (i.e 800 kb/s a 2Mb/s et 2500 kb/s a 11Mb/s).

Fig. 4.5 – Estimation de la synchronisation du lien (C, D)

Les figures 4.6(a) et 4.6(b) representent la bande passante residuelle reelle du lien (C, D),mesuree en ajoutant un flux entre ces deux nœuds et en monitorant le debit effectif. Cettevaleur est comparee a la valeur de la bande passante residuelle estimee par le protocoleAAC decrit precedemment et par synchronisation. Le but ici est de voir l’apport de la syn-chronisation des periodes de silence entre l’emetteur et le recepteur sans se preoccuper descollision eventuelles. C’est pourquoi nous avons retenu AAC comme solution de comparai-son, car cette approche est basee sur une ecoute active du medium et considere la bandepassante residuelle du lien comme le minimum des bandes passantes residuelles des nœudsaux extremites.

La technique AAC ne considere aucune synchronisation entre l’emetteur et le recepteur.Par consequent elle surestime la bande passante residuelle reelle au niveau de ce lien. Avecnotre methode prenant en compte la synchronisation entre l’emetteur et le recepteur, cettesurestimation est plus faible qu’avec AAC, mais reste toujours presente. Nous pouvons doncconclure que la synchronisation des periodes de temps libres entre l’emetteur et le recepteurfavorise une estimation plus precise de la bande passante residuelle, principalement lorsquele medium est libre aux alentours du recepteur (entre 80 et 100% de periode d’inactiviteaux alentours du recepteur). Neanmoins, elle n’est pas suffisante a cause de la presence descollisions qui degradent le debit des communications. Nous devons donc mettre en place unmecanisme permettant de predire la proportion de collision au niveau du recepteur.

40


0

200

400

600

800

1000

0 20 40 60 80 100

Ban

de p

assa

nte

rési

duel

le d

u lie

n (C

,D)

(kb/

s)

Pourcentage d’occupation médium autour du récepteur D (%)

Bande passante résiduelle réelleBande passante résiduelle estimée par synchronisation

Bande passante résiduelle estimée par AAC

(a) Capacite de 2 Mb/s

0

500

1000

1500

2000

2500

3000

0 20 40 60 80 100

Ban

de p

assa

nte

rési

duel

le d

u lie

n (C

,D)

(kb/

s)


Bande passante résiduelle réelleBande passante résiduelle estimée par synchronisation

Bande passante résiduelle estimée par AAC

(b) Capacite de 11Mb/s

Fig. 4.6 – Bande passante residuelle du lien (C, D) obtenue par synchronisation

4.1.2.2 Prise en compte des collisions

Le phenomene des collisions degrade plus ou moins fortement le debit des communica-tions dans un reseau ad hoc. En presence de plusieurs flux emis par des sources differentesdans le reseau, les emissions peuvent entrer en collision, empechant du meme coup unereception correcte par les nœuds destinataires. Ainsi la seule connaissance de la distributiondes periodes de temps libre au niveau de l’emetteur et du recepteur n’est pas toujours suffi-sante pour prevoir une collision. En effet, lorsqu’un paquet est emis au niveau de la source,il est possible que le medium au niveau du nœud recepteur soit occupe ce qui va engendrerune collision au niveau de ce dernier. La presence de collision engendre des retransmissionsde paquets et augmente la taille de la fenetre de contention, ce qui tend a reduire la bandepassante residuelle.

Dans le scenario presente au niveau de la figure 3.2, des protocoles tels que BRuIT, CACPet AAC faussent l’evaluation de la bande passante residuelle sur le lien (A, B) car toutes cesmethodes ne prennent pas en compte les collisions qui surviennent au niveau du nœud B. Parconsequent, pour que l’estimation de la bande passante residuelle soit precise, nous devonsestimer une probabilite de collision au niveau du nœud recepteur.

Periodiquement, des paquets Hello sont envoyes en diffusion pour que les mobiles puissents’echanger les informations de bande passante et de voisinage. Ainsi nous pouvons estimersur ces messages Hello une probabilite de collision notee par pHello selon la formule :

pHello =Nombre de paquets Hello entres en collision

Nombre de paquets Hello que l’on devrait recevoir(4.2)

Pour estimer cette probabilite de collision, les messages Hello sont envoyesperiodiquement en mode diffusion par tous les nœuds a une frequence supposee connue.Ainsi, des qu’un mobile recoit un message Hello d’un de ses voisins, il peut en deduire lenombre de messages Hello qu’il devrait recevoir de ce voisin durant une periode de mesure.

41


Cette valeur correspond au denominateur ”Nombre de paquets Hello qu’on devrait recevoir”.Le numerateur correspond a cette derniere valeur moins le nombre de paquets Hello effec-tivement recus durant cette meme periode de mesure. Il est important de remarquer que laprobabilite de collision sur le lien (i, j), n’est pas forcement la meme que celle sur le lien (j, i).Ceci est principalement du aux interferences qui n’exercent pas ses effets de facon symetriqueet des collisions qui peuvent survenir aussi bien a l’emission qu’a la reception de donnees.

Une telle estimation n’est toujours pas assez precise. En effet, le nombre de paquets Hellorecus dans un intervalle de temps donne, peut etre influence aussi bien par une congestionque par des collisions. Cependant, il est interessant de noter que si l’emetteur n’emet pasun nombre important de paquets Hello, cela implique que le medium est charge dans sonvoisinage. Par consequent tous les liens associes a ce nœud n’auront pas une bande passanteresiduelle elevee et l’erreur sur la valeur de pHello n’aura pas un impact important sur l’esti-mation. De plus, cette erreur va generer une sous-estimation de la bande passante residuelle,ce qui est preferable (il est preferable de diminuer le nombre de flux QoS que de degrader ledebit des flux voisins) a une surestimation qui entraınerait une degradation des flux QoS.

Les paquets Hello ont une taille petite et constante. En consequence la probabilite decollision que l’on observe sur des paquets de donnees de plus grandes tailles ne sera pasidentique a la probabilite de collision sur ces paquets Hello. Pour resoudre ce probleme nousutilisons une interpolation a l’aide des polynomes de Lagrange dont le but est de trouver ununique polynome P (m) dependant de la taille m du paquet telle que :

p(m) = P (m)× pHello (4.3)

p(m) etant la probabilite de collision sur un paquet de taille m octets.

0

20

40

60

80

100

120

0 500 1000 1500 2000

Pro

babi

lité

de c

ollis

ion


Taille des paquets = 1000 octetsTaille des paquets = 500 octets Taille des paquets = 250 octets

Taille d’un paquet Hello

(a) Probabilite de collision en B, obtenue par simu-lation et pour differentes tailles de paquets

0

20

40

60

80

100

120

0 500 1000 1500 2000

Pro

babi

lité

de c

ollis

ion


Probabilité de collision obtenue par simulation pour m=1000 octetsProbabilité de collision obtenue par simulation pour m=500 octets

Probabilité de collision obtenue par estimation pour m=1000 octetsProbabilité de collision obtenue par estimation pour m=500 octets

(b) Probabilite de collision en B, obtenue par estima-tion et pour differentes tailles de paquets

Fig. 4.7 – Probabilite de collision au niveau du nœud B

Considerons le scenario de la figure 3.2. Nous estimons la probabilite de collision auniveau du nœud B en fonction du debit sur le lien (C, D). La figure 4.7(a) represente cette

42


probabilite de collision obtenue par simulation avec NS-2 pour differentes tailles de paquets,en presence de paquets Hello. A partir de ces mesures, nous pouvons deduire analytiquementle polynome d’interpolation correspondant a cette situation :

P (m) = −5, 65 · 10−9m3 + 11, 27 · 10−6m2 − 5, 58 · 10−3m + 2, 19.

La figure 4.7(b) represente la probabilite de collision estimee au niveau du nœud B, p(m),en utilisant le polynome d’interpolation P (m), pour differentes tailles de paquets. Cette figuremontre que la probabilite de collision estimee est une bonne approximation de la probabilitede collision obtenue par simulation pour des tailles de paquets de 1000 et 500 octets.

Afin d’obtenir une idee sur le degre de precision de l’interpolation, nous estimons l’erreurrelative commise par le biais de l’interpolation. Elle estime l’ecart separant la courbe de laprobabilite de collision obtenue par simulation de celle interpolee. L’erreur relative notee ε,est un vecteur ligne ou chaque composante εi represente l’erreur relative au point d’abscissexi :

ε = (ε1, ε2, . . . , εn) avec εi = |f(xi)−g(xi)f(xi)

| ∀i ∈ [1; n]

f(xi) et g(xi) etant respectivement les valeurs des probabilites de collision obtenues au pointd’abscisse xi par simulation et par interpolation.Nous pouvons aussi calculer l’erreur relative moyenne notee ε a l’aide de la formule ci-dessous :

ε =1

n

n∑i=1

∣∣∣∣f(xi)− g(xi)

f(xi)

∣∣∣∣Le tableau 4.1 represente l’erreur d’interpolation faite dans notre cas. Ainsi le vecteur

d’erreur obtenu en pourcentage est ε = (9, 3; 1, 5; 4, 7; 1) ce qui represente une erreur moyennede ε = 4% environ. Ceci demeure relativement faible et traduit de la precision de l’interpo-lation a l’aide des polynomes de Lagrange.

(xi) 0 250 500 750 1000(g(xi)) 0 29 62 89 100(f(xi)) 0 32 63 85 99εi (%) - 9,3 1,5 4,7 1

Tab. 4.1 – Erreur relative due a l’ interpolation

Afin de s’interesser a la precision de cette probabilite de collision interpolee dans d’autresconfigurations, nous generons une topologie aleatoire de dix nœuds et cinq flux CBR (sources,destinations et debits aleatoires). Les paquets de donnees ont une taille de 1000 octets. Unlien specifique entre les nœuds 0 et 1 est place au centre de la topologie. Sur ce lien, nousestimons trois parametres :

– La probabilite de collision sans le mecanisme d’interpolation : pHello.

43


0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

0 5 10 15 20 25 30 35 40 45 50

Pro

babi

lité

de c

ollis

ion

Date de la simulation (s)

Probabilité de collision sans interpolationProbabilité de collision avec interpolation

Probabilité de collision réelle

Fig. 4.8 – Precision de la probabilite de collision interpolee sur un scenario aleatoire

– La probabilite de collision lorsque le mecanisme d’interpolation est active et pour despaquets de taille m =1000 octets : pm.

– La probabilite de collision reelle, obtenue de maniere offline en analysant les traces dela simulation.

La figure 4.8 represente l’evolution temporelle des trois probabilites de collision decritesprecedemment. Comme nous pouvons le constater, lorsque le mecanisme d’interpolationn’est pas active, il y a une sous estimation de la probabilite de collision reelle. Lorsque cemecanisme est active, la probabilite de collision obtenue par interpolation devient alors tresproche de la probabilite de collision reelle.

Il est important de noter que la probabilite de collision ne depend que de la taille despaquets envoyes par la source et de la distribution de l’occupation du medium au niveaudu recepteur. Nous avons donc presente une methode permettant d’evaluer la probabilite decollision qui combine deux approches :

– Une approche on-line permettant d’evaluer l’impact de la distribution de l’occupationdu medium au niveau du recepteur par le biais de la probabilite de collision sur lespaquets Hello.

– Une approche off-line qui prend en compte la taille des paquets envoyes par la sourcepar le biais d’une interpolation.

Dans la norme IEEE 802.11, a chaque collision la taille de la fenetre de contention aug-mente jusqu’a une valeur limite. Nous devons donc modeliser le backoff exponentiel pourraffiner davantage l’estimation de la bande passante residuelle.

44


4.1.2.3 Prise en compte du backoff

Lorsqu’un mobile subit une collision, il double la taille de sa fenetre de contention. Jusqu’apresent, nous n’avons considere que la proportion de bande passante consommee par lescollisions sans tenir compte du mecanisme du backoff de la norme IEEE 802.11. Dans leparagraphe precedent nous avons pu estimer la probabilite de collision au niveau d’un nœudrecepteur. Parallelement, nous devons egalement estimer la proportion de bande passanteperdue lors de la phase du backoff exponentiel.

Le temps passe dans la procedure du backoff exponentiel depend de la version du protocoleet du taux de collisions sur le lien. Ce temps ne depend pas de la taille du paquet. Parconsequent, ignorer l’influence du backoff pour des paquets de petites tailles, peut introduireune imprecision dans l’estimation de la bande passante residuelle.

Dans un premier temps, lorsqu’il n’y a pas de collision, le backoff suit une loi uniformedans l’intervalle [0 ;CWmin−1] et peut donc etre approxime par sa valeur moyenne CWmin−1

2.

Nous utiliserons les notations suivantes :– K represente la proportion de bande passante perdue a cause du backoff.– backoff est la valeur moyenne du backoff sans collision qui equivaut a CWmin−1

2.

– DIFS (SIFS resp.) est la duree d’un DIFS (SIFS resp.) defini par la norme IEEE802.11.

– T (m) est le delai separant l’emission de deux paquets consecutifs. Cette valeur dependdu debit d’emission et de la taille m du paquet.

La proportion de bande passante perdue a cause du backoff et notee K est donnee parla formule :

K =DIFS + backoff

T (m)(4.4)

On constate que la valeur de K diminue lorsque la taille des paquets augmente. Danscertains cas (avec des paquets de tres petites tailles), le fait de ne pas prendre en compte lavaleur de K peut entraıner une estimation imprecise de la bande passante residuelle.

En cas de collision, le mecanisme du backoff exponentiel est active. Apres chaque paquetayant subi une collision, la taille de la fenetre de backoff est doublee jusqu’a une valeurmaximale CWmax definie par la norme. Par consequent la valeur du backoff augmente au-dela de la valeur moyenne obtenue lorsqu’il n’y a pas de collision.

Considerons un lien radio pour lequel la probabilite de collision vaut p. La variable nrepresente le nombre de retransmissions associe a cette probabilite de collision p.Avec une probabilite equivalente a (1− p), la premiere transmission est reussie et le backoffmoyen est equivalent a CWmin−1

2.

Avec une probabilite p.(1 − p), le premier paquet subit une collision et le deuxieme paquetest transmis correctement en utilisant un backoff moyen equivalent a 2×

(CWmin−1

2

).

Apres C retransmissions sans succes, C dependant de la taille du paquet, la norme IEEE802.11 specifie que le paquet correspond doit etre detruit.

Nous pouvons donc representer cette progression par une chaıne de Markov a tempsdiscret dont les etats representent le nombre de retransmissions et les transitions sont lesprobabilites de subir une nouvelle collision ou une emission avec succes (retour a l’etat ini-

45


Fig. 4.9 – Retransmissions d’un paquet ayant subit des collisions

tial) comme indique sur la figure 4.9.Soit X la variable aleatoire representant le nombre de retransmissions. Elle peut etre ex-primee a l’aide des probabilites suivantes :

P (X = k) =

pk · (1− p) si k ≤ Cpk si k = C + 10 si k ≥ C + 1

Les deux dernieres probabilites indiquent le fait que, comme specifie par la norme IEEE802.11, le nombre maximum de retransmissions est fixe a C. Au-dela de cette valeur limite,le paquet est detruit et le backoff est ramene dans l’intervalle initial [0 ;CWmin − 1].

Ainsi, pour un lien dont la probabilite de collision est p, le nombre moyen de retransmis-sions n associe a cette probabilite de collision est egal a l’esperance de la variable aleatoireX. D’ou :

n =+∞∑k=1

k · P (X = k) =C+1∑k=1

k · P (X = k)

n =C∑

k=1

k.pk(1− p) + (C + 1)p(C+1)

Le nombre de slots de backoff decrementes depuis le debut de la transmission est donc :

backoff =+∞∑k=1

P (X = k) · min(CWmax; 2k−1 · CWmin)− 1

2

Pour simplifier cette expression, supposons que CWmax = 2c · CWmin avec c ≤ C :

backoff =

(c∑

k=1

P (X = k) · 2k−1 · (CWmin − 1)

2

)+

(C∑

k=c+1

P (X = k) · (CWmax − 1)

2

)

46


backoff =(c∑

k=1

pk−1 · (1− p) · 2k−1 · (CWmin − 1)

2

)+

(C∑

k=c+1

pk−1 · (1− p) · (CWmax − 1)

2

)

=⇒ backoff =1− p

2·(

1− (2p)c

1− 2p· CWmin +

pc − pC

1− p

)Dans cette evaluation, nous considerons la probabilite de collision independante du debit

d’emission du nœud emetteur. Cette approximation est juste dans la plupart des cas. Eneffet, la probabilite de collision reflete le fait qu’un paquet, une fois emis, subit une collisionparce que le medium dans le voisinage du recepteur est occupe par d’autres transmissions.Ainsi l’instant d’emission du paquet par l’emetteur influe tres peu sur cette probabilite decollision. Cependant, pour des topologies ou plusieurs emetteurs generent des transmissionsvers un recepteur commun, les collisions au niveau du recepteur vont entraıner une augmen-tation de la fenetre de contention de tous les nœuds ayant subi une collision et modifier lacharge autour du recepteur et par consequent la probabilite de collision. En fin de compte,dans notre approche, a chaque envoi periodique de paquet Hello, la probabilite de collision estrecalculee ce qui tend a ameliorer la precision de l’estimation de la bande passante residuelle.

Finalement, la proportion de bande passante perdue a cause du mecanisme du backoffen cas de collision est donnee par la formule :

K =DIFS + backoff

T (m)(4.5)

4.1.2.4 Formule d’evaluation de la bande passante residuelle

Les differents points abordes precedemment peuvent etre combines pour estimer la bandepassante residuelle d’un lien radio, i.e. entre un emetteur et un recepteur a portee radio. Lemecanisme d’estimation repose essentiellement sur la perception qu’ont les nœuds emetteuret recepteur de leur environnement. En conclusion, pour estimer la bande passante residuelled’un lien compose de deux nœuds s et r a portee de communication, trois parametres sontnecessaires :

– b(s,r) qui represente une estimation de la synchronisation des periodes de temps libreentre les nœuds source s et destinataire r a portee de communication et calculee al’aide de l’equation 4.1.

– La valeur K qui represente la proportion de bande passante perdue sous forme debackoff.

– La valeur pm qui represente la probabilite de collision sur des paquets de taille m octets.Pour estimer de maniere fine la bande passante residuelle sur le lien (s, r), il faut donc

retrancher les proportions de bande passante perdues par le backoff et les collisions.

47


D’ou la formule :

Efinal

(b(s,r)

)= (1−K) · (1− pm) · b(s,r) (4.6)

4.1.2.5 Comparaison avec QOLSR

Nous reprenons le scenario de la figure 4.5 et simulons QOLSR. Dans cette simulation,l’occupation du medium autour du nœud emetteur C est de 50% tandis qu’elle varie de 0 a100% autour du recepteur D. Le protocole QOLSR [45] propose une estimation de la bandepassante residuelle qui se base sur une evaluation de l’occupation du medium et une priseen compte des collisions par le biais des paquets Hello. Cependant, les auteurs ne precisentpas si cette occupation du medium correspond a l’occupation du medium du lien ou de l’unedes extremites. Nous allons donc considerer deux cas :

– L’occupation du medium correspond a celle autour du nœud recepteur, etiquetee par lacourbe ”Bande residuelle estimee par QOLSR sans synchronisation”. Par consequent,il n’y a aucune synchronisation prise en compte.

– L’occupation du medium consideree est celle du lien (C, D), impliquant une prise encompte de la synchronisation des periodes de temps libre entre C et D, comme nousvenons de le presenter1. La courbe correspondante est etiquetee par ”Bande passanteresiduelle estimee par QOLSR avec synchronisation”.

0

200

400

600

800

1000

1200

1400

1600

0 20 40 60 80 100

Ban

de p

assa

nte

rési

duel

le d

u lie

n (C

,D)

(kb/

s)


Bande passante résiduelle réelleBande passante résiduelle estimée par QOLSR avec synchronisationBande passante résiduelle estimée par QOLSR sans synchronisation

Bande passante résiduelle estimée par l’équation (4.6)

(a) Capacite 2 Mb/s

0

1000

2000

3000

4000

5000

0 20 40 60 80 100

Ban

de p

assa

nte

rési

duel

le d

u lie

n (C

,D)

(kb/

s)


Bande passante résiduelle réelleBande passante résiduelle estimée par QOLSR avec synchronisationBande passante résiduelle estimée par QOLSR sans synchronisation

Bande passante résiduelle estimée par l’équation (4.6)

(b) Capacite 11Mb/s

Fig. 4.10 – Influence de la synchronisation pour QOLSR

Les figures 4.10(a) et 4.10(b) representent la bande passante residuelle reelle obtenue parsimulation et celle estimee par QOLSR avec ou sans synchronisation a des debits respectifsde 2 et 11Mb/s.

Lorsqu’aucune synchronisation n’est prise en compte, la bande passante residuelle estimeepar QOLSR est largement superieure a la bande passante residuelle reelle. Par exemple pour

1Cette estimation n’est pas proposee dans QOLSR

48


une occupation medium de 20% autour de D, la bande passante residuelle reelle est de600 kb/s tandis qu’avec QOLSR sans synchronisation cette valeur passe a 1225 kb/s pourune capacite de 2Mb/s.

Lorsqu’une synchronisation est prise en compte, la bande passante residuelle estimee parQOLSR surestime toujours la bande passante residuelle reelle du lien (C, D). Toutefois, cettesurestimation est moins importante que dans le cas precedent car la charge autour du nœudemetteur est prise en compte dans l’evaluation.

De plus, l’estimation de la probabilite de collision proposee par le protocole QOLSR neprend pas en compte la taille des paquets. En effet, les paquets Hello etant plus petits queles paquets de donnees utilises au niveau de cette simulation, les probabilites de collision enD sont plus faibles et par consequent la bande passante residuelle reelle est une fois de plussurestimee.

Cette simulation montre qu’il est indispensable de considerer a la fois une synchronisationdes mobiles emetteur et recepteur et une prise en compte de la taille des paquets dansl’estimation de la probabilite de collision comme c’est le cas dans la methode d’estimationque nous proposons.

4.1.3 Estimation de la bande passante residuelle d’un lien :complements

Reprenons l’exemple de la figure 3.2 que nous representons une nouvelle fois dans lafigure 4.11. La methode proposee dans la section 4.1.2.3 permet de calculer la probabilite decollision au niveau du recepteur B en fonction du debit du Flux 2. Nous sommes donc enmesure d’evaluer la bande passante residuelle du lien (A, B).

Fig. 4.11 – Stations cachees

Considerons maintenant le probleme dans le sens inverse. La nouvelle question devient :quelle est la bande passante residuelle du lien (C, D), s’il existe un flux sur le lien (A, B) ?

49


Autrement dit, quelle est la proportion de collision que va creer une emission de C vers Dau niveau du recepteur B.

Cette estimation est cruciale car si un flux est emis sur le lien (A, B), nous devonsconnaıtre le debit maximum de transmission sur le lien (C, D) afin de ne pas degraderle flux entre A et B. Ceci revient a evaluer les collisions qui vont etre generees sur leflux existant s’il y a acheminement de ce nouveau flux. Il est donc necessaire d’estimerproprement la bande passante residuelle du lien (C, D) pour evaluer son impact sur le Flux 1.

Pour cela, nous mettons en place une simulation au niveau de laquelle le debit du Flux 1note par d1 est egal a la capacite du medium radio Dmax. Nous augmentons progressivementle debit du Flux 2 de 0 a Dmax. Cette augmentation va donc provoquer des collisions auniveau du recepteur B et degrader le debit du Flux 1.

En analysant les traces de la simulation, nous pouvons recuperer le debit effectif du Flux1 note par d1ef pour chaque valeur du debit du Flux 2. Ainsi, la degradation du debit du Flux1 de la valeur Dmax a la valeur d1ef est provoquee par les collisions en B dues aux emissionsde C vers D. Notons p cette probabilite de collision qui depend du debit du Flux 2, impactqui ne peut pas etre determine par la methode donnee dans la section 4.1.2.

Nous avons donc la relation :

d1ef = Dmax × (1− p) =⇒ p = 1− d1ef

Dmax

(4.7)

En pratique, la seule inconnue pour le nœud C est donc la variable d1ef . Cependant, tousles paquets emis de A vers B et qui n’ont pas subi de collision sont acquittes. A partir despaquets d’acquittements que C recoit, C est en mesure :

– de determiner s’il se trouve dans la situation de la figure 4.11 en recevant des acquit-tements dont le destinataire ne fait pas partie de son voisinage ;

– d’estimer le debit d1ef a partir de la frequence d’emission des acquittements associesa ce flux. En effet, la frequence d’emission des acquittements correspond a celle despaquets de donnees. En mesurant le nombre de paquets d’acquittement recus sur unintervalle de temps et en supposant une taille de paquet pour les donnees, d1ef peutalors etre estime. Ce n’est qu’une estimation car la taille des donnees envoyees par An’est pas connue de C2. Une solution aurait ete de modifier les paquets d’acquittementde 802.11 afin d’inclure cette information. Cependant, nous n’avons pas retenu cetteapproche qui necessite de modifier 802.11 ;

– d’en deduire la probabilite p pour calculer le debit avec lequel il pourra envoyer sesdonnees a D sans degrader le Flux 1 existant. Cette deduction se fait grace auxcourbes de la figure 4.7(a).

Cette approche necessite de pouvoir decoder correctement les paquets d’acquittements. SiC et B ne sont pas en zone de communication mais que l’emission de C provoque neanmoins

2La taille des donnees retenue est de 1000 octets comme nous le verrons dans la partie evaluation

50


des collisions en B, C ne sera pas en mesure de prendre en compte le Flux 1 dans sonevaluation.

Nous expliquons par la suite comment integrer les estimations des sections 4.1.2 et 4.1.3dans une version protocolaire.

4.2 Version protocolaire d’ABE

Pour mettre en place une version protocolaire de notre estimation de bande passanteresiduelle, tous les nœuds s’echangent periodiquement par le biais de paquet Hello, leurinformation de bande passante. Ainsi, toutes les ∆ secondes, un nœud estime localement sonoccupation du medium et inclut cette information dans un paquet Hello legerement modifie.La precision de l’estimation de la bande passante residuelle est conditionnee par le choixde la periode de mesure ∆. Plus la valeur de ∆ est grande, plus stables seront les mesures.Cependant, ∆ ne doit pas etre trop grand afin de pouvoir s’adapter a la mobilite des nœuds.Nous avons choisi ∆ = 1 s, i.e. une frequence deux fois plus elevee que dans OLSR.

Ainsi, un nœud r qui recoit un message Hello d’un nœud voisin s, peut estimer la bandepassante residuelle du lien (s, r) en utilisant l’equation 4.6 comme indique au niveau de lafigure 4.12. Il est important de remarquer que c’est toujours le nœud recepteur r qui estime labande passante residuelle du lien (s, r), afin de faciliter le controle d’admission et le processusde routage.

Fig. 4.12 – Fonctionnement du protocole ABE

51


La figure 4.12 resume le fonctionnement protocolaire d’ABE. On constate donc qu’unecommunication inter-couches plus communement appele cross layer facilite la conceptionprotocolaire d’ABE. En effet, les informations necessaires a l’estimation de la bande passanteresiduelle vont transiter entre les differentes couches du modele OSI et faciliter ainsi lecontrole d’admission. De facon plus generale, les auteurs de [48] ont montre que dans lesreseaux IEEE 802.11, il est indispensable qu’une communication entre les differentes couchesdu modele OSI s’etablisse afin de faciliter la gestion de la bande passante.

4.3 Controle d’admission dans ABE

Tout mecanisme visant a garantir un certain niveau de qualite de service pour un traficdonne repose sur un controle d’admission qui se doit d’etre le plus fiable possible. Dans lasection 4.1.2, nous nous sommes attaches a decrire une methode permettant d’estimer demaniere precise la bande passante residuelle d’un lien. Une estimation erronee de la bandepassante residuelle conduirait ineluctablement vers un controle d’admission fausse.

ABE combine une approche aussi bien reactive que proactive :– L’approche reactive concerne le mecanisme de routage QoS ou une route est cal-

culee lorsque l’application desire envoyer ses donnees. Le routage QoS que nous avonsimplemente constitue essentiellement une extension du protocole AODV. Nous avonsprivilegie l’approche reactive pour le routage car elle nous semble plus simple d’utilisa-tion qu’une approche proactive. De plus, le but recherche est de trouver des routes quisatisfont les contraintes demandees par les applications et non les routes optimales enterme de bande passante disponible comme le ferait un protocole de routage proactif.

– L’approche proactive concerne l’estimation distribuee de la bande passante residuellede tous les liens du reseau, recalculee periodiquement a chaque reception d’un nouveaupaquet HELLO.

Nous cherchons a offrir des chemins pouvant garantir une certaine bande passante aux ap-plications. Ainsi plusieurs applications ayant la meme source et la meme destination pourrontemprunter des chemins differents en fonction de la disponibilite des ressources du reseau.

4.3.1 Decouverte de route

Nous utilisons les paquets de requete de route (RREQ) auxquels nous rajoutons l’in-formation de bande passante desiree par l’application. Pour pouvoir fournir de la QoS auprotocole AODV, des extensions sur les paquets de decouverte de route RREQ ont ete pro-posees dans [49].

Lorsque la source veut etablir une route pour un flux QoS, elle diffuse un paquet de RREQa ses voisins. Cet envoi est soumis a un premier controle d’admission qui indique si le debitdesire par l’application ne va pas degrader les flux existants et se trouvant en configuration destations cachees avec l’emetteur. Cette verification se fait grace a l’estimation donnee dans lasection 4.1.2. Pour eviter les cycles lors de la phase de routage, un numero de sequence unique

52


associe a l’adresse de l’emetteur, est affecte a chaque paquet emis. Lorsqu’une demandedupliquee est detectee, le paquet de RREQ correspondant est supprime.

(a) Recherche de route

(b) Reponse de route

Fig. 4.13 – Etablissement d’une route QoS

Chaque nœud intermediaire qui recoit la requete effectue deux controles d’admission.Le premier verifie si la bande passante demandee par l’application est inferieure a la bandepassante residuelle du lien par lequel le paquet de RREQ a ete recu. Cette verification permetde s’assurer que le flux a emettre ne sera pas degrade par les flux existants et que l’emissionde ce flux ne degradera pas les flux existants se trouvant dans les voisinages des mobiles auxextremites du lien (estimation donnee de la section ??. Une telle verification ne permet pas

53


de dire si l’emission du flux par ce nœud intermedaire degradera les flux existants se trouvanten configuration de stations cachees avec ce nœud. C’est pour cela qu’un deuxieme controled’admission fonction de l’estimation donnee dans la section 4.1.3 est effectue.

Si ces deux controles sont reussis, le mobile ajoute son adresse sur la route et renvoie lepaquet de RREQ ; sinon il le detruit. Lorsque le destinataire le recoit, il verifie aussi si soncontrole d’admission a reussi. Finalement, le destinataire renvoie a la source un paquetde reponse (RREP) en mode unicast par le chemin inverse pour s’assurer que la routereservee est toujours utilisable. Lorsque ce paquet revient au nœud source, alors les ressourcessont reservees et le nouveau flux QoS est envoye sur cette route comme indique sur lesfigures 4.13(a) et 4.13(b).

4.3.2 Maintenance de route

ABE detecte une route cassee en monitorant les paquets Hello. Lorsqu’un mobile ne recoitaucun message Hello pendant une certaine duree predeterminee, il renvoie un message deroute erreur (RERR) a la source qui va se charger de trouver une route de secours. Le memeprocessus est repete lorsqu’un mobile intermediaire se rend compte que les conditions dureseau ne lui permettent plus d’acheminer son flux QoS au debit desire. Une autre solutionpourrait etre de conserver localement pour tous les mobiles des routes de secours, afin de nepas informer la source a chaque fois qu’il se produit une cassure de route.

4.3.3 Contention intra flux

Lorsque l’emetteur et le recepteur sont a plus d’un saut radio, necessitant un routagemulti-saut, la propagation des paquets le long de cette meme route genere des interferencesau-dela de la zone de communication. Une transmission sans fil consomme de la bandepassante sur un ensemble de liens en aval, bloquant par la meme occasion l’acces au mediuma l’ensemble des nœuds se trouvant dans cette zone : c’est le phenomene de la contention intraflux. Par consequent, une simple comparaison entre le debit demande par l’application et labande passante residuelle sur le lien n’est pas suffisante. En effet, elle ne prend pas en comptele fait que le flux QoS sera route par des mobiles voisins, bloquant toutes les transmissionsdans un rayon superieur a la zone de communication du mobile. Afin d’accepter un nouveauflux dans le reseau sans degrader le debit des flux existants, le controle d’admission doit etreen mesure d’evaluer avec precision l’impact de l’introduction de ce nouveau flux sur tous lesnœuds dans le voisinage.

Dans [42], les auteurs calculent un parametre d’un meme flux appele le contention count(CC) a travers un chemin et qui caracterise le nombre de nœuds se trouvant dans la zonede detection de porteuse du mobile considere. La valeur du CC de chaque nœud est estimeen analysant la distribution de la puissance du signal. Cependant, l’inconvenient de cettemethode est que pour pouvoir estimer le CC de chaque nœud, il faut etre en mesure delocaliser tous les mobiles dans la zone de detection de porteuse ce qui n’est pas toujourspossible.

54


Les experimentations menees dans [50] montrent qu’avec 802.11b (pour un debit de2Mb/s), la zone de detection de porteuse est approximativement egale au double de lazone de communication. Sous cette hypothese, les auteurs de [51] demontrent aisement quela propagation d’un flux QoS le long d’un chemin, ne perturbe que les liens situes dans unrayon maximum de quatre sauts. En d’autres termes, reserver X kb/s de bande passante lelong d’une chemin a n sauts, revient a reserver (k ×X) kb/s avec k etant le minimum entren et 4.

4.4 Limitations du protocole ABE

Le protocole tel que decrit ci-dessus possede quelques limitations qui sont essentiellementliees a la precision de l’estimation de la bande passante residuelle. Il existe de nombreusessituations imprevisibles, liees a des topologies particulieres pouvant conduire a une estimationerronee de la bande passante residuelle. La mise en place d’un mecanisme extremementprecis, vehiculant toutes les informations necessaires pour apporter une precision tres fine al’estimation, necessiterait un volume d’informations trop couteux au detriment des donneeset n’est peut-etre pas toujours realisable. Plusieurs sources d’erreurs peuvent etre identifieesparmi lesquelles nous pouvons citer :

– Les mobiles qui ecoutent le support radio ne peuvent decoder les transmissions desmobiles qui se trouvent dans la zone de detection de porteuse. Dans ABE, l’identitedu nœud emetteur permet un calcul de la bande passante residuelle plus precis. L’im-possibilite d’exploiter cette information pour les emissions se trouvant dans la zonede detection de porteuse peut entraıner une estimation imprecise de la bande passanteresiduelle sur un lien dans le cas ou l’emetteur et le recepteur peuvent detecter en memetemps ces emissions. Toutefois, l’ecoute du support est preferable a la transmission despaquets Hello a deux sauts afin de decouvrir les mobiles se trouvant dans la zone dedetection de porteuse, car elle permet dans le pire des cas de quantifier l’occupationmedium de ces mobiles interferents.

– Les mobiles recepteurs estiment la probabilite de collision avec un emetteur se trouvantdans son voisinage, en comptabilisant le nombre de paquets Hello non recus. Il est clairque pour que cette probabilite converge vers une valeur significative, il faut que lesmesures s’effectuent sur un nombre de paquets Hello significatifs. Il faut donc decalerl’estimation de la bande passante residuelle, le temps de permettre aux mobiles dedecouvrir localement la topologie du reseau.

– Les collisions sur les paquets de RREQ empechent la decouverte de routes pouvantacheminer les donnees avec la qualite de service desiree. Cependant, cet inconvenientest propre a tous les protocoles de routage avec QoS.

– L’estimation de la section 4.1.3 repose sur une estimation de la taille des paquets dedonnees qui ne correspond pas necessairement a la taille relle de ces paquets.

Un controle d’admission errone peut se traduire par l’acceptation d’un flux qu’on ne pourrarouter ou bien le routage de ce flux va degrader considerablement tous les flux QoS en conten-

55


tion, pouvant meme generer une congestion dans le reseau. La mobilite est un autre facteurimportant a prendre en compte, engendrant des pertes de paquets et des retransmissions.

56

CHAPITRE

5 Evaluation des perfor-mances d’ABE

Nous presentons dans ce chapitre les performances de notre protocole de reservation debande passante ABE, dans un contexte ad hoc multi-saut. L’implementation a ete realiseesous le simulateur NS-21 sans modification de la couche MAC IEEE 802.11 fournie avec lesimulateur. Ce simulateur offre des outils et des structures hierarchiques afin de simuler etanalyser des configurations reseau en toute simplicite et efficacite.

Les simulations que nous avons realisees sont constituees dans un premier temps par destopologies simples dont le but est de s’assurer que le mecanisme de reservation des ressourcesest fiable. Nous avons par la suite evalue des scenarios plus complexes pour lesquels nousgenerons de maniere totalement aleatoire la position des nœuds, les connexions, le debitdes flux et la mobilite. Nous comparons egalement les performances d’ABE avec d’autresapproches passives decrites dans la section 3. Le but de ce travail n’est donc pas de mettreau point un nouveau protocole de routage, mais plus d’utiliser les techniques de routageproposees par les autres protocoles tout en comparant la precision des techniques mises aupoint pour evaluer la bande passante residuelle. Nous avons donc compare nos resultatsavec trois protocoles reactifs disponibles sur Internet2 : BRuIT, AAC et QoS-AODV. Unecomparaison avec QOLSR, protocole proactif, aurait ete interessante mais n’a pas ete realiseedans cette these. Il faut noter qu’une telle comparaison implique une evaluation plus complexeque le seul mecanisme d’estimation des ressources disponibles puisque le routage proactifintroduit un autre niveau de complexite.

5.1 Environnement de travail : le simulateur NS-2

NS ou Network Simulator (http ://www.isi.edu/nsnam/ns) est un simulateur aevenements discrets developpe dans un but de recherche. Il utilise le langage OTCL (ObjectTools Command Language) derive de TCL. Par l’intermediaire de ce dernier, l’utilisateurdecrit les conditions de la simulation et fixe la valeur de certains parametres : la position desnœuds, les caracteristiques des liens physiques, les protocoles utilises, les communicationsqui ont lieu, etc.La simulation doit d’abord etre saisie sous forme de fichier texte que NS va utiliser pour

1Network Simulator 22BRuIT :http://citi.insa-lyon.fr/∼iguerinl/QoS.html – QoS-AODV et AAC :http://www.ctr.

kcl.ac.uk/members/ronan/default.asp

57

http://citi.insa-lyon.fr/~iguerinl/QoS.html

http://www.ctr.kcl.ac.uk/members/ronan/default.asp

http://www.ctr.kcl.ac.uk/members/ronan/default.asp

CHAPITRE 5. EVALUATION DES PERFORMANCES D’ABE

produire un fichier trace contenant les evenements qui se sont deroules durant la simulation.Le langage C++ est utilise pour pouvoir definir les objets a utiliser. Les parametres d’unesimulation reseau sous NS sont les suivants : la topologie avec la creation des nœuds et desliens, les couches protocolaires a implementer et la structure des messages (Flux CBR, Data-gramme IP, Segments TCP). Par le biais de ce simulateur, nous avons evalue les performancesd’ABE.

5.2 Resultats de simulation

Le but de l’evaluation est de verifier que lorsque nous utilisons ABE, les flux QoS sontroutes de la source vers la destination sans subir de degradation au niveau de leur debit.Les flux dont on ne peut garantir la bande passante sont tout simplement rejetes par la phasede controle d’admission.

Les parametres pour les differentes simulations sont resumes au niveau du tableau 5.1.Le parametre taille de la grille est definie pour les topologies aleatoires.

Parametres Valeurs

Protocole de routage ABEProtocole MAC IEEE 802.11bIntervalle Hello 1 s

Taille des paquets 1000 octetsModele de propagation TwoRayGroundCapacite du medium 2 ou 11Mb/s

Zone de communication 250mZone de detection de porteuse 550m

Taille de la grille 1000m×1000mDuree des simulations Entre 50 et 100 secondes

Tab. 5.1 – Parametres generaux pour les simulations

5.2.1 Un premier scenario simple

Afin de valider le mecanisme de reservation, la premiere topologie presentee estconstituee de deux chaınes de six nœuds comme indique au niveau de la figure 5.1. Pourcette simulation, le mobile A souhaite envoyer a destination de B un flux audio a un debitconstant de 160Kb/s. Vingt secondes plus tard, le mobile C cherche a envoyer un autre fluxaudio de debit equivalent a destination de D. Plusieurs simulations de ce scenario ont eterealisees et les memes resultats ont ete obtenues.

Au niveau de la figure 5.2(a) lorsqu’aucun mecanisme de reservation des flux n’est mis enplace, la presence du second flux va engendrer un partage des ressources du reseau, ce qui

58


Fig. 5.1 – Un premier scenario simple

va se traduire par une instabilite des debits au niveau des deux flux. De plus, des paquets deRREQ vont etre perdus ce qui va engendrer des reconstructions frequentes de route. Dansnotre simulation, le mobile A va reconstruire sa route 10 fois tandis que C va la reconstruire9 fois.

En activant le mecanisme de reservation de flux par le biais du protocole ABE, les debitsobtenus sont representes au niveau de la figure 5.2(b). Le premier flux de A vers B effectueune requete de reservation qui est acceptee et emet son flux au debit de 160Kb/s sansdegradation. Lorsque le second flux emet une requete, celle-ci est rejetee car la bande passanteresiduelle est insuffisante. Aucune route n’est etablie entre les nœuds C et D qui ne pourrontenvoyer leurs donnees.Lorsqu’une requete est rejetee, le flux QoS ne peut acceder au medium. Il est envisageablede mettre en place des politiques de degradation afin de diminuer sensiblement le debit dupremier flux de telle sorte que les requetes des autres flux QoS puissent etre acceptees. L’ideesous-jacente serait de pouvoir developper un protocole avec QoS qui s’adapterait en fonctiondes conditions de l’environnement. Nous n’avons pas aborde cette approche dans cette these.

0

50

100

150

200

0 5 10 15 20 25 30 35 40 45 50

Déb

it (k

b/s)


AODV − flux1AODV − flux2

(a) AODV

0

50

100

150

200

0 5 10 15 20 25 30 35 40 45 50

Déb

it (k

b/s)


ABE − flux1ABE − flux2

(b) ABE

Fig. 5.2 – Debits obtenus par les deux flux concurrents avec AODV et ABE

59


5.2.2 Topologies aleatoires

Afin d’etre moins dependant des topologies pour lesquelles nous pouvons a l’avanceprevoir les cas pathologiques, nous avons teste notre protocole sur des scenarios aleatoires.Nous avons genere des topologies pour lesquelles les nœuds sont places aleatoirement. Lesdebits des flux ainsi que les connexions (choix du nœud source et du nœud destination)sont aussi choisis de maniere aleatoire. Pour chacun des protocoles evalues, nous simulons lememe scenario avec des graines aleatoires differentes et et les resultats presentes represententla moyenne de 30 simulations.

Communications a un saut radio : la premiere topologie etudiee est constituee de dixnœuds places aleatoirement dans un carre de 1000 m × 1000 m. La capacite du canal radioest de 2Mb/s. Cinq flux CBR sont demarres, pour chacun d’entre eux le mobile initiateurde la communication choisit aleatoirement un mobile voisin (a 1 saut radio) commedestinataire. Par consequent, il n’y a donc ni mecanisme de routage, ni prise en comptede la contention intra flux, le destinataire se trouvant directement dans le voisinage a unsaut radio de l’emetteur. La simulation dure 50 secondes, le demarrage de chaque flux QoSest espace de 5 secondes. Les debits de ces flux CBR sont representes au niveau du tableau 5.2.

Identite du flux Debit en kb/s

Flux 1 108Flux 2 452Flux 3 796Flux 4 585Flux 5 347

Tab. 5.2 – Debits des flux CBR

En effectuant aucun controle d’admission, l’utilisation du protocole AODV au niveau dela figure 5.3(a) engendre un partage du canal entre les differents flux, ce qui entraıne unecongestion du reseau.

Le protocole AAC surestime la valeur de la bande passante residuelle du flux 4. Parconsequent, des que ce flux est accepte, il degrade le debit des flux existants. Le cinquiemeflux qui est aussi accepte degrade son debit initial de 65% et celui des flux existants jusqu’a30% comme indique sur la figure 5.3(b).

Le protocole BRuIT (figure 5.3(c)) sous-estime la bande passante residuelle et seuls deuxflux sur cinq sont admis avec le debit desire.

Avec le protocole ABE, tous les flux excepte le quatrieme sont admis sans aucunedegradation du debit demande par les applications. Contrairement au protocole AAC, lecontrole d’admission du quatrieme flux a echoue et ce dernier a ete rejete.

Dans cette configuration, il est clair que les communications etant a 1 saut, l’estimationde la bande passante residuelle est relativement precise favorisant du meme coup desresultats adequats. Nous presentons par la suite un scenario pour lequel la source et la

60


0

200

400

600

800

1000

0 5 10 15 20 25 30 35 40 45 50

Déb

it (k

b/s)


AODV − flux1AODV − flux2AODV − flux3AODV − flux4AODV − flux5

(a) AODV

0

200

400

600

800

1000

0 5 10 15 20 25 30 35 40 45 50

Déb

it (k

b/s)


AAC − flux1AAC − flux2AAC − flux3AAC − flux4AAC − flux5

(b) AAC

0

200

400

600

800

1000

0 5 10 15 20 25 30 35 40 45 50

Déb

it (k

b/s)


BRuIT − flux1BRuIT − flux2BRuIT − flux3BRuIT − flux4BRuIT − flux5

(c) BRuIT

0

200

400

600

800

1000

0 5 10 15 20 25 30 35 40 45 50

Déb

it (k

b/s)


ABE − flux1ABE − flux2ABE − flux3ABE − flux4ABE − flux5

(d) ABE

Fig. 5.3 – Scenarios aleatoires - Debits obtenus avec AODV, AAC, BRuIT et ABE pour descommunications a un saut radio

61


destination ne sont pas voisins, necessitant la mise en place d’un routage des donnees.

Communications multi-sauts : pour cette deuxieme topologie aleatoire nous reprenons lesmemes caracteristiques que dans le scenario precedent avec quatre principales modifications :

– La source et la destination ne sont pas a portee radio, ce qui va necessiter le routagedes donnees et complexifier l’estimation de la bande passante residuelle notamment acause du phenomene de la contention intra-flux.

– La capacite du medium est fixee a 11Mb/s.– Nous augmentons la charge du reseau avec sept flux CBR et vingt nœuds dans le

reseau.– Les debits sont representes au niveau du tableau 5.3.


Flux 1 243Flux 2 124Flux 3 134Flux 4 485Flux 5 536Flux 6 892Flux 7 91

Tab. 5.3 – Debits des flux CBR

Au niveau de la figure 5.4(a), lorsqu’AODV est utilise, le reseau tend a etre dans un etatde congestion car aucun controle d’admission n’est effectue afin de limiter le debit des flux. Onobserve aussi de frequentes cassures de routes ce qui reduit tres fortement les performancesglobales du reseau.

Les figures 5.4(b) et 5.4(c) representent les debits obtenus respectivement avec AAC etQoS-AODV. Ces deux protocoles admettent plus de flux QoS qu’ils ne devraient ce quitend aussi vers une congestion du reseau. AAC ne prend pas en compte les collisions tandisque QoS-AODV ne prend ni en compte les collisions a la reception, ni le phenomene dela contention intra-flux. Par consequent, ces deux protocoles surestiment la bande passanteresiduelle. Ce qui se traduit par l’acceptation de flux QoS qui degrade automatiquement ledebit des flux existants. Ce scenario met donc en relief l’importance crucial de la prise encompte des collisions et de la contention intra-flux pour une bonne estimation de la bandepassante residuelle.

Sur la figure 5.4(e), ABE effectue un controle d’admission plus fin qu’avec AAC et AODV,car seuls trois flux sur sept ont pu trouver une route au debit desire. Ce scenario montreque notre estimation de la bande passante residuelle ne surestime pas la bande passanteresiduelle.

Finalement, lorsqu’on utilise BRuIT (figure 5.4(d)), seul un flux sur sept est admis, ce quiimplique que BRuIT sous-estime la bande passante residuelle. La raison est principalement

62


due au fait que BRuIT ne prend pas en compte la synchronisation possible de flux distants.

La figure 5.5 represente la quantite de trafic agrege a travers tout le reseau en fonctiondu protocole de QoS utilise sur cette deuxieme topologie aleatoire generee. Ainsi lorsqu’ABEest utilise, les chemins choisis garantissent la bande passante desiree par l’application et lestaux de perte sont relativement faibles favorisant un debit agrege plus eleve par rapportaux autres protocoles de QoS (voir tableau 5.4 pour les taux de perte). Il faut aussi noterque le routage au mieux du protocole AODV permet d’explorer un grand nombre de routes.La quantite de trafic convoyee par AODV peut donc etre plus importante que celle desautres protocoles de QoS pour lesquels, lorsqu’un flux n’est pas admis, il n’y a aucun traficde donnees qui est envoye sur le reseau. Toutefois, l’exploration d’un plus grand nombre deroutes par AODV genere plus d’interferences et de collisions d’ou un taux de perte globaldans le reseau de l’ordre de 58,4%.

Protocoles Taux de perte (en %)

AODV 58,4AAC 38,3

QoS-AODV 45,8BRuIT 2,6ABE 5,8

Tab. 5.4 – Taux de perte global dans le reseau

Nous avons represente l’ensemble des chemins QoS reserves (apres reception d’un paquetde RREP et etablissement de la route) par les applications en fonction du protocole utiliseet pour les scenarios aleatoires definis ci-dessus. On constate qu’avec AODV (figure 5.6(a))beaucoup de routes sont creees provoquant une congestion du reseau. Avec le protocoleABE, seuls trois routes ont ete reservees pour les flux QoS (figure 5.6(c)) ayant reussileur controle d’admission alors que la sous-estimation faite par le protocole BRuIT, ne luipermet de trouver qu’une seule route QoS comme indique au niveau de la figure 5.6(d).Le protocole AAC, qui surestime la bande passante residuelle va emprunter un plus grandnombre de routes par rapport a BRuIT et ABE. Cependant ce nombre de routes creeesest beaucoup plus faible que celui d’AODV, la phase de controle d’admission reduisant laprobabilite de trouver des nouvelles routes (figure 5.6(b)).

Influence de la mobilite : il est difficile de fournir de la qualite de service en cas demobilite des nœuds. Ainsi des violations frequentes de la QoS apparaissent dues a la mobilitedes nœuds, aux cassures de routes ou a des chutes de debit des flux QoS. Par consequent ilest rarement possible d’acheminer un flux de bout en bout avec le debit desire sans aucunedegradation dans un environnement mobile. Avec ABE, des qu’une des situations precitees

63


0

100

200

300

400

500

600

0 5 10 15 20 25 30 35 40 45 50

Déb

it en

(kb

/s)

Date de la simulation

AODV − flux1AODV − flux2AODV − flux3AODV − flux4AODV − flux5AODV − flux6AODV − flux7

(a) AODV

0

100

200

300

400

500

600

0 5 10 15 20 25 30 35 40 45 50

Déb

it (k

b/s)


AAC − flux1AAC − flux2AAC − flux3AAC − flux4AAC − flux5AAC − flux6AAC − flux7

(b) AAC

0

100

200

300

400

500

600

0 5 10 15 20 25 30 35 40 45 50

Déb

it (k

b/s)


QoS−AODV − flux1QoS−AODV − flux2QoS−AODV − flux3QoS−AODV − flux4QoS−AODV − flux5QoS−AODV − flux6QoS−AODV − flux7

(c) QoS-AODV

0

100

200

300

400

500

600

0 5 10 15 20 25 30 35 40 45 50

Déb

it (k

b/s)


BRuIT − flux1BRuIT − flux2BRuIT − flux3BRuIT − flux4BRuIT − flux5BRuIT − flux6BRuIT − flux7

(d) BRuIT

0

100

200

300

400

500

600

0 5 10 15 20 25 30 35 40 45 50

Déb

it en

(kb

/s)


ABE − flux1ABE − flux2ABE − flux3ABE − flux4ABE − flux5ABE − flux6ABE − flux7

(e) ABE

Fig. 5.4 – Scenarios aleatoires - Debits obtenus avec AODV, AAC, QoS AODV, BRuIT etABE pour des communications multi-sauts

64


0

500

1000

1500

2000

2500

ABE AODV QoS−AODV AAC BRuIT

Qua

ntité

de

donn

ées

reçu

es e

n M

o

Protocoles de QoS

2131 Mo2037 Mo

1986 Mo

1860 Mo

1340 Mo

Fig. 5.5 – Quantite de trafic agrege en Mo a travers le reseau

apparaıt, un message d’erreur est envoye a la source, qui reconstruit sa route. La phase dereconstruction peut etre plus ou moins longue et generera un surplus de messages de controle.

Pour evaluer les effets de la mobilite sur les flux QoS, nous avons mis en place un scenarioconstitue de 10 nœuds places aleatoirement et cinq flux CBR de debit aleatoire (voir ta-bleau 5.5) et dont les dates d’emission sont espacees de 2 secondes. La simulation dure 100 s.Le modele de mobilite est le Random Way Point avec une vitesse maximale de 20m/s et destemps de pause de 10 s.


Flux 1 627Flux 2 72Flux 3 80Flux 4 470Flux 5 493

Tab. 5.5 – Debits des flux CBR en cas de mobilite

Le modele de mobilite Random Way Point (RWP) [52] est caracterise par une vitessemaximale Vmax et un temps de pause Tp. Un nœud se dirige vers un point choisi aleatoirementavec une vitesse constante comprise entre 0 et Vmax. Lorsque le nœud arrive a ce point, ils’arrete pendant une duree Tp avant de recommencer les memes mouvements en choisissantun autre point.

65


(a) AODV (b) AAC

(c) ABE (d) BRuIT

Fig. 5.6 – Graphe des chemins reserves pour les flux QoS

66


0

200

400

600

800

1000

0 20 40 60 80 100

Déb

it en

(kb

/s)


AODV − flux1AODV − flux2AODV − flux3AODV − flux4AODV − flux5

(a) AODV

0

200

400

600

800

1000

0 20 40 60 80 100

Déb

it en

(kb

/s)


AAC − flux1AAC − flux2AAC − flux3AAC − flux4AAC − flux5

(b) AAC

0

200

400

600

800

1000

0 20 40 60 80 100

Déb

it en

(kb

/s)


ABE − flux1ABE − flux2ABE − flux3ABE − flux4ABE − flux5

(c) ABE

0

200

400

600

800

1000

0 20 40 60 80 100

Déb

it (k

b/s)


BRuIT − flux1BRuIT − flux2BRuIT − flux3BRuIT − flux4BRuIT − flux5

(d) BRuIT

Fig. 5.7 – Debits obtenus avec AODV, AAC, ABE et BRuIT en cas de mobilite

67


Les figures 5.7(a) et 5.7(b) montrent qu’en cas de mobilite aussi bien AODV qu’AACgenerent une congestion du reseau et des degradations des flux QoS. Avec BRuIT (fi-gure 5.7(d)), la sous-estimation est toujours presente et seuls deux flux QoS ont trouve uneroute. De plus, BRuIT n’a pas pu reconstruire les routes des flux 4 et 5 tandis qu’ABE(figure 5.7(c)) a pu acheminer trois flux QoS au debit desire tout en reconstruisant au boutde 5 secondes la route du flux 4 a la date T = 40 s. L’introduction des temps de pause parle modele Randow Way Point permet aux mobiles de reconstruire leur route. Ainsi memeen cas de mobilite, le debit des flux QoS n’est pas degrade, mais la transmission est decalee,le temps de reconstruire des routes intermediaires pouvant garantir le debit requis.

Protocoles Quantite de trafic agrege (en Mo) Taux de perte (en %)

AODV 7760 42AAC 6321 27

BRuIT 3817 3,2ABE 7544 4,3

Tab. 5.6 – Quantite de trafic agrege et taux de perte en cas de mobilite

Les resultats au niveau du tableau 5.6 montrent que le protocole BRuIT possede le tauxde perte le plus faible (3,2%) car le nombre de paquets envoyes sur le reseau est faible acause de la sous-estimation de la bande passante residuelle qui reduit le nombre de flux QoSachemines. Toutefois, l’inconvenient principal est que le protocole BRuIT achemine a peine50% de la quantite de trafic agrege dans tout le reseau par rapport aux autres protocoles deQoS et a AODV. Le protocole ABE semble effectuer le meilleur compromis car il possedeun taux de perte relativement faible (4,3%), tout en acheminant une quantite de traficconsequente.

En resume, les resultats des simulations precedentes pour des topologies aleatoires, in-diquent un comportement similaire pour les protocoles AAC et QoS-AODV. En effet, cesdeux protocoles surestiment la bande passante residuelle ce qui provoque une degradation desflux existants. Le protocole BRuIT sous-estime cette bande passante residuelle, cependantcette sous-estimation est preferable car les flux QoS admis ne subissent pas de degradationde leur debit. Enfin, avec ABE une estimation plus fine permet par rapport a AAC de ne pasdegrader les flux voisins et par rapport a BRuIT d’accepter plus de flux QoS. Le mecanismede garantie des ressources dans un reseau ad hoc est tres fortement lie a la precision del’estimation de la bande passante residuelle ou des ressources disponibles en general, commrnoud pouvons le voir avec cette evaluation.

68


5.2.3 Evaluation du cout du mecanisme

L’etablissement et la maintenance des routes necessitent des echanges de messages(RREQ, RREP, RERR). Nous evaluons le surcout de notre protocole ABE en addition-nant le nombre total de tous ces messages a travers un reseau dont le nombre de nœudscroıt de 10 a 50 avec 10 flux CBR dont les debits sont distribues aleatoirement entre 10 et80 kb/s. Tous les resultats presentes ci-dessous sont la moyenne de 30 simulations pour unnombre de nœuds defini avec un intervalle de confiance a 95%.

0

5000

10000

15000

20000

25000

30000

35000

10 15 20 25 30 35 40 45 50

Nom

bre

tota

l de

mes

sage

s de

con

trôl

e

Nombre de noeuds

ABEAODV

AAC/QoS−AODV

Fig. 5.8 – Nombre total de messages de controle necessaires pour l’etablissement et la main-tenance des routes

La figure 5.8 represente le nombre total de messages de controle necessaires pourl’etablissement et la maintenance des routes en fonction du nombre de nœuds. AAC etQoS-AODV generent le meme nombre de messages de controle car ces deux protocoles sontbases sur un protocole de routage similaire avec seulement quelques differences. Nous n’avonspas presente les resultats pour le protocole BRuIT car il n’integre pas de mecanisme de re-construction de routes et donc les resultats ne sont pas comparables.

AAC et ABE generent moins de messages de controle qu’AODV car la phase de controled’admission elimine les routes ne possedant pas assez de bande passante residuelle pour routerles flux QoS. De plus, lorsque le reseau devient congestionne, AODV essaie de reconstruireses routes, ce qui augmente encore plus le nombre de messages de controle. Cependant,ABE genere moins de messages de controle qu’AAC, car AAC surestime la bande passanteresiduelle et explore donc un plus grand nombre de chemins durant la phase de decouvertede route.

69


5.2.4 Precision de l’evaluation

La precision de l’estimation de la bande passante residuelle et de la phase de controled’admission peuvent etre evaluees par le biais d’une nouvelle metrique. Cette metrique in-dique le nombre de flux corrects. Un flux correct est un flux QoS qui a ete admis et pourlequel on observe au maximum 5% de degradation du debit de bout en bout par rapport ala valeur desiree par l’application. Nous definissons donc cette metrique notee β par :

β =Nombre de flux corrects

Nombre total de flux dans le reseau

Le numerateur indique le nombre de flux corrects tel que definit precedemment tandisque le denominateur indique le nombre total de flux que l’on veut faire transiter dans lereseau. Cette metrique caracterise aussi bien une surestimation qu’une sous-estimation de labande passante residuelle. Dans le cas d’une surestimation, le controle d’admission accepteraun flux qui degradera automatiquement le debit des flux voisins et la valeur du numerateurdiminue. En cas de sous-estimation, le nombre de flux correct admis est faible par consequentla valeur de β egalement.

Nous avons procede a des simulations pour estimer la valeur de la metrique β. Le nombrede nœuds dans le reseau considere varie de 10 a 40 et sont positionnes aleatoirement. Cinqconnexions CBR sont etablies entre des nœuds source et destination choisis aleatoirement.Les debits sont distribues uniformement dans l’intervalle [0-500] Kb/s. Chaque simulationdure 100 secondes.

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

10 20 30 40

Val

eur

du p

aram

ètre

bet

a

Nombre de mobiles

ABEAAC

QoS−AODVBRuIT

(a) Zone de detection de porteuse = 2×Zone de com-munication

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

10 20 30 40

Val

eur

du p

aram

ètre

bet

a

Nombre de mobiles

ABEAAC

QoS−AODVBRuIT

(b) Zone de detection de porteuse = Zone de com-munication

Fig. 5.9 – Evaluation de la metrique β avec les protocoles AAC, QoS-AODV, BRuIT etABE

Influence de l’evaluation :La figure 5.9(a) represente la valeur moyenne de β en fonction du protocole de routage

70


QoS utilise avec un intervalle de confiance. Comme l’on pouvait s’y attendre, plus le reseaudevient dense, plus la valeur de β diminue car la bande passante residuelle des liens devientplus faible et moins de routes sont etablies.

Lorsque le reseau n’est pas dense (entre 10 et 20 nœuds), le taux d’acceptation β estplus faible pour les protocoles AAC et QoS-AODV par rapport a BRuIT et ABE. Ainsi cesdeux protocoles provoquent, en surestimant la bande passante residuelle, un depassementlocal de la capacite du medium qui degrade aussitot les flux voisins et diminue la valeur dela metrique β.

Cependant, lorsque le reseau est moyennement dense (entre 20 et 30 nœuds), le tauxd’acceptation de BRuIT diminue tres fortement car tres peu de chemins sont etablis a causede la sous-estimation de la bande passante residuelle.

Lorsque le reseau est tres dense (40 nœuds), le taux d’acceptation des flux QoS estpresque nul pour les protocoles AAC, QoS-AODV et BRuIT tandis qu’avec ABE il reste auxalentours de 8%. L’utilisation d’ABE permet dans tous les cas d’obtenir un taux d’accepta-tion des flux QoS plus eleve que celui des autres protocoles, meme lorsque le reseau est dense.

Influence de la taille de la zone de detection de porteuse :En rendant la zone de detection de porteuse egale a la zone de communication (figure ??),le taux de precision β des protocoles AAC, QoS-AODV et BRuIT diminue pour un memenombre de nœuds par rapport a la figure 5.9(a). En effet, reduire la zone de detection deporteuse revient a creer un plus grand nombre de scenarios de stations cachees. Or, lesprotocoles AAC, QoS-AODV et BRuIT ne prennent pas en compte ces types de scenariosdans leur evaluation de la bande passante residuelle, entraınant une degradation des fluxvoisins et une diminution du parametre β.

Avec ABE, les scenarios de stations cachees sont pris en compte dans l’evaluation(section 4.1.3) et par consequent aucune degradation des flux voisins n’est effectuee. Deplus, en reduisant la zone de detection de porteuse, tous les paquets envoyes par lesnœuds brouilleurs deviennent decodables. Ceci permet donc d’obtenir plus d’informationssur le reseau, comme par exemple les identites des voisins communs ou les identites desstations cachees. Cet apport d’informations permet d’augmenter le taux de precisionβ pour le protocole ABE. De tels resultats montrent que reduire la zone de detectionde porteuse a la zone de communication a un veritable interet des que l’on est en me-sure d’evaluer correctement les ressources du reseau et d’apporter un controle dans ce reseau.

Influence de la taille des paquets :Nous reprenons le scenario precedent avec la zone de detection de porteuse egale a la zone decommunication. Cette situation va donc creer un nombre plus important de configurationsde stations cachees. Dans la section 4.1.3, pour evaluer le debit des mobiles en stationscachees, la taille des paquets est une information necessaire. Cependant, dans les paquetsd’acquittement de 802.11, cette information n’est pas indiquee. Ainsi, considerer une taillede paquets fixes peut introduire des erreurs dans la precision de l’evaluation de la bandepassante disponible. Dans les simulations, nous avons pris comme hypothese une taille de

71


1000 octets. Lorsque des paquets de plus petites tailles sont envoyes, l’evaluation realisee auniveau des stations cachees conduit a une sous-estimation de la bande passante libre. Ceciimplique que nous accepterons peut-etre moins de flux QoS mais nous ne degraderons pasles flux existant si le nouveau flux QoS est accepte. En revanche, si la taille des paquetsest plus grande que 1000 octets, alors l’evaluation conduit a une surestimation de la bandepassante libre dans le cas des stations cachees. Nous nous proposons donc de quantifier cetteerreur au niveau de la precision de l’evaluation pour des tailles de paquets de 1000 (commeprecedemment) et de 1500 octets. Nous avons choisi une taille de 1500 octets, comme taillemaximale, car generalement, la couche IP des cartes sans fil croit avoir a faire a une carteEthernet et fragmente tous les paquets de taille superieurs a 1500 octets. Ce phenomene aete mis en relief dans [53]. Avec une taille maximale de 1500 octets, le debit des emetteurs enconfiguration de stations cachees est maximal et par consequent la bande passante residuelleest plus faible a travers le reseau.

Taille / Nombre de nœuds 10 20 30 40

1000 octets 42% 67% 38% 7%1500 octets 37% 61% 35% 5%

Tab. 5.7 – Valeur de β pour des tailles de paquets de 1000 et 1500 octets

La tableau 5.7 represente la valeur du parametre β pour des tailles de paquets de 1000et 1500 octets en fonction du nombre de nœuds presents dans le reseau. On remarque quelorsque la taille des paquets dans le reseau passe de 1000 a 1500 octets, la valeur du taux deprecision β diminue au maximum de 6%. Par exemple, pour 30 nœuds dans le reseau, β passede 38 a 35% lorsque la taille des paquets augmente de 1000 a 1500 octets. Ainsi, la differenceentre ces tailles de paquets influe peu sur la valeur du parametre β. L’approximation faitedans l’estimation de la bande passante des emetteurs en stations cachees avec un taille depaquets constante et egale 1000 octets dans les simulations introduit une erreur faible auniveau de β.

5.3 Synthese

Dans ce chapitre nous avons evalue les performances de notre protocole. ABE combine uneapproche reactive pour la recherche de route et une approche proactive pour l’estimation dela bande passante residuelle. Les informations de bande passante sont periodiquement misesa jour grace aux paquets Hello facilitant la phase de controle d’admission. Les simulationspresentees ont permis de valider les mecanismes d’ABE. Notamment, elles montrent que lesflux QoS sont routes vers leur destinataire avec le debit desire, sans subir de degradation ettout en reduisant globalement le taux de perte des paquets dans le reseau. De plus, memeen cas de mobilite, ABE est en mesure de garantir le debit des flux QoS par intervalles enreconstruisant des nouvelles routes pouvant garantir les conditions initialement requises parles couches applicatives. Comme tout mecanisme utilisant des paquets de controle, notre

72


protocole presente un cout en terme de trafic de controle qui reste cependant relativementfaible par rapport aux autre approches QoS.

L’apport du protocole ABE reside dans l’estimation de la bande passante residuelle desliens du reseau. Cette estimation peut aussi s’averer utile en presence de flux privilegies et aumieux comme nous allons le voir par la suite. Dans le chapitre suivant, nous reutilisons l’esti-mation de la bande passante residuelle d’ABE en y rajoutant quelques nouveaux mecanismesafin d’augmenter le taux d’acceptation des flux privilegies.

73

CHAPITRE

6 Co-existence de trafics pri-vilegies et Best Effort

L’absence d’une gestion centralisee des communications dans un contexte ad hoc renddifficile le partage des ressource entre flux de classes differentes. Dans un reseau ad hocmulti-saut, nous sommes generalement en presence de deux types d’applications : celles quiexigent des garanties en terme de delai ou de bande passante ou d’une metrique quelconquequi sont communement appeles flux QoS, et d’autres qui sont beaucoup plus tolerantes ala degradation de leurs ressources appelees applications Best Effort. Beaucoup de travauxse sont interesses a la garantie de ressources pour les applications QoS sans se soucier dela presence des flux Best Effort. Par exemple dans notre protocole ABE presente dans leschapitres precedents, on considere qu’il n’y a que des flux QoS. Que se passe-t-il si on autorisemaintenant l’emission de flux Best Effort ? Il faut alors etre en mesure de reguler le debit desflux Best Effort afin qu’ils ne degradent pas les flux QoS. Une solution serait de reserver unepartie fixe de la bande passante pour les flux Best Effort. Une telle approche est neanmoinspeu efficace si peu de flux QoS sont presents dans le reseau. L’ideal est de proposer unesolution dynamique ou les flux Best Effort pourraient augmenter leur debit lorsqu’il n’y apas ou peu de flux QoS. Mais il faut aussi etre en mesure de diminuer le debit des fluxBest Effort si de nouveaux flux QoS cherchent a etre emis. Ne pas pouvoir realiser ce pasarriere pourrait conduire rapidement a des configurations ou la majeure partie des ressourcesdisponibles serait occupee par des flux Best Effort et ou aucun nouveau flux QoS ne pourraitetre accepte.

La solution que nous proposons consiste a mettre en place un protocole distribue appeleDRBT pour Dynamic Regulation of Best Effort Traffic. L’idee principale de cette approcheconsiste a estimer de maniere differenciee la bande passante residuelle des liens afin de dimi-nuer si necessaire le debit des flux Best Effort. L’estimation de la bande passante residuelleutilise les mecanismes definis dans ABE en y rajoutant quelques extensions. Cette diminu-tion du debit des flux Best Effort permet d’augmenter le taux d’acceptation des flux QoSexistants ou a venir. Ainsi, les deux principaux objectifs a remplir sont les suivants :

– Diminuer si necessaire le debit des flux Best Effort afin de maximiser le taux d’accep-tation des flux QoS.

– Obtenir une utilisation efficace des liens radio, i.e. permettre aux flux Best Effortd’utiliser le maximum de bande passante lorsque cela est possible.

74

CHAPITRE 6. CO-EXISTENCE DE TRAFICS PRIVILEGIES ET BEST EFFORT

Dans ce chapitre, nous dressons dans un premier temps un etat de l’art sur les techniquesde regulation des flux Best Effort avant de presenter dans le detail le fonctionnement denotre solution et les resultats de simulations.

6.1 Etat de l’art

Pour garantir les debits des applications QoS, la plupart des approches se basent surune estimation de la bande passante libre afin de reguler le debit des applications. Lesmecanismes de regulation consistent generalement a accepter ou refuser les flux QoS ou/et aadapter le debit des flux Best Effort. Les approches etudiees precedemment (ABE, BRuIT,AAC, CACP, etc.) se concentrent essentiellement sur les flux QoS et ne s’interessent pas ala cohabitation entre flux QoS et Best Effort.

6.1.1 Approches existantes

Dans [54], une solution proposee consiste a separer les trafics en utilisant deux canauxde transmissions distincts. La difficulte de conception de cette technique est un obstaclemajeur et rend son utilisation peu probable surtout dans un contexte ad hoc.

SWAN [55] est un protocole distribue qui n’utilise aucun messages de controle pourgarantir dynamiquement la bande passante des flux QoS. Pour atteindre cet objectif SWANmet en place trois mecanismes. Un mecanisme de controle d’admission a la source des fluxQoS et deux mecanismes de regulation dynamique de trafic, l’un pour les flux QoS et l’autrepour les flux Best Effort.

Le controle d’admission a la source utilise une approche intrusive pour estimer la bandepassante residuelle. Avant chaque transmission d’un flux QoS, une sonde est envoyee de lasource vers la destination pour evaluer la bande passante residuelle le long de ce chemin.En fonction de cette valeur, le controle d’admission a la source decide de l’envoi ou non duflux QoS concerne. Il n’y a pas de routage car le chemin entre la source et la destination estsuppose connu.

Lorsque le protocole SWAN estime que le reseau est dans un etat de congestion, alors lesmecanismes de regulations sont declenches.

Le premier mecanisme de regulation dynamique de trafic QoS se base sur une approchepassive d’estimation de la bande passante residuelle. La modelisation de la DCF de 802.11faite par Bianchi permet d’estimer la bande passante residuelle sur un lien moyennant letaux d’utilisation du canal radio. Ainsi, lorsqu’une congestion est detectee, la source du fluxQoS est informee et diminue dans un premier temps le debit du flux QoS.

Le deuxieme mecanisme de regulation dynamique du trafic Best Effort se base sur uneautre methode d’estimation de la bande passante residuelle : le delai des paquets d’acquit-tements (ACK) sur un lien est mesure. Si ce delai est superieur a un seuil (dependant de labande passante desiree par les flux QoS [56]), alors le protocole SWAN considere le reseaudans un etat de congestion et par consequent diminue le debit des flux Best Effort.

75


L’estimation de la bande passante residuelle a l’aide d’une sonde envoyee de bout enbout consomme une part non negligeable de la bande passante comme presente dans lasection 3. Pour le premier mecanisme de regulation, la bande passante residuelle est obtenuea partir de la modelisation de la DCF de 802.11 faite par Bianchi. Cependant, les travauxde Bianchi ne sont applicables que dans une cellule ou tous les mobiles sont a portee decommunication et dans un environnement a saturation ce qui n’est pas toujours le cas.Par consequent, le protocole SWAN est tres imprecis dans l’evaluation de bande passanterestante sur un lien ce qui rend plus complexe la decision de reguler le debit des traficsBest Effort. De plus le protocole SWAN s’interesse aussi a la metrique delai. Cependant,determiner la valeur du delai desire pour les applications Best Effort est une tache difficile.

Le protocole QPART [57] se base sur une estimation passive de la bande passante et unmecanisme de regulation dynamique du debit des flux Best Effort. Il classifie les trafics avecqualite de service en fonction de deux metriques : le delai et la bande passante. Toutefois,nous nous interesserons ici qu’a la bande passante residuelle comme metrique, puisque c’estcelle que nous avons consideree dans cette section.

L’estimation de la bande passante restante effectuee dans QPART se base sur la theoriedes files d’attente et plus precisement sur le protocole RED [58]. L’algorithme RED demontreque pour maintenir un debit constant sur un chemin multi-saut, la taille des files d’attentesdoit etre maintenue en dessous d’un certain seuil predetermine. Si ce seuil est depasse alorsles mecanismes de regulation sont automatiquement demarres afin de resorber le surplus detrafic.

En cas de congestion, la taille de la fenetre de contention des flux QoS et Best Effortest mise a jour de maniere a rendre la transmission des flux QoS prioritaire. Parallelement,l’algorithme de QPART selectionne des flux susceptibles d’etre rejetes en se basant sur unepriorite des flux.

Cependant, QPART souffre des memes limitations que le protocole SWAN.Premierement, il se base sur un mecanisme d’estimation de la bande passante utilisedans les reseaux filaires et qui est inadapte dans un contexte ad hoc. En effet l’estimationutilisee dans QPART se base sur la theorie de file d’attente. L’algorithme RED utilisestipule que pour maintenir un debit constant sur un chemin multi-saut, on doit maintenirla taille des files d’attentes au niveau de chaque emetteur en dessous d’un seuil determine.Cependant, dans un contexte ad hoc sans fil, cette assertion n’est pas toujours verifiee.En effet, il existe de nombreuses topologies, notamment celle des stations cachees ou lesfiles d’attente des nœuds restent en dessous d’un seuil mais les collisions a la receptionengendrent des retransmissions frequentes. Deuxiemement, le mecanisme de regulationdynamique du trafic Best Effort dans le protocole QPART, consistant a faire varier la taillede la fenetre de contention, ne permet d’augmenter ou de diminuer le debit des ces flux BestEffort qu’en moyenne. Une variation de la taille de la fenetre de contention ne permet pasde predire avec precision quelle sera la variation la bande passante associee. Cela s’expliquesimplement par le fait qu’au niveau du protocole IEEE 802.11, la transmission sur le canalradio depend aussi bien de la taille de la fenetre de contention mais egalement de l’etat

76


du canal (occupe ou libre) et des collisions qui surviennent a la reception. C’est pourquoiQPART ne peut garantir avec precision la bande passante des flux QoS ni garantir uneutilisation au mieux du medium pour les flux Best Effort.

Le protocole presente dans [59] utilise egalement un mecanisme d’estimation de la bandepassante residuelle proche de celui utilise dans QPART en y apportant quelques modifica-tions. Il compare au niveau du premier saut d’un flux QoS (nœud appele H-Node), le nombrede paquets qu’il peut recevoir et transmettre avec le nombre de paquets effectivement recuset transmis. En fonction du resultat de cette comparaison, le protocole est en mesure deconclure si le flux QoS a ete degrade ou pas et declencher si necessaire une regulation dudebit des flux Best Effort. Durant le processus de regulation, un paquet appele SquelechPacket est envoye a partir du H-Node vers tous les nœuds de la zone de communication quifont transiter au moins un flux Best Effort. Ces nœuds sont appeles DRI. Tous les nœudsDRI qui interceptent un Squelech Packet arretent leur transmission pendant un intervalle detemps de 5 s. Les nœuds sources des flux Best Effort arretent egalement leur transmissiondurant un intervalle predetermine correspondant en moyenne au temps de transmission d’unflux QoS et seront reactives au-dela de ce delai d’attente.

Un tel protocole permet certes de garantir partiellement le debit des flux QoS, mais negarantit en aucune maniere une utilisation au mieux de la bande passante des flux BestEffort. En effet, aucune estimation de la bande passante restante n’est effectuee et seule uneestimation des debits des flux QoS est mise en place, grace a une supervision continue, desnœuds H-Node. Cette absence d’informations sur la bande passante restante des liens nepermet pas aux flux Best Effort de savoir exactement a quel debit ils devront re-emettre detelle sorte qu’ils puissent utiliser toute la bande passante restante sans pour autant degraderles flux QoS. L’utilisation de la bande passante restante n’est pas optimale car ce protocoleoblige un grand nombre de flux Best Effort a stopper leur transmission pendant un intervallede temps relativement eleve. En plus, les seuls nœuds H-Node consideres sont ceux quise trouvent dans la zone de communication. Cela implique que ce protocole ne prend encompte ni les flux Best Effort qui se trouvent dans la zone de detection de porteuse, ni ceuxqui degradent les flux QoS et qui sont eloignes a plus d’un saut. Enfin, ce protocole utilisedes paquets de controle supplementaires a diffuser sur le reseau (Squelech paquet). Aucunmecanisme de re-emission de ces paquets de controle en cas d’echec n’est prevu bien que l’onsoit dans un contexte ad hoc ou les collisions sont frequentes.

6.1.2 Synthese

D’apres les protocoles etudies ci-dessus, il apparaıt clairement que les mecanismes deregulation du debit des flux Best Effort doivent etre combines a une estimation tres precisede la bande passante residuelle, sous peine de ne pouvoir assurer des garanties strictes auxflux QoS.

Les protocoles tels que SWAN et QPART sont des protocoles de type passifs, ils neconservent localement aucunes informations sur l’etat du reseau. Une congestion est detecteelorsque des seuils predefinis sont depasses et la decision de reguler les flux Best Effort ne

77


s’effectue que dans ce cas precis. Le principal avantage de ce type d’approche est le passage al’echelle car aucune information n’est vehiculee a travers le reseau. Cependant, il est difficilede fixer au prealable des valeurs de seuils qui puissent s’adapter a toutes les topologies multi-sauts. Ainsi, il arrive tres souvent que les mecanismes de regulation soient actives alors quele reseau n’est pas congestionne ou dans le cas contraire qu’il ne soient pas actives en cas decongestion.

Dans la solution proposee, nous reutilisons l’estimation de la bande passante residuelledeja mise en place par le protocole ABE presente dans la section 4.1. L’avantage de ceprotocole est qu’il propose une estimation fiable de la bande passante residuelle comme nousl’avons vu precedemment. Ici, nous rajoutons une estimation differenciee de la bande passanteresiduelle en fonction du type de trafic (QoS ou Best Effort), ce qui permet d’instaurer unebonne cohabitation entre les flux QoS et les flux Best Effort.

6.2 Presentation du protocole DRBT

Dans cette section nous presentons en detail les mecanismes mis en place afin de regulersi necessaire et de maniere totalement distribuee le debit des flux Best Effort. Une telleapproche permet de maximiser le taux d’acceptation des flux QoS.

Nous presentons d’abord les differentes idees utilisees au niveau de la solution avant dedecrire l’estimation differenciee de la bande passante residuelle et le mecanisme de regulationdynamique du debit des flux Best Effort.

6.2.1 Idees utilisees dans DRBT

Les idees presentees dans cette partie representent plus des concepts a definir auprealable pour garantir la QoS dans un environnement ad hoc multi-saut en presence detrafic QoS et Best Effort.

Diminution du debit des flux Best Effort : il est parfois necessaire de diminuer ledebit des flux Best Effort pour pouvoir accepter plus de flux QoS. Cette reduction doit etrela meilleure possible : lorsque la bande passante disponible est importante, les flux BestEffort doivent pouvoir augmenter leur debit. La solution que nous avons retenue s’inspiredu protocole RED. Ainsi, la regulation du debit des flux Best Effort est engendree par unemodification de la taille de la file d’attente des mobiles. Nous pensons que les methodestelles que la variation de la taille de la fenetre de contention et du delai inter paquets,presentees dans QPART et SWAN, ne permettent pas d’avoir un controle fiable sur le debitdes flux.

Collaboration entre les nœuds : tous les protocoles garantissant de facon dynamiquela bande passante dans les reseaux ad hoc proposent un mecanisme de communication entreles nœuds. Ce mecanisme permet aux nœuds d’estimer la bande passante residuelle desliens et d’alerter les emetteurs des flux Best Effort si necessaire. Des paquets contenant des

78


informations necessaires a la regulation des debits des flux Best Effort vont donc transitera travers les nœuds du reseau. Cependant, pour que cette collaboration inter-nœuds soitefficace, il faut rajouter un mecanisme de collaboration inter-couches plus communementappele, cross-layer.

Communication inter-couches : la communication entre les couches est un des pointscles du protocole DRBT. Les informations etant disponibles a des niveaux differents de lapile protocolaire, les couches doivent par consequent collaborer entre elles pour exploiter cesdonnees. L’estimation de la bande passante residuelle est effectuee au niveau de la coucheMAC. Toutefois, la notion de flux n’est geree qu’au niveau reseau. Il y a donc une necessitede communiquer entre les couches MAC et IP. De plus, d’apres l’algorithme RED, reduirele debit des flux Best Effort necessite de controler la taille de la file d’attente des nœuds.Cette operation s’effectue au niveau de la couche LL. Enfin, le niveau applicatif specifie lescontraintes QoS desirees sur les flux. Tout ceci est resume au niveau de la figure 6.1.

Dans ce paragraphe et dans celui qui precede nous avons explique l’utilite de faire colla-borer les nœuds entre eux puis les couches entre elles. Pour realiser ces deux objectifs, nousutilisons des paquets de controle, sans pourtant rajouter un surplus de signalisation.

Fig. 6.1 – Communication inter-couches

Paquets de communication : utiliser de nouveaux paquets de controle consommeune part de la bande passante residuelle. Dans notre solution retenue, nous utilisons lespaquets de controle classiques que l’on retrouve generalement dans la plupart des protocoles

79


de routage : HELLO, RREQ et RREP. Ces paquets de controle, au-dela de la mise a jourdes informations de voisinage, serviront egalement a vehiculer les informations necessaires ala QoS que nous voulons mettre en place et qui viennent d’etre rapidement decrites.

6.2.2 Estimation de la bande passante residuelle

La premiere etape pour garantir le debit des flux QoS, consiste a estimer la bande passanteresiduelle sur l’ensemble de liens du reseau. Cette estimation va nous permettre de quantifierla proportion de bande passante libre pour les flux QoS, et qui est occupee par les flux BestEffort.

L’estimation doit etre distribuee et prendre en compte les differents phenomenes propresaux reseaux ad hoc (interferences, collisions, etc.). Ainsi, nous reutilisons l’estimation dela bande passante residuelle effectuee par le protocole ABE presente dans le chapitre 4,auquel nous rajoutons un nouveau mecanisme correspondant a la differenciation entreles paquets QoS et les paquets Best Effort.

Une differenciation entre les flux QoS et Best Effort doit permettre une meilleure utilisa-tion de la bande passante pour les flux QoS. Cette differenciation s’effectue au niveau MAC etconsiste a ne mesurer que l’occupation medium des paquets QoS durant la phase d’ecoute dusupport radio et a ne pas prendre en compte les flux Best Effort dans cette occupation. Ellen’est donc possible que si les mobiles peuvent decoder les informations sur les paquets. Eneffet, lorsqu’un paquet est transmis sur le medium radio, les nœuds qui ecoutent le supportne pourront identifier la nature du paquet (QoS ou Best Effort) en analysant les champs ToSde l’en-tete IP, que s’ils sont en mesure de decoder le paquet. Les paquets emis dans la zonede detection de porteuse ne peuvent etre decodes parce que la puissance du signal percue estfaible. En consequence, le protocole DRBT considere ces paquets comme des paquets QoS.En d’autres mots, les flux Best Effort se trouvant dans la zone de detection de porteuse sontconsideres comme des flux QoS dans l’evaluation de l’occupation du medium.

Considerons l’exemple de la figure 6.2 pour lequel tous les nœuds sont dans la meme zonede communication. La capacite est de 1600Kb/s. Un flux QoS de debit 500Kb/s et un autreflux Best Effort de debit 1000Kb/s sont transmis. Un troisieme flux QoS desire acceder aumedium avec un debit de 1000Kb/s. Si nous estimons la bande passante residuelle avec leprotocole ABE, cette valeur est presque nulle et le troisieme flux QoS ne peut etre transmis.Cependant, si nous effectuons une estimation differenciee de cette bande passante residuelle(qui ne prend en compte que les transmissions QoS) nous obtenons une bande passanteresiduelle de 1100Kb/s pour le troisieme flux QoS qui peut alors acceder au reseau. Parconsequent, le nouveau flux QoS pourra etre transmis sans degrader le premier flux QoS sile debit du flux Best Effort est diminue.

6.2.3 Regulation du debit des flux Best Effort

Comme explique precedemment, le controle d’admission de certains flux QoS peut echouercar une partie de la bande passante est consommee par des flux Best Effort. Par consequent,

80


Fig. 6.2 – Exemple de differenciation de flux

il necessaire de reguler leur debit en fonction de l’estimation de la bande passante residuellepresentee ci-dessus. Dans DRBT, cette regulation ne concerne que les flux Best Effort et sederoule en deux etapes :

1. Reduire le debit des flux Best Effort lorsqu’un nouveau flux QoS desire transmettre etne trouve pas assez de bande passante residuelle car une partie de celle-ci est occupeepar ces flux Best Effort.

2. Augmenter le debit de ces flux Best Effort lorsqu’un flux QoS libere de la bande pas-sante ou se deplace dans une autre zone de transmission.

6.2.3.1 Reduction du debit des flux Best Effort

Dans cette partie, nous expliquons la methode utilisee pour reduire le debit des fluxBest Effort si necessaire. Le protocole DRBT n’utilise que les paquets classiques tels que lesRREQ et RREP que l’on retrouve dans la plupart des protocoles de routage reactifs.

Ainsi, pour chaque nouvelle transmission d’un flux QoS, un paquet de RREQ est envoyeau prealable afin de reserver les ressources ainsi que le paquet de reponse RREP correspon-dant. Les informations stockees dans ces paquets sont :

– L’adresse du nœud emetteur.– L’adresse du nœud recepteur.– Un numero de sequence unique.– Le debit desire par le nouveau flux QoS (ThroughputQoS).– Le nombre total de flux Best Effort se trouvant dans le voisinage du flux QoS concerne

(nbBE). En effet, chaque flux Best Effort possede un identifiant unique propage atravers les paquets Hello. En consequence, chaque nœud peut estimer le nombre totalde flux Best Effort dans son voisinage et analysant ces identifiants.

81


– La bande passante residuelle differenciee (qui ne prend en compte que les transmissionsQoS et notee DiffBandwith). Si la bande passante residuelle differenciee indiquee parle paquet de RREQ est inferieure a la valeur stockee sur le lien par lequel le paquet deRREQ a ete recu, alors elle est mise a jour au niveau de ce paquet de RREQ.

La precision de notre protocole DRBT passe aussi bien par une estimation precise dela bande passante residuelle que par un processus de routage efficace. Nous utilisons unroutage reactif proche de celui d’AODV. La source d’un flux QoS envoie un paquet deRREQ a l’ensemble de ses voisins. Tout nœud recevant ce paquet de RREQ effectue unsimple controle d’admission en verifiant si la bande passante desiree et transportee parle paquet de RREQ est inferieure a la valeur de la bande passante residuelle differencieesur ce lien. Si c’est le cas, le nœud ajoute son adresse dans la route et retransmet cepaquet de RREQ. Ce processus continue jusqu’au nœud destinataire qui apres avoireffectue le dernier controle d’admission, envoie le paquet de RREP en unicast, par le chemininverse afin de reserver les ressources si le controle d’admission a ete positif sur tout le chemin.

A chaque reception d’un paquet de RREQ ou de RREP par un emetteur d’un flux BestEffort, ce dernier estime s’il y a assez de bande passante residuelle pour transporter ce fluxQoS sans degrader son debit. Si ce n’est pas le cas, il reduit son debit en envoyant un paquetappele DRP pour Dynamic Regulation Packet. Ce paquet, envoye depuis la couche IP versla couche LL du meme nœud, ne circule pas a travers le reseau. Les informations stockeesdans ce paquet DRP sont :

– La valeur de la bande passante desiree par le nouveau flux QoS (ThroughputQoS) etextraite du paquet de RREQ ou RREP.

– La valeur actuelle de debit du flux Best Effort (ThroughputBE).– Le nombre total de flux Best Effort rencontres le long du chemin (nbBE).– La valeur de la bande passante residuelle differenciee stockee le long du chemin dans

la variable DiffBandwith.– Un numero de sequence unique permettant d’identifier le paquet RREQ et RREP.Il est important de remarquer que seule la source du flux Best Effort est en mesure de

degrader son debit Pour des topologies ou la source du flux Best Effort n’est pas dans levoisinage du flux QoS qu’il gene, une solution aurait pu etre d’informer la source a l’aide denouveaux paquets de controle. Cependant nous n’avons pas retenu cette solution notammenta cause de la part non negligeable de ressources qu’elle consommerait.

Un exemple d’une telle situation est presente au niveau de la figure 6.3. Le nœud emetteurdu flux Best Effort D est en mesure de decoder le paquet de RREQ emis par A et de recupererla valeur de la bande passante desiree par cette transmission QoS (equivalente a X Kb/s).A la reception d’un tel paquet, le nœud D envoie un paquet DRP. Lorsque la couche LLreceptionne ce paquet DRP, elle enclenche le mecanisme de reduction du debit des flux BestEffort.

En pratique, deux files d’attentes virtuelles sont utilisees. La premiere sert a transporterles paquets QoS et la seconde les paquets Best Effort. Nous pouvons donc controler dy-

82


Fig. 6.3 – Reception d’un paquet RREQ

namiquement la taille de chacune des files. La figure 6.4 represente le schema general del’architecture d’un nœud DRBT.

Pour diminuer de maniere precise le debit du trafic Best Effort, nous reduisons la taille dela file Best Effort jusqu’a une valeur seuil. Cette valeur seuil, note Threshold varie a chaquereception d’un nouveau paquet DRP. Elle est obtenue grace a la formule :

Threshold =ThroughputBE

AvailableBandwidth(6.1)

avec :

AvailableBandwidth =DiffBandwidth− ThroughputQoS

nbBE(6.2)

L’equation 6.2 represente la nouvelle bande passante residuelle que l’on pourra allouerau flux Best Effort, si le nouveau flux QoS est accepte. D’apres l’equation 6.1, si la valeurdu seuil est superieure a un, alors le debit du trafic Best Effort doit etre diminue.

Une fois que le seuil est determine, la taille de la file d’attente sizeBE est donnee par laformule :

sizeBE =NbpacketsBE

Threshold(6.3)

La variable NbpacketsBE represente le nombre de paquets Best Effort entres dans lafile d’attente durant une periode de mesure d’une seconde. Nous avons choisi de fixer cette

83


Fig. 6.4 – Architecture interne d’un nœud DRBT

periode de temps a une seconde car au niveau du protocole ABE, les debits de l’ensembledes liens du reseau sont mis a jour toutes les secondes.

6.2.3.2 Augmentation du debit des flux Best Effort

Lorsqu’un flux QoS arrete sa transmission ou se deplace dans une autre zone de com-munication, tous les flux Best Effort ayant reduit leur debit, a cause de la presence de ceflux QoS, peuvent augmenter leur debit jusqu’a la valeur initiale. Cette augmentation per-met d’utiliser de maniere optimale et dynamique les ressources disponibles qui se liberentdans le reseau. Pour atteindre cet objectif nous reutilisons les paquets Hello. Chaque nœudtransportant un flux QoS stocke, dans ces paquets Hello, des informations sur l’identite dece flux et la valeur de la bande passante residuelle differenciee.

Quand un flux QoS arrete de transmettre ou libere de la bande passante, ce changementd’etat est indique au niveau des paquets Hello. L’emetteur du flux Best Effort qui se trouvedans le voisinage du flux QoS est en mesure d’intercepter ces paquets Hello indiquant qu’unflux QoS a libere de la bande passante. Finalement, le flux Best Effort peut augmenter sondebit en fonction de la nouvelle valeur de la bande passante disponible. En cas de mobilited’un ou des nœuds du flux QoS hors de leur ancienne zone de communication, les nœuds BestEffort ne recoivent plus de paquets Hello de ces derniers. En consequence, ils augmententleur debit jusqu’a la derniere valeur du debit qui avait ete conservee.

84


6.2.4 Synthese

Nous avons presente dans cette partie, DRBT un protocole de regulation dynamiquedu debit des flux Best Effort. Cette regulation se base sur une estimation differenciee dela bande passante residuelle prenant en compte le type des paquets (QoS ou Best Effort).En s’inspirant du protocole RED, la regulation du debit des flux Best Effort s’effectue enadaptant dynamiquement la taille de la file d’attente des nœuds emetteurs Best Effort.Comme nous allons le voir, contrairement aux methodes consistant a reduire la taille de lafenetre de contention, cette approche permet de mieux controler le debit des flux Best Effort.

6.3 Evaluation des performances de DRBT

Nous presentons dans ce chapitre les performances de notre protocole de regulation dy-namique du debit des flux Best Effort, DRBT. Nous nous placons dans un contexte ad hocmulti-saut. Nous avons utilise le simulateur NS-2 afin d’etudier les performances de notreapproche. Nous comparons les resultats obtenus avec trois autres protocoles :

– Le protocole au mieux AODV qui fournit un routage basique sans controle d’admission.– Le protocole ABE dont la comparaison va nous permettre de voir quel est l’apport

d’une differentiation de flux lorsqu’on regule le debit des communications Best Effort.– Le protocole QPART que nous avons implemente et qui servira de base pour la com-

paraison avec DRBT, puisque c’est un des rares protocoles de QoS qui s’interessent ala cohabitation des flux QoS et Best Effort.

La premiere topologie etudiee permet de comprendre le fonctionnement de base de notreprotocole, puis nous generons par la suite des scenarios aleatoires plus complexes.

6.3.1 Un premier scenario simple : les 2 paires

Ce premier scenario basique est constitue de deux paires de nœuds se trouvant dans lameme zone de communication. Il nous permet de valider le mecanisme de differenciation etde regulation des flux. Ainsi, a la date t = 1 s, le nœud A emet vers B un flux Best Effort dedebit 1000Kb/s. Quatre secondes plus tard, le mobile C cherche a envoyer un flux QoS dedebit equivalent a destination de D, comme indique sur la figure 6.5. A la date t = 30 s, leflux QoS s’arrete tandis que la simulation dure 50 s. La capacite du medium est de 2Mb/s.

Lorsque le protocole AODV est utilise, aucune differenciation des flux n’est etablie. Parconsequent l’introduction du second flux QoS va engendrer un partage des ressources avecle premier flux Best Effort introduit dans le reseau. A partir de la date t = 30 s, l’arret duflux QoS permet au flux Best Effort de retrouver son debit initial (figure 6.6(a)).

Lorsque le protocole ABE est active, le controle d’admission du flux QoS echoue car 70%de la bande passante est consommee par les emissions du flux Best Effort. Le flux QoS n’estdonc pas introduit dans le reseau et seul le flux Best Effort est emis comme indique sur lafigure 6.6(b).

L’apport du protocole DRBT au niveau de la figure 6.6(c) se deroule en deux grandesphases. Durant la premiere phase, de t = 5 s a t = 30 s, le debit du flux Best Effort est degrade

85


Fig. 6.5 – Les 2 paires

jusqu’a un debit d’environ 500Kb/s. Cette degradation permet au flux QoS d’emettre audebit desire de 1000Kb/s. Durant la seconde phase, lorsque le flux QoS est arrete (a partirde t = 30 s), le debit du flux Best Effort est retabli jusqu’a sa valeur initiale de 1000Kb/s.

Le protocole QPART, comme DRBT diminue le debit du flux Best Effort durant lapremiere phase correspondant a l’introduction du flux QoS, et reinitialise sa valeur a1000Kb/s lorsque le flux QoS arrete sa transmission. Cependant, par rapport a DRBT, onremarque au niveau de la figure 6.6(d), que la diminution du debit du flux Best Effort n’estpas assez importante. Cette situation engendre automatiquement une legere degradation dudebit du flux QoS qui peut parfois atteindre 800Kb/s au lieu des 1000Kb/s demande parl’application.

Le protocole QPART, qui ne conserve aucun etat du reseau, n’effectue aucune estimationde la bande passante residuelle. Ainsi, le debit du flux Best Effort est diminue, mais aucuneestimation ne permet de fixer sa valeur exacte. La consequence immediate est une legeredegradation du debit du flux QoS. Ce premier scenario montre que pour offrir aux flux QoSdes garanties, il peut etre utile d’estimer la proportion de bande passante maximale quipourra etre allouee aux flux Best Effort.

Il apparaıt clairement que la differenciation de flux permet au protocole DRBT, parrapport a ABE, de privilegier l’emission des flux QoS sur les flux Best Effort. Par rapport aQPART, l’estimation de la bande passante residuelle permet quant a elle de determiner avecprecision le debit maximum d’emission des flux Best Effort, afin d’eviter une degradationdes flux QoS.


L’evaluation des performances d’un protocole sur des topologies aleatoires per-met de mieux caracteriser le comportement du protocole dans des situations totale-

86


0

200

400

600

800

1000

1200

0 5 10 15 20 25 30 35 40 45 50

Déb

it (K

b/s)


AODV−flux1AODV−flux2

(a) AODV

0

200

400

600

800

1000

1200

0 5 10 15 20 25 30 35 40 45 50

Déb

it (K

b/s)


ABE−flux1ABE−flux2

(b) ABE

0

200

400

600

800

1000

1200

0 5 10 15 20 25 30 35 40 45 50

Déb

it (K

b/s)


DRBT−flux1DRBT−flux2

(c) DRBT

0

200

400

600

800

1000

1200

0 5 10 15 20 25 30 35 40 45 50

Déb

it (K

b/s)


QPART−flux1QPART−flux2

(d) QPART

Fig. 6.6 – Debits obtenus par les deux flux avec AODV, ABE, DRBT et QPART

87


ment imprevisibles. Ainsi, nous disposons aleatoirement 10 nœuds dans un carre de1000m× 1000m. Nous demarrons cinq connexions CBR, dont trois connexions de type BestEffort et deux connexions de type QoS. Le tableau 6.1 represente les debits desires par cha-cune des connexions. Pour chacune des ces transmissions, une source choisit aleatoirementune destination vers laquelle elle route ses informations. La destination peut ne pas etre dansla zone de communication de l’emetteur, necessitant dans ce cas un routage multi-saut. Ledemarrage des flux est espace de 5 s et la simulation dure 50 s.

0

100

200

300

400

500

600

700

0 5 10 15 20 25 30 35 40 45 50

Déb

it (K

b/s)


BE−flux1 (319 Kb/s)BE−flux2 (164 Kb/s)BE−flux3 (386 Kb/s)

QoS−flux4 (129 Kb/s)QoS−flux5 (281KB/s)

(a) AODV

0

100

200

300

400

500

600

700

0 5 10 15 20 25 30 35 40 45 50

Déb

it (K

b/s)




(b) ABE

0

100

200

300

400

500

600

700

0 5 10 15 20 25 30 35 40 45 50

Déb

it (K

b/s)




(c) DRBT

0

100

200

300

400

500

600

700

0 5 10 15 20 25 30 35 40 45 50

Déb

it (K

b/s)




(d) QPART

Fig. 6.7 – Debits obtenus avec AODV, ABE, DRBT et QPART

Au niveau de la figure 6.7(a), les resultats presentes montrent qu’avec le protocole AODV,un partage des ressources dans le reseau est effectue ce qui empeche les flux QoS d’atteindrele debit desire. Cette situation conduit rapidement a une congestion du reseau entraınantparallelement des cassures de routes et des reconstructions frequentes.

Avec le protocole ABE (figure 6.7(b)), les trois premiers flux Best Effort se partagent lesressources au niveau du medium radio. Par la suite, la phase de controle d’admission des

88


Flux Type Debit desire (Kb/s) Date d’emission (s)

CBR1 Best Effort 319 5CBR2 Best Effort 164 10CBR3 Best Effort 386 15CBR4 QoS 129 20CBR5 QoS 281 25

Tab. 6.1 – Debits desires et type de flux

deux flux QoS estime qu’il n’y a pas assez de bande passante pour pouvoir les acheminer audebit desire. Par consequent, seuls les trois flu

x Best Effort sont emis a travers le reseau. L’inconvenient du protocole ABE provient dufait qu’aucune differenciation n’est effectuee entre les flux Best Effort et QoS.

L’utilisation du protocole QPART au niveau de la figure 6.7(d) permet de diminuer ledebit des flux Best Effort. Cependant, le debit des flux QoS introduits n’est pas stable etsubit parfois des degradations. La cause principale est que la diminution du debit de fluxBest Effort n’est pas assez importante car aucune estimation des ressources disponibles n’estmise en place.

Avec le protocole DRBT, on estime la bande passante maximale a allouer au flux BestEffort, ce qui permet de garantir aux flux QoS une transmission stable sans degradation deleur debit comme indique au niveau de la figure 6.7(c).

Les deux scenarios presentes montrent qu’une estimation de la bande passante residuelleest efficace pour limiter correctement le debit des flux Best Effort. Beaucoup d’autresscenarios de ce type ont ete effectues et dans tous les cas, les conclusions sont identiques.

6.3.3 Taux d’acceptation des flux QoS

De par la nature des flux QoS, la fiabilite de leur transmission permet d’estimer laprecision des protocoles de qualite de service utilisees. La but de notre protocole DRBTest de reduire efficacement le debit des flux Best Effort afin d’augmenter le taux d’accepta-tion des flux QoS. Pour evaluer le taux d’acceptation de DRBT nous reutilisons la metriqueβ defini dans le chapitre 5. Ici nous avons :

β =Nombre de flux QoS admis correctement

Nombre total de flux QoS a emettre dans le reseau(6.4)

Un flux QoS admis correctement est un flux QoS n’ayant pas subi plus de 5% dedegradation de son debit lors de sa transmission. Cette situation implique donc que l’es-timation de la bande passante residuelle differenciee et la phase de controle d’admission sontfiables.

Cette metrique va nous permettre d’estimer la fiabilite de l’estimation differenciee de labande passante residuelle. En effet, une estimation erronee entraınerait irremediablementune degradation du debit des flux QoS et par consequent une diminution de la valeur de lavariable β.

89


Nous avons procede a des simulations pour estimer la valeur du parametre β. Le nombrede nœuds dans le reseau considere varie de 10 a 50 et sont positionnes aleatoirement. Dixconnexions CBR, dont cinq Best Effort et cinq QoS sont etablies entre des nœuds source etdestination choisis aleatoirement. Les debits sont distribues uniformement dans l’intervalle[0-200]Kb/s. Chaque simulation dure 100 secondes et les resultats presentes constituent lamoyenne de 30 simulations pour un nombre de nœuds defini.

0

10

20

30

40

50

60

70

80

90

10 20 30 40 50

Val

eur

du p

aram

ètre

bet

a

Nombre de mobiles

AODVABE

QPARTDRBT

(a) Zone de detection de porteuse = 2×Zone de com-munication

0

10

20

30

40

50

60

70

80

90

10 20 30 40 50

Val

eur

du p

aram

ètre

bet

a

Nombre de mobiles

AODVABE

QPARTDRBT

(b) Zone de detection de porteuse = Zone de com-munication

Fig. 6.8 – Taux d’acceptation des flux QoS avec les protocoles AODV, ABE, QPART etDRBT

Influence de l’evaluation :La figure 6.8(a) represente la valeur du parametre β en fonction du protocole utilise. Demaniere evidente, plus le reseau devient dense, plus le taux d’acceptation β des flux QoSdiminue car la bande passante residuelle des liens devient plus faible.

Lorsque le reseau est peu dense (entre 10 et 20 nœuds), le taux d’acceptation est relati-vement eleve pour notre protocole (70%) tandis que le protocole QPART achemine environ51% des flux QoS. Ainsi, les deux mecanismes de differenciation de flux et d’estimationdifferenciee de la bande passante residuelle permettent d’augmenter le taux d’acceptationdes flux QoS.

Cependant, lorsque le reseau est moyennement dense (entre 20 et 30 nœuds), le taux d’ac-ceptation des flux QoS de tous les protocoles commencent a diminuer. Toutefois le protocoleDRBT arrive encore a acheminer jusqu’a 61% des flux QoS presents.

Enfin, lorsque le reseau est tres dense (entre 40 et 50 nœuds), la bande passante residuelledes liens devenant tres faible, une diminution du debit des flux Best Effort est insuffisantepour garantir les ressources au flux QoS. Cependant avec DRBT, 10% des flux QoS sontencore achemines avec les conditions requises alors que les autres protocoles acheminentdans le meilleur des cas 3.5% de ces flux.

90


Influence de la taille de la zone de detection de porteuse :Lorsque la zone de detection de porteuse est egale a la zone de communication (voir fi-gure 6.8(b)), le taux d’acceptation des flux pour les protocoles QPART et ABE est legerementplus eleve qu’au niveau de la figure 6.8(a) pour un meme nombre de mobiles. En revanche,les protocoles QPART et AODV voient une diminution de la valeur de β.

En effet, reduire la zone de detection de porteuse permet de decoder un plus grand nombrede paquets emis dans le voisinage d’un nœud. Ceci facilite le mecanisme de differenciationdes paquets pour DRBT. L’inconvenient majeur de cette reduction est l’apparition d’unplus grand nombre de topologies de stations cachees, ce qui pose des problemes a QPARTet AODV qui ne savent pas gerer ces situations. Toutefois, cet inconvenient est negligeablepour DRBT et ABE car les estimations de la bande passante residuelle proposees dans cesprotocoles prennent en compte les phenomenes de stations cachees.

91

CHAPITRE

7 Estimation du delai moyen

Dans ce chapitre nous nous interessons a l’etude du delai de transmission dans un contextead hoc multi-saut afin de proposer un protocole de qualite de service base sur cette metrique.Le delai est un critere aussi important que la bande passante pour les applications multimediaqui necessitent des garanties pour ces deux metriques.

Dans ce chapitre, nous presentons DEAN (Delay Estimation in Ad hoc Networks) unprotocole de reservation de ressources base sur le delai moyen comme metrique. La metriquedelai designe le temps que met un paquet pour etre achemine d’une source vers une destina-tion. Contrairement a la bande passante, le delai est une metrique additive. Ainsi, le delaile long d’un chemin est egal a la somme des delais des liens qui constituent ce chemin. Cetemps prend en compte principalement deux etapes : le delai dans la file d’attente des nœudsle long du chemin et le delai de propagation du paquet sur le medium physique.

Pour ce travail, nous allons supposer que toutes les horloges des mobiles sont parfaitementsynchronisees. Cette hypothese permet d’avoir une evaluation correcte du delai. Il est clairque dans la realite, cette synchronisation peut etre difficile a obtenir dans un contexte adhoc. Ce probleme a neanmoins ete laisse de cote pour ce travail.

Nous proposons donc, apres avoir dresse un etat de l’art sur les techniques d’evaluationdu delai moyen, une modelisation permettant d’estimer ce delai moyen sur un chemin apartir des mecanismes mis en place dans ABE.

7.1 Etat de l’art sur les techniques d’evaluation du

delai

Les auteurs de [60] se sont interesses a la modelisation du delai de transmission a un sautradio a l’aide de chaınes de Markov a temps discret. Largement base sur la modelisationde la DCF de 802.11 faite par Bianchi dans [61], ils ont modelise dans un premier tempsla probabilite de collision et la probabilite de transmission en fonction de l’etat initial dusysteme. Dans un second temps, grace au calcul de ces probabilites, ils ont pu en deduire ladistribution moyenne du backoff et le temps de service associe en modelisant la file d’attentede l’emetteur par une file M/MMGI/1/K.

Cependant, les auteurs stipulent qu’une simple transformation permet d’etendre leursresultats a des reseaux multi-sauts, mais la problematique devient plus complexe car les

92

CHAPITRE 7. ESTIMATION DU DELAI MOYEN

hypotheses permettant d’estimer les probabilites de collision ne sont plus valables dansun environnement multi-saut, notamment a cause des interferences et du phenomene desstations cachees.

Dans [62], un mecanisme d’estimation du delai a 1 saut radio pour les reseaux ad hoc802.11 est presente. Ce mecanisme repose sur une estimation du taux d’occupation du canalradio. Le delai est par la suite pondere par ce taux d’occupation. Si l’on considere U commele taux d’occupation du canal et L comme le temps moyen de transmission d’un paquet surce canal alors le delai note d s’ecrit : d = U ×d

′+(1−U)×L. Lorsque U = 0 correspondant

a un canal libre, il n’y a pas de collision et le delai est egal au temps moyen de transmissiondu paquet. Lorsque le canal n’est pas libre (U 6= 0), alors les auteurs evaluent la valeurdu parametre d

′qui correspond au temps total des retransmissions incluant les differentes

valeurs de backoff choisies a chaque etage de backoff. Cependant, pour des configurations destations cachees, le canal peut etre percu comme libre par le nœud emetteur (U = 0) alorsque des collisions peuvent survenir a la reception.

Le principe de [63, 64] est de modeliser un nœud 802.11 par une file M/G/1/K afind’estimer le temps moyen de service d’un paquet dans la file d’attente des nœuds. Une foisce parametre determine, les auteurs utilisent une fonction generatrice du temps de serviceau niveau de la couche MAC qui depend de la taille du paquet, de la probabilite de collision,et de la taille de la fenetre de contention. Finalement on obtient le temps moyen de serviced’un nœud en estimant la moyenne des temps de service sur la longueur des paquets et leurprobabilite de collision.

Dans [65, 66] les auteurs estiment le delai d’un lien en calculant la difference de tempss’ecoulant entre la creation d’un paquet Hello et la reception de ce dernier par le destinataire.Cette approche semble assez simpliste car elle ne prend pas en compte la taille d’un paquetqui peut varier alors que les paquets Hello ont une taille constante. De plus ces paquetsHello n’etant pas acquittes car envoyes en broadcast, en cas de collision il n’y a pas dereemission, tandis que les paquets de donnees sont retransmis, ce qui tend a augmenter demaniere non negligeable le delai de transmission.

Dans [67] Tickoo et Sikdar, proposent un modele analytique base sur une file G/G/1afin d’estimer le delai d’un paquet. L’analyse en moyenne presentee dans cet article permetd’obtenir une expression du backoff moyen en fonction de la probabilite de collision. Pourun reseau de n stations, Bianchi donne une formule permettant d’estimer la probabilite decollision en fonction de n. A partir de cette formule les auteurs proposent une resolutionnumerique afin de determiner la valeur de la probabilite de collision. Le delai ou tempsde service du mobile est alors represente par le temps mis pour traverser la file d’attenteobtenue par la loi de Little et le temps s’ecoulant entre l’instant d’arrivee a la couche MACet l’instant ou le canal est libre. Cette derniere valeur n’est pas triviale et necessite demodeliser le nombre de slots de backoff que le mobile devra attendre entre deux emissions

93


reussies avant de pouvoir emettre sur le canal radio. Finalement on ajoute le temps depropagation sur la canal radio avec les eventuelles retransmissions en cas de collision. Uneetude analogue du delai, deduite a partir des probabilites de collision obtenues a l’aide dela modelisation de la DCF faite par Bianchi, est proposee dans [68].

7.2 Synthese

L’estimation du delai dans un contexte ad hoc multi-saut est un probleme complexe.Certaines approches considerent la metrique delai comme connue ou effectue simplementune difference entre l’instant de depart d’un paquet de decouverte de route et l’instantd’arrivee.

D’autres travaux plus pertinents, se basent sur une modelisation de la DCF de 802.11,largement inspiree du modele propose par Bianchi dans [61]. Cette modelisation permetd’estimer les probabilites du canal radio (probabilite d’acces, de collision, etc.). Par la suite,les auteurs peuvent en deduire une expression du delai de bout en bout. L’inconvenientprincipal est que les hypotheses effectuees au niveau de ces modeles sont appliquees a unecellule ou tous les mobiles sont a portee de communication. De maniere plus generale ceshypotheses sont :

– Le nombre n de stations en competition est connu par tous les mobiles et constant.– La probabilite de collision est constante.– Cette probabilite de collision est la meme pour tous les nœuds.– Les nœuds sont tous dans la meme zone de communication. Il n’y a donc pas de

phenomene de stations cachees, ni d’interferences. Les collisions ne proviennent que del’acces concurrentiel au medium radio.

– Le debit est a saturation, c’est-a-dire qu’il y a toujours un paquet a emettre dans lafile d’attente des nœuds.

L’approximation principale du modele de Bianchi est que la probabilite de collision estconstante et ne provient que de l’acces concurrentiel au medium radio, ce qui permet del’exprimer en fonction du nombre de stations en competition. Toutes ces hypotheses fonda-mentales permettent de simplifier les chaınes de Markov obtenues et de les resoudre, ce quisemble beaucoup plus difficile pour des reseaux multi-sauts.

Certaines informations, difficilement recuperables de maniere analytique, pourraient etreplus facilement obtenues via des mesures realisees dans un protocole. Nous proposons par lasuite, une methode afin d’estimer le delai de bout en bout dans un environnement ad hocmulti-saut tirant parti de certains mecanismes deja mis en place au niveau de notre protocoleABE (voir chapitre 4).

94


7.3 Estimation du delai moyen dans les reseaux ad hoc

7.3.1 Hypotheses

Comme nous l’avons vu precedemment, le delai designe le temps que met un paquet pouretre achemine d’une source s vers une destination d. Effectuer la difference entre l’instant dereception d’un paquet et sa date d’emission permet de connaıtre le delai d’un seul paquet.Cependant, un protocole de QoS doit etre en mesure, lors de la phase de decouverte de route,de quantifier un delai moyen en estimant les ressources disponibles a travers le reseau. Lamethode d’acces influe fortement sur le delai des paquets. Dans notre etude, le protocole deniveau MAC est la norme IEEE 802.11.

Un mobile 802.11 se comporte comme un buffer qui se remplit par des paquets de donneeset se vide en fonction de la vitesse de traitement de ces paquets de donnees. Nous modelisonscomme dans [69, 70] ce systeme par une file d’attente M/M/1/K (voir figure 7.1) dont lesproprietes sont les suivantes :

Fig. 7.1 – Modelisation d’un nœud 802.11 par une file M/M/1/K

– L’arrivee des paquets suit une loi exponentielle de parametre λ.– Le traitement des paquets suit egalement une loi exponentielle de parametre µ.– The size of the queue is limited by the value K. When a new packet arrives and there

is already K packet in the queue,– La taille de la file est bornee par la valeur K. Lorsqu’un paquet arrive et qu’il y a deja

K paquets dans le systeme alors celui-ci est perdu.Le parametre λ qui est le taux d’arrivee des paquets dans la file d’attente du nœud peut

etre represente par le debit d’emission desire par l’application et qui est explicitement fournilors de la phase de requete de route avec QoS.

Le parametre µ qui est le taux de service du nœud peut etre represente par la bandepassante residuelle autour du mobile considere.Intuitivement, lorsque µ ≥ λ, la bande passante residuelle autour du nœud est assez eleveepour la transmission du flux considere au debit desire sans congestion du reseau. Dans le cascontraire, la file d’attente du nœud va se remplir progressivement et des pertes de paquetsvont survenir entraınant une augmentation du delai.

Dans ABE, nous avions deja propose un mecanisme pour estimer la bande passanteresiduelle autour d’un nœud a partir de l’ecoute du support afin de determiner les periodesde temps libre du canal. Par consequent, nous sommes en mesure de quantifier la valeur dece parametre selon la formule : µ = τi × Cmax avec τi qui est le pourcentage de temps libre

95


du canal autour du nœud i et Cmax la capacite du medium.

Nous avons choisi de modeliser le taux de service µ par la bande passante residuelle d’unnœud car cela permet de prendre en compte deux facteurs :

– Le temps s’ecoulant entre l’instant ou le mobile rentre dans la file d’attente et l’instantou il la quitte.

– Le temps que le mobile doit attendre au niveau MAC avant de pouvoir emettre sespaquets, le medium etant occupe par des transmissions voisines.

Dans un contexte ad hoc multi-saut, la modelisation de certains parametres s’avereextremement difficile a mettre en œuvre, c’est pourquoi nous recuperons certains parametrespar le biais de mesures. Nous supposons donc que la probabilite de collisions des liens pest connue, car nous avions deja propose dans ABE un mecanisme pour l’evaluer grace auxpaquets Hello et d’une interpolation a l’aide des polynomes de Lagrange.

7.3.2 Delai dans la file d’attente des nœuds

Nous evaluons dans cette partie le delai moyen dans la file d’attente des nœuds traverses.Ce delai represente la duree qui s’ecoule entre l’instant ou le paquet rentre dans la filed’attente du nœud et l’instant ou il est emis sur le medium radio. Les nœuds 802.11 etantmodelises par des files d’attente M/M/1/K, le delai moyen dans la file d’attente n’est autreque le temps moyen de sejour.Nous representons l’evolution du nombre moyen de paquets N dans la file par un processusde Markov a temps continu dont les etats representent le nombre de paquets dans la fileet les transitions sont les taux d’arrivees λ et les taux de services µ, comme indique sur lafigure 7.2.

Fig. 7.2 – Processus de Markov representant le nombre de paquets dans la file

Soit p(n) la probabilite d’avoir n paquets dans la file avec la contrainte que 0 ≤ n ≤ K.Tout nouveau paquet arrive avec un taux λ ou quitte la file avec un taux µ, d’ou les equationssuivantes :

λ p(0) = µ p(1)

λ p(1) = µ p(2)

96


.

.

.

λ p(K − 1) = µ p(K)

On pose ρ = λµ. On peut donc exprimer de maniere simple p(n) en fonction de p(0) et ρ :

p(n) = ρn p(0) pour 0 ≤ n ≤ K

La somme des probabilites etant egale a 1 (K∑

i=0

p(i) = 1), on obtient une expression de

p(0) puis de p(n) :

=⇒

p(n) = ρn 1− ρ

1− ρK+1si ρ 6= 1

p(n) =1

K + 1si ρ = 1

D’apres la loi de Little, le temps moyen de sejour note Ts est egal a :

Ts =N

λ

Ts =

K∑i=0

i p(i)

λ

D’ou l’expression finale du temps moyen de sejour dans la file d’attente des nœuds :

Ts =

ρ

1− ρ

1− (K + 1)ρK + KρK+1

1− ρK

1

λsi ρ 6= 1

1

2(K + 1)

1

λsi ρ = 1

97


7.3.3 Delai sur le medium radio

Le delai sur le medium radio correspond au delai qui s’ecoule depuis l’emission d’un pa-quet sur le canal radio jusqu’a la reception du paquet d’acquittement correspondant. En casde collision, ce delai est rallonge a cause des eventuelles retransmissions et de l’augmentationde la taille de la fenetre de contention.

Dans la section 4.1.2.2, nous avions deja propose un mecanisme permettant d’evaluer laprobabilite de collision p d’un lien radio. Cette methode estime dans un premier temps laprobabilite de collision sur un lien en comptabilisant au niveau du nœud recepteur et sur uneperiode predefinie, le ratio entre le nombre de paquets Hello non recus et le nombre total depaquets Hello que l’on devrait recevoir sur cette meme periode de mesure. Dans un secondtemps, une interpolation a l’aide des polynomes de Lagrange permet de prendre en comptela taille des paquets de donnees.

Soit X la variable aleatoire representant le nombre moyen de retransmissions d’un paquetayant subi une collision. On a donc les egalites suivantes en terme de probabilite (la normeIEEE 802.11 impose un maximum de C retransmissions) :

P (X = k) =

pk · (1− p) si k ≤ Cpk si k = C + 10 si k ≥ C + 1

Le nombre moyen de retransmissions n associe a cette probabilite de collision p est egalea l’esperance de la variable aleatoire X :

n = E(X) =+∞∑k=0

k.P (X = k) =C∑

k=1

k.pk(1− p) + (C + 1)p(C+1)

La figure 7.3 represente le nombre moyen de retransmissions en fonction de la probabilitede collision, arrondi a l’entier naturel le plus proche. On remarque que ce nombre moyende retransmissions croıt tres lentement lorsque la probabilite de collision est inferieur a 0.5(une retransmission au maximum lorsque p ≤ 0.5). A partir de cette valeur, la croissance dece nombre moyen de retransmissions devient exponentielle jusqu’a la valeur maximale desept retransmissions obtenue pour p = 1.

Soit TDIFS la duree d’un DIFS defini par la norme, CWmin la valeur initiale de la taillede la fenetre de contention et Ttrans le temps de propagation avec succes d’un paquet sur lemedium incluant les en-tetes physique, MAC, les donnees, le SIFS et l’acquittement.

Dans ABE, nous avions propose un mecanisme permettant d’evaluer le nombre de slots debackoff (backoff) decrementes depuis le debut de la transmission en presence des collisions(c est tel que CWmax = 2c.CWmin avec c ≤ C) :‘

backoff =1− p

2·(

1− (2p)c

1− 2p· CWmin +

pc − pC

1− p

)

98


0

1

2

3

4

5

6

7

8

0 0.2 0.4 0.6 0.8 1

Nom

bre

moy

en d

e re

tran

smis

sion

s

Probabilité de collision

Nombre moyen de retransmissions

Fig. 7.3 – Nombre moyens de retransmissions en fonction de la probabilite de collision pourC = 6

Nous pouvons donc estimer le temps total Tp sur le medium radio :

Tp = backoff +n∑

k=0

(TDIFS + Ttrans)

Tp = backoff + (n + 1) (TDIFS + Ttrans)

Finalement, le delai a un saut radio correspondant au temps de service note Tserv, est lasomme du delai passe dans la file d’attente et du temps passe sur le medium radio :

Tserv = Tp + Ts (7.1)

7.4 Implementation

Le delai moyen de l’ensemble des liens radio va etre calcule proactivement toutes lessecondes afin de faciliter la phase de controle d’admission. Cette valeur sera ainsi connueavant l’envoi des paquets de donnees. La solution passe par l’utilisation des paquets Helloafin de determiner la probabilite de collision p des liens et le delai moyen vers chacun desmobiles a portee de communication.

99


Dans notre protocole DEAN, chaque seconde, tous les nœuds du reseau envoient des messagesHello vers leurs voisins. Ces messages Hello contiennent deux informations :

– Le pourcentage d’utilisation du medium percu par le nœud emetteur afin de calculerle delai passe dans sa file d’attente.

– L’identite du nœud emetteur pour differencier les liens.A la reception de ces messages Hello, les nœuds recepteurs sont en mesure d’estimer le

delai avec les nœuds sources selon l’equation 7.1. On obtient ainsi le delai moyen sur chaquelien.

Le protocole DEAN est une extension du protocole AODV. Nous cherchons a offrir deschemins pour lesquels le delai de bout-en-bout specifie par l’application est superieur a lavaleur moyenne estimee le long du chemin.Par exemple, si l’on considere un nœud source 0 desirant communiquer avec un nœud Ket que les nœuds i et i + 1 sont a portee de communication (0 ≤ i ≤ K − 1), a portee decommunication, alors la contrainte de recherche de routes peut s’exprimer sous forme d’uneinegalite :

K−1∑i=0

di⇒i+1 ≤ Dappli (7.2)

Le parametre Dappli represente le delai de bout-en-bout desire par l’application

Decouverte et maintenance de route : Le mecanisme de recherche de route estsemblable a celui adopte dans ABE. Un paquet de RREQ contenant des informations sur ledelai desire, l’identite de l’emetteur et le debit de l’application est envoye en mode diffusion.Plusieurs controles d’admission sont realises. Un premier controle est effectue par chaqueemetteur d’un paquet RREQ. Le but de ce controle est de verifier qu’on ne gene pas deflux se trouvant en situation de stations cachees. Ce controle verifie qu’on ne cree pas decongestion au niveau de la bande passante via l’estimation de la section 4.1.3. En effet, creerune congestion reviendrait a augmenter le delai des flux existants.

Les deuxieme et troisieme controles sont realises par chaque nœud intermediaire qui recoitla requete.

Le deuxieme verifie si l’inegalite de l’equation 7.2 est toujours verifiee. Cela permet des’assurer que la route recherchee verifie bien la contrainte imposee sur le delai par l’applica-tion.

Le troisieme controle est un controle sur la bande passante afin de verifier que l’on neva pas degrader et donc eventuellement retarder les flux se trouvant dans le voisinage desextremites du lien.

Si tous les controles sont positifs, le mobile ajoute son adresse sur la route et additionneson delai avec celui contenu dans le paquet de RREQ, puis transmet le paquet, sinon il ledetruit. Lorsque le controle d’admission a reussi au niveau du destinataire, ce dernier envoieun paquet de RREP pour indiquer a la source la validite de ce chemin.

100


Lorsqu’aucun message Hello n’est recu pendant une certaine duree ou que les conditionsdu reseau ne permettent plus d’acheminer le flux QoS au delai desire, un message d’erreur(RRER) est envoye a la source qui reconstruit une nouvelle route.

7.5 Simulations

Nous presentons dans ce chapitre les performances de notre protocole de reservationde flux QoS base sur le delai dans un contexte ad hoc multi-saut. L’implementation a eterealisee sous le simulateur NS-2 afin de valider les mecanismes mis en place. Notre protocolepossede une approche proactive pour l’estimation du delai de l’ensemble des liens radio etune approche reactive pour la recherche de route. L’objectif principal des simulations estde montrer que les routes choisies permettent aux flux QoS d’acheminer leurs paquets dedonnees avec un delai maximum specifie par l’application.

Nous nous sommes interesses dans un premier temps a un scenario presentant desinegalites d’acces au canal ainsi qu’a une chaıne de transmission. Le but de ces deux scenariosest de comparer la precision de l’estimation du delai obtenue par simulation et par le biaisde notre estimation. Par la suite, nous avons effectue des simulations sur des scenarios pluscomplexes telles que des topologies aleatoires afin de valider le mecanisme de reservation desressources. Nous comparons egalement les performances de notre protocole DEAN avec leprotocole de routage au mieux AODV.

Les parametres generaux des differentes simulations sont resumes au niveau du ta-bleau 7.1.

Parametres Valeurs

Protocole de routage DEANProtocole MAC IEEE 802.11bIntervalle Hello 1 s

Taille des paquets 1000 octetsModele de propagation TwoRayGroundCapacite du medium 2Mb/s

Zone de communication 250mZone de detection de porteuse 550m

Taille de la grille 1000m×1000mDuree des simulations Entre 50 et 100 secondes

Tab. 7.1 – Parametres generaux pour les simulations

101


7.5.1 Precision de l’estimation du delai de bout-en-bout

7.5.1.1 Stations cachees

Afin de mesurer la precision de l’estimation du delai, nous allons nous interesser auscenario de la figure 3.2 presente dans le chapitre 3. Le but de ce scenario est d’evaluer laprecision de l’estimation du delai a un saut radio en presence de collisions. Nous cherchonsa evaluer le delai au niveau du lien A =⇒ B en fonction de la charge du lien C =⇒ D.

Nous utilisons deux mesures du delai :– Le delai moyen theorique mesure avec notre protocole DEAN par le biais des

paquets Hello.– Le delai moyen reel obtenu de maniere ”offline” en analysant les traces de la si-

mulation. Dans ce cas precis, pour chaque paquet emis, on mesure le delai comme ladifference entre la date d’emission et de reception du paquet. Le probleme de la syn-chronisation des horloges enonce precedemment ne se pose pas car dans la simulation,tous les nœuds ont la meme horloge. Le delai reel est obtenu est faisant la moyennesur le delai de l’ensemble des paquets emis lors de cette simulation.

Les resultats obtenus sont presentes au niveau de la figure 7.4 avec un intervalle deconfiance.

0

5

10

15

20

25

30

0 100 200 300 400 500 600 700 800

Dél

ai d

e pr

opag

atio

n en

ms

Débit du lien (C−>D) en kb/s

Délai moyen théoriqueDélai moyen réel

Fig. 7.4 – Comparaison entre delai moyen theorique et delai moyen reel

Pour des debits faibles au niveau du lien C =⇒ D, le delai estime correspond au temps detransmission avec succes d’un paquet de 1000 octets a 2Mb/s soit environ 5ms. Cependant,lorsque ce debit augmente, les emissions du nœud A vont provoquer des collisions au niveaudu nœud recepteur B, entraınant des retransmissions de plus en plus frequentes. Cela se

102


traduit sur la courbe par l’augmentation du delai. Par exemple pour une charge de 500Kb/ssur le lien C =⇒ D, le delai estime est d’environ 12ms. Lorsque la charge est importante(≥ 900Kb/s) tous les paquets emis sur le lien A =⇒ B entrent en collision, le delai devientalors infini.

On remarque que quel que soit le debit sur le lien C =⇒ D, le delai theorique obtenuavec le protocole DEAN est proche du delai reel, ce qui traduit la precision de l’estimationdu delai moyen pour ce scenario.

7.5.1.2 Chaıne de transmission

Nous considerons la topologie decrite au niveau de la figure 7.5, consistant en une chaınede transmissions a quatre sauts maximum. Le nœud source A transmet ses donnees vers lenœud destinataire E qui se trouve a quatre sauts.

Fig. 7.5 – Chaıne de transmission a 4 sauts

A chaque saut, nous estimons le delai moyen obtenu a l’aide de notre estimation et ledelai moyen reel afin de comparer les resultats.

0

20

40

60

80

100

120

140

160

1 2 3 4

Dél

ai d

e pr

opag

atio

n en

ms

Nombre de saut

Délai moyen théoriqueDélai moyen réel

Fig. 7.6 – Delai moyen theorique et delai moyen reel pour une chaıne a 4 sauts

103


Comme precedemment, nous remarquons au niveau de la figure 7.6 que la valeur theoriquedu delai moyen de transmission est tres proche de la valeur reelle obtenue par simulation,quel que soit le nombre de sauts. Ainsi, pour un saut radio, le delai moyen est egal au tempsd’un paquet de 1000 octets a 2Mb/s qui est d’environ 5ms. A deux sauts, les nœuds A et Bsont en contention mais il n’y a pas de collision. Le delai est par consequent rallonge, car letemps de sejour dans la file d’attente du nœud B n’est plus negligeable. A partir de quatresauts, on est en presence de stations cachees et par consequent les collisions augmentent demaniere significative le delai de bout en bout qui passe de 35ms pour 3 sauts a 120ms pour4 sauts.

Dans cette simulation, l’augmentation du delai de transmission est due aux collisionsmais aussi au temps de sejour des paquets dans la file d’attente des nœuds intermediairesB, C et D.Les deux scenarios presentes ci-dessus traduisent la precision de l’estimation du delai moyende bout en bout de notre protocole.


Afin de valider le mecanisme de reservation, nous avons genere un scenario aleatoireconstituee de 10 nœuds places aleatoirement dans un carre de 1000m×1000m. Pour chaqueflux QoS, nous recherchons une route vers le destinataire dont le delai est inferieur a 100ms.Cinq flux CBR sont inities et pour chacun d’entre eux le mobile initiateur de la communica-tion choisit aleatoirement un mobile comme destinataire (celui-ci peut etre hors de sa zonede communication necessitant un routage pour l’atteindre). La simulation dure 50 secondes,le demarrage de chaque flux est espace de 5 secondes.

Au niveau de la figure 7.7(a), lorsqu’AODV est utilise comme protocole de routage, chaqueemetteur recherche une route vers son destinataire sans aucune contrainte en terme de delai.Ainsi la premiere route stockee est utilisee pour acheminer les donnees sans tenir compte del’etat de cette derniere. Cette situation entraıne le choix de routes pour lesquelles le delaiest superieur a la valeur maximale de 100ms. D’apres les resultats presentes au niveau dutableau 7.2, le flux 5 a un delai moyen d’environ 1966ms, ce qui est largement superieur ala valeur maximale de 100ms.

Lorsque le protocole DEAN est active (figure 7.7(b)), un controle d’admission permet dese rendre compte que les conditions du reseau ne permettent pas d’acheminer les flux numero4 et 5 au delai desire. Par consequent ces deux flux sont rejetes et tous les autres flux admissont convoyes avec un delai moyen inferieur a 100ms.

7.5.3 Taux d’acceptation des paquets QoS

La precision de l’estimation du delai moyen de bout-en-bout et de la phase de controled’admission peuvent etre evaluees par le biais d’une nouvelle metrique note α, caracterisant letaux d’acceptation des paquets QoS. En effet lorsqu’un flux QoS est admis, le delai moyen detous les paquets doit etre inferieur a la borne maximale specifiee par l’utilisateur. Toutefois,il arrive que certains paquets QoS soient achemines avec un delai moyen legerement superieur

104


0

20

40

60

80

100

120

140

0 5 10 15 20 25 30 35 40 45 50

Dél

ai d

es p

aque

ts s

econ

des

Date de la simulation en secondes

Délai AODV flux1Délai AODV flux2Délai AODV flux3Délai AODV flux4Délai AODV flux5

Délai maximal 100 ms

(a) AODV

0

20

40

60

80

100

120

140

0 5 10 15 20 25 30 35 40 45 50

Dél

ai d

es p

aque

ts s

econ

des

Date de la simulation en secondes

Délai QoS flux1Délai QoS flux2Délai QoS flux3Délai QoS flux4Délai QoS flux5

Délai maximal 100 ms

(b) DEAN

Fig. 7.7 – Delai moyen des flux avec les protocoles AODV et DEAN

105


Identifiant du flux DEAN (ms) AODV (ms)Delai moyen Int. conf (95%) Delai moyen Int. conf (95%)

Flux 1 50.15 [49.17, 51.13] 102.52 [97.6, 107.45]Flux 2 28.26 [26.31, 30.21] 28.88 [25.75, 32.01]Flux 3 16.09 [15.65, 16.52] 19.92 [19.14, 20.70]Flux 4 pas admis pas admis pas de route pas de routeFlux 5 pas admis pas admis 1966.39 [1907.30, 2025.49]

Tab. 7.2 – Delais moyens obtenus avec DEAN et AODV

a cette valeur maximale. Ainsi, nous preconisons une marge de 5% afin de prendre en compteces situations.

Nous pouvons donc estimer pour chaque flux QoS admis, le nombre de paquets dontle delai est inferieur a la valeur maximale specifiee par l’application plus 5% de marged’erreur. Soit n le nombre de paquets dont le delai est inferieur a la valeur maximale avecune marge de 5%, et N le nombre total de paquet emis dans le reseau. Nous obtenons larelation suivante :

α =n

N

Plus l’estimation est precise, plus le nombre de paquets dont le delai est inferieur a lavaleur specifiee par l’application est grand et la valeur de α augmente. Dans le cas contraire,cette valeur diminue. Ainsi, le parametre α permet de caracteriser aussi bien la precisionde l’estimation que la phase de controle d’admission. Toutefois, le delai moyen caracterisele comportement moyen de tous les paquets. Il peut arriver qu’un ou plusieurs paquetsQoS possede un delai largement superieur a la valeur specifiee par l’application, les raisonspouvant etre multiples.

Nous avons par la suite procede a des simulations pour estimer la valeur de la metrique αen fonction du nombre de nœuds dans le reseau. Nous generons des topologies dont le nombrede nœuds considere varie de 10 a 40 et sont positionnes aleatoirement. Cinq connexions CBRsont etablies entre des nœuds source et destination choisis aleatoirement. Les debits sontdistribues uniformement dans l’intervalle [0-500] Kb/s et le delai maximal pour chaque fluxQoS est de 50ms. De plus, chaque simulation dure 100 secondes et les resultats presentesconstituent la moyenne de 30 simulations.

Il est important de remarquer que durant les simulations, nous generons des topologiesconnexes (il existe toujours un chemin entre n’importe quelle paire de nœuds du reseau)afin que les pertes de paquets ne soient pas causes par des routes non etablies.

La figure 7.8 represente la valeur de α en fonction du nombre de nœuds presents dansle reseau. Comme l’on pouvait s’y attendre, plus le reseau devient dense, plus la valeur duparametre α diminue car le delai moyen des liens devient plus faible.

106


30

40

50

60

70

80

90

100

10 20 30 40

Val

eur

du p

aram

ètre

alp

ha (

%)

Nombre de mobiles

DEANAODV

Fig. 7.8 – Evaluation de la metrique α avec les protocoles DEAN et AODV

Avec le protocole AODV, le taux d’acceptation avoisine 60% pour 10 nœuds et tombe a40% pour 40 nœuds. Lorsque notre protocole DEAN est active, le taux d’acceptation passede 85% pour 10 nœuds a 71% pour 40 nœuds. On constate donc que contrairement a labande passante residuelle (voir figure 5.9(a)), augmenter le nombre de nœuds ne diminuepas de maniere tres importante le delai moyen des paquets. Cela s’explique par le fait quel’augmentation du nombre de nœuds n’entraıne pas systematiquement une augmentationdu nombre de sauts entre une source s et une destination d. En moyenne, la longueur deschemins choisis reste identique lorsque le nombre de nœuds augmente dans le reseau, d’ouune variation tres faible du delai moyen des paquets et par consequent du taux d’acceptationα.

Nous nous sommes par la suite interesses a l’influence du protocole applicatif au niveaudu protocole DEAN. Nous evaluons une fois de plus la valeur du parametre α en fonction duprotocole de niveau applicatif mis en place. Les deux protocoles que nous comparons sont :

– CBR : Le flux CBR ou Constant Bit Rate envoie des paquets de donnees de memetaille a une frequence connue et fixe : le debit reste donc constant tout au long dela simulation. De plus, ce protocole fonctionne en mode non connecte et utilise UDPcomme protocole de niveau transport.

– FTP : Le protocole FTP ou File Transfer Protocol fonctionne en mode connecte etnecessite des acquittements supplementaires par rapport aux paquets de donnees en-voyes sur le reseau. Le debit des applications est gere par le protocole FTP et ne peutetre specifie par l’utilisateur.

107


DEAN AODVDelai (ms) CBR FTP CBR FTP

25 90 ([86 ;94]) 66 ([59 ;73]) 68 ([62 ;74]) 59 ([52 ;66])50 92 ([88 ;96]) 74 ([69, 79]) 77 ([73 ;81]) 69 ([64 ;74])75 94 ([90 ;98]) 81 ([77 ;85]) 83 ([79 ;87]) 74 ([70 ;78])100 95 ([92 ;98]) 87 ([82 ;92]) 86([83 ;89]) 77 ([74 ;80])

Tab. 7.3 – Valeur de α avec les protocoles CBR et FTP

Le schema des piles protocolaires mises en place pour cette serie de simulation est resumeeau niveau de la figure 7.9.

Fig. 7.9 – Pile protocolaire mises en place

Les simulations mises en place sont constituees de topologies connexes de 20 nœudspositionnees aleatoirement et de 5 flux CBR ou FTP selon le protocole de niveau applicatifutilise. Les debits des flux CBR sont distribues uniformement dans l’intervalle [0-500]Kb/set le delai maximal pour chaque flux QoS varie entre 25 et 100ms. Enfin, chaque simulationdure 100 secondes et les resultats presentes au niveau du tableau 7.3 constituent la moyennede 30 simulations. Les valeurs se trouvant entre parentheses representent l’intervalle deconfiance a 95%.

L’analyse des resultats du tableau 7.3 permet de degager trois principales remarques.Premierement, comme l’on pouvait s’y attendre, l’utilisation du protocole DEAN par

rapport a AODV permet d’augmenter le taux d’acceptation de flux QoS. La phase de controle

108


DEAN AODVDelai (ms) CBR FTP CBR FTP

25 8 26 26 3350 6 20 16 2475 5 14 13 22100 4 11 11 19

Tab. 7.4 – Taux de perte en % avec les protocoles CBR et FTP

d’admission elimine les paquets dont le delai moyen est susceptible de depasser le delaimaximal specifie par l’utilisateur et limite la degradation des flux existants.

Deuxiemement, l’utilisation de CBR permet d’obtenir un taux d’acceptation des flux QoSmeilleur qu’avec TCP et ceci quel que soit le protocole de routage utilise. Par exemple, pourun delai de 25ms, les valeurs de α sont de 90% avec des flux CBR et de 66% avec des fluxFTP, le protocole de routage etant DEAN. Lorsqu’on utilise AODV comme protocole deroutage, ces valeurs passent respectivement a 68% et 59%. Ces resultats peuvent s’expliquerpar la nature du protocole TCP. Ce protocole fonctionne en mode connecte et necessite doncl’envoi d’un paquet d’acquittement pour chaque paquet de donnees envoye. Ce mecanismeaugmente donc le delai des paquets reduisant ainsi le taux d’acceptation par rapport aux fluxCBR. De plus, nous n’avons aucun controle sur le debit de ces flux ce qui pose un problemepour le controle d’admission sur la bande passante residuelle.

Troisiemement, le choix du delai par l’application influe sur le taux d’acceptation. Lorsquece delai maximum est faible (25ms), le protocole DEAN arrive a acheminer un taux d’accep-tation assez eleve 90% pour des flux CBR tandis qu’AODV achemine environ 68%. Lorsquele delai maximum specifie par l’utilisateur augmente, le delai des paquets devient plus faibleque ce delai maximal et par consequent le taux d’acceptation de flux QoS peut augmenterquelle que soit la pile protocolaire mise en place. Par exemple, pour un delai de 100ms, lestaux d’acceptation sont respectivement de 95, 87, 86 et 77% pour CBR sur DEAN, FTP surDEAN, CBR sur AODV et FTP sur AODV.

Le tableau 7.4 represente le taux de perte global dans le reseau. Nous definissons ce tauxde perte comme le taux de paquets dont le delai est superieur au double du delai desire parl’application.

On remarque que l’utilisation du protocole DEAN permet de reduire ce taux de perte parrapport a AODV grace a la phase du controle d’admission. Pour les flux CBR, un controlesur le debit d’emission que ne nous permet pas le protocole FTP, entraıne une reductionde ce taux de perte. Enfin, plus le delai est grand, plus le nombre de paquets pouvant etreachemines au delai moyen desire est grand. Par consequent, le taux de perte est reduit atravers le reseau. Notre protocole DEAN est adapte pour des applications audio qui exigentgeneralement un taux de perte de paquets inferieur a 20% pour un fonctionnement correct.

109


7.6 Conclusion

Dans ce chapitre, nous avons propose une methode permettant d’estimer le delai moyende bout en bout dans un reseau ad hoc multi-saut. L’estimation du delai moyen de bout enbout proposee peut se decomposer en deux grandes parties :

– Le delai moyen dans la file d’attente des nœuds intermediaires constituant le chemin. Ceparametre est obtenu en modelisant le nœud 802.11 par une file d’attente M/M/1/K.Les resultats classiques sur la theorie des files d’attente permettent par la suite dederiver une expression du temps moyen de sejour.

– Le delai moyen sur le canal radio est obtenu en modelisant le nombre moyen de re-transmissions par une variable aleatoire.

Nous avons par la suite implemente une version protocolaire appelee DEAN dont lebut est de determiner des routes dont le delai moyen est inferieur a la valeur demandeepar l’application. La precision de l’estimation du delai moyen et du controle d’admissionpermettent de s’assurer que les routes choisies respectent les contraintes applicatives. Lessimulations montrent qu’avec des flux CBR, les routes choisies garantissent l’acheminementdes donnees en tenant compte des contraintes applicatives specifiees.

110

Conclusion et perspectives

La facilite de deploiement et l’absence d’une gestion centralisee des communications desreseaux ad hoc en font une solution presentant de nombreux avantages aussi bien dans lesdomaines civil que militaire. Ces dernieres annees, de nombreuses recherches ont ete meneessur ces types de reseaux et plus recemment, la problematique de la Qualite de Service aete etudiee. Cependant, comme nous l’avons vu dans tout au long de ce document, lescaracteristiques propres aux reseaux ad hoc rendent difficile la garantie des ressources.

Dans la premiere partie de cette these, nous nous nous sommes interesses a laproblematique de reservation de bande passante dans les reseaux ad hoc multi sauts. Leprotocole ABE ainsi developpe propose une estimation de la bande passante residuelle del’ensemble des liens radio du reseau. Cette estimation se base sur une synchronisation desperiodes de temps libre entre les mobiles emetteur et recepteur, combinee a une estimationde la probabilite de collision des liens. ABE adopte un fonctionnement reactif pour larecherche des routes admissibles qui garantissent la transmission des flux QoS avec labande passante desiree et specifiee explicitement par l’application. Un controle d’admissioneffectue par chacun des nœuds du reseau permet d’eliminer les routes consideres comme”non conformes aux exigences”. Les resultats de simulation montrent que le point crucialet difficile lors de la mise en place de protocoles de reservation de bande passante restel’estimation de la bande passante residuelle des liens radio. Avec ABE, les routes reserveesgarantissent le debit des applications.

Dans la deuxieme partie, nous avons mis en relief le fait que la reservation de bandepassante ne peut se faire sans tenir compte de la nature des flux. Nous nous sommes placesdans le cas ou deux classes de trafic sont presents : les flux QoS et les flux Best Effort dontla degradation des ressources est moins importante. Il est possible qu’une grande partie dela bande passante residuelle soit occupee par ces flux Best Effort, empechant ainsi aux fluxQoS d’effectuer leurs transmissions avec les garanties requises. Pour pallier cette situation,nous avons donc mis en place DRBT, un protocole qui regule le debit des flux Best Effortafin d’augmenter le taux d’acceptation des flux QoS a venir ou existants. La decision deregulation se base sur une estimation differenciee de la bande passante residuelle prenanten compte la nature des paquets transmis sur le medium radio. L’etude des performancespermet d’augmenter de maniere non negligeable le taux d’acceptation des flux QoS, tout en

111


utilisant de maniere optimisee les ressources du reseau.

Enfin, dans la troisieme partie le probleme de la reservation est une fois de plusaborde. Cependant la metrique consideree est le delai moyen. Moins souvent etudie que labande passante, le delai est une metrique aussi importante surtout pour les applicationsmultimedia. L’estimation du delai moyen est realisee grace a une modelisation des nœudsIEEE 802.11 par une file d’attente M/M/1/K. Les resultats de simulation obtenus montrentque les routes choisies permettent d’acheminer les donnees avec un delai borne, inferieur ala valeur specifiee par l’application.

Pour conclure, nous pensons que l’estimation de la bande passante residuelle proposeedans ABE constitue un socle important pour les protocoles de qualite de service dans lesreseaux ad hoc. En effet, cette these a montre qu’il etait possible de deriver, a partir de cesocle, des solutions de qualite de service efficaces avec des objectifs differents. Cependant,ABE ne fournit pas une estimation fiable a 100% pour differentes raisons :

– La norme 802.11 dans l’etat actuel ne permet pas de recuperer la taille des paquetsde donnees a partir des acquittements associes a ces paquets. Ceci ne nous permetpas de determiner avec precision le debit des flux qui sont en configuration de stationscachees.

– La connaissance des configurations de stations cachees se fait dans ABE grace audecodage des paquets d’acquittements. Or, il est possible d’avoir deux stations cacheesavec un des emetteurs a portee de communication de son recepteur associe tandisque l’autre emetteur n’est pas a portee de communication de ce dernier. Cependant,le deuxieme emetteur peut generer de collisions sur ce recepteur. ABE n’est pas enmesure de detecter ces configurations particulieres.

Ameliorer ABE necessite de s’attaquer aux problemes precedents. On voit bien que cesdeux problemes necessitent de comprendre un maximum d’informations dans le reseau, cequi implique de decoder le maximum de paquets circulant dans le voisinage. On retrouvece probleme dans le protocole DRBT, pour lequel la differenciation des paquets ne peut sefaire que grace a un decodage correct de ceux-ci. Comme nous l’avons vu dans cette these,rendre le seuil de detection de porteuse de 802.11 equivalent au seuil de communication estune premiere solution qui permet un meilleur decodage des paquets. Cet ajustement du seuilde detection de porteuse ne doit pas etre utilise avec n’importe quel protocole, sous peined’augmenter le nombre de collisions. En revanche, s’il est utilise avec un protocole capablede quantifier et de controler ces collisions, alors il est benefique pour le reseau, comme c’estle cas pour ABE ou DRBT. Modifier le seuil de detection de porteuse constitue un premierpar vers plus d’informations utiles mais ne permet pas de detecter tous les scenarios destations cachees. Des ameliorations sont encore a apporter et constituent clairement lesperspectives a court terme.

112


Au niveau des perspectives a moyen terme, plusieurs pistes me semblent interessantes.La premiere serait de comparer le protocole DEAN avec d’autres protocoles de routagebases sur le delai et non seulement avec AODV. Ceci permettrait de comparer la techniqued’evaluation du delai moyen. La deuxieme piste concerne la simulation de scenarios plusrealistes. L’evaluation des scenarios aleatoires est un premier pas pour l’evaluation desperformances des protocoles mais ne reflete peut-etre pas des topologies realistes. Lespremiers scenarios plus realistes envisages concerneraient les reseaux mailles avec desschemas de communication comme la voix sur IP ou la diffusion de video.

A plus long terme, j’aimerais pouvoir comparer les approches de qualite de service proac-tives des approches reactives. Un premier travail pourrait etre de comparer ABE et DEANavec QOLSR. Un deuxieme axe de recherche serait d’etudier l’impact des protocoles proposessur des profils de trafics differents des trafics CBR utilises principalement dans toutes lessimulations. Les resultats obtenus avec DEAN et TCP dans le chapitre 7 semblent montrerqu’il est difficile de s’affranchir des caracteristiques de TCP dans l’evaluation des ressourcesdisponibles. Si TCP devient un protocole de transport utilise dans les reseaux ad hoc, ce quin’est pas si sur, il faudra alors integrer son fonctionnement dans l’evaluation des ressourcescomme nous l’avons fait avec 802.11. Enfin, un dernier point concerne l’implantation reellede ces protocoles. Ce travail n’est pas aise car il necessite de recuperer des informations de lacouche MAC, qui ne sont pas fournies par les cartes sans fil actuel. Neanmoins cette etape estfondamentale, car seule une evaluation reelle pourra effectivement valider le fonctionnementdes solutions presentees.

113

Liste de publications

Journaux internationaux avec comite de lecture

[1] Cheikh SARR, Claude Chaudet, Guillaume Chelius and Isabelle Guerin-Lassous - Anode-based available bandwith evaluation in IEEE 802.11 ad hoc network - Inter-national Journal of Parallel Emergent and Distributed Systems (Taylor Francis) - Volume21, Issue 6, 2006.

Conferences internationales avec comite de lecture

[2] Cheikh SARR, Claude Chaudet, Guillaume Chelius and Isabelle Guerin-Lassous - Anode-based available bandwith evaluation in IEEE 802.11 ad hoc network - InFirst International Workshop on System and Networking for Smart Objects (SANSO 2005)- Fukuoka, Japan, July 2005

[3] Cheikh SARR, Claude Chaudet, Guillaume Chelius and Isabelle Guerin-Lassous -Improving Accuracy in Available Bandwidth Estimation for IEEE 802.11-basedAd hoc Network - In Proceedings of the The Third IEEE International Conference onMobile Ad-hoc and Sensor Systems (MASS) - Vancouver, Canada, October 2006

[3] Sofiane Khalfallah, Cheikh SARR and Isabelle Guerin-Lassous - Dynamic bandwidthmanagement for multihop wireless ad hoc networks - In Proceedings of the IEEE65th Vehicular Technology Conference VTC2007-Spring - Dublin, Ireland, April 2007

Conferences nationales avec comite de lecture

[5] Cheikh SARR, Claude Chaudet, Guillaume Chelius and Isabelle Guerin-Lassous - ABE :Un protocole de reservation de bande passante pour les reseaux ad hoc basessur IEEE 802.11 - In Proceedings of CFIP (Colloque Francophone sur l’Ingenierie desProtocoles) - Tozeur, Tunisie, October 2006

114


[6] Cheikh SARR, Claude Chaudet, Guillaume Chelius and Isabelle Guerin-Lassous -Amelioration de la precision pour l’estimation de la bande passante residuelledans les reseaux ad hoc bases sur IEEE 802.11 - In Proceedings of JDIR (JourneesDoctorales en Informatique et Reseaux ) - Marne la Vallee, France, Janvier 2007

[7] Cheikh SARR and Isabelle Guerin-Lassous - Gestion dynamique de la bandepassante dans les reseaux ad hoc - In 9eme rencontre francophones sur les aspectsalgorithmiques des telecommunications (ALGOTEL 2007) - Ile d’oleron, France, Juin 2007

En attente

[8] Cheikh SARR, Claude Chaudet, Guillaume Chelius and Isabelle Guerin-Lassous -Bandwidth Estimation for IEEE 802.11-based Ad Hoc networks - In IEEETransactions on Mobile Computing (IEEE TMC) - 2007

Rapport de Recherche

[9] Cheikh SARR, Claude Chaudet, Guillaume Chelius and Isabelle Guerin-Lassous -Improving Accuracy in Available Bandwidth Estimation for 802.11-based Adhoc Networks - Technical Report INRIA number RR-5935 - April 2006

115

Bibliographie

[1] Guy Pujolle. Pujolle les reseaux. 6eme Edition. Paris : Eyrolles, 2005. pp. 547 - 549.

[2] Guy Pujolle. Pujolle les reseaux. 6eme Edition. Paris : Eyrolles, 2005. pp. 549 - 550.

[3] Bluetooth Special Interest Group. En ligne, disponible sur http ://www.bluetooth.org,consulte le 10-12-2006.

[4] IEEE Standard for Information Technology - Telecommunications and information ex-change between systems - Local and metropolitan area networks. Specific requirements- Part 11 : Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY)Specifications, 1997.

[5] Mobile Ad hoc Network (MANET), IETF. En ligne, disponible surhttp ://www.ietf.org/html.charters/manetcharter.html, consulte le 05-10-2006.

[6] Muhlethaler Paul. 802.11 et les reseaux sans fil. Paris : Eyrolles, 2002. page 281.

[7] IEEE 802.3 CSMA/CD (Ethernet) . En ligne, disponible surhttp ://www.ieee802.org/3/, consulte le 01-01-2007.

[8] Vaduvur Bharghavan, Alan J. Demers, Scott Shenke and Lixia Zhang. MACAW : Amedia access protocol for wireless LAN’s. In Special Interest Group on Data Commu-nications (SIGCOMM), pages p. 212–225, 1994.

[9] Tahiry Razafindralambo and Fabrice Valois. Stochastic behavior study of backoff al-gorithms in case of hidden terminals. In IEEE Symposium on Personal, Indoor andMobile Radio Communications (PIMRC), 2006.

[10] Hardware specification of lucent orinoco wireless pc card,http ://www.orinocowireless.com.

[11] Henrik Lundgren, Erik Nordstrom and Christian Tschudin. Coping with communica-tion gray zones in IEEE 802.11b based ad hoc networks. Technical report, UppsalaUniversity, Sweden, June 2002.

[12] Claude Chaudet, Dominique Dhoutaut and Isabelle Guerin Lassous. Performance issueswith IEEE 802.11 in ad hoc networking. IEEE Communications magazine, 43(7), July2005.

[13] Claude Chaudet et Isabelle Guerin-Lassous. Routage QoS et reseaux ad hoc : de l’etatdes liens a l’etat de noeud. Technical report, INSA Lyon (CITI), Janvier 2003.

116

BIBLIOGRAPHIE

[14] Philippe Jacquet and Thomas Clausen. Optimized Link State Routing Protocol (OLSR).Internet Request For Comments RFC 3626. Internet Engineering Task Force (IETF),October 2003.

[15] C. E. Perkins, P. Bhagwat . Highly Dynamic Destination-Sequenced Distance Vectorrouting protocol (DSDV). In Proc. of the SIGCOMM 1994 Conference on Communi-cations Architectures, Protocols and Applications, pages 234 – 244, August 1994.

[16] J. Moy. Open Shortest Path First Specification (OSPF). IETF RFC 1131, October1989.

[17] J. Moy. Open Shortest Path First v2 (OSPF). IETF RFC 2328, April 1998.

[18] J. Malkin. Routing Information Protocol (RIP) Version 2. IETF RFC 1338, January1993.

[19] Richard G. Ogier, Fred L. Templin and Lewis Mark G. Topology Dissemination Basedon Reverse-Path Forwarding (TBRPF), Internet Request For Comments RFC 3684.Internet Engineering Task Force (IETF), February 2004.

[20] Charles E. Perkins, Elizabeth M. Belding-Royer and Samir Das. Ad hoc On-DemandDistance Vector (AODV) Routing. Internet Request For Comments RFC 3561. InternetEngineering Task Force IETF, July 2003.

[21] Yih-Chun Hu, David B. Johnson and David A. Maltz. The Dynamic Source RoutingProtocol for Mobile Ad Hoc Networks (DSR), Internet Draft. draft-ietf-manet-dsr-09.txt,April 2003.

[22] Zygmunt J. Haas, Marc R. Pearlman and Prince Samar. The Zone Routing Protocol(ZRP) for Ad Hoc Networks - Internet Draft. Internet Engineering Task Force (IETF),July 2002.

[23] Raghupathy Sivakumar, Prasun Sinha and Vaduvur Bharghavan. CEDAR (Core Ex-traction Distributed Ad hoc Routing). The 18th Annual Joint Conference of the IEEEComputer and Communications Societies - IEEE Infocom, pages 202–209, March 1999.

[24] M. Jiang, J. Li and Y.C. Tay. Cluster Based Routing Protocol (CBRP). draft-ietf-manetcbrp-spec-01.txt, July 1999.

[25] Young-Bae Ko and Nitin H. Vaidya . Location-aided routing (LAR) in mobile ad hocnetworks. In Proceedings of the 4th annual ACM/IEEE international conference onMobile computing and networking, pages p. 66–75, Dallas, Texas, United States, 1999.

[26] E. Crawley, R. Nair, B. Rajagopalan and H. Sandick and. A Framework for QoS-basedRouting in the Internet. IETF RFC 2386, August 1998.

[27] Kui Wu And Janelle Harms. QoS Support in Mobile Ad Hoc Networks. CrossingBoundaries - the GSA Journal of University of Alberta, 1(1) :92–106, November 2001.

[28] Claude Chaudet and Isabelle Guerin-Lassous. Etat des lieux sur la qualite de servicedans les reseaux ad hoc. In Proceedings of Colloque Francophone sur l’Ingenierie desProtocoles (CFIP’06), pages p. 229–251, Tozeur, Tunisie, 2006.

117

BIBLIOGRAPHIE

[29] Stefan Mangold, Sunghyun Choi, Peter May, Ole Klein, Guido Hiertz and Lothar Stibor.IEEE 802.11e Wireless LAN for Quality of Service. In Proceedings of European Wireless2002 (EW2002), pages 32–39, Florence, Italy, February 2002.

[30] M.Jain and C. Dovrolis. Pathload : A measurement tool for end-to-end available band-width. In Proceedings of Passive and Active Measurement (PAM), 2002.

[31] T. Oetiker. MRTG : Multi Router Traffic Grapher - http ://ees-taff.ethz.ch/oetiker/mrtg/mrtg.html.

[32] Robert L. Carter and Mark E. Crovella. Measuring bottleneck Link Speed in PacketSwitched Network. Technical report, Computer Science Department, Boston University,March 1996.

[33] Bob Melander, Mats Bjorkman, and Gunningberg. A new end-to-end probing analysismethod for estimating bandwith bottlenecks. In Proceedings of the Fifth Global InternetSymposiumin held in conjunction with Globecom 2000, San Francisco, USA, November2000.

[34] Ravi Prasad, Margaret Murray, Constantinos Dovrolis, and K. Claffy. Bandwidth es-timation : metrics, measurement techniques, and tools. IEEE Network, 17(6) :27–35,November 2003.

[35] Andreas Johnsson, Bob Melander, and Mats Bjorkman. Bandwidth Measurement inWireless Network. Technical report, Malardalen University, Sweden, March 2005.

[36] Samarth H Shah, Kai Chen and Klara Nahrstedt. Available Bandwidth Estimationin IEEE 802.11-based Wireless Networks. In Proceedings of The first ISMA/CAIDABandwidth Estimation Workshop (BEST 2003), San Diego, Californie, USA, December2003.

[37] Frank Y. Li, Mariann Haugea, Andreas Hafslund, Oivind Kure and Pal Spilling. Estima-ting Residual Bandwidth in 802.11-based Ad Hoc Networks : An empirical Approach. InProceedings of The Seventh International Symposium on Wireless Personal MultimediaCommunications (WPMC 2004), Abano Terme, Italy, September 2004.

[38] Claude Chaudet, Isabelle Guerin Lassous. BRuIT - Bandwidth Reservation under In-Terferences influence. In Proceedings of European Wireless 2002 (EW2002), Florence,Italy, Feb 2002.

[39] Claude Chaudet and Isabelle Guerin-Lassous. Evaluation of the BRuIT protocol. In Pro-ceedings of the IEEE 61st Semiannual Vehicular Technology Conference (VTC Spring2005), Stockholm, Sweden, May 2005.

[40] Claude Chaudet. Autour de la reservation de bande passante dans les reseaux ad hoc.PhD thesis, Institut National des Sciences Appliquees de Lyon (INSA), 2004.

[41] Yaling Yang and Robin Kravets. Contention Aware Admission Control for Ad HocNetworks. IEEE Transactions on Mobile Computing, 4 :363–377, 2005.

[42] K. Sanzgiri, I. D. Chakeres, and E. M. Belding-Royer. Determining Intra-Flow Conten-tion Along Multihop Paths in Wireless Networks. In Proceedings of BroadNet, San Jose,California (USA), October 2004.

118

BIBLIOGRAPHIE

[43] Ronan de Renesse, Mona Ghassemian, Vasilis Friderikos, A. Hamid Aghvami. QoSEnabled Routing in Mobile Ad Hoc Networks. In IEEE 3G 2004, 2004.

[44] R. de Renesse, M. Ghassemian, V. Friderikos and A.H Aghvami. Adaptive AdmissionControl for Ad Hoc and Sensor Networks Providing Quality of Service (AAC). Technicalreport, King College, London, May 2005.

[45] Hakim Badis. Etude et conception d’algorithmes pour les reseaux mobiles et ad hoc.PhD thesis, Universite Paris-Sud, Orsay, 2006.

[46] Dang Quang Nguyen. Support de la qualite de service dans les reseaux ad hoc. PhDthesis, Universite Paris 6 - Pierre et Marie Curie, Septembre 2006.

[47] Srinivasan Seshan, Mark Steem and Randy H Katz. SPAND : Shared Passive NetworkPerformance Discovery. In Proceedings of USITS - Usenix Symposium on InternetTechnologies and Systems, Monterey, December 1997.

[48] K. Nahrstedt, S. H. Shah, and K. Chen. Cross-layer architectures for bandwidth manage-ment in wireless networks. In Resource Management in Wireless Networking, New-York(USA), 2005.

[49] C. Perkins, E. Royer and SR. Das. Quality of Service for Ad Hoc On-Demand DistanceVector (AODV) Routing. Internet-Draft, July 2000.

[50] Dominique Dhoutaut and Isabelle Guerin-Lassous. Experiments with 802.11b in adhoc configurations. In Proceedings of the fourteenth IEEE International Symposium onPersonal, Indoor and Mobile Radio Communications (PIMRC 2003), pages 1618–1622,Beijing, China, September 2003.

[51] L. Chen and W. Heinzelman. QoS-aware Routing Based on Bandwidth Estimation forMobile Ad Hoc Networks. IEEE Journal on Selected Areas of Communication, 3, 2005.

[52] J. Yoon, M. Liu and B. Noble. Random waypoint considered harmful. In Proceedingsof Infocom 2003, pages 1312–1321, San Fransisco, California, USA, April 2003.

[53] Dominique Dhoutaut. Etude du standard IEEE 802.11 dans le cadre des reseaux adhoc : de la simulation a l’experimentation. PhD thesis, INSA de Lyon, LaboratoireCITI, Decembre 2003.

[54] Fethi Filali. Towards a fully distributed QoS-aware MAC protocol for multihop wirelessnetworks. In IWWAN 2005, International Workshop on Wireless Ad-hoc Networks,May 23rd - 26th 2005, London, UK, May 2005.

[55] Gahng-Seop Ahn, Andrew T. Campbell, Andreas Veres and Li-HsiangSun. SWAN :Service Differentiation in Wireless Ad Hoc Networks. In IEEE INFOCOM, 2002.

[56] A. Veres, A. Campbell, M. Barry and L-h. Sun. Supporting Service Differentation inWireless Packet Networks Using Distributed Control. IEEE Journal on Selected Areasin Communications (JSAC), 19 :(10), October 2001.

[57] Yaling Yang and Robin Kravets. Distributed QoS Guarantees for Realtime Traffic inAd Hoc Networks. In IEEE International Conference on Sensor and Ad Hoc Commu-nications and Networks (SECON), pages 118– 127, Oct 2004.

119

BIBLIOGRAPHIE

[58] Sally Floyd and Van Jacobson. Random Early Detection Gateways for CongestionAvoidance . IEEE/ACM Transaction on Networking, 1 :397–413, 1993.

[59] H. Arora and L. Greenwald. Toward the use of local monitoring and network-widecorrection to achieve QoS guarantees in mobile ad hoc networks. In Society Conferenceon Sensor, Mesh and Ad Hoc Communications and Networks IEEE SECON, 2004.

[60] Mustafa Ozdemir and A. Bruce McDonald. An M/MMGI/1/K Queing Model for IEEE802.11 Ad hoc Networks. In Proceedings of Performance Evaluation of Wireless Ad Hoc,Sensor, and Ubiquitous Networks (PE-WASUN), Italy, October 2004.

[61] Giuseppe Bianchi. Performance Analysis of the IEEE 802.11 Distributed CoordinationFunction. IEEE Journal on Selected Areas in Communications, Volume 18(3) :pages535–547, March 2000.

[62] A. Veres, A. Campbell, M. Barry and L-H SUN. Supporting Service Differentation inWireless Packet Networks Using Distributed Control. IEEE Journal on Selected Areasin Communications, 19 :10, October 2000.

[63] Amina Meraihi Niami and Philippe Jacquet. One-Hop Delay Estimation in 802.11 AdHoc Networks Using the OLSR Protocol. Technical Report RR-5327, INRIA, October2004.

[64] Amina Meraihi Naimi. Delai et Routage dans les reseaux ad hoc 802.11. PhD thesis,Universite de Versaille Saint-Quentin-En-Yvelines, 2005.

[65] H. Badis, A. Munaretto, K. Al Agha and G. Pujolle. Qos for Ad Hoc Networking Basedon Multiple Metrics : Bandwith and Delay. In IEEE international conferenceon Mobileand Wireless CommunicationsNetworks (MWCN 2003), 2003.

[66] A. Munaretto, H. Badis, K . AL agha and G. Pujolle. A Link-state QoS Routing Protocolfor Ad Hoc Networks. In IEEE MWCN’02 : International Workshop On Mobile andWireless Communications Networks, Sweden, September 2002.

[67] Omesh Tickoo and Biplab Sikdar. Queueing Analysis and Delay Mitigation in IEEE802.11 Random Access MAC based Wireless Networks. In IEEE Infocom, 2004.

[68] P. Chatzimisios, A.C. Boucouvalas and V. Vitsas. IEEE 802.11 packet delay - A finiteretry limit analysis. In Proceedings of Global Telecommunications Conference, 2003.GLOBECOM’03. IEEE, volume 2, pages 950–954, December 2003.

[69] R.S. Wong, S. Shankar, N. Van der Schaar. Integrated application MAC modeling forcross-layer optimized wireless video. In IEEE International Conference on Communi-cations (ICC 2005), volume 2, pages 1271–1275, 2005.

[70] Ibrahima Niang and Dominique Seret. Dimensionnement de DiffServ et metriques deperformances. In Colloque africain sur la recherche en Informatique - CARI02, Yaounde,October 2002.

120

Table des figures

1.1 Architecture en couche de 802.11 . . . . . . . . . . . . . . . . . . . . . . . . 101.2 Mode ad hoc et infrastructure de la norme IEEE 802.11 . . . . . . . . . . . . 121.3 Exemple d’acces au canal par deux stations concurrentes . . . . . . . . . . . 141.4 Une situation de stations cachees . . . . . . . . . . . . . . . . . . . . . . . . 151.5 Zones de communication et de detection de porteuse . . . . . . . . . . . . . 16

2.1 Recherche de route dans AODV . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.1 Voisinage dans la zone de detection de porteuse . . . . . . . . . . . . . . . . 293.2 Inequite d’acces au medium . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.3 Bande passante residuelle du lien (A,B) en fonction du debit sur le lien (C,D) 32

4.1 Occupation medium percue par le nœud s . . . . . . . . . . . . . . . . . . . 364.2 Pire cas : desynchronisation totale entre emetteur et recepteur . . . . . . . . 374.3 Meilleur cas : synchronisation totale entre emetteur et recepteur . . . . . . . 384.4 Cas general : synchronisation partielle entre emetteur et recepteur . . . . . . 384.5 Estimation de la synchronisation du lien (C, D) . . . . . . . . . . . . . . . . 404.6 Bande passante residuelle du lien (C, D) obtenue par synchronisation . . . . 414.7 Probabilite de collision au niveau du nœud B . . . . . . . . . . . . . . . . . . 424.8 Precision de la probabilite de collision interpolee sur un scenario aleatoire . . 444.9 Retransmissions d’un paquet ayant subit des collisions . . . . . . . . . . . . 464.10 Influence de la synchronisation pour QOLSR . . . . . . . . . . . . . . . . . . 484.11 Stations cachees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.12 Fonctionnement du protocole ABE . . . . . . . . . . . . . . . . . . . . . . . 514.13 Etablissement d’une route QoS . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.1 Un premier scenario simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.2 Debits obtenus par les deux flux concurrents avec AODV et ABE . . . . . . 595.3 Scenarios aleatoires - Debits obtenus avec AODV, AAC, BRuIT et ABE pour

des communications a un saut radio . . . . . . . . . . . . . . . . . . . . . . . 615.4 Scenarios aleatoires - Debits obtenus avec AODV, AAC, QoS AODV, BRuIT

et ABE pour des communications multi-sauts . . . . . . . . . . . . . . . . . 645.5 Quantite de trafic agrege en Mo a travers le reseau . . . . . . . . . . . . . . 655.6 Graphe des chemins reserves pour les flux QoS . . . . . . . . . . . . . . . . . 66

121

TABLE DES FIGURES

5.7 Debits obtenus avec AODV, AAC, ABE et BRuIT en cas de mobilite . . . . 675.8 Nombre total de messages de controle necessaires pour l’etablissement et la

maintenance des routes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695.9 Evaluation de la metrique β avec les protocoles AAC, QoS-AODV, BRuIT et

ABE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

6.1 Communication inter-couches . . . . . . . . . . . . . . . . . . . . . . . . . . 796.2 Exemple de differenciation de flux . . . . . . . . . . . . . . . . . . . . . . . . 816.3 Reception d’un paquet RREQ . . . . . . . . . . . . . . . . . . . . . . . . . . 836.4 Architecture interne d’un nœud DRBT . . . . . . . . . . . . . . . . . . . . . 846.5 Les 2 paires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 866.6 Debits obtenus par les deux flux avec AODV, ABE, DRBT et QPART . . . 876.7 Debits obtenus avec AODV, ABE, DRBT et QPART . . . . . . . . . . . . . 886.8 Taux d’acceptation des flux QoS avec les protocoles AODV, ABE, QPART et

DRBT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

7.1 Modelisation d’un nœud 802.11 par une file M/M/1/K . . . . . . . . . . . . 957.2 Processus de Markov representant le nombre de paquets dans la file . . . . . 967.3 Nombre moyens de retransmissions en fonction de la probabilite de collision

pour C = 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997.4 Comparaison entre delai moyen theorique et delai moyen reel . . . . . . . . . 1027.5 Chaıne de transmission a 4 sauts . . . . . . . . . . . . . . . . . . . . . . . . 1037.6 Delai moyen theorique et delai moyen reel pour une chaıne a 4 sauts . . . . . 1037.7 Delai moyen des flux avec les protocoles AODV et DEAN . . . . . . . . . . . 1057.8 Evaluation de la metrique α avec les protocoles DEAN et AODV . . . . . . . 1077.9 Pile protocolaire mises en place . . . . . . . . . . . . . . . . . . . . . . . . . 108

122

Liste des tableaux

4.1 Erreur relative due a l’ interpolation . . . . . . . . . . . . . . . . . . . . . . 43

5.1 Parametres generaux pour les simulations . . . . . . . . . . . . . . . . . . . . 585.2 Debits des flux CBR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605.3 Debits des flux CBR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625.4 Taux de perte global dans le reseau . . . . . . . . . . . . . . . . . . . . . . . 635.5 Debits des flux CBR en cas de mobilite . . . . . . . . . . . . . . . . . . . . . 655.6 Quantite de trafic agrege et taux de perte en cas de mobilite . . . . . . . . . 685.7 Valeur de β pour des tailles de paquets de 1000 et 1500 octets . . . . . . . . 72

6.1 Debits desires et type de flux . . . . . . . . . . . . . . . . . . . . . . . . . . 89

7.1 Parametres generaux pour les simulations . . . . . . . . . . . . . . . . . . . . 1017.2 Delais moyens obtenus avec DEAN et AODV . . . . . . . . . . . . . . . . . . 1067.3 Valeur de α avec les protocoles CBR et FTP . . . . . . . . . . . . . . . . . . 1087.4 Taux de perte en % avec les protocoles CBR et FTP . . . . . . . . . . . . . 109

123

Documents

Thèses de l'INSA de Lyon | Les Thèses de l'INSA de …theses.insa-lyon.fr/publication/2007ISAL0046/these.pdfrecherches sur les r´eseaux ad hoc ont suscit´e un tel engouement qu’un