La migration d'un réseau optique en anneaux interconnectés vers un réseau arbitrairement maillé et d'un trafic statique vers un trafic dynamique nécessite l'introduction de plusieurs niveaux de granularité pour s'adapter à cette diversité spatiale et temporelle et réduire ainsi la complexité et la taille des brasseurs optiques. Cette taille peut être réduite en traitant en bloc un groupe de longueurs d'onde contiguës. Cette bande d'ondes sera éventuellement traitée comme une seule entité. Par contre, ce traitement en bloc complique l'opération de routage et d'allocation de longueurs d'onde. Quelques ports d'entrée/sortie du brasseur de bandes peuvent éventuellement être connectés à des démultiplexeurs/multiplexeurs pour passer à un brassage par longueurs d'onde. De cette manière, on résout la commutation en bloc et quelques bandes pourront sortir de la continuité des tunnels établis pour passer d'un tunnel à l'autre. Cette notion peut être étendue pour couvrir différentes granularités et différents niveaux de brassage à l'aide de brasseurs optiques hiérarchiques. La coexistence des différents concepts de groupage optique et électronique ainsi que la manipulation de plusieurs niveaux et différentes échelles d'agrégation forment l'idée de base derrière ce qu'on appelle "réseau optique à plusieurs niveaux de granularité". Dans cette thèse, On propose un nouveau modèle graphique adapté au réseau optique à plusieurs niveaux de granularité. Le modèle d'un composant optique est formé par l'interconnexion d'un nombre d'éléments de base (BNE). Chaque BNE est une représentation graphique des supports du trafic. On introduit la notion de "groupes" qui permet l'abstraction des agrégateurs/désagrégateurs et définit par suite la granularité de commutation de chaque côté du BNE. Étant modulable, ce modèle pourra servir au développement d'un outil d'aide à la conception de ce type de réseaux. On propose un nouveau modèle combinatoire du brasseur hiérarchique permettant de comparer différentes réalisations matérielles. Ceci nous a permis d'étudier la réduction de la complexité du matériel et l'augmentation de la complexité opérationnelle quand on remplace un brasseur optique simple par un brasseur optique hiérarchique. On propose le nouveau concept de modifier les canaux de longueurs d'onde sans modifier l'allocation logique des longueurs d'onde et par suite, permettre un réarrangement avec un minimum d'interruptions afin d'optimiser le brassage à plusieurs granularités. Ce réarrangement est réalisé sans changer la distribution du trafic résultant du routage et de l'attribution des longueurs d'onde. On montre l'importance de la gestion des granularités et on propose une nouvelle méthode de contrôler l'allocation des multiplexeurs/démultiplexeurs dans le contexte du trafic dynamique. Dans ce contexte et en utilisant le modèle graphique, on propose de construire une topologie logique multicouche dans le but d'avoir une base d'informations adaptée à la proposition d'ingénierie de trafic. Dans cette solution, on estime la diversité potentielle d'acheminement des tunnels établis par le brassages hiérarchique en considérant une distribution de charge donnant le flot maximal. cette distribution est considérée comme objectif à atteindre et est mise à jour après tout changement. On donne aux tunnels ayant la plus grande diversité potentielle d'acheminement la priorité de passer aux fines granularités. L'ensemble des propositions est renforcé par des analyses et simulations et plusieurs domaines à aborder en perspective sont présentés en conclusion.

Dans cette thèse, nous nous sommes intéressés à l'optimisation du partage de charge dans un réseau supportant le routage à la source. Une modélisation générique en files d'attente alimentées par un trafic caractérisé par sa bande passante effective et l'utilisation de la théorie des Grandes Déviations nous a permis de déduire de règles d'ingénierie dans divers contextes en optimisant des fonctions de coût qui reflètent les besoins des réseaux opérationnels. Des propriétés structurelles sur les politiques optimales ont été démontrées pour des importants dans le domaine de l'ingénierie du trafic. La variabilité de la capacité des chemins d'un réseau a été intégrée à l'aide du concept de capacité effective. Nous avons mis en évidence qu'un dimensionnement basé sur une capacité moyenne peut s'avérer sous optimal et nous avons quantifié cela. Ainsi, une approche d'ingénierie de trafic adaptative a été proposée en faisant évoluer le partage en fonction des mesures réalisées sur le réseau.

La problématique de la fourniture de qualité de service (QoS) dans les réseaux Internet connaît un regain d'intérêt engendré par deux phénomènes : (1) la croissance des services à valeur ajoutée qui demandent de la QoS (e.g., IPTV) et (2) la convergence des réseaux vers une architecture unifiée, basée sur IP, pour les services de voix, d'image, et de données. Dans ce contexte, des limitations des technologies actuelles de QoS apparaissent : il est actuellement difficile pour un opérateur de garantir les niveaux de service que son réseau peut offrir. Par ailleurs, il est très difficile de garantir un traitement cohérent de bout en bout pour les flux sensibles à la QoS et qui traversent les réseaux de plusieurs opérateurs. En effet, le contrôle de ces flux d'information est partagé entre tous les opérateurs traversés. Dans la thèse, nous avons étudiés ces différents problèmes. Nous nous sommes plus spécifiquement penchés sur les problèmes de routage et d'ingénierie dynamique de trafic au niveau inter-domaine. Nous avons proposés plusieurs solutions algorithmiques pour permettre de calculer des chemins soumis à plusieurs contraintes de performance. Des études analytiques et par simulations montrent que nos algorithmes sont efficaces et extensibles. Enfin, nous les avons intégrés dans une architecture récemment standardisée à l'IETF et avons étudié les adaptations protocolaires requises pour leur déploiement. Nos contributions représentent un pas important vers une gestion plus efficace du trafic inter-domaine dans les réseaux à ingénierie de trafic.

Les réseaux sans fil constituent de plus en plus une technologie émergente permettant à ses utilisateurs<br />un accès à l'information et aux services électroniques indépendamment de leurs positions<br />géographiques. Le succès de ce type de réseaux est suscité par un grand intérêt de la part des particuliers,<br />des entreprises et du milieu industriel. Les débits atteints actuellement avec les réseaux<br />sans fil rendent possible le transfert de flux multimédia soumis à de fortes contraintes. Ainsi, le<br />respect de certaines contraintes telles que la bande passante, le délai ou encore le taux de pertes<br />de paquets devient primordial. Cependant, les solutions qui ont été introduites dans le monde des<br />réseaux filaires deviennent inadaptées pour des réseaux utilisant un médium radio partagé sans aucune<br />administration centralisée.<br />Dans ce cadre, plusieurs travaux concernant l'étude de la qualité de service (QoS) dans les réseaux<br />sans fil et notamment les réseaux ad hoc ont été réalisés afin de définir des modèle de QoS, des protocoles<br />d'accès au médium, des protocoles de routage avec QoS et des protocoles de signalisation. Pour<br />cela, notre premier objectif a été l'étude des différents mécanismes de QoS. Ce travail se place donc,<br />dans le cadre de la QoS et la proposition de mécanismes permettant d'offrir des solutions optimales<br />à des applications sensibles à certains facteurs de QoS. L'autre contribution de ce travail se situe<br />dans l'intégration du concept de l'ingénierie du trafic dans les réseaux ad hoc. En effet, ce concept<br />nous a permis de proposer des mécanismes offrant des services différenciés afin d'assurer la QoS dans<br />ces réseaux. De même, nous avons proposé de nouveaux mécanismes d'ordonnancement dans le but<br />de gérer les différents types de flux passant par la couche MAC du standard IEEE 802.11. Enfin, la<br />dernière contribution a été la proposition de solutions d'équilibrage de charge, d'ingénierie de trafic<br />et la validation des différents résultats par le biais de simulations et de preuves mathématiques.

Résumé non disponible en français

L'objectif de ce travail de thèse dans un premier temps est l'évaluation de performances des modèles de routage multi-chemins pour l'ingénierie de trafic et l'équilibrage de charge sur un réseau de type IP/MPLS (MPLS-TE). Nous comparons la capacité de ces modèles à équilibrer la charge du réseau tout en faisant de la différentiation de trafic. Nous les appliquons sur des grandes topologies générées par le générateur automatique des topologies BRITE, qui s'approchent en forme et en complexité du réseau réel. Nous mesurons ainsi l'impact de leur complexité respective et donc la capacité à les déployer sur des réseaux de grande taille (scalabilité). Dans un second temps, l'objectif est de proposer un concept de modélisation générale d'un réseau à commutations par paquets. Ce modèle est établi sur la base de la théorie différentielle de trafic et la théorie des files d'attente, tout en utilisant des approches graphiques. Le but est d'estimer l'état de charge du réseau et de ses composants (routeurs, liens, chemins). Ensuite, en fonction de ça, nous développons des approches de contrôle de congestion et commande sur l'entrée améliorant les techniques de routage adaptatif et l'équilibrage de charge dans les réseaux IP/MPLS

La superposition de topologies virtuelles à la topologie physique d'un réseau est un des principaux mécanismes de l'ingénierie de trafic. Soit un réseau physique d'une certaine topologie et capacité fixées et une matrice de trafic à véhiculer, il s'agit trouver une topologie logique permettant de mapper de manière optimale la matrice de trafic sur le réseau physique. Lors de l'évolution de la matrice de trafic sur des échelles de temps longues, il faudra agir sur le layout. La première contribution concerne la définition de fonctions de coût mieux adaptées à la réalité d'un opérateur, la deuxième contribution concerne la prise en compte du coût de changement du layout. Il s'avère intéressant d'un point de vue opérateur de réduire la complexité du layout, mesurée comme une fonction du nombre de chemins virtuels. Nous avons donc formulé divers problèmes de minimisation de la complexité du layout sous des contraintes de QoS. Il s'agit d'une modélisation réaliste mais qui engendre des modèles difficiles à résoudre. Nous avons développés des heuristiques qui permet de trouver des solutions approchées pour des réseaux de grande taille. Nous avons montré que la complexité des layouts peut être significativement réduite en comparaison avec celle obtenue suite à l'optimisation des fonctions de coût classiques. Le changement du layout implique d'une part un coût d'opération et d'autre part peut engendrer des coupures de service qui affecteront directement le coût d'opération. Nous avons formulé une famille de problèmes prenant en compte le coût de reconfiguration du layout. L'une des heuristiques citées a été adaptée pour analyser ces nouveaux problèmes.

La majorité des grands opérateurs utilise la technologie MPLS pour gérer leur réseau via des protocoles de signalisation et de distributions de labels. Or, ces protocoles sont complexes à déployer, à maintenir et la résolution des pannes est souvent très difficile. L'IETF a initié la standardisation d'une architecture de routage par segments (Segment Routing) s'appuyant sur un plan de contrôle simple, léger, facile à gérer et instanciée sur MPLS ou IPv6. Cette architecture repose sur le concept de routage à la source, dans lequel l'en-tête des paquets transporte les indications du chemin à suivre pour atteindre sa destination. Adapté aux cas d'usages simples et offrant nativement une résistance aux pannes, les cas d'usages plus complexes exigent de résoudre des verrous technologiques pour lesquels nous proposons plusieurs solutions. Dans cette thèse effectuée au sein d'Orange Labs, nous nous sommes intéressés à l'instanciation de l'architecture Segment Routing sur le plan de transfert MPLS et plus particulièrement à l'ingénierie de trafic, notamment avec réservation de ressources. Nous avons proposé des solutions aux problèmes liés à la limitation matérielle des routeurs actuels ne permettant pas l'expression de tous les chemins contraints. Ce travail est divisé en deux parties : (i) la proposition d'algorithmes de calcul et d'encodage de chemins de routage par segment afin de contourner les limitations matérielles. (ii) la définition des exigences architecturales et la construction d'une preuve de concept fonctionnelle. Enfin, cette thèse propose de nouvelles pistes d'études afin de consolider les outils d'ingénierie de trafic pour le routage par segment. / Most major operators use MPLS technology to manage their network via signalling and label distribution protocols. However, these protocols are complex to deploy, maintain and troubleshooting is often very difficult. The IETF has initiated the standardization of a segment routing architecture based on a simple control plane, lightweight, easyto-manage and instantiated on MPLS or IPv6. This architecture is based on the concept of source routing, in which the packet header carries the indications of the path to follow to reach its destination. Suitable for simple use cases and natively resistant to failure, more complex use cases require the resolution of technological issues for which we offer several solutions.In this thesis carried out within Orange Labs, we were interested in the instantiation of the Segment Routing architecture on the MPLS transfer plan and more particularly in traffic engineering, particularly with resource reservation. We have proposed solutions to the problems related to the hardware limitation of current routers that do not allow the expression of all constrained paths. This work is divided into two parts : (i) the proposal of algorithms for computing and encoding segment routing paths in order to bypass hardware limitations. (ii) the definition of architectural requirements and the construction of a functional proof of concept. Finally, this thesis proposes new research issues to consolidate traffic engineering tools for segment routing.

Cette thèse porte essentiellement sur les problématiques fondamentales d'optimisation combinatoire qui se dégagent de la modélisation structurelle et algorithmique du dimensionnement des réseaux de transport WDM tout-optiques. L'optimisation de ces réseaux est nécessaire aux opérateurs de télécommunication, qui demandent la garantie d'une exploitation efficace des ressources déployées. La thèse est organisée en trois parties. La première partie traite du problème de routage et affectation de longueur d'onde. Nous proposons de résoudre le problème considérant des demandes de trafic permanentes. Des méthodes à la fois exactes basées sur la programmation linéaire et approchées ont été développées. Nous étendons ensuite le modèle de trafic pour considérer simultanément des demandes de trafic pré-planifiées et des demandes de trafic aléatoires. Différent algorithmes de routage ont été développés. Les différents algorithmes ont été comparés en terme de taux de rejet global. La deuxième partie concerne le problème de routage et affectation de longueurs d'onde avec protection. Les ressources dédiées à la protection sont rarement sollicitées, nous cherchons à en minimiser le nombre grâce au multiplexage des circuits optiques de protection. Des méthodes exactes et approchées sont encore une fois proposées considérant les demandes de trafic citées ci-dessus. La dernière partie présente un algorithme de reroutage de canaux optiques afin d'améliorer le taux de rejet dans les réseaux tout-optiques sans convertisseurs en longueurs d'onde. Plusieurs variantes de l'algorithme ont été proposées. Les résultats obtenus montrent un gain intéressant en terme de taux de rejet.

Ce travail a pour but d'améliorer l'efficacité énergétique des réseaux de cœur en éteignant un sous-ensemble de liens par une approche SDN (Software Defined Network). Nous nous différencions des nombreux travaux de ce domaine par une réactivité accrue aux variations des conditions réseaux. Cela a été rendu possible grâce à une complexité calculatoire réduite et une attention particulière au surcoût induit par les échanges de données. Pour valider les solutions proposées, nous les avons testées sur une plateforme spécialement construite à cet effet.Dans la première partie de cette thèse, nous présentons l'architecture logicielle ``SegmenT Routing based Energy Efficient Traffic Engineering'' (STREETE). Le cœur de la solution repose sur un re-routage dynamique du trafic en fonction de la charge du réseau dans le but d'éteindre certains liens peu utilisés. Cette solution utilise des algorithmes de graphes dynamiques pour réduire la complexité calculatoire et atteindre des temps de calcul de l'ordre des millisecondes sur un réseau de 50 nœuds. Nos solutions ont aussi été validées sur une plateforme de test comprenant le contrôleur SDN ONOS et des commutateurs OpenFlow. Nous comparons nos algorithmes aux solutions optimales obtenues grâce à des techniques de programmation linéaires en nombres entiers et montrons que le nombre de liens allumés peut être efficacement réduit pour diminuer la consommation électrique tout en évitant de surcharger le réseau.Dans la deuxième partie de cette thèse, nous cherchons à améliorer la performance de STREETE dans le cas d’une forte charge, qui ne peut pas être écoulée par le réseau si des algorithmes de routages à plus courts chemins sont utilisés. Nous analysons des méthodes d'équilibrage de charge pour obtenir un placement presque optimal des flux dans le réseau.Dans la dernière partie, nous évaluons la combinaison des deux techniques proposées précédemment : STREETE avec équilibrage de charge. Ensuite, nous utilisons notre plateforme de test pour analyser l'impact de re-routages fréquents sur les flux TCP. Cela nous permet de donner des indications sur des améliorations à prendre en compte afin d'éviter des instabilités causées par des basculements incontrôlés des flux réseau entre des chemins alternatifs. Nous croyons à l'importance de fournir des résultats reproductibles à la communauté scientifique. Ainsi, une grande partie des résultats présentés dans cette thèse peuvent être facilement reproduits à l'aide des instructions et logiciels fournis. / This work seeks to improve the energy efficiency of backbone networks by automatically managing the paths of network flows to reduce the over-provisioning. Compared to numerous works in this field, we stand out by focusing on low computational complexity and smooth deployment of the proposed solution in the context of Software Defined Networks (SDN). To ensure that we meet these requirements, we validate the proposed solutions on a network testbed built for this purpose. Moreover, we believe that it is indispensable for the research community in computer science to improve the reproducibility of experiments. Thus, one can reproduce most of the results presented in this thesis by following a couple of simple steps. In the first part of this thesis, we present a framework for putting links and line cards into sleep mode during off-peak periods and rapidly bringing them back on when more network capacity is needed. The solution, which we term ``SegmenT Routing based Energy Efficient Traffic Engineering'' (STREETE), was implemented using state-of-art dynamic graph algorithms. STREETE achieves execution times of tens of milliseconds on a 50-node network. The approach was also validated on a testbed using the ONOS SDN controller along with OpenFlow switches. We compared our algorithm against optimal solutions obtained via a Mixed Integer Linear Programming (MILP) model to demonstrate that it can effectively prevent network congestion, avoid turning-on unneeded links, and provide excellent energy-efficiency. The second part of this thesis studies solutions for maximizing the utilization of existing components to extend the STREETE framework to workloads that are not very well handled by its original form. This includes the high network loads that cannot be routed through the network without a fine-grained management of the flows. In this part, we diverge from the shortest path routing, which is traditionally used in computer networks, and perform a particular load balancing of the network flows. In the last part of this thesis, we combine STREETE with the proposed load balancing technique and evaluate the performance of this combination both regarding turned-off links and in its ability to keep the network out of congestion. After that, we use our network testbed to evaluate the impact of our solutions on the TCP flows and provide an intuition about the additional constraints that must be considered to avoid instabilities due to traffic oscillations between multiple paths.