Étude des méthodes et algorithmes pour gérer le problème de la fragmentation dans un réseau optique

Les réseaux optiques sont en évolution permanente, proposant des structures de plus en plus flexibles. Le spectre est divisé en plusieurs tranches ou slots de fréquences et cette grille de slots de fréquences est passée d'une largeur de centaines de GHz à 6.25 GHz avec la dernière génération d'Elastic Optical Network (EON). Ceci permet d'améliorer les performances des réseaux, mais pose également de nouveaux problèmes. Le problème sur lequel nous allons principalement nous pencher est d'assigner les connexions dans un réseau. La structure des réseaux optiques impose des contraintes de continuité et contigüité par rapport au spectre. Les demandes ne sont plus assignables sur n'importe quel slot libre dans le réseau. Les arrivées et départs de ces demandes entraînent l'apparition de slots difficilement accessibles sans violer une des deux contraintes. Dans ce cas, on parle de fragmentation du réseau. L'état de fragmentation du réseau est intimement lié au blocage observé. Pour un même trafic, plus la fragmentation du réseau est considérée comme haute, plus le blocage doit être haut. Des métriques ont été construites pour quantifier la fragmentation du réseau et des algorithmes pour assigner les demandes ont été conçus pour minimiser cette fragmentation. Afin de déterminer la qualité d'une métrique ou d'un algorithme, on a mis en place au sein de l'équipe de recherche un outil informatique pour simuler un tel réseau optique. Pour améliorer le problème de la fragmentation dans un réseau optique, le but de ce mémoire est de proposer une description de l'ensemble des algorithmes et métriques présents dans la littérature. On discute aussi de certains aspects autour de ces métriques et algorithmes. Enfin, on propose un nouvel algorithme pour répondre au problème de l'assignation. L'algorithme proposé se base sur l'idée de partition du spectre. Brièvement, on assigne à chaque taille de demandes possibles (granularité) une région du spectre. Pour évaluer notre algorithme, on a mis en place une méthodologie et un ensemble de tests. On évalue graduellement les performances de notre algorithme en partant d'un simple lien pour arriver jusqu'à un petit réseau. Au cours de cette méthode, on a mis en place des tests pour optimiser certains paramètres de cet algorithme afin d'avoir de bonnes performances tant sur le plan du blocage que des métriques de fragmentation. On compare les résultats de notre algorithme avec des algorithmes sans partition présents dans la littérature.

Abstract

Optical networks are constantly evolving, offering more and more flexibility in their structure. Indeed, the frequency slot grid has decreased from hundreds of GHz to 6.25 GHz with the latest generation of EON. This improves the performances of these ones but it brings new problems. One of these is the problem of assigning the connections in a network. The structure of optical networks imposes two main constraints : continuity and contiguity. Demands can no longer be assigned to any free slot in the network. The arrivals and departures of these demands cause the appearance of slots that are difficult to access without breaking one of the two constraints. This is called network fragmentation. The state of fragmentation of the network is closely related to the observed blocking. For a given traffic, the higher the network fragmentation is, the higher the blocking should be. Metrics have been developed to quantify network fragmentation and algorithms for assigning demands have been designed to minimize this fragmentation. In order to determine the quality of a metric or an algorithm, a simulator has been set up by the research team in order to simulate such an optical network. In order to tackle the problem of fragmentation in an optical network, the purpose of this master thesis is to describe the different algorithms and metrics that exist in the literature. We discuss some issues related to these metrics and algorithms. Finally, we propose a new algorithm to deal with the assignment problem. The proposed algorithm is based on the concept of spectrum partition. Briefly, we assign to each possible demand size (granularity) a region of the spectrum. To test our algorithm, we set up a methodology and a set of tests. We gradually evaluate the performance of our algorithm starting from a single link to a small network. During this methodology, we set up tests to optimize some parameters of this algorithm in order to have good performances both in terms of blocking and fragmentation metrics. We compare the results of our algorithm with non-partitioned algorithms present in the literature. We observe that a partitioned algorithm has better blocking rate and fragmentation metrics performances than a non-partitioned algorithm for the link and path cases. We propose 2 methods to compute restrictions for the granularities at a network level. We observe that better results can be obtained for this case as well. However, we also show that this method has some limitations when we have more heterogeneous traffic.