Méthodes d’optimisation pour le dimensionnement de réseaux ayant des liens à capacités variables

This thesis summaries the work we have done in optimization of resilient communication networks. More specifically, the main goal is to propose appropriated recovery mechanisms for managing the demand traffic in a network under partial failures, i.e. when some part of the network (one or some links and/or nodes) is operational with reduced capacity. The main criterion in deciding the efficiency of the proposed recovery scheme is the dimensioning cost of the network while keeping the management cost at reasonable levels. Our main contribution is the design of two restoration strategies named Flow Thinning and Elastic Flow Rerouting. This document is organized in three main parts. In the first part, we present the problematic of the thesis. It includes an introduction on the protection and rerouting state-of-art strategies, together with their mathematical models and resolution methods. The second part presents in depth the first protection strategy named Flow Thinning. This strategy manages partial failures by decreasing appropriately the bandwidth on some flows routed through one of perturbed links. This implies overdimensionning of the network in the nominal state to ensure demand traffic in all failure states. The third and last part deals with the second rerouting strategy called Elastic Flow Rerouting. This strategy is a bit more complex than the first one because, in a failure state, we need to distinguish demands which are disturbed and the one which are not. If a demand is disturbed, it can increase the traffic on some of its paths. If it is not disturbed, it can release bandwidth on paths at the condition it remains non-disturbed. All this allows for further reducing the dimensioning cost but at a higher cost in terms of recovery process management. Note that the dimensioning problems for each strategy are shown to be NP-hard in their general form. The work of the thesis has been published in: three journal articles (Fouquet et al. (2015b), Pióro et al. (2015), Shinko et al. (2015)), two invited articles (Fouquet and Nace (2015), Fouquet et al. (2014c)) and height articles in international conferences (Fouquet et al. (2015a; 2014d;a;b;e), Pióro et al. (2013b;a), Shinko et al. (2013)). Note that Pióro et al. (2013b) has been rewarded by a "Best Paper Award" from the RNDM conference. To conclude, note that this thesis was realized in the Heudiasyc laboratory, from the Université de Technologie de Compiègne (UTC). It was financed by the French Ministry of Higher Education and Research1 with the support of the Labex MS2T2 of the UTC.Cette thèse porte sur l’optimisation des stratégies de reroutage dans les réseaux de télécommunications. Plus précisément, l’objectif est de proposer ou d’adapter des mécanismes permettant de router le trafic du réseau après une panne partielle, c’est-à-dire, après une baisse de la bande passante d’un ou plusieurs liens du réseau, tout en minimisant le coût de dimensionnement du réseau. Nos contributions principales sont la proposition de deux stratégies de protection/routage nommée Flow Thinning et Elastic Flow Rerouting. La thèse est organisée en trois parties. Dans la première partie, nous présentons la problématique de la thèse avant de passer en revue les stratégies de protection et reroutage de la littérature, leur modélisation et méthode de résolution. La deuxième partie présente en détails la première stratégie de protection appelée Flow-Thinning. Cette stratégie gère les pannes partielles en diminuant la bande passante de certain flots qui passent par le ou les arc(s) perturbés. Cela implique un surdimensionnement du routage nominal permettant d’assurer le trafic en cas de perturbations. La troisième et dernière partie concerne la deuxième stratégie de routage dénommée Elastic Flow Rerouting. Cette stratégie est un peu plus complexe que la première dans le sens où, en cas de panne, une distinction est faite entre les demandes perturbées ou non. Si une demande est perturbée, elle peu augmenter le trafic sur ces chemins. Si elle ne l’est pas, elle peut libérer de la bande passante sous la condition qu’elle ne devienne pas perturbée à son tour. Notons que ces deux stratégies sont assez difficiles du point de vue de leur complexité. Cette thèse a fait l’objet de divers travaux écrits : trois articles (acceptés ou en révision) dans des journaux (Fouquet et al. (2015b), Pióro et al. (2015), Shinko et al. (2015)), deux articles invités (Fouquet and Nace (2015), Fouquet et al. (2014c)) et huit articles dans des conférences internationales (Fouquet et al. (2015a; 2014d;a;b;e), Pióro et al. (2013b;a), Shinko et al. (2013)). Notons que Pióro et al. (2013b) a reçu le "Best Paper Award" de la conférence RNDM 2013. Pour finir, notons que cette thèse a été réalisée au laboratoire Heudiasyc de l’Université de Technologie de Compiègne (UTC). Elle a été financée par le Ministère de l’enseignement et de la recherche français3 avec le soutien du labex MS2T4 de l’UTC