Upload
said-el-kafhali
View
184
Download
2
Embed Size (px)
Citation preview
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
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.
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).
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.