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

The goal of this thesis is to investigate scheduling mechanisms that allow to offer service differentiation in the Internet. For this purpose, we study least attained service (LAS) scheduling policy in packet switched networks to support quality of service (QoS). LAS has been known for decades as job scheduling policy but has never been considered for packet switched networks. When analyzed under M/M/1 queue LAS penalizes the largest jobs a lot. However, recent Internet traffic measurements have revealed that the Internet traffic exhibits a high variability property; many flows are short Web transfers and less than 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 is stable 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 connections in congested heterogeneous networks. The simulation results show that LAS penalizes long-lived TCP and UDP flows at high network load. 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 for the new LAS-based and LAS policies to compute the mean flow transfer time. Over a wide range of settings and when the loss rate is low, we show that the analytic models perfectly agree with the ns2 simulation of the policies in packet networks. 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 has impact to the performance of the largest jobs when a job size distribution exhibits a high variability property. We also analyze and evaluate variants of LAS-FCFS that offer service differentiation.