Retour au site du LAAS-CNRS

Abstract

Integrated services networks are expected to support services that provide a wide range of Quality of Service (QoS) guarantees. The following mechanisms are central to the design of networks with such capabilities : traffic shaping, traffic policing, packet scheduling, buffer management, admission control, and routing (not addressed by this work). This dissertation is on the modeling, design, and analysis of these mechanisms. Three main contributions are introduced. The first concerns the definition of a Stochastic Petri Nets (SPN) based framework for QoS analysis in packet switched networks. The framework presents: SPN models for the well-known algorithms that these mechanisms implement in practice; a compositional method to construct the SPN model of a complete network with an arbitrary architecture ; and an analysis method to derive the most common QoS parameters. The second contribution is the proposition of two implementations of the "assured forwarding" per hop behavior group of the DIFFSERV architecture. Both are based on the packet marking algorithm proposed in the IETF RFC 2698, on a static priority packet scheduling algorithm, and on a class-based-threshold buffer management algorithm (i.e. the packet discard decisions are taken by simply comparing classes' buffer occupancy to predefined thresholds). They aim at guaranteeing that each class's volume of traffic that is stored in the buffer is no lower than a given traffic envelope function. The two implementations differ in the way this traffic envelope is shared among packets with different markings. The last contribution concerns the admission of flows with deterministic QoS requirements in a network of rate-controlled service disciplines with EDF as the scheduling algorithm. This discipline is optimal in admitting flows and hence in utilizing network resources. However, its admission control algorithm is excessively complex. We first propose an improvement of the existing admission control algorithm that reduces its complexity. We also propose two complementary methods to choose the traffic envelope function of the rate-controller's traffic shapers that enhance flow admission and network utilization.

Résumé

Pour fournir des services à garanties de Qualité de Service (QdS), les réseaux doivent employer les mécanismes fondamentaux suivants : la mise en forme et la mise en vigueur du trafic, l'ordonnancement de paquets, la gestion de buffer, le contrôle d'admission, et le routage (non traité par ce travail). Ce mémoire de thèse traite de la modélisation, de l'analyse et de la conception de ces mécanismes. Dans ce travail de thèse, trois contributions sont présentées. La première concerne la définition d'un cadre basé sur les Réseaux de Petri Stochastiques (RdPS) pour l'analyse de la Qualité de Service dans les réseaux à commutation de paquets. Nous y présentons: les modèles RdPS des principaux algorithmes qu'implémentent les mécanismes cités ci-dessus ; une méthode de composition permettant de construire le modèle d'un réseau avec une architecture quelconque ; ainsi qu'une méthode d'analyse permettant de mesurer les principaux paramètres de QdS. La deuxième propose deux mises en ¿uvre de la famille "traitement assuré" (assured forwarding) de l'architecture DIFFSERV. Ces mises en ¿uvre se basent sur le marquage de paquets qui a été proposé par le RFC 2698 de l'IETF, sur un ordonnancement à priorités statiques, et sur un algorithme de gestion de buffer dit à seuils par classe, i.e. qui prend les décisions d'élimination de paquets par simple comparaison de l'occupation des classes à des seuils prédéfinis. Les mises en ¿uvre que nous proposons cherchent à garantir que le volume de trafic d'une classe qui est stocké dans le buffer n'est pas inférieur à une fonction enveloppe de trafic donnée. Les deux implémentations se distinguent par la manière avec laquelle cette enveloppe est partagée entre les paquets de différents marquages. La troisième concerne l'algorithme d'admission de flux avec garanties de QdS déterministes dans les réseaux à disciplines de service à débit contrôlé avec l'algorithme EDF comme algorithme d'ordonnancement de paquets. Cette discipline de service qui est optimale en termes d'admission de flux et d'utilisation de la bande passante souffre de son algorithme de contrôle d'admission qui est complexe. Premièrement, nous proposons une amélioration de l'algorithme de contrôle d'admission existant qui réduit sa complexité. Nous proposons également deux méthodes complémentaires de calcul des fonctions enveloppe de trafic des mécanismes de mise en forme de trafic du contrôleur de débit qui permettent d'augmenter l'admissibilité des flux et l'utilisation des ressources réseau.

Mots-Clés / Keywords

Qualité de service; Contrôle d¿admission; Ordonnancement de paquets; Gestion du buffer; Réseaux de Petri stochastiques; Quality of service; Admission control; Packet scheduling; Buffer management; Stochastic Petri nets;