Multi-Constrained Quality of Service Routing in Networks
Routage avec contraintes de Qualité de Service multiple dans les réseaux
Résumé
In recent years, the network traffic requiring Quality of Service (QoS) has been growing explosively. In this thesis, we study the multi-constrained QoS routing in networks. The objective is to find routes in wired and wireless networks taking into account constraints related to the QoS and minimizing the cost of the communication. We present several propositions. To solve the Multi-Constrained Path problem (MCP), an efficient exact algorithm 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 compute hierarchies, which are the exact solutions for MCMCM. An efficient preprocessing-based algorithm is also designed to accelerate the resolution time in large size networks. Regarding the problem of QoS routing in Low Power and Lossy Networks (LLNs), a new Objective Function (OF)-based solution is presented. This solution uses a non-linear length function. It is the first that takes into account any number of metrics and constraints for QoS routing. We designed an exact and two heuristic routing algorithms with QoS constraints for LLNs.
Au cours des dernières années, le trafic réseau nécessitant une qualité de service (QoS) a augmenté de façon exponentielle. Dans cette thèse, notre objectif est de trouver des routages dans les réseaux câblés et sans fil en prenant en compte les contraintes liées à la QoS et en minimisant le coût de la communication. Nous nous intéressons tout d’abord à la résolution du problème du chemin multi-contraint (MCP) pour lequel un algorithme exact efficace est proposé. Cet algorithme permet d'améliorer le temps d'exécution tout en maintenant la qualité de la solution. En ce qui concerne le problème de la diffusion multipoint (multicast) multi-contraint de coût minimal (MCMCM), une nouvelle formulation utilisant la Programmation Linéaire en Nombres Entiers est proposée. Elle permet de calculer les hiérarchies optimales, structures les plus pertinentes pour résoudre de manière exacte le problème MCMCM. Un algorithme de prétraitement efficace est également conçu pour accélérer le temps de résolution dans les réseaux de grande taille. En ce qui concerne le problème du routage avec QoS dans les « Low Power et Lossy Networks » (LLN), une solution basée sur une nouvelle fonction objective est présentée. Cette solution minimisant une longueur non linéaire est la première à prendre en compte un nombre quelconque de contraintes pour le routage avec QoS. Nous avons conçu un algorithme exact et deux algorithmes de routage heuristique pour résoudre ce problème dans les réseaux LLN avec QoS.
Origine : Version validée par le jury (STAR)