4
1 er Colloque National de Modélisation et Traitement de l’Information (CoMTI 2009) Tétouan, les 29-30 Mai 2009 Etude et comparaison des mécanismes de gestion active de files d’attente dans les réseaux de télécommunication Said EL KAFHALI Mohamed HANINI Abdelkrim HAQIQ Faculté des Sciences et Techniques Département de Mathématiques et Informatique B.P. 577, Route de Casablanca, Settat, Maroc E-mails: {kafhalisaid, haninimohamed, ahaqiq}@gmail.com RésuméLes mécanismes de gestion des files d’attente se sont avérés d’une grande utilité pour éviter la congestion des buffers dans les réseaux de télécommunication. 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 cet article, on propose de faire une étude de différents mécanismes de gestion active des files d’attente, notamment le mécanisme RED (Random Early Detection) et ses variantes Gentle RED, Adaptive RED, REM ainsi que BLUE, et de faire ensuite une comparaison des performances de ces mécanismes. Mots clés; Réseaux de télécommunication, Congestion, Files d’attente, Gestion active des files d’attente, RED. I. INTRODUCTION 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 on é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 [13]. 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 utilisé pour gérer les files d’attente, ce mécanisme n’élimine les paquets que lorsque la taille maximale du buffer est atteinte. En dépit de la simplicité d’implémentation de TD, ce mécanisme présente quelques inconvénients : 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épendante de la taille de la file. Plusieurs AQM ont été proposé dans la littérature ; Floyd et Jacobson ont présenté l’algorithme RED (Rondom Early Detection) dont plusieurs variantes améliorées ont été ensuite proposées. Dans ce papier on propose de faire une présentation et une comparaison des performances des mécanismes : RED, GRED, ARED, REM, et BLUE. Ce papier est organisé comme suit : dans la section II cinq mécanismes de gestion active de file d’attente sont présentés. La section III présente une comparaison des mécanismes étudiés. La section IV donne une conclusion et des perspectives. II. PRÉSENTATION DE QUELQUES MÉCANISMES DE LA GESTION ACTIVE DES FILES DATTENTE A. RED ( Random Early Detection) Le RED a été proposé par S. Floyd et V.Jacobson en 1993 [5]. 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 Tail Drop, pour lequel un buffer saturé entraîne la baisse des débits de toutes les sources qui l’utilisent (problème de synchronisation). Le mécanisme RED rejette les paquets entrants avec une certaine probabilité avant que les buffers ne soient pleins [10]. 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. 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 q avg w avg wq

Said El Kafhali Comti 2009

Embed Size (px)

Citation preview

Page 1: Said El Kafhali Comti 2009

1er Colloque National de Modélisation et Traitement de l’Information (CoMTI 2009)

Tétouan, les 29-30 Mai 2009

Etude et comparaison des mécanismes de gestionactive de files d’attente dans les réseaux de

télécommunication

Said EL KAFHALI Mohamed HANINI Abdelkrim HAQIQFaculté des Sciences et Techniques

Département de Mathématiques et InformatiqueB.P. 577, Route de Casablanca, Settat, Maroc

E-mails: {kafhalisaid, haninimohamed, ahaqiq}@gmail.com

Résumé— Les mécanismes de gestion des files d’attente se sontavérés d’une grande utilité pour éviter la congestion des buffersdans les réseaux de télécommunication. Ces mécanismes sediffèrent par la méthode de sélection des paquets rejetés. Ondistingue alors deux catégories de mécanismes: les mécanismespassifs (PQM : Passive Queue Management) et les mécanismesactifs (AQM: Active Queue Management). Dans cet article, onpropose de faire une étude de différents mécanismes de gestionactive des files d’attente, notamment le mécanisme RED(Random Early Detection) et ses variantes Gentle RED, AdaptiveRED, REM ainsi que BLUE, et de faire ensuite une comparaisondes performances de ces mécanismes.

Mots clés; Réseaux de télécommunication, Congestion, Files d’attente,Gestion active des files d’attente, RED.

I. INTRODUCTION

Le contrôle de congestion dans les files d’attente, désignel’ensemble des actions du réseau qui permettent de minimiserl’intensité et les effets d’un éventuel état de congestion.Pour réaliser ce contrôle plusieurs algorithmes on été proposésdans la littérature, leur rôle commun est de décider quand etcomment éliminer des paquets afin d’éviter la congestion duréseau [13].La performance d’un tel algorithme peut être évaluée par sacapacité à contrôler le trafic d’une manière efficacegarantissant une quantité de service acceptable pendant lespériodes de congestion. Tail Drop (TD) est le mécanismeclassique utilisé pour gérer les files d’attente, ce mécanismen’élimine les paquets que lorsque la taille maximale du bufferest atteinte.En dépit de la simplicité d’implémentation de TD, cemécanisme présente quelques inconvénients : 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 quisubissent des pertes au même moment et ralentissentsimultanément leurs débits.

Il pénalise les flux qui envoient le trafic en rafles, et peutconduire à une monopolisation du lien par certainesconnexions.

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

Pour remédier aux inconvénients du TD, les mécanismes degestion active des files d’attente (AQM) adoptent uneapproche préventive en éliminant les paquets avant lasaturation du buffer, et ceci avec une probabilité dépendantede la taille de la file.Plusieurs AQM ont été proposé dans la littérature ; Floyd etJacobson ont présenté l’algorithme RED (Rondom EarlyDetection) dont plusieurs variantes améliorées ont été ensuiteproposées.Dans ce papier on propose de faire une présentation et unecomparaison des performances des mécanismes : RED,GRED, ARED, REM, et BLUE.Ce papier est organisé comme suit : dans la section II cinqmécanismes de gestion active de file d’attente sont présentés.La section III présente une comparaison des mécanismesétudiés. La section IV donne une conclusion et desperspectives.

II. PRÉSENTATION DE QUELQUES MÉCANISMES DE LA

GESTION ACTIVE DES FILES D’ATTENTE

A. RED ( Random Early Detection)

Le RED a été proposé par S. Floyd et V.Jacobson en 1993 [5].Son objectif est, d’une part, de contrôler la longueur de la filed’attente dans les buffers et, d’autre part, d’éviter lesinconvénients du Tail Drop, pour lequel un buffer saturéentraîne la baisse des débits de toutes les sources qui l’utilisent(problème de synchronisation).Le mécanisme RED rejette les paquets entrants avec une

certaine probabilité avant que les buffers ne soient pleins [10].Pour détecter la congestion, RED maintient une moyennemouvante qui est pondérée de manière exponentielle pour lalongueur de la file d’attente.Le paramètre avg qui désigne la taille moyenne de la filed’attente est initialisé à 0, et à chaque arrivée d’un paquet,avg prend la valeur :

(1 )q qavg w avg w q

Page 2: Said El Kafhali Comti 2009

1er Colloque National de Modélisation et Traitement de l’Information (CoMTI 2009)

Tétouan, les 29-30 Mai 2009

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 lataille 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. Cetteprobabilité 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 [9].

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.

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.

B. GRED (Gentle RED)

Le GRED proposé dans [7] est une amélioration de RED, ils’en diffère par les points suivants : 100% de rejet des paquets est effectué seulement quand

avg est deux fois égale au thMax .

Quand 2th thMin avg Max , le GRED commence à

rejeter aléatoirement les paquets entrants avec laprobabilité Q donnée ci-dessous. Cette probabilité

augmente de manière linéaire par morceaux en fonctionde 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

C. ARED (Adaptative RED)

L’idée de base pour une solution résolvant les problèmes deRED repose sur le ARED proposé par Feng et Al. en 2001 [6].Ce mécanisme 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 tropagressive. 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 .

D. Random Exponential Marking (REM)

Le REM (Random Exponential Marking) est proposé parAthuraliya et Al dans [1]. Son idée majeure est de stabiliserles débits autour de la capacité du lien, et de garder lalongueur de la file petite autour d’une valeur cibleprédéterminée.Le mécanisme définit une variable coût en charge del’utilisateur, qui doit être grande au temps de la congestion.La variable coût noté C(t) est définie comme une sommepondé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.

La probabilité d’éliminer/marquer un paquet est alors calculé

comme suit :( )1 C tP où est une constante ( 1) .

E. BLUE

Le BLUE a été proposé par Feng et Al. [4]. C’est le premiermécanisme de gestion active des files d’attente qui ne prendpas en compte la longueur de la file d’attente pour calculer laprobabilité de perte des paquets. Il est utilisé pour améliorerles performances de RED en termes d’estimation des paquetsperdus et la taille du buffer du réseau.L’algorithme de ce mécanisme est le suivant:

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

Page 3: Said El Kafhali Comti 2009

1er Colloque National de Modélisation et Traitement de l’Information (CoMTI 2009)

Tétouan, les 29-30 Mai 2009

freeze_time: l’intervalle du temps minimal entre deuxmises à 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.

III. COMPARAISONS

La comparaison entre les mécanismes TD et RED, était sujetde plusieurs travaux de recherche, les résultats de simulationobtenus dans [11] et [12] (figures 1 et 2), montrent que REDréduit de manière très claire (presque la moitié) la taillemoyenne de la file d’attente, de même RED diminue le délaid’attente des paquets par rapport à TD. Cependant REDprésente un taux de perte élevé en comparaison avec TD.

Figure 1 : Comparaison de TD et RED.

Figure 2 : Comparaison entre TD, RED et REM.

La figure 3, qui explicite les résultats de simulation réaliséepar les auteurs de l’article [3], montre qu’avec le mécanismeRED, le délai d’attente des paquets est nettement plus élevéque celui avec ARED. Alors que le taux de paquets rejetésavec RED est inférieur à celui de ARED. Par ailleurs les deuxmécanismes assurent le même débit.

(a) RED (b) ARED

Figure 3: Comparaison des performances de RED et ARED.

En se referant aux résultats obtenus dans [2] et [4] (figure 4),on peut remarquer que lorsque le nombre de connexionaugmente, le mécanisme BLUE garde toujours un débit

meilleur et relativement stable que celui de RED. Et avec cedernier le taux de perte de paquets est nettement plus élevéqu’avec le mécanisme BLUE.

Figure 4 : Comparaison des performances de RED et BLUE.

En se basant sur les simulations faites dans [8] (figures 5 et 6),on peut remarquer que ARED présente une fluctuation plusimportante par rapport à BLUE au niveau de la longueurmoyenne de la file d’attente. On peut aussi observer queBLUE maximise l’utilisation des ressources, et parconséquence il maximise le débit sortant (en évitant toute sousutilisation de la file d’attente). ARED offre un débit assezconstant et moins performant par rapport à BLUE. En contrepartie, cela induit un très grand délai de bout en bout, ce quiest nuisible pour les applications temps réel et multimédia.

(a) ARED (b) BLUE

Figure 5 : Longueur moyenne de la file d’attente au niveau du routeurutilisant ARED, BLUE.

Le mécanisme REM se distingue de tous les autresalgorithmes présentés par le fait de prendre en considération lecoût de la congestion qui dépend du nombre de sourcesutilisant le lien [1]. Par ailleurs, la probabilité demarquage/suppression dans REM augmente d’une manièreexponentielle selon le niveau de congestion au moment oùcelle-ci augmente de manière linéaire (pour RED) ou linéairepar morceau (pour GRED) (figure 7).

Page 4: Said El Kafhali Comti 2009

1er Colloque National de Modélisation et Traitement de l’Information (CoMTI 2009)

Tétouan, les 29-30 Mai 2009

Figure 6 : Débit sortant du routeur utilisant ARED, BLUE.

La figure 2, résultat des simulations effectuées par les auteursde l’article [11], montre que RED et REM réalisent des tauxde suppression de paquet relativement proches mais qui restesupérieur à celui dans TD. La longueur moyenne de la filed’attente pour REM est relativement inférieure à celle deRED ; au moment où le débit pour REM est inférieur à celuide RED et de TD.

Figure 7 : Probabilité de marquage pour GRED et REM.

IV. CONCLUSION ET PERSPECTIVE

Dans cet article, on s’est intéressé à l’étude et la comparaisonde certains mécanismes de gestion active des files d’attentedans les réseaux de télécommunication, tels que RED, GRED,ARED, REM et BLUE. On s’est intéressé aussi à une étudecritique de ces mécanismes.La comparaison s’est basée sur certains paramètres deperformance tels que le débit, la perte des paquets, le délaid’attente et la taille moyenne de la file d’attente.On a remarqué que chacun de mécanismes étudiés présentedes inconvénients et des avantages, tout dépend du paramètrede performance évalué. Par exemple, lorsque BLUE tente demaximiser le débit, il fait accroître, considérablement, le délaide bout en bout, et lorsque ARED tente de stabiliser lalongueur de la file d’attente, il fait décroître le débit d’entrée.Comme perspective nous pourrions étudier, à travers dessimulations, le choix des paramètres qui assurent lesmeilleures performances de certains mécanismes AQM.

BIBLIOGRAPHIE

[1] S. Athuraliya,V. H. Li, S. H. Low, and Q. Yin, “REM: Active Queue

Management”, IEEE Network, May 2001.[2] Chong, P.K., Tan, S.W. and Lee, S.W, “A Performance Comparison of

BLUE and RED AQM using ECN and non-ECN Traffic”, ConferencePaper, MMU, 2002.

[3] L. Emmanuel et Talavera Bruno, “Managing network congestion with aKohonen-based RED queue”, IEEE, International Conference onCommunications, Beijing, China, 19- 23 May 2008.

[4] W. Feng, D. Kandlur Dilip, Saha Debanjan and G. Shin Kang, “BLUE:A New Class of Active Queue Management Algorithms”, TechnicalReport CSE-TR-387-99, Département de EECS, Université duMichigan, avril 1999.

[5] S. Floyd and V. Jacobson, "Random Early Detection Gateways forCongestion Avoidance", ACM/IEEE Transaction on Networking, 1(4):pgs 397-413, August 1993.

[6] S. Floyd, R. Gummadi, and S. Shenker, “Adaptive red: An algorithm forincreasing the robustness of red”, technical report, internationalcomputer science institute, August 2001.

[7] S. Floyd, “Recommendations on using the gentle variant of RED”, 2000.http://www.aciri.org/floyd/red/gentle.html

[8] Y. HADJADJ AOUL, A. MEHAOUA, “Gestion active des filesd’attente pour les flux sensibles aux délais dans le réseau Internet”, InProc. of GRES 2005, The International Congress on NetworksManagement, Luchon, France, February 28th, 2005.

[9] L. TOUMI, “Algorithmes et mécanismes pour la qualité de servicedans des réseaux hétérogènes ”, Thèse de doctorat, Institut NationalPolytechnique de Grenoble, pp.72-75, 20 décembre 2002.

[10] B.P.Wydrowski, “Techniques in Internet Congestion Control”, Thèse dedoctorat, Electrical and Electronic Engineering Department TheUniversity of Melbourne, February 2003.

[11] D. Xidong, “Network queue management and congestion control ininternet and wireless networks”, thèse de doctorat, The PennsylvaniaState University the Graduate School College of Engineering, August2004.

[12] S. Ye-Qiong, “Garantir la Qualité de Service Temps Réel:Ordonnancement et Gestion de Files d’Attente”, ERT, 7 septembre2007.

[13] T. ZAHRATAHDI, “Algorithmes pour la différenciation proportionnellede délai dans Internet”, Thèse de doctorat, Université Mohammed V –Agdal, pp. 71-75, 1er novembre 2008.