Multi-Constrained Quality of Service Routing in Networks
Routage avec plusieurs contraintes de QoS dans les réseaux
Résumé
In recent years, the network traffic has been growing explosively. The main reason behind this growth comes from numerous multimedia applications (e.g. Video on Demand, video-conferencing). These applications require several constraints of Quality of Service (QoS) to operate properly. Therefore, delivering this enormous amount of packets to their intended destinations (i.e. routing) with respect of the QoS constraints brought serious challenges for the next generation of networks. In this thesis, we study the multi-constrained QoS routing in network. The objective is to find the route, for instances of wired and wireless networks, to distribute the message to the destination(s) while taking into account both the constraints of QoS and minimizing the total cost. The first chapter presents a brief introduction to the routing with multiple constraints of QoS in networks, involving the evolution of networks and some basic concepts of network architecture.
Then, the role of routing and the need of QoS are presented with the motivation of this work. This chapter presents also the formulation of the problems under consideration. In order to analyse the Multi-Constrained Path problem (MCP), an efficient algorithms based on an earlier MCP algorithm named SAMCRA is proposed. This algorithm is shown to be able to improve the execution time while maintaining the quality of the solution. Concerning the Multi-Constrained Multicast Minimum Cost problem (MCMCM), a new Integer Linear Programming (ILP) formulation is proposed to model the hierarchy as an exact solution for MCMCM. It is proven that the optimal structure of MCMCM is neither a tree nor a sub-graph but a hierarchy. An efficient preprocessing-based algorithm (ArcReduce) is also proposed to accelerate the resolution time of the ILP in large size networks. Regarding the problem of routing with QoS in Low Power and Lossy Networks (LLNs), a new Objective Function (OF) based on Non-Linear Length (NL-OF) is proposed. The standard IPv6 routing protocol for LLNs called (RPL) builds acyclic graphs and applies an OF which is responsible of choosing the best links during the construction of the route map. The NL-OF is the first OF that takes into account any number of metrics and constraints for QoS routing. An exact and some heuristic routing algorithms with QoS constraints for LLNs are also proposed.
Au cours des dernières années, avec la croissance spectaculaire de nombre d’objets connectés sur Internet, les réseaux deviennent de plus en plus complexes et difficiles à gérer. Nous avons maintenant différents types de données échangées entre ces objets, dans des liens d’interconnexions (réseau), comme les données multimédia (voix, images, vidéos,. . . , etc) par exemple.
Les applications multimédia exigent des conditions rigoureuses de Qualité-de-Service (QoS) telles qu’un délai de bout en bout minimal, une gigue bornée, et une utilisation efficace de la bande passante. Les protocoles de routage traditionnels on été conçus pour un trafic de données «Best-effort ». Ils construisent des routes principalement basées sur la connectivité et l’optimisation du coût de transmission des données. De telles routes ne peuvent pas satisfaire la QoS à cause du manque de ressources. Récemment, plusieurs algorithmes de routage sensible à la QoS ont été proposés pour trouver des routes réalisables. Cette thèse donne un bref état de l’art pour les problèmes de routages avec QoS dans les réseaux.
En fait, il y a deux aspects impliqués par le routage : les protocoles de routage et les algorithmes de routage. Nous nous intéressons dans cette thèse aux algorithmes de routage qui permettent de respecter une QoS demandée. Il existe dans la littérature des algorithmes exacts, approchés ou heuristiques pour les problèmes unicast / multicast. Dans un premier temps, nous allons faire un aperçu sur les travaux concernant le problème de routage unicast et notre proposition. Ensuite, nous allons expliquer le problème de routage multicast avec QoS et notre contribution en ce qui le concerne. Enfin, nous présentons notre travail lié au problème de routage avec QoS en utilisant le protocole de routage RPL (Routing Protocol for Low Power and Lossy Networks), qui est un protocole standardisé, de plus en plus utilisé.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...