Dritan Nace, for this precious guidance, encouragement and availability during this work to bring it to its completion. His enthusiasm, his continuous support, experience and friendship, have a great influence in my first sets in researches and it will be greatly helpful in my future carrier. I am deeply thankful to my supervisor because he believes in

Résumé

C ette thèse porte sur l'optimisation des stratégies de reroutage dans les réseaux de télécommunications. Plus précisement, l'objectif est de proposer ou d'adapter des méchanismes 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 traffic 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 traffic 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), [START_REF] Pióro | Optimizing flow thinning protection in multicommodity networks with variable link capacity (submitted)[END_REF], [START_REF] Shinko | Elastic routing for survivable networks[END_REF]), deux articles invités (Fouquet and Nace (2015), [START_REF] Fouquet | Flow adjustment methods for survivable networks[END_REF]) et huit articles dans des conférences internationales (Fouquet et al. (2015a;[START_REF] Fouquet | Elastic rerouting -models and resolution methods[END_REF]a;b;e), [START_REF] Pióro | An optimization model for multicommodity flow networks with partial multiple link failures[END_REF]a), [START_REF] Shinko | A study on a distributed rerouting scheme[END_REF]). Notons que [START_REF] Pióro | An optimization model for multicommodity flow networks with partial multiple link failures[END_REF] a reçu le "Best Paper Award" de la conférence RNDM 2013.

Pour finir, notons que cette thèse a été réalisé 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çais 3

Conclusion A Appendices

Context and Motivation

The thesis addresses resilience of communication networks in both wired and wireless context. These networks are subject to total failures when link capacities are totally lost, and partial failures when the capacities are only partially reduced. In the following, we introduce the failure management aspect in both networks, starting with wireless networks.

Wireless communications

Fixed broadband wireless communications sector holds great promise for providing private high-speed data connections by means of microwave radio [START_REF] Anderson | Fixed broadband wireless system design[END_REF][START_REF] Lehpamer | Microwave transmission networks: Planning, design, and deployment[END_REF] or free space optical (FSO) transmission [START_REF] Willebrand | Free space optics: Enabling optical connectivity in today's networks[END_REF]Ghuman 2002, Son and[START_REF] Son | Design and optimization of a tiered wireless access network[END_REF]. Both microwave and optical transmission refer to terrestrial point-to-point digital communications, usually employing highly directional antennas within the line-of-sight (LOS). What is important, the two technologies operate at unlicensed frequency bands, contrary to radio communications based on the Wi-Fi IEEE 802.11-family standards. Moreover, both microwave and FSO are sensitive to interference-the feature we utilize in our optimization model. Despite recent advances in optimization of fixed broadband wireless networks, a variety of questions remain unaddressed in this area.

Particularly, capacity planning in fixed wireless networks is quite different from that in wired networks. In fact, environment conditions, especially weather, play an important role since they can introduce instantaneous variations into the communication channel, likely leading to outage events which can be modeled as multiple partial link failures. As a common practice, operators tend to highly over-provision bandwidth during network planning to avoid traffic bottlenecks under adverse scenarios (when the performance of some links deteriorates). This approach, however, incurs additional costs that do not result in resource-and cost-efficient networks, leading to an inefficient use of the radio spectrum.

Even though FSO and microwave radio have a lot in common, this introduction will focus on microwave radio communications. Radio frequency spectrum is a limited resource regulated worldwide by the International Telecommunications Union (ITU). In conjunction with the ITU regulations, national legislation instruments establish the availability of frequency bands for specific applications and the procedures to use licenses. A license (assignment) is an authorization given by administration for a radio station to use a radio frequency under specified conditions. In most cases, the price of frequency spectrum for a single microwave link is a function of the amount of spectrum (bandwidth) in MHz with which the license is associated.

Commonly, to support broadband applications, modern microwave systems use quadrature amplitude modulation (QAM). Note that QAM An m-QAM scheme presents m combinations of amplitude and phase, each one representing an n-bit pattern called a symbol (with n = log 2 m and integer). Given the channel bandwidth B and the m-QAM scheme in use, we can approximate the channel capacity C by:

C [ Mb/s] = nB [ MHz].
(1.1)

The m-QAM schemes with high values of m assure bandwidth efficiency, but are more susceptible to errors due to channel impairments. As the modulation scheme changes to accommodate higher data rates, the signalto-noise ratio (SNR) requirement increases to preserve the bit error rate (BER). Moreover, the transmitted signal suffers deep fades and hence microwave links are susceptible to outage events. To overcome this issue, modern microwave systems employ adaptive modulation and coding which has been proven to considerably enhance link performance [START_REF] Goldsmith | Variable-rate variable-power mqam for fading channels[END_REF]. To keep the BER performance, this technique entails the variability of the link capacity.

In the thesis, we will exploit the capability of the above considered networks to adapt the capacity of links to meet the current SNR requirement. We assume that a list of states, typically corresponding to degraded weather condition in a particular area, is given. Each state is represented by a vector of link capacities where a set of links (corresponding to the degraded area) have their capacity decreased due to the modulation scheme applied to cope with the weather condition in the area, while the others remain unchanged. Note that adverse weather conditions most affect low- Note that the above considerations hold also for FSO networks. Factors such as beam dispersion, atmospheric absorption, rain, fog, snow, and scintillation, among other factors, can lead to capacity limitations [START_REF] Xiaoming | Free-space optical communication through atmospheric turbulence channels[END_REF]Kahn 2002, Puryear 2011). Furthermore, QAM modulation can be applied [START_REF] Harjeevan | Performance analysis of terrestrial free space optical (fso) communication link using m-qam modulation technique[END_REF].

Wired networks

Broadband cable communications are in place for decades. Nowadays, these transmissions are done through cable modem or optical fibers [START_REF] Berthold | Optical networking: Past, present, and future[END_REF]. Failures in high-speed networks have always been a concern of high importance. The specificity of these networks is the fact that a link failure corresponds to the total failure of a link (i.e. no capacity remains on the link). These failures, typically link cuts or router damages, can lead to heavy losses of traffic. The management of failures in wired networks has led to a large set of mechanisms, ensuring traffic requirements after a failure if possible. A brief listing of existing mechanisms is presented in Chapter 2. Note that contrary to wireless networks, capacities in wired networks are fixed in advance. Indeed, installing new fiber, with the right-of-way and installation costs, is very expensive and there is no way to increase capacities by increasing transmission power. Survivability can be addressed in many layers in a network. Even though partial failures seem impossible in the physical layer of wired networks, partial link failures can appear in the upper layer of these wired networks. Figure 1.2 illustrates this phenomenon. First note that a network can be represented by a graph where routers are seen as nodes, and links as edges. In this network, link ( A, B) in the logical layer is physically routed through paths A B and A C B. Similarly, link ( A, D) in the upper layer is routed through path A B D in the physical layer. Hence, when the physical link ( A, B) is cut, link ( A, D) in the upper layer totally fails but link ( A, B) suffers a degradation of only 50% of its capacity as physical path A C B is not affected by the failure.

Our contribution

In this thesis, we investigate network optimization problems related to the design and configuration of networks which can suffer partial link failures. The study is pursued also for total failures. We are concerned with a general class of problems expressed in terms of minimum cost multicommodity flow (MCMCF) problems, which are largely used for optimal design and dimensioning of telecommunication networks [START_REF] Kennington | A survey of linear cost multicommodity network flows[END_REF][START_REF] Minoux | Multicommodity network flow models and algorithms in telecommunications[END_REF]). These problems basically consist of transporting different commodities, from their respective sources to their destinations, which simultaneously use the network and are coupled through either by links' capacities or the cost function to be minimized. Obviously, there should be enough capacity in the network to simultaneously carry all traffic requirements. Various special cases of the MCMCF problem are reported in [START_REF] Minoux | Multicommodity network flow models and algorithms in telecommunications[END_REF][START_REF] Fortz | Dantzig-wolfe reformulation for the network pricing problem with connected toll arcs[END_REF][START_REF] Botton | Benders decomposition for the hop-constrainted survivable network design problem[END_REF], each of them associated with an appropriate choice of link cost function. Generally, the optimization criterion refers to the total cost of the equipment to be installed on various links of the network. When the cost function is considered linear, then the MCMCF problem can be formulated as a large scale continuous linear program (LP), and many efficient algorithms are available to tackle it. These mathematical models are the basis of the mathematical formulation in our work.

In telecommunication networks, the idea of failure is largely limited to scenarios in which every link can fail but one at a time. A failure scenario consists on the total failure of one link, i.e., the temporary lost of a link. This assumption may be considered valid for large scale wired networks using for instance optical fiber. In this thesis, we consider a link as perturbed if its modulation scheme has changed and so its capacity decreased. Despite a large amount of strategies available to recover from total failures (global rerouting, N:M protection [START_REF] Mannie | Recovery (protection and restoration) terminology for generalized multi-protocol label switching (gmpls)[END_REF], path diversity (Pióro and Medhi 2004a), . . . ), only a few of them seem to be able to manage partial failures.

Our contribution can be summarized as follows. First, we have studied state-of-the-art recovery mechanisms. These mechanisms have been studied in deep, their mathematical model presented, solved and compared. Our objective is to take the advantages of the existing strategies while limiting their drawbacks.

Hence, we have designed a protection strategies denoted Flow Thinning (FT), which handles partial link failures. We formulated the mathematical LP model for network design problem under such recovery strategy. FT is shown to be N P -hard. We chose tu use decomposition algorithms to solve this problem. The column generation (CG) algorithm differs from usual CG algorithm in the sense that it requires solving Mixed Integer Linear Program (MILP) using binaries. In addition, a complexity study has been made and special cases were presented and solved using arc-node formulations. This work has been done in collaboration with my supervisor Prof. Dritan Nace with Prof. Michal Pióro from Warsaw University of Technology (Poland) and Lund University (Sweden) and Dr. Michael Poss from the Université de Montpellier (France).

Moreover, the work on FT was done in parallel with the design of a second strategy named Elastic Flow Rerouting (EFR). We studied the mathematical modelisation of this strategy, still using CG algorithms. Contrary to FT, EFR required branch-and-bound algorithm coupled with CG. Hence, we had to develop a heuristic to obtain near-optimal solutions in a limited period of time. This work was done in collaboration with Dr. Mateusz Z ˙ otkiewicz from Warsaw University of Technology and Dr. Ilir Shinko from Polytechnic University of Tirana (Albania) in addition to the group working on FT.

Finally, we have addressed the practicability of the two strategies and the implementation issues.

Outline of this thesis

This thesis is composed of three main parts.

The first part is divided into three chapters and includes this introduction chapter, together with a literature review of state-of-the-art recovery mechanisms. Recovery mechanisms can be categorized in protection or restoration mechanisms. We present three protection strategies, denoted 1+1 Protection [START_REF] Mannie | Recovery (protection and restoration) terminology for generalized multi-protocol label switching (gmpls)[END_REF], N:M Protection [START_REF] Mannie | Recovery (protection and restoration) terminology for generalized multi-protocol label switching (gmpls)[END_REF] and Path Diversity (Pióro and Medhi 2004a). We also present several restoration strategies. In those strategies, the rerouting can be local, i.e. around the failure (Local Rerouting), or end-to-end from the source to the destination of the demand (Global Rerouting, endto-end rerouting with and without stub release). We also introduce Shared Robust Rerouting [START_REF] Fundo | A hybrid rerouting scheme[END_REF]), a hybrid mechanism in which some non-affected demands can release capacities in a failure state. We analyze though brief explanations and examples the idea of each strategy. All these strategies, but Global Rerouting, can only manage total link failures. Thus, we present some mechanisms handling partial link failures as Elastic Traffic Flows [START_REF] Tomaszewski | Design of optical wireless networks with fair traffic flows[END_REF] or Probabilistic Routing [START_REF] Claßen | Bandwidth assignment for reliable fixed broadband wireless networks[END_REF]. A focus will be put on the mechanisms used in MPLS networks. Hence, we introduce some MPLS specific mechanisms such as MPLS Fast Reroute [START_REF] Pan | Fast reroute extensions to rsvp-te for lsp tunnels[END_REF] and MPLS-TE Auto-bandwidth adjustment [START_REF] Dhody | Pcep extensions for mpls-te lsp automatic bandwidth adjustment with stateful pce[END_REF]. This review of the literature is followed by an introduction to the network dimensioning problem. The mathematical formulation of most strategies is presented using continuous linear program (LP) or mixed integer linear program (MILP). Some of these strategies lead to N P -hard network dimensioning problems (end-to-end rerouting for instance with stub release). Furthermore, compact arc-node formulations are not always possible or not convenient to handle realistic instances and the preferred models are those based on path-flow variables. Hence, we use Path Generation (PG) to avoid the use of the full set of paths and to reduce the size of the problems. This part is concluded by a numerical study of the efficiency of the strategies.

The second part, composed of Chapters 4, 5 and 6 is dedicated to the Flow-Thinning strategy (FTS) [START_REF] Pióro | An optimization model for multicommodity flow networks with partial multiple link failures[END_REF]). The main idea behind FTS is as follows. Following the idea of path diversity, we assume that each demand is in general routed over several paths, not necessarily disjoint, with over-dimensioned path-flows to ensure an assumed level of survivability. Unlike conventional end-to-end restoration strategies, FTS guarantees survivability solely by releasing a fraction of flow on the affected routing paths. Consequently, no flow is rerouted or increased. It is important that this thinning of path-flows is done in an appropriate failure-state dependent way. Chapter 4 introduce the strategy through examples. Then, we present the basic FT optimization problem (FTOP) followed by a discussion on its complexity. FTOP is N P -hard at least for two-links failure scenarios. Thus, we study the separation problem and propose an original Path Generation algorithm using a binary LP. Next, in Chapter 5, we study the efficiency of FTS. We first compare the dimensioning cost of the network using FTS with other strategies presented in Chapter 2. This study is followed by a comparison with a lower bound formulation of the problem. In the last chapter (Chapter 6), we present an affine version of FTS that reduces the number of failure states for which the strategy needs to be optimized (propose in [START_REF] Pióro | Optimizing flow thinning protection in multicommodity networks with variable link capacity (submitted)[END_REF]). Next, we deal with implementation issues of FTS and its affine variant. Finally, we present an extension of FTS that allows for thickening and we explain the reasons why this was not considered in the final version of FTS.

The third and last part is composed of Chapters 7,8 and 9. This part is dedicated to the Elastic Flow Rerouting (EFR) strategy [START_REF] Fouquet | Elastic routing: a distributed variant, implementation issues, and numerical results[END_REF] which works as follows. In the nominal state (when all links are operational), traffic is routed over a given set of paths for each traffic demand. In each failure state, EFR uses the same set of (nominal) routing paths but with possibly modified path-flow values. The main idea behind EFR is to restore traffic of the affected demands by means of increasing the flow on their routing paths, possibly together with decreasing flows of the unaf-fected demands. Notice that no new paths are allowed to be established. Summarizing, flows (on existing paths) can be increases due to capacity released on affected paths, capacity possibly released on some paths of unaffected demands or protection capacity present on links due to network over-dimensioning. In Chapter 7, we introduce the mathematical formulation for total failure scenarios (EFR-P) together with a complexity study. EFR-P is N P -hard and requires branch-and-price to be solved to optimality due to the distinction between affected and unaffected demands. Thus, we propose a greedy heuristic method to solve EFR. Note that once again, EFR-P is solved using Path Generation with a pricing problem requiring a binary problem. As this thesis deals with both total and partial failures, in chapter 8, we study practical applications of EFR to partial failures. Following the idea of microwave communications (presented in 1.1.1), we introduce channels and modulation schemes in our formulation and show how EFR can be combined with FTS to give a strategy capable to handle both type of failures. Finally, we study a distributed variant of EFR. In the last chapter of this part, Chapter 9, we study the efficiency of EFR and its formulations followed by an analysis of the heuristic method performance. We conclude this part with a study of restoration time in case of failure of both centralized and distributed versions of EFR.

In the conclusion, we summarize the work done in the thesis. We analyze our contribution to the literature about rerouting strategies and network design. Finally, we present possible future works on these strategies. T his chapter is dedicated to a general presentation of recovery mechanisms for communication networks. We have chosen MPLS networks (see appendix A. ) to illustrate the mechanisms. Obviously, these methods can be applied to other transport protocols, especially to tunneling protocols. The first section will briefly introduce the strategies. In the next section, we consider total link failures and study the most well-known recovery mechanisms divided in protection and rerouting strategies. In the third section, we analyze strategies of the literature for partial link failures. Finally, the last section will sum up the advantages and drawbacks of each strategies.

Introduction to Recovery Mechanisms

Resiliency in telecommunication networks is currently an important issue and a hot research topic in network optimization. The main problem remains the design of efficient recovery techniques in terms of management effort and cost-effectiveness. Generally speaking, in a network we distinguish between the nominal state (where all elements are operational) and failure states (where one or more elements have ceased to function). Each 11 failure state is identified by the subset of the failed elements. The restoration procedure then works as follows: given a fixed routing in the nominal state, in cases of failure backup Label Switch Paths (LSPs) are used to restore the disrupted traffic following a precise recovery process. Before discussing in details the mechanisms that are the focus of this chapter let us recall briefly the main existing recovery techniques. Roughly speaking, recovery techniques can be separated into protection strategies and restoration strategies. Figure 2.1 presents a classification of the recovery mechanisms presented in this chapter. In this figure, strategies able to manage total link failures are represented with a T while strategies that can handle partial failures are indicated with a P. Note that GR can manage both type of failure scenarios. Let us recall some basic notions. A traffic demand is represented by a pair of nodes and a flow metric that needs to be satisfied between these nodes. The traffic demands are summarized in a demand matrix. The routing in the network is the flow which satisfies a given traffic demand, i.e. a set of LSPs between the two extremities of all demands with a nonnegative flow value. These LSPs are called nominal routing paths. As stated above, we distinguish between the nominal state (NS) where the entire network is operational and the failure state (FS) where at least one link is not operational. In this chapter, we will focus on cases where only one link can fail at any given time. We consider here total link failures, where the failed element is assumed to have totally ceased to function, and partial link failures, where only a part of the link capacity is lost. Rerouting in cases of link failure involves reorganizing the routing of some demands, which may or may not have been disrupted by the failure, in order to restore the lost traffic. The lost traffic is thus (re)routed through some backup LSPs or restoration paths. Protection schemes use preplanned recovery paths that are fully defined before the failure occurs. Protection schemes can be divided into three main groups: Protection 1 + 1, Protection N : M, and Path Diversity (PD). Rerouting is a way of restoring traffic that is an alternative to protection schemes. It ensures restoration using the capacity available in the network to route the disrupted traffic. The recovery level can be very high (up to 100%). At the same time, the residual capacities can be shared between different backup paths, which makes this strategy more cost-effective than protection strategies. The main drawback of rerouting is that when failures occur the recovery time and the number of paths used are significantly higher compared to protection strategies. The best-known rerouting strategies are local rerouting (LR) and end-toend rerouting, depending on whether the traffic is rerouted between the extremities of the failed link or the extremities of the disrupted demand. Hence, end-to-end rerouting handles failures by rerouting the traffic from the source to the destination nodes on alternative LSPs. When a failure occurs in a network and a set of demands is disrupted, the following endto-end rerouting strategies may be used:

• Global Rerouting (GR) if nominal paths are removed after the failure and a set of paths is created to route the traffic,

• End-to-end Rerouting without stub release (RR ) if only disturbed traffic is rerouted and restoration is done using available capacities in the network,

• End-to-end Rerouting with stub release, or Restricted Restoration (RR + ) when restoration is done using available capacities in the network and capacities released by disturbed paths. Some other strategies will be presented as they are an extension of the previously described strategy (ShRR extends RR + ), or specific MPLS mechanisms (MPLS Fast Reroute and Auto-Bandwidth Adjustment).

Example 2.1 In this section, every strategy will be illustrated using the same example. Let

2 A B 1 2 2 2 E 1 C D 2

STRATEGIES FOR TOTAL LINK FAILURES

ln this section, we present mechanisms that are designed to manage total link failures. First, protection strategies are presented, followed by restoration strategies. Finally, MPLS Fast Reroute, a dedicated MPLS mechanism will be presented. Protection :1+:1 1+1 Protection [START_REF] Mannie | Recovery (protection and restoration) terminology for generalized multi-protocol label switching (gmpls)[END_REF] is composed of one working LSP,. one protection LSP, and a permanent bridge. At the ingress node, the normal traffic is permanently bridged to both the working and protection LSP. At the egress node, the normal traffic is selected from the better of the two LSPs. Due to the permanent bridging, the 1+1 protection does not allow an unprotected extra traffic signal to be provided. At the ingress, the normal traffic is permanently connected toits N working LSPs and to one of its M protection LSPs. At the egress node, the normal traffic is selected from either its working or one of the protection LSP. Unprotected extra traffic can be transported over the M protection LSP whenever the protection LSPs is not used to carry a normal traffic.

A B 1/1 A B 1/1 C D 1/1 E 1/1 E C D 1/1

Path Diversity -PD

Path Diversity (Pióro and Medhi 2004a), or Demand-wise Shared Protection [START_REF] Koster | Demand-wise shared protection for meshed optical networks[END_REF], is a protection scheme in which the traffic of a demand is routed in several paths not necessarily vertex-disjoint. They are "dedicated" to this demand and a part of the reserved bandwidth is intended for backup. The only requirement is that, whatever the failure link, the remaining capacity on the non-disrupted paths has to be sufficient to route all the traffic corresponding to the demand. Note that the complete establishment of the restoration LSP (i.e., activation) occurs only after failure detection and/or notification of the working LSPs and requires some additional restoration signaling. Therefore, this mechanism protects against working LSPs failure(s) but requires activation of the restoration LSPs after failure occurrence. After the ingress node has activated the restoration LSPs, the latter can carry the normal traffic. Notice that when each working LSP is recoverable by exactly one restoration LSP, one refers also to 1+1 Protection.

In Figure 2.6, the demand is routed from node A to node E. Paths {A-B-E} and {A-B-D-E} are working LSPs, while paths {A-C-D-E} and {A-C-B-E} are protection LSPs. When link (B,E) fails, 0.5 unit of bandwidth is missing to fully route the traffic of demand (A,E). Hence, protection path {A-C-D-E} is activated and the two paths can route all the traffic.

Restoration Strategies

Rerouting is another way to restore the traffic. It ensures restoration using the unused capacity available in the network to route the disturbed traffic. The recovery level can be very high (until 100%). In the same time, the 0.5/0.5 0/0.5 residual capacities can be shared between different backup paths, which makes this strategy more cost efficient than protection strategies. The main drawback of this rerouting strategy is that the recovery time in case of failure and the number of paths used for every demand is really higher than ones obtained by protections strategies.

Local Rerouting-LR

When a link failure occurs, the rerouting is clone between the extremities of the broken link. ln other words, a new demand is created between the extremities of the broken link with a value equal to the nominal flow on this link. Concerning non-disturbed paths, no modification will be clone.

ln

Global Rerouting -GR

This strategy allows us to reroute all the demands, even those which are not perturbed by the failure. This strategy is highly complex to manage and almost not conceivable for large networks. However, this strategy is the most cost efficient and is used as a lower bound for the other strategies. to route the traffic using path {A-C-D-E} for demand (A,E) and {A-B-D} for demand (A,D).

End-to-end rerouting with stub release-RR+

This strategy can reroute the disturbed paths using the capacities released by the other disturbed paths. When a link fails, the traffic of the demands using this link in the nominal state is broken and rerouted on other paths. The capacities used by disturbed routing paths over remaining operational links, are released and can be used for rerouting.

ln the following example, Figure 2.9, demand (A,E) is routed though path {A-B-E}. When link (B,E) fails, this path is perturbed and the traffic can be rerouted to another LSP, here path {A-B-D-E} using capacities available on links ( B, D) and ( D,E) and those released by disturbed path {A-B-E} and link (AB). Note that, contrary to GR (Figure 2.8), path {A-C-D} cannot be rerouted as it is not perturbed . One drawback of the method is in obtaining long routing paths and in sorne cases including cycles [START_REF] Nace | Complexity of a classical flow restoration problem[END_REF]. This happens because the strategy releases all disturbed flows and rerou te them so longer they are, more often they will be affected, released and rerouted [START_REF] Nace | A polynomial multicommodity flow problem with difficult path generation[END_REF]. To the extreme end, it could be possible to release all paths (all are disturbed) and reroute all from scratch, which cornes to be GR.

1 @---Figure 2.9-RR+ before (lejt) and after ( right) failure of link ( B,E).

End-to-end rerouting without stub release-RR-

This strategy reroutes the lost traffic without using capacities released by the disturbed paths i.e. the capacities are dedicated to the routing or to the rerouting but not to both of them. This strategy is easier to implement than the RR+ strategy but it is more costly due to the split between nominal and restoration available capacities. In Figure 2.10, we consider that 2 units of bandwidth are avaitable on link (A,C) and only 1unit on the other links. After failure of link (B,E), the traffic cannot be rerouted using link (A,B) as their is no room left to route the traffic (remind that rerouting is clone without using capacities released by the disturbed paths). Hence, demand (A,E) can only be rerouted on path {A-C-B-D-E}.

Shared Robust Rerouting-ShRR

Shared Robust Rerouting (ShRR) [START_REF] Fundo | A hybrid rerouting scheme[END_REF] is a hybrid end-toend rerouting method based on the following ideas. First, like for the PD strategy, routing paths allow routing a traffic demand beyond the required demand, i.e. higher than 100% of the demand. This guarantees a high level of robustness when traffic varies. Furthermore the amount of traffic to be rerouted is generally less than for the other rerouting strategies: for instance, it may be that for a given affected demand, the nondisrupted routing paths allow full routing of the demand and no rerouting is needed. The second feature is concerned with the fact that the non-disrupted demands are allowed to release a part of their bandwidth in order to accommodate the rerouting of the disrupted demands. Last, as for the other end-to-end restoration strategies, the rerouting linked to a demand can use paths out of the set of nominal paths. Given all the above, the ShRR strategy combines features from the following recovery techniques: PD, RR+ and GR. In terms of cost-effectiveness this strategy is somewhere between GR and RR+ . Note that ShRR is the base of our work on Elastic Flow Rerouting. ShRR is illustrated by Figure 2.11. Demand (A,E) is routed through a two LSPs {A-B-E} and {A-C-D-E}, and demand (A,D) is routed using two paths {A-B-D} and {A-C-D}. When link (B,E) fails, the bandwidth associated to path {A-B-D} is reduced by 0.5 units to make room for new (rerouting) paths on links (A,B) and (B,D). Hence, demand (A,E) can be rerouted using path {A-B-D-E}.

MPLS feature -MPLS Fast Rerouting

MPLS Fast Reroute [START_REF] Pan | Fast reroute extensions to rsvp-te for lsp tunnels[END_REF]) (also called MPLS local restoration) is a hybrid strategy between local rerouting and end-to-end rerouting. MPLS Fast Reroute works as follows. A LSP is set for a demand. When a link of this LSP fails, the upstream node of the failed link informs the source node of the demand and reroute the traffic directly to the destination. This is a temporary action which enable fast recovery of the traffic. Once the ingress node is aware of the failure, it switches the traffic to a protection LSP from the source to the destination nodes of the demand.

1 1 A B A B E 1 E C D C D 1

Strategies for partial link failures

In this section, we present mechanisms that are designed to manage partial link failures or that can be adapted to manage them. [START_REF] Claßen | Bandwidth assignment for reliable fixed broadband wireless networks[END_REF] propose a method that we call Probabilistic Routing which has been designed for wireless microwave networks and could be seen as an extension of Path Diversity to manage partial link failures. It ensures that the flows can carry the required traffic with high probability. Indeed, when designing the network to be used with PR, the capacity of each link is computed so that, in case of failure i.e. change of modulation, the link can carry out the traffic. If we consider that a probability is given to each link and each possible modulation scheme. Hence, as the available capacity on the link depends on the modulation scheme, a probability is given to each failure scenarios. Taking into account these probabilities, a nominal capacity (corresponding to the best modulation scheme) is assigned to each link while capacities in case of failure only depend on the change of modulation. Contrary to PD, the traffic routed for a demand in the nominal case is not higher than the requirements but the capacity of the links is highly over-dimensioned, as it can be observed in Figure 2.13.

Probabilistic Routing -PR

1 1 A B A B 2 Mbps E  1 Mbps E C D C D

Global Rerouting -GR

Global Rerouting has not been designed for partial link failures. However, as all nominal paths are released after a failure, partial failure can be easily managed. Note that this strategy remains the most cost efficient for the management of partial link failures. Figure 2.15 illustrates the behavior of Global Rerouting when suffering from a partial link failure. In the nominal

2.3-4 MPLS feature -MPLS TE Auto-bandwidth Adjustment

MPLS TE Auto-Bandwidth Adjustment [START_REF] Dhody | Pcep extensions for mpls-te lsp automatic bandwidth adjustment with stateful pce[END_REF] allows an LSP to automatically and dynamically ad just its reserved bandwidth over time, i.e. without network operator intervention. The bandwidth adjustment uses the make-before-break adaptive signaling method so that there is no interruption to traffic flow.

The new bandwidth reservation is determined by sampling the actuai traffic flowing through the LSP. If the traffic flowing through the LSP is lower than the configured or current bandwidth of the LSP, the extra bandwid th is being reserved needlessly and being wasted. Conversely, if the actual traffic flowing through the LSP is higher than the configured or current bandwidth of the LSP, it can potentially cause congestion or packet loss. Contrary to the presented strategies, Auto-bandwidth is not computed off-line, the LSP bandwidth can be set to sorne arbitrary value (even zero) during initial setup time, and it will be periodically adjusted over time based on the actual bandwidth requirement.

The traffic rate is repeatedly sampled at each interval and the sampled traffic rates are accumulated over the interval period. The ingress node reports the traffic information. Auto-Bandwidth will ajust the bandwidth of the LSP to the highest sampled traffic rate amongst the set of samples taken over the adjustment-interval. Note that the highest sampled traffic rate could be higher or lower than the current LSP bandwidth.

Auto-Bandwidth Adjustment is a mechanism that deals with capacity changes (i.e. partial failures). RSVP tunnels (used by MPLS TE) are periodically refreshed to recover from network capacity changes. If the capacity of a link has been reduced, the refresh process will fail, the LSP will be broken and the traffic will be rerouted to other LSPs. Instead of removing the LSP, Auto-Bandwidth feature will decrease the bandwidth of the LSP. As the traffic is too high, it will then try to enlarge the LSP.

Because of the failure, this action will fail and the traffic will be rerouted through other LSPs.

I 3

Notation

The considered network is modeled with a graph G = (V , E ), undirected or directed, composed of the set of nodes V and the set of links E . In the sequel, we will always assume directed graphs, unless explicitly stated otherwise. Thus, each link e ∈ E represents a directed pair (v, w) of nodes 23 v, w ∈ V , and is assigned a non-negative unit capacity cost ξ e which is a parameter, and the maximum capacity y 0 which is an optimization variable. The cost of the network is given by the quantity C = ∑ e ξ e y 0 . The traffic demands are represented by the set D. Each demand d ∈ D is characterized by a directed pair (o(d), t(d)), composed of the originating node o(d) and the terminating node t(d), and a reference value h 0 (a parameter) of the traffic volume that has to be carried from o(d) to t(d).

Here δ + (v) = {(v, w) ∈ V } and δ (v) = {(u, v) ∈ V } are the outgoing arcs and ingoing arcs of v, respectively. Demand volumes and link capacities are expressed in the same units.

Each Note that we can represent flows, not as an end-to-end path-flow, but as a flow routed through an edge. These flows are defined, for each demand, by the vector

f d = ( f d , e ∈ E , d ∈ D).
The basic feature of the considered network model is that the links are subject to failures. In the nominal state S 0 (failure-less situation), link capacities are defined by the vector y 0 = (y 0 , e ∈ E ). In a failure scenario, a subset of links have no capacity (failed links), and the remaining links are totally operational. We thus distinguish a set of failure scenarios S . Each state s ∈ S is characterized by the two following fixed vectors: the link availability coefficient vector α s := (α s , e ∈ E ), and the traffic demand satisfaction coefficient vector β α s := (β s , d ∈ D). Basically, we assume s e = 0 for all edges e which failed in failure state S and α e = 1 for all other links. The capacity of link e ∈ E available in state s is equal to y s s 0 e := α e y e while the volume of demand d ∈ D to be carried in s is given by h s := β s h 0 (the fixed parameter β s is called the demand coefficient).

d d d d

Recall that h 0 := (h 0 , d ∈ D) is a given demand volume reference vector. The set of links that are not available in state s ∈ S will be denoted by E s := {e ∈ E : α s < 1}, and, symmetrically, the set of states in which link e ∈ E is not available, by S e := {s ∈ S : α s < 1}. Note that E s = ∅ for each s ∈ S 0 .

∑ f d f d 0 e∈δ + (o(d)) e + ∑ e∈δ (o(d)) e ≥ h d , d ∈ D (3.1c) ∑ e∈δ + (v) e ∑ e∈δ (v) e = 0, d ∈ D, v ∈ V \ {o(d), t(d)} (3.1d)
f , y continuous and nonnegative (3.1e)

Objective (3.1a) minimizes the total cost of links. The first capacity constraint (3.1b) makes sure that the reference link loads do not exceed the maximum link capacities. Next, the demand constraint (3.1c) assures that the net out-flow of the demand sources are sufficient to realize the volume of each demand d ∈ D. Equations (3.1d) are called flow conservation constraints (or Kirchoff constraint), since they guarantee that the in-flow equals the out-flow for all nodes except o(d) and t(d). Note that this LP can be solved polynomially.

We now give a path formulation for the nominal routing problem. The problem assumes that the required demand volume h 0 (d ∈ D) is realized within the bandwidth reserved by the reference flows x 0 , p ∈ P d , so that the links capacities y 0 , e ∈ E , available in state s are not exceeded. For given admissible path-lists P d , d ∈ D, the considered problem is denoted by P(P ) (where P = U d∈D P d ) and represented by the following link-path linear programming (LP) formulation involving variables x 0 (d ∈ D, p ∈ P d ), and y 0 (e ∈ E ):

min C = ∑ ξ e y 0 (3.2a) [π 0 ≥ 0] y 0 e∈E δ x 0 ≥ 0, e ∈ E (3.2b) e e ∑ ∑ ed p d p d∈D p∈P d [λ 0 ≥ 0] 0 d p p∈P d ≥ h 0 , d ∈ D, s ∈ S (3.2c)
x 0 , y 0 continuous and nonnegative (3.2d) Objective (3.2a) minimizes the total cost of links. The first capacity constraint (3.2b) makes sure that the reference link loads do not exceed the maximum link capacities. Next, the demand constraint (3.2c) assures that the flows are sufficient to realize the volume of each demand d ∈ D. The optimal value of the cost (3.2a) of P(P ) will be denoted by C(P ). In (3.2), the quantities in the square brackets on the left-hand side are dual variables. Dual variable π 0 corresponds to the increase of the objective function (3.2a) for one unit of bandwidth reserved on edge e ∈ E without being used by any paths. In the same way, λ 0 represents the increase of the objective function for one unit of traffic increase for demand d ∈ D. Let us introduce reduced costs. While dual variables are associated to constraints in the LP, reduced costs are associated to the variables. The reduced cost associated to an edge e ∈ E takes 0 if the edge is used, i.e. at least one path is routed through this edge, c e otherwise. The reduced cost corresponding to a path p ∈ P d represent the increase of the objective function if the path is used, and takes value 0 if it is already used. These dual variables and reduced costs will be of high interest when studying dual separation in subsection 3.2.1.

Observe, that our assumption of admitting only elementary paths on the path-lists made in 3.1 is not limiting. If we admitted non-elementary paths in the overall path-list P , then eliminating loops in any feasible solution of P(P ) would never increase C(P ). For the full sets of admissible paths, the corresponding instance of problem (3.2) is referred to as P( ˆ ). Contrary to (3.1), this formulation would require adding all paths to the problem and the number of variables would become very large.

In order to avoid an exponentially high number of variables, we will use Path Generation (PG). In this context, P(P ) with P ⊂ ˆ a subset of all admissible paths, represents the restricted master problem. Note that a feasible solution x 0 , d ∈ D, p ∈ P d for P(P ) can be expanded to a feasible ˆ ˆ ˆ solution x 0 , d ∈ D, p ∈ P d for P(P ) (setting x 0 = 0 for p ∈ P d \ P d .

Dual problem and dual separation

Let us consider the problem dual to problem P(P ) formulated in (3.2) for a given set of admissible paths P . The dual, denoted by D(P ), is as follows:

max W = ∑ h 0 λ 0 (3.3a) d d d∈D π 0 e ≤ ξ e , e ∈ E (3.3b) d p ≤ ∑ e∈E δ ed p π 0 , d ∈ D, p ∈ P d (3.3c)
all variables λ, π continuous and nonnegative. (3.3d) Let Π(P ) denote the dual polyhedron of all feasible solutions (π, λ) of D(P ), where π = (π 0 , e ∈ E ), λ = (λ 0 , d ∈ D). We treat the dual Let W (P ) denote the optimal value of the objective function (3.3a) of D(P ). Clearly, W (P ) is also equal to the optimal value of objective (3.3a) maximized over (π, λ) ∈ T(P ). Due to the strong duality property [START_REF] Lasdon | Optimization Theory for Large Systems[END_REF][START_REF] Minoux | Mathematical Programming: Theory and Algorithms[END_REF]), W (P ) = C(P ). Moreover, P ⊆ ˆ implies that polyhedron Π(P ) contains polyhedron Π( ˆ ), so that W (P ) ≥ W ( ˆ ) P P and hence W (P ) is actually an upper bound of the optimal objective C( ˆ ) of P( ˆ ). Suppose π, λ form an optimal solution of the dual problem D(P) defined by (3.3). Checking whether the above inequalities are satisfied for all paths q ∈ ˆ is called pricing subproblem. This can be done efficiently by computing paths w.r.t. the weight vector π 0 , e ∈ E for each commodity d ∈ D. If a path is at least λ d , then we must have:

∑ δ ed p π 0 0 d e∈E e ≥ λ d p , d ∈ D, p ∈ P (3.4)
Otherwise, we find a new path q that has the positive reduced cost and we can add this path (column) to the new master problem P(P U q).

Path generation

In fact, in path generation it is advantageous (to speed up the PG algorithm) to find, for each d ∈ D, not only a path (if any) in ˆ that just separates the current dual solution π, λ, but rather a path q ∈ ˆ for which the dual constraints (4.2c) are maximally violated by the considered dual solution π, λ. This is especially true when finding such a path is not substantially more complex than finding an arbitrary path that violates the dual constraints. In our setting, the (negative) measure of violation of the dual constraints corresponding to path q is equal to 0 0 lql = ∑ e∈E δ ed p π e λ d provided it is negative. Maximizing the measure of violation is equivalent to minimizing ∑ e δ π 0 . This can be done efficiently by computing the shortest path w.r.t. the weight vector π 0 , e ∈ E . Note that finding a shortest path in graph G (V , E ) with nonnegative weights π 0 ≥ 0, e ∈ E is polynomial (e.g., by Dijkstra's algorithm).

The PG algorithm is then described in Algorithm 1.

Algorithm 1: PG algorithm for the nominal routing Input: Graph G = (V , E ), a set of demands D, a vector of traffic requirements h 0 and an admissible paths-list P .

Output: Subset of paths P ⊆ ˆ leading to optimal cost C P ). 1: Repeat 2:

Solve P(P )

3:

Let π, λ be the dual variables for D(P ) 4:

For each demand d ∈ D

5:

Find a shortest path w.r.t. weights π 0 6:

If length of shortest path q is less that λ 0 , add q to P 7:

End If 8:

End for 9: Until no path has been added

Study of Global Rerouting

As we did in the previous section, let us introduce the edge-node LP formulation of GR involving variables f 0 (d ∈ D, e ∈ E ), f s (d ∈ D, s ∈ S , e ∈ E \ s) and y 0 (e ∈ E ):

∑ f 0 f 0 0 e∈δ + (o(d)) d,e + ∑ e∈δ (o(d)) d,e ≥ h d , d ∈ D (3.5c) ∑ e∈δ + (v) d,e ∑ e∈δ (v) d,e = 0, d ∈ D, v ∈ V \ {o(d), t(d)} (3.5d) ∑ f s 0 d∈D d,e ≤ y e , s ∈ S , e ∈ E (3.5e) ∑ f s f s 0 e∈δ + (o(d)) d,e + ∑ e∈δ (o(d)) d,e ≥ h d , s ∈ S , d ∈ D (3.5f) ∑ e∈δ + (v) d,e ∑ e∈δ (v)
d,e = 0,

s ∈ S , d ∈ D, v ∈ V \ {o(d), t(d)} (3.5g)
f 0 , f s , y continuous and nonnegative (3.5h) Objective (3.5a) minimizes the total cost of links. Capacity constraints (3.5b) and (3.5e) make sure that the reference link loads do not exceed the maximum link capacities in the nominal and failure states. Next, the demand constraints (3.5c) (resp. (3.5f)) assure that the out-flow of the demand sources are sufficient to realize the volume of each demand d ∈ D in the nominal (resp. failure) state. Equations (3.5d) and (3.5g) are called flow conservation constraints, since they guarantee that the in-flow equals the out-flow for all nodes except o(d) and t(d). Note that this LP can be solved polynomially.

We now give a path formulation for the problem. For given admissible path-lists P d , d ∈ D, the considered problem is denoted by P(P ) (where P = U d∈D P d ) and represented by the following link-path linear programming (LP) formulation involving variables x 0 (d ∈ D, p ∈ P d ), and y 0 (e ∈ E ):

min C = ∑ ξ e y 0 (3.6a) [π 0 ≥ 0] y 0 e∈E δ x 0 ≥ 0, e ∈ E (3.6b) e e ∑ ∑ ed p d p d∈D p∈P d [λ 0 ≥ 0] 0 d p p∈P d ≥ h 0 , d ∈ D (3.6c) [π 0 ≥ 0] y 0 δ x s ≥ 0, s ∈ S , e ∈ E (3.6d) e e ∑ ∑ ed p d p d∈D p∈P d [λ s ≥ 0] s d p p∈P d ≥ h s , d ∈ D, s ∈ S (3.6e)
x 0 , y 0 continuous and nonnegative (3.6f) (where the quantities in the square brackets on the left-hand side are dual variables). Objective (3.6a) minimizes the total cost of links. The first capacity constraint (3.6b) makes sure that the reference link loads do not exceed Capacity constraint (3.6d) makes sure that the link loads do not exceed the maximum link capacities in any failure scenario s. Finally, constraint (3.6e) assures that the flows are sufficient to realize the possibly reduce volume of each demand. The optimal value of the cost (3.6a) of P(P ) will be denoted by C(P ).

Dual problem and dual separation

Let us consider the problem dual to problem P(P ) formulated in (3.6) for a given set of admissible paths P . The dual, denoted by D(P ), is as follows: Below, D(P ) will denote the problem defined by (3.7) for a given set of admissible paths P = U d P , Π(P )-the polyhedron (in R n of an appropriate dimension n) defined by constraints (4.2b)-(4.2e), and W (P )the optimal value of the objective function of D(P ). Certainly, W (P ) is equal to the optimal value C(P ) considered for the admissible path-set P , and W ( ˆ ) (recall that ˆ is the maximum set of admissible paths) is the P P solution of GR we are looking for. Certainly, W (P ) ≥ W ( ˆ ) for P ⊆ ˆ . P P Suppose π, λ form an optimal solution of the dual problem D(P ) defined by (3.7). We consider the following two cases that fully characterize the set of all paths q ∈ ¯ \ P d that separate the current optimal dual solution.

max W = ∑ h 0 λ 0 + h s λ s (3.7a)
Case 1 There exists a path q such that |q| < λ 0 which, by equation (3.7c), makes the inequalities in (3.7) infeasible.

Case 2 Suppose that |q| ≥ λ 0 for a path q, and for some s ∈ S , |q| s < λ s .

Equation (3.7d) does not allow any |q| s λ s to be negative. Hence, (3.7) is infeasible.

Path generation

Because of the specific form of the LP, we can use Benders decomposition [START_REF] Benders | Partitioning procedures for solving mixed-variables programming problems[END_REF]. Hence, the path generation process requires a subproblem for each demand d ∈ D, for the nominal state and for each failure state s ∈ S . Subproblems related to the nominal state are the same than in 3. is polynomial (e.g., by Dijkstra's algorithm). The PG algorithm is then described in Algorithm 2.

Algorithm 2: PG algorithm for Global Rerouting Input: Graph G = (V , E ), a set of demands D, a vector of traffic requirements h s , s ∈ S U S 0 and an admissible paths-list P .

Output: Subset of paths P ⊆ ˆ leading to optimal cost C P ).

1: Repeat 2:

Solve P(P )

3:

Let π, λ be the dual variables for D(P ) 4:

For each demand d ∈ D

5:

Find a shortest path w.r.t. weights π 0 6:

If length of shortest path q is less that λ 0 , add q to (GR) If length of shortest path q is less than λ s , add q to P 12:

End If 13:

End for 14:

End for 15:

End for 16: Until no path has been added

Mathematical formulation of the restoration methods

In this section, we study the dimensioning problem for five other recovery methods of the literature: end-to-end rerouting with stub release (RR + ), end-to-end rerouting without stub release (RR ), local rerouting (LR), path diversity (PD) and shared robust rerouting (ShRR).

End-to-end rerouting with stub release -RR +

The arc-path formulation of the problem dimensioning problem for RR + , denoted P RR + (P ), is as follows: Using notations introduce in section 3.3 (i.e. |q| 0 and |q| s ), we can extract from 3.9 that a path q ∈ ˆ \ P d will be added to 3.8 if it meets one of the following cases. Case 1 |q| s < λ s . This can be computed using Dijkstra's algorithm with with nonnegative weights e ≥ 0, s ∈ S , e ∈ E \ s.

[λ 0 ≥ 0] 0 d p p∈P d ≥ h 0 , d ∈ D (3.8c) [π s ≥ 0] y 0 e e ∑ ∑
Case 2 |q| 0 + ∑ s ,s /q |q| s < λ 0 + ∑ λ s . This inequality can easily be

∈S ∈ d s∈S ,s∈ /q d transformed to |q| 0 + ∑ s ,s /q |q| s + ∑ λ s < λ 0 + ∑ λ s . Note ∈S ∈ s∈S ,s∈q d d s∈S d s
that the second term of the above equation (∑ s∈S ,s∈ /q |q| ) makes the shortest reduced cost problem difficult. It is similar to the quadratic shortest path problem, a N P -hard problem. Notice, for instance, that the property of the optimality of any sub-path of an optimal path does not apply to this case.

End-to-end rerouting without stub release -RR

RR reroutes the disturbed demands from the source to the destination without using the capacities of the disturbed paths. In this strategy, capacities are used for the nominal state or for the failure state, but not both. The arc-path formulation of the dimensioning problem for end-toend rerouting without stub release, denoted P RR (P ), is a follows:

min C = ∑ ξ e y 0 (3.10a) e∈E y 0 0 e ∑ ∑ δ ed p x d p ≥ 0, e ∈ E (3.10b) d∈D p∈P d ∑ x 0 0 p∈P d d p ≥ h d , d ∈ D (3.10c) e ∑ ∑ δ ed p x 0 ∑ δ ed p x s ≥ 0, s ∈ S , e ∈ E \ s (3.10d) d∈D p∈P d d∈D p∈P s ∑ x 0 x s s p∈P d ,s∈ / p d p + ∑ p∈P s d p ≥ h d , d ∈ D, s ∈ S (3.10e)
x 0 , x s , y 0 continuous and nonnegative (3.10f) Constraints (3.10b) (respectively (3.10d)) express capacity constraints in the nominal (respectively failure) state. Constraints (3.10c) ensure the satisfaction of traffic in the nominal state and constraints (3.10e) ensure the lowest traffic satisfaction rate for the failure scenario s. Finally, the non-negativity of variables is expressed by constraints (3.10f). Note than in constraints (3.10d) all paths are considered, while in constraints (3.10e) only non-disturbed paths are taken into account. Note that path generation for RR is polynomial [START_REF] Lutton | Assigning spare capacities in mesh survivable networks[END_REF].

Local Rerouting -LR

The rerouting process is local if, in case of a link failure, we do not reroute the disturbed demands from the source to the destination but we only reroute the traffic between the extremities of the failure link. Let us introduce some more notations:

• Let P l be the set of paths of graph G (V , E \ l) between the extremities of link l ∈ E .

• Let x l be the proportion of cumulated traffic routed on path p ∈ P l between the extremities of failed link l ∈ E .

The formulation of the dimensioning problem for local rerouting, denoted P LR (L), is a follows:

d∈D p∈P d ∑ x 0 0 p∈P d d p ≥ h d , d ∈ D (3.11c) e ∑ ∑ δ ed p x 0 δ e p x l ≥ 0, l ∈ E , e ∈ E \ {l} (3.11d) d∈D p∈P d ∑ x l p∈P l x 0 p∈P l p ≥ ∑ p∈P d ,l∈p d p , d ∈ D, l ∈ E (3.11e)
x 0 , x s , y 0 continuous and nonnegative (3.11f) Constraints (3.11b) (respectively (3.11d)) express capacity constraints in the nominal (respectively failure) state. Constraints (3.11c) ensure the satisfaction of traffic in the nominal state and constraints (3.11e) ensure that all the lost traffic from the extremities of the failed link l is rerouted. Finally, the non-negativity of variables is expressed by constraints (3.11f). Note that, as RR , path generation for LR is polynomial.

Path Diversity -PD

Contrary to the above strategies, PD is a protection strategy. The only requirement is that in case of failure, enough bandwidth is remaining to route the traffic of every demand. The formulation of the dimensioning problem for path diversity, denoted P PD (P ), is as follows:

min C = ∑ ξ e y 0 (3.12a) e∈E y 0 0 e ∑ ∑ δ ed p x d p ≥ 0, e ∈ E (3.12b) d∈D p∈P d ∑ x 0 0 p∈P d y 0 d p ≥ h d , d ∈ D (3.12c) 0 e ∑ ∑ δ ed p x d p ≥ 0, s ∈ S , e ∈ E \ s (3.12d) d∈D p∈P d ,s∈ / p ∑ x 0 s p∈P d ,s∈ / p d p ≥ h d , d ∈ D, s ∈ S (3.12e)
x 0 , x s , y 0 continuous and nonnegative (3.12f) Constraints (3.12b) (respectively (3.12d)) express capacity constraints in the nominal (respectively failure) state. Constraints (3.12c) ensure the satisfaction of traffic in the nominal state and constraints (3.12e) ensure the lowest traffic satisfaction rate for the failure scenario s (recall that we only consider single total link failures). Finally, the non-negativity of variables is expressed by constraints (3.12f).

Notice that PD is polynomial in case of single link failure scenarios, i.e. when every link can fail but one at a time. However, it becomes N P -hard in the general case of failure scenarios that admit simultaneous failures of multiple links [START_REF] Tomaszewski | On the complexity of resilient network design[END_REF]. ) + ∑

Shared Robust Rerouting -ShRR

Contrary to the other mechanisms, ShRR makes a distinction between affected and unaffected demands after a failure. A traffic demand d is said to be affected by a failure state s if its surviving nominal path-flows (thinned or not) are not sufficient to carry the traffic volume assumed for this state, i.e., when

∑ p∈ ¯ s x d p + ∑ p∈P s x d p < h s . Otherwise,
min C = ∑ ξ e y 0 (3.13a) e∈E y 0 0 e ∑ ∑ δ ed p x d p ≥ 0, e ∈ E (3.13b) d∈D p∈P d ∑ x 0 0 p∈P d d p ≥ h d , d ∈ D, s ∈ S (3.13c) e ∑ ∑ δ ed p x 0 ∑ δ ed p u s d∈D p∈P s d∈D s p∈P s + ∑ d∈ ¯ ∑ p∈P s d p ≥ 0, s ∈ S , e ∈ E \ s (3.13d) ∑ (x 0 p∈P s s s d p d p p∈P s ≥ h s , d ∈ D, s ∈ S (3.13e) ∑ x 0 s s p∈P s d p + M(T d 1) < h d , s ∈ S (3.13f) ∑ x 0 s s s p∈P s d p + h d T d ≥ h d , s ∈ S (3.13g) x 0 s s d p u d p ≥ 0, d ∈ D, s ∈ S , p ∈ P d (3.13h) u s s s d p + M(T d 1) ≤ 0, d ∈ D, s ∈ S , p ∈ P d (3.13i)
x 0 , x s , u s , y 0 continuous and nonnegative (3.13j) Constraints (3.13b) (respectively (3.13d)) express capacity constraints in the nominal (respectively failure) state. Constraints (3.13f) and (3.13g) classify demands in affected and unaffected. Constraints (3.13c) ensure the satisfaction of traffic in the nominal state and constraints (3.13e) ensure the lowest traffic satisfaction rate in any link failure state. Then, constraints (3.13h) guarantee that decreasing the traffic volume over non-disrupted demand paths by more than the corresponding nominal traffic is not permitted and constraints (3.13i) ensure that only unaffected demands can release bandwidth. Finally, the non-negativity of variables is expressed by constraints (3.13j) . Note that ShRR has not been solved to optimality using classic path generation algorithms because of the distinction between affected and unaffected demands.

Numerical results for all mechanisms

In this section, we present results of computational study illustrating the performances of the mechanisms presented in 3.4 and Global Rerouting.

We also study the efficiency of the path generation algorithm compare to the other formulation of the same problems.

The undirected network instances used in our tests and listed in table 3.1 are taken from SNDlib [START_REF] Orlowski | SNDlib 1.0survivable network design library[END_REF]).

Dimensioning cost

In the following, we compare the Global Rerouting strategy (GR) and the presented strategies (Local Rerouting (LR), Restricted Rerouting with stub release (RR + ), Restricted Rerouting without stub release (RR ) and Path Diversity (PD)) applied to the total single link failure case in terms of cost effectiveness.

For the experiments reported in this section we assume a uniform demand satisfaction ratio β, i.e. h s = βh 0 for all d ∈ D, s ∈ S . In the comparisons, let C GR denote the optimal value of the objective function (i.e., minimum cost of the link capacity) for GR, and C LR , C RR + , C RR , C PD the respective values for the remaining strategies. Certainly, the computed link capacities (and thus the link capacity cost) ensure the routing of all traffic demands in the nominal state and the guaranteed traffic restoration (specified by β) in all failure states.

As we already mentioned, the cost C GR indicated by GR is not greater than any of the remaining cost, as GR assumes the least restricted flow restoration mechanisms. Hence, we can define the relative cost increase (in percent) for each strategy S (where S stands for LR, RR, WoR or PD) with respect to GR as G S = C S C G R * 100%. In the following, this quantity will be called relative gap. Note that, by definition, G GR = 0.

Figures 3. 1-3.3 show that Path Diversity is by far the less cost-efficient strategy with up to 87% gap. Note that PD seems not to be sensitive to variations of β, regarding to the gap with GR. LR and RR have slightly the same cost with a gap varying between 1% and 35% for all networks and all values of β. Finally, RR seems to be the most cost-efficient strategy for single total link failures (after GR) with a gap less than 2% for total traffic restoration, i.e. β = 1.

Efficiency of Path Generation

In sections 3.2, 3.3 and 3.4, a

+ ∑ d |P | + ∑ ∑ |P l | while for PD it is limited to |E| + ∑ d∈D |P d |.
To have a clear sight of these numbers, let us take a look at them for the 4 networks. Hence, the need for PG becomes clear as the number of variables might by very high depending on the network instance. We can see from above that the total number of paths for a highly dense network such as pdh (with only 11 nodes) is up to 2 million while this number is highly reduced for a sparse network with more nodes such as polska. Notice that the network used in this section are small networks. Let us study the efficiency of the arc-path formulation with and without path generation for the GR and RR + strategies. As the compact formulation of GR is presented, it is added to the following results.

Tables 3.3 and3 shows that using PG improves the computation time for these networks.

It is especially clear for GR. More importantly, the number of paths used, and so the number of variables, is drastically reduced (more than 90% less paths) with up to 99.95% of reduction for network pdh for GR. Path Generation will be used for the strategies presented in the following chapters. Note that the pricing problem for RR + is N P -hard and this can be seen for network pdh, where the computation time using PG is up to 23 hours while the computation of the compact formulation is 17 times faster.

Part II

Flow Thinning

This part is dedicated to the Flow-Thinning strategy (FTS). Chapter 4 introduces the principle of the strategy and gives illustration through examples. Then, we present the basic FT optimization problem (FTOP) followed by a discussion on its computational complexity. FTOP is NP-hard at least for two-links failure scenarios. Thus, we study the separation problem and propose an original Path Generation algorithm using a binary LP. Next, in Chapter 5, we study the efficiency of FTS. We first compare the dimensioning cost of the network using FTS with other strategies such as GR. This study is followed by a study of a lower bound formulation of the problem. In the last chapter (Chapter 6), we briefly present an affine version of FTS that reduces the number of failure states for which the strategy needs to be optimized. Next, we deal with implementation issues of FTS and its affine variant. Finally, we present an extension of FTS that allows for thickening and argue why this method cannot be implemented in the current form. low thinning (FTS) is a protection strategy1 , designed to manage multiple partial link failures. In this chapter, we first introduce this strategy with some illustrations. Then, we present the mathematical formulation of the dimensioning problem using FTS, denoted FTOP. Before studying the path generation algorithm, we present the dual separation problem. Next, we analyze the complexity of the pricing problem. Finally, we study two special cases: single partial link failures and single partial node failures.

Flow Thinning -Introduction and Optimization Problem

Introduction to Flow Thinning

The flow-thinning protection strategy (FTS, [START_REF] Pióro | An optimization model for multicommodity flow networks with partial multiple link failures[END_REF]), designed for Multiple Partial Link Failures (MPLF), is inspired by the idea of flow adjustment proposed in ShRR [START_REF] Fundo | A hybrid rerouting scheme[END_REF] and path diversity (Orlowski and Pióro 2012). The main idea behind FTS is as follows:

• Following the idea of path diversity, we assume that each demand is in general routed over several paths, not necessarily disjoint, with over-dimensioned path-flows to ensure an assumed level of survivability.

• Unlike conventional end-to-end restoration strategies, FTS guarantees survivability solely by releasing a fraction of flow on the affected routing paths as ShRR. Consequently, no flow is rerouted or increased. It is important that this thinning of path-flows is done in an appropriate failure-state dependent way.

To give a more clear idea of how FTS works, we wish to emphasize a few points. First, note that no distinction is made between capacity devoted to flow routing in the normal state and those devoted to protection, and all available link capacity is used jointly as a common pool of resources to realize demand flows in failure states. Hence, the selected routing paths carry the flows dimensioned so that the total flow realized on the demand's paths can in general be greater than the nominal traffic. The most important feature of FTS is handling partial failures without any flow rerouting/restoration at all. In other words, no nominal paths increase their flows in failure states and no paths besides the nominal paths are used for handling failure states. Therefore, the proposed approach results in using a sort of limited dynamic routing, adapting to the network states. To summarize, for each demand there is a fixed set of nominal routing paths carrying nominal flows. In a failure state in general only a part of the total nominal demand flow will be realized on these paths, depending on the available capacity and a given demand restoration ratio. Consequently, each affected nominal routing path can only release a fraction of its flow according to the failure that has occurred, and no new (re)routing paths are allowed. Note that FTS becomes equivalent to PD for total link failure situations. Another failure scenario is presented on Figure 4.3, concerning the failure of link ( A, B). This failure scenario is slightly more complex as two paths p 1 and p 3 are routed through this link and due to the failure, the capacity of ( A, B) is now 3 equal to 4 6 and the sum of the bandwidth of the paths routed through ( A, B) is

3 equal to > 4 1
. FTS will manage this failure by releasing all bandwidth of path 4 p 3 , and 4 of bandwidth of path p 1 . Thus, the sum of the bandwidth of the paths 3 routed through ( A, B) is equal to the bandwidth of path p 1 i.e. which is equal 4 to the capacity of link ( A, B). Futhermore, all traffic requirements are met.

Note that, as FTS is a protection strategy, the total bandwidth associated to the demands is always sufficient to route the traffic. However, before FTS manages the failure, strong congestion may appear on the paths routed through the disturbed link.

This example considered failures of 50% of the reference capacities. Figure 4.4 represents the evolution of the optimal dimensioning cost of the network varying the failure coefficient from 0% (nominal state) to 100% (total link failures).

We notice that the optimal cost of C FT = 7 obtained for total link failures (failure coefficient of 100%) corresponds to path diversity.

4•2 FTOP-THE BASIC FT OPTIMIZATION PROBLEM

The basic problem considered in this section is referred to as flow-thinning optimization problem (FTOP) and is as follows. We minimize the cost of link capacity assuming that in the normal state of network operation all demand volumes are realized by means of (normal) path-flows. When the network is subject to a failure from a given set of failure states (we assume that a failure state consists of multiple partial failures of links) then the demand volumes, possibly reduced, are realized for the duration of the failure state by appropriate thinning of the normal flows. The detailed formulation of FTOP will be given in Subsection (4.2.2). A feasible solution is as follows. The nominal capacity of the four tunnels is defined as x 0 0 0 0 11 = 1, x 12 = 1/3, x 21 = 1, x 22 = 1/3 and hence the (minimal) nominal capacity of the links that realizes the nominal flows is equal to y 0 = y 0 = 4/3, y 0 = y 0 = 1/3. The cost of the network is then equal to C = 10/3. The path flows (i.e., the capacity of the tunnels) in the three considered availability states is as follows:

4.2.:1 Notations

x 1 1 1 1 11 = 2/3, x 12 = 1/3, x 21 = 1, x 22 = 0 x 2 2 2 2 11 = 1, x 12 = 0, x 21 = 2/3, x 22 = 1/3 x 3 3 3 3 11 = 1, x 12 = 0, x 21 = 1, x 22 = 0.
Note that the nominal capacity of the tunnels could carry the traffic volume h = 4/3 simultaneously for both demands, i.e., the volume greater than the nominal volume h 0 = 1.

Formulation of FTOP

In essence, FTOP consists in minimizing the cost of nominal link capacity that supports a set of nominal tunnel capacities (path-flows) that are subject to thinning in each of the considered network states. The FTOP instance corresponding to a given set of admissible path-lists P d , d ∈ D is denoted by P FT (P ) (where P = P FT (P ):

C(P ) = min ∑ ξ e y 0 (4.1a) [π 0 ≥ 0] e∈E ∑ ∑ δ ed p 0 ≤ y 0 , e ∈ E (4.1b) [λ s ≥ 0] d∈D p∈P d x s ≥ h s , d ∈ D, s ∈ S (4.1c) d [π s ≥ 0] ∑ d p p∈P d δ d x s ≤ α s y 0 , e ∈ E , s ∈ S e (4.1d) e ∑ ∑ ed p d p e e d∈D p∈P d s ≥ 0] x s 0 , d ∈ D, p ∈ P d , s ∈ S (4.1e)
x 0 , x s , y 0 ≥ 0 and continuous (4.1f)

(where the quantities in the square brackets on the left-hand side are dual variables to be used later).

Objective (4.1a) minimizes the overall cost of links. The first capacity constraint (4.1b) makes sure that the nominal link loads do not exceed the nominal link capacities. Next, the demand constraint (4.1c) Observe that our assumption of admitting only elementary paths on the path-lists made in Section 4.2.1 is not limiting. If we admitted nonelementary paths in the overall path-list P , then eliminating loops in any feasible solution of P FT (P ) would never increase C(P ). This is true because if path p t is an elementary version of path p ∈ P d , then adding p t to P d , putting x 0 := x 0 and x s := x s , s ∈ S , and finally setting x 0 and d p , s ∈ S , to 0 would lead to a feasible solution of (4.1) which does not require the capacity reserved on the links in p \ p t . The last statement also implies that non-elementary paths will not appear in optimal solutions of (4.1) when ξ e > 0, e ∈ E . An illustration of the above considerations is given in Example 4.3.

Example 4.3

For the network depicted in Figure 4.5, the solution given in Example 4.2 is feasible and optimal for 4.1. Note that the flows x 0 , x 1 , x 2 of Example 4.2 are unique at optimality while x 3 are not. For example, the flows x 3 = x 0 are also optimal. If we change the unit costs of links 3 and 4 to M, where M is a large number (M » 1), then the optimal solution of FTOP will change. The optimal cost will increase to C = 4 and the optimal tunnel capacities will be as follows:

x 0 0 0 0 11 = 2, x 12 = 0, x 21 = 2, x 22 = 0 y 0 0 0 0 1 = 2, y 2 = 2, y 3 = 0, y 4 = 0 x 1 1 1 1 11 = 1, x 12 = 0, x 21 = 1, x 22 = 0 x 2 2 2 2 11 = 1, x 12 = 0, x 21 = 1, x 22 = 1 1 ≤ x 3 ≤ 2, x 3 = 0, 1 ≤ x 3 ≤ 2, x 3 = 0.

Complexity of FTOP and global rerouting

In the sequel, by FTOP we will always mean the instances of problem (4.1) with the full sets of admissible paths ˆ , i.e., P( ˆ ). (Instances of P(P ) with P restricted sets of admissible paths P Ç ˆ P will be denoted by FTOP < .) We note that problem FTOP is N P -hard (already for a polynomial number of states) since it contains, as a special case, the corresponding PD optimization problem whose N P -hardness was proven by [START_REF] Tomaszewski | On the complexity of resilient network design[END_REF] Difficulty of FTOP stems from the thinning constraint (4.1e) which introduces dependence between the nominal flows and the state-dependent flows. In fact, when constraints (4.1e), together with the associated nominal path-flow variables x 0 and constraints (4.1b), are deleted from formulation (4.1), then the resulting optimization problem becomes polynomial and corresponds to the so called global rerouting (GR) flow restoration strategy, also referred to as unrestricted flow reconfiguration or dynamic routing, see (Pióro and Medhi 2004b), [START_REF] Orlowski | Complexity of column generation in network design with path-based survivability mechanisms[END_REF]. In GR, the flows x s realizing the demands in different states are independent of each other and are only coupled by the capacity constraints (4.1d). This can be interpreted as if for each state s ∈ S the flows x s were established from scratch in the currently available capacity α s y e , e ∈ E . We note that the resulting GR optimization problem (4.1a), (4.1c), (4.1d) is polynomial also for the full set of admissible paths ˆ , as, because of the independence of flow variables x s , s ∈ S , it can be easily formulated as a compact linear program using the node-link notation. GR is the most flexible protection mechanism we can think of and therefore it provides a lower bound for the network cost (4.1a). Yet, for the network considered in Example 4.2, the optimal FTOP solution happens to be optimal for GR as well.

A natural extension of FTOP that allows for limited tunnel thickening is discussed in Chapter 6.

Dual problem and dual separation

In this section we will formulate the problem dual to the primal problem P FT (P ) defined by (4.1) and discuss the separation problem corresponding to the dual polyhedron.

Dual problem formulation

Problem D FT (P ) dual to P FT (P ) for a given set of admissible paths P is as follows (for derivation see Pióro and Medhi (2004b)): D FT (P ):

W (P ) = max ∑ ∑ h s λ s (4.2a) d d d∈D s∈S π 0 α s s e + ∑ s∈S e
e π e ≤ ξ e , e ∈ E (4.2b)

d p ≤ ∑ δ ed p π 0 , d ∈ D, p ∈ P d (4.2c) s∈S λ s e∈E s δ π s d ≤ σ d p + ∑
n n = |E | + ∑ e∈E |S e | + |D| • |S |, is defined as Ω(P ) := {(π, λ) ∈ R : ∃ σ ∈ R Nn , (π, λ, σ) ∈ Π(P )}.
Polyhedron Ω(P ) is also fully dimensional. Assume that the linear program P FT (P ), where P ⊆ ˆ , formulated in (4.1) is feasible. Then, due to the strong duality property [START_REF] Lasdon | Optimization Theory for Large Systems[END_REF][START_REF] Minoux | Mathematical Programming: Theory and Algorithms[END_REF], the optimal objective W (P ) of the corresponding dual problem D(P ) formulated in (4.2) is equal to the optimal primal objective C(P ) of P FT (P ), i.e., W (P ) = C(P ). Moreover, P ⊆ ˆ implies that polyhedron Π(P ) contains polyhedron Π( ˆ ), Π(P ) ⊇ Π( ˆ ), so that W (P ) ≥ W ( ˆ ) P P P and hence W (P ) is actually an upper bound on the optimal objective C( ˆ ) of P FT ( ˆ ), i.e., of FTOP.

Certainly, problem D DP ( ˆ ) represented by formulation (4.2) is N Phard since it is an LP dual of an N P -hard LP problem P PD ( ˆ ) represented by formulation (4.1).

Dual separation

In the sequel, the dual polyhedrons of FTOP, i.e., Π( ˆ ) and Ω( ˆ ), will be P P simply denoted by Π and Ω, respectively. The dual separation problem for FTOP is the separation problem for polyhedron Ω formulated as follows (see [START_REF] Grotschel | Geometric Algorithms and Combinatorial Optimization[END_REF], [START_REF] Nemhauser | Integer and Combinatorial Optimization[END_REF]):

Dual separation problem (DSP): Given an arbitrary vector (π, λ) ∈ R n , determine whether (π, λ) ∈ Ω, and if not, find a hyperplane in R n that separates (π, λ) from the polyhedron Ω.

Let us first notice that if (π, λ) ∈ / n then it is separated from Ω trivially, by one of the nonnegativity inequalities in (4.2e). Hence, we can assume that (π, λ) ∈ R n . Then, it is easy to check whether π fulfills all constraints in (4.2b). If it does not, then (π, λ) is separated from Ω by one of the unfulfilled inequalities in (4.2b), i.e., by one of the hyperplanes π 0 s s e + ∑ s∈S e α e π e = ξ e .

So now we can assume that (π, λ) ∈ R n and π is feasible with respect to (4.2b). Under this assumption (π, λ) ∈ / Ω if, and only if, there exists a demand d ∈ D and a path q ∈ ˆ such that for any σ s ≥ 0, s ∈ S , (π, λ) does not fulfill constraints (4.2c) or (4.2d) for path q. Before formulating a condition for such a path q (in Proposition 1), we introduce the following useful definitions.

For a given path q ∈ ˆ , the quantity |q| 0 := ∑ e δ edq π 0 is called the nominal dual length of q, while the quantities |q| s := ∑ e ∈E s δ edq π s , s ∈ S , are called the state-dependent dual lengths of path q, where as before, δ edq , e ∈ E , are the link-path incidence coefficients characterizing path q. Note that, by definition, E s ∩ q = ∅ implies |q| s = 0, and in particular |q| s = 0 for all q ∈ ˆ and s ∈ S 0 . With these two notions we can rewrite Now we can define the total dual length of path q ∈ ˆ , a crucial quantity specified for a given vector (π, λ) ∈ R n :

∑ (λ s | q| s ) ≤ σ s ≤ dq σ s ≤ |q| 0 < (λ s |q| s ). d s∈S q (π,λ) s∈S q (π,λ) s∈S s∈S q (π,
q) := |q| 0 + ∑ s∈S q (π,λ) (|q| s λ s ), (4.4)
where

S q (π, λ) := {s ∈ S : |q| s < λ s }. (4.5)
Proposition 1 Consider a given vector (π, λ) ∈ R n with π fulfilling constraints (4.2b). Then (π, λ) ∈ / Ω if, and only if, there exists a demand d ∈ D and a path q ∈ ˆ such that q) < 0. (4.6)

If this is the case, the inequality reverse to (4.6), that is,

∑ δ edq π 0 ∑ ∑ edq e d e∈E e + s∈S q (π,λ) ( δ e∈E s π s λ s ) ≥ 0, (4.7)
is not fulfilled by (π, λ) and thus the hyperplane ∑ e δ π 0 + s s ∑ s∈S q (π,λ) ( ∑ e∈E s δ edq π e λ d ) = 0 separates (π, λ) from Ω.

Proof 4.1

The proof of Proposition 1 is as follows. Consider vector (π, λ) ∈ R n with π fulfilling constraints (4.2b) and a given path q ∈ ˆ . We will show that system of inequalities (4.3) is infeasible if, and only if, inequality (4.6) holds.

Clearly, this implies that (4.7) separates (π, λ) from Ω. Suppose q) ≥ 0, that is, |q| 0 ≥ ∑ s ∈S q (π,λ) (λ s |q| s ). Then, obviously,

( λ s s dq := d |q| , if s ∈ S q (π, λ) (4.8) 0, if s ∈ S \ S q (π, λ) (σ s , λ s ) is a feasible solution of the system of inequalities (4.3). Now suppose dq d q) < 0, that is, ∑ s∈S q (π,λ) (λ s |q| s ) > |q| 0 . (4.9)
Then, assuming feasibility of (4.3), due to (4.5), (4.3b), (4.3c), (4.3a), and (4.9), respectively, the following sequence of inequalities must hold:

0 ≤ d ∑ ∑ dq ∑ (4.
10) This is a contradiction since in (4.10) the second term is strictly less that the last term but they are identical. Thus, system (4.3) is infeasible. (4.2b), and (iii) for each d ∈ D, q ∈ ˆ , the total dual length of q with respect to (π, λ) is nonnegative, i.e., q) ≥ 0. The last condition, however, cannot be used as an inequality characterizing polyhedron Ω since its form (4.7) depends on a particular vector (π, λ) through S q (π, λ). Still, it directly implies such inequalities.

+ P d q ∈ + + P ˆP P d Proposition 1 states that (π, λ) ∈ Ω if, and only if, (i) (π, λ) ∈ R n , (ii) π fulfills
The explicit characterization of the projected polyhedron Ω is as follows:

π 0 α s s e + ∑ s∈S e e π e ≤ ξ e , e ∈ E (4.11a) e ≥ (λ s δ π s ), d ∈ D, p ∈ ˆ , S t ⊆ S (4.11b) ∑ δ ed p π 0 e∈E ∑ d s∈S t ∑ e∈E s ed p e P d π ≥ 0, λ ≥ 0. (4.11c)
The above characterization follows from the fact that for a fixed path ˆ , the quantity on the right hand side of (4.11b) computed for any given (π, λ) ∈ R n attains its maximum for S t = S q (π, λ). This means that 4.7), dominates for the given path, the proper inequality, i.e., inequality ( the remaining inequalities in (4.11b) for each (π, λ) ∈ R n . Clearly, characterization (4.11) can be easily obtained with Fourier-Motzkin elimination (see [START_REF] Motzkin | Two consequences of the transposition theorem on linear inequalities[END_REF]).

Finally, we observe that by equivalence of optimization and separation in linear programming, see (Grotschel et al. 1988, Nemhauser and[START_REF] Nemhauser | Integer and Combinatorial Optimization[END_REF], DSP is N P -hard since problem D( ˆ ) specified in (4.2) is N P -hard as a problem dual to FTOP which is N P -hard (already for polynomially bounded number of states |S |, see Section 4.2.3). This fact is reflected by the difficulty of finding a path q violating inequality (4.7). We will come back to the complexity issues related to FTOP and DSP in Section 4.5.

Path generation

The link-path LP formulation (4.1) of FTOP is non-compact because of the presence of exponentially many path-flow variables x (and, as a matter of fact, of exponentially many constraints (4.1e)) corresponding to all possible elementary paths included in the maximum admissible path-list P . The formulation is potentially non-compact also because of possibly exponential number of states in the set S (since the number of all link availability coefficient vectors is in general exponential, equal to K |E | when each link has K levels of availability). To avoid such an additional intrinsic hardness of the problem, we assume that |S | is polynomially bounded by the number of links.

Thus, in practice, formulation (4.1) of FTOP cannot be solved directly, as we are virtually not able to include all elementary routing paths in the path-lists. In order to consider all paths in ˆ , we need to apply path generation (PG), see [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF]))-a classical technique in multicommodity flow networks related to column generation in linear programming, cf. [START_REF] Lasdon | Optimization Theory for Large Systems[END_REF][START_REF] Minoux | Mathematical Programming: Theory and Algorithms[END_REF]). With PG, starting from some initial path-lists P d , d ∈ D, we iteratively generate new paths, one per demand, and add those paths that may improve the solution to the path-lists-in effect, we + ˆPd

P d P d + d e d e P d
are adding the corresponding path-flow variables to the problem formulation. As discussed below, this is done by solving an appropriate pricing problem using, as parameters, optimal dual variables, i.e., an optimal solution (λ * , π * ) of the current problem D FT (P ) dual to P FT (P ). The application of PG to FTOP is explained below.

Pricing problem

PG is based on the so called pricing problem (PP). In essence, PP is similar to DSP (in the sequel, by DSP we will mean its version implied by Proposition 1), but with two main differences:

• the point to be separated from polyhedron Ω is not just any vector (π, λ) ∈ R n with π fulfilling (4.2b), but one of the optimal solutions ) for some P ⊆ ˆ D FT P

• in PP we need to find, for each d ∈ D, not just a path (if any) in P d which separates the current optimal dual solution (π, λ) of D(P ), but rather a path q ∈ ˆ \ P d for which the constraints of Ω corresponding to the given d and q are most violated by (π, λ). In the sequel, the problem of finding such a path, i.e., PP for this setting, will be denoted by PP(P , π, λ, d).

In fact, the second property does not necessarily have to be obeyed in PG since any path q ∈ ˆ that violates at least one of the constraints (4.7) provides a cut that decreases, in a valid way, the current polyhedron Ω(P ). Still, the use of the most violated cuts implied by the second property can substantially speed up the path generation process, especially when finding the most violated cut is not substantially more time consuming than finding an arbitrary cut.

Consider a given dual optimal solution (π, λ) of D FT (P ) and a given path q ∈ ˆ for some d ∈ D. Let D(q) denote the degree of violation of constraints (4.7) (for the considered d and q) by vector (π, λ). Proposition 2 D FT (q) = max{ q), 0}.

Proof 4.2

The proof of Proposition 2 is as follows. Since (π, λ) is a solution of D(P ), (π, λ) ∈ R n and hence, as already noticed when introducing characterization (4.11) of the projected dual polyhedron Ω, the equality

∑ s∈S q (π,λ) (λ s ∑ e∈E s δ edq π s ) = max { ∑ s∈S t (λ s ∑ e∈E s δ edq π s ) : S t ⊆ S } (4.12)
holds. Assume that for some S t ⊆ S , the corresponding constraint (4.11b) is

0 s s broken, i.e., ∑ e∈E δ edq π e < ∑ s∈S t (λ d ∑ e∈E s δ edq π e ).
Then, due to (4.12), also

0 s s the constraint ∑ e∈E δ edq π e < ∑ s∈S q (π,λ) (λ d ∑ e∈E s δ edq π e
) is broken, and, for the same reason, the degree of violation of the latter constraint, i.e., D(q) = s s 0

∑ s∈S q (π,λ) (λ d ∑ e∈E s δ edq π e ) ∑ e∈E δ edq π e = q)
is the largest among all the constraints (4.11b) corresponding to path q.

Certainly, Proposition 2 is not surprising as it implies that the pricing problem PP(P , π, λ, d) is equivalent to minimize q) over q ∈ ˆ , i.e., to finding the most violated separating inequality (4.7). Clearly, when the solution q) of (4.13) is negative, then for a given d ∈ D q ∈ / P d and D FT (q) = q) is the largest degree of violation of constraints (4.7) by (π, λ) corresponding to a given d ∈ D.

Finally, let us note that the dual separation problem and the pricing problem are similar in that in both DSP and PP we need to find a path with a negative total dual length q).

Binary formulation of PP

The pricing problem formulated in (4.13) is difficult because of the particular form of the total dual length q). Nevertheless, the problem can be stated as a binary programming problem by means of formulation (4.14) given below. In the formulation, binary variables u e , e ∈ E , specify the path q ∈ ˆ we are looking for: q = {e ∈ E : u e = 1}. Binary variables z s , s ∈ S , in turn, identify the set S q (π, λ) corresponding to the so defined path q: S q (π, λ) = {s ∈ S : z s = 1}. Besides, δ + (v) and δ (v) denote the sets of all links outgoing from, and all links incoming to node v ∈ V , respectively. Also, o(d) is the originating node of the considered demand d ∈ D and t(d) is its terminating node. , s ∈ S , to be equal to 1 when the length, with respect to π s , of the path q defined by variables u is sharply smaller than λ s . Assume (for a while) that z s = 0 when the length, with respect to π s , of path q is greater than or equal to λ s . Then it is clear that the objective function computes the total dual length of path q, i.e., q) = |q| 0 + ∑ s ∈S q (π,λ) (|q| s λ s ) (see definition (4.4)). But this assumption will be fulfilled by any optimal solution of (4.14)-this is easily seen from the equivalent form of the objective function

min L = ∑ (π 0 + e∈E ∑ s∈S e π s z s )u e ∑ s∈S λ s z s (4.14a) ∑ e∈δ + (o(d)) u e ∑ e∈δ (o(d)) u e = 1 (4.14b) ∑ e∈δ + (v) u e ∑ e∈δ (v) u e = 0, v ∈ V \ {o(d), t(d)} (4.14c) λ s s s s d z ≥ λ d ∑ π e u e ,
L = ∑ π 0 u e + ( π s u e λ s )z s , (4.15) e e∈E ∑ s∈S ∑ e d e∈E s
which, when minimized, will set z s to 0 whenever |q| s = ∑ e π s u e > λ s .

∈E s e d

Hence, an optimal solution u, z, L of (4.14) defines an optimal path q := {e ∈ E : u e = 1}, with L = |q| 0 + ∑ s total dual length q). ∈S q (π,λ) (|q s | λ s ) equal to its To get rid of bi-linearities z s • u e in the objective function, we can introduce binary variables Z s , e ∈ E , s ∈ S , rewrite objective as

L = ∑ π 0 u e + π s Z s λ s z s , ( 4

PG algorithm

The algorithm for solving FTOP by path generation is as follows.

Algorithm 3: PG algorithm for Global Rerouting

Input: Graph G = (V , E ), a set of demands D, a vector of traffic requirements h s , s ∈ S U S 0 .

Output: Subset of paths P ⊆ ˆ leading to optimal cost C P ). If optimal L is negative Then 8:

Add the resulting path q to the path-list P d 9:

End If 10:

End for 11: Until no path has been added

When the algorithm stops, after M iterations, say, it results in a sequence of dual polyhedrons Π(P 0 ) ⊃ Π(P 1 ) ⊃ . . . ⊃ Π(P M ), where the inclusions are proper. The corresponding optimal dual objective values are decreasing, W (P 0 ) ≥ W (P 1 ) ≥ . . . ≥ W (P M ), and W (P M ) = W ( ˆ ) = C( ˆ ). P P Assume that the set S 0 of maximum availability states is not empty. If there exists a path q ∈ ˆ with |q| 0 < ∑ s ∈S 0 λ s , then q) ≤ |q| 0 ∈S 0 λ d < 0 (because |q| = 0 for all s ∈ S 0 ). Hence, for any such path q the degree of violation D(q) is greater than or equal to ∑ s λ s |q| 0 > 0. Thus, while the pricing problem (finding a path q with minimum q)) is in general N P -hard (see Section 4.5), finding a path q with minimum |q| 0 is obviously polynomial. Hence, we may speed up the PG process: in Step 2 for each d ∈ D we find a path q ∈ ˆ with minimum |q| 0 , and if |q| 0 < ∑ s ∈S 0 λ s , then we add path q to the problem and skip solving PP (P , π, λ, d) for the current d. Certainly, the overall time efficiency of this modification is in general hard to assess since there is a tradeoff between the value of D(q) (the larger the better) and the time spent in Step 2. An illustration of the above considerations is given in Example 4.4). The corresponding optimal solution of the dual problem D(P ) (see (4.2)) is in turn given by:

π 1 2 0 0 1 2 1 = π 2 = 2, π 3 = π 4 = 1, λ 1 = λ 2 = 2, W = 4,
and all other dual variables π 0 , π 0 , λ 2 , λ 1 , λ 3 , λ 3 , σ s , s ∈ S , d ∈ D, equal to 0.

Computational complexity of PP, DSP, and special cases

Although not shown guaranteed, the iterative PG process described in Section 4.4.3 will typically terminate in a polynomial number of steps, as it is closely related to the revised simplex method [START_REF] Lasdon | Optimization Theory for Large Systems[END_REF][START_REF] Minoux | Mathematical Programming: Theory and Algorithms[END_REF], an exponential algorithm which exhibits this desirable property in practical applications. Indeed, consider a path q ∈ ˆ \ P d that solves PP(P , π, λ, d) for d ∈ D. The variables x 0 and x s , s ∈ S , are by assumption non-basic as they are not seen in formulation (4.1) of P(P ), and the maximum degree of constraint violation D(q) is equal to the sum of the reduced cost of variable x 0 and of the reduced costs of those variables among x s , s ∈ S , that have the negative reduced cost. Thus, the computational complexity of the PG algorithm is in practice determined by the complexity of the pricing problem PP.

Let us consider the special case of state scenarios containing only partial failures of single links. Hence, S = S 0 ∪ S 1 , where S 0 is a set of maximum states (recall that in a maximum state, all links maintain full availability), and S 1 := U e∈E S (e) is a set of single-link partial availability states. Each set S (e) represents a set of states in which only link e has the reduced capacity, i.e., s ∈ S (e) implies α s < 1 and α s = 1, e t ∈ E \ {e}. Note that if link e is assumed to be perfectly reliable then the set S (e) is empty. It turns out that in the considered case the pricing problem is polynomial.

Lemma 3 Consider a given single-link failure scenario S and a fixed demand d ∈ D. The total dual length of any path q ∈ ˆ is given by the formula The proof of this lemma is presented in 4.6.2 Since the term ∑ s∈S λ d in (4.18) is constant, solving PP is equivalent to finding a shortest path with respect to the link weights ω(e), e ∈ E , e.g., by the Dijkstra algorithm. Hence, PP is polynomial (provided that the number of states in S is polynomial-note that this is the case for a finite number K of link availability levels).

q) = ∑ ω(e) ∑ λ
The same argument shows that DSP (the dual separation problem), and hence the dual to FTOP, and thus FTOP, are polynomial as well. Moreover, the way dual is solved by the ellipsoidal method of [START_REF] Khachian | A polynomial algorithm for linear programming[END_REF] (implied by Proposition 1, i.e., by finding successive paths that separate the current dual solution) gives a polynomial set of paths required to solve FTOP. Besides, since FTOP is polynomial, we may expect that it can be solved with a compact node-link linear program-such an LP formulation is given in the following section (Section 4.6.1).

The above weight construction applies to undirected networks as well. Also, the compact FTOP formulation (4.37) can be easily modified for the undirected links case. Besides, as shown in Section 4.7, the single-node failure scenarios can be treated by polynomial algorithms in a way analogous to the single-link case.

As already mentioned at the end of Section 4.3.2, the dual separation problem is N P -hard for the general case of a state scenario with polynomially bounded size. Moreover, DSP is N P -hard already for partial double-link failures, i.e., when any two links can fail simultaneously. This was demonstrated by [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF] (see also [START_REF] Orlowski | Complexity of column generation in network design with path-based survivability mechanisms[END_REF]) for a PD problem formulation analogous to (4.1). Thus the pricing problem (4.13) is most likely N P -hard in those cases as well, as it is very similar to DSP. min C = ∑ ξ e y 0 (4.20a) Note that possible loops in the optimal solutions can be eliminated as their capacity is not used by the state-dependent path-flows x s , p ∈ P d , s ∈ S , realizing the demand volume h s defined by (4.21). Since, as discussed Section 4.2.2, FTOP (4.1) does not require non-elementary paths (and thus loops in the link-flows), formulation (4.20) is correct. In fact, when all link unit capacity costs ξ e , e ∈ E , are strictly positive, the loops will not appear in the optimal solutions of (4.20).

e∈E ∑ x 0 x 0 0 e∈δ + (o(d)) ed ∑ e∈δ (o(d)) ed = X d , d ∈ D (4.20b) ∑ e∈δ + (v) ∑ x 0 ed ∑ e∈δ (v) 0 ed = 0, d ∈ D, v ∈ V \ {o(d), t(d)} (4.20c) d∈D X 0 ed ≤ y e , e ∈ E (4.20d) s d ≥ h d , d ∈ D, s ∈ S 0 (4.20e) X 0 s s d z ed ≥ h d , d ∈ D, e ∈ E , s ∈ S (e) (4.20f) ∑ (x 0 z s ) ≤ α s y 0 , e ∈ E , s ∈ S (e)
It is interesting to note that for the single-link failure scenarios the LBP formulation (5.1) remains to be only a lower bound for the exact formulation (4.20). In fact, when an optimal solution x 0 , x s , s ∈ S , y 0 of (5.1) does not contain loops in the flow x 0 then the optimal values of (5.1) determine the corresponding feasible solution x 0 , z s , s ∈ S , y 0 of (4.20) with the same x 0 , y 0 and z s := x 0 x s , d ∈ D, e ∈ E , s ∈ S (e). In this case, as LBP is a lower bound for FTOP, its optimum is at the same time the optimum for FTOP. However, if the link-flow x 0 contains loops, then the solution C t of LBP can be strictly smaller than the optimal solution C of FTOP, as illustrated in Example 4.5 below. This is because no counterpart of constraint (4.20f) is present in (5.1) and hence we may thin the loops without thinning the realized overall demand volume X 0 .

Example 4.5 Consider the network depicted in Figure 4.6. There is one demand (from o to t)

and two states, s = 1 and s = 2, with link 1 and link 2 failing, respectively. In both states the failing link has the same availability coefficient α, and the demand volume to be realized is equal to h. The unit link costs are as follows:

ξ 1 = ξ 2 = ξ 3 = 1, ξ 4 = M, where M » 1.
In the considered cost setting with ξ 4 » 1, optimal solutions of (4.20) (and hence of FTOP) are induced by the nominal path/loop-flows of the form: x 0 = f (on the upper path (o, v, t)), x 0 = f (on the lower path (o, v, t)), x 0 = 0 (on the 2 3 upper loop (o, v, o)), x 0 = 0 (on the lower loop (o, v, o)). There are two cases to consider. Case 1: 0 ≤ α < 1 . The optimal solutions is given by f = h and y 0 =

h h 1 M 2 Mh 2h(M+1) 1+ 1+α +α , 1+α , 0, 1+α ). Hence, C = α . 0 Case 2: 1 ≤ α ≤ 1.
One of the optimal solutions, a symmetric one, is given by f = h and y 0 = ( h , h , 0, h). Hence, C = h + Mh. 0

2α 2α α

The optimal solution of LBP (5.1), in turn, is induced by the two nominal path-flows equal to h , and by the two nominal loop-flows equal to ( 1

2 1 (1α)h 1+α 0
2 )h = 2(1+α) . Then the corresponding nominal link-flows are equal to x = ( 1

h h (1α)h t (3α)h 1+
+α , 1+α , 1+α , h), and the resulting cost is equal to C = α + Mh. In the availability state s = 1, the link-flows become equal to x 1 = ( αh , h , 0, h), 1+α 1+α

and in s = 2, the link-flows are symmetric and equal to x 2 = ( 1 h , αh , 0, h). Certainly, for M » 1, the LBP cost C t will be strictly smaller that the FTOP cost C.

Example EC.4 shows that loops can be necessary in the LBP optimum so in general they cannot be removed without an impact on the optimal Intuitively, the inclusion of loops in LBP allows for (implicit) "forced thinning" of the flows from origin to destination that otherwise would not traverse the failed links. We observe that in the considered example the loops (o, v, o) could be eliminated by putting (5.1). Yet, this does not help much as in the general case loops will appear anyhow, only they will not involve the demands' origins and destinations.

x 0 = 0, d ∈ D, e ∈ δ (o(d)) ∪ δ + (t(d)), and x s = 0, s ∈ S , d ∈ D, e ∈ δ (o(d)) ∪ δ + (t(d)), in
In the case of undirected links the situation ia analogous to the directed case. The standard counterpart of formulation (4.20) for the undirected links (with two oppositely directed link-flows corresponding to each undirected link) remains correct, and the LBP formulation modified for undirected links is still not equivalent to the modified formulation (4.20).

Single-link failures -proof of Lemma 3

First, we observe that the total dual length of path q ∈ ˆ defined by (4.4) can be (in fact also in the general case of S ) equivalently expressed as

q) = (|q| 0 + ∑ \ql s ) ∑ λ s , (4.22) s∈S s∈S
where the modified dual length \ql s of path q in state s ∈ S is defined as

( |q| s , if |q| s ≤ λ s \ql s := d (4.23) d , otherwise.
Since for the considered states s ∈ S , the state-dependent dual length of a path q can take only two values: ( 0, if s ∈ S 0 , or s ∈ S (e) and e ∈ / q |q| s = e , if s ∈ S (e) and e ∈ q (4.24)

the modified dual path lengths are equal to:

\ql s = 0, if s ∈ S 0 , or s ∈ S (e
) and e ∈ / q π s , if s ∈ S (e) and e ∈ q and π s ≤ λ s where the quantity on the left-hand side is equal the length of path q with respect to the link weights defined by (4.26) (and (4.19)). Hence, by (4.22) we finally obtain the equality ∑ ω(e) = q) + ∑ λ s , Graph ˆ (d) is defined by the following conditions: where the (non-negative) link weights ω(e ˆ) are defined for each link e ˆ in ˆ(d) as follows:

ˆ ˆ V (d) := {v ˆ(e) : e ∈ E } ∪ {o(d), t(d)}; (v ˆ(e), v ˆ( f )) ∈ E (d) ⇔ ∃v ∈ V \ {o(d), t(d)}, e ∈ δ (v) ∧ f ∈ δ + (v); (o(d), v ˆ( f )) ∈ ˆ(d), f ∈ δ + (o(d)); (v ˆ(e), t(d)) ∈ ˆ(d), e ∈ δ (t(d)). E E In graph ˆ (d), all links of the form (v ˆ(e), v ˆ( f )), where e ∈ δ (v), f ∈ δ + (v) for a given (original) node v ∈ V \ {o(d), t(d)},
ω(v ˆ(e), v ˆ( f )) := π 0 + f ∑ s∈S (v) min{π s + π s , λ s }, e f d v ∈ V \ {o(d), t(d)}, e ∈ δ (v), f ∈ δ + (v) (4.30a) ω(o(d), v ˆ( f )) := π 0 + min{π s , λ s }, f ∈ δ + (o(d)) (4.30b) f ∑ f d s∈S (o(d)) ω(v ˆ(e), t(d)) := ∑ min{π s , λ s }, e ∈ δ (t(d)). (4.30c) e d s∈S (t(d))
As in the proof of Lemma 3 (see (4.22)), the total dual length of path ˆ defined by (4.4) can be expressed as:

q) = (|q| 0 + ∑ \ql s ) ∑ λ s . (4.31) s∈S s∈S
In the considered case, for a given path q ∈ ˆ , its dual lengths in the considered states s ∈ S can take one of the three values:

|q| s = 0, if s ∈ S 0 , or s ∈ S (v) and q ∩ δ(v) = ∅ π s , if s ∈ S (v) and q ∩ δ(v) = {e} (4.32) π s s t tt e t + π e tt , if s ∈ S (v) and q ∩ δ(v) = {e , e }. and π + π λ G V ˆG E d G f
Thus, the modified dual lengths, defined in (4.23), are as follows:

0, if s ∈ S 0 , or s ∈ S (v) and q ∩ δ(v) = ∅ s s(v) s(v) \ql s = π e , if s ∈ S (v) and q ∩ δ(v) = {e} and π e ≤ λ d λ s , if s ∈ S (v) and q ∩ δ(v) = {e} and π s(v) > λ s(v) d e d π s + π s , if s ∈ S (v) and q ∩ δ(v) = {e t , e tt s(v) s(v) s(v)
} ≤

ω(v ˆ(e), v ˆ( f )) := π 0 + min{π s + π s , λ s }, v ∈ V \ {o(d), t(d)}, e ∈ δ (v), f ∈ δ + (v) f ∑ s∈S (v) e f d (4.34a) ω(o(d), v ˆ( f )) := π 0 + min{π s , λ s }, f ∈ δ + (o(d)) (4.34b) f ∑ f d s∈S (o(d)) ω(v ˆ(e), t(d)) := ∑ min{π s , λ s }, e ∈ δ (t(d)) (4.34c) e d s∈S (t(d))
and consider a path q ˆ = (o(d), v ˆ(e 1 ), v ˆ(e 2 ), . . . , v ˆ(e n ), t(d)). We observe that the length ∑ e ˆ∈q ˆ ω(e ˆ) of path qˆ with respect to the link weights (4.34) obeys the equality

∑ ω(e ˆ) = |q| 0 + ∑ \ql s (4.35) e ˆ∈q ˆ s∈S
where q = (e 1 , e 2 , . . . , e n ) is the path in graph G corresponding to qˆ. Hence,

∑ ω(e ˆ) = q) + ∑ λ s , (4.36) e ˆ∈q ˆ
which is equivalent to (4.29).

s∈S

In consequence, and due to the one-to-one correspondence of the paths in the original graph and the transformed graph, the pricing problem in the considered case of single-node failures can be solved by a shortest path algorithm applied to graph ˆ.

The above construction can be applied, after a slight modification, to undirected graphs. In the undirected case we first define the transformed graph as an undirect graph, similarly as in the directed case. Then we transform it to a bi-directed graph, with two oppositely directed arcs corresponding to each undirected link. The two arcs in each such pair are assigned non-symmetric arc weights, differing in the π 0 value that is determined by the direction of the arc (see definition (4.30a)). In this case we just skip the directions of links in the definition of the new graph and adopt the following definition:

V := {v ˆ(e) : e ∈ E } ∪ {o(d), t(d)} ∃v ∈ V , e, f ∈ δ(v) ⇒ {v ˆ(e), v ˆ( f )} ∈ ˆ(d) {o(d), v ˆ( f )} ∈ ˆ(d), f ∈ δ(o(d)) {v ˆ(e), t(d)} ∈ ˆ(d), e ∈ δ(t(d)).
Since the term ∑ s λ s in (4.18) is constant, solving PP is equivalent to finding a shortest path in the transformed graph with respect to the link weights ω(e ˆ), e ˆ ∈ ˆ. Hence, PP is polynomial, and so is FTOP. A compact LP formulation for the considered case of FTOP is given in Section 4.7.2. The values of transit variables w v can be used to define the overall flow on the paths p ∈ ˆ traversing a transit node v of a demand d ∈ D containing two particular links e and e + , where e ∈ δ (v) and e + ∈ δ + (v). When node v fails, the flows on these paths can be consistently thinned using the value of z s instead of z s in a formula analogous to (4.21). A similar observation applies to variables Z.

Single-node failures -compact FTOP formulation

For a fixed d ∈ D, an elementary path-flow pattern x 0 > 0, p ∈ P d (for some P d ⊆ P d ), that realizes the link-flows x 0 , e ∈ E , and is consistent with the values of variables w can be found recursively as follows. Initially, we set P d equal to ∅, and find a (elementary) path q = (v 0 , e 1 , v 1 , e 2 , . . . , e n1 , v n1 , e n , v n ) in ˆ , where v 0 = o(d) and v n = t(d), such that the values of all variables to P d , and repeat the procedure until no such path q for d can be found. This observation justifies the correctness of formulation (4.37).

x 0 v 1 v 2 v n1 0 e 1 d ,
min C = ∑ ξ e y 0 (4.37a)

e∈E ∑ x 0 x 0 0 e∈δ + (o(d)) ed ∑ e∈δ (o(d)) ed = X d , d ∈ D (4.37b) ∑ e∈δ + (v) ∑ x 0 ed ∑ e∈δ (v) 0 ed = 0, d ∈ D, v ∈ V \ {o(d), t(d)} (4.37c) d∈D X 0 ed ≤ y e , e ∈ E (4.37d) s d ≥ h d , d ∈ D, s ∈ S o (4.37e) ∑ w v 0 + e ∈δ (v) e ed = x ed , d ∈ D, v ∈ V \ {o(d), t(d)}, e ∈ δ (v) (4.37f) ∑ w v 0 e + ∈δ + (v) z s ee + d = x ed , d ∈ D, v ∈ V \ {o(d), t(d)}, e ∈ δ v (v) (4.37g) e e + d ≤ w e e + d , d ∈ D, v ∈ V \ {o(d), t(d)}, e ∈ δ (v), e + ∈ δ + (v), s ∈ S (v) (4.37h) X 0 s s d ∑ ∑ z e e + d ≥ h d , d ∈ D, e ∈δ (v) e + ∈δ + (v) v ∈ V \ {o(d), t(d)}, s ∈ S (v) (4.37i) Z s 0 + ed ≤ x ed , d ∈ D, e ∈ δ (o(d)), s ∈ S (o(d)) (4.37j) X 0 Z s s d ∑ e∈δ + (o(d)) ed ≥ h d , d ∈ D, s ∈ S (o(d)) (4.37k) Z s 0 ed ≤ x ed , d ∈ D, e ∈ δ (t(d)), s ∈ S (t(d)) (4.37l) X 0 Z s s d ∑ e∈δ (t(d)) ed ≥ h d , d ∈ D, s ∈ S (t(d)) (4.37m) ∑ x 0 z s Z s s 0 ed ∑ ∑ e ed ∑ ed ≤ α e y e , d∈D d∈D(v) e ∈δ (v) d∈D + (v) v ∈ V , e ∈ δ + (v), s ∈ S (v) (4.37n) ∑ x 0 z s Z s s 0 ed ∑ ∑ ee + d ∑ ed ≤ α e y e , d∈D d∈D(v) e + ∈δ + (v) d∈D (v) v ∈ V , e ∈ δ (v), s ∈ S (v) (4.
37o) all variables x 0 , X 0 , w, z, Z, y 0 continuous and nonnegative. (4.37p) It turns out that the LBP formulation becomes exact when it has loopless optimal solutions and each node can fail at most once (i.e., |S (v)| ≤ 1, v ∈ V ). This is because only then any feasible loop-less solution of (5.1) determines a feasible solution of (4.37) with the same cost. (Note that this is true for an arbitrary single-link failure scenario.) For single-node failure scenarios admitting |S (v)| > 1 for some v ∈ V , the above observation is not true anymore because of constraint (4.37h) which implies that for each value of w v (for v, e , e + , d fixed) must be in this case an upper bound for the set of values z s , s ∈ S (v) with more than one element. This is illustrated by the following example. It is clear that in terms of link capacity the optimal solution of the lower bound formulation (5.1) is unique and symmetric. Hence, a simple cut-based argumentation implies that the common optimal value y 0 of the link capacity must fulfil the equality y 0 + αy 0 = h, that is, y 0 = h 1+α . The common value x 0 for the optimal nominal link-flows is equal to y 0 . In each state, the optimal link-flows on the links with reduced capacity are equal to hα , while on the fully available links-to 1 h . Hence, the optimal LBP objective function value is equal to C t = 4h . The optimal solution for FTOP is obtained by considering the two following cases. Case 1: 0 ≤ α < 1 . The optimal FTOP solution is as follows: f = h , y 0 = 2h 2 8h 1+4α

1+4α , C = 1+4α . All four nominal path-flows are equal to f . In each state s, the nominal flow f on the unaffected path p s is maintained, the flow on the path with both links affected is deleted (thinned to 0), and the flows on the two remaining paths are thinned from f to 2hα . 0 Case 2:

1 ≤ α ≤ 1.
The optimal FTOP solution is as follows:

f = h , y 0 = h 2 4h 2(1+α)
1+α , C = 1+α . In state s, the nominal flow f on the unaffected path p k is maintained, the flows on the two paths with only one link affected are also maintained, and the flow on the path with both links affected is thinned to h(2α1) . 0

Note that in Case 2 the optimal solutions of LBP and of FTOP have the same cost, i.e., C t = C. In Case 1, however, C t < C and CC t = 12α . For α = 0, the difference of the FTOP cost and the LBP cost constitutes 50% of the FTOP cost. For α = 1 , this value decreases to 20%. his chapter is devoted to numerical part. The purpose of our computational experiments is threefold. The first objective is to demonstrate the traffic efficiency of flow thinning. Our results from section 5.1 illustrate the efficiency of FTS by comparing the corresponding minimum capacity allocation costs for several strategies. Second, we assess the computational difficulty of FTOP. Hence, in section 5.2 we present the results of two sets of experiments which evaluate the computational efficiency of the path generation algorithm. Finally, since FTOP is N P -hard, we introduce a polynomial problem that provides a lower bound for its cost C( ˆ ) referred to as LBP. The results of LBP will be compared with FTOP, formulated in 4.1.

In this chapter, we present the results of our numerical study carried out for four realistic undirected network examples taken from the library of network instances SNDlib [START_REF] Orlowski | SNDlib 1.0survivable network design library[END_REF]): pdh, polska, nobel-us, and nobel-germany. Figure 5.1 represents the number of vertices, edges and demands of each networks, as well as the maximum and minimum degree of the corresponding graphs (∆(G), δ(G)). The demand matrices for those networks specified are taken as the nominal demand volumes in C GR our models. The study was carried out on a computer equipped with an Intel(R) Xeon(R) CPU E5-2670 @ 2.60GHz processor, and 132 GB of RAM, using CPLEX 12.5 (CPLEX 2013)

Cost efficiency of flow thinning

In this section, we compare the cost effectiveness of flow thinning and global rerouting. We first start by a short note on the typology of failures occurring frequently. Let us consider the example presented in Figure 5.1 representing rainfall in north-west of Poland a day of July 20151 .

[mm/h] 0 0.25 1 We can notice the following type of failure scenarios illustrated in the figure :   • single link failures

• single node failures

• double link failures (in close proximity) . . . In the sequel, these three failure scenarios will be studied and we will also present results for double link failures where the two links are randomly located (realistic for large scale network).

Let the quantity C GR denote the optimal cost for reliable networks under GR (recall that GR implies the cheapest networks and is thus taken as the reference value). The cost increases with respect to GR (in percents) for FTS is given by Ga p FTS := C FTS C G R × 100, where C FTS is the cost for the flow thinning strategy. Certainly, the computed link capacities (and thus the link capacity cost) ensure routing of all traffic demands in the d d

Relative gap

Relative gap nominal state and the guaranteed traffic restoration (specified by β) in all failure states. In the reported experiments, we always use the same traffic reduction ratio β = 1 for all demands in all failure states, i.e., h s = h 0 for all d ∈ D and s ∈ S .

Single partial link failure scenarios

In , for all four network instances, we present Ga p FTS as a function of the availability coefficient α assumed for the failure states. We here consider only single partial link failures, i.e. in a failure state one link can loose a percentage of its nominal capacity (1 α%) and all remaining links reach their nominal capacities. We consider 21 scenarios, varying α from 0% (nominal state) to 100% (total failure) with a step of 5%. Note that the dotted lines represents availability coefficient for which the relative gaps meet levels of 10%, 20%, 30%, 40% and 50%. These levels are used to compare the network instances. First, we note that for α = 0% FTS comes to be as path diversity. Considering single total link failure scenarios, PD can be considered as an upper bound of the cost of the network for all single partial link failure scenarios that can occur.

Second, let us analyze the performance of FTS. As shown in Figures rerouting and local rerouting is up to 30% for total failures. Hence, as local rerouting is used in MPLS Fast Reroute (described in section 2.2.3), let us consider a relative gap of 30% as acceptable for a recovery mechanism.

Let us track now when this value is achieved for two types of networks, meshed and sparse, respectively network pdh versus polska, nobel-us and nobel-germany. In one hand, the relative gap of 30% is met for α = 0.45 in pdh. Hence, FTS is of reasonable cost for light to moderate perturbations. On the other hand, considering sparse network, the relative gap of 30% is met for α = 0.25 up to α = 0.1. Thus, FTS can be considered cost-efficient even for strong perturbations in sparse networks. However, in both cases, strong perturbations (including total failure) cannot be managed by FTS with reasonable cost.

Single partial node failure scenarios

In , for all four network instances, we present Ga p FTS as a function of the availability coefficient α assumed for the failure states. We here consider only single partial node failures, i.e. in a failure state every link outcoming from or incoming to the failed node suffers a degradation of their capacities of 1 α% and all remaining links reach their nominal capacities. We consider 20 scenarios, varying α from 0% (nominal state) to 95%. Note that in this context, we cannot present results on total node failures as we require the traffic to be fully rerouted in case of failure. Note that even though the failure scenarios may appear stronger than single link failures due to the fact that many links fail in the same time, the computation time of FTOP is significantly decreased due to the reduction of the number of failure scenarios ISI and of the number of variables (lVI « lEI for all network instances). Considering single node failure scenarios, flow thinning is clearly a cast-efficient strategy with a relative gap to GR inferior to 20% for all a. Note that the relative gap for network pdh is equal to 0 for all values of oe.

Relative gap

Contrary to single link failure scenarios, this kind of scenarios can be managed by FTS with limited cost (Ga p FTS < 5%) for light perturbations but higher cost for relatively major perturbations. Note that the cost of FTS for moderate perturbations remains reasonable (< 17% for all networks). This is mostly due to the fact that we require to recover all demand traffic after a failure. In case of major perturbations, GR and FTS have the same behavior i.e. they use the shortest path to route the traffic and overdimension the network. However, for moderate perturbations, GR becomes more cost-efficient.

Double partial failure scenarios

In Figure 5.9, we present Ga p FTS as a function of the availability coefficient α assumed for failure scenarios corresponding to the failure of two simultaneous links close to each other. This proximity was determined as follows. Considering a planar graph (here polska), two link can fail in the same scenario only if an arc joining the two links can be drawn without cutting any other link. Hence, for network polska we will get 26 failure scenarios. Once again, note that in this context, we cannot present results on total node failures as we require the traffic to be fully rerouted in case of failure. 20% 15% 10% 5% 0% α 100% 90% 80% 70% 60% 50% 40% 30% 20% 10% Figure 5.9 -Relative gap between GR and FTS depending on the availability coefficient α for network polska (failures of two links in close proximity).

Next, Figure 5.10 represents the Ga p FTS as a function of the availability coefficient α for double links failures i.e. the set of all pair of links (including single link failures). Table 5.2 gives for polska the size of scenarios set with respect to four types of failure scenarios.

Notice that, considering network polska, the four failure scenarios presented are related to a growing number of failures illustrated in Table 5 considering failures of close links presented in Figure 5.9, FTS manages the failures with the same relative gap from α = 0.45 (moderate perturbation) to α = 0 (total failure). Summing up on the performance of flow thinning, FTS can be considered cost-efficient except for major single link failures as it always give a relative gap inferior to 30% for all network instances and all α. In the following section, we deal with the efficiency of the resolution algorithm for FTOP.

Computational efficiency of flow thinning optimization

Path generation

Recall that PG is the path generation algorithm for FTOP (i.e., problem (4.1) assuming the full set of admissible paths), based on the binary pricing problem (PP) formulation (4.14) (see Section 4.4.3), and that FTOP < denotes instances of (4.1) with limited sets of admissible paths. Below we report results illustrating the computational efficiency of solving FTOP through PG, and of solving FTOP < through a direct use of CPLEX for a predefined set of admissible paths. The PG algorithm was initialized by putting only one shortest (with respect to the unit capacity costs ξ e , e ∈ E ) path on the path-list of each demand. (Note that such minimal path-lists are sufficient for an optimal solution for FTOP involving only the nominal state, i.e., for FTOP with S = {s 0 }, and also for a feasible solution when links do not fail totally, i.e., when α s > 0, e ∈ E , s ∈ S .) For FTOP < , the predefined sets of admissible paths contain all elementary paths having up to 5 links.

For the reported experiments we assume a uniform availability coefficient α for all the affected links in each failure state, i.e., α s = α, s ∈ S , e ∈ E s (recall that E s denotes the subset of links affected by failure s), and α s = 1, s ∈ S , e ∈ E \ E s . Also, we use a uniform demand satisfaction coefficient β, i.e., h s = βh 0 , d ∈ D, s ∈ S \ {s 0 }. Tables 5.3 and 5.4 present results for three networks (pdh, polska and nobel-us) under the single-link failure scenario (SL) and the double-link failure scenario (DL). SL contains the nominal state plus one failure state for each link (with the assumed α for the failing link). DL contains SL plus one failure state for each pair of links (with the assumed α for both failing links). Each type of scenario is considered for the four pairs (α, β) specified by all four combinations of α ∈ {0.25, 0.5} and β ∈ {0.75, 1}.

The following quantities denote the running time (in seconds) observed in our experiments:

• t FTOP < -solving FTOP for the predefined set of admissible paths

• t GP -generating the predefined set of admissible paths (t FTOP < includes t GP )

• t FTOP -solving FTOP through PG

• t PP -solving the pricing problems (4.14) within the PG algorithm (t FTOP includes t PP ).

In addition, the quantity in brackets in column "network" gives the number of predefined paths (generated in time t GP ), column "#iter." gives the number of iterations of the PG algorithm, and column "#gen.paths" gives the number of paths generated by PG. We set the running time limit to 3 hours; the cases when the timeout had to be applied (this happened only for FTOP < ) are denoted by * . Note that the total number of paths for network pdh (resp. Tables 5.3 and 5.4 show that the relative efficiency of FTOP < and of FTOP is instance-dependent. Still, FTOP (i.e., the PG algorithm), despite the necessity of solving the binary PP subproblems, is faster than FTOP < (predefining the admissible set of paths plus application of the linear solver) for 18 out of 24 instances tested, including 4 instances (pdh for DL) for which FTOP could not solve the problem within the time limit. The results also show that a significant fraction of the PG algorithm execution time is spent in the pricing problem.

Evolution of the PG iterations

An important aspect of the PG algorithm is the number of added paths and the evolution of the network cost. after only a few (approximatively 7) PG iterations. Furthermore, the gap between the current solution and the optimal solution decreases drastically after only 1 or 2 PG iterations. Remind that the network instances are small networks and no conclusions can be drawn in general.

Running times

Our second set of experiments compares the running times and the network costs for the optimization problems corresponding to the two protection strategies considered in this paper, i.e., for FT and GR. The study is performed for the three networks pdf, polska and nobel-us with the predefined path-lists containing all paths up to 5 links. Thus, we study the following two variants of protection strategies and their related problems:

• FT (flow thinning): problem (4.1), i.e., FTOP We consider three kinds of state scenarios: single-link (SL), double-link (DL), and triple-link(TL). SL consists of the nominal state and failures of single links, DL contains SL plus failures of pairs of links, and scenario TL consist of DL and failures of triples of links.

Table 5.5 reports the running times in seconds, taking the averages of the times corresponding to the two cases of β = 1 and α = 0.5. We set the time limit to 10 hours-the cases when the timeout occurred are denoted by * . Table 5.5 reveals that the running times for the general flow thinning procedure (FT) are highly impacted by the number of the simultaneously failing links. In particular, all instances assuming TL could not be solved to optimality within the time limit.

A lower bound formulation

Since FTOP is N P -hard, it is worthwhile finding a polynomial problem that provides a lower bound for its cost C( ˆ ).

LBP -Lower Bound Problem

A compact linear program, referred to as LBP, whose solutions can be used as the lower bound of FTOP without the necessity of generating paths is as follows.

LBP: min C t = ∑ ξ e y 0 (5.1a)

∑ x 0 e∈E x 0 e∈δ + (v) ∑ x 0 ed ∑ e∈δ (v) 0 ed = 0, d ∈ D, v ∈ V \ {o(d), t(d)} (5.1b) d∈D ed ≤ y e , e ∈ E (5.1c) ∑ x s x s s e∈δ + (o(d)) ed ∑ e∈δ (o(d)) ed ≥ h d , d ∈ D, s ∈ S (5.1d) ∑ e∈δ + (v) ed ∑ e∈δ (v) ed = 0 x s 0 d ∈ D, v ∈ V \ {o(d), t(d)}, s ∈ S (5.1e) ed ≤ x ed , e ∈ E , d ∈ D, s ∈ S (5.1f) ∑ x s
∑ e∈δ + (o(d)) x ed ∑ e∈δ (o(d))
x ed , does not have to be explicitly specified in the formulation.

Comparing LBP and FTOP

The solution of formulation (5.1) is a lower bound for FTOP because all constraints of (5.1) are obviously fulfilled by the link-flows defined by any feasible solution x 0 s , d ∈ D, p ∈ ˆ , s ∈ S of (4.1), that is, by the link-flows

x 0 0 s s ed := ∑ ˆ P d x d p , x ed := ∑ ˆ P d x d p , e ∈ E , d ∈ D, s ∈ S .
Conversely, an optimal solution x 0 , x s , e ∈ E , d ∈ D, s ∈ S , of (5.1) could ed ed be translated to an optimal solution of FTOP only if there existed elementary path-flows that would realize the nominal link-flows x 0 , and at the same time could be appropriately thinned to realize the state-dependent link-flows x s for each state s. However, this is in general not possible and hence optimal LBP solutions may in this sense be infeasible for FTOP already for the single-link failure scenarios (Section 4.6.1,Example 4.5) and for the single-node failure scenarios (Section 4.7.2,Example 4.6).

We evaluated the lower bound of FTOP resulting from compact formulation (5.1) for state scenarios SL, DL and SN (single-node failures) for the four cases of (α, β) considered in Section 5.2.1. As the tests were made for undirected networks, we implemented a version of formulation (5.1) with undirected links.

It turned out that for SL and SN, the cost of the LBP solution in all the considered network was smaller than the optimal cost of FTOP by 2-8 percent. The solution times of both approaches where comparable for SL. In the case of SN, however, the running time for LBP was much longer than that of the PG algorithm for FTOP-the LBP running time was always at least 30 times longer.

A comparison of LBP and FTOP in terms of the network cost and the running time assuming DL is presented in Tables 5.6 and5 is a lot less. Second, typically LBP requires much more Simplex iterations than FTOP. This is because for a given state s ∈ S the number of thinned link-flows in LBP (for every link with limited availability in s all its nonzero demand specific link-flows are typically thinned) is in general much larger than the number of thinned path-flows in FTOP (only the non-zero path-flows through the links with limited availability in s are thinned). For example, for polska limited to 4 demands LBP stopped after 2053 iterations while FTOP required only 13 to 52 Simplex iterations at each of the 7 PG iterations, i.e., less than 365. Perhaps it would be possible to improve the solution time of LBP by applying a decomposition method such as Benders' decomposition. Nevertheless, this Finally let us address the question raised in Section 5.3: why we consider FT instead of an LBP-based strategy (i.e., a kind of link-flow thinning) despite the fact that in general solutions of FTOP are strictly more expensive than solutions of LBP. The reason is three-fold.

First, as discussed earlier in this section, in general the state-dependent link-flows optimized with LBP do not correspond to any path-flows (tun- nels) that obey the assumptions of FT. Thus, the simple tunnel thinning and traffic control mechanism that with FT is performed at the traffic/tunnel originating nodes cannot be directly applied. Certainly, a linkflow thinning mechanism could be applied at the link originating nodesthis, however, would most likely lead to a substantially more complicated traffic control mechanism as compared to FT. Second, as shown above, the cost advantage of LBP over FTOP is only marginal. In addition, as discussed above, except for small networks the running time required to solve LBP is significantly larger than that required by the PG algorithm of FTOP.

Third, as shown in Example 4.5, in general the optimal nominal linkflow x 0 delivered by LBP must contain loops. This can cause serious problems for traffic routing protocols. In this chapter, we deal with implementation issues of flow thinning. We first present, in section 6.1, a version of FTS called affine flow thinning (AFT) that reduces the number of failure states for which the strategy needs to be optimized. Next, we analyse implementation issues related to FTS and AFT. Then, in section 6.2 we present an extension of FTS denoted flow adjustment (FAS) that allows for thickening. This evolution leads to a more cost-efficient strategy but the management cost and other issues prevent us from adding this feature to FTS. Finally, we conclude this chapter in section 6.4 with some remarks on possible evolution of FTS.

Affine versions of FTS

As discussed in more detail in Section 6.2, the practical usefulness of the FT strategy in its form presented so far is limited for three reasons. First, broadcasting of the current link capacity information in real time could be difficult. Next, it would be difficult to solve FTOP (and to store the resulting solution) for an excessive (exponential) number |S | of states. Finally, even if we managed to achieve an optimal solution (and could store it) for a given (reasonably large) set of states S , for the valid states outside S the thinning would be undefined. The flow thinning strategy FT and its optimization model FTOP presented in the previous sections assume a predefined finite list of states S characterized by α s , s ∈ S , where α s = (α s , e ∈ E ). The considered states consist of multiple partial link failures and this means that the potential number of states is enormous, of the order of 2 |E | already for total link failures. To avoid potential intractability of FTOP, we have so far (see the beginning of Section 4.4) assumed the number of states in S to be polynomially bounded by the number of nodes and links; as we know, FTOP is N P -hard already for this case.

Hence, what we can actually do in practice is to solve FTOP for a reasonable (for sure polynomial, but even then for not too large) number of states, and activate proper flow thinning (having the flow thinning factors stored in the originating nodes) when a particular predefined state α s of links is detected and made known, by some signaling protocol, to the originating nodes of the demands, and using approximated thinning factors when a state not considered in FTOP occurs.

Because of that, in this section we will consider a version of FT called affine flow thinning (AFT) that addresses the above issues. In particular, we will study a variant of FTOP (called AFTOP) corresponding to AFT. AFTOP relies on using the decision rules largely used in multi-stage robust optimization, and more particularly, affine decision rules [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]) (application of affine decision rules to traffic routing were introduced by [START_REF] Ouorou | A model for robust capacity planning for telecommunications networks under demand uncertainty[END_REF] and further investigated by [START_REF] Poss | Affine recourse for the robust network design problem: between static and dynamic routing[END_REF]). In essence, AFTOP turns out to be nothing else but a particular example of an adjustable robust linear program, where the uncertainty set is S and the adjustable variables are x s . Hence, rather than letting the adjustable variables depend on each specific state s, following [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF] in AFTOP we let these variables depend affinely on the parameters that describe the state: α s , e ∈ E . We adapt these ideas by considering two special types of FT described in Section 6.1.2 below.

Notice that AFT and its variants were mostly studied by Michael Poss, Michal Pioro and Dritan Nace in [START_REF] Pióro | Optimizing flow thinning protection in multicommodity networks with variable link capacity (submitted)[END_REF]. Hence, we will only briefly introduce AFT.

Affine flow thinning and the related version of FTOP

With AFT, the flows x 0 reserved on paths d ∈ D, p ∈ P d , are thinned to x s for the states s ∈ S not in an arbitrary way, as with FT, but by assumption each such flow is thinned according to its individual affine function of the availability coefficients α s . More precisely, ) is referred to as AFTOP. In AFTOP, the parameters z become optimization variables and variables x s play only an auxiliary role. Such a formulation is obtained by adding equations (6.1) to (4.1).

Observe also that with appropriately limited cardinality of S , traffic efficiency of AFT can be very close to traffic efficiency of FT. In fact, as shown in [START_REF] Poss | Affine recourse for the robust network design problem: between static and dynamic routing[END_REF] for a similar problem, AFT becomes equivalent to FT if, and only if, S contains at most |E | + 1 states.

In the implementation aspect, AFT is more practical than FT. Although as FT, AFT must be aware of the current link states α s , it will use the (optimized) affine functions A d p , d ∈ D, p ∈ P d , for thinning the nominal flows. Such thinning, contrary to FT, is applicable to all possible states, i.e., also to the states not in the set S assumed for optimization.

In spite of the above advantages, AFT suffers from two problems. First, introduction of affine coefficients (variables) z 0 e , e ∈ E , for each path p ∈ P d , d ∈ D, and each link e ∈ E , leads to large linear programs for AFTOP, both when included in formulation (4.1). Second, AFT can still be hard to implement because the affine function of each path p involves, as arguments, the link availability coefficients of all links. Thus, disseminating the link-status information is as difficult as for FT.

Restricted affine flow thinning

As AFT, restricted affine flow thinning (RAFT) assumes that the flow on each path for each state is an affine function of the availability coefficients α s , but only of the links that belong to path p: The most important advantage of RAFT over AFT (and for that matter, over FT as well) is that with RAFT disseminating link capacity information is, not a major issue, as a path-originating node thins the corresponding path-flow only on the basis of the current capacities of the links along the path. In fact, we could easily use even more information on the link availability states, namely the thinning function of a path-flow could be made dependent on coefficients α s of all the links e belonging to the sets δ(v) for all nodes v traversed by the considered path, i.e.,

Implementation issues of FT

A major implementation issue related to FT is to ensure proper online tunnel capacity control. Assuming that the nodes can instantaneously determine and apply appropriate thinning factors (thinning factor is the ratio of the tunnel capacity calculated for a given state to its nominal capacity) once the link availability state is made known to them, we need an ongoing online signalling process of informing the network nodes about the changes in the current link availability coefficients. For the general version of FT this would call for a network protocol, like OSPF-TE (Open Shortest Path First -Traffic Engineering) [START_REF] Katz | Rfc3630: Traffic engineering (te) extensions to ospf version 2[END_REF], enabling the originating node of a link to broadcast a link-status message whenever the capacity of the link is changed. A difficulty is to make the message reach all the nodes in a reasonable time. This issue can be overcome by applying RAFT (see Section 6.1.2) instead of FT. With RAFT, the thinning factors of each tunnel are specified by means of an affine function depending only on the availability coefficients of the links along the tunnel. Then the link-status message concerning a change of the availability coefficient of a particular link is sent by its originating node backwards along all the tunnels that traverse this node and use the link in question. In this way, by means of appropriately extended path-error messages in Resource Reservation Protocol -Traffic Engineering (RSVP-TE, the protocol from the TCP/IP stack that is used to establish, maintain, and erase LSPs, see [START_REF] Minei | MPLS-Enabled Applications: Emerging Developments and New Technologies[END_REF] and [START_REF] Awduche | Rsvpte: Extensions to rsvp for lsp tunnels[END_REF]), the nodes can be quickly informed (at least when the links are bidirectional-a typical case in WMN) about the changes in the links capacity they need to be aware of. (Observe that since a tunnel is thinned to 0 already when only one of its links fails totally, it is enough that the originating node of a tunnel is informed only about the total failure of its closest link.) Hence, the crucial mechanism for FT could be implemented in a network composed of IP routers interconnected by IP links with logical tunnels (LSP) realized by means of the MPLS mechanism (see [START_REF] Minei | MPLS-Enabled Applications: Emerging Developments and New Technologies[END_REF] and [START_REF] Andersson | RFC3468: The Multiprotocol Label Switching (MPLS) Working Group decision on MPLS signaling protocols[END_REF]).

Next, FT requires a low-level QoS packet admission control mechanism (including packet scheduling and policing), see [START_REF] Evans | Deploying IP and MPLS QoS for Multiservice Networks -Theory and Practice[END_REF] and [START_REF] Harhira | A mathematical model for the admission control problem in MPLS networks with end-to-end delay guarantees[END_REF] to assure, for each demand, that the instantaneous packet flow admitted to enter each of its dedicated tunnels does not exceed the current tunnel capacity. The users that compose a demand, in turn, could be notified (using some kind of explicit congestion notification mechanism, see [START_REF] Evans | Deploying IP and MPLS QoS for Multiservice Networks -Theory and Practice[END_REF]) about the current admitted-to-nominal traffic ratio. Then, the users could decide which sessions to realize so that the combined demand traffic would be served in an efficient way, minimizing the number of packets discarded by the demand originating node admission control.

Another issue is that with FT in general only a fraction of all possible link availability states can be explicitly considered in optimization, simply because the number of states can be exponential. Hence, the thinning factors for a non-considered state must be somehow calculated at the tunnel originating nodes, having in mind that the resulting tunnel capacity cannot overload the links and the reduction of traffic is acceptable. For the general version of FT, finding a reasonable algorithm for that would be difficult but this task becomes tractable with RAFT (and, for that matter, also for AFT): for the non-considered states, the thinning factor for a given tunnel is automatically determined by the affine function once availability coefficients for its links are known. Moreover, the affine functions, even when optimized using a limited number of states, would tend to ensure reasonable thinning factors also for the states not explicitly considered in optimization. This is particularly sound when thinning is based on the non-negative value of an affine function:

x s = max{ 0, x 0 ∑ e∈ d p (1 α s ) }, d ∈ D, p ∈ P d
, where all

d p ≥ 0, e ∈ E .

Practicability of FTOP and its affine version

In our optimization model each link availability coefficient α (for a given link and a given state) is a fixed parameter while the nominal capacity y of the link is an optimization variable. Using the availability coefficients to determine the state-dependent link capacity as α • y is a sound assumption for the following reason. In reality, in most cases link capacity is modular, i.e., equal to M • y where y is a number (an integer variable) of modules of size M installed on the considered link. Referring to the application examples discussed in Section 1.1.1, in the IP/MPLS over wireless case, where the modules correspond to parallel microwave radio links or wireless optical links, coefficient α corresponds to the modulation and coding scheme applied in the considered state. In the IP/MPLS over DWDM case, α is the percentage of modules (for example, 0%, 33%, 66%, 100%) that are not lost in the considered link as a result of the failure in the DWDM layer.

That is, we assume the equal split of y modules to be realized over a given set of k disjoint DWDM paths (k = 3 paths in our example), whatever the value of y (provided y is divisible by k, to be precise). Note that capacity is linearized and variables y are made continuous to avoid unnecessary complication of the optimization model. The state description assumed for FTOP is on purpose quite general. The implementation of FT described in Section 6.2, however, assumes that the demand reduction coefficients depend only on the vector α s (i.e., β s = β(α s ), s ∈ S ), so that the state is in fact determined by the current vector α s of link availability coefficients. This kind of state description, together with the assumption that the demands will accept reduction in their nominal traffic volumes in the states with significant link capacity reduction, opens a way to specify reasonable demand reduction coefficients by the network operator to avoid substantial network over-dimensioning, and hence excessive network cost. Clearly, the degree to which the preferable traffic volume is decreased should reflect the fractions of the nominal link capacity available in a given state.

A simple way for achieving reasonable reductions is to divide the set of states into several classes corresponding to several degrees of lost capacity, and to assume a certain percentage of the nominal traffic that should be carried for each demand in a given state. For example, we may distinguish d two classes of states, one of "almost nominal" states with the entire (100%) nominal traffic to be carried, and the second class of "degraded states" that allow for carrying only 75%, say, of nominal traffic for each demand. A more sophisticated way, applicable in the affine version of FTOP, is to relate the demand reduction coefficients to the link availability coefficients through the so called uncertainty polytope.

Another important practical issue is how to select a representative set of states of reasonable (tractable) size to be assumed for FTOP (or AFTOP). These states should, on one hand, represent a whole range of typical states, and, on the other hand, be sufficient to effectively approximate the thinning factors in the remaining feasible states (see Section 6.2). Such a selection is network dependent. For the IP/DWDM case the selection is basically simple. As it is a common practice to consider only single optical cable cuts (simultaneous cuts of more than one cable are very unlikely), the resulting multiple partial IP link failures are easy to list and include in FTOP. In the case of WMN, the situation is more complicated. For modeling link availability states implied by weather conditions in a metropolitan WMN, we could divide the nodes into disjoint groups and assume that the bad whether conditions affects either all of them or a subset of them at a time. If we distinguish only several groups then we are able to consider all the states corresponding to all subsets of the family of these groups, i.e., the partial failures (with different levels of link availability, depending for example on the rain intensity) of all nodes in the affected groups. The demand reduction coefficients would then depend on the total number of affected nodes and (demand-wise) on the position of the demand's end nodes. This issue, however, requires a separate study.

For everyday network operation a pure flow allocation version of FTOP (or AFTOP) becomes important. Such a problem (let us call it FTOP/FA) arises when nominal link capacities are fixed, i.e., y 0 become given parameters. FTOP/FA has to be considered whenever the nominal traffic matrix (assumed for FTOP) is significantly perturbed causing the nominal flows and the thinning factors (tunnel flow-defining affine functions in the case of AFT) not fit the new traffic matrix anymore. Hence, the nominal flows and thinning factors have to be re-optimized. In order to properly accommodate the new traffic by the network, some kind of fairness criteria (link max-min fairness or proportional fairness (see Chapter 8 in Pióro and Medhi (2004b)) should be imposed on the values of h s , d ∈ D, s ∈ S (these quantities would become optimization variables on top of the tunnel flows), and reflected by an appropriate objective function used instead of (4.1a).

Observe that optimization of FTOP does not have to be decentralized since it could be done once for all in a central facility before the network is set to operation. FTOP/FA, in turn, should be resolved, using an off-line optimization algorithm, whenever the nominal traffic matrix (assumed for FTOP) is significantly perturbed. When perturbations are not frequent, such optimization could be done in a central facility as well. Otherwise, the computation should be decentralized and distributed among the network nodes. This would require some information exchange mechanism, for example an extension of the OSPF-TE. Such an algorithm, however, is outside the scope of this paper.

Thickening versions of FTS

A natural extension of FTS, and thus of FTOP denoted Flow Adjustment (FAS) (Fouquet et al. 2014a;c), allows for tunnel thickening limited by additional parameters t d ≥ 1, d ∈ D, called the thickening bounds.

Flow Adjustment -The flow thickening extension of FTOP

The extension is obtained by modifying constraint (4.1e):

x s 0 d p ≤ t d x d p , d ∈ D, p ∈ P d , s ∈ S . (6.4)
Hence, FAS is represented by the following link-path linear programming (LP) formulation involving variables

x 0 (d ∈ D, p ∈ P d ), x s (d ∈ D, p ∈ P d , s ∈ S )
and y e (e ∈ E ):

P FAS (P ):

C(P ) = min ∑ ξ e y 0 (6.5a) [π 0 ≥ 0] e∈E ∑ ∑ δ ed p 0 ≤ y 0 , e ∈ E (6.5b) [λ s ≥ 0] d∈D p∈P d x s ≥ h s , d ∈ D, s ∈ S (6.5c) d [π s ≥ 0] ∑ d p p∈P d δ d x s ≤ α s y 0 , e ∈ E , s ∈ S e (6.5d) e ∑ ∑ ed p d p e e d∈D p∈P d s ≥ 0] x s ≤ t d x 0 , d ∈ D, p ∈ P d , s ∈ S (6.5e)
x 0 , x s , y 0 ≥ 0 and continuous (6.5f)

Objective (6.5a) minimizes the overall cost of links. The first capacity constraint (6.5b) makes sure that the nominal link loads do not exceed the nominal link capacities. Next, the demand constraint (6.5c) assures that in each state s ∈ S , the thinned nominal flows are sufficient to realize the volume of each demand d ∈ D assumed for this state. Then, the second capacity constraint (6.5d) assures that in each state s ∈ S , the available capacity of each link e ∈ E s is not exceeded. Finally, constraint (6.5e) assures thinning.

Clearly, with t d > 1 a (limited) path-flow thickening for demand d ∈ D is permissible, not only thinning. In fact, this modification (even when the thickening factor is made tunnel-dependent) has virtually the same properties as FTOP and can be approached essentially in the way discussed in Section 4.4 as done in (Fouquet et al. 2014a).

When the thickening bounds t d , d ∈ D, are considered (constraint (4.1e) is substituted by (6.4)) then constraint (4.2c) in the related dual problem takes the form

∑ σ s 1 δ π 0 , d ∈ D, p ∈ P (6.6) s∈S d p ≤ t ∑ e∈E ed p e d
while the rest of the constraints remain unchanged. When all t d → ∞, i.e., when the primal problem becomes the GR optimization problem, the right-hand side of constraint (6.6) becomes equal to 0 which forces all

GapFA (τ = 1.1) GapFA (τ = 1.25) GapFA (τ = 1.5) GapFA (τ = 2) GapGR d p λ s e FTS , C GR FTS = C FAS GR FTS
Relative gap dual variables σ s , s ∈ S , d ∈ D, p ∈ P d , to be equal to 0. Hence, constraint (4.2d) takes the form

d ≤ ∑ e∈E s δ ed p π s , s ∈ S , d ∈ D, p ∈ P d (6.7)
and this makes the related dual separation (and path generation) problem polynomial. This could be expected, since the GR problem is, as mentioned in Section 4.2.3, polynomial.

Performance of Flow Adjustment

Although in general FAS is designed to handle multiple partial link failures, below we focus on the single link failures to illustrate the performance of the strategy compared to FTS.

-Network description

In Table 6.1 we describe the undirected network instances used in our tests taken from [START_REF] Orlowski | SNDlib 1.0survivable network design library[END_REF]. We consider several scenarios with different values of the link availability coefficients α and the thickening coefficientst d . In all cases, we assume 100% traffic restoration. In Figures 6.1-6.4, we compare the GR, FT and FA strategies with respect to their cost-effectiveness. In the comparisons, C α α FAS and C α denote the optimal value of the network cost for FAS and GR respectively. Remind that considering t d = 1, C α α FAS . Ga pFAS and Ga pGR expresses the relative gain of cost of C α and C α , respectively, with respect to C α for a given availability ratio α. Consider strategy S (S equals to FAS or GR),

Ga pS = (C α C α )/C α .

FTS S S

These figures shows that the gain of cost is limited for low intensity perturbation. However, the gain of cost becomes significant for strong perturbation with a gain of at least 15% for a thickening limit fixed to 25% (t d = 1.25) for all networks. Notice that for sparse networks (polska, nobel-us), allowing to double the bandwidth leads to dimensioning cost close to Global Rerouting. However, the gap between C α and C α remains high for meshed networks (di-yuan). Note that more results of the cost-efficiency aspect of FAS are presented in (Fouquet et al. 2014a) and [START_REF] Fouquet | Flow adjustment methods for survivable networks[END_REF]. It is clear that Flow Adjustment is a lot more prove traffic performance of FT, a natural question arises why we still opt for FT. The three main reasons are described in the following.

GapFA (τ = 1.1) GapFA (τ = 1.25) GapFA (τ = 1.5) GapFA (τ = 2) GapGR GapFA (τ = 1.1) GapFA (τ = 1.25) GapFA (τ = 1.5) GapFA (τ = 1.75) GapGR GapFA (τ = 1.1) GapFA (τ = 1.25) GapFA (τ = 1.5) GapFA (τ = 2) GapGR FTS GR

Higher number of paths to be adjusted

First, with FT the maximum number of flows that are adjusted when moving from state s 1 to state s 2 is equal to the number of flows that traverse links affected in state s 1 plus the number flows that traverse links affected in state s 2 . This number is quite small as compared to the number of all (non-zero) nominal flows. However, with thickening this bound is not valid and the number of adjusted flows can become significant. In general, the larger the thickening bound the more tunnel flows are adjusted, and this number is typically the largest for GR (with GR frequently virtually all flows can be adjusted even for modest changes in link capacity). Moreover, the scale of the perturbation, i.e., the ratio of the number of nominal path-flows changed when a failure occurs is increased in FAS. While for FTS the perturbation observed only for a number of paths ranging from 30% to 45%, the scale of the perturbation is much larger for FAS. We have notice that for all the single link failure states with α = 0.5, almost all routing paths are subject to thinning or thickening (more than 98% of the total number of routing paths). All of this is shown in the following Table 6.2 which reports the average percentage of the routing paths required to be thinned ( ) or thickened ( ) per failure for FAS (remind that t d = 1 represents FTS). Even though this number clearly shows the advantage of using FT, the values of percentages. Thus, they must be reported to the actual number of paths in the optimal solution. In the following Figures 6.5 and 6.6, we represent the number of distinct paths per demand used by FAS for partial link failures (α = 0.5) and for total link failure (α = 0).

network t d = 1 t d = 1.1 t d = 1.5 t d = 2 di-
We first notice that FTS requires less paths than FAS, and that this difference increases with t d . Moreover, except for di-yuan, the number of routing paths required by FAS for total single link failures is similar to the number of paths required for partial single link failure with α = 0.5.

Transient behavior of the flow adjustment process

The main interest in the flow-thinning strategy stems from the simplicity of the path-flow handling process. Indeed, the reaction to a particular availability state basically consists in decreasing the flow on (some of) the affected paths. In the following we assume that a signaling protocol sends a message from the end node of the failed link to the source nodes of the routing paths traversing this link when its capacity decreases by a certain fixed threshold. Hence, the time required to recover from a failure state with FTS is equal to the time required for the signaling messages to traverse the path from the end nodes of the perturbed links to the source nodes of the affected demands. Then, upon the receipt of such signaling messages, the source nodes will set.apply the appropriate flow value to their originating routing paths. The flow adjustment process in FAS is not as simple as in FTS. This process is composed of two simultaneous stages managed by the source and destination nodes of traffic demands.

The source nodes of the demands will first need to decrease the flow on some affected paths in order to make room for enlarging the flows on some other paths. Then, in the next stage, the destination nodes will be able to increase te flow of the latter paths. To examine the process, we have run appropriate simulations. Figures 6.7 and 6.8 report the ratio of the perturbed demands for a fixed link failure as a function of time for network polska with, respectively, α = 0.5 and α = 0. The considered failed link is contained in the routing paths of 20% of demands that are in this way affected. Nevertheless, the flow adjustment process perturbs more demands, as the nominal path-flows of non-affected demands are in general subject to changes as well. In the process, the flows on a set of paths are first decreased to allow the flows on another set of paths to be subsequently increased. This makes a lot of demands to be temporarily perturbed reaching about 55% (respectively, up to 80%) of the number of (1l demands after 3 units of time for oe = 0.5 (resp. oe = 0). We notice that, as expected, the flow adjustment process is faster for the partial failure than for the total failure. Nevertheless, the process converges very fast as compared with GR. Finally, we notice that the ratio of perturbed demands remains high as compared with that observed for the flow-thinning strategy FTS (no flow thickening).

Cil 80%

"C 1: --FA (T=l.l)

(1l
--FA (T=l.l) ••••••••••••••FA (<=1.5) --FA(T=2)
••••••••••••••FA (<=1.5) --FA(T=2)
Figure 6.8 -Evolution of the ratio of perturbed demands for polska (IX = 0).

6-3-3•3 Link overloads

The third reason are link overloads caused by erroneous approximation of flow thickening factors. If a certain state is not considered in optimization, its tunnel thickening factors must be approximated, as it is clone in FT for the thinning factors. However, since with thickening the nominal tunnel capacities are allowed to be exceeded in the states with reduced link capacity, wrong approximation of the thickening factors could easily lead to link overloads during the whole duration the unforeseen states. To summarize, as far as unforeseen traffic losses are concerned, FT is safer than its variants admitting flow thickening (including GR).

6-4 CONCLUDING REMARKS

Flow thinning (FT) is an original concept of a traffic routing and protection strategy for communication networks with variable link capacity. lts affine variant, AFT (more specifically, RAFT), opens a way for distributed implementations. To our knowledge, similar strategies (working at the logical tunnel level and reacting online to link capacity fluctuations) have not been proposed and therefore studying optimization models for FT and AFT is worthwhile, the more that the related multicommodity flow problems contribute to the area of resilient network design and are interesting from the OR viewpoint.

In this chapter, we have studied relations between the investment and management cost and the restoration performance for the considered protection strategies (FAS, FTS, GR). It turns out that the flow adjustment approach of FAS (and FTS) assures acceptable investment and management cost while achieving high restoration performance. Nevertheless, an important issue that needs special care is the volume of information required to be maintained at each routing node that could become problematic in large networks. One way of alleviating this would be to limit the number of path-flows that are adjusted per failure situation. This can be done by making a distinction between affected and non-affected demands. This distinction could help to reduce the number of routing paths affected per failure situation but still the volume of information kept at each node remains almost as large. Thus, a variant of the method needs to be designed for distributed environments. These important interrogations were considered while conceiving a new recovery mechanism named Elastic Flow Routing, presented in the next part of this thesis, in the three next chapters.

Part III

Elastic Flow Rerouting

This part is dedicated to the Elastic Flow Rerouting (EFR) strategy. In Chapter 7, we introduce the mathematical formulation for total link failure scenarios (EFR-P) together with a complexity study. EFR-P is N Phard and requires branch-and-price to be solved to optimality due to the distinction between affected and unaffected demands. Thus, we propose a greedy heuristic method to solve EFR. As this thesis deals with both total and partial failures, in chapter 8, we study practical applications of EFR to partial failures. In accordance with microwave communication context, we propose a formulation of the modulation schemes and show next how EFR can be combined with FTS to give a strategy capable to handle both type of failures. Finally, we study a distributed variant of EFR. In the last chapter of this part, Chapter 9, we study the effiency of EFR and its formulations followed by an analysis of the heuristic method performance. We conclude this part with a study of restoration time in case of failure of both centralized and distributed versions of EFR.

Elastic Flow Rerouting for total link failures n this chapter, we study a method that combines positive features of the strategies discussed in Chapter 2. The method is intended to achieve a compromise between the capacity cost, restoration time, and management effort, while covering a large set of applications. The method is called Elastic Flow Rerouting (EFR). Its full study, including a mathematical formulation and a discussion on its complexity, is presented in (Fouquet et al. 2015b). We show that the problem becomes computationally intractable even for moderate size instances, so that there is a need for heuristic approaches. Hence, we propose a heuristic solution method accompanied with numerical results. EFR is dedicated to the management of total link failures. An adapted version of EFT, able to manage partial failures, will be presented in the next chapter.

Introduction to Elastic Flow Rerouting

Elastic Flow Rerouting (EFR, [START_REF] Fouquet | Elastic routing: a distributed variant, implementation issues, and numerical results[END_REF]) is intended to deal with total link failures. The approach works as follows. In the nominal state (when all links are operational), traffic is routed over a given set of paths for each traffic demand. In each failure state (to simplify the explanation only total failures of single links are considered), EFR uses the same set of (nominal) routing paths but with possibly modified path-flow values. In each failure state we distinguish between affected flows and affected demands. In a given failure state the affected flows are those routed on paths going through a failing link, and the affected demands are those for which at least one path is affected and the total capacity of unaffected paths is not sufficient to carry the demand traffic. The main idea behind EFR is to restore traffic of the affected demands by means of increasing the flow on their routing paths, possibly together with decreasing flows of the unaffected demands. Thus, an increase of the path-flows is allowed only for the affected demands, and a decrease of path-flows is allowed only for the unaffected demands (besides the failed flows which are automatically removed). Notice that no new paths are allowed to be established. To limit the number of path-flows and prevent from establishing paths with no bandwidth (that could be adjusted upon failure occurrence), the thinning and thickening are bounded by a fixed percentage of their nominal path-flows. Summarizing, flows (on existing paths) can be increases due to:

• capacity released on affected paths

• capacity possibly released on some paths of unaffected demands

• protection capacity present on links due to network overdimensioning.

Clearly, the capacity released on routing paths of unaffected demands is limited because the remaining flows on the routing paths for the unaffected demands must be sufficient to carry the requested traffic volume.

In short, we can say that EFR adds rerouting capabilities to PD but, unlike RR and GR, seeks to find the capacity needed for rerouting by decreasing some flows on the nominal routing paths of unaffected demands (in addition to the capacity released by the affected flows). Contrary to ShRR, EFR avoid path creation. We consider single-link failure scenarios in which each link can fail, but once at a time. We show below what is the result of the minimum link cost network when EFR is used to recover from single link failures.

The obtained solution gives a capacity of 1 to link (B, E), 3 2 to link (C, E), 0 3 to link (D, E) and 1 for the other five links. In the nominal state, as depicted in Another failure scenario is presented on Figure 7.3 , concerning the failure of link (A,E). The traffic requirement for d 1 is no longer meet and there is no bandwidth available ta increase the traffic on paths p 2 and p 3 . As demand d 2 is not affected by the failure, it releases ofbandwidth on path p 5 ta make room for path p 3 thickening. Finally, dt increases the bandwidth of paths p2 by and all demands recovered the failure.

Ps('-1/3) Figure 7•3-EFR-Failure of link (A, E).
The other failure scenarios are simple of similar ta the two examples described above. Failures oflinks ( B,E) and (C,E) do not cause any problemfor demand d1. The other link failures a re close ta the failure of (A,C) . Note the dimensioning cast of 5 is also the o ptimal cast for bath GR and RR st rategies.

We recall that differentl y ta EFR :

h x 0 s P d d d ξ s 0
• GR and RR allow path creation (longer process than bandwidth increase),

• GR suffers from failure propagations

Mathematical model of EFR

The optimization problem considered in this section is referred to as Elastic Flow Rerouting Problem (EFR-P) and is as follows. We want to minimize the total cost of link capacity assuming that in the nominal state of network operation, all demand volumes are realized by means of nominal path-flows. When the network is subject to a failure of a link then the demand volumes, possibly reduced, are realized for the duration of the failure state by appropriate thinning or thickening of the nominal pathflows depending on the state of their demand. A brief reminder of the notation used in this section is given in 7.2.1 and the detailed formulation of EFR-P is given in Subsection 7.2.2. Section 7.3 is devoted to its complexity study.

Notation

EFR-P formulation

Optimization problem EFR-P is given in the non-linear path-flow formulation ( 7 x, y, u, v continuous, nonnegative, T binary (7.1k)

In the formulation, objective (7.1a) minimizes the total cost of links, i.e., the dimensioning cost. Constraints (7.1b) do not allow that nominal link loads exceed nominal link capacities. Constraints (7.1c) assure that for each demand its paths have jointly sufficient capacity to satisfy the demand volume requested for the nominal state. Next, constraints (7.1d) make sure that in each state s ∈ S the capacity of each working link e ∈ E \ {s} is not exceeded. Constraints (7.1e) assure that in each failure state s ∈ S , the adjusted flows are sufficient to realize the (possibly reduced with respect to h 0 ) volume h s of demand d ∈ D. Then, constraints (7.1h) the demand is affected (by more than a given c > 0) in the failure state s and constraints (7.1g) deal with unaffected demands. Finally, constraints (7.1h)-( 7.1j) forces variables x, u and v to be correctly defined with respect to affected/unaffected demands and T binary variables.

We discuss next state-dependent constraints (7.1f), (7.1g),(7.1i) and 0 s (7.1j). If 0 ≤ ∑ p∈P s x d p < h d , demand d is affected by the failure state s and its path-flows can only be thickened u s = 0. Otherwise, demand d is not affected and its path-flows can only be thinned v s = 0. For this purpose, the constraints use a very large number called big-M coefficient, as well as a very small value c which, together with T s binary variables, emulate I F-like constraints. Using a large value M could lead to numerical instability. To avoid this issue, constraints (7.1f),(7.1g), (7.1i) and (7.1j) are modeled in the solver CPLEX as indicator constraints. For instance, the "strictly less than" linear constraints (7.1f) is modeled as

0 s s s I F ( ∑ p∈P s x d p ≥ h d ) T HEN T d = 0 ELSE T d = 1.

Complexity discussion

Formulation (7.1) is hard to solve exactly by mixed-integer linear solvers for mainly two reasons. First, the number of variables used in the formulation can be very large, since the sets of admissible paths can be of exponential sizes with respect to the size of a network. Second, it contains binary variables and big-M coefficients, which leads to numerical instability and very poor linear relaxations. All this gives a hint on the practical difficulty and the computational complexity of the EFR problem. Before stating on the complexity let us clarify, in the light of the above formulation, the connection of EFR to other restoration strategies mentioned in Section 4.1. First, taking a = 0 and b = 0 leads to PD strategy (neither thinning nor thickening are possible). Second, for a = 1 and b → ∞ one can see that EFR converges to Global Rerouting while for a = 0 and b → ∞ EFR becomes RR strategy. We can easily check that all requirements for each strategy are satisfied. For instance, taking a = 0 implies that flow thinning is not allowed, while b → ∞ means that virtually new rerouting paths can be created; this is because the flow on some path can be enlarged at any finite value starting from practically insignificant flow values. All these special cases have different levels of complexity for the single link failure case: GR and PD fall into the polynomial time complexity class [START_REF] Orlowski | Complexity of column generation in network design with path-based survivability mechanisms[END_REF], while RR is shown to be N P -hard for both the directed case [START_REF] Nace | Complexity of a classical flow restoration problem[END_REF]) and the undirected one [START_REF] Tomaszewski | The final answer to the complexity of a basic problem in resilient network design[END_REF]. The observation suggests that both problems will exhibit the same N P complexity.

Not surprisingly, we will use similar arguments to show the NPhardness in question. The proof given for EFR is inspired by the RR N Phardness proof presented in [START_REF] Nace | Complexity of a classical flow restoration problem[END_REF]). The proof is based on a specific network constructed to show that finding an RR solution is equiv-alent to solving the elementary path problem EL-PATH, which consists in answering the question whether there exists an elementary path going through a fixed link in a directed graph. Problem EL-PATH is N P -hard, because it can be reduced from 2-DIV-PATH, which itself is N P -hard [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF]. The network instance utilized in the proof is depicted in Figure 7.4. It assumes a simplified failure scenario involving a single demand and failures of only two links. Considering a single demand only has a particular impact on using EFR, the method cannot employ thinning as there is no interest in considering cases when the demand is unaffected. Hence, in the following, we consider the EFR problem with a set to 0 and b set to a large but finite value, thus the nominal flows cannot be decreased, but they can be increased and multiplied by b + 1. Then, bearing in mind that we are looking for solutions involving only elementary routing paths, the following proposition can be proven. Proposition 7. 1 EFR problem,represented by (7.1), is N P -hard already for the case with two failing links and one demand.

Proof. The proof is deduced from the problem of existence of an elementary path in a directed graph traversing a given link. Let this problem be denoted by EL-PATH. As discussed in [START_REF] Nace | Complexity of a classical flow restoration problem[END_REF], EL-PATH is N P -hard.

The upper left part of Figure 7.4 represents an instance of EL-PATH, asking for finding whether there exists an elementary path from v to w traversing a given link (a, b) in a directed graph represented by the oval. The main part of the figure shows how this instance of EL-PATH can be reduced to an instance of the considered case of EFR with one demand d from node o to node t (with volume h d = 1) and two failing links f 1 and f 2 .

In the main graph, the links depicted by solid lines have large unit costs ξ, while unit costs of the links drawn as dotted lines are negligible with respect to ξ. The two ovals in the main graph are the copies of the oval in the upper left part. Unit costs of all possible links in these two ovals are also negligible as compared to ξ. Note that the nodes in both ovals in the main graph have the same names, but this should not lead to a confusion. We first show that the objective function value C of any feasible solution 5 of EFR must be greater than or equal to 3 ξ. The capacity of each of these five cuts must be greater than or equal to the requested volume h d = 1. Hence, by summing up the inequalities expressing these conditions for all five cuts we see that the sum of the capacity reservations of the five expensive links must be at least 5 . As 3 each of these links has the unit cost i;, we conclude that C 2:: SNow we will establish bounds of optimal solutions of EFR in the case when an elementary path from v to w traversing link (a,b) in the oval exists (Case :1), and in the case when it does not exist (Case 2).

Case :1: Suppose that the oval contains an elementary path P from v to w traversing link (a,b). Then, there exists a solution that achieves the cost 0 = 5 c; + I 1 JS• ln this solution, the flows in the normal state are as C 3 follows:

• Case 2: Now assume that there is no elementary path from v to w through (a, b) in the oval. We will show that in this case the cost C 0 of an 7 optimal solution of EFR must be greater than or equal to 4

1 : path 0 -VI -WI -UI -(b -W part of P) -t, 1 • (( path o -V3-W3I -U3I -v-(v-a part of P) -WI-UI -b - (b -w part of P) -t, 1 • (( path o -v3 -W32 -u32 -v -(v -a part of P) -w2 -u2 -b - (b-w part of P) -t, • 1 3: path o-V2-w2-u2-(b-w part of P)-t, 1 • 6 b: path 0 -V3 -W32-u32-V-p-t, 1 • b: path o -VI -W3I -u3I -v -P -t, 3 1 • 6 b: path o-V3-W3I-u3I-v--P-t, 1 • b : path o -V I -w32 -u32 -v -P -t.
ξ. Indeed, it has been shown in [START_REF] Nace | Complexity of a classical flow restoration problem[END_REF]

Heuristic method

As remarked in the previous section, formulation (7.1) combines the big-M constraints with a large number O(|D||S |) of binary variables, and produces large-scale integer-programming problems which happen to be intractable even for moderate size networks.

Solving the EFR-P requires solving a combinatorial optimization problem over the combinations of affected/unaffected demands sets for each failure. Additionally, it requires applying path generation in the solution process. In consequence, the exact solution of EFR-P would require branch-and-price algorithms. Obviously, solving formulation (7.1) with binary variables T s set to fixed values representing a certain choice of affected/unaffected demands would give an upper bound for the optimal solution of EFR-P. In fact, as we will see below, the optimization problem behind such upper bound solutions is much simpler to solve than EFR-P itself.

Hence, a natural heuristic approach to solve EFR-P would be to solve sequentially a set of problems with the unaffected/affected demands gradually fixed in each iteration. All this leads to a greedy heuristic approach described in Section 7.4.1. Next, the problem solved at each iteration, called EFR-PF (EFR-P fixed), is presented in detail in Section 7.4.2.

T s P d

Description of the heuristic

In this section, we present the greedy heuristic method used to solve the EFR-P optimization problem. In each iteration, the heuristic creates and solves an instance of EFR-PF (version of EFR-P (7.1), in which all d , d ∈ D, s ∈ S , are fixed to values 0 or 1), and then adjusts the status (affected/unaffected) of the demands. The process is repeated until no improvement is achieved-more precisely, we stop when all demands' status remain unchanged.

The algorithm starts with an empty set of unaffected demands for each failure state, and with some initial admissible path-sets. Thus, at the beginning all demands are considered as potentially affected. After solving the corresponding LP, we know exactly which demands are affected and non-affected in the current solution x. This gives a hint how to update the unaffected demands for the next iteration-the set of unaffected demands is extended with the demands that are not affected in the obtained solution x. In this way the new unaffected demands can contribute to the restoration process by potentially releasing some flow on their paths. For the next iteration, the EFR-PF instance is extended with the constraints that characterize the demands just set to the unaffected status.

In consequence, any feasible solution will always keep these demands unaffected because of these constraints, which are not subject to removal in the subsequent steps of the iteration process. Therefore, at each iteration, the obtained solution x can only extend the set of unaffected demands and no demands that have been previously made unaffected can become affected. We proceed like this with updating the sets of unaffected demands, and stop when the current solution does not change the status of the demands assumed for the previous iteration. This is the key idea of the method used in Heuristic EFR-H detailed in Algorithm 4 below. Step 4:

Return the solution

We can easily deduce that the algorithm will always stop. According to the above, once a demand is considered unaffected it will remain unaffected for all consecutive iterations. One the other hand, affected demands can change their status and become unaffected. Hence, the process will necessarily stop since the set of unaffected demands cannot be extended to infinity, and the algorithm ends when we obtain the same set of unaffected demands for two consecutive iterations.

One of the disadvantages of the presented algorithm is its fast con- vergence to local minima. If a large set of demands becomes unaffected in a single iteration, the heuristic may not be able to find high quality solutions. In order to alleviate this issue, the number of demands that can become unaffected in a failure state s in a single iteration is limited to M AX d demands. If M AX d takes a very low value, the heuristic will slowly converge, will explore a lot more scenarios, but the computation time will be much longer. In contrast, if M AX d takes a high value, the computations will be fast, but the algorithm will quickly converge to a local minimum that can be very far from the true optimum. The most reasonable value of M AX d depends on a network instance. However, we notice that M AX d = 5 represents a good compromise between the computation time and the solution quality. Still, observe that the presented method is not exact; thus, obtained solutions are in general suboptimal.

Formulation of EFR-PF problem

Let us now look in detail how the EFR-PF problem used in each iteration of the above algorithm is formally defined. We first introduce additional notation by defining two sets: E (d) = {s ∈ S : d ∈ D s } is the set of links whose failure does not affect demand d, and ¯(d) = {s ∈ S : d ∈ ¯ s } is E D the set of links that affect demand d. Note that in the EFR-PF problem the sets D s , s ∈ S are predefined. Then, a linear programming formulation for EFR-PF, denoted P F (D s , P ) and given in (7.2), can be obtained from (7.1) by fixing the variables accordingly. ≤ y e , s ∈ S , e ∈ E \ {s} (7.2d)

EFR-PF(P

[λ s ] [λ s ] ∑ p∈P s 0 d p (x 0 s d p + v s ) ≥ h s , d ∈ D, s ∈ E (d) (7.2e) ) ≥ h s , d ∈ D, s ∈ ¯(d) (7.2f) d ∑ d p d p d E p∈P s s d p [σ s s d p ] v s ≤ ax 0 ≤ bx 0 , s ∈ E (d), p ∈ P s , s ∈ ¯(d), p ∈ P s (7.2g) (7.2h) d p d p d p E d
x, u, z, y continuous, nonnegative (7.2i) In formulation (7.2), objective (7.2a) minimizes the total cost of links, and (7.2b)- (7.2f) are similar to (7.1b)- (7.1e). Constraint (7.1e) is split in two constraints (7.2e) and (7.2f). Then, constraints (7.2g) do not allow releasing more than a fraction a of the normal flow assigned to a path, and constraints (7.2h) ensure that flow increase on a disrupted path by more than the fraction b of the normal flow is not permitted. The values The condition stipulating that surviving flows of the affected demands are not sufficient to satisfy the required demand volume can be expressed as:

d p ≤ h d c, s ∈ S , d ∈ ¯ , (7.3) ∑ x 0 s D s p∈P s
for a very small c > 0. Nevertheless we have deliberately chosen to not introduce this constraint into the EFR-PF formulation (7.2) 1 . In practice, the EPRF-PF formulation (7.2) solved in the first iteration of the algorithm does not contain constraints (7.2e). Having a solution, we check each demand d ∈ D if it satisfies (7.3). If constraint (7.3) is not satisfied for a particular demand, the demand is added to set D s . At this stage, the obtained solution x remains feasible for the new LP problem. Thus, the heuristic generates a sequence of improving approximate solutions.

Although EFR-PF is an LP, the problem is still not easy to solve because of the possibly exponential numbers of path-flow variables x, u, and v. To avoid the non-compact nature of the formulation, we are forced to generate path on the fly using Path Generation (PG) applied to formulation (7.2). Unfortunately, PG turns out to be a difficult problem as we show in the next subsections.

Dual problem

Let us consider the problem dual to problem (7.2) for a given set of admissible paths P . The dual, denoted by EFR DF(P ), is as follows (for the derivation see for example Pióro and Medhi (2004b)):

EFR-DF(P ): max W = ∑ (h 0 λ 0 + h s λ s ) (7.4a)

d d d∈D π 0 π s ∑ d d s∈S e + ∑
s∈S \{e} e = ξ e , e ∈ E (7.4b)

λ 0 (λ s + aσ s ) + (λ s + bσ s ) d + ∑ d s∈E (d)\p d p ∑ d d p s∈ ¯(d)\p ≤ ∑ s∈S \p λ s s |p| + |p| , d ∈ D, p ∈ P d (7.4c) s d + σ d p ≥ |p| , d ∈ D, p ∈ P d , s ∈ E (d) \ p (7.4d) λ s s s E (d) \ p (7.4e) d σ d p ≤ |p| , d ∈ D, p ∈ P d , s ∈ ¯ λ, π, σ continuous, nonnegative (7.4f)
where, for a given path p ∈ P , we have used the notation |p| = ∑ e p π 0 and |p| = ∑ e p π s . We notice that the optimal solution of (7.4) Observe that if we replace σ s by these values, formulation (7.4) and formulation (7.9) given below have the same sets of feasible variables π and λ. We introduce some additional notation. For d ∈ D, p ∈ P d :

F d ( p) = {s ∈ E (d) \ p : |p| s > λ s } (7.7)
Symmetrically, for d ∈ D, p ∈ P d :

F d ( p) = {s ∈ E (d) \ p : |p| s < λ s } (7.8) ¯ ¯
d Considering (7.5)- (7.8), the transformed formulation of the dual problem is as follows:

max W = ∑ (h 0 λ 0 + h s λ s ) (7.9a) d d d∈D π 0 π s ∑ d d s∈S e + ∑
s∈S \{e} e = ξ e , e ∈ E (7.9b)

λ 0 s s ∆ s 0 d + a ∑ s∈F d ( p) ∆ d p + b ∑ s∈ ¯ ( p) ∆ d p ∑ s∈S \p d p ≤ |p| , with ∆ s d ∈ D, p ∈ P d (7.9c) λ, π continuous, nonnegative (7.9d)
= |p| s λ s , d ∈ D, p ∈ P d , s ∈ S \ p.

Pricing problem

Let ¯ denote the set of all paths in the network graph between o(d) and t(d). The essence of the pricing problem related to the dual problem (7.9) formulated for a given (limited) admissible path-sets P d , d ∈ D, is to check whether for at least one demand d ∈ D there exists a path q ∈ ¯ \ P d (i.e., path q outside the current admissible path-set P d ), for which (7.9c) cannot be satisfied for any set of non-negative dual variables σ s , s ∈ ¯(d) \ q. In fact, this is the case if and only if:

dq E dq + ∑ s∈S \q ∆ s a s∈F d (q) ∆ s b s∈ ¯ (q) ∆ s < 0 (7.10) with ∆ 0 0
The Pricing Problem (PP) for a given π, λ and a given demand d ∈ D is as follows: where minimize lql over q ∈ ˆ (7.11)

lql = ∆ 0 + ∑ dq q a ∑ s s∈F d (q) b ∑ s s∈ ¯ (q)
Observe that if lql < 0 for a path q satisfying (7.11), then the current optimal dual solution π, λ violates the dual constraints (7.9c) for path q. Moreover, the violation is maximal over all paths p ∈ ˆ . Finally, we note that PP is difficult.

In particular, the term s s

∑ s∈S \q ∑ e∈p π e included in ∑ s∈S \q ∆ dq is difficult to deal with. This problem is also known in the literature as the quadratic shortest path problem, since its cost depends not only on the arcs included in the path, but also on the arcs outside. Furthermore it is encountered in the pricing problem of RR known to be N P -hard, see [START_REF] Maurras | Network synthesis under survivability constraints[END_REF][START_REF] Mereu | Primary and backup paths optimal design for traffic engineering in hybrid igp/mpls networks[END_REF][START_REF] Orlowski | Local and global restoration of node and link failures in telecommunication networks[END_REF], Nace et al. 2013) and a survey on path generation [START_REF] Orlowski | Complexity of column generation in network design with path-based survivability mechanisms[END_REF]. In our experiments we have incorporated all potential paths in the initial path set.

Binary formulation of the pricing problem

The pricing problem formulated in (7.11) is difficult because of the particular form of the total dual length lql. Nevertheless, the problem can be stated as a binary programming problem by means of formulation (7.12) given below. In the formulation, binary variables u e , e ∈ E , specify the path q we are looking for: q = {e ∈ E : u e = 1}. Binary variables z s , s ∈ S , in turn, denote if |p| s > λ s . If that is the case, then z s = 1;

otherwise z s = 0. Besides, δ + (v) and δ (v) denote the sets of all links outgoing from, and all links incoming to, respectively, node v ∈ V , constant d indicates a considered demand, node o is its originating node and t is its terminating node.

min L = ∑ u e π 0 + (1 u s )( u e π s λ s ) e∈E e ∑ s∈S ∑ e d e∈E a ∑ z s (1 u s )(1 T s )( u e π s λ s ) s∈S d ∑ e d e∈E b ∑ (1 z s )(1 u s )T s ( u e π s λ s ) (7.12a) s∈S d ∑ e d e∈ ¯ ∑ e∈δ + (o) ∑ e∈δ + (v) u e ∑ e∈δ (o) u e ∑ e∈δ (v)
u e = 1 (7.12b) 7.12e) force each variable z s , s ∈ S , to be equal to 1 when the length, with respect to π s , of the path q defined by variables u is greater than λ s ; and to be equal 0 otherwise. T s are already given from the instance of the problem in hand.

u e = 0, v ∈ V \ {o, t} (7.12c) λ s (1 z s ) ≥ λ s ∑ π s u e ,
To get rid of bi-and tri-linearities involving variables z s and u e in the objective function, we can introduce five binary variables W s , V s , X s , Y s , Z s , e ∈ E , s ∈ S . The objective function should be rewritten as The other failu C re scenarios can be m B anaged in a similar m D anner.

L = ∑ u e π 0 + ( X s π s (1 u s )λ s ) e∈E e ∑ s∈S ∑ e e d e∈E (7.13) a ∑ (1 T s )( Y s π s W s λ s ) b T s ( Z s π s V s λ s ) s∈S d ∑ e
A 1 1 ↗ 2/3 1 (↘ 1/2) 8.1.2 Mathematical formulation of 2 2 ↘ 1/3 EFR PLF -P E 2 (↗ 1/2)
The p 1 r 2 ↘ 1/3 considered in this 2 2

2/3 eferred to as Elas-optimization oblem section is r tic Flow Rerouting Problem for Part A ial Link Failures (EFR PLF -P) B i 3s (↘ a 1 s /3) and follows. We want to minimize the total cost of link capacity assuming that in the nominal state of network operation, all demand volumes are realized by means of nominal path-flows. When the network is subject to a failure of a set of links then the demand volumes, possibly reduced, are realized for the duration of the failure state by appropriate thinning or thickening of the nominal path-flows depending on the state of their demand and the fact that they are perturbed.

The mathematical formulation of EFR PLF -P, inspired from EFR, is given below. In 8.1, the objective function of EFR PLF -P is to minimize the total cost of the network. Constraints (8.1b) do not allow the nominal link loads to exceed the nominal link capacities. Constraints (8.1c) ensure that the nominal flows are sufficient to realize the volume of each demand d ∈ D. In a failure state s ∈ S , the best modulation scheme cannot be used for the affected links as they no longer meet the SNR requirement, see (8.1d)

∑ z s x 0 s s d p + ∑ ¯ s p∈P s d p + M(T d 1) ≤ h d c, s ∈ S , d ∈ D (8.1f) ∑ z s x 0 s s s d p + ∑ ¯ s p∈P s d p + h d T d ≥ h d , s ∈ S , d ∈ D (8.1g) 0 ≤ u s 0 ≤ v s ≤ ax 0 ≤ bx 0 , s ∈ S , d ∈ D, p ∈ P s , s ∈ S , d ∈ D, p ∈ P s (8.1h) (8.1i) 0 ≤ z s u s 0 , d ∈ D, s ∈ S , p ∈ ¯ s s s (8.1j) d p + M(T d 1) ≤ 0, s ∈ S , d ∈ D, p ∈ P d (8.1k) v s s s d p MT d ≤ 0, s ∈ S , d ∈ D, p ∈ P d (8.1l)
x, y, z, u, v continuous, nonnegative, T binary (8.1m)

Note that EFR PLF -P is obviously as difficult as EFR as for total failures it reduces to EFR. This statement holds since Flow Thinning can be applied only for partial failures-it completely disappears when the link failure cuts the traffic entirely (total failure). Therefore the already demonstrated N P -hardness of EFR immediately implies the following corrolary. In practice, EFR PLF -P is intrinsically harder than EFR as it includes two consecutive optimization procedures, namely Flow Thinning of affected flows and Elastic Flow Rerouting for the rest of flows. In the line of the heuristic proposed above for EFR, a similar process can be built for EFR PLF -P.

The source of difficulty is three-fold: first, the combinatorial aspect related to the distinction between the affected and the unaffected demands; second, potentially exponential number of multiple partial link failure states to be considered; third, the difficulty of the associated pricing problem.

Modulation Schemes management

In this section, we adjust the EFR PLF -P problem presented in 8.1 to manage channels modulation.

Each link e ∈ E is assigned a set of usable frequencies W e (7MHz, 17MHz, 28MHz . . . see Table 1.1) and a non-negative cost associated which In a failure state s ∈ S , the best modulation scheme cannot be used for the affected links as they no longer meet the SNR requirement. When e = 1 for w ∈ W e , the link capacity available in state s is assumed to be equal to a given value b ws , e ∈ E , s ∈ S with b ws ≤ b w0 for all s ∈ S . In

P d ), x d p (s ∈ S , d ∈ D, p ∈ P d ), z d p (s ∈ S , d ∈ D, p ∈ ¯ d ), u d p (s ∈ S , d ∈ s s s s P D, p ∈ P s ), v s (s ∈ S , d ∈ D, p ∈ P s ),
∑ z s x 0 s s d p + ∑ ¯ s p∈P s d p + M(T d 1) ≤ h d c, s ∈ S , d ∈ D (8.6f) ∑ z s x 0 s s s d p + ∑ ¯ s p∈P s u s 0 d p + h d T d ≥ h d , s ∈ S , d ∈ D (8.6g) s d p ≤ ax d p , s ∈ S , d ∈ D, p ∈ P d (8.6h) v s 0 s d p ≤ bx d p , s ∈ S , d ∈ D, p ∈ P d (8.6i) d p ≤ x d p , d ∈ D, s ∈ S , p ∈ ¯ d (8.6j) z s 0 P s u s s s d p + M(T d 1) ≤ 0, s ∈ S , d ∈ D, p ∈ P d (8.6k) v s s s d p MT d ≤ 0, s ∈ S , d ∈ D, p ∈ P d (8.6l)
∑

w∈W e e = 1, e ∈ E (8.6m)

x, y, z, u, v continuous, nonnegative, T binary (8.6n)

The main drawback of EFR remains the fact that it is a centralized strategy. In case of failure, it consider that all nodes are aware of the failures and that all paths can be modified. The following section present a distributed version of EFR.

Towards a distributed version of EFR

The EFR strategies is not directly usable in a network restoration process. The main difficulty is storing a large amount of information in each router node. Indeed, EFR can require significant management efforts, since extensive state information (for instance, release/increase of bandwidth according to the failure state) is needed at each routing node to maintain all the nominal routing paths. This may, however, prevent the strategy from scaling in large networks. Applying this method in a restoration process involves releasing the bandwidth of some non-affected nominal paths of non-affected demands. This implies that the respective source nodes of these demands need to know about the failure and the amount of bandwidth to be released (or added) for each nominal path. All this means that a lot of information has to be stored at each node, while each source node has to be informed about the occurrence of failures. One way to handle this problem is to restrict the amount of information stored at each node while omitting to communicate information about the state failure to all routing nodes. Consequently, we propose a modification of the method such that each node acts according to the local information, thus making this method more suitable for distributed environments.

The distributed versions of EFR is described below. The principle of DEFR (Distributed Elastic Flow Rerouting) consists in restricting the restoration to the extremity nodes of affected demands only. This is a natural solution, as these nodes will be aware of the failure and they will quickly be able to react to restore the lost traffic. These nodes may also be source and/or destination nodes for other traffic demands that have not necessarily been disrupted, and thus they can act directly to modify the bandwidth of some paths. The benefit of this method is twofold: first, the state information will concern only a subset of (failure) links; secondly, the nodes concerned with the traffic restoration are informed about the failure without any additional action as they are placed at the extremities of the affected path. In terms of cost-effectiveness, we would expect the DEFR strategy to perform slightly less well than EFR.

Let us illustrate how the DEFR strategy operates using the example 8.2, given below. as traffic requirement for d 1 is no longer met and capacities used by d 2 on link (A,B) cannat be released. DEFR must overdimension link (A,B) with a capacity 1 of 1instead of. The global cast has increase ta :. Thus, DEFR is on general slightly more expensive than EFR but in sorne case, it does not require any additional cast, especially when the set of demands is large.

Notice that implementation issues related to DEFR are present in appendix A. n this chapter, we present results of a computational study illustrating the performance of EFR-P and the heuristic on the total single link failure case problem. followed by some preliminary results for the EFR PLF

Dimensioning cost

We consider undirected networks; thus, the optimization problems are treated in their versions for undirected network graphs. Network instances used in our tests, listed in Table 9.1, are taken from SNDlib [START_REF] Orlowski | SNDlib 1.0survivable network design library[END_REF]). In the table depicted are the number of vertices, edges and demands of each networks, as well as the maximum and minimum degree of the corresponding graphs (∆(G), δ(G)). When solving the problems, we consider sets of all paths for polska, nobel-us, and nobel-germany (as these are low meshed network instances), and all paths with up to 7 links for di-yuan (a highly meshed network with 11 nodes). The study was carried out on a computer equipped with an Intel Xeon CPU E5-2670 2.60GHz processor and 132 GB of RAM, using CPLEX 12.5 (CPLEX 2013).

We recall that although in theory EFR-P gives the exact formulation and solving it should provide the optimal solution of the problem, using big-M coefficients in the formulation yields numerical issues. To handle this, constraints with the big-M coefficients are replaced by appropriate CPLEX indicator constraints.

Below we compare the cost effectiveness of the following traffic protection strategies: Elastic Flow Rerouting (EFR), Path Diversity (PD), Restricted Restoration (RR), i.e., end-to-end rerouting with stub release, and Global Rerouting (GR In the reported experiments, we always use the same traffic reduction ratio β for all demands in all failure states, i.e., h s = βh 0 for all d ∈ D and s ∈ S . We also assume that the decreasing factor a is always equal to 1.0, while the increasing factor b takes values 0.1, 0.5, 1.0, or 3.0, which means that the nominal flows can be increased by up to 10% (resp. to 50%, multiplied by 2, or multiplied by 4). The decreasing and increasing factors are maximum limits applied to each path-flows in case of failures. In our experiments, we have incorporated all potential paths in the initial path set.

Let C GR denote the optimal value of the objective function (i.e., minimum cost of the link capacity) for GR, and C b , C PD , and C RR the respective values for the remaining strategies. Note that C a is computed by solving EFR-P for the assumed thickening factor b. The rest of the costs are computed through solving appropriate optimization problems that can be found for example in (Pióro and Medhi 2004b). Certainly, the computed link capacities (and thus the link capacity cost) ensure routing of all traffic demands in the nominal state and the guaranteed traffic restoration (specified by β) in all failure states. As we already mentioned, the cost C GR , indicated by GR, is not greater than any of the remaining costs, as GR assumes the least restricted flow restoration mechanism. Hence, we can define the relative cost increase for each strategy S (where S stands for EFR, PD, RR, or GR) with respect to GR as G S = C S C G R × 100%. In the following, this quantity will be called the relative gap. Note that, by definition, G GR = 0.

In Table 9.2, for all four network instances, we present G RR , G PD , and EFR , as a function of the traffic reduction ratio β assumed for the failure states. We consider 5 scenarios with different values of β varying from 60% to 100%. In the table, numbers in bold correspond to the scenarios, in which EFR performs better than RR and PD in terms of the cost. Experiments for values of β less than 60% show that for EFR and GR the cost does not increase comparing to the cost of routing the demands in the nominal state.

In Table 9.2, interesting results in terms of the cost-effectiveness are indicated. As expected, the cost of the network for EFR is often lower than C RR for b = 1 for most of β. In fact, C RR can be seen as C +∞ with a = 0. Hence, because increasing b decreases C b , the gain of cost using EFR instead of RR comes from the ability to decrease the bandwidth of paths of unaffected demands. We also notice that the gap between the lower bound-(the cost of C GR ) and C 3.0 remains low, with a maximum of 12.6%. 4 47.8 43.4 31.9 23.9 11.9 0.8 21.0 53.1 48.0 34.9 25.9 12.6 0.9 17.5 60.1 46.9 31.6 22.0 11.4 1.0 9.4 60.2 46.0 30.9 19.7 11.0 0. 6 14.4 47.2 35.5 20.6

Heuristic performance

We now study the efficiency of the heuristic method expressed as a relative gap between the objective function of the EFR-P problem using formulation (7. 9.2. We notice that the heuristic method performs well for all networks indicating the maximum relative gap of less than 2%. However, as this method contains some randomness, the gap with the exact solution can be different if we compute the solution of the heuristic a second time. Still, the heuristic seems to be able to find a solution close to the optimal solution, with a gap not exceeding 2% in most cases. In the table, we present the best obtained gap after running the heuristic for three times. Thus, we notice that the heuristic is usually able to find the optimal solution after just a few repetitions, as indicated by the 0.0 value of the gap (in bold).

Effiency of EFR applied to partial failures

Finally, we study the performance of EFR PLF , i.e., EFR applied to partial failures. Let C GR denote the optimal value of the objective function (i.e., minimum cost of the link capacity) for GR, and C b PLF , C FT the respective values for the remaining strategies. We define the relative cost increase for each strategy S (where S stands for EFR PLF or FT) with respect to GR as K S = C S C G R × 100%. To make a comparison with results for FT and GR possible, some vital changes are needed in the way the capacities are Table 9. between the exact solution and the heuristic solution. we use γy e , e ∈ E , s ∈ S , where γ express the perturbation ratio. The results are given for several levels of perturbation γ: 50%, 75%, and 95%. As no network instance could be solved within a limited period of time (10 hours), we present results of network polska with a limited set of demands: 20 demands instead of 66.

γ K FT K 0. We notice that EFR PLF performs generally better than FT. For lower perturbation ratios, for instance γ = 50%, differences of costs of the network for FT and EFR PLF remains insignificant-the gap between FT and EFR PLF for all values of b is less than 10%. However, if we consider stronger perturbation ratios, for instance γ = 95%, EFR PLF becomes clearly more cost-efficient than FT. When the thickening ratio is very low, for instance 10%, the gap between FT and EFR PLF is equal to 5.7%1 . If we increase the thickening ratio, the gap between FT and EFR PLF reaches 25.7% (b = 3).

Restoration time

We here analyze the solutions given by the EFR, GR and RR strategies in terms of average number of paths, length of the paths and restoration time. Table 9.5 shows the average number of paths in the nominal state, the total number of distinct paths and the number of paths to thick or create. Moreover, the Table shows the average length of the paths, in the nominal state and in the failure states. We notice that even though GR and RR use less paths in the nominal state; nevertheless, the average total number of paths used by these strategies is significantly higher. Note that, for EFR, increasing b seems to decrease the average number of paths and length of paths. EFR 0.5 EFR 1.0 In the following, we study the restoration time of EFR, compared to GR and RR. In the experiment, we use a simplified restoration model that returns a fraction of satisfied demands in a function of time elapsed after the failure. The results are presented in Figures 9.1 and 9.2, where the former represents the ratio of satisfied demands in time in the network polska for a total failure of a link at the border of the network, while the latter presents the same result for a total failure of a link in the center of the network. As expected, EFR leads to a substantial gain in terms of restoration time, roughly two times faster than GR and three times faster than RR. This is mainly due to two factors: EFR do not create new paths and the total number of paths it uses is smaller. Therefore, the time when EFR practically ends the whole restoration process is also the time when GR strategy ends disconnecting flows that are to be rerouted. The reason GR outperforms RR in terms of total restoration time is the average length of restoration paths used by the strategies. The longer restoration paths of RR strategy induce longer restoration times. Another important aspect, mentioned earlier, is the capability of EFR to maintain a high level of satisfaction ratio of demands during the restoration process. From the figures we notice that GR encumbers the process as a lot of routing paths should first be released and others have to be settled from the scratch, while EFR benefits from optimized flow paths at a large part available in most of failure situations. The issue can be perfectly seen in the figures around time 5-7, when the demand satisfaction ratio for GR plunges to merely 50%, while at the same time reaching 100% for EFR and about 85% for RR. This feature is expected to be even more important for partial failure situations.

Conclusion on the efficiency of EFR

When it comes to the relation of link capacity cost, management effort, and traffic restoration time, the EFR and EFR PLF strategies appear to be encouraging, especially when traffic is supposed to be partially restored.

The heuristic seems to perform well, leading to optimal or near-optimal solutions for most network instances used in our tests.

Conclusion and future work

The work done on this thesis led to the design of two recovery mechanisms: Flow Thinning (FT) and Elastic Flow Rerouting (EFR).

FT is an original concept of a traffic routing and protection strategy for communication networks with variable link capacity. Its affine variant, AFT, opens a way for distributed implementations. To our knowledge, similar strategies (working at the logical tunnel level and reacting online to link capacity fluctuations) have not been proposed and therefore studying optimization models for FT and AFT is worthwhile, the more that the related multicommodity flow problems contribute to the area of resilient network design. We have studied in-depth a basic FT optimization problem (FTOP, see Section 4.2), and its affine version (AFTOP, see Section 6.1). FTOP turns out to be N P -hard and its non-compact link-path LP formulation requires path generation for which we have found a quite effectively solvable (though N P -hard) pricing problem. We have also exhibited some special cases when path generation is polynomial and formulated a polynomially solvable algorithm for finding accurate lower bounds for FTOP. The numerical study shows that in terms of cost/traffic efficiency, FT exhibits cost not significantly superior to that of GR-the theoretically most cost efficient strategy, at least when (reasonable) demand reduction coefficients are acceptable.

EFR is based on the concept of elastic (failure state-dependent) pathflows. EFR is designed to handle total link failures, while its extension, called EFR PLF , deals with multiple partial link failures related to broadband wireless (FSO, microwave) networks. When it comes to the relation of link capacity cost, management effort, and traffic restoration time, the EFR strategy appears to be encouraging, especially when traffic is supposed to be partially restored. From the theoretical viewpoint, optimization of EFR gives rise to a challenging multi-commodity flow problem EFR-P, combining two difficult issues: a combinatorial subproblem dealing with the choice of the demand states, and a likely N P -hard pricing subproblem for path generation. To the best of our knowledge, such a problem has not been considered in the literature on traffic protection strategies before. We have introduced an exact MIP formulation of EFR-P that works for a given set of admissible paths, and proposed a fast suboptimal heuristic approach for EFR-P. Looking for an exact approach with a reasonable efficiency will be the subject of our future work. We have also considered the case with partial failures. The corresponding problem, denoted by EFR PLF -P, is even more difficult, since it combines two levels of decisions: at the first level it choses flows that have to be thinned and at the second level it optimizes the way the affected demands can enlarge their flows using resources released from the unaffected demands. All this makes the problem highly combinatorial. Additionally, the corresponding 127 pricing problem is very complicated, as it embraces features coming from two other N P -hard pricing problems: one for FT and the other for EFR.

The above strategies are designed under the consideration of management cost hypotheses. A further study on implementation issues is needed to assess the relevance of such considerations. At this very moment, (July 2015), members of IETF are currently working on a way to manage partial link failures on MPLS networks [START_REF] Long | Rsvp-te signaling extension for links with variable discrete bandwidth[END_REF] and an extension of RSVP-TE signaling is proposed. This extension can be used to set up a label switching path (LSP) that contains links with discretely variable bandwidth. Each link has a set of <capacity, availability> information and paths will have a set of <capacity, availability> requirements. In accordance with above, we are currently looking how the proposed strategies can be implemented.

Finally, from an optimization point of view, the heuristic method for EFR may be improved to obtain solutions of lower cost and an affine version could lead to a problem easier to solve and to a solution resilient to more failure scenarios. Next, the principle of EFR PLF can be applied to other reroute get strategies, namely RR. Then, it is possible to apply FT as proposed and handle the remaining lost traffic with RR. Finally, one of difficulties that one will encounter when dealing with partial failures in fixed wireless networks is the extremely large number of failure states withe respect to weather conditions to be considered. Hence, this calls for robust optimization methods covering a very large part of these states while providing high restoration ratio for the remaining states. We are now looking for an appropriated way of failure state generation through a constraint generation process in an iterative algorithm. A.1 MPLS Networks MPLS (Multi-Protocol Label Switching) [START_REF] Rosen | Multiprotocol label switching architecture[END_REF]) is a mechanism in telecommunications networks which combines IP routing concept of level 3, and level 2 switching mechanisms as implemented in ATM or Frame Relay. The aim of this section is to explain how data are routed and rerouted in such a network. We will not explain MPLS in deep but only the main features as label switching principle, routing protocol and its "standard" rerouting algorithm.

A.1.1 Label Switching

When a packet enters a MPLS network (1), depending of its FEC (Forwarding equivalence class), the ingress node reads its switching table (2), assigns a label to this packet ( 3), and forwards it to the following LSR (4).

MPLS Network

(1) ingress node

(2) switching table When the packet arrives in a LSR inside the MPLS network (1), the routing protocol running on this node finds, in its label database (Label Base Information), the next label to assign to this packet in order to send it to its destination (2). The LSR updates the MPLS header of the packet (switch the label, update the TTL field ...) (3) and sends it to the following node (LSR or egoess node) (4). We can notice that in an internai LSR, 1he routing protocol of the network layer is never used. Finally, once the MPLS packet arrives in the egress node [START_REF]2 Partial failures in logical layers of wired networks[END_REF], the router removes ali MPLS prints (2) and transmits the packet to 1he network layer. Thus, we notice 1hat 1he routing of a demand is made between its extoemity nodes. We now need to find a routing algorithm to find ali needed LSPs to route the traffic.

MPLS Network

A.1.2. Routing Principle

As described above, the routing strategy is based on label switching. A LSR in the MPLS network switches labels by studying the incoming label and port, reads 1he switching table and then sends 1he packet to the next node. Labels are assigned to a packet only once in the border of the MPLS network by an ingress node E-LSR (Edge Label Switch Router) where a cakulation is done on 1he datagram to find 1he specifie label. This cakulation is done only once by the ingress node, depending of its destination. Thus, 1he ingress node chooses the end-to-end routing of the demands.

The routing of a demand is done using RSVP-TE (Resource Reservation Protocol-Traffic Engineering) [START_REF] Awduche | Rsvpte: Extensions to rsvp for lsp tunnels[END_REF]). We will not go further into this routing protocol but we will point out the main characteristics of this routing. Each demand may be routed by one or severa! LSP(s), and every LSP assodaoed to a flow may be configured in order to ensure QoS.

A.2 EFR -Implementation issues

The numerical results clearly show that both "centralized" and distributed ShRR strategies are cost-effective, with results close to that of global rerouting (GR), which is a lower bound of the cost of a network for all routing strategies. In several cases EFR strategies are also more cost-effective than end-to-end rerouting with stub release (RR). Nevertheless, the gap between these strategies and ShRR remains significant. Hence, a natural question here would be: what is the interest of EFR/DEFR strategies? The answer is directly linked to the management cost these strategies will have in practice, as discussed below. Let us focus first on the distributed variant of ShRR, that is to say DShRR. This strategy uses only extremity nodes of affected demands to initiate the recovery process after a failure. We notice that when a failure occurs new paths may have to be created. This action can only be performed by the source node of the demand. This creation of a new path is preceded by decreasing the bandwidth of some paths, which can be performed by both source and destination nodes. Unlike the DShRR strategy, DERR does not need to create new paths to recover the traffic after a failure. This strategy only increases or decreases the bandwidth of some (possibly) affected paths to recover the traffic. It is a feature of great interest, since the restoration delay is significantly reduced in comparison to DShRR. To show this, let us describe in detail the process of creation of a new path.

Depending on the transport protocol, establishing a new path from the node source to its destination will have a cost which greatly depends on the number of links. Let us look how this is accomplished using the Resource Reservation Protocol (RSVP) (see (Braden et al. 1997, Braden andZhang 1997)). First, the source node sends a PATH message, which contains the required flow parameters (TSPEC), to the destination node using the routing protocol. Then, every visited router has two operations to perform: storing the PATH-STATE, i.e. the message received from the last node to have transmitted the message, and modifying the ADSPEC field, i.e. the flow parameters, when the required bandwidth is not available. When the destination node receives the PATH message it uses both the TSPEC and the ADSPEC fields to determine the parameters of the flow, and sends the flow descriptor, using a RESV message, to the source node using the same path as the PATH message. Finally, the source node sends a RESV-CONF message to the destination node validating the opening of the flow. This means that the time needed to create a new path is almost 3 times as long as the time needed to transfer data from the source to the destination node (c denotes the end-to-end transfer time). In contrast, the time required for decreasing or increasing the bandwidth is significantly lower. In order to maintain the flow, periodically, the source node sends a PATH message to the destination node, and the destination node sends a RESV message to the source node. The flow parameters included in these messages can be modified to increase or decrease the bandwidth of the path. We will use this property to perform bandwidth modification for DShRR and DERR. Hence, if the destination node of some affected demands initiates the decreasing (resp. decreasing/increasing) process for DShRR (resp. DEFR), the time needed will be equal to c. This is possible, since the source can use the updated path immediately after receiving the PATH message from the destination node (Figure A.4.a). If it is the source node that initiates the process, the time needed to modify the bandwidth is equal to 2c, because the source node has to wait for the confirmation before using the updated path (Figure A.4.b). It will be remarked that this procedure cannot be employed to create a new path. In both strategies it is important to begin by decreasing the bandwidth of paths of non-affected demands, before increasing the bandwidth of nonaffected paths of the affected demands. Indeed, before the bandwidth of any path is increased it must be certain that there is sufficient available bandwidth, otherwise the process will fail and must be restarted. This situation is depicted in The DEFR strategy would thus appear to be faster than other endto-end rerouting strategies that employ new rerouting paths, including DShRR.

A.3 SNDlib -Graph details

SNDlib [START_REF] Orlowski | SNDlib 1.0survivable network design library[END_REF]) is a library of test instances for Survivable fixed telecommunication Network Design. Its purpose is to make realistic network design test instances available to the research community and to serve as a standardized benchmark for testing, evaluating, and comparing network design models and algorithms. In the document, we use undirected networks pdh, di-yuan, polska, nobel-us and nobel-germany. TableA.1 represents the number of vertices, edges and demands of each networks, as well as the maximum and minimum degree of the corresponding graphs (∆(G), δ(G)).

network

|V In the sequel of this section, we present the topology of all five networks.

  129 A.1 MPLS Networks . . . . . . . . . . . . . . . . . . . . . . . . . 130 A.1.1 Label Switching . . . . . . . . . . . . . . . . . . . . . . . A.1.2 Routing Principle . . . . . . . . . . . . . . . . . . . . . . A.2 EFR -Implementation issues . . . . . . . . . . . . . . . . . A.3 SNDlib -Graph details . . . . . . . . . . . . . . . . . . and Motivation . . . . . . . . . . . . . . . . . . . . .

3 1 . 1 . 1 6 1. 3

 11163 Wireless communications . . . . . . . . . . . . . . . . . . . 3 1.1.2 Wired networks . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Our contribution . . . . . . . . . . . . . . . . . . . . . . . . . . Outline of this thesis . . . . . . . . . . . . . . . . . . . . . . . 7 he work done in this thesis has taken place in the Heudiasyc laboratory, in the Université de Technologie de Compiègne. It was financed by the French Ministry of Higher Education and Research with the support of the Labex MS2T of the UTC. This thesis focuses on network dimensioning problems, and more specifically on the design of recovery mechanisms to manage the traffic in case of failures.

Figure 1 . 1 -

 11 Figure 1.1 -Adverse weather conditions decrease wireless channel capacity.

Figure 1 . 2 -

 12 Figure 1.2 -Partial failures in logical layers of wired networks.

Figure 2 . 1 -

 21 Figure 2.1 -Classification of recovery mechanisms from the literature.

Figure 2 . 2 -Figure 2 . 3 -

 2223 Figure 2.2 -The network.consider a network with 5 nodes A, B, C, D and E and 7 links (A,B), (A,C), (B,C), (B,D), (B,E), (C,D), (D,E). All links have the same unit cost c e = 1 and a capacity of 1 to 2 unit(s). We also consider two demands (A,E) and (A,D), both requiring 1 unit of traffic.

Figure 2 -

 2 4 illustrates the behavior of 1+1 Protection. In the nominal state, two LSPs are set from node A to node E with the same capacity of 1unit of traffic. However, only path {A-B-E} carry out the traffic of the demand. Once link (B,E) fails, the traffic is switched to path {A-C-D-E}.

Figure 2 . 4 -

 24 Figure 2.4-1+1 Protection be fore (lejt) and after (right) failure of link (B,E).

  protection[START_REF] Mannie | Recovery (protection and restoration) terminology for generalized multi-protocol label switching (gmpls)[END_REF] has N working LSPs carrying normal traffic and M protection LSP that may carry extra-traffic.

Figure 2 . 5 -

 25 Figure 2.5 -N:M Protection before (left) and after (right) failure of link (B,E).

Figure 2 .

 2 Figure 2.5 illustrates the behavior of N:M Protection with N = 2 and M = 1. In the nominal state, three LSPs are set from node A to node E with the same capacity of 1 unit of traffic. Paths drawn in black {A-B-E} and {A-C-D-E} are working LSPs, while the path drawn in dark gray {A-B-C-D-E} is a protection LSP and the egress node E selects the traffic from one of these two working paths. Once link (B,E) fails, if the traffic was taken from path {A-B-E} then E must change its selected path to {A-C-D-E} or {A-B-C-D-E}. However, if the traffic was taken from another path, nothing is changed.

Figure 2 . 6 -

 26 PD before (left) and after (right) failure of link (B 1 E).

Figure 2 . 7 ,

 27 we observe that when link (B,E) fails, the primary LSP of demand (A,E) remains the same from node A to node B. The perturbed traffic is rerouted on path {B-D-E}, from the upstream node of the failed link to its downstream node, which in our example is the egress node of the demand.

Figure 2 . 7 -

 27 Figure 2.7-Local Rerouting before (left) and after (right) failure of link (B 1 E).

Figure 2 .Figure 2 . 8 -

 228 Figure 2.8 illustrates the GR strategy. In the nominal state, a LSP {A-B-E} is set for demand (A,E) and another LSP {A-C-D} is set for demand (A,D). When link (B,E) fails, all LSPs are removed. New LSPs are created

Figure 2 .

 2 Figure 2.10-RR-before (lejt) and after (right) Jailure oflink (B,E).

Figure 2 .

 2 Figure 2.11 -ShRR before (lejt ) and after ( right ) Jailure o f link (B,E).

Figure 2 .

 2 Figure 2.12 -MPLS Fast Reroute before (left) and after (right) failure of link (B,E).

Figure 2 .

 2 Figure 2.12 shows how MPLS Fast Reroute works. A path is established to route the traffic from node A to node E. When link (B,E) fails, the traffic is temporary rerouted from node B to the demand destination E. A few milliseconds later, the ingress node A reroutes all the traffic on path {A-C-D-E}.

Figure 2 .Figure 2 .

 22 Figure 2.13 -PR before (left) and after (right) failure of link (B,E).

Figure 2 .

 2 Figure 2.15-GR before (lejt) and after (right) Jailure of link (B 1 E).

2 (

 2 Study of the nominal state Now we introduce the basic problem related to the nominal routing. The network dimensioning problem is to find a feasible flow minimizing the overall cost of the network i.e. the sum of the cost of the links of the network. The problem can be represented by the following edge-node linear programming (LP) formulation involving variables f d (d ∈ D, e ∈ E ), and y 0 (e ∈ E ): min C = ∑ ξ e y 0

  λ) as vectors in the R N space of dimension N = |E | + |D|), and observe that Π(P ) is a fully dimensional subset of R N .

  capacities. Next, the demand constraint (3.6c) assures that the flows are sufficient to realize the volume of each demand d ∈ D.

  δ ed p x d p ≥ 0, e ∈ E(3.11b)

  the demand is unaffected. The status (affected/unaffected) of demand d ∈ D in failure state s ∈ S is represented, by a binary variable T s , d ∈ D, s ∈ S : T s = 1 if d is d d an affected demand in s and T s = 0 if d is not affected in s. In failure state s ∈ S , unaffected demands d ∈ D s can only thin their unaffected pathflows (concerning only paths in P s ) and affected demands d ∈ ¯ s can d D reroute the perturbed path-flows. The formulation of the dimensioning problem for path diversity, denoted P ShRR (P ), is a follows:

  Contents

4. 1

 1 Introduction to Flow Thinning . . . . . . . . . . . . . . . . 42 4.2 FTOP-the basic FT optimization problem . . . . . . . . . .

44 4 . 2 . 1

 421 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.2.2 Formulation of FTOP . . . . . . . . . . . . . . . . . . . . . . 46 4.2.3 Complexity of FTOP and global rerouting . . . . . . . . . 47 4.3 Dual problem and dual separation . . . . . . . . . . . . . . 48 4.3.1 Dual problem formulation . . . . . . . . . . . . . . . . . . . 48 4.3.2 Dual separation . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.4 Path generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.4.1 Pricing problem . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.4.2 Binary formulation of PP . . . . . . . . . . . . . . . . . . . 53 4.4.3 PG algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.5 Computational complexity of PP, DSP, and special cases 55 4.6 Single-link failures . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.6.1 Single-link failures -compact FTOP formulation . . . . . 57 4.6.2 Single-link failures -proof of Lemma 3 . . . . . . . . . . . 59 4.7 Single-node failures . . . . . . . . . . . . . . . . . . . . . . . . 60 4.7.1 Single-node failures -the pricing problem . . . . . . . . . 60 4.7.2 Single-node failures -compact FTOP formulation . . . . . 63

Example 4 . 1 Figure 4 . 1 -

 4141 Figure 4.1 -FTS -Nominal State.

Figure 4 .

 4 Figure 4.2 represents the failure of link (C, D). In this scenario, the capacity 1 of link (C, D) decreases down to . Hence, the basic solution is to decrease the 2 bandwidth of path p 4 (the only path routed through (C, D)) by 50%. Hence, capacity constraints are respected and all traffic requirements are met.

A

Figure 4 . 2 -

 42 Figure 4.2 -FTS -Failure of link (C, D).

  s

Figure 4 • 3 -

 43 Figure 4•3-FTS-Failure of link (A, B).

Figure 4 - 4 -

 44 Figure 4-4 -Evolution of the optimal cast of the network using FTS depending on the failure coefficient.

FTOP 1 vFigure 4 . 5 -Example 4 . 2 2

 145422 Figure 4.5 -A simple network example

U

  d∈D P d ) and represented by the following link-path linear programming (LP) formulation involving variables x 0 s 0 d p (d ∈ D, p ∈ P d ), x d p (d ∈ D, p ∈ P d , s ∈ S ) and y e (e ∈ E ):

  for multiple total link failure scenarios. More precisely, the PD optimization problem (and thus FTOP) is N P -hard already for undirected graphs with |V | = L + 1 nodes, |E | = 2L links, one demand (|D| = 1), and |S | = L failure states (each such state consists of simultaneous failures of e P ∑ σ s e a certain subset of links). Consequently, FTOP cannot be formulated as a compact linear program (unless P = N P ). Yet, whenever admissible paths in P are predefined and |P | is polynomial with the size of the network, then problem P(P ) becomes polynomial as (4.1) becomes compact (provided |S | is polynomial).

  e∈E s ed p e , s ∈ S , d ∈ D, p ∈ P d (4.2d) π, λ, σ ≥ 0 and continuous. (4.2e) Let Π(P ) denote the dual polyhedron of all feasible solutions (π, λ, σ) of D FT (P ), where π = (π 0 , π s , e ∈ E , s ∈ S e ), λ = (λ s , d ∈ D, s ∈ S ), σ s , d ∈ D, p ∈ P d , s ∈ S ). We treat the dual solutions (π, λ, σ) as vectors in the R N space of dimension N = |E | + ∑ e |S e | + |D| • |S | + (∑ d∈D |P d |) • |S |, and observe that Π(P ) is a fully dimensional subset of R N . The projection of polyhedron Π(P ) onto the (π, λ) space R n , where

1 :

 1 Define initial admissible path-lists P d , d ∈ D, and P := U P , π, λ, d) formulated in (4.14) 7:

4

 4 Consider for the network described in Example 4.2 and depicted in Figure 4.5 with the two sets of admissible paths reduced to P = P 1 ∪ P 2 where P 1 = {p 11 } and P 2 = {p 21 }. One of the optimal solutions of the resulting instance P(21 = 2, x 11 = x 12 = 1, s ∈ S , y 1 = y 2 = 2, y 3 = y 4 = 0, C = 4.

  failures -compact FTOP formulationA compact node-link FTOP formulation for a given single-link failure scenario S = S 0 ∪ S 1 , where S 1 = U e∈E S (e), is as follows.

  ed , d ∈ D, e ∈ E , s ∈ S (e) (4.20h) all variables x 0 , X 0 , z, y 0 continuous and nonegative.(4.20i) In the formulation, variables x 0 , e ∈ E , are the link-flows of demand d ∈ D(realizing its nominal path-flows), while variable X 0 expresses the overall flow of demand d from o(d) to t(d) (realized by its nominal path-flows).Variables z s , e ∈ E , d ∈ D, s ∈ S (e), in turn, specify the amount of linkflow by which the nominal link-flow x 0 is reduced in state s ∈ S (e). Constraints(4.20b) and (4.20c) are conservation equations for the nominal link-flows. Capacity constraint (4.20d) assures that the nominal link loads do not exceed the maximum link capacities, and constraint (4.20g) assures that the capacity available on link e ∈ E is not exceeded by its loads in its failure states. Demand constraints (4.20e) and (4.20f) take care about satisfaction of the assumed demand volumes in the maximum states and the single-link failure states, respectively. Finally, constraint (4.20h) bounds the possible link-flow reductions.In the case of a failure of a single link, say of link e t ∈ E in one of its failure states s ∈ S (e t ), any given pattern of nominal path-flows realizing the nominal link-flows x 0 , e ∈ E , for a given demand d ∈ D, can be properly thinned according to the values of z s , d ∈ D. Let P d and L d be the sets of elementary o(d) t(d) paths and loops, respectively, assigned nonzero path/loop-flows x 0 when realizing the nominal link-flows x 0 , e ∈ E , of a given demand d ∈ D (such sets of paths and loops exist, see Theo-[START_REF] Korte | Combinatorial Optimization Theory and Algorithms[END_REF]). Because ∑ p∈P d x d p = X d , due to constraints (4.20f) and (4.20g), we can apply thinning for any given failure state s ∈ S (e t ) only to the nominal path-flows in P d (and not to the loops in L d ) containing the failing link e t . Let then Q e t d ⊆ P d denote the set of 0 0 paths that contain the considered link e t , so that ∑ p∈Q e t d x d p = x e t d . We can consistently thin down the nominal path-flows through link e t in the d 0 d p := x d p 0 e t d • x d p , p ∈ Q e t d . (4.21)

2 Figure 4 . 6 -

 246 Figure 4.6 -A network example with a loop in the optimum link-flow

  s ∈ S (e) and e ∈ q and π e > λ d . Now we make use of the link weights ω(e), e ∈ E , specified by(4.19) in the formulation of Lemma 3:ω(e) = π 0 + max{π s , λ s }. (4.26) e By (4.26) and (4.25) we have ∑ ω(e) = |q| 0 + ∑ ∑ e d s∈S (e)∑ \ql s = |q| 0 + ∑ \ql s ,

4 . 7 . 1

 471 node failures scenario consists of the states with limited availability of the links incident to one single node. Thus, a single-node failure scenario S is composed of a set of maximum states and a set of singlenode failure states: S = S 0 ∪ S 2 , where S 0 is a set of maximum states, and S 2 := U v∈V S (v) is a set of single-node failure states. Each set S (v), if not empty, represents a set of states in which only node v fails. That is,s ∈ S (v) implies that α s ≤ 1, e ∈ δ(v), α s = 1, e ∈ E \ δ(v),and α s(v) < 1 e e e for at least one e ∈ δ(v) (where δ(v) := δ (v) ∪ δ + (v)). If node v does not fail at all, then the set S (v) is empty. Single-node failures -the pricing problem In the single-node failure scenario the pricing problem (4.13) is also polynomial. To apply shortest path computation to solve PP, we consider, for each d ∈ D, a transformed graph ˆ (d) = ( ˆ (d), ˆ(d)), constructed from G V E the original network graph G = (V , E ) by exchanging, in a way, the roles of nodes and links. The transformation is illustrated in Figures 4.7and 4.8 for a demand d from node o to node t. The original graph G is depicted on the left-hand side while the transformed graph ˆ (d) is shown on the right-hand side.

Lemma 4 Figure 4 . 8 -

 448 Figure 4.7 -Original graph G

A

  compact node-link FTOP formulation for a given single-node failure scenario S = S 0 ∪ S 2 , where S 2 = U v∈V S (v), is given in 4.37. Below, D(v) := {d ∈ D : v ∈ / {o(d), t(d)}} denotes the set of all demands for which node v is a transit node. Similarly D (v) := {d ∈ D : v = t(d)} and D + (v) := {d ∈ D : v = o(d)} denote the sets of demands with v as the destination node and the originating node, respectively. Transit flow variables w v , v ∈ V \ {o(d), t(d)}, e ∈ δ (v), e + ∈ δ + (v), specify the amount of nominal flow realizing demand d traversing its transit node v via links e and e + . Next, variables z s , v ∈ V \ {o(d), t(d)}, e ∈ δ (v), e + ∈ δ (v), s ∈ S (v), specify the amount of flow by which the portion of the nominal flow X 0 of demand d traversing its transit node v via links e and e + is reduced when node v fails in state s ∈ S (v). Further, variables Z s , d ∈ D, e ∈ δ (t(d)), s ∈ S (t(d)), specify the amount of flow by which the portion of the nominal flow X 0 of demand d entering its destination node t(d) via link e is reduced when node t(d) fails in state s ∈ S (t(d)). Finally, variables Z s , d ∈ D, e ∈ δ + (o(d)), s ∈ S (o(d)), specify the amount of flow by which the portion of the nominal flow X 0 of demand d leaving its originating node o(d) via link e is reduced when node o(d) fails in state s ∈ S (o(d)).

Example 4 . 6 Figure 4 . 9 -

 4649 Figure 4.9 -A network example volume h) between nodes o and t can be realized on 4 paths: p 1 = {1, 3}, p 2 = {1, 4}, p 3 = {2, 3}, p 4 = {2, 4}. We consider a single-node failure scenario with 4 states s = 1, 2, 3, 4 characterized by the sets of failing links E 1 = {2, 4}, E 2 = {2, 3}, E 3 = {1, 4}, E 4 = {1, 3}. (Note that the four availability states can be considered as four different failures of node v.) The availability coefficients of all the failing links in all the states are equal to α. The demand has the nominal volume and the volumes in the states all equal to h. Note that in each state s = 1, 2, 3, 4 only path p s remains unaffected.It is clear that in terms of link capacity the optimal solution of the lower bound formulation (5.1) is unique and symmetric. Hence, a simple cut-based argumentation implies that the common optimal value y 0 of the link capacity must fulfil the equality y 0 + αy 0 = h, that is, y 0 = h 1+α . The common value x 0 for the optimal nominal link-flows is equal to y 0 . In each state, the optimal link-flows on the links with reduced capacity are equal to hα , while on the fully available links-to 1 h . Hence, the optimal LBP objective function value is equal

  efficiency of flow thinning . . . . . . . . . . . . . . . . 68 5.1.1 Single partial link failure scenarios . . . . . . . . . . . . . . 69 5.1.2 Single partial node failure scenarios . . . . . . . . . . . . . 70 5.1.3 Double partial failure scenarios . . . . . . . . . . . . . . . . 72 5.2 Computational efficiency of flow thinning optimization 73 5.2.1 Path generation . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.2.2 Evolution of the PG iterations . . . . . . . . . . . . . . . . . 74 5.2.3 Running times . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.3 A lower bound formulation . . . . . . . . . . . . . . . . . . . 77 5.3.1 LBP -Lower Bound Problem . . . . . . . . . . . . . . . . . 77 5.3.2 Comparing LBP and FTOP . . . . . . . . . . . . . . . . . . 77

Figure 5 . 1 -

 51 Figure 5.1 -Rainfall radar over Poland for network polska.

Figure 5 . 3 -

 53 Figure 5.3 -Relative gap between GR and FTS depending on the availability coefficient α for network polska (link failures).

Figure 5 . 5 -

 55 Figure 5.5 -Relative gap between GR and FTS depending on the availability coefficient α for network nobel-germany (link failures).

Figure 5 . 6 -

 56 Figure 5.6-Relative gap between GR and FTS depending on the availability coefficient IX for network polska (node failures).

Figure 5 . 8 -

 58 Figure 5.8 -Relative gap between GR and FTS depending on the availability coefficient IX for network nobel-germany (node failures).

Figure 5 .

 5 Figure 5.10 -Relative gap between GR and FTS depending on the availability coefficient α for network polska (double links failures).

Figure 5 .Figure 5 .

 55 Figure 5.11 -Value of the objective function and number of paths added at each iteration for pdh.

Figure 5 . 13 -

 513 Figure 5.13 -Value of the objective function and number of paths added at each iteration for nobel-us.

  e y e , e ∈ E , s ∈ S e(5.1g) all variables x, y 0 continuous and nonnegative.(5.1h)Note that for any demand d ∈ D, the value of flow x 0 = (x 0 , e ∈ E ), i.e.,

  .7 for polska and nobel-us, respectively. The tables show the ratios C FTOP /C LBP and T FTOP /T LBP . The quantities C FTOP and C LBP are the optimal costs for FTOP and for LBP, respectively, while T FTOP and T LBP are the respective running times. The results indicate that for the DL case the LBP cost is only marginally smaller than the FTOP cost, and that LBP becomes extremely time consuming. The reason for that large difference in running times is two-fold. First, assuming the common case |D| ~ |V | 2 and |E | ~ |V |, in the node-link formulation (5.1) the number of variables and constraints is of the order of O(|V ||D||S |) = O(|V | 3 |S |). At the same time, for a given set of admissible paths P with |P d | ≤ P, d ∈ D (where P is bounded and does not increase with the size of the network), the FTOP formulation (4.1) requires O(|P ||S |) variables and O(|P ||S |) = O(|P ||S |) constraints, that

P 6 FTS 1

 61 Affine versions of FTS . . . . . . . . . . . . . . . . . . . . . . . 81 6.1.1 Affine flow thinning and the related version of FTOP . . . 82 6.1.2 Restricted affine flow thinning . . . . . . . . . . . .

  A d p (α ) = z d p + ∑ z d p α e , d ∈ D, p ∈ P d .(6.1) e∈E Note that parameters z 0 e , e ∈ E , of the affine function A d p specified for the given path p ∈ P d do not depend on the state s. The AFT version of dp ,

  A d p (α ( p)) = z d p + ∑ z d p α e , d ∈ D, p ∈ P d , (6.2) e∈p where α s ( p) = (α s , e ∈ p). Clearly, RAFT involves less variables z than AFT (an advantage), but it is not necessarily as efficient as FT, in particular for sets S with |S | ≤ |E | + 1 (a disadvantage).

  A d p (α ( p)) = z d p + ∑ e∈E t ( p) z d p α e , d ∈ D, p ∈ P d , (6.3) where α s ( p) = (α s , e ∈ E t ( p)), E t ( p) := U of all nodes visited by path p ∈ P d . v∈V ( p) δ(v), and V ( p) is the set 6.2 Implementation issues

Figure 6 . 1 -

 61

Figure 6 . 4 -

 64

Figure 6 . 5 -Figure 6 . 6 -

 6566 Figure 6.5 -Average number of distinct paths per demand used by FAS per single partial link failure (α = 0.5).

Figure 6 . 7 -

 67 Figure 6.7-Evolution of the ratio ofperturbed demands for polska (IX = 0.5).

  Contents

7. 1

 1 Introduction to Elastic Flow Rerouting . . . . . . . . . . 97 7.2 Mathematical model of EFR . . . . . . . . . . . . . . . . . . . 100 7.2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 7.2.2 EFR-P formulation . . . . . . . . . . . . . . . . . . . . . . . 101 7.3 Complexity discussion . . . . . . . . . . . . . . . . . . . . . . . 102 7.4 Heuristic method . . . . . . . . . . . . . . . . . . . . . . . . . . 105 7.4.1 Description of the heuristic . . . . . . . . . . . . . . . . . . 106 7.4.2 Formulation of EFR-PF problem . . . . . . . . . . . . . . . 107 7.4.3 Dual problem . . . . . . . . . . . . . . . . . . . . . . . . . . 108 7.4.4 Pricing problem . . . . . . . . . . . . . . . . . . . . . . . . . 109 7.4.5 Binary formulation of the pricing problem . . . . . . . . . 110

Example 7 . 1

 71 Consider a network with 5 nodes A, B, C, D and E and 8 undirected links ( A, B), ( A, C), ( A, E), (B, D), (B, E), (C, D), (C, E) and (D, E). The unit capacity cost of all eight links is equal to 1. We consider two demands d 1 and d 2 (each with demand volume equal to 1) between nodes A and E for d 1 and A and D for d 2 .

Figure 7 . 1 ,

 71 demand d 1 is realized on 3 paths: d 1 is routed on 3 paths: p 1 = {A 1 E} with 1 flow value, p 2 = {A B E} and p 3 = {A C E} with 3 flow value; while d 2 is routed on 2 paths: p 4 = {A B D} and p 5 = {A C D} 2 both with 3 flow value.

Figure 7 .

 7 Figure 7.2 represents the failure of link ( A, C). Due to the failure, the traffic requirement for d 2 is no longer meet and there is no bandwidth remaining on

Figure 7 - 1 -Figure 7 . 2 -

 7172 Figure 7-1-EFR-Nominal State.

  failure scenario s ∈ S , allowed to thin D s their path-flows. A demand is unaffected if, by definition, it is not affected. s value of thinned path-flow associated to path p ∈ P s for d p demand d ∈ D s in falure state s ∈ S s value of thickened path-flow associated to path p ∈ P s for d p demand d ∈ ¯ s in falure state s ∈ S binary variable representing the status (affected/unaffected) of s demand d ∈ D. T s = 1 if d is an affected demand in s and d = 0 if d is not affected in s. Note that the thinning/thickening state-dependent path-flows u s s s d p , v d p , s ∈ S , d ∈ D, p ∈ P d , are optimization variables and are bounded by ratio a ≤ 1 (resp. b ≥ 0) of their nominal values, or by 0 depending on the status of the demand.

)

  .1) for a given list of admissible path sets P d , d ∈ D.EFR-P(P ): minC = ∑ ξ e y e d p + v d p ) ≤ y , s ∈ S , e ∈ E \ {s} (7≥ h s , s ∈ S , d ∈ D (7.1e) s p∈P s d p + M(T d 1) < h d , s ∈ S , d ∈ D p + h d T d ≥ h d , s ∈ S , d ∈ D ≥ 0, s ∈ S , d ∈ D, p ∈ P d (7.1h) s d p + M(T d 1) ≤ 0, s ∈ S , d ∈ D, p ∈ P d (d ≤ 0, s ∈ S , d ∈ D, p ∈ P d (7.1j)

  releasing by more than the fraction a of the nominal flow assigned to a path, or increasing by more than the fraction b of the nominal flow. The values of a and b are fixed parameters with 0 ≤ a ≤ 1 and b ≥ 0. Constraints(7.1f) assure that the binary variable T s takes value T s = 1 ifd d

Figure 7 - 4 -

 74 Figure 7-4-Network instance proving NP-hardness of EFR.

Algorithm 4 :

 4 Heuristic method for EFR-P Step 0: Initialization of path-sets Define initial admissible path-sets P d ⊆ ¯ , d ∈ D. Step 1: Initialization of demands status Put D s := ∅, s ∈ S . Step 2: Solving EFR-PF Let x be the resulting solution. Set D s (x): the set of unaffected demands corresponding to solution x. Step 3: Update demands states If D s = D s (x), s ∈ S , then go to Step 4. Otherwise, D s := D s (x), s ∈ S , and go back to Step 2.

  ): min C = ∑ ξ e y e (7.2a) e∈E [π 0 ] ∑ ∑ δ ed p 0 ≤ y e , e ∈ E δ ed p s + ∑ ∑ δ ed p s d∈D p∈P s d∈D s p∈P s d∈ ¯ p∈P s

  a and b are fixed parameters with 0 ≤ a ≤ 1, b ≥ 0. In the formulation, the quantities in brackets to the left are dual variables associated with constraints. All these variables are, by assumption, non-negative.

F

  Figure 8.1, Demand d 1 is realized on 2 paths: p 1 = {A E} , p 2 = {A B D E} 1 with respectively 1 and 4 1 flow value; and demand d 2 is routed on 2 paths: p 3 = 3 {A B D} with 2 flow value, p 4 = {A C D}, with 4 flow value . ig 1 u 1 r e18/.31 -EFR -N o m 2 1 in al

2 1 1 2 -

 212 is not affected by the failure, it releases of bandwidth on path p 3 (enough 4 bandwidth is remaining of path p 4 ). unit of bandwidth is now available on 4 1 links ( A, B) and (B, D) and the bandwidth of p 2 is increased to 2 to meet traffic requirement of d 1 . Then, both demands are fully operational. EFR -Partial Failure of link ( A, E).

Figure 8

 8

Corollary 8 . 1

 81 The EFR PLF problem represented by(8.1) is N P -hard.

  the frequency, ξ w , w ∈ W e . The capacity of link e, denoted by y e , is determined by the combination of the modulation and the w0 w w0 frequency (y e = ∑ w∈W e b e y e ), where b e gives the bandwidth efficiency coefficient used in optimal conditions while in degraded conditions (partial failure s) this is given by b ws < b w0 which leads to a decreased capacity e e of the link. The objective of EFR PLF -P is to minimize the total cost of the network. Hence, 8.1a is modified as follows: C = ∑ ∑ ξ w y w . state, constraint 8.1b do not allow the nominal link loads to exceed the nominal link capacities. The nominal capacity of link e is now equal to b w0 , where w ∈ W e and y w = 1 e ∑ ∑ δ ed p x 0 e ∑ e y e , e ∈ E

  a failure state more than one link can have its availability ratio decreased by the modulation scheme. The following constraints assure that in each failure state s ∈ S , the surviving capacity of each link e ∈ E is not exceeded. δ ed p z s ∑ e y e , s ∈ S , e ∈ E d∈D p∈ ¯ s d p ≤ w∈W e b ws w Hence, for given sets of admissible paths P d , d ∈ D, problem EFR PLF -P can be represented by the path-flow mixed-integer programming (MIP) formulation involving nonnegative continuous variables x 0 (d ∈ D, p ∈

Example 8 . 2 4 (Figure 8 . 3 -

 82483 Figure 8.3 -EFR -Nominal State.

Figure 8 .

 8 Figure 8.4 represents the failure of link (B, E). Clearly, this example is very similar the management of the failure of link ( A, E) in Example 8.1. However, when considering DEFR, the two examples are very different. When link (B, E) fails, node B and E are aware of the failure as they are extremity nodes of demand d 1 , which has disturbed paths. In example 8.1, demands d 1 and d 2 shares the same source node. Hence, paths of d 2 can be thinned if required. The 18 solution cost remains the same, with a global cost of . 4 In this new example, demand d 2 can be modified only by node A and D, which are not aware of the failure. Solution of EFR depicted in Figure 8.4 is not feasible

Figure 8 - 4 -

 84 Figure 8-4-EFR-Partial Failure oflink (B, E).

  cost . . . . . . . . . . . . . . . . . . . . . . . . . . 121 9.2 Heuristic performance . . . . . . . . . . . . . . . . . . . . . . . 123 9.3 Effiency of EFR applied to partial failures . . . . . . . . . 123 9.4 Restoration time . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 9.5 Conclusion on the efficiency of EFR . . . . . . . . . . . . . 126

  1) (denoted C b ) and the cost achieved by the heuristic algorithm b EFRH and C b -as a function of the traffic reduction ratio. The results are given for the settings used in Table

  affected by the perturbation for EFR PLF . Instead of variables y w , e ∈ E , w ∈ we use y , e ∈ E . By extension, instead of b ws y w , e ∈ E , w ∈ W ,

Figure 9 . 1 -

 91 Figure 9.1 -Demand satisfaction ratio of the network polska after failure of Kolobrzeg-Szczecin (at the border of the network).

Figure 9 . 2 -

 92 Figure 9.2 -Demand satisfaction ratio of the network polska after failure of Lodz-Warsaw (in the center of the network).

(

Figure A. 1 -

 1 Figure A.1 -Ingress Node in MPLS network.

Figure A. 2 -

 2 Figure A.2 -Label Switch Router (LSR) in MPLS network.

3 -

 3 Figure A.3-Egress Node in MPLS network.

Figure A. 4 -

 4 Figure A.4 -Bandwidth increase procedure, managed by source node (a) and destination node (b) for DEFR.

FigureFigure A. 5 -

 5 Figure A.5 -Failed attempt to increase the bandwidth of a path managed by source node (up) and destination node (down).

Figure A. 6 -

 6 Figure A.6 -Topology of networks pdh (left) and di-yuan (right).

Figure A. 7 -

 7 Figure A.7 -Topology of networks polska (left) and nobel-germany (right).

Figure A. 8 -

 8 Figure A.8 -Topology of network nobel-us.

  avec le soutien du labex MS2T 4 de l'UTC. Context and Motivation . . . . . . . . . . . . . . . . . . . 1.1.1 Wireless communications . . . . . . . . . . . . . . . . . 1.1.2 Wired networks . . . . . . . . . . . . . . . . . . . . . . . 1.2 Our contribution . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Outline of this thesis . . . . . . . . . . . . . . . . . . . . . Dual problem and dual separation . . . . . . . . . . . . 3.2.2 Path generation . . . . . . . . . . . . . . . . . . . . . . . 3.3 Study of Global Rerouting . . . . . . . . . . . . . . . . . . 3.3.1 Dual problem and dual separation . . . . . . . . . . . . 3.3.2 Path generation . . . . . . . . . . . . . . . . . . . . . . . 3.4 Mathematical formulation of the restoration methods 3.4.1 End-to-end rerouting with stub release -RR + . . . . . . . 3.4.2 End-to-end rerouting without stub release -RR . . . . . 3.4.3 Local Rerouting -LR . . . . . . . . . . . . . . . . . . . . 3.4.4 Path Diversity -PD . . . . . . . . . . . . . . . . . . . . . Application to Fixed Wireless Networks . . . . . . . . 8.1.1 Introduction to EFR PLF and Notations . . . . . . . . . . 8.1.2 Mathematical formulation of EFR PLF -P . . . . . . . . . 8.1.3 Modulation Schemes management . . . . . . . . . . . 8.2 Towards a distributed version of EFR . . . . . . . . . . Introduction to Elastic Flow Rerouting . . . . . . . . . 7.2 Mathematical model of EFR . . . . . . . . . . . . . . . . . 7.2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.2 EFR-P formulation . . . . . . . . . . . . . . . . . . . . . 7.3 Complexity discussion . . . . . . . . . . . . . . . . . . . . . 7.4 Heuristic method . . . . . . . . . . . . . . . . . . . . . . . . 7.4.1 Description of the heuristic . . . . . . . . . . . . . . . . 7.4.2 Formulation of EFR-PF problem . . . . . . . . . . . . . . 7.4.3 Dual problem . . . . . . . . . . . . . . . . . . . . . . . . 7.4.4 Pricing problem . . . . . . . . . . . . . . . . . . . . . . 7.4.5 Binary formulation of the pricing problem . . . . . . . . 110

	Contents Contents I Optimization methods for resilient networks 1 Introduction II Flow Thinning 4 Flow Thinning -Introduction and Optimization Prob-lem 8 EFR -Practical applications to Multiple Link Failures Partial 7 Elastic Flow Rerouting for total link failures 8.1 III Elastic Flow Rerouting 7.1 . . . . . . . . . 1.1 i i 95 .

2 Background and Literature Review 2.1 Introduction to Recovery Mechanisms . . . . . . . . . . 11 2.2 Strategies for total link failures . . . . . . . . . . . . . . 14 2.2.1 Protection Strategies . . . . . . . . . . . . . . . . . . . . 14 2.2.2 Restoration Strategies . . . . . . . . . . . . . . . . . . . 15 2.2.3 MPLS feature -MPLS Fast Rerouting . . . . . . . . . . . 19 2.3 Strategies for partial link failures . . . . . . . . . . . . 19 2.3.1 Probabilistic Routing -PR . . . . . . . . . . . . . . . . . 19 2.3.2 Elastic Traffic Flows -ETF . . . . . . . . . . . . . . . . . 20 2.3.3 Global Rerouting -GR . . . . . . . . . . . . . . . . . . . 20 2.3.4 MPLS feature -MPLS TE Auto-bandwidth Adjustment . 3 Network Dimensioning Problem 3.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Study of the nominal state . . . . . . . . . . . . . . . . . . 3.2.1 3.4.5 Shared Robust Rerouting -ShRR . . . . . . . . . . . . . 3.5 Numerical results for all mechanisms . . . . . . . . . . 3.5.1 Dimensioning cost . . . . . . . . . . . . . . . . . . . . . 35 3.5.2 Efficiency of Path Generation . . . . . . . . . . . . . . . 35 9 EFR -Efficiency of the strategy 9.1 Dimensioning cost . . . . . . . . . . . . . . . . . . . . . . 9.2 Heuristic performance . . . . . . . . . . . . . . . . . . . 9.3 Effiency of EFR applied to partial failures . . . . . . . 9.4 Restoration time . . . . . . . . . . . . . . . . . . . . . . . 9.5 Conclusion on the efficiency of EFR . . . . . . . . . . .

Table 1 . 1 -

 11 Bandwidth efficiency, SNR requirement and capacity. -class services. However, extreme environmental conditions can lead to total failures as the lowest SNR requirements cannot be met, and high-class services will be affected.

	Modulation	Bandwidth	SNR require-	Capacity for	Capacity for
	scheme	efficiency	ment		7MHz	28 MHz
	QPSK 16-QAM	2 bps/Hz 4 bps/Hz	14.21 dB 21.02 dB		14 Mbps 28 Mbps	56 Mbps 112 Mbps
	32-QAM	5 bps/Hz	25.24 dB		35 Mbps	140 Mbps
	64-QAM	6 bps/Hz	27.45 dB		42 Mbps	168 Mbps
	128-QAM	7 bps/Hz	31.10 dB		49 Mbps	196 Mbps
	256-QAM	8 bps/Hz	33.78 dB		56 Mbps	224 Mbps
	class and midChannel
	Capacity
	High-class	256 QAM	128 QAM	64 QAM	32 QAM QPSK	256 QAM
	services
	Low-/Mid-class
	services
				Time

  Introduction to Recovery Mechanisms . . . . . . . . . . . 11 2.2 Strategies for total link failures . . . . . . . . . . . . . . . 14 2.2.1 Protection Strategies . . . . . . . . . . . . . . . . . . . . . . 14 2.2.2 Restoration Strategies . . . . . . . . . . . . . . . . . . . . . 15 2.2.3 MPLS feature -MPLS Fast Rerouting . . . . . . . . . . . . Elastic Traffic Flows -ETF . . . . . . . . . . . . . . . . . . . 20 2.3.3 Global Rerouting -GR . . . . . . . . . . . . . . . . . . . . . 20 2.3.4 MPLS feature -MPLS TE Auto-bandwidth Adjustment . . 21

	Background and Literature Review	2
	Contents 2.1

19 2.3 Strategies for partial link failures . . . . . . . . . . . . . . 19 2.3.1 Probabilistic Routing -PR . . . . . . . . . . . . . . . . . . . 19 2.3.2

  Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	Network Dimensioning
	Problem
	Contents 3.1 23
	3.2 Study of the nominal state . . . . . . . . . . . . . . . . . . . . 25
	3.2.1 Dual problem and dual separation . . . . . . . . . . . . . .	26
	3.2.2 Path generation . . . . . . . . . . . . . . . . . . . . . . . . .	27
	3.3 Study of Global Rerouting . . . . . . . . . . . . . . . . . . . . 27
	3.3.1 Dual problem and dual separation . . . . . . . . . . . . . .	29
	3.3.2 Path generation . . . . . . . . . . . . . . . . . . . . . . . . .	29
	3.4 Mathematical formulation of the restoration methods 30
	3.4.1 End-to-end rerouting with stub release -RR + . . . . . . .	30
	3.4.2 End-to-end rerouting without stub release -RR . . . . .	32
	3.4.3 Local Rerouting -LR . . . . . . . . . . . . . . . . . . . . . .	32
	3.4.4 Path Diversity -PD . . . . . . . . . . . . . . . . . . . . . . .	33
	3.4.5 Shared Robust Rerouting -ShRR . . . . . . . . . . . . . . .	34
	3.5 Numerical results for all mechanisms . . . . . . . . . . . 35
	3.5.1 Dimensioning cost . . . . . . . . . . . . . . . . . . . . . . .	35
	3.5.2 Efficiency of Path Generation . . . . . . . . . . . . . . . . .	35
	n this chapter, we present the dimensioning problem of some recovery
	mechanisms of the literature. We first introduce some notations. Then, we
	study the modelisation of the nominal state, and continue with dimension-
	ing problem for networks resilient to total link failures using restoration
	presented in Chapter 2.

  demand d has a specified set of admissible paths P d (called the path-list) composed of selected elementary paths from o(d) to t(d) in graph G. Recall that an elementary path does not traverse any node more than once. Paths in P d , used to realize the demand (traffic) volumes, are assigned flows x 0 , p ∈ P d , which are optimization variables. Each value d p specifies the reference capacity (expressed in the same units as link capacity and demand volume) reserved on the tunnel realized by path p ∈ P d . The set of all admissible paths is denoted by P := Since we assume only elementary paths, we will sometimes identify the paths with the sets of links they traverse: p ⊆ E , p ∈ P . The given sets of admissible paths define the link-path incidence coefficients δ ed p , e ∈ E , d ∈ D, p ∈ P d , where δ ed p = 1 if path p ∈ P d traverses link e ∈ E , i.e., if e ∈ p, and δ ed p = 0 otherwise. It is important to note that the sets of admissible paths P d , d ∈ D, are parameters in the problem formulations considered in the sequel, although in general we assume that all possible elementary paths can potentially be used if this is required to achieve the optimum.

	U The maximum path-lists, i.e., path-lists P d containing all elementary paths d∈D P d . from o(d) to t(d), will be denoted by ˆ , d ∈ D, with ˆ := U d∈D ˆ . P d P P d

  Above |p| 0 = ∑ e δ ed p 0 and |p| s = ∑ e∈E δ ed p π s , s ∈ S denote the state-dependent (dual) lengths of path p.

	d∈D	d d	∑ ∑ d d s∈S d∈D
	π 0 e + ∑ s∈S	π s e ≤ ξ e , e ∈ E	(3.7b)
	λ 0 d p ≤ |p| , d ∈ D, p ∈ P d 0	(3.7c)
	λ s d p ≤ |p| , s ∈ S , d ∈ D, p ∈ P d s s	(3.7d)
	all variables λ, π 0 , π s continuous and nonnegative.	(3.7e)

  2.1. Failure state related subproblems can efficiently be solved by computing the shortest path w.r.t. the weight vector π s , e ∈ E , s ∈ S and π s , s ∈ S , e ∈

	E \ s for each commodity d ∈ D. Note that finding a shortest path in graph G (V , E ) with nonnegative weights π 0 ≥ 0, e ∈ E or π s ≥ 0, s ∈ S , e ∈ E \ s e e
	d	P	(
		e
		d
		e
		d
		e	e

  , π s , λ 0 , λ s ) are given in the left-hand terms.

		d∈D p∈P d ,s∈ / p	δ ed p x 0 d p
		∑ ∑ d∈D p∈P s			d p ≥ 0, s ∈ S , e ∈ E \ s	(3.8d)
	[λ s ≥ 0]	p∈P d ,s∈ / p	0 d p	p∈P s	s d p	≥ h s , d ∈ D, s ∈ S	(3.8e)
		x 0 , x s , y 0 continuous and nonnegative	(3.8f)
	Constraints (3.8b) (respectively (3.8d)) express capacity constraints
	in the nominal (respectively failure) state. Constraints (3.8c) ensure the
	satisfaction of traffic in the nominal state and constraints (3.8e) ensure
	the lowest traffic satisfaction rate for the failure scenario s. Finally, the
	non-negativity of variables is expressed by constraints (3.8f) and dual variables (π 0 e e d d
	Let us consider the problem dual to problem P RR + (P ) formulated in (3.8) for a given set of admissible paths P . The dual is as follows:
	max W = ∑ h 0 λ 0 d d d∈D						(3.9a)
	π 0 e + ∑ s∈S d + ∑ λ s ≤ δ ed p e + ∑ ∑ δ ed p π s , d ∈ D, p ∈ P d (3.9c) π s (3.9b) e ≤ ξ e , e ∈ E s∈S ,s∈ / p e∈E s∈S ,s∈ / p e∈E
	λ s d ≤ ∑ δ ed p π e , s ∈ S , d ∈ D, p ∈ P d s s e∈E	(3.9d)
	all variables λ 0 , λ s , π 0 , π s continuous and nonnegative.	(3.9e)

Table 3 .

 3

		1 -Network description
	Network	Nodes Links Demands
	pdh	11	34	24
	polska	12	18	66
	nobel-us	14	21	91
	nobel-germany	17	26	121

  Path Generation algorithm intended to accelerate the CPU time was presented. From the LP presented above, we can Relative gap (in %) for all strategies for network polska.

	70%
	60%
	50%	LR
	40%	RR	+
	30% 20%	WoR	-
	10%	PD
	0%
	50% 55% 60% 65% 70% 75% 80% 85% 90% 95% 100%
	Figure 3.1 -90%
	80%
	70% 60%	LR
	50% 40% 30%	RR WoR
	20% 10%	PD
	0%
	50% 55% 60% 65% 70% 75% 80% 85% 90% 95% 100%
	∈D d	l∈S d∈D d

+ -Figure 3.2 -Relative gap (in %) for all strategies for network nobel-us. establish that the number of variables is the same for GR, RR + and RR with |E| + (1 + |S|) * ∑ d∈D |P d | variables. The number of variables for LR is equal to |E|

Table 3 . 2 -

 32 Number of optimization variables for all networks, for all strategies.

	Network	GR, RR + , RR	LR	PD
	pdh	65 885 819 1 882 485 1 882 485
	polska	46 701	37 455	2 475
	nobel-us	156 507	128 437	7 134
	nobel-germany	324 215	224 875	12 033

Table 3 .

 3

	Network	arc-node time (s) time (s) nb paths time (s) nb paths arc-path arc-path + PG
	pdh	9	442 1 882 451	7	98
	polska	4	1	2 457	1	184
	nobel-us	38	6	7 113	5	245
	nobel-germany	18	16	12 007	19	439

3 -Study of Path Generation for GR.

Table 3 . 4 -

 34 Study of Path Generation for RR + .

	Network	arc-path time (s) nb paths time (s) nb paths arc-path + PG
	pdh	4 874 1 882 451	83 607	721
	polska	10	2 457	2	403
	nobel-us	74	7 113	6	706
	nobel-germany	140	12 007	43	837

  assures that in each state s ∈ S , the thinned nominal flows are sufficient to realize the volume of each demand d ∈ D assumed for this state. Then, the second capacity constraint (4.1d) assures that in each state s ∈ S , the available capacity of each link e ∈ E s is not exceeded. Finally, constraint (4.1e) assures thinning. Note that constraint (4.1d) is, for each link e ∈ E , written down only for s ∈ S e , and not for all s ∈ S because for any state s ∈ S \ S e (in which the considered link e is fully available, α s = 1) such a constraint would be redundant-it is implied by(4.1b), as the link load s 0∑ d∈D ∑ p∈P d δ ed p x d p does not exceed its nominal load ∑ d∈D ∑ p∈P d δ ed p x d p due to constraint (4.1e). The optimal value of the cost (4.1a) of P FT (P ) is denoted by C(P ). Note also that formulation of FTOP does not explicitly involve dependence of β s on α s (s ∈ S )-this is done while preprocessing h s .

						e
	x s	d p t	d p	dp t	dp	d p
			11	12	21	22
					P

  .16)

			e∈E	e	∑ ∑ e e e∈E s∈S	∑ d s∈S
	and add the constraints
	Z s	s	s	s	s	s	(4.17)
	These constraints force the equalities Z s Z s	= z s u

e ≤ u e , Z e ≤ z , Z e ≥ 0, Z e ≥ u e + z 1, e ∈ E , s ∈ S . e , e ∈ E , s ∈ S , so that s e = 1 if, and only if, e ∈ S e and s ∈ S q (π, λ); otherwise Z e = 0. Hence, variables Z can be assumed continuous.

  Hence, applying PG, we find out that paths p 12 and p 22 have their total dual lengths (defined by(4.4)) equal to p 12 ) = p 22 ) = 1. Since these values are negative, both paths are added to the problem so that the set of admissible paths P becomes set equal to ˆ , i.e., the set of all (loop-less) paths in the network graph for the considered two demands. An optimal solution of the resulting instance P( ˆ ) of FTOP is given inExample 4.2.

	1	2	1 2 1 1 d

  } and π e t + π e tt > λ d .(4.33) represented by the sequence of nodes in ˆ , q ˆ = (o(d), v ˆ(e 1 ), v ˆ(e 2 ), . . . , v ˆ(e n ), t(d)). Then the corresponding sequence of links from E , q := (e 1 , e 2 , . . . , e n ), is a path from o(d) to t(d) in graph G, i.e., q ∈ P d . Conversely, if we specify path q = (e 1 , e 2 , . . . , e n ) from o(d) to t(d) in graph G, then q ˆ(o(d), v ˆ(e 1 ), v ˆ(e 2 ), . . . , v ˆ(e n ), t(d)) will be a path from o(d) to t(d) in graph G. This establishes a one-to-one correspondence of o(d) t(d) paths qˆ and q in graphs ˆ and G, respectively. Now we make use of the link weights ω(e ˆ), e ˆ ∈ ˆ, specified by (4.30) in the formulation ofLemma 4:

		e t λ s d ,	e tt	t tt if s ∈ S (v) and q ∩ δ(v) = {e , e	e t s(v)	e tt s(v)	d s(v)
	Let	qˆ be a path from o(d) to t(d) in graph ˆ

Table 5 .

 5 .

	network	|V | |E | |D| ∆(G) δ(G)
	pdh	11 34 24	9	7
	polska	12 18 66	5	2
	nobel-us	14 21 91	6	2
	nobel-germany 17 26 121	4	2

1 -Network description.

  , the gap between the dimensioning cost of global

		90%
		80%
		70%
	Relative gap	60% 50% 40% 30%
		20%
		10%
		0%	α
		100% 90% 80% 70% 60% 50% 40% 30% 20% 10% 0%
	Figure 5.4 -Relative gap between GR and FTS depending on the availability coefficient
		α for network nobel-us (link failures).
		60%
		50%
	Relative gap	40% 30% 20%
		10%
		0%	α
		100% 90% 80% 70% 60% 50% 40% 30% 20% 10% 0%

Table 5 .

 5 .2.

	single node failures	|S | 12
	single link failures	18
	two near-links failures	26
	double links failures	324

2 -Number of failures |S | depending on the failure scenarios.

The results show that assuming FT instead of GR increases the cost by up to 17 % maximum for the two failing links scenarios. Furthermore,

Table 5 . 3 -

 53 polska and nobel-us) is equal to 6 639 paths (resp. 491 and 609 paths). Effectiveness of the path generation algorithm for SL.

	network	α	β	t FTOP < t GP t FTOP t PP #iter. #gen.paths
		0.5 0.75	467	308	28	22	8	298
	pdh	0.5 0.25 0.75 1	460 478	299 311	46 43	35 34	11 11	335 198
		0.25 1	293	473	52	43	12	316
		0.5 0.75	533	5	16	13	5	412
	polska	0.5 0.25 0.75 1	560 383	6 4	28 23	22 19	8 7	466 471
		0.25 1	2451	2	27	20	5	506
		0.5 0.75	4	2	29	23	6	530
	nobel-us	0.5 0.25 0.75 1	4 4	2 2	43 30	35 24	8 6	591 560
		0.25 1	4	2	40	33	7	621

Table 5 . 4 -

 54 illustrate an important aspect of the PG algorithm, namely the evolution of the number Effectiveness of the path generation algorithm for DL.

	network pdh	α 0.5 0.75 β 0.5 1 0.25 0.75 0.25 1 0.5 0.75	t FTOP < t GP t FTOP t PP #iter. #gen.paths * * 2914 2506 13 354 * * 3612 3034 14 391 * * 1882 1524 10 354 * 2653 2202 10 354 * 539 54 345 286 8 466
	polska	0.5 0.25 0.75 1	667 425	53 55	387 858	317 746	8 8	486 511
		0.25 1	303	61 1193 1038 10	530
		0.5 0.75 1798 162 755	649	8	542
	nobel-us	0.5 0.25 0.75 1999 160 1719 1444 1 2804 140 2187 1925 10 9	572 615
		0.25 1	2741 137 2494 2020 11	646

of added paths |P + | and the network cost C FT for the consecutive iterations. The two α cases for SL with β = 1 are illustrated for pdh, polska and nobel-us. Practically, for all these cases the optimal solution is obtained .

.

Table 5 . 5

 55

	scenario network	GR	FT
		pdh	5	100
	SL	polska	0	1
		nobel-us	1	2
	DL	pdh polska	2262 6	* 269
		nobel-us 12 2367
	TL	pdh polska 389 * nobel-us 281	* * *

-Solution times in seconds for different routing variants.

Table 5 .

 5 is out of the scope of this work. 6 -LBP vs. FTOP for polska under DL.

	α	β	C FTOP /C LBP T FTOP /T LBP
	0.25 0.75	1.04	0.011
	0.25	1	1.05	0.013
	0.5 0.75	1.08	0.017
	0.5	1	1.07	0.029

Table 5 .

 5

	α	β	C FTOP /C LBP T FTOP /T LBP
	0.25 0.75	1.02	0.03
	0.25	1	1.02	0.01
	0.5 0.75	1.04	0.007
	0.5	1	1.03	0.002

Table 6 . 1

 61

	network di-yuan	|V | |E | |D| 11 42 22
	polska	12 18 66
	nobel-us	14 21 91
	nobel-germany 17 26 121

  Relative gap between FAS and GR for polska. Relative gap between FAS and GR for nobel-us.

		40%
		35%
	Relative gap	30% 25% 20% 15% 10%	1.1	1.25
		5%	1.5
		0%	2
		α
		95% 85% 75% 65% 55% 45% 35% 25% 15% 5%
		Figure 6.2 -40%
		35%
		30%
	Relative gap	25% 20% 15% 10%	1.1	1.25
		5%	1.5
		0%		1.75
		α
		95% 85% 75% 65% 55% 45% 35% 25% 15% 5%
		Figure 6.3 -40%
		35%
		30%
	Relative gap	25% 20% 15%		1.1 1.25 1.5 2
		10%
		5%
		0%
		α
		95% 85% 75% 65% 55% 45% 35% 25% 15% 5%

Table 6 . 2 -

 62 Average percentage per link failure of nominal paths which are thinned or thickened in FAS

	yuan	0 19 69 30 55 44 38 61
	polska	0 44 56 44 57 43 43 57
	nobel-us	0 41 60 40 58 42 46 54
	nobel-germany 0 48 52 48 49 51 40 60

  set of paths that are affected in failure state s ∈ S , i.e. that contain a link in s link-path incidence coefficients (δ ed p , e ∈ E , d ∈ D, p ∈ P d ). It takes value δ ed p = 1 if path p ∈ P d traverses link e ∈ E , and δ ed p = 0 otherwise. affected demands in failure scenario s ∈ S , allowed to thick their remaining path-flows. A demand is affected if its surviving nominal path-flows are not sufficient to carry the traffic volume assumed for this state, i.e., when ∑ p∈ ¯ s z d p + ∑ p∈P s x d p < h s .

	EFR-P requires the use of the following notations: V set of routers set of links, directed or undirected, represented by a pair {v, w} E of some nodes v, w ∈ V non-negative unit capacity cost of link e ∈ E , seen as a e parameter set of demands associated with an unordered pair of nodes D {o(d), t(d)}. For the sake of simplicity we call o(d) a source node and t(d) a termination node.
	0 d P d set of nominal paths, parameters in the EFR-P formulation volume that has to be sent between o(d) and t(d) for demand d ∈ D, seen as a parameter S set of failure scenario equal to all possible link failure d p nominal path-flow associated to path p ∈ P d for demand d ∈ D y e capacity reservation for edge e ∈ E , which is an optimization variable P d set of paths that are unaffected in failure state s ∈ S
	¯ s P d
	δ ed p
	¯ s D

  To demonstrate this, consider the following cuts involving the expensive links, i.e., links (o, v 1 ), (o, v 2 ), (o, v 3 ), (w 31 , u 31 ), and (w 32 , u 32 ):• second cut for failre of f 2 : {(w 31 , u 31 ), (w 32 , u 32 ), (o, v 1 )}

	• one cut for the normal state: {(o, v 1 ), (o, v 2 ), (o, v 3 )}
	• first cut for failure of f 1 : {(w 31 , u 31 ), (w 32 , u 32 ), (o, v 2 )}
	• second cut for failure of f 1 : {(w 31 , u 31 ), (o, v 2 ), (o, v 3 )}
	• first cut for failure of f 2 : {(o, v 1 ), (o, v 3 ), (w 32 , u 32 )}

3 d

 3 When link f 1 fails, flow on o v 3 w 32 u 32 v P t is enlarged to reach 1 1 6 and flow on o v 1 w 31 u 31 v P t is thickened to 3 . When link f 2 fails, the third and the fourth normal flows are rerouted in a symmetric way by enlarging respectively the flows on path o v 3 w 31 u 31 v P t and path o v 1 w 32 u 32 v P t.

	The resulting
	1 capacity reservations of the expensive, solid-line links are all equal to 3 1 1 (for links w 31 v 31 and w 32 v 32 ), and ( 3 ) for the three other links + 3b (respectively o V 1, O v 2, and o v3) as depicted in Figure 7.4. 5 The resulting capacity is ( + 3 1 )ξ and for b = 36 it gives a cost of B 61 36 ξ.

  This holds also for EFR as for a = 0 all EFR solutions are necessarily solutions of RR, so EFR cannot do better than RR. To summarize, solving the constructed instance of EFR for the optimal cost C 0 yields a solution of 61 EL-PATH: an elementary path P in question exists if C 0 ≤

	that any solution for RR in the considered 7 network is necessarily greater than or equal to ξ, which is greater than 4 61 36 36 ξ, and does ξ. 7 ξ. In this way, EL-PATH is reduced to EFR and not exist when C 0 ≥ 4 hence EFR is N P -hard.

  ∈ D, p ∈ P d , s ∈ ¯(d) \ p: ( |p| s λ s , if |p| s < λ s

			E
		σ s d p =	0,	d	if |p| ≥ λ s d s d	(7.6)
				dp
						d
				F d
	d p	d
	P d
						P d
	∆ 0		dq	∑	dq	F d ∑ dq
	dq = |q| λ 0 , d ∈ D. d
	P d , s ∈ E (d) \ p:	d p = dq	P d must give for d ∈ D, p ∈ if |p| s ≤ λ s (7.5) |p| λ d , if |p| > λ s ( 0, ∆ ∆ F d ∆ s dq .
						P d

dq and for d

1 Introduction to EFR PLF and Notations

  We keep the notations presented in 7.2.1. However, we need to introduce a few more notations.Network links are subject to capacity variations that we consider as (partial) failures. The set of failure states is still denoted by S . Each failure state s ∈ S is identified with a set of links (s ⊆ E ) that cannot operate at full capacity and a set of bandwidth availability coefficient α s , s ∈ S , e ∈ E with value α s < 1 if s contains e, and α s = 1 otherwise. First, the nominal EFR, affected nominal path-flow are lost). They are thinned to z s , which are optimization variables. A traffic demand d is said to be affected by a failure state s if its surviving nominal path-flows (thinned or not) are not sufficient to carry the traffic volume assumed for this state, i.e., when ∑ p∈ ¯ s z d p + ∑ p∈P s x d p < h s . Otherwise, the demand is unaffected. The rest of variables are such as in EFR-P formulation and the process follows the same idea as for EFR. Consider the same example than Example 7.1 dedicated to EFR. We show below what is the result of the minimum link cost network when EFR is used to recover from single partial link failures, where a failing link suffers a degradation of 50% of its capacity due to a change in the modulation scheme. As the aim is to describe the behavior of EFR

	e and add the following set of constraints e d e∈E e ≥ u e u s , e ∈ E , s ∈ S Y s s s s e ≤ z , Y e ≤ (1 u s ), Y e ≤ u e , e ∈ E , s ∈ S ∑ s∈S d ∑ e e e d e∈ ¯ Z s s s s W s ≥ z s u s , s ∈ S e ≤ (1 z ), Z e ≤ (1 u s ), Z e ≤ u e , e ∈ E , s ∈ S d p e 8.1.e path-flow x 0 e affected by s (p ∈ ¯ s ) can only be thinned (remind that in (7.14a) (7.14d) (7.14c) (7.14b) d p P d
	P d	V s ≥ 1 u s z s , s ∈ S . d d s 0				(7.14e)
	Example 8.1 18	1 2	to link (B, E), and	3 4	to each other
		epr	of
					2/3
		1 2			2 2

PLF , the presented solutions is only near-optimal. The obtained solution gives a capacity of 1 to link ( A, E), link, which gives a global cost equal to 4 < 5. Several nominal routing gives the same dimensioning cost. In the nominal state, as depicted in

  2/ S3tate.

	Figure 8.2 r link ( A, C) is decreased down to . C esents the failure 1 1 2	B link ( A, E). In 1 1 1/3 Hence, bandwidth 2 2	D this scenario, capacity of

of path p 1 has to meet the capacity limit of l i nk ( A 2 , / E 3 ), i.e. 2 . Now that pat h s ro u 2 t / e 3 d through a failed link has been thinned (or not), we can dete A rmine the status of each demand. Clearly, due to the failure, the traffic requirement for d 1 is no longer met and d 1 is considered affected, while d 2 remains unaffected. There is no bandwidth remaining on

  . When y w = 1 for w ∈ W e , the link capacity available in state s is assumed to be equal to a given value b ws , e ∈ E , s ∈ S with b ws ≤ b w0

	z.
	min C = ∑ ξ e y e e∈E		(8.1a)
	∑ ∑ δ ed p x 0 d∈D p∈P d d p ≤ y , e ∈ E e	(8.1b)
	∑ x 0 p∈P d d p ≥ h d , d ∈ D 0		(8.1c)
	d ∑ ( ∑ δ ed p (x 0 d∈D p∈P s d p u d p + v d p ) + s s	p∈ ∑ ed p d p δ ¯ s P d z s ) ≤ α s y , s ∈ S , e ∈ E (8.1d) e e
	d ∑ δ ed p (x 0 p∈P s d p u d p + v d p ) + s s	p∈ ∑ ed p d p d δ ¯ s P d z s ≥ h s , s ∈ S , d ∈ D	(8.1e)
	p∈ P d	d
	p∈ P d	d
	d p	d p		d
	d p	d p		d
	d p ≤ x	d p		P d
	e for all s ∈ S . In general, in a failure state more than one link can have its e e availability ratio decreased by the modulation scheme. Constraints (8.1e) assure that in each failure state s ∈ S , the adjusted flows are sufficient

to realize the volume of each demand d ∈ D and constraints

(8.1d

) check that the surviving capacity of each link e ∈ E is not exceeded. Constraints (8.1f) -

(8.1g

) are related to the status of demands. They restrict T s values to be equal to 1 for an affected demand and 0 otherwise. Note that

(8.1f

) is handled by CPLEX MIP solver n the same way as

(7.1f)

in Section 7.2. Constraints (8.1h) -(8.1l) express bound constraints for variables u, v, and

  and binary y w (e ∈ E , w ∈ W e ) and

	T s d (s ∈ S , d ∈ D). This MIP formulation is as follows:
	min C = ∑ ∑ ξ w y w e e e∈E w∈W e			(8.6a)
	∑ ∑ δ ed p x 0 d∈D p∈P d	∑ e y e , e ∈ E w∈W e	(8.6b)
	∑ x 0 p∈P d d p ≥ h d , d ∈ D 0		(8.6c)
	d ∑ ∑ δ ed p (x 0 d∈D p∈P s d p u d p + v d p ) + s s ≤ ∑ b ws w w∈W e e y e , s ∈ S , e ∈ E	∑ ∑ ed p d p δ z s d∈D p∈ ¯ s P d	(8.6d)
	d ∑ δ ed p (x 0 p∈P s d p u d p + v d p ) + s s	p∈ ∑ ed p d p d δ ¯ s P d z s ≥ h s , s ∈ S , d ∈ D (8.6e)
	p∈ P d	d
	p∈ P d	d
		y w
	d	d p		d	e

  ).

	network	|V | |E | |D| ∆(G) δ(G)
	di-yuan	11 42	22	9	7
	polska	12 18	66	5	2
	nobel-us	14 21	91	6	2
	nobel-germany 17 26 121	4	2
	Table 9.1 -Network description.
				d	d
			EFR
					EFR
					C GR
	G a
					EFR
			EFR
		EFR
					121

Table 9 .

 9

	15.5	7.7

2 -Relative gap (in %) for all strategies.

Table 9 . 4 -

 94 Relative gap (in %) of EFR PLF and FT compared to GR.

		1 EF R P LF	0.5 K EF R P LF K EF R P LF K EF R P LF 1.0 3.0
	50% 14.3	11.3	6.6	5.0	3.3
	75% 26.0	20.9	10.9	7.8	3.9
	95% 43.9	35.8	18.3	11.6	7.0

Table 9 . 5 -

 95 GR RR Paths analyzis on the solutions obtained by EFR, GR and RR for network polska

	Avg number of paths per demand in NS Avg number of distinct paths per demand	4.12 4.12	3.02 1.27 1.51 3.02 7.26 7.36
	Avg number of paths to thick/create per demand	0.94	0.61 1.24 0.41
	Avg length of the paths in NS	3.41	3.14 3.13 2.46
	Avg length of all paths	3.41	3.14 4.44 5.57

Table A .

 A | |E | |D| ∆(G) δ(G)

	pdh	11 34 24	9	7
	di-yuan	11 42	22	9	7
	polska	12 18	66	5	2
	nobel-us	14 21	91	6	2
	nobel-germany 17 26 121	4	2

1 -Description of SNDLib Network instances

http://www.enseignementsup-recherche.gouv.fr/

https://www.hds.utc.fr/labex-ms2t-484/ vii

http://www.enseignementsup-recherche.gouv.fr/

https://www.hds.utc.fr/labex-ms2t-484/ ix

We categorize FTS in the group of protection strategies because the main feature of FTS is not creating new paths which is proper to restoration methods

We note that for the single-node failures, the relation between the exact formulation (4.37) and the lower bound formulation(5.1) in the undirected case is the same as for the directed case.

Data from WeatherOnline Limited -July

(http://www.weatheronline.co.uk/)

d d

The idea behind this relies on the way the above heuristic works: we do not need to constrain the solution obtained at each step of the heuristic to the fixed set of affected/unaffected demands but only keeping the set of unaffected ones as growing.

links ( A, B) and (B, D) to increase the traffic of d 1 on path p 2 . Hence, as demand

This gap value is computed using results for each strategy as done for the gap with GR.

Acknowledgements

T his PhD thesis was carried out at the Heudiasyc Laboratory in the Uni-

It was financed with a grant from the French National Education and Research Ministry.

At the end of this work, I would like to address my deepest gratitude to my supervisor Prof. To conclude, note that this thesis was realized in the Heudiasyc laboratory, (UTC). It was financed by the French Ministry

cost-efficient than Flow Thinning.

Why Flow Adjustment should be avoided

Flow thickening leads to cheaper solutions as compared to pure thinning, and when all t d → ∞ the resulting modification of FTOP becomes equivalent to the GR optimization problem. As the corresponding modification of FT allowing for thickening can be implemented in the same way as the original FT (including the affine versions, see 6. hapter 7 focused on total single link failures. In this chapter, our intention is to extend the study to multiple partial link failures that can arise in 1, broadband wireless communications networks, presented in Chapter [START_REF] Willebrand | Free space optics: Enabling optical connectivity in today's networks[END_REF]Ghuman 2002, Son and[START_REF] Son | Design and optimization of a tiered wireless access network[END_REF]. The extended version of EFR, denoted EFR PLF is based on both Flow-Thinning and Elastic Flow Rerouting strategies.

Application to Fixed Wireless Networks

In this section we present an extension of EFR, referred to as EFR PLF , intended to handle partial link failures. It is among the first attempts to address flow protection against multiple partial failures in an implementable way. The approach is based on the two (re)routing strategies presented in this document: Flow-Thinning and Elastic Flow Rerouting. In short, EFR PLF can be seen as an extension of EFR to partial failures using the features of FT. The approach works as follows. When a link partially fails, the affected nominal path-flows can only be thinned following the idea of FT. Next, flow adjustments are made according to EFR. In this section, we present the optimization problem (referred to as EFR PLF -P) associated to the EFR PLF approach discussed above.

List of Publications