QoS SUPPORT IN EDGE ROUTERS - Archive ouverte HAL Access content directly
Theses Year : 2004

QoS SUPPORT IN EDGE ROUTERS

Support de la qualité de service dans les routeurs accès de l'Internet

(1)
1

Abstract

many flows are short Web transfers and about 1% of the largest flows carry more than 50% of all bytes. Motivated by the high variability property of Internet traffic, we first analyze the performance of LAS under the M/G/1 queue, where G is a job size distribution with varying degree of variability. The analysis for LAS shows that the conditional mean response time highly depends on the variability of a job size distribution and that the percentage of large jobs that see penalty under LAS is negligible when a job size distribution shows the high variability property. While shortest remaining processing time (SRPT) is known to be the optimal policy in reducing the mean response time, we show that LAS offers a conditional mean response time close to SRPT. When compared to first-come first-serve (FCFS), LAS significantly outperforms FCFS for job size distributions with the high variability property. Moreover, as opposed to FCFS, we prove that LAS can service some jobs even at overload. We then use simulations to investigate the performance of LAS in packet networks for various network configurations. We also study the interaction of LAS with TCP. We find that LAS has quite interesting features that cause it to reduce the transfer time for short TCP flows without penalizing large flows a lot. In addition, we show through simulations that LAS allocates bandwidth equally among competing TCP connections in congested heterogeneous networks. The simulation results show that LAS penalizes long-lived TCP and UDP flows at high network load above 75%. To address this issue, we propose a family of new LAS-based scheduling policies that differentiate the service in order to improve the performance of priority flows. To evaluate these policies, we develop analytic models to compute the mean flow transfer time for TCP flows that share a single bottleneck link that uses LAS or one of new LAS-based policies . Over a wide range of settings , we show that the analytic models agree with the ns2 simulation of the policies in packet networks when loss rates are low. Evaluation of the proposed policies shows that they notably improve the performance of priority flows in terms of reducing their mean transfer time, average jitter, and loss rate while affecting ordinary flows in a minor way. Finally, we evaluate a hybrid policy called LAS-FCFS that services small jobs using LAS and large jobs using FCFS. This policy can be useful when the penalty for the largest jobs under LAS is not acceptable. Analytical results show that LAS-FCFS improves the performance of the largest jobs when a job size distribution exhibits the high variability property. We also analyze an evaluate variants of LAS-FCFS that offer service differentiation.
Cette thèse porte sur l'étude de la discipline de service LAS ({\it least attained service}) et de variantes de cette discipline, dans le but d'offrir de la différentiation de service dans l'Internet. LAS donne la priorité au client qui a reçu le moins de service à un instant donné. Elle est connue, en théorie des files d'attente, depuis une trentaine d'années, mais n'a jamais été considérée dans les réseaux de paquets à cause de certains résultats (sur une file M/M/1 par exemple) montrant que LAS pénalise trop les plus "gros" clients.\\ Des études récentes ont montré que le trafic Internet, au niveau flot, se caractérise par une forte variabilité: de nombreux flots sont très courts alors que les flots les plus longs représentent plus de 50\% de la charge totale. Motivé par ce nouveau résultat, nous avons analysé LAS dans le cas d'une file M/G/1 avec une discipline de service G ayant une variabilité plus ou moins marquée. Cette analyse a montré que les temps moyens de réponse conditionels de LAS dépendent fortement de la variabilité de G et que la fraction de flots pénalisés dans le cas où G a une forte variabilité est très faible. Nous avons comparé LAS avec SRPT ({\it Shortest Remaining Processing Time}), car, parmis les disciplines de service fonctions de la taille des clients, SRPT est optimale en terme de nombre moyen de clients actifs. Nous avons montré que LAS offrait des performances très similaires à celles de SRPT lorsque G est très variable. Nous avons aussi comparé LAS à FCFS ({\it First Come First Serve}) qui est la discipline de service des routeurs de l'Internet. Nous avons montré que LAS surpassait FCFS lorsque G est très variable. De plus LAS offre une fonctinonement dégradé en cas de surcharge, alors que FCFS est totalement instable.\\ Nous avons ensuite mené une étude à base de simulations pour déterminer les performances de LAS dans diverses configurations de réseaux paquets. Notamment, nous avons étudié les effets de LAS sur TCP. Nous avons trouvé que LAS interagit très bien avec TCP car il réduit le temps de transfert des flots courts et ne pénalise pas notablement les flots longs. De plus, nous avons montré que LAS ne souffrait pas des problèmes d'inéquité dans le partage de la bande passante (entre flots TCP et UDP par exemple) rencontrés avec FCFS.\\ Nos résultats de simulation montrent aussi que LAS pénalise trop les flots extrêmement longs lorsque la charge est trop élevée. Pour corriger ce problème, nous avons proposé une famille de politiques de service basées sur LAS et capables d'offir un meilleur service aux flots dits prioritaires. Pour évaluer ces politiques, nous avons développé des modèles analytiques de LAS et de ces politiques au niveau flot. Nous les avons validés par des simulations ns2 pour une large gamme de paramètres et un taux de perte faible. L'évaluation des politiques proposées montre qu'elles améliorent notablement la performance des flots rioritaires, en terme de temps moyen de transfert, gigue et taux de perte, sans pour autant trop affecter les flots dits ordinaires. Finalement, nous avons évalué une politique de service LAS-FCFS qui sert les flots courts comme LAS et les flots longs comme FCFS. Cette politique peut être utile lorsque la pénalité infligée aux flots longs avec LAS est jugée inacceptable. Nous avons aussi proposé et évalué des variantes de LAS-FCFS capables d'offrir un service différentié.
Fichier principal
Vignette du fichier
rai_thesis.pdf (2.36 Mo) Télécharger le fichier
Loading...

Dates and versions

pastel-00000848 , version 1 (25-11-2004)

Identifiers

  • HAL Id : pastel-00000848 , version 1

Cite

Idris A. Rai. QoS SUPPORT IN EDGE ROUTERS. domain_other. Télécom ParisTech, 2004. English. ⟨NNT : ⟩. ⟨pastel-00000848⟩
579 View
264 Download

Share

Gmail Facebook Twitter LinkedIn More