Pfe-said El Kafhali

Université Hassan 1er

Faculté des Sciences et TechniquesSETTAT

MEMOIRE

Présenté pour l’obtention du diplôme du

Master Sciences et Techniques

S p é c i a l i t é : I n g é n i e r i e M a t h é m a t i q u e s e tI n f o r m a t i q u e

Sujet

Etude et comparaison des mécanismes de gestion active des

files d’attente

Réalisé Par

Said EL KAFHALI

Soutenu le 22 Juillet 2009 devant le jury composé de :

Mr Hassan Essoufi Pr. à la FST de Settat Président

Mr Amine Berqia Pr. à l’ENSIAS, Rabat Examinateur

Mr Driss El Ouadghiri Pr. à la Faculté des Sciences de Meknès Examinateur

Mr Abdelkrim HAQIQ Pr. à la FST de Settat Encadrant

Année Universitaire : 2008-2009

Dédicace

S’il n’y avait pas d’hiver, le printemps ne serait pas si agréable: Si nous ne goûtions pas à

l’adversité, la réussite ne serait pas tant appréciée.

Anne Bradstreet

Dédicace

À ma mère & mon père

Vous êtes pour moi une source de vie car sans vos sacrifices, votre tendresse et votre

affection je ne pourrais arriver jusqu’au bout. Je me réjouis de cet amour filial. Que Dieu

vous garde afin que votre regard puisse suivre ma destinée.

À mes frères & mes sœurs

Mon amour à votre égard est une grandeur non quantifiable.

À tous les membres de ma famille

À mes professeurs

À mes amis

En leurs souhaitant le succès dans leur vie aussi bien professionnelle que familiale.

À tous ceux qui me sont chères

À tous ceux pour qui je compte et qui comptent pour moi

À tous ceux qui se sentent participants dans ma réussite

« Que dieu vous garde »

Je dédie ce travail, à titre de reconnaissance

Remerciements

Remerciements

Ce projet est le fruit de travail entrepris sous la direction de Mr. Abdelkrim HAQIQ,

professeur à la FST de Settat. Je tiens à lui exprimer ma plus grande reconnaissance pour la

confiance, l’écoute et le soutien qu’il m’a accordés tout au long de la réalisation de ce

projet. Je le remercie vivement pour les nombreuses discussions, pour la gentillesse dont il a

toujours fait preuve à mon égard et notamment pour les encouragements qu’il n’a cessé de

me faire tout au long de ce travail. Qu‘il trouve ici mes véritables considérations.

Je suis très sensible à l’honneur que me fait Mr. Hassan Essoufi, professeur à la

FST de Settat, d’avoir bien voulu accepter de présider le jury de ma soutenance. Que ce

travail soit pour moi l’occasion de lui exprimer ma grande estime.

Je tiens aussi à remercier vivement Mr. Amine Berqia, professeur à l'ENSIAS,

Rabat, et Mr. Driss El Ouadghiri, professeur à la faculté des Sciences de Meknès, d’avoir

acceptés de siéger à mon jury de soutenance. Je considère leur présence parmi le jury comme

un témoignage de haute valeur et je suis heureux de leur exprimer ma profonde gratitude.

Je remercie vivement tous les professeurs qui ont enseigné dans le programme du

Master Sciences et Techniques “Ingénierie Mathématiques et Informatique”, et

particulièrement Mr. Khalid Allali, Mr. Mohamed Bahaj, Mr. Abdelkrim Haqiq, Mr.

Bouchaib Radi et Mr. Hassan Essoufi.

Je remercie également l’équipe de recherche du professeur Abdelkrim Haqiq, et plus

particulièrement Mr. Mohamed Hanini, qui m'a, à plusieurs reprises, témoigné de son

soutien et son aide.

Je remercie sincèrement tous mes camarades, étudiants à la FST de Settat et

particulièrement tous les étudiants du Master « Ingénierie Mathématique et Informatique »

pour leur amicale et efficace collaboration tout le long de cette formation.

Je garde une place toute particulière à ma famille : ma mère Aicha, mon père Ali, et tous

mes frère et sœurs. Je voudrais leur exprimer toute ma profonde reconnaissance et je leur

remercie du fond de mon cœur car ils m’ont constamment aidé, par leur soutien moral et leur

encouragement pour achever ce projet.

Résumé

Résumé

Pour éviter la congestion dans les réseaux Internet, due à l’accroissement du trafic qui

transite par ces réseaux, on utilise des buffers (files d’attente) dans les routeurs pour absorber

l’excès du trafic lorsque le débit offert dépasse la capacité de transmission. Mais l’espace limité

de ces buffers, entraîne la perte des paquets d’informations au cours du temps.

Les mécanismes de gestion des files d’attente se sont avérés d’une grande utilité pour éviter

la congestion des buffers. Ces mécanismes se diffèrent par la méthode de sélection des

paquets rejetés. On distingue alors deux catégories de mécanismes : les mécanismes passifs (PQM

: Passive Queue Management) et les mécanismes actifs (AQM: Active Queue Management).

Dans ce mémoire, on propose de faire une étude des différents mécanismes de gestion active

des files d’attente, notamment le mécanisme RED (Random Early Detection) et ses variantes, et

de faire ensuite une comparaison des performances de ces mécanismes.

Pour montrer l’utilité de ces mécanismes pour l’amélioration de la qualité de service

dans les réseaux Internet, on présente l’évaluation des performances du protocole MAODV

(Multicast Ad hoc On-Demand Distance Vector) par l’utilisation de certains mécanismes de

gestion active de files d’attente dans les réseaux Ad hoc.

Mots clés: Réseaux Internet, Congestion, Files d’attente, Réseaux Ad hoc, Gestion active des files

d’attente, RED.

Abstract

Abstract

To avoid congestion in Internet networks, due to increased traffic which transits

among them, we use buffers (Queues) in routers to handle the excess of traffic when the debit

exceeds the transmission capacity. But the limited space of these buffers, cause the loss of

packets of information over time.

Management mechanisms queues have great utilities to avoid buffers congestion.

These mechanisms differ in the method of selection of discarded packets. We distinguish two

categories of mechanisms: passives mechanisms (PQM: Passive Queue Management) and

actives mechanisms (AQM: Active Queue Management).

In this work, we propose to make a study of different mechanisms for the active queues

management, including the RED mechanism (Random Early Detection) and its variants, and

to compare their performances.

In order to show the importance of these mecanisms to improve the quality of service

in the Internet networks, we present the performances of the protocol MAODV (Multicast Ad

hoc On-Demand Distance Vector) bay using some Active Queue Management mechanisms in

the Ad hoc networks.

Keywords: Internet Networks, Congestion, Queues, Ad hoc Networks, Active Queues

Management, RED.

Table des Matières

5

Table des Matières

GLOSSAIRE ......................................................................................................................................................... 7

CHAPITRE 1 : INTRODUCTION ET MOTIVATION ................................................................................. 10

CHAPITRE 2 : CONTROLE DE CONGESTION .......................................................................................... 14

1- INTRODUCTION ............................................................................................................................................. 152- LE PROBLEME DE CONGESTION ..................................................................................................................... 153- LE CONTROLE DE CONGESTION ..................................................................................................................... 164-CERTAINS PARAMETRES DE PERFORMANCE POUR LE CONTROLE DE CONGESTION ......................................... 19

4.1- Le taux de perte de paquets.................................................................................................................. 194.2- Le débit................................................................................................................................................. 194.3-Le délai d’attente................................................................................................................................... 194.4- La taille moyenne de la file d’attente ................................................................................................... 20

CHAPITRE 3 : ETAT DE L’ART DES MECANISMES DE GESTION ACTIVE DES FILESD’ATTENTE (AQM).......................................................................................................................................... 21

1- INTRODUCTION ............................................................................................................................................. 222- PRESENTATION DE CERTAINS MECANISMES DE LA GESTION ACTIVE DES FILES D’ATTENTE ........................... 22

2.1- RED (Random Early Detection)........................................................................................................... 222.2- GRED (Gentle RED) ............................................................................................................................ 242.3- ARED (Adaptative RED)...................................................................................................................... 252.4- BLUE.................................................................................................................................................... 262.5- Stabilized RED (SRED)........................................................................................................................ 262.6- Random Exponential Marking (REM).................................................................................................. 292.7- Double Slope RED (DSRED) ............................................................................................................... 302.8- RED with In and Out............................................................................................................................ 312.9- CHOKe................................................................................................................................................. 322.10- Weighted Random Early Detection (WRED)...................................................................................... 342.11- Dynamic-RED (DRED) ...................................................................................................................... 352.12- Flow Random Early Drop (FRED) .................................................................................................... 352.13- Selective Fair Early Detection (SFED).............................................................................................. 362.14- Balanced RED (BRED) ...................................................................................................................... 372.15- Adaptive Virtual Queue (AVQ)........................................................................................................... 392.16- GREEN (Generalized Random Early Evasion Network).................................................................... 402.17- LRED (Loss Ratio based RED) .......................................................................................................... 422.18- Proportional Integral controller (PI controller) ............................................................................... 44

3- CONCLUSION................................................................................................................................................. 45

CHAPITRE 4 : COMPARAISON DES MECANISMES DE GESTION ACTIVE DES FILESD’ATTENTE (AQM).......................................................................................................................................... 46

1- COMPARAISON DES PERFORMANCES DE TD, RED ET REM .......................................................................... 472- COMPARAISON DES PERFORMANCES DE RED, ARED ET BLUE................................................................... 473- COMPARAISON DES PERFORMANCES DE TD, GREEN ET FRED ................................................................... 484- COMPARAISON DES PERFORMANCES DE RED, PI, AVQ ET REM.................................................................. 495- COMPARAISON DES PERFORMANCES DE DT, RED, BLUE, REM ET PI......................................................... 506- COMPARAISON DES PERFORMANCES DE CHOKE, FRED, RED ET SFED ..................................................... 507- COMPARAISON DES PERFORMANCES DE DT, RED, REM ET AVQ................................................................ 50

CHAPITRE 5 : UTILISATION DE CERTAINS MECANISMES DE GESTION ACTIVE DES FILESD'ATTENTE POUR LE ROUTAGE DANS LES RESEAUX AD HOC....................................................... 52

1- INTRODUCTION ............................................................................................................................................. 532- LES RESEAUX AD HOC (MOBILE AD HOC NETWORK) ................................................................................... 53

2.1- Les caractéristiques des réseaux Ad hoc.............................................................................................. 532.2- Les protocoles de routage .................................................................................................................... 542.3- Communication dans les réseaux Ad hoc............................................................................................. 572.4- Gestion d’énergie en mode Ad-hoc ...................................................................................................... 58

3- L’EVOLUTION DES PERFORMANCES DU PROTOCOLE MAOVD PAR L’UTILISATION DE CERTAINS MECANISMES

DE GESTION ACTIVE DES FILES D’ATTENTE DANS LES RESEAUX AD HOC ........................................................... 58

Table des Matières

6

3.1- Description du protocole MAODV....................................................................................................... 583.2- Amélioration des performances de MAODV par la gestion active des files d’attente ......................... 59

CONCLUSION ET PERSPECTIVES .............................................................................................................. 63

ANNEXE A : RESULTATS DE SIMULATION ............................................................................................. 66

ANNEXE B : PRESENTATION DU SIMULATEUR NS-2 .......................................................................... 76

1- INTRODUCTION ............................................................................................................................................. 772- ORGANISATION DU SIMULATEUR NS-2 ......................................................................................................... 773- PRESENTATION DE TCL ................................................................................................................................. 784- PRESENTATION DE OTCL .............................................................................................................................. 795- ARCHITECTURE DU RESEAU .......................................................................................................................... 80

5.1-Nœuds de réseau.................................................................................................................................... 805.2- Liens de communication entre les réseaux ........................................................................................... 815.3- Agents de communication..................................................................................................................... 815.4- Applications.......................................................................................................................................... 82

6- PRINCIPE D’UTILISATION............................................................................................................................... 82

BIBLIOGRAPHIE ET WEBOGRAPHIE........................................................................................................ 84

Glossaire

7

Glossaire

Glossaire

8

AODV : Ad Hoc On-Demand Distance-Vector Protocol

AQM : Active Queue Management

ARED : Adaptative RED

ATIM : Ad-Hoc Traffic Information Map

ATM : Assynchrone Transfer Mode

AVQ : Adaptive Virtual Queue

BRED : Balanced Random Early Detection

CBR : Constant Bit Rate

CCDF : Cumulative Ccomplementary Distribution Function

CHOKe : CHOose and Keep the responsitive flows, CHOose and Kill the

unresponsitive flows

DiffServ: Differentiated Services

DRED : Dynamic Random Early Detection

DSDV : Destination-Sequenced Distance Vector Protocol

DSR : Dynamic Source Routing

DSRED : Double Slope RED

ECN : Explicit Congestion Notification

EWMA : Exponential Weighted Moving Average

FQ : Fair Queuing

FRED : Flow Random Early Drop

FSR : Fish-eye State Routing

FTP : File Transfert Protocol

GRED : Gentle RED

GREEN : Generalized Random Early Evasion Network

HTML : Hyper Text Markup Language

HTTP : Hyper Text Transfert Protocol

IETF : Internet Engeneering Task Force

IntServ : Integrated Services

LRED : Loss Ratio based RED

MANET : Mobile Ad hoc NETwork

MAODV : Multicast Ad hoc On-Demand Distance Vector

NAM : Network Animator

Glossaire

9

NS : Network Simulator

OLSR : Optimized Link State Routing Protocol

OTcl : Object Tool Command Language

PQM : Passive Queue Management

QdS : Qualité de Service

QoS : Quality of Service

RED : Random Early Detection

REM : Random Exponential Marking

RERR : Route Error

RIO : RED with In and Out

RREP : Route Reply

RREQ : Route Request

RTT : Round Trip Time

RTT : Round Trip Time

SFED : Selective Fair Early Detection

SMTP : Simple Mail Transfert Protocol

SNMP : Simple Network Management Protocol

SRED : Stabilized RED

STARA: System and Traffic dependent Adaptive Routing Algorithm

TBRPF : Topology Broadcast Based on Reverse-Path Forwarding

TCP/IP : Transport Control Protocol / Internet Protocol

TD : Tail Drop

TO : Time Out

TORA : Temporally Ordered Routing Algorithm

WRED : Weighted Random Early Detection

WWW : World Wide Web

ZRP : Zone Routing Protocol

Chapitre 1 : Introduction et motivation

10



11

Aujourd'hui dans les réseaux Internet, la retransmission des paquets due à une

expiration des horloges ou à la perte de paquets ou encore à la taille limitée des files d'attente,

sont les différentes causes de la congestion au niveau des routeurs. Cette congestion sera par

la suite la cause de longs délais de bout en bout. Et le service ne peut pas assurer une qualité

de service (Quality of Service : QoS) suffisante pour les applications temps réel. Pour ces

applications le délai d’attente, la perte des paquets et le débit ont une importance pour garantir

la performance. Diverses approches ont été proposées dans la littérature pour garantir une

qualité de service aux applications ayant de telles contraintes de QoS. La plus encourageante

est une solution qui se base sur un marquage/suppression des paquets avant que la file

d’attente soit pleine avec un traitement différencié. La complexité est écartée dans les

extrémités du réseau. Le cœur du réseau est laissé aussi simple que possible. L'architecture de

qualité de service DiffServ (Differentiated Services) s'appuie sur cette dernière approche pour

garantir une qualité de service aux applications temps réel.

Le contrôle de congestion dans les files d’attente, désigne l’ensemble des actions du

réseau qui permettent de minimiser l’intensité et les effets d’un éventuel état de congestion.

Pour réaliser ce contrôle plusieurs algorithmes ont été proposés dans la littérature, leur

rôle commun est de décider quand et comment éliminer des paquets afin d’éviter la

congestion du réseau [66].

La performance d’un tel algorithme peut être évaluée par sa capacité à contrôler le

trafic d’une manière efficace garantissant une quantité de service acceptable pendant les

périodes de congestion. Tail Drop (TD) est le mécanisme classique pour gérer les files

d’attente, ce mécanisme n’élimine les paquets que lorsque la taille maximale du buffer est

atteinte.

La technique TD permet d’écouler en priorité les paquets qui arrivent en premier dans

la file d’attente. Si la longueur de celle-ci atteigne la taille maximale, les nouveaux paquets

qui arrivent sont automatiquement éliminés. L’état de saturation est, trivialement, dû au

phénomène suivant : le débit d’arrivée des paquets dans la file est supérieur au débit de sortie.

Cette méthode est utilisée par défaut, mais s’avère inadéquate lorsque la charge sur le routeur

est intense car elle génère une file d’attente engorgée ainsi que de grandes pertes de paquets.

En dépit de la simplicité d’implémentation de TD, ce mécanisme présente quelques

inconvénients :


12

Il ne permet pas de distinguer la priorité des trafics.

Il entraîne une diminution de l’utilisation du réseau, due à la synchronisation entre les

différentes connexions qui subissent des pertes au même moment et ralentissent

simultanément leurs débits.

Il pénalise les flux qui envoient le trafic en rafles, et peut conduire à une

monopolisation du lien par certaines connexions.

Il entraîne des délais d’attente relativement longs.

Pour remédier aux inconvénients du TD, les mécanismes de gestion active des files

d’attente (AQM) adoptent une approche préventive en éliminant les paquets avant la

saturation du buffer, et ceci avec une probabilité dépendant de la taille de la file. Ceci permet

d’éviter la saturation de la file d’attente en avertissant l’émetteur que la file est quasi-remplie

pour réduire son débit et rejette des paquets avant que la file soit pleine.

Plusieurs AQM ont été proposés dans la littérature ; Floyd et Jacobson présentaient

l’algorithme RED (Rondom Early Detection) [24], dont plusieurs variantes améliorées ont été

ensuite proposées.

Le problème de congestion des paquets dans les réseaux Internet aura une influence

grave sur les performances de ces réseaux.

Les algorithmes de type AQM (Active Queue Management) sont inspirés de RED

(Random Early Detection), leur point commun est de provoquer des pertes anticipées pour

contrôler les utilisateurs de TCP Reno qui forment le flux élastique des routeurs. Tous ces

algorithmes ont un problème en commun, c’est qu’ils sont très difficiles à régler au vu de la

grande variété des situations possibles. De sorte que si RED est aujourd’hui implémenté dans

tous les routeurs, il n’est presque jamais activé. Rappelons de plus que sur le plan de la

conception des réseaux, l’utilisation de RED a de nombreux opposants du fait que le réseau

pénalise indifféremment tous les utilisateurs en détruisant des paquets pour contrôler

uniquement certains d’entre eux qui utilisent un protocole qui pourrait bien disparaître un

jour. Il convient donc de réserver les usages des AQM aux cas où la congestion s’avère aigue

et en différenciant le trafic élastique des autres types de données échangées [39].

L’objectif de ce travail est de faire une présentation détaillée des différents

mécanismes de gestion active des files d’attente ainsi qu’une étude comparative et critique de

ces mécanismes.


13

Certains de ces mécanismes ont été utilisés à la fin de ce travail pour évaluer les

performances du protocole MAODV (Multicast Ad hoc On-Demand Distance Vector) dans un

réseau Ad hoc.

Le reste de ce mémoire est organisé comme suit : dans le chapitre 2 nous présentons

une étude générale sur le contrôle de congestion. Dans le chapitre 3 on présente certains

mécanismes de gestion active des files d’attente. Dans le chapitre 4, notre contribution porte

sur la comparaison des performances des mécanismes de gestion active des files d’attente

étudiés. Le chapitre 5 est consacré à l’utilisation de certains mécanismes de gestion active des

files d'attente pour le routage dans les réseaux Ad hoc. Ensuite, une conclusion générale et

des perspectives sont données. Enfin, on donne deux annexes, la première présente les

résultats des simulations des différents mécanismes de gestion active des files d’attente

présentés dans ce projet et la deuxième donne une brève présentation du logiciel de simulation

NS (Network Simulator).

Chapitre 2 : Contrôle de congestion

14



15

1- Introduction

Aujourd’hui, la consommation de la bande passante sur Internet a explosé, surtout par

l’implantation des services audio et vidéo qui génèrent de très hauts débits, et également par

le nombre d’utilisateurs qui ne cesse d’augmenter. Ceci ne peut qu’encombrer la bande

passante, engendrer des délais très importants de transfert et donc dégrader dangereusement la

qualité de service du réseau. D’où la nécessité de contrôler la congestion par des mécanismes

bien spécifiés, afin d’éviter l’écroulement des performances d’un réseau lorsque la charge sur

celui-ci devient importante.

Le contrôle de congestion dans les réseaux Internet est une action cruciale permettant

d’assurer l’acheminement optimal des paquets et de garantir la qualité de service du réseau.

Reposant sur le principe de bout en bout, TCP s’avère le protocole le plus fiable, capable de

pallier les inconvénients de la congestion par le biais de différents mécanismes. A savoir, la

technique la plus basique « le fenêtrage » et l’implantation des différentes phases du transfert

TCP.

Les services avancés des réseaux Internet sont nécessaires pour transférer des

informations précises vers des destinations correctes, en temps réel. Donc il faut que ces

réseaux supportent des grandes quantités d’informations et permettent de les échanger entre

les différents partenaires. Pour cela il est judicieux d’augmenter la qualité de service (QoS)

qui garantie la performance et démunie la perte d’informations entre le destinataire et

l’émetteur.

2- Le problème de congestion

La congestion d’un réseau correspond à un phénomène de goulot d’étranglement

lorsque des points de trafic dépassent la capacité du réseau. En particulier, la congestion du

réseau peut se produire lorsque la capacité de lien d’entrée est plus grande que la capacité de

lien de sortie. La congestion également se produit lorsque de multiples flux d’entrée

parviennent à un routeur dont la capacité de sortie est inférieure à la somme des entrées. S’il y

a n sources avec un débit D pour un réseau ayant un lien offrant un débit qui est inférieur à

nD, une congestion du réseau se produit [37]. Et plus précisément les problèmes de

congestion arrivent lorsque les nœuds d’un réseau saturent leurs files d’attente comme le

montre la figure ci-dessous.


16

Figure 1 : Problème de congestion dans un réseau

La congestion est définie comme l'état des équipements du réseau, dans lequel le

réseau n'est pas en mesure de satisfaire les objectifs négociés en matière de performance pour

les connexions déjà établies ou pour de nouvelles demandes d'établissement de connexion. De

plus elle provoque des pertes de paquets, pertes qui peuvent s'avérer excessives vis-à-vis de

la qualité de service ( Quality of Service) négociée avec les applications, et la saturation des

espaces de stockage des paquets, saturation qui peut entraîner des temps de transfert des

paquets inacceptables vis-à-vis de la qualité de service négociée avec les applications [9].

Lorsque le débit diminue, il faut plus de temps pour télécharger une page. Ce faisant la

proportion du temps que l’on passe à télécharger par rapport au temps pendant lequel on lit

devient de plus en plus grande. Ceci explique le phénomène d’auto-amplification de la

congestion. D’autre part la file d’attente ne sert à rien dans cet exemple à part à augmenter le

temps de transmission, ce qui permet des fenêtres plus grandes pour le même débit. Dans tous

les cas, on est ici face à un problème de congestion sévère, la seule solution pour l’éviter est

d’augmenter le débit disponible ou de diminuer le nombre d’utilisateurs [39].

Les problèmes de congestion entrainement des risques de rejet pour les paquets en

attente d’acheminement : le routeur stocke et traite les paquets en cours de transit en fonction

de leur ordre d’arrivée et des ressources disponibles. Les limites de capacités des mémoires

tampon et les délais maximums de transmission d’un paquet peuvent induire des rejets

d’informations, non pas parce que les paquets sont erronés mais parce que les paquets n’ont

pas pu être traités dans le temps imparti. Ces rejets, liés à des problèmes de capacité de

l’infrastructure de communication, imposent de retransmettre l’information et peuvent donc

aggraver les problèmes de congestion [37].

3- Le contrôle de congestion

Le contrôle de congestion est un mécanisme visant à adapter les sources de trafic aux

conditions variables du réseau. Ainsi, lorsqu'une congestion se produit, suite à une


17

augmentation de la charge du réseau, le contrôle de congestion doit en aviser les sources pour

qu'elles adaptent leur trafic afin d'éviter la congestion ou la réduire [66].

La gestion des congestions, l’un des problèmes cruciaux du travail en réseau, est

usuellement traitée par le destinataire final des informations grâce à des algorithmes

appropriés. Dans l’implantation actuelle des réseaux Internet, le niveau transport,

particulièrement le protocole TCP, est fortement pénalisé du fait du fort taux de pertes de

paquets, pertes souvent liées à l’expiration de leur durée de vie, notamment pendant les

périodes de congestion du réseau ce qui affecte le niveau de Qualité de service (QoS). Pour

répondre à ces problèmes, une démarche en deux temps a été proposée [37]:

Une modélisation du fonctionnement des équipements d’interconnexion et du trafic

généré par des applications types qui doit permettre à terme de mieux appréhender les

performances de l’infrastructure de communication.

Un algorithme de gestion de congestion implanté sur des nœuds névralgiques peut

permettre, en équilibrant les charges, d’augmenter le niveau de qualité de service global et

pénalisant le moins possible les flux peu agressifs.

Plusieurs techniques sont utilisées pour le contrôle de congestion, dont le feedback et

l’adaptation :

Le feedback : est utilisée pour contrôler l'état du réseau et en aviser l'émetteur. Le

plus important signal de feedback est le signal de congestion par lequel une application

détecte qu'un certain nombre de ses paquets ont été éliminés par le réseau. Ce mécanisme peut

être implicite, lorsque le réseau élimine simplement les paquets en excès, ou explicite, lorsque

le réseau notifie à l'application la présence d'une congestion. Le protocole TCP utilise un

feedback implicite. Le TCP émetteur détecte la présence d'une congestion suite à l'expiration

d'un temporisateur d'acquittement, ou suite à la réception d'un double acquittement (duplicate

acknowledgement) envoyée par le TCP récepteur ayant détecté une perte de paquets [66].

L’adaptation : Le mécanisme d'adaptation est la suite logique du feedback.

Lorsqu'une situation anormale est détectée dans le réseau, le mécanisme d'adaptation modifie

le trafic pour l'adapter aux nouvelles conditions du réseau. Les mécanismes slow-start et

congestion avoidance du protocole TCP sont des formes d'adaptation. Lorsqu'une congestion

est détectée suite à une perte de paquets, TCP modifie son débit d'émission afin d'éviter une

telle congestion. Ce mécanisme suppose que toutes les sources se comportent de la même


18

façon pour maximiser l'utilité du réseau, ce qui n'est pas le cas. En effet, les applications

temps-réel n'adaptent pas leur débit d'émission à l'état du réseau, et la congestion est contrôlée

grâce aux sessions TCP qui réduisent leur débit d'émission. Le réseau peut forcer l'adaptation

du trafic par l'intermédiaire de mécanismes mis en œuvre dans les routeurs d'accès (edge

routers) tels le lissage de trafic (trafic shaping) ou la surveillance de trafic (trafic policing) qui

procèdent par retardement, marquage ou élimination de certains paquets. Ces mécanismes

sont efficaces puisqu'ils ne supposent pas que l'utilisateur adaptera son débit d'émission de son

propre gré [66].

Deux objectifs opposés et contradictoires peuvent être attribués au contrôle de

congestion, le premier est relatif au service offert aux applications, le second est relatif à

l'optimisation du réseau. Le premier objectif est de garantir pour chaque connexion la qualité

de la transmission des données en terme, par exemple, de taux de perte des paquets et de délai

de transfert. Le deuxième objectif est de gérer de manière optimale les ressources du réseau

afin de servir le plus d'applications possibles au mieux.

Les mécanismes mis en œuvre pour assurer le contrôle de congestion doivent posséder

les propriétés suivantes : la flexibilité, l'efficacité, la robustesse. La flexibilité permet au

contrôle de congestion de s'adapter aux différents types de qualité de service demandé par les

applications. L'efficacité, grâce à une utilisation de mécanismes de contrôle de congestion

simples (peu complexes) et systématiques (homogènes), permet l'utilisation maximum des

ressources disponibles du réseau. La robustesse assure une conservation de l'offre des services

de transmission en toutes circonstances [9].

Deux grandes classes de mécanismes de contrôle de congestion peuvent être

discernées : la classe des mécanismes passifs (réactifs) et celle des mécanismes actifs

(préventifs).

Les mécanismes passifs: Ce sont des mécanismes qui réagissent après l’apparition de la

congestion. Ils consistent à rejeter les paquets quand les files d’attente sont pleines. L’idée de

base est d’agir en fonction de l'évolution de l'état du réseau selon le degré de congestion

attient. La mesure de la congestion peut se faire de plusieurs manières (en mesurant les pertes,

les délais, le remplissage des buffers, etc.) par le réseau ou par les équipements terminaux. Si

une congestion se déclare la source diminue son débit. Le principe du contrôle passif est de

pouvoir partager les ressources par le maximum de connexions pour optimiser l'utilisation du

réseau. De ce fait, ce type de contrôle peut être approprié aux connexions de données qui


19

peuvent s'adapter aux conditions du réseau. Cependant, il n'est pas adapté aux connexions qui

nécessitent une garantie de qualité de service tel que les services vidéo en temps réel.

Les mécanismes actifs : Ce sont des mécanismes qui permettent de prévenir la congestion.

Qui déterminent la réaction des routeurs face au remplissage de leur file d’attente. En effet ils

consistent à prendre des mesures a priori, visant à minimiser les chances de l’apparition d’une

congestion et de protéger le réseau contre les rafales de données, et ce afin de pouvoir assurer

une qualité de service satisfaisante. Nous verrons ces mécanismes plus loin dans le chapitre 3.

4-Certains paramètres de performance pour le contrôle de congestion

4.1- Le taux de perte de paquets

Le taux de perte de paquets représente la quantité d’informations rejetée pour cause

d’erreur de transmission. les pertes sont généralement dues soit au non-fiabilité des liens physiques

soit aux mécanismes de gestion des files d’attente dans les routeurs intermédiaires qui se trouvent

souvent obligés d’éliminer des paquets pour faire face à des situations de congestion. Ce facteur est

très important. En effet, certaines applications ne tolèrent pas des valeurs élevées de ce facteur.

4.2- Le débit

Le débit définit le nombre maximum d’informations qui doit être transporté sur une

connexion de réseau dans un temps long. C’est la quantité d’informations transmise par unité

de temps. Les applications requérant un certain débit d’informations verront leurs

performances s’effondrer (temps d’attente long entre l’affichage de formulaire,…) ou

deviendront incompréhensible. C’est en fait le taux de transfert maximum pouvant être maintenu

entre deux points terminaux (un émetteur et un récepteur), ce facteur est influencé non seulement par

les capacités physiques des liens, mais aussi par les autres flux partageant ces liens.

4.3-Le délai d’attente

Le délai d’attente est le temps mis par un paquet pour aller de la machine émettrice

vers la machine réceptrice. C’est le temps écoulé entre l’envoi d’un paquet par l’émetteur et sa

réception par le destinataire, le délai tient compte du délai de propagation le long du chemin parcouru

par les paquets et du délai de transmission induit par la mise en file d’attente des paquets dans les

systèmes intermédiaires (les routeurs). La plupart des applications et surtout les applications temps

réel sont très sensibles aux valeurs élevées de délais et exigent un délai limité pour qu’elles puissent

fonctionner correctement.


20

4.4- La taille moyenne de la file d’attente

La taille moyenne de la file d’attente est le nombre des paquets qui occupent le buffer

d’attente lorsque l’interface de sortie d’un routeur est pleine.

Chapitre 3 : Etat de l’art des mécanismes de gestion active des files d’attente (AQM)

21

Chapitre 3 : Etat de l’art des mécanismes de gestionactive des files d’attente (AQM)


22

1- Introduction

La gestion active des files d’attente est un axe de recherche d’actualité qui présente un

intérêt croissant attirant de plus en plus d’équipe de recherche.

La gestion active des files d'attente adoptent une approche préventive en éliminant les

paquets avant la saturation du buffer, et ceci avec une probabilité dépendant de la taille de la

file. Sa performance peut être évaluée par sa capacité à contrôler le trafic de manière équitable

et efficace pendant les périodes de congestion contrairement au TCP qui permet d’informée

les sources d’ajuster leurs taux de transmission selon le degré de congestion. Les mécanismes

de gestion des files d'attente sont nécessaires dans les routeurs pour compléter les mécanismes

de contrôle de congestion.

2- Présentation de certains mécanismes de la gestion active des filesd’attente

2.1- RED (Random Early Detection)

Le RED a été proposé par S. Floyd et V. Jacobson en 1993 [24]. Son objectif est,

d’une part, de contrôler la longueur de la file d’attente dans les buffers et d’autre part, d’éviter

les inconvénients du Drop Tail, pour lequel un buffer saturé entraîne la baisse des débits de

toutes les sources qui l’utilisant (problème de synchronisation).

Le mécanisme RED rejette les paquets entrants avec une certaine probabilité avant que

les buffers ne soient pleins [63]. Pour détecter la congestion, RED maintient une moyenne

mouvante qui est pondérée de manière exponentielle pour la longueur de la file d’attente à

l’aide de l’algorithme EWMA (Exponential Weighted Moving Average) [37].

Figure 2 : Évolution de la probabilité de perte de RED en fonction de la taille moyenne de lafile d'attente.


23

Le paramètre avg qui désigne la taille moyenne de la file d’attente est initialisé à 0, et

à chaque arrivée d’un paquet, avg prend la valeur :

(1 )q qavg w avg w q

où q est la taille réelle de la file d’attente et qw est le poids de la file d’attente, il intègre des

informations sur le nombre et la taille des paquets en attente.

Le RED fixe deux seuils thMin et thMax tels que th thMin Max . Quand la taille de la

file dépasse le seuil thMin , le RED commence à rejeter les paquets entrants avec la probabilité

P donnée par la formule ci-dessous. Cette probabilité croît linéairement en fonction de la

taille de la fille. Au-delà du seuil thMax , tous les nouveaux paquets entrants sont rejetés

comme le montre la figure 2.

th

0 si avg ,

si ;

1 si avg Max .

th

thP th th

th th

Min

avg MinP Max Min avg Max

Max Min

où pMax désigne la probabilité maximale de rejet de paquet.

L’algorithme simplifié de ce mécanisme est le suivant :

Pour chaque paquet reçuCalculer la taille moyenne de file avg

Si th thMin avg Max alors

Calculer la probabilité PMarquer/Supprimer le paquet avec la probabilité P

Sinon si thavg Max

Supprimer le paquet avec la probabilité PFin Si

Malgré sa politique de prévention de la congestion, l’algorithme RED présente

quelques problèmes, tels que :

La taille de la file ne donne pas d’indication sur le type de congestion.

Problème du choix adapté des paramètres de configuration.


24

Le système de gestion de la file RED est un exemple de modification du niveau réseau

seul (le système Tail Drop est remplacé par RED dans les routeurs). Les routeurs sont les

équipements qui subissent la congestion ; il n'y a qu'eux qui peuvent la voir venir

suffisamment tôt et envoyer le signal. La mise en place de ce mécanisme, ou d'un mécanisme

similaire, a pour objectif de prévenir la congestion en la signalant par une perte, avant que

celle-ci se produise [8].

2.2- GRED (Gentle RED)

Le GRED proposé dans [25] est une amélioration de RED, il adopte la même approche

que RED mais attarde le rejet des paquets on ajoutant un autre intervalle dans le calcule de la

probabilité de rejet, il s’en diffère par les points suivants :

100% de rejet des paquets est effectuée seulement quand avg est deux fois égale

au thMax .

Quand 2th thMin avg Max , le GRED commence à rejeter aléatoirement les paquets

entrants avec la probabilité Q donnée ci-dessous. Cette probabilité augmente de manière

linéaire par morceaux en fonction de la taille de la file.

0 si ,

si ;

(1 )( )si 2

1

th

thP th th

th th

P thp th th

th

avg Min

avg MinMax Min avg Max

Max MinQ

Max avg MaxMax Max avg Max

Max

thsi 2 .avg Max

Figure 3 : Évolution de la probabilité de perte de GRED en fonction de la taille moyenne de lafile d'attente.

Cette version de RED présente l’avantage de ne pas introduire de discontinuité dans la

dynamique d’évolution des pertes [39].


25

2.3- ARED (Adaptative RED)

L’idée de base pour une solution résolvant les problèmes de RED repose sur le ARED

original proposé par Feng et Al. en 2001 [26]. Ce mécanisme est conçu comme une adaptation

de l’algorithme RED il permet d’améliorer les performances de RED en adaptant le paramètre

pMax (la probabilité maximale de suppression) en fonction de la charge du trafic.

Si la taille moyenne de la file est proche de thMin , cela montre que la détection

précoce de la congestion est trop agressive. Dans ce cas, on faite décroître la valeur de

pMax d’un facteur constant α. D’autre part, si la taille moyenne est proche de thMax , cela

signifie que la détection précoce est trop conservatrice. Dans ce cas, la valeur de pMax est

augmentée d’un facteur constant β. Cependant, si la taille moyenne oscille bien

entre thMin et thMax , on ne change pas la valeur de pMax . Cette configuration de pMax fait en

sorte que la taille de la file d’attente oscille entre thMin et thMax [60].

L’algorithme ARED permet de rejeter préventivement des paquets pour offrir une

gestion proactive des congestions en fonction des besoins en bande passante des différentes

sources, et suppose que les équipements gèrent leur files de sortie selon une logique FIFO, ce

qui est le mode par défaut dans la plupart des cas [37].

L’algorithme de ce mécanisme est le suivant :

A chaque mise à jour de avg :

Si ( th thMin avg Max ) alors

statut= entre ;Fin SiSi( & & !thavg Min statut entre ) alors

statut = dessous ;/p pMax Max ;

Fin SiSi ( & & !thavg Max statut dessus ) alors

statut = dessus ;*p pMax Max ;

Fin Si

où et sont deux facteurs tous supérieurs à 1.


26

2.4- BLUE

Le BLUE a été proposé par Feng et Al. en 1999 [22]. C’est le premier mécanisme de

gestion active des files d’attente qui ne prend pas en compte la longueur de la file d’attente

pour calculer la probabilité de suppression des paquets. Il est utilisé pour améliorer les

performances de RED en termes d’estimation des paquets perdus et la taille du buffer du

réseau.

BLUE utilise la durée d’occupation du lien pour indiquer la congestion. Il entretient

une probabilité P pour marquer/ supprimer les paquets entrants. La probabilité P est

incrémentée par d1 quand le paquet est supprimé due à buffer overflow. Cette probabilité est

décrémenté par d2 quand la file d'attente est vide. L'intervalle minimal pour augmenter ou

diminuer la probabilité de marquage est configuré pour une _freeze time un intervalle pour

éviter de changer la probabilité de marquage de manière trop agressive.

L’algorithme de ce mécanisme est le suivant [60]:

Pour chaque paquet perdu :Si (( now-last_update) >freeze_time) alors

P=P+d1;last_update = now;

Fin SiPour chaque lien disponible:Si ((now-last_update) >freeze_time) alors

P=P-d2;last_update = now;

Fin SiPour chaque paquet arrivé :Marquer ou supprimer le paquet avec la probabilité P.

P : la probabilité utilisée pour marquer ou supprimer les paquets.

freeze_time : l’intervalle du temps minimal entre deux mises à jour successives de P.

d1 : la valeur d’incrémentation de P lorsque la file est pleine.

d2 : la valeur de décrémentation de P lorsque le lien est disponible.

now : la date courante du système.

last_udpdate : la date de la dernière mise à jour de P.

2.5- Stabilized RED (SRED)

SRED (Stabilized RED) c’est un mécanisme proposé par Ott et al. en 1999 [54]. Qui

permet de stabiliser la longueur de la file d’attente. Les oscillations de la file d'attente de RED


27

dépendent souvent du nombre de flux, alors SRED utilise une technique statistique pour

estimer le nombre de flux actifs afin d'éliminer cette dépendance.

SRED fonctionne comme suit: chaque fois qu'un nouveau paquet arrive, il est comparé

au hasard à un paquet qui a été reçu avant. Si les deux paquets appartiennent au même flux,

un «hit» est déclaré, et le nombre de «hit» est utilisé pour calculer l'estimation du nombre de

flux actifs. De plus, la file d'attente ne doit pas limiter la possibilité de remarquer que les

paquets vont ensemble, cette fonction n'est pas atteinte par le choix d'un paquet aléatoire du

buffer, alors une «zombie liste» est conservée à sa place.

Cela fonctionne comme suit: pour tous les paquets qui arrivent, un identificateur de

flux est ajouté à la liste avec un timestamp (temps d'arrivée du paquet) et un "Count" qui est

initialement mis à zéro. Cela se poursuit jusqu'à ce que la liste soit pleine, puis l’identifiant du

flux d'arrivée des paquets est comparé à l'identifiant d'une entrée choisis au hasard dans la

liste (ce qu'on appelle un «zombie»). Dans le cas d'un "hit", le "Count" du zombie est

augmenté de 1. Autrement, les zombies sont remplacés par l’identifiant du flux du nouveau

paquet arrivé avec une probabilité P. Avec la probabilité 1 - P, il n'y a aucun changement de

la liste des zombies.

Les auteurs de [54] ont estimé le nombre des flux actifs de moyenne "hit" comme

décrit ci-dessous. Ils estiment en premier la fréquence du "hit" P(t) au temps de l'arrivée du t-

th paquets s'accorder à la formule suivante: ( ) (1 ) ( 1) ( )P t P t Hit t (2.5.1)

où est une constante tel que 0 1 , et0 si aucun hit,

( )1 si hit.

Hit t

(2.5.2)

Les auteurs montrent que 1/ ( )P t est une bonne estimation pour le nombre N du flux

actifs jusqu'à l'arrivée du t - th paquets. Au lieu d'utiliser la longueur moyenne de la file

comme RED, SRED calcule la probabilité de suppression de paquet ( , )curd avg N pour estimer

le nombre de flux actifs et la taille instantanée de la file ( curavg ). La première fonction SREDP

est définie comme suit :

cur

max cur

max cur

0 si 0 avg / 6,

1( ) si B/6 avg / 3,

4

si B/3 avg ,

SRED cur

B

P avg P B

P B

(2.5.3)


28

où B est la capacité du Buffer de la file et maxP est la probabilité maximale de suppression.

Noter que SREDP a seulement trois niveaux possibles de suppression max max(0, / 4 et )P P ,

et ne dépend pas du comportement passé de la longueur instantanée de la file, comme le

montre la figure 4 ci-dessous.

Figure 4 : La fonction de suppression de SRED.

Les auteurs ont proposé dans [54] deux versions de SRED:

le “Simple SRED”, où la probabilité de suppression ( , )curd avg N dépend seulement de la

taille instantanée du buffer et de l’estimation P (t) :

2( , ) ( ) min 1, .

2256

Nd avg N P avgcur curSRED

(2.5.4)

Le “Full SRED”, où la probabilité de suppression ( , )curd avg N dépend aussi du paquet

causé d’un "hit" ou non, est calculé comme suit :

2( , ) ( ) min 1, (1 ( ) ).

2256

Nd avg N P avg Hit t Ncur curSRED

(2.5.5)

L’algorithme de ce mécanisme est le suivant [60] :

Pour chaque paquet arrivé : Calculer ( )P t en utilisant la formule (2.5.1) ;

Calculer ( )SRED curP avg en utilisant la formule (2.5.3) ;

Calculer ( )curd avg en utilisant la formule (2.5.4) pour le

“Simple SRED” ou (2.5.5) pour le “Full SRED” ;


29

Marquer ou supprimer le paquet avec la probabilité ( )curd avg ;

où P(t) : représente l’inverse du nombre estimé du flux actifs, et ( )d avgcur est la probabilité

de suppression du paquet.

2.6- Random Exponential Marking (REM)

Le REM (Random Exponential Marking) est proposé par Athuraliya et al. en 2001 [6].

Son idée majeure est de stabiliser les débits autour de la capacité du lien, et de garder la

longueur de la file petite autour d’une valeur cible prédéterminée.

Le mécanisme définit une variable coût en charge de l’utilisateur, qui peut être

considéré comme un modèle pour les utilisateurs pour facturer l'utilisation d'un lien. En

période de congestion, la variable coût devrait être élevée.

La variable coût noté C(t) est définie comme une somme pondérée de deux variables.

V1=taux d’entrée dans la file - capacité du lien.

V2=La longueur de la file - la longueur cible prédéterminée.

Pour stabiliser le coût, la somme pondérée doit être égale à zéro, c'est-à-dire la

longueur de la file d'attente doit être exactement égale à la longueur cible prédéterminée et le

taux d’entrée dans la file doit être le même que la capacité du lien. Toutefois, si la longueur de

la file d'attente cible est plus grande que zéro, il est également possible de se prévenir de

contrôler le taux et de n'utiliser que la longueur de la file d'attente comme un facteur du

contrôle de la congestion. REM sépare la file d'attente pour mesurer la congestion

différemment à RED qui exige que la durée moyenne de la file d'attente à augmenter en vue

de déterminer des congestions, mais REM gère le tout en gardant la même file d'attente stable.

Ce dernier point est important, car la mesure de la congestion qui est inscrite dans la fonction

de probabilité de RED, et la longueur de la file d'attente, automatiquement grandissent

proportionnellement au trafic. Le calcul de la moyenne (filtrage des fluctuations à court

terme) ne peut pas changer le fait qu'il n'est pas possible de stabiliser la file d'attente à une

faible valeur tandis que le volume de trafic augmente de façon significative avec RED. C'est

différent avec REM, qui utilise seulement la longueur instantanée de la file d'attente pour

mettre à jour explicitement la variable coût, mais il n'est pas nécessaire de la maintenir à une

valeur élevée afin de détecter une croissance importante du trafic.


30

La probabilité d’éliminer/marquer un paquet est alors calculée comme suit :

( )1 C tP où est une constante ( 0) et C(t) est le coût au temps t. La probabilité de

suppression de REM augmente de façon exponentielle en comparaison à RED qui augmente

d’une façon linéaire par morceau. Cela est nécessaire pour la probabilité de suppression de

bout-en-bout pour augmenter la somme des coûts de tous les liens congestionnés le long du

chemin, en REM, elle est en fait égal à la baisse de la fonction de probabilité donnée ci-

dessus, avec C(t) étant la somme de toutes les probabilités de baisse par lien, qui est

approximativement proportionnelle à la somme des coûts de chaque lien dans le chemin. Cela

signifie implicitement que REM transmet des coûts pour les utilisateurs finaux par

l'intermédiaire de son paquet de baisse de probabilité, qui est un autre aspect intéressant de ce

mécanisme.

REM a été conçu pour augmenter l’utilisation du lien dans le routeur et maintient la

longueur de la file petite. Cependant, REM ne fournit pas d’équité adéquate quelle sacrifie au

coût de plus haute utilisation. D’ailleurs, sous une lourde congestion ou avec une grande

probabilité de suppression, REM souffre d'un long temps de réponse. De plus, quand la taille

du buffer est petite, la sensibilité de REM devient pire [60].

2.7- Double Slope RED (DSRED)

Le Double Slope RED (DSRED) a été proposé par Zheng et Atiquzzaman en 2000

[67], son but d’améliorer le taux de perte et le délai d’attente dans le mécanisme RED. Il

utilise deux segments de fonction de suppression permettant de fournir beaucoup plus

d’opérations flexibles de suppression que celles du RED comme le montre la figure 5.

Figure 5


31

DSRED introduit les variables additionnelles suivantes :

lK : le seuil de la langueur moyenne de la file pour commencer la suppression des paquets

du buffer.

hK : le seuil de la langueur moyenne de la file pour changer la fonction de suppression.

mK : le seuil de la langueur moyenne de la file pour changer la fonction de suppression.

: la pente de la fonction de suppression du premier segment entre lK et mK .

: la pente de la fonction de suppression du deuxième segment entre mK et hK .

: mode de sélection pour ajuster les pentes de la fonction de suppression.

DSRED utilise une des fonctions de suppression exprimées comme suit :

m

h

0 si ,

( ) si ,

1- + ( ) si K ,

1 si K ,

l

l l m

b

m h

avg K

avg K K avg KP

avg K avg K

avg N

où α et β sont les pentes des deux segments calculés comme suit :

2(1 ),

h lK K

2,

h lK K

Le paramètre adapte le mode de fonctionnement de DSRED. Le taux de suppression

peut être augmenté ou diminué en ajustant .

L’algorithme de ce mécanisme est le suivant [60] :

Pour chaque paquet arrivé : Calculer la longueur moyenne de la file avg ;

Calculer la probabilité de suppression du paquet bP ;

Marquer ou supprimer le paquet avec la probabilité bP ;

2.8- RED with In and Out

Le mécanisme de RIO (RED with In and Out) [14] se base sur le calcul de la longueur

moyenne de la file d’attente, mais, par rapport à RED, il adopte le principe de différenciation

de services [61]. Plus précisément, les paquets sont marqués In "in profile" ou Out "out of

profile" à l'entrée du réseau selon leur degré de priorité ; en cas de congestion les paquets Out

sont rejetés en premier, puis les paquets In le sont à leur tour dès lors que la congestion

s'amplifie.


32

A l'arrivée d'un paquet, le routeur vérifie si ce paquet est IN ou bien OUT. Si le paquet

est IN, alors le routeur calcule la longueur moyenne de la file inavg correspondant aux paquets

IN. De même, si le paquet est OUT, alors le routeur calcule la longueur moyenne de la file

totalavg correspondant l'ensemble des paquets entrants IN et OUT. La probabilité d'élimination

d'un paquet IN dépend de inavg , et la probabilité d'élimination d'un paquet OUT dépend de

totalavg [66].

La probabilité de suppression de RIO est présenté figure 6 :

Figure 6 : La probabilité de suppression de RIO

2.9- CHOKe

Rang Pan et Al. Ont définit une variante de RED appelée CHOKe (CHOose and Keep

the responsitive flows, CHOose and Kill the unresponsitive flows) en 2000 [55], qui protège

les flux adaptatifs contre les flux non adaptatifs. C’est un algorithme qui ne nécessite pas des

informations sur l’état de chaque flux [17, 51].

CHOKe marque aussi deux seuils pour la taille moyenne de la file. Dans le cas où

avg (calculé comme dans RED) est inférieure à thMin les paquets qui arrivent à la file sont

acceptés. Si avg est compris entre les deux seuils, chaque paquet arrivé est comparé à un

paquet tiré aléatoirement dans la file d’attente. Si les deux paquets appartiennent à un même

flux, alors ils sont tous les deux rejetés avec une probabilité calculée de la même façon que

dans RED. Sinon, le paquet tiré est gardé dans la file (dans la même position avant d’être

candidat au rejet) et le paquet arrivé est éliminé avec la même probabilité. Quand

avg dépasse thMax , chaque paquet arrivé est comparé à un paquet tiré aléatoirement de la file.


33

Si les deux paquets font parti d’un même flux, ils sont tous les deux éliminés, sinon seulement

le paquet arrivé est rejeté et le paquet tiré est resté dans la position qui occupe avant d’être tiré

dans la file. Dans cette dernière phase, on peut tirer m (>l) paquets de la file qui seront ensuite

comparés un par un avec le paquet arrivé. Les paquets appartenant au même flux que celui du

paquet arrivé sont tous éliminés [51].

Ce raisonnement a conduit à l'algorithme suivant qui est exécuté à chaque fois qu'un

paquet arrive:

Si la longueur moyenne de la file d'attente (tel que calculé avec RED) est inférieure

à thMin , le paquet est admis, et l'algorithme se termine.

Sinon, un paquet est choisi au hasard de la file d'attente par rapport aux nouveaux

arrivants. Si les paquets appartiennent au même flux, ils sont tous les deux rejetés.

Sinon, l'algorithme procède comme RED: si la taille moyenne la file d'attente est

supérieure ou égale à thMax , le paquet est abandonné, et sinon, il est supprimé avec une

probabilité qui est calculée comme en RED.

Il existe un moyen pour réduire l’agressivité des flux non adaptatifs qui traversent le

routeur et donc maintenir la taille moyenne de la file inférieure à thMax . Il suffit d’introduire

plusieurs seuils en partageant l’intervalle entre thMin et thMax en plusieurs régions R1,

R2,…RK et choisir la valeur m de la région atteinte par la taille moyenne de la file d’attente.

Par exemple, m=2*i (i=l,…, K), quand avg atteint la région Ri. La valeur de m augmente

avec l’occupation moyenne de la file [17].

CHOKe est un algorithme qui assure un partage équitable de la bande passante entre

tous les flux adaptatifs (flux TCP) contre les flux non adaptatifs et agressifs (flux UDP). Avec

les flux agressifs et non adaptatifs les paquets subissent souvent des pertes multiples alors que

les flux adaptatifs subissent des pertes simple et aléatoire similaires à celles de RED [51].

Selon (Pan et al. 2000) [55], ils donnent au plus un sens de comparer le nouveau

paquet avec non seulement un, mais un certain nombre de paquets à partir du buffer et de

supprimer tous ceux qui appartiennent au même flux, ce qui impose une plus grave forme de

punition sur les flux qui ne répondent pas, mais exige plus d'efforts de calcul.


34

2.10- Weighted Random Early Detection (WRED)

Une extension de RIO à plus de deux niveaux est WRED (Weighted RED). Elle se

base notamment sur la politique de RED, mais résout le problème de priorité en assurant le

DiffServ. WRED utilisé pour différencier la probabilité d'élimination des paquets dans une

file d'attente unique. A l'entrée de la file d’attente, s’effectue une classification des paquets

permettant de déterminer la provenance des paquets (IntServ, DiffServ). Lorsque la taille

moyenne de la file dépasse un seuil, qui varie selon la classe, les paquets sont éliminés

conformément à la probabilité d'élimination de leur classe.

WRED est un algorithme dynamique de gestion des files d'attente qui est capable de

fournir plusieurs niveaux de précédence de rejet et associer à chacun de ces niveaux une

fonction de probabilité de rejet différente en fonction de la taille moyenne de la file, et, selon

le type du paquet, de la priorité de ce dernier. Ainsi, nous bénéficions pleinement des

ressources inutilisées du réseau.

WRED est une même technique que RED, mais permet en plus de déterminer quel

trafic on jette grâce au champ IP Précédence pour décider de l’élimination des paquets. On

évite ainsi la monopolisation des ressources par certaines classes de trafic. Le flux de trafic

moins prioritaire s’adaptera au trafic de priorité plus élevée.

Pour chaque paquet entrant, l’algorithme suivant est appliqué [61] :

1. Calcul de la taille moyenne de la file selon la formule :

1 1_ 1 _ _

2 2n navg old avg current queue size

où n est un facteur de poids, configurable par l’utilisateur.

2. Si la taille moyenne calculée est inférieure au seuil autorisé, le paquet est mis en file

d’attente ;

3. Si la taille moyenne de la file est comprise entre le minimum et le maximum du seuil

autorisé, le paquet est soit éliminé, soit mis en file (tout est fonction de la probabilité

d’élimination).

4. Enfin, si la taille moyenne de la file est supérieure au seuil maximum, le paquet est

automatiquement éliminé.

La figure 7 présente un scénario de WRED agissant sur trois niveaux de priorité [61] :

les paquets de faible précédence se voient rapidement éliminés, dès que la moyenne de la


35

taille de la file atteint un niveau relativement bas ; la probabilité d’élimination des paquets de

plus haute priorité est moindre, et s’effectue au moment où la moyenne de la taille de la file

est plus importante.

Figure 7 : Principe de fonctionnement de WRED

2.11- Dynamic-RED (DRED)

Dynamic-RED (DRED) est un mécanisme qui vise également à la stabilisation de la

file d'attente des routeurs, par le maintien de la longueur moyenne de la file d'attente près d'un

seuil fixe, il parvient à offrir des performances prévisibles, tout en permettant la transition du

trafic sans supprimer les paquets intitules. Le DRED est décrit dans (Aweya et al. 2001), il

suit une approche de contrôle strictement théorique, Le choix de contrôleur qui surveille la

file d'attente et la probabilité de suppression de paquet qui utilise une technique du contrôle

intégrante travaillera toujours contre une erreur (celle de la mesure de la sortie du système, au

quel est affecté par des perturbations dans l'environnement, moins la référence d'entrée) d'une

manière qui soit proportionnelle au temps intégral de l'erreur, de façon à ce que l'état stable

d'erreur devient nul. Le signal d'erreur qui est utilisée pour piloter le contrôleur est filtré avec

le processus EWMA, qui a le même effet que le filtrage (en moyenne) de la longueur de la

file d'attente comme RED, ce qui permet à DRED d’ajuster un libre court trafic.

DRED à une grande variété de paramètres qui peuvent être adaptés, sur la base des

analyses et des simulations, des recommandations pour les valeurs par défaut sont données

dans (Aweya et al. 2001).

2.12- Flow Random Early Drop (FRED)

Flow RED (FRED) est un mécanisme proposé par Lin et Morris en 1997 [46]. Qui est

une autre amélioration de RED, qui permet de résoudre le problème des flux non sensibles


36

acceptant toujours les flux qui ont moins d'un seuil minimal ( qMin ) des paquets dans le buffer

tant que la taille moyenne de la file d'attente est plus petite que thMax . FRED ne concerne que

les flux qui ont plus de qMin paquets dans la file d’attente. Ce type de contrôle exige que le

mécanisme permettant de stocker des flux par état que pour les flux qui ont des paquets dans

la file d'attente et non pas pour tous les flux qui ne traversent jamais le lien, et donc, la

mémoire nécessaire est limitée par la longueur maximale de la file d'attente.

FRED introduit les paramètres qMin et qMax qui sont respectivement le nombre

minimal et maximal que peux un flux contenir dans la zone mémoire.

FRED ne prend pas en compte les événements de départ lors du calcul de la durée

moyenne de la file d'attente. C'est à dire, quand un paquet arrive et la file d'attente est très

longue, et aucun paquet arrive pour une longue période, le calcul à l'arrivée du prochain

paquet sera basé sur l'ancienne durée moyenne de la file d'attente, qui conduisant à un trop

haut résultat.

2.13- Selective Fair Early Detection (SFED)

Le SFED (Selective Fair Early Detection) proposé dans [40], c’est un mécanisme qui

permet le contrôle du taux basé sur la gestion de la file qui assure une allocation de la bande

passante juste parmi les flux en concurrence égale dans la présence du trafic non adaptif.

SFED peut être utilisé pour diviser la bande passante par rapport à des poids pré-assignés et

bien assortis pour l’allocation de la bande passante pour agréger les flux exigés dans les

services différenciés. Il maintient un jeton porté dans un seau pour chaque flux (ou tous les

flux) comme le montre la figure ci-dessous.

Figure 8 : Architecture pour le contrôle de taux en utilisant les seaux de jeton.


37

Toutes les fois qu'un paquet est en file d’attente, les jetons sont enlevés en

correspondance aux seaux. La décision à mettre en file d’attente ou supprimer un paquet de

tout flux dépend de l'occupation de son seau dans le temps.

SFED assure la prévention de la détection et la notification de la congestion à la

source adaptative. En envoyant un taux plus haut que la bande passante autorisée, qui résulte

en un bas seau d’occupation et ainsi une plus grande probabilité de suppression qui indique

donc le début de la congestion à l'entrée. Cela permet au flux adaptatif d'atteindre un état

stable ce qui prévient d’une sévère pénalisation. Cependant, les flux non-adaptatifs

continueront à envoyer les données au même taux et donc ne souffrent plus de pertes.

Le taux auquel les jetons sont enlevés du seau d'un flux est égal au taux des nouveaux

paquets de ce flux. Seulement le taux d'addition de jetons dans un seau dépend de sa part

autorisée de la bande passante et pas sur le taux auquel les paquets de ce flux particulier ne

sont pas en file d’attente. Dans ce chemin un seau symbolique sert comme un contrôle sur la

bande passante consommée par un flux.

2.14- Balanced RED (BRED)

Balanced RED est a été proposé par Anjum et Tassiulas en 1999 [4, 5]. Est une

extension de FRED avec le but d’accomplir la bande passante pour les trafics TCP et UDP. Le

principe de BRED est la régulation de la bande passante d’un flux en restant en compatibilité

avec le flux actif. Cela est fait en supprimant préventivement les paquets afin que le trafic non

adaptatif n’occupe plus de la bande passante des flux adaptatifs.

Pour ce but, BRED introduit cinq variables globales qui sont utilisées pour contrôler

la bande passante :

mW : le nombre maximal de paquets que chaque flux est permis d'avoir dans le buffer.

il : le nombre minimal de paquets du flux i qu’il peut avoir dans le buffer avant que ses

paquets commencez à être supprimés avec la probabilité pi, pour i = 1, 2.

ip : probabilité de suppression de paquet du flux i quand il est atteint pour ce flux.

Ces paramètres sont donnés comme suit :


38

1 2l l , 2

2

Bl

N

, 2

10

Np

N

et 21

10

pp .

où est une constante (0 1) et N

est une estimation du nombre du flux actifs de

l’entrée. Il est calculé comme suit :

(1 ) activeN N N

;

et activeN est la mesure du nombre de flux qui ont au moins un paquet dans le buffer. Le

paramètre est mis à 0.02.

La décision de supprimer ou d’accepter un nouveau paquet est basée principalement

sur iqlen et igap lesquels donnent le pas de la fonction de suppression. La variable igap

empêche des suppressions multiples consécutives qui sont malfaisants aux flux adaptatifs. Les

trois seuils 1l , 2l et mW divise l’espace de iqlen en quatre régions : 1(0, )l , 1 2( , )l l , 2( , )ml W ,

( , )mW pour chaque longueur de la file.

Si ( , )i mqlen W alors le paquet est définitivement supprimé.

Si 2( , )i mqlen l W et 2igap l , alors le paquet est supprimé avec la probabilité 2p .

Si 1 2( , )iqlen l l et 1igap l , alors le paquet est supprimé avec la probabilité 1p .

Si 1(0, )iqlen l , alors le paquet est accepté.

iqlen etigap sont augmentés si le paquet est accepté. iqlen est diminué pour chaque

départ d'un paquet qui appartient au flux i.

Bien que BRED peut minimiser les différences dans la bande passante obtenue pour

chaque flux, il a besoin de maintenir les états du flux, quel est difficile à mette en œuvre qui

est proportionnel à la taille du buffer de retour.


A chaque paquet arrivé du flux i :Si c'est le premier paquet du flux i (i est le premier flux) alors

iqlen = 0 ;


39

igap = 0 ;

activeN = activeN +1 ;

Fin SiSi iqlen nW ou le buffer est plein alors

Supprimer le paquet ;Sinon Si 2m iW qlen l et 2igap l alors

Supprimer le paquet avec la probabilité 2P ;

Sinon Si 2 1il qlen l et 1igap l alors

Supprimer le paquet avec la probabilité 1P ;

Sinon Si 1iqlen l alors

Accepter le paquet ;1i iqlen qlen ;

1i igap gap ;

Fin SiA chaque départ du paquet du flux i :

1i iqlen qlen ;

Si 0iqlen alors

1active activeN N ;

0igap ;

Fin SiPour chaque paquet du flux i supprimé:

0igap ;

2.15- Adaptive Virtual Queue (AVQ)

Adaptive Virtual Queue (AVQ) a été proposé par Kunniyur et Srikant en 2004 [43].

C’est un mécanisme basé sur le débit et la haute utilisation du lien et qui a une base théorique

plus solide que RED. C’est un schéma d’AQM qui détecte la congestion selon le taux d’arrivé

des paquets au lien.

AQV utilise une file virtuelle avec une capacité du service virtuelle qui est moins que

la capacité réelle du lien. La capacité virtuelle à chaque lien est modifiée tel que le flux total

entrant à chaque exécution du lien qui désire l’utilisation du lien. Il utilise aussi comme une

entrée au modèle, des paramètres du système comme le maximal Round Trip Time (RTT), le

nombre minimal des connexions actives N pour trouver le taux le plus rapide auquel la

probabilité du marquage est adaptée et par conséquent accomplir la stabilité du système. Le

taux de l'adaptation qui est destiné à maintenir la stabilité du système, dénoté par , est

calculé donc comme un taux d’utilisation du lien désirable.


40

Les variables utilisées par le mécanisme AVQ sont:

: utilisation du lien désiré ( 1) .

: facteur utilisé pour déterminer comment la probabilité de marquage est adaptée au

lien au changement des conditions du réseau.

C : la capacité du lien.

C:

: la capacité virtuelle du lien.

B : la taille du buffer.

B:

: la taille virtuelle du buffer.

: Le taux d’arrivé au lien.

L’algorithme de ce mécanisme est le suivant :

Pour chaque paquet arrivé :t le temps courant ;b le nombre de bytes ;/* la mise à jour de la taille de la file virtuelle*/

VQ max (VQ- C:

(t-s), 0) ;Si VQ +b > B alors

Marquer ou supprimer un paquet de la file réelle ;Sinon /* la mise à jour de la taille de la file virtuelle*/

VQVQ +b ;Fin Si/* la mise à jour de la capacité virtuelle*/

C:

max (min (C:

+ * *C(t-s), C) - *b, 0) ;

/* la mise à jour de la capacité virtuelle*/s t ;

où VQ est le nombre de bytes courants dans la file virtuelle, et s le temps d’arrivé du paquet

précédent.

2.16- GREEN (Generalized Random Early Evasion Network)

Le GREEN (Generalized Random Early Evasion Network) a été proposé par Feng et

al. [21, 41]. Il permet d’appliquer la connaissance du comportement d'état stable pour les

connexions TCP pour router ou supprimer (ou marquer) d’une manière intelligente les

paquets pour la notification de la congestion. En utilisant un tel mécanisme, A chaque

connexion toute route prend sa part de la bande passante en prévenant l'augmentation des

paquets dans la file. Le débit d'une connexion TCP dépend, parmi autre acteurs, sur son temps


41

d’aller-retour (RTT) et la probabilité de suppression de ses paquets dans le réseau. Le débit

d’une connexion est donné par la formule suivante :

MSS cBW

RTT p

(1)

où MSS est la taille maximale du segment, RTT est le temps d’aller-retour, p est la

probabilité de la perte du paquet, et c est une constante qui dépend de la stratégie de la

reconnaissance qui est utilisée (par exemple, différé ou chaque paquet) comme si les paquets

sont assumés d’être périodiquement perdu.

Ce modèle peut ne pas être applicable à la mise en ouvre de non-SACK TCP. Pour les

plus courtes connexions, qui n'atteignent jamais un état stable, ou les connexions dont la taille

de la fenêtre artificielle est limitée par rapport à la fenêtre du contrôle de flux du receveur.

Si L est la capacité du lien et N est le nombre du flux TCP actifs qui partagent

équitablement le lien de la bande passante, alors la part de la bande passante d'un flux est

égale à L/N et la probabilité de perte d’un paquet est déduite de l’équation (1) par la formule

suivante :

2N MSS c

PL RTT

(2)

Une amélioration de GREEN est proposée dans [41], en ajoutant un paramètre

additionnel ( )t dans la formule (2) pour adapter la fonction de suppression du paquet au taux

d’utilisation du lien et au nombre de paquets perdu pendant le dernier intervalle du temps.

Donc cette probabilité devient comme suit :

2

( )

N MSS cP

t L RTT

(3)

Le paramètre ( )t est adapté comme suit :

Si le lien est 100% utilisé alors : ( 1) 2 ( )t t

Si les paquets sont perdus pendant le dernier intervalle du temps alors : ( 1) 0.95 ( )t t

Si le taux d’utilisation du lien est moins que 98% alors :1

( 1) ( )2

currentUtilt t

currentUtil


42

L’algorithme de ce mécanisme est donné comme suit :

Pour chaque paquet arrivé :

( )RTT obtainRTT paquet ;

2

( )

N MSS cP

t L RTT

;

Marquer ou supprimer le paquet avec la probabilité P.

Si ( ()currentTime - lastUpdate window ) alors

Mettre a jour les variables currentUtil , N et queueDrops ;

()lastUpdate currentTime ;

Si ( 0queueDrops ) alors 0.95 ;

Sinon Si ( 0.98currentUtil ) alors1

2

currentUtil

currentUtil

;

Fin Si

Fin si

où window est la fenêtre de temps utilisé pour estimer le nombre de flux et pour estimer

l’utilisation courant du lien, currentUtil est l’utilisation courant du lien, et queueDrops est le

nombre de suppression dans la file dû au débordement.

2.17- LRED (Loss Ratio based RED)

LRED (Loss Ratio based RED) c’est un schéma de gestion active des files d’attente

récemment proposé par Wang et al. en [62]. Qui permet d’estimer le degré de congestion de

lien en se basant sur le taux de perte des paquets et la longueur de la file. Le taux de perte des

paquets est utilisé dans la grande échelle du temps qui rend le schéma plus adaptatif et

robuste, pendant que la longueur de la file est utilisée dans la petite échelle du temps qui rend

le schéma plus sensible en réglant la longueur à une valeur attendu 0q . Dans la grande échelle

du temps, la règle de base est de garantir que la probabilité de suppression du paquet soit le

plus possible comme le taux de perte du paquet. Le dessin gouverné dans la petite échelle du

temps montre que :

1) Quand la longueur de la file est égale à 0q , la probabilité de suppression du paquet sera

égale au taux de perte du paquet.


43

2) Quand la longueur de la file est plus grande (ou plus petite) que 0q , la probabilité de la

suppression du paquet sera aussi plus grande (ou plus petite) que le taux de perte du

paquet.

Le taux de perte des paquets c’est un indice important qui désigne la gestion du buffer

depuis :

Qu’un taux de perte du paquet croissant est une indication claire qu’une congestion sévère

a lieu, et la suppression agressive des paquets est exigée.

Qu‘une baisse de taux de perte du paquet peut servir comme un signal que la congestion

s'éloigne et par conséquent l'action de suppression des paquets est moins agressive.

LRED mesure le taux de perte du paquet dans la grande échelle du temps, et met à jour

la probabilité de suppression du paquet dans la petite échelle du temps à chaque arrivée du

paquet. La probabilité de suppression du paquet P est calculé chaque mp (une durée qui doit

être moins que RTT) comme suit:

0( ) ( )( )P l k l k q q

où ( )l k est le taux de perte du paquet, q est la taille de la file et est une constante

préconfigurée ( 0 ).

Le taux de perte du paquet ( )l k est calculé comme étant le rapport du nombre de

paquets supprimés et le nombre total des paquets arrivées pendant une longue période M.

l’estimation ( )l k est obtenu alors comme un EWMA de ( )l k comme le montre la figure 8:

( ) ( 1) (1 ) ( )l k l k mw mw l k

Avec

1

01

0

( )

( )

( )

M

diM

ai

N k i

l k

N k i

où mw est le facteur du poids mesuré auquel est mis une petite valeur pour obliger le taux de

perte courant, dN est le nombre des paquets supprimés dans une période k th et aN est le

nombre des paquets arrivés dans une période k th .


44

Figure 9 : La mesure du taux de perte des paquets par LRED


Mise à jour de ( )l k chaque mp secondes :

Calculez

1

01

0

( )

( )

( )

M

diM

ai

N k i

l k

N k i

;

Calculez ( ) ( 1) (1 ) ( )l k l k mw mw l k ;


Calculez la probabilité de suppression 0( ) ( )( )P l k l k q q ;

Marquer ou supprimer le paquet avec la probabilité P ;

où ( )l k est le taux de perte du paquet pendant une longue période M.

2.18- Proportional Integral controller (PI controller)

Proposé par Hollot et al. en [34]. Il est conçu pour augmenter l’utilisation du lien en

maintenant une petite taille de la file. En effet PI permet d’utiliser la longueur de la file et le

taux de l'entrée comme une mesure de la congestion pour accomplir la meilleure stabilité de la

taille instantanée de la file en essayant de régler la longueur de file à une valeur attendue 0q ,

en utilisant la disparité de la longueur de la file et son intégrale.

Chaque paquet qui arrive est supprimé par la probabilité suivante :

0 0( ) ( )cur prev oldP a q q b q q P


45

où curq est la taille instantanée actuelle de la file, prevq est la taille instantanée précédente de

la file et oldP est la probabilité du marquage/suppression précédent. La probabilité de

suppression P est mise à jour à chaque intervalle du temps INTERVAL .


A chaque intervalle du temps INTERVAL :

Calculer la probabilité de suppression du paquet P ;


Marquer ou supprimer le paquet avec la probabilité P ;

3- Conclusion

Les mécanismes décrits dans ce chapitre sont un petit sous-ensemble d'AQM

existants dans la littérature, on peut dire que les mécanismes présentés dans ce chapitre

sont parmi les plus populaires. La classification de ces mécanismes sur la base de leur

nature n'est pas facile. Certains d'entre eux s'appuyer sur RED, tandis que d'autres suivent

une approche totalement différente, et il ya une transition sans percussion d'une extrémité

à l'autre. En outre, certains mécanismes basent leurs décisions sur la longueur de la file

d'attente tandis que d'autres mesurent les taux de perte ou de l'arrivée des paquets.

Chapitre 4 : Comparaison des mécanismes de gestion active des files d’attente (AQM)

46

Chapitre 4 : Comparaison des mécanismes de gestionactive des files d’attente (AQM)


47

1- Comparaison des performances de TD, RED et REM

La comparaison entre les mécanismes TD et RED, était sujet de plusieurs travaux de

recherche, les résultats de simulation obtenus dans [64] et [65] (Tableaux 1 et 2), montrent

que RED réduit de manière très claire (presque la moitié) la taille moyenne de la file d’attente,

de même RED diminue le délai d’attente des paquets par rapport à TD. Cependant RED

présente un taux de perte élevé en comparaison avec TD.

RED TDTaille moyenne de la file 4.3 9.0Délai moyenne (ms) 4.5 8.7Taux de perte 22% 20%

Tableau 1 : Comparaison de TD et RED [64].

Le tableau 2, qui présente des résultats des simulations effectuées dans [64], montre

que RED et REM réalisent des taux de perte des paquets relativement proches mais qui restent

supérieurs à celui dans TD. La longueur moyenne de la file d’attente pour REM est

relativement inférieure à celle de RED ; au moment où le débit pour REM est inférieur à celui

de RED et de TD.

AQM Taux de perte Débit (Paquets/s) Taille moyenne de la fileDrop Tail 11.8% 1249.2 92.7

RED 13.1% 1245.8 42.1REM 13.6% 1237.0 40.1

Tableau 2 : Comparaison entre TD, RED et REM [65].

Le mécanisme REM se distingue de tous les autres algorithmes présentés par le fait de

prendre en considération le coût de la congestion qui dépend du nombre de sources utilisant le

lien [6]. Par ailleurs, la probabilité de marquage/rejet dans REM augmente d’une manière

exponentielle selon le niveau de congestion au moment où celle-ci augmente de manière

linéaire (pour RED) ou linéaire par morceau (pour GRED) (figure A5).

2- Comparaison des performances de RED, ARED et BLUE

Les figures A1, qui explicitent des résultats de simulation réalisée dans [18], montre

qu’avec le mécanisme RED, le délai d’attente des paquets est nettement plus élevé que celui

avec ARED. Alors que le taux de paquets rejetés avec RED est inférieur à celui de ARED. Par

ailleurs les deux mécanismes assurent le même débit.


48

En se référant aux résultats obtenus dans [11] et [22] (figures A2), on peut remarquer

que lorsque le nombre de connexions augmente, le mécanisme BLUE garde toujours un débit

meilleur et relativement stable que celui de RED. Et avec ce dernier, le taux de perte de

paquets est nettement plus élevé qu’avec le mécanisme BLUE.

En se basant sur les simulations faites dans [30] (figures A3 et A4), on peut remarquer

que ARED présente une fluctuation plus importante par rapport à BLUE au niveau de la

longueur moyenne de la file d’attente. On peut aussi observer que BLUE maximise

l’utilisation des ressources, et par conséquence il maximise le débit sortant (en évitant toute

sous utilisation de la file d’attente). ARED offre un débit assez constant et moins performant

par rapport à BLUE. En contre partie, cela induit un très grand délai de bout en bout, ce qui

est nuisible pour les applications à temps réel et multimédia.

Dans [2] (figures A19 et A20) on trouve des résultats de simulations qui illustrent la

comparaison entre le RED et ARED au niveau débit et délai d’attente en changeant les valeurs

des seuils maximal et minimal. La figure A19 démontre que la courbe RED reste toujours

supérieure à celle de ARED au niveau délai d’attente lorsque le débit augmente (seuil

minimal fixé a 5 et seuil maximal fixé a 15 et 0.002qw ). Dans la figure A20 on voit presque

le même changement mais la courbe de RED reste toujours au dessus de celle de ARED.

Pour comparer RED, GRED et Adaptative RED au niveau longueur de la file en

fonction du temps on prend les résultats de simulations de [12] (figures A21 et A22). Dans les

figures A21, la longueur de la file de RED reste ascendante stable pour les trafics de 150 flux,

seulement pour 200 flux cela atteint, le seuil maximal et devient instable. Concernant celle de

GRED elle est capable de gérer un chargement ascendant pour 200 flux. Pour RED-ECN,

GRED-ECN et ARED-ECN on prend les figures A22 ; la longueur moyenne de la file est

instable pour le chargement de 150 flux pour RED-ECN de plus elle est très bénéfique pour

GRED-ECN pour 200 flux.

3- Comparaison des performances de TD, GREEN et FRED

Pour comparer les mécanismes TD, GREEN et FRED on prend les résultats de

simulation de [21, 41] (figures A6, A7, A8). Les figures A6 montrent que lorsque le nombre

du flux augmente, GREEN est plus performant en termes d’utilisation du lien par rapport à

FRED. Par contre TD atteint la plus haute utilisation du lien parce que les flux occupent le


49

lien pendant des petits RTTs et aucun paquet n’a été supprimé volontairement. Concernant la

perte des paquets on voit qu’il y a des petites fluctuations entre les trois mécanismes, mais il

n’ya pas de grande différence. Les figures A7 et la figure A8 permettent de comparer ces

AQM au niveau d’occupation de la taille de la file. Nous observons que le TD permet

d’augmenter dramatiquement la taille moyenne de la file lorsque le nombre des flux

augmente. Par contre on peut constater que GREEN et FRED gardent la taille moyenne de la

file basse. FRED garde la taille de la file basse par le marquage des paquets à partir d’un

certain seuil et limite l’occupation de l’espace du buffer pour chaque flux.

4- Comparaison des performances de RED, PI, AVQ et REM

La comparaison de RED et PI était sujet des résultats de simulations réalisées dans

[34] (figures A9, A10). Dans les figures A9 (a) on observe que pour une petite valeur de 0q

l’utilisation du lien est presque totale le cas des flux FTP. Concernant le délai d’attente, il est

illustré dans la figure A9 (b) qui indique qu’il est presque une fonction linéaire soit pour les

flux FTP ou HTTP. La figure A10 donne le délai d’attente en fonction de l’utilisation du lien.

Pour comparer les mécanismes RED, AVQ, REM et PI on se base sur les simulations

faites dans [43, 44] (figures A11, A12, A13, A14, A15, A16, A17 et A18). La figure A11

donne le nombre des paquets perdus pour chaque lien en fonction du nombre de connexion

FTP pour les mécanismes RED, AVQ, REM et PI. Le mécanisme AVQ est meilleur en

comparaison avec les autres mécanismes arrive après PI ensuite RED et à la fin on trouve

REM qui induit la perte la plus élevée des paquets lorsque le nombre de connexion FTP

augmente. La figure A12 montre que REM et PI utilisent 100% du lien et la file est toujours

non vide, le mécanisme AVQ utilise 98 % du lien, de plus une faible utilisation du lien par

RED par rapport au autres AQM. La figure A13 illustre que le RED et AVQ gardent une

petite taille de la file en comparaison avec les mécanismes REM et PI qui maintiennent une

haute moyenne de la longueur de la file lorsque le nombre de connexion FTP augmente. La

figure A14 prouve que le mécanisme AVQ ne supprime pas plus de paquets par rapport aux

RED, REM et PI. La figure A15 montre que les mécanismes REM et PI ont la même

utilisation du lien qui est plus haute, et une faible utilisation par le RED, par contre AVQ

présente une meilleure utilisation du lien mais reste basse par rapport a REM et PI. Les

figures A16 et A17 montrent que le mécanisme AVQ maintient une petite longueur de la file

pour le nombre des court-flux par rapport aux autres mécanismes qui dépendent du paramètre

Gama, lorsque ce paramètre augmente la longueur de la file augmente. Dans la figure A18 on


50

observe que Les mécanismes REM et PI gardent un débit plus important par rapport aux

autres mécanismes. Le débit présenté par AVQ dépend du paramètre Gama, lorsque ce

paramètre augmente le débit augmente.

5- Comparaison des performances de DT, RED, BLUE, REM et PI

Les simulations de [42] (figures A23, A24 et A25) comparent les mécanismes DT,

RED, BLUE, REM et PI au niveau utilisation du lien, délai moyen d’attente et le taux de perte

des paquets.

Un des problèmes les plus importants que pose l’utilisation des mécanismes AQM est,

les paramètres de configurations de ces mécanismes influencent sur l’analyse de performance

des algorithmes de gestion active des files d’attente pour les réseaux IP.

Le tableau 3 donne la classification de certains AQM.

Critères Congestion Seuils Etat d’informationSchémas Contrôle Aviodance Non Globale Par-

connexionGlobale Par-

connexionTD * * *

RED * * *BLUE * * *REM * * *

PI * * *

Tableau 3 : La classification de certains AQM

6- Comparaison des performances de CHOKe, FRED, RED et SFED

Les résultats de simulations réalisées dans [40] (figures A26, A27, A28 et A29)

illustrent le débit en fonction du temps des mécanismes CHOKe, FRED, RED et SFED pour

les flux TCP et CBR. On observe que SFED est meilleur en terme d’équité de débit pour les

flux TCP et CBR. Dans la figure B27 FRED pénalise les flux TCP durant un certain intervalle

de simulation, et le partage du débit devient équitable pour les flux CBR et TCP après.

7- Comparaison des performances de DT, RED, REM et AVQ

Dans [59] (Tableau 4) se trouve une comparaison entre les mécanismes DT, RED,

REM et AVQ au niveau taux de perte de paquets, débit, et la taille moyenne de la file. AVQ

est moins performant par rapport à RED et REM au niveau de perte des paquets, le DT est le


51

meilleur. Concernant le débit, on observe que DT présente un débit plus important par rapport

aux autres mécanismes, le AVQ présente le plus petit débit. La taille moyenne de la file

d’attente avec RED et REM est la moitié de celle de DT, par contre celle de AVQ est le ¼ par

rapport à REM et RED.

AQM Taux de perte Débit Taille moyenne de la file

Drop Tail 11.8% 1249.2 92.7RED 13.1% 1245.8 42.1REM 13.6% 1237.0 42.1AVQ 14% 1218.0 10.5

Tableau 4 : Comparaison des performances entre certains AQM.

Chapitre 5 : Utilisation de certains mécanismes de gestion active des files d'attente pour leroutage dans les réseaux Ad hoc

52

Chapitre 5 : Utilisation de certains mécanismes degestion active des files d'attente pour le routage dans

les réseaux Ad hoc


53

1- Introduction

L’AQM pourrait améliorer la qualité de service dans les réseaux mobiles de nouvelles

générations. A titre d’exemple, on peut citer les performances du protocole MAODV

(Multicast Ad hoc On-Demand Distance Vector) [1] qui pourraient être améliorées par

l’utilisation des AQM dans un réseau Ad hoc.

Avant de présenter ces performances, déjà étudiées dans l’article [1] et soulever des

questions auxquelles il faut apporter des réponses, on va présenter brièvement les réseaux Ad

hoc.

2- Les réseaux Ad Hoc (Mobile Ad hoc Network)

MANET (Mobile Ad-hoc NETwork) est le groupe de travail de l’IETF qui se

préoccupe de la normalisation des protocoles Ad hoc fonctionnant sous IP. Ce groupe s’est

appuyé sur les protocoles classiques d’Internet et les a perfectionnés pour qu’ils puissent

fonctionner avec des routeurs mobiles.

Un réseau sans fil Ad hoc (Mobile Ad hoc Network i.e MANet) est une collection de

nœuds mobiles qui communiquent les uns avec les autres sans avoir recours à une

infrastructure préexistante. Les nœuds étant mobiles et communicant sans fil, ils peuvent à

tout moment quitter ou joindre le réseau. De fait, à mesure que les connexions entre les nœuds

se créent et se détruisent, la topologie du réseau peut rapidement être modifiée.

Par l’absence d’infrastructures dans de tels réseaux, les nœuds se comportent comme

des routeurs de manière à transférer les données d’une source à une destination. Ils utilisent

pour cela des protocoles de routage qui peuvent être de différentes natures.

2.1- Les caractéristiques des réseaux Ad hoc

Les réseaux mobiles Ad hoc sont caractérisés par ce qui suit :

Une topologie dynamique : Les unités mobiles du réseau, se déplacent d’une façon libre et

arbitraire. Par conséquent la topologie du réseau peut changer, à des instants imprévisibles,

d’une manière rapide et aléatoire. Les liens de la topologie peuvent être unis ou

bidirectionnels.


54

Une bande passante limitée : Une des caractéristiques primordiales des réseaux basés sur la

communication sans fil est l’utilisation d’un médium de communication partagé. Ce partage

fait que la bande passante réservée à un hôte soit modeste.

Des contraintes d’énergie : Les hôtes mobiles sont alimentés par des sources d’énergie

autonomes comme les batteries ou les autres sources consommables. Le paramètre d’énergie

doit être pris en considération dans tout contrôle fait par le système.

Une sécurité physique limitée : Les réseaux mobiles Ad hoc sont plus touchés par le

paramètre de sécurité, que les réseaux filaires classiques. Cela se justifie par les contraintes et

limitations physiques qui font que le contrôle des données transférées doit être minimisé.

L’absence d’infrastructure : Les réseaux Ad hoc se distinguent des autres réseaux mobiles

par la propriété d’absence d’infrastructure préexistante et de tout genre d’administration

centralisée. Les hôtes mobiles sont responsables d’établir et de maintenir la connectivité du

réseau d’une manière continue.

Equivalence des nœuds du réseau : Dans un réseau classique, il existe une distinction nette

entre les nœuds terminaux (stations, hôtes) qui supportent les applications et les nœuds

internes (routeurs par exemple) du réseau, en charge de l’acheminement des données. Cette

différence n’existe pas dans les réseaux Ad hoc car tous les nœuds peuvent être amenés à

assurer des fonctions de routage.

Communication par lien radio : Les communications entre les nœuds se font par

l’utilisation d’une interface radio. Il est alors important d’adopter un protocole d’accès au

médium qui permet de bien distribuer les ressources radio et ceci en évitant le plus possible

les collisions et en réduisant les interférences. Les technologies de communication sans fil

sont alors indispensables à la mise en place d’un réseau Ad hoc.

Rapidité de déploiement : Les réseaux Ad hoc peuvent être facilement installés dans les

endroits difficiles à câbler, ce qui élimine une bonne part du travail et du coût généralement

liés à l'installation et réduit d'autant le temps nécessaire à la mise en route.

2.2- Les protocoles de routage

Le routage est une méthode d’acheminement des informations à la bonne destination à

travers un réseau de connexion donné. Le problème de routage consiste pour un réseau dont les


55

arcs, les nœuds et les capacités sur les arcs sont fixés à déterminer un acheminement optimal des

paquets à travers le réseau au sens d’un certain critère de performance. Le problème consiste à

trouver l’investissement de moindre coût en capacités nominales et de réserves qui assure le

routage du trafic nominal et garantit sa surveillance en cas de n’importe quelle panne d’arc ou de

nœud.

Les protocoles de routage jouent un rôle important si deux hôtes souhaitent échanger des

paquets et qui sont incapables de communiquer directement. Tous les nœuds sont mobiles et

peuvent être connectés dynamiquement de manière arbitraire. Tous les nœuds de ces réseaux se

comportent comme des routeurs prenant part de la découverte et de l’entretient des routes à

d’autres nœuds du réseau. Cette situation devient plus complexe lorsque plusieurs nœuds sont

ajoutés au réseau Ad hoc.

Un protocole de routage doit être en mesure de déterminer le meilleur chemin entre les

nœuds, de minimiser les frais de bande passante pour permettre le routage, de réduire le temps

nécessaire à la convergence, après changement de la topologie du réseau.

Il existe trois grandes classes de protocoles de routage [19] : les proactifs, les réactifs

et les hybrides.

• Protocoles proactifs : Les nœuds utilisant un protocole de routage proactif

échangent périodiquement des messages de contrôle entre nœuds voisins. Cette transmission

volontaire de l'information est qualifiée de proactive.

Les nœuds disposent, après un certain temps, d'une connaissance fiable de la topologie

du réseau. Sur la base de cette carte du réseau, des chemins entre des nœuds sont déterminés.

Les chemins peuvent être calculés selon plusieurs critères tels que le nombre de sauts,

le délai, la bande passante.

L'inconvénient majeur de cette approche est son coût important pour maintenir à jour

toutes les informations liées à la topologie de chaque nœud, même si aucun message utile

n'est échangé.

Les principaux protocoles de routage proactifs :

Destination-Sequenced Distance Vector Protocol (DSDV)

Optimized Link State Routing (OLSR)


56

Fish-eye State Routing (FSR)

Topology Broadcast Based on Reverse-Path Forwarding (TBRPF)

• Protocoles réactifs : Les protocoles de routage réactifs ne gardent que les routes en

cours d'utilisation pour le routage. Aucun message de contrôle n'est émis pour maintenir les

tables de routage à jour. Uniquement à la demande, le protocole engage une procédure de

découverte de route. Tous les protocoles basés sur cette approche sont qualifiés de protocoles

réactifs.

Cette découverte de route consiste à inonder le réseau par des messages de découverte

de route. En plus de cet inconvénient majeur, cette classe de protocoles est très sensible aux

changements de topologie. Les mécanismes de maintenance de route sont lourds en termes de

gestion et de bande passante utilisée pour faire transiter le trafic de contrôle.

Quelques protocoles de routage réactifs proposés dans MANET :

Dynamic Source Routing (DSR)

Ad Hoc On-Demand Distance-Vector Protocol (AODV)

• Protocoles hybrides : Les protocoles hybrides sont une combinaison des approches

proactives et réactives. En général, ils utilisent une approche proactive dans un voisinage

immédiat ou proche, voisinage de quelques sauts, puis une approche réactive au delà du

voisinage proche. Cette combinaison permet une grande réactivité et rapidité des

communications locales sans perturber la globalité du réseau. Cette approche hybride est

intéressante car elle cumule tous les avantages des approches proactives et réactives, qualités

appréciables pour un grand réseau, mais elle en cumule également les inconvénients : envois

périodiques de messages de contrôle et le coût d'une découverte de route.

Quelques exemples des protocoles hybrides :

Zone Routing Protocol (ZRP)

Temporally Ordered Routing Algorithm (TORA)

System and Traffic dependent Adaptive Routing Algorithm (STARA)


57

2.3- Communication dans les réseaux Ad hoc

Un réseau est dit sans fil lorsque les machines qui le composent ne sont pas reliées entre

elles par des câbles, mais utilisent, pour communiquer, le médium radio ou infrarouge. Comme les

signaux propagés sur ces media s’atténuent au fur et à mesure qu’ils s’éloignent de leur émetteur,

un nœud ne peut pas communiquer avec un autre s’il est situé trop loin de lui. On définit alors

l’ensemble des voisins d’un nœud comme étant l’ensemble des nœuds capables de recevoir et de

comprendre les signaux émis par celui-ci.

Les conditions suivantes doivent être remplies pour qu’un paquet puisse être reçu [16]:

La puissance du signal reçu doit dépasser un certain seuil (seuil de communication).

Le rapport signal sur bruit ambiant doit être suffisamment grand (le signal doit être clairement

identifié, et non noyé dans le bruit).

Il existe un seuil de détection de porteuse. Si la puissance du signal est comprise entre ce

seuil et le seuil de communication, alors le message n’est pas compris mais l’activité sur le canal

est néanmoins détectée. Si le modèle de propagation radio utilisé est «two-ray ground» (ou le

modèle «free-space»), ces seuils définissent donc deux zones autour d’un nœud. Si le récepteur est

placé au centre de la figure 10, alors un émetteur placé dans la zone interne (zone de

communication) pourra lui envoyer des messages qui seront compris (en l’absence d’autres

interférences). Si l’émetteur est placé dans la zone externe (zone de détection de porteuse), la

communication ne sera pas possible mais l’autre mobile sera informé à chaque fois que l’émetteur

accédera au canal. Si le modèle de propagation radio utilisé est «shadowing», les deux zones sont

également définies, mais leurs frontières sont ”floues” du fait du caractère probabiliste du modèle.

Figure 10 : Zones de communication et de détection de porteuse


58

2.4- Gestion d’énergie en mode Ad-hoc

Les réseaux sans fil peuvent posséder des terminaux fixes ou mobiles. Le problème

principal des terminaux mobiles concerne leur batterie, qui n’a généralement que peu

d’autonomie. Pour augmenter le temps d’activité de ces terminaux mobiles, le standard prévoit un

mode d’économie d’énergie.

Il existe deux modes [16]:

Continuous Aware Mode : La station est tout le temps allumée et écoute constamment le

support (fonctionnement par défaut).

Power Save Polling Mode : Permet une économie d’énergie. Les stations qui sont en mode

normal stockeront les paquets pour les stations en mode économie d’énergie et vont jouer le

rôle de tampon pour ces stations. Lorsqu’une station reçoit une trame pour une station qui est

en mode économie d’énergie et que celle-ci n’est pas active, il la stocke. La station qui la

stocke doit être en mode normal pour remplir cette fonctionnalité. Elle émet ensuite des

trames ATIM (Ad-Hoc Traffic Information Map) qui informent les stations en mode économie

d’énergie, qu’il y a des paquets en attente pour elles. Lorsque, la station en mode économie

d’énergie acquitte l’ATIM, la station qui a émis cette trame, lui fait suivre le paquet qu’elle a

pour elle.

3- L’évolution des performances du protocole MAOVD parl’utilisation de certains mécanismes de gestion active des filesd’attente dans les réseaux Ad hoc

3.1- Description du protocole MAODV

MAODV (Multicast Ad hoc On-Demand Distance Vector) étend AODV pour offrir

des possibilités de multicast. Il est capable de faire l’unicast, le broadcast et le multicast. La

découverte de la route se fait sur demande sous forme de question/réponse, et les informations

obtenues par la demande de route (RREQ) et la réponse de route (RREP) sont maintenues

dans la table de routage des nœuds. Si un message est de type RREQ, alors seuls les nœuds

membres du groupe multicast peuvent répondre. Chaque groupe multicast est identifié par une

adresse unique. Dans l’opération de multicast, un nœud leader du groupe maintient les

numéros de séquence du groupe multicast ; il met périodiquement à jour le numéro de

séquence et l’envoi à travers le réseau en employant des messages hellos du groupe (GRPHs).


59

Ce leader du groupe est habituellement le premier nœud qui rejoint le groupe. Si un nœud

veut joindre un groupe multicast qui n’existe pas, alors ce dernier devient le leader de ce

groupe et est alors responsable de la maintenance du groupe [1].

3.2- Amélioration des performances de MAODV par la gestion active desfiles d’attente

Dans un réseau ayant une limitation d’énergie comme les réseaux MANETs, la perte

de paquets entraîne la perte d’énergie pour retransmettre les paquets qui ont été

éventuellement éliminés. L’AQM a montré ses preuves comme solution au problème de

synchronisation globale dans un contexte de réseaux câblés. Selon les auteurs de l’article [1] il

existe peu d’études sur l’AQM dans les MANETs, et aucune pour le multicast. Ils ont

modélisés un réseau sous forme de files d’attente en choisissant trois files qui sont:

- Priority Queuing (PriQ) utilise un processus de classification qui aiguille les paquets

provenant de différents flux vers différentes files selon leur priorité. Les files de haute priorité

sont servies dès que le nœud reçoit des paquets.

- Drop Tail (DT) est la technique classique pour gérer les files d’attente dans les réseaux

mobiles et câblés. Pour plus de détaille sur cette file voir le chapitre 1.

- Deficit Round Robin (DRR) veut résoudre le problème de l’équité posé par la différence des

tailles des paquets. Dans DRR, les files sont servies dans l’ordre round robin et chaque file est

autorisée à envoyer un nombre déterminé d’octets lors de chaque passage de l’Ordonnanceur.

Le modèle de simulation utilisé dans [1] basé sur NS. L’environnement de simulation

est le suivant :

1) Surface: 1500m x 300m

2) Nombre de nœuds: 50

3) Durée simulation: 910 secondes

4) Physical/Mac Layer: IEEE 802.11 à 2Mbps, transmission à 250m

5) Modèle de mobilité: modèle random waypoint sans temps de pause, vitesse des nœuds

égale à 1m/s.

6) Chaque récepteur est membre du groupe multicast, mais chaque émetteur n’est pas

forcément membre du groupe multicast (excepté le cas avec 50 récepteurs où tous les nœuds

sont membres du groupe).


7) Tous les récepteurs rejoignent un groupe multicast unique au début de la simulation, et les

émetteurs débutent l’émission des données 30 secondes plus tard. Après 900 secondes, tous

les émetteurs arrêtent la transmission des données.

8) Flux de type CBR (Constant Bit Rate): taille d’un paquet = 256 bytes, intervalle = 0,5

secondes, nombre maximum de paquets émis = 1740.

9) Seul le trafic multicast existe dans la simulation.

10) Tous les modèles ont 1 émetteur 10, 20, 30, 40, 50 récepteurs; 2 émetteurs 10, 20, 30, 40,

50 récepteurs; 3 émetteurs 10, 20, 30, 40, 50 récepteurs et 5 émetteurs 10, 20, 30, 40, 50

récepteurs.

A. Résultats de simulation :

Les résultats de simulations sont présentés ci-dessous.

A. Le taux de délivrance de paquet

Figure 11 : PDR MAODV, 1 émetteur,vitesse 1m/s.

Figure 12 : PDR MAODV, 2émetteurs, vitesse 1m/s.

60




61

B. Latence

B. Résumé des résultats :

Les résultats obtenus après ces séries de simulat

A. Le taux de délivrance de paquet

Quand on croit le nombre d’émetteurs, les valeurs

l’augmentation du trafic sur le réseau entraînant une pe

Quand on croit le nombre de récepteurs, les valeurs de

Figure 15 : Latence MAODV, 1émetteur, vitesse 1m/s.

Figure 16 : Latence MAODV, 2émetteurs, vitesse 1m/s.

Figure 17 : Latence MAODV, 3émetteurs, vitesse 1m/s.
Figure 18 : Latence MAODV, 5
émetteurs, vitesse 1m/s.

ions sont les suivants [1] :

de PDR décroissent, ceci est dû à

rte de paquets émis.

PDR varient aléatoirement.


62

B. Latence

Quand on croit le nombre d’émetteurs, les latences pour PriQ et DT sont proches, et ont une

valeur moyenne de 0,03 secondes.

Quand on croit le nombre de récepteurs, la latence varie aléatoirement.

C. Conclusion :

D’après le travail est les résultats de simulations faites dans [1] on peut conclure que

avec MAODV, les valeurs de PDR sont meilleures avec les files d’attente Drop Tail dans tous

les exemples, alors même que la latence moyenne est égale à celle de Priority Queuing.

Deficit Round Robin aussi donne de meilleurs PDR, mais dans deux cas, sa latence est

supérieure à celle de Priority Queuing. Entre un et cinq émetteurs, le PDR de Priority Queuing

a chuté de 9,9% contre 8,8% pour Drop Tail – illustrant ainsi sa plus forte stabilité – et 10,3%

pour Deficit Round Robin. Les simulations montrent que les performances du protocole

MAODV original, utilisant l’algorithme Priority Queuing, peuvent être améliorées par

l’utilisation des AQMs, dans un réseau MANET.

Conclusion et perspectives

63



64

Dans ce travail, on s’est intéressé à l’étude et la comparaison de certains mécanismes

de gestion active des files d’attente dans les réseaux Internet, tels que RED, et ces variantes.

On s’est intéressé aussi à une étude critique de ces mécanismes.

On a présente aussi l’évaluation des performances du protocole MAODV par

l’utilisation de certains mécanismes de gestion active de files d’attente dans les réseaux Ad

hoc.

La comparaison s’est basée sur certains paramètres de performance tels que le débit, la

perte des paquets, le délai d’attente et la taille moyenne de la file d’attente.

Cette investigation nous a conduit a remarqué que chacun de mécanismes étudiés

présente des inconvénients et des avantages, tout dépend du paramètre de performance

évalué.

Parmi ces remarques nous pouvons citer :

Lorsque le mécanisme BLUE tente de maximiser le débit, il fait accroître, énormément, le

délai de bout en bout.

Lorsque le mécanisme ARED tente de stabiliser la longueur de la file d’attente, il fait

décroître le débit d’entrée.

Sensibilité des AQM en fonction des paramètres de l’algorithme.

Le mécanisme REM présente un avantage par rapport aux autres AQM, il permet de

calculer la probabilité de rejet sur le lien tout entier (la probabilité de rejet augmente d’une

manière exponentielle).

Quand la taille du buffer est petite, REM présente une mauvaise sensibilité.

Le mécanisme AVQ est basé sur le débit et la haute utilisation du lien et a une base

théorique plus solide que RED. Il se base sur le taux d’arrivé des paquets au lien pour

détecter la congestion.

Le mécanisme PI permet d’augmenter l’utilisation du lien en maintenant une petite taille

de la file.

Le mécanisme RIO par rapport à RED, adopte le principe de différenciation de services.

Comme perspectives, nous comptons étudier, à travers des simulations, le choix des

meilleurs paramètres de performance de ces mécanismes.


65

Nous comptons aussi de simuler des réseaux Ad hoc dans lesquels circulent des trafics

qui ne sont pas de type CBR (Constant Bit Rate) afin de réguler la consommation de la bande

passante entre ces trafics et de permettre aux applications d’être adaptatives et changer leur

débit en fonction de l’état du réseau. Ainsi de réaliser des simulations qui permettent

d’illustrer l’influence de l’augmentation de la surface, du nombre de nœuds ainsi que de la

vitesse moyenne des nœuds sur l’état des réseaux Ad hoc. Et finalement d’évaluer les

performances des réseaux Ad hoc où circulent différents types de trafics (unicast et multicast).

Annexe A : Résultats de simulation

66



67

(a) RED (b) ARED

Figures A1 : Comparaison des performances de RED et ARED.

Figures A2 : Comparaison des performances de RED et BLUE.

(a) ARED (b) BLUE

Figures A3 : Longueur moyenne de la file d’attente au niveau du routeur utilisant ARED,BLUE.


68

Figure A4 : Débit sortant du routeur utilisant ARED, BLUE.

Figure A5 : Probabilité de marquage pour GRED et REM.


69

Figures A6 : Utilisation du lien et la perte des paquets en fonction du nombre du flux

(a) Tail Drop (b) GREEN

Figures A7: Occupation de la taille de la file par TD et GREEN

Figure A8 : Occupation de la taille de la file par FRED


70

Figures A9 : Utilisation du lien et le délai d’attente pour le mécanisme PI.

Figure A10 : Délai d’attente en fonction de l’utilisation du lien du mécanisme PI.

(a) Utilisation du lien (b) Délai d’attente

Figure A11 : La perte des paquets dans le lienen fonction du nombre de connexion FTP pourles mécanismes AVQ, RED, REM et PI.

Figure A12 : L’utilisation du lienpar les mécanismes AVQ, RED,REM et PI.


Figure A13 : La longueur moyenne de la file dans le lien en fonction du nombre deconnexions FTP pour les mécanismes AVQ, RED, REM et PI.

Figure A15 : Utilisation du lien par lesmécanismes AVQ, RED, REM et PI.

Figure A14 : La perte des paquets dans le lienpour les mécanismes AVQ, RED, REM et PI.

Packet losses at the link for various AQM

71


72

Figures A16 : La longueur de la file d’attente dans le lien pour les mécanismes RED, REM,AVQ et PI.

Figure A17 : Utilisation du lien pourRED, REM, AVQ et PI.

Figure A18 : Le débit total pour RED,REM, AVQ et PI.


73

Figures A21 : La taille de la file : RED (gauche), GRED (centre) et ARED (droit)

Figures A22 : La taille de la file: REDECN (gauche), GREDECN (centre) et AdaptativeREDECN (droit)

Figure A19 : Le débit en fonction de délaid’attente pour RED, Adaptive RED.

Figure A20 : Le taux moyenne d’arrivé enfonction de la longueur moyenne de la file pourRED et Adaptative RED.


74

Figure A23 : L’utilisation du lien pour les mécanismes DT, RED, REM, BLUE et PI.

Figure A24: Délai moyenne pour les mécanismes DT, RED, REM, BLUE et PI.

Figure A25 : Le taux de perte pour les mécanismes DT, RED, REM, BLUE et PI.


75

Figure A26 : Le débit en fonction du tempspour l’algorithme CHOKe.

Figure A27: Le débit en fonction du tempspour l’algorithme FRED.

Figure A28 : Le débit en fonction du tempspour l’algorithme RED.

Figure A29 : Le débit en fonction du tempspour l’algorithme SFED.

Annexe B : Présentation du simulateur NS-2

76



77

1- Introduction

NS est un logiciel qui permet de faire des simulations très avancées sur les différents

types de réseaux. Il est principalement basé sur la conception par objets, la réutilisabilité du

code et la modularité. Il devient aujourd'hui un standard de référence en ce domaine. C'est un

logiciel libre disponible sur l’adresse suivante http://www.isi.edu/nsnam/. Son utilisation est

gratuite pour les travaux de recherche. Le logiciel est exécutable tant sous Linux que sous

Windows. Il est bien adapté aux réseaux à commutation de paquets et à la réalisation de

simulations de petite taille. Il contient les fonctionnalités nécessaires à l'étude des algorithmes

de routage, des protocoles de transport, de session, de réservation, des services intégrés, des

protocoles d'application comme HTTP. De plus le simulateur possède une palette de systèmes

de transmission, d'ordonnanceurs et de politiques de gestion de files d'attente pour effectuer

des études de contrôle de congestion. Ainsi, le NS a pris en charge les communications sans

fil (réseaux Ad hoc et réseaux mobile en générale). Depuis, et après les mises à jours qu’a

connus NS (NS2.26, NS2.28, NS2.33…etc.) plusieurs protocoles de routages ont vu le jour

dont : AODV, DSR, DSDV, TORA, OLSR, TBRPF…etc.

Au départ, NS a été développé au Laboratoire National de Lawrence Berkeley (LBNL)

par le groupe de recherche réseau. Son développement fait maintenant partie du projet VINT

(Virtual InterNetwork Testbed) qui a pour but la construction d’un simulateur réseau offrant

des outils et des méthodes novatrices, dans un environnement proche de la réalité [20]. Ce

simulateur utilise un utilitaire NAM (Network Animator) qui récupère les données textuelles

fournies en sortie et offre une visualisation graphique de la topologie et d’autres utilitaires qui

permettent la conversion vers d'autres outils (comme par exemple xgraph pour dessiner des

courbes).

2- Organisation du simulateur NS-2

NS-2 est écrit en C++ et en OTcl (Object Tool Command Language) et ces deux

langages sont étroitement liés [20]. Quand l’utilisateur crée un nouvel objet via l’interpréteur

OTcl (qui est la version objet de tcl), un objet correspondant est aussi crée dans la hiérarchie

C++. Bien entendu, les objets peuvent être manipulés aussi bien en OTcl qu’en C++, grâce à

la mise en place de procédures de liaison entre les deux langages. La partie codée en C++ est

rapide à exécuter mais plus lente à modifier et est utilisée pour ce qui concerne le

fonctionnement interne des composants du réseau. Celle en OTcl est, quant à elle, plus lente à

http://www.isi.edu/nsnam/


78

l’exécution qu’elle ne l’est à modifier, ce qui la rend optimale pour la configuration des

simulations. L’utilisation de NS-2 se fait en trois étapes comme le montre la figure B1 :

1. L’utilisateur écrit un script OTcl pour définir la topologie du réseau, pour instancier les

différents modules du réseau, pour décrire des scénarios du trafic.

2. NS-2 interprète le script et exécute la simulation. Les résultats sont stockés dans des

fichiers en fonction des commandes du simulateur utilisées.

3. Une fois la simulation terminée, les résultats peuvent être analysées directement avec

l’outil de visualisation NAM ou avec des autres outils.

Figure B1 : Flot de simulation avec NS-2

3- Présentation de Tcl

Tcl (Tool Command Language) a été developpé en 1988 par John K. Ousterhout.

C’est un langage de scripts comme le shell UNIX mais qui sert à contrôler les applications. Il

offre des structures de programmation telles que les boucles, les procédures ou les notions de

variables. Il y a deux principales façons de se servir de Tcl: comme un langage autonome

interprété ou comme une interface applicative d'un programme classique écrit en C ou C++.

En pratique, l'interpréteur Tcl se présente sous la forme d'une bibliothèque de procédures C

qui peut être facilement incorporée dans une application. Cette application peut alors utiliser

les fonctions standards du langage Tcl mais également ajouter des commandes à l'interpréteur

[3].

La _n de ligne est le délimiteur d'instructions. Les commentaires commencent par un #

et finissent à la fin de ligne. Les variables ont toujours le type chaîne de caractères (ou liste de

chaînes). La valeur de la variable de nom a est $a. Les variables sont toujours instanciées

avant l'exécution d'une instruction, même à l'intérieur d'une chaîne de caractères.

Le tableau suivant décrit les principales instructions.


79

Commentaires les commentaires sont introduits par le caractère #

set a 10 affecter la chaîne de caractères 10 à la variable a

set a "une chaîne de car" Autre affectation

set b $a affecter le contenu de la variable a à la variable b

puts $b Imprimer le contenu de la variable b

puts "B vaut $b" Idem, mais à l'intérieur d'une chaîne de caractères. B est évaluée

set a(couleur) "red" les tableaux ont des indices qui sont des chaînes de caractères

[fonc par1 par2] appeler la fonction fonc avec des paramètres

set obj [new Class1/Class2] Créer une instance d'un objet

[$obj meth par1 par2] invoquer la méthode meth de l'objet obj

$obj set field val Instancier une variable de l'objet obj

set a [$obj set field] Récupérer la valeur d'une variable de l'objet obj

[expr $a + 6 * $b] évaluer l'expression arithmétique

set f [open "File" w] ouvrir le fichier de nom File en écriture, et mettre le descripteur dans f

puts $f "truc" écrire une chaîne dans le fichier de descripteur f

exec xemacs & Exécuter un processus système (en arrière plan avec &)

if { $a = $b } { # code if }else { # code else }

les structures de contrôle sont : pour les tests

for { set i 0 } { $i < 10 } {incr i} { # code de la boucle }

les structures de contrôle sont : pour les boucles

proc fonc {par1 par2} {global var1 var2 # codereturn $quelquechose}

définition des fonctions. où l'instruction globale permet de faireréférence à des variables globales du script tcl.

4- Présentation de OTcl

OTcl (Object Tool Command Language), est la version objet de tcl. Les classes sont

également des objets avec des possibilités d'héritage. Il est facilement possible d’établir une

analogie entre OTcl et le C++ comme le montre le tableau suivant :

C++ OTcl

Unique déclaration de classe Les méthodes sont attachées à un objet ouune classeMéthodes appelées l’objet en préfixe

Constructeur/Destructeur init{}/destroy{}L'identification de l'objet lui-même this enC++

$self en OTcl

Les méthodes sont tout le temps « virtual »détermination de la méthode à appelereffectuée à l’exécution


80

Les méthodes non définies dans la classeappelées explicitement avec l’operateur deportée « :: »

Appel de méthode de même nom de classeparant

Méthodes implicitement appelées dansl’arbre d’héritage par « $self next »

L’héritage multiple possible L’héritage multiple possible

AttributsMéthodesVoid XTP : Send(Char* data)

Déclaration de variable d’instance : instvarDéclaration méthode de classe : instprocXTP : instproc Send {data}

5- Architecture du réseau

L’architecture réseau de NS-2 est basée sur le modèle des couches OSI. NS2 est un

simulateur à événements discrets, chaque activité physique sur le réseau est traduite en un

événement qui est mis en file d’attente. A chaque événement est attribué un instant de

traitement, permettant d’ordonnancer cette file. Un modèle de réseau en NS-2 est constitué de:

5.1-Nœuds de réseau

Endroit où est généré le trafic, ou nœuds de routage. Chaque nœud (classe OTcl :

Node) est composé de Classifiers et d’Agents. Les Classifiers démultiplexent les flux des

paquets. Les Agents gèrent le protocole. Ils sont les producteurs et les consommateurs de

paquets. Lorsqu’un paquet arrive dans le nœud, il est orienté vers un des liens raccordés au

nœud en fonction de son adresse de destination.

Chaque nœud possède une adresse (id_). Si l’adresse est celle du nœud, le paquet est

reçu par l’Agent dont le port correspond. Il n’y a pas de durée modélisée pour ces traitements

au niveau du nœud. Les noms suivis du caractère « _ » correspondent à des variables internes

de la classe Node. Entry_ pointe sur le premier Classifier à l’entrée du nœud. Cette entrée est

utilisée à la fois par les paquets venant d’un autre nœud et par les Agents raccordés au nœud

comme le montre la figure B2.


81

Figure B2 : Composant d’un nœud unicast NS-2.

5.2- Liens de communication entre les réseaux

Qui servent à raccorder les nœuds entre eux. Les caractéristiques principales d’un lien

sont la bande passante et le délai de propagation (géré par l’élément link_). Un lien contient

également une file d’attente (queue_) avec différentes politiques de gestion possible, un

élément pour gérer les pertes de paquets (dropphead_) en fonction de l’état de la file d’attente

et un élément pour gérer la durée de vie des paquets (ttl_) figure B3.

Figure B3 : Composant d’un lien NS-2

5.3- Agents de communication

Représentant les protocoles de niveau transport (TCP, UDP) ; ces agents sont attachés

aux nœuds et connectés l'un à l'autre, ce qui représente un échange de données (connexion

TCP, flux UDP).


82

5.4- Applications

Qui génèrent le trafic de données selon certaines lois, et se servent des agents de

transport.

6- Principe d’utilisation

Pour terminer et illustrer bien cette présentation du simulateur NS-2, nous allons

présenter un exemple simple de modélisation d’un réseau. L’objectif est de montrer comment

à partir d’un script OTcl, il est possible de définir un réseau, de générer un trafic et de lancer

une simulation. À travers ce langage, l'utilisateur décrit les conditions de la simulation :

topologie du réseau, caractéristiques des liens physiques telles que le débit, le délai, les

protocoles utilisés, communications...etc.

La simulation doit d'abord être saisie sous forme de fichier texte que NS utilise pour

produire un fichier trace contenant les résultats. Donc la première des choses il faut que nous

programmions un fichier avec l'extension .tcl dont on mettra des instructions spéciales pour

mettre en œuvre notre simulation.

Notre premier programme consistera en deux nœuds reliés par un lien qu’on compilera

et on verra l’animation (figure B4), pour cela il faut suivre les étapes suivantes :

Ouvrez un fichier texte et enregistrez le sous le nom "premier_exemple.tcl"

La première instruction à mettre dedans c'est :

set ns [new Simulator]

Par la suite nous mettrons deux instructions qui permettrons de créer un fichier .nam qui

servira pour un fichier d'animation :

set nf [open anim.nam w]

$ns namtrace-all $nf

Comme vous pouvez le constater notre fichier animation se nomme "anim.nam", la deuxième

ligne ordonne NS à mettre toute la trace du notre programme dans notre fichier.

Nous allons maintenant déclarer nos deux nœuds n0 et n1 :

set n0 [$ns node]

set n1 [$ns node]


83

Maintenant on crée le lien entre ces deux nœuds avec une bande passante 1Mb et un délai

de 10ms et une queue de type Droptail :

$ns duplex-link $n0 $n1 1Mb 10ms DropTail

Chaque programme de simulation doit contenir une procédure de fin, dont voici la

structure pour notre petit programme qui ne fait rien :) (Juste deux nœuds et un lien) :

proc finish {} {

global ns nf

$ns flush-trace

close $nf

exec nam anim.nam &

exit 0

}

Cette procédure va appeler notre fichier animation et l'ouvrir en fin de l'exécution de notre

simulation.

On va ajouter une instruction qui permettra d'appellerai la procédure fininsh après 6

secondes du lancement de la simulation :

$ns at 6.0 "finish"

En fin on mettra l'instruction qui permettra à NS d'exécuter le programme de simulation :

$ns run

Figure B4: Capture d’écran NAM

Bibliographie et Webographie

84



85

[1] P. Alberto de Barros et M. El Koutbi, “Enhancing MAODV performance using Active

Queue Management, ” NGNS’09, Rabat, Maroc, 4-6 juin 2009.

[2] F. AL-Raddady, M. Woodward, “A new active congestion control mechanism for the

Internet,” 2008. Online at: http://www.comp.brad.ac.uk/het-net/tutorials/WP06.pdf

[3] P. Anelli & E. Horlait, “NS-2: Principes de conception et d'utilisation, ” UPMC - LIP6

: Laboratoire d'Informatique de Paris VI 8, Rue du Capitaine Scott 75015 paris France.

[4] F. Anjum and L. Tassiulas, “Fair bandwidth sharing among adaptive and non-

adaptive flows in the Internet,” In Proc. IEEE INFOCOM’99, New York, NY, March

1999.

[5] F. M. Anjum and L. Tassiulas, “Balenced-RED: An Algorithme to achieve Faireness in

the Internet,” University of Maryland at College Park, March 8, 1999.

[6] S. Athuraliya, V. H. Li, S. H. Low, and Q. Yin, “REM: Active Queue Management,”

IEEE Network, May 2001.

[7] J. Aweya, M. Ouellette and D.Y. Montuno, “A control theoretic approach to active

queue management,” Computer Networks 36 (2001), pp. 203–235, 2001.

[8] G. Benjamin, “Traitement différencié et marquage adaptatif de paquets pour le

transport des flux hétérogènes dans l'Internet,” These de doctorat, l'Université Claude

Bernard -Lyon 1, pp.12-13, 18 décembre 2003.

[9] C. Bernard, “Les mécanismes de contrôle de congestion dans ATM, ” Laboratoire

IRISA Université de Rennes-1, Campus universitaire de Beaulieu 35042 RENNES.

[10] C. Brandauer, G. Iannaccone, C. Diot, T. Ziegler, M. May and S. Fdida, “Comparison

of Tail Drop and Active Queue Management Performance forbulk-data and Web-

like Internet Traffic,” in Proceedings of the Sixth IEEE Symposium on Computers and

Communications, IEEE ISCC 2001.

[11] P.K Chong, S.W. Tan and S.W. Lee, “A Performance Comparison of BLUE and

RED AQM using ECN and non-ECN Traffic,” Conference Paper, MMU, 2002.

http://www.comp.brad.ac.uk/het-net/tutorials/WP06.pdf


86

[12] J. Chung and M. Claypool, "Analysis of active queue management," In Proceedings

of the 2nd IEEE International Symposium on Network Computing and Applications

(NCA), Cambridge, Massachusetts, USA, April 2003. Online at:

http://www.cs.wpi.edu/~claypool/papers/queue-law/

[13] J. Chung and M. Claypool, “Aggregate Rate Control for Efficient and Practical

Congestion Management,” Online at: ftp://ftp.cs.wpi.edu/pub/techreports/pdf/04-03.pdf

[14] D. Clarkand W. Fang, “Explicit allocation of best-effort packet delivery service,”

IEEE/ACM Transactions on Networking, 6(4):362–373, August 1998.

[15] A. Dada et A. Bennia, “Algorithme de contrôle réactif de la congestion sur un

nœud ATM, ” RIST Vol.14 n°02 Année 2004.

[16] M. Dawoud, “ Analyse du protocole AODV, ” DEA d'Informatique, Université

libanaise, Faculté des sciences, No

d'ordre: 6/2006, Université Paul Sabatier – I.R.I.T,

2005/2006.

[17] D. El Ouadghiri et K. El Yassini, “Les mécanismes de gestion active des files

d’attente: RED et ses variantes,” 1er Workshop International sur l’Informatique Mobile

et Applications, Hôtel Kenzi Farah, Marrakech, Maroc, Lundi 4 juin 2007.

[18] L. Emmanuel and T. Bruno, “Managing network congestion with a Kohonen-based

RED queue,” IEEE, International Conference on Communications, Beijing, China, 19- 23

May 2008.

[19] M. Erwan ERMEL, “Localisation et Routage géographique dans les réseaux sans

fil hétérogènes, ” Thèse de Doctorat, Université Paris VI Pierre et Marie CURIE, 21 Juin

2004.

[20] K. Fall and K. Varadhan, “The ns Manual (formerly ns Notes and

Documentation),” The VINT ProjectA Collaboration between researchers at UC

Berkeley, LBL, USC/ISI, and Xerox PARC, January 6, 2009.

[21] W.-C. Feng, A. Kapadia, and S. Thulasidasan, “GREEN: proactive queue

management over a best-effort network,” In Proc. IEEE GLOBECOM’02, Taipei,

Taiwan, November 2002.

http://www.cs.wpi.edu/~claypool/papers/queue-law/

ftp://ftp.cs.wpi.edu/pub/techreports/pdf/04-03.pdf


87

[22] W.C. Feng, D.D. Kandlur, D. Saha and K.G. Shin “BLUE: A New Class of Active

Queue Management Algorithms,” Technical Report CSE-TR-387-99, Department of

EECS, University of Michigan, April 1999.

[23] S. Floyd and K. Fall, “ Ns Simulator Tests for Random Early Detection (RED)

Queue Management ,” Online at: http://www.aciri.org/floyd/red.html

[24] S. Floyd and V. Jacobson, "Random Early Detection Gateways for Congestion

Avoidance," ACM/IEEE Transaction on Networking, Vol. 1, pp 397-413, August 1993.

[25] S. Floyd, “Recommendations on using the gentle variant of RED,” March, 2000.

[Online]. Available: http://www.aciri.org/floyd/red/gentle.html

[26] S. Floyd, R. Gummadi, and S. Shenker, “Adaptive RED: An algorithm for

increasing the robustness of REDs Active Queue Management,” technical report,

international computer science institute, August 1, 2001. [Online]. Available:

http://www.icir.org/floyd/red/gentle.html.

[27] V. V. Govindaswamy, G. Záruba and G. Balasekaran, “Receiver-Window Modified

Random Early Detection (RED-RWM) Active Queue Management Scheme:

Modeling and Analysis,” in the IEEE ICC 2006 proceedings.

[28] U-K. Guillaume, “De la qualité de service à l’analyse de trafic,” Thèse

d’habilitation à diriger des recherches, 11 décembre 2006.

[29] L. Guy et K. Ludovic, “Spécification formelle des mécanismes de support des

qualités de service dans l'Internet,” Dans l’ouvrage de CAVALLI Ana: Ingénierie des

protocoles et qualité de service, chapitre 3. Ed. Lavoisier 2000.

[30] Y. Hadjadj Aoul, A. Mehaoua, “Gestion active des files d’attente pour les flux

sensibles aux délais dans le réseau Internet,” In Proc. of GRES 2005, The International

Congress on Networks Management, Luchon, France, February 28th, 2005.

[31] A. Haider, H. Sirisena, K. Pawlikowski, & M.J. Ferguson, “Congestion Control

Algorithms in High Speed Telecommunication Networks,” Thanks to PA Consulting

Group, Charles River Associates, and Jade Corp. for supporting Conference, November

30, 2001.

http://www.aciri.org/floyd/red.html

http://www.aciri.org/floyd/red/gentle.html

http://www.lavoisier.fr/fr/livres/detail.asp?texte=270500&action=new&select=auteur

http://www.lavoisier.fr/fr/livres/not2.asp?id=3LKLX3TO2RAOKE&rec=oui&pos=0&referer=%2Ffr%2Fdetail.asp%3Faction%3Dcurrent

http://www.lavoisier.fr/fr/livres/not2.asp?id=3LKLX3TO2RAOKE&rec=oui&pos=0&referer=%2Ffr%2Fdetail.asp%3Faction%3Dcurrent

http://www.irit.fr/gres05/


88

[32] Go Hasegawa, and Masayuki Murata, “Analysis of dynamic behaviors of many

TCP connections sharing Tail-Drop/RED routers,” IEEE GLOBECOM 2001,

November 2001.

[33] S. HOCEINI, “Techniques d’Apprentissage par Renforcement pour le Routage

Adaptatif dans les Réseaux de Télécommunication à Trafic Irrégulier,” Thèse de

doctorat, Université Paris Xii – Val De Marne, 23 Novembre 2004.

[34] C. Hollot, V. Misra, D. Towsley, and W. Gong, “Analysis and design of controllers

for AQM routers supporting TCP flows,” IEEE Transactions on Automatic Control,

47(6):945–959, June 2002.

[35] C.V. Hollot, V. Misra, D. Towlsey, and W. Gong, “A control theoretic analysis of

RED,” in Proceedings of INFOCOM, Alaska, Anchorage, April 2001.

[36] T. Hutschenreuther and A. Schill, “Content based discarding in IP router,” In Proc.

IC3N’00, pages 122–126, Las Vegas, Nevada, October 2000.

[37] K. II-Won, “Les tic pour l’entreprise communicante: contribution a la

modélisation de l’infrastructure de communication et gestion de la qualité de

service," Thèse de doctorat, l’Institut National des Sciences Appliquées de Lyon, pp. 63-

73, 94-108, 17 octobre 2002.

[38] V. Jacobson, K. Nichols and K. Poduri, “RED in a Different Light,” Draft of

September 30, 1999.

[39] R. Julien, “Modélisation mathématique et simulation de TCP par des méthodes

de champ moyen,” These de doctorat, Ecole Doctorale de l'Ecole Polytechnique -

Palaiseau, INRIA, 15 septembre 2006.

[40] A. Kamra, S. Kapila, V. Khurana, V. Yadav, R. Shorey, H. Saran and S. Juneja.,

“SFED: A Rate Control Based Active Queue Management Discipline,” IBM India

research laboratory Research Report ,available online from :

http://www.cse.iitd.ernet.in/srajeev/publications.htm


89

[41] A. Kapadia, W.-C. Feng, and R. Campbell, “GREEN: a TCP equation-based

approach to active queue management,” Technical report, University of Illinois,

February 2004.

[42] J. Koo, S. Ahn, and J. Chung, “Performance Analysis of Active Queue

Management Schemes for IP Network,” ICCS 2004, LNCS 3036, pp. 349–356, 2004.

Springer-Verlag Berlin Heidelberg 2004.

[43] S. Kunniyur and R. Srikant, “An adaptive virtual queue (AVQ) algorithm for

active queue management,” IEEE Transactions on Networking, pages 286–299, April

2004.

[44] S. Kunniyur and R. Srikant, “Analysis and design of an adaptive virtual queue

(AVQ) algorithm for active queue management,” in Proceedings of SIGCOMM, San

Diego, CA, August 2001.

[45] L. Le, J. Aikat, K. Jeffay and F. D. Smith, “The Effects of Active Queue

Management and Explicit Congestion Notification on Web Performance,” In proc.

IEEE/ACM Transactions on Networking, 2005.

[46] D. Lin and R. Morris, “Dynamics of Random Early Detection,” Computer

Communication Review, Proceedings of ACM SIGCOMM 1997, vol.27 No.4, pp. 127-

137, 1997.

[47] C.N. Long, B. Zhao, X.P. Guan, “SAVQ: stabilized Adaptive Virtual Queue

Management Algorithm,” IEEE Communications Letters, VOL. 9, NO. 1, January 2005.

[48] R. Mahajan and S. Floyd, “Controlling High-Bandwidth Flows at the Congested

Router,” IEEE Computer Society Washington, DC, USA, November 20, 2000.

[49] M. Martin, “Evaluation quantitative des nouveaux mécanismes de gestion de la

qualité de service dans Internet,” Thèse de doctorat, Université de Nice-Sophia

Antipolis, pp. 106-115, 8 octobre 1999.

[50] M. May, T. Bonald and J. Bolot, “Analytical evaluation of RED performance,” in

IEEE INFOCOM, 2000, Vol. 3 pp. 1415-1424.


90

[51] W. Michael, “Network Congestion Control Managing Internet Traffic,” John

Wiley & Sons, Ltd, pp. 129-138, 2005.

[52] S. Mišković, G. Petrović, and L. Trajković, “Implementation and Performance

Analysis of Active Queue Management Mechanisms,” in: Telecommunications in

Modern Satellite, Cable and Broadcasting Services, 2005. 7th International Conference

on, IEEE.

[53] V. Misra, W. Gong, and D. Towlsey, “A fluid-based analysis of a network of AQM

routers supporting TCP flows with an application to RED,” in Proceedings of

SIGCOMM, Stockholm, Sweden, September 2000.

[54] T.J. Ott, T.V. Lakshman and L. Wong, “SRED: Stabilized RED,” Proceedings of

IEEE INFOCOM 1999, pp. 1346-1355, March 1999.

[55] R. Pan, B. Prabhakar and K. Psounis, “CHOKe: A stateless active queue

management scheme for approximating fair bandwidth allocation,” IEEE INFOCOM

2000.

[56] Q. X. Pang, S. C. Liew, W. Wang, and V. O.K. Li, “Performance Study of TCP

Veno over WLAN and RED Router,” IEEE Globecom 2003, Dec 2003.

[57] J. Prabhu Balakrishna, “Markov chains and decision processes for congestion

avoidance and power control,” These de doctorat, Université de Nice- Sophia Antipolis,

INRIA, pp. 93-110, 4 octobre 2004.

[58] S. Ryu, C. Rump and C. Qiao, “Advances in internet congestion control,” In proc.

IEEE Communications Surveys & Tutorials • Third Quarter 2003.

[59] G. Thiruchelvi and J. Raja, “A Survey On Active Queue Management

Mechanisms,” IJCSNS International Journal of Computer Science and Network Security,

VOL.8 No.12, December 2008.

[60] A. Tigist, “ Evaluation des Performances des Mécanismes de Qualité de Service

dans l’Internet,” Thèse de doctorat, Université de Montpellier II, 13 décembre 2004.

http://ieeexplore.ieee.org/xpl/RecentCon.jsp?punumber=10500




91

[61] L. Toumi, “Algorithmes et mécanismes pour la qualité de service dans des réseaux

hétérogènes,” Thèse de doctorat, Institut National Polytechnique de Grenoble, pp.72-75,

20 décembre 2002.

[62] C. G. Wang, B. Li, T. Y. Hou, K. Sohraby, and Y. Lin, “LRED: a robust active

queue management scheme based on packet loss ratio,” In Proc. INFOCOM’04,

March 2004.

[63] B.P.Wydrowski, “Techniques in Internet Congestion Control,” Thèse de doctorat,

Electrical and Electronic Engineering Department the University of Melbourne, February

2003.

[64] D. Xidong, “Network queue management and congestion control in internet and

wireless networks,” These de doctorat, The Pennsylvania State University the Graduate

School College of Engineering, August 2004.

[65] S. Ye-Qiong, “Garantir la Qualité de Service Temps Réel: Ordonnancement et

Gestion de Files d’Attente,” ERT, 7 septembre 2007.

[66] T. Zahratahdi, “Algorithmes pour la différenciation proportionnelle de délai dans

Internet,” Thèse de doctorat, Université Mohammed V – Agdal, pp. 71-75, Rabat,

Maroc, 1er novembre 2008.

[67] B. Zheng and M. Atiquzzaman, “DSRED: an active queue management scheme for

next generation networks,” In Proc. LCN’00, pages 242–251, Tampa, Florida,

November 2000. Mentioned on page(s) 35, 52.

Documents

Pfe-said El Kafhali