M Mateusz Żotkiewicz

M Andrzej Dabrowski -Président

M Włodzimierz

M Zbigniew Kotulski

M Eugeniusz

M Michał

Robust routing optimization in resilient networks -polyhedral model and complexity issues

Keywords:

In the thesis robust routing design problems in resilient networks are considered. In the first part computational complexity of such problems are discussed. The following cases are considered:

• path protection and path restoration

• failure-dependent and failure-independent restoration

• cases with and without stub-release

• single-link failures and multiple-link failures (shared risk link group)

• non-bifurcated (unsplittable) flows and bifurcated flows For each of the related optimization cases a mixed-integer (in the non-bifurcated cases) or linear programming formulation (in all bifurcated cases) is presented, and their computational complexity is investigated. For the N P-hard cases original N P-hardness proofs are provided, while for the polynomial cases compact linear programming formulations (which prove the polynomiality in the question) are discussed. Moreover, pricing problems related to each of the considered N P-hard problems are discussed.

The second part of the thesis deals with various routing strategies in networks where the uncertainty issues are modeled using the polyhedral model. In such networks two extrema are possible. The simplest in terms of implementation, and simultaneously the least effective strategy, is the robust stable routing. On the other hand, the most effective strategy, i.e., the dynamic routing, is virtually impossible to implement in real world networks. Therefore, the major aim of this part of the thesis is to present novel routing strategies that merge the simplicity of the robust stable routing with the efficiency of the dynamic routing.

List of Symbols

(i, j) -edge from i to j; i → j -path from i to j; ij -demand from i to j; p, q -paths;

p(e) -path corresponding to independent set e; r = (p, q) -failure-disjoint primary/backup path-pairs; s -failure state;

s n -failure state encompassing simultaneous failures of b n , and of every t m such that in graph G nodes v n and v m are adjacent;

t -traffic matrix, or top link;

xii t ij -volume of a demand between i and j in matrix t; t ′ ij -volume of a demand between i and j in matrix t routed using first routing;

t ′′ ij -volume of a demand between i and j in matrix t routed using second routing; w a -weight of edge a;

x p -flow of demand d ∈ D allocated to path p ∈ P d ;

x ad -flow of demand d ∈ D allocated to edge a ∈ A;

x dr -flow of demand d ∈ D allocated to pair r = (p, q) ∈ T d , or flow of demand d ∈ D allocated to sequence r = (p, q s : s ∈ Sp ) ∈ W d ;

x ij p -proportion of a traffic demand from i to j carried through a path p;

x ij a -proportion of traffic from i to j flowing through edge a;

x ij,t p -proportion of a traffic demand from i to j for traffic matrix t carried through path p;

x ij,t a -proportion of traffic from i to j for traffic matrix t on edge a; y a -total capacity of edge a; y ′ a -primary capacity of edge a; y ′′ a -protection capacity of edge a; z -congestion; z e -weight variable associated with independent set e;

A i -upper bound for outgoing traffic for node i; P ad -subset of paths in P d that contain link a ∈ A; P(i, j) -set of paths from i to j;

Q p -set of all candidate backup paths that can be used for protecting path p;

Q -support of a feasible solution to P G ; xiv Q s -support of a feasible solution to P G surviving in failure state s; R ′′ eds -set of all pairs r = (p, q) such that a ∈ q and s ∈ Sp ;

S -family of failure scenarios;

S a -set of all failure states in which edge a is available;

S p -set of all failure states in which path p is available;

Sp -set of all failure states where path p fails;

T -graph obtained by extending G in the proof of Lemma 4.2.5;

T d -set of all candidate failure-disjoint primary/backup path-pairs for demand d;

T ′ ad -set of all pairs r = (p, q) ∈ T d such that a ∈ p; U -universe;

V -set of all nodes (vertices);

V act -set of active nodes;

W -set of vertices for Fractional Coloring;

W ′ ad -set of all sequences r = (p, q s : s ∈ Sp ) ∈ T d such that a ∈ p;

W ′′ ads -set of sequences r = (p, q s : s ∈ Sp ) ∈ T d such that a ∈ q s for s ∈ Sp ;

P -problem FI-nSR;

α -direction of a hyperplane;

β -position of a hyperplane; γ -precision;

Introduction

In core wide-area transport networks already single network elements (such as transmission facilities or switching nodes) carry large amounts of traffic. This makes such networks vulnerable to failures, in particular to cable cuts, so that appropriate recovery mechanisms have to be used to avoid major traffic losses. For example, in DWDM optical transport networks, a transmission facility has capacity up to the order of TB/s and, if unprotected, its failure can cause enormous losses of traffic before restoration actions are taken. This was the reason to devote the first part of the thesis to the complexity of resilient network optimization problems.

In fact, transport networks are best protected through the restoration mechanisms of the transport layer so that the transport operators (carriers) can fully control the resiliency of their networks and use the most efficient means in terms of restoration time and consumption of extra protection capacity of transmission facilities. Moreover, the carriers do know what failures can be expected (as for example failures of certain conduits) and can effectively cope with them, also at the network planning stage. Another factor here is that having reliable IP links (protected in the transport layer), IP network operators can concentrate on providing resilience to the failures occurring in the IP layer, e.g., node breakdowns, and do not bother about the failures in the transport layer. Note that failures in the transport layer, if not protected, are often seen at the IP layer as complicated multiple IP link failures on which the operators have no direct control.

One of the most common mechanisms for securing transport communication networks against failures is path protection (PP). In optical networks the mechanisms of this kind protect end-to-end lambda paths. An example is the 1+1 hot-standby protection mechanism in which a primary (working) path is assigned a dedicated disjoint protection (backup) path which carries the same signal and therefore assures the end-to-end transmission whenever the primary path fails. The 1+1 mechanism is efficient in terms of restoration time, but costly in terms of extra (protection) capacity. The protection capacity is not shared between different primary paths in different failure situations and therefore must be at least equal to the working capacity. Some of its variants (as n : m protection and path diversity) can alleviate the issue of high protection capacity cost, but only to a limited extent.

Because of that, active mechanisms called path restoration (PR) can be considered instead. Although PR can be complex in terms of implementation and can have longer restoration times than PP, they are among the most efficient mechanisms as far as the extra link capacity required for path flow protection is concerned. The idea of a PR mechanism is as follows. The traffic demand (a set of lambda paths in the case of an optical transport network) between a pair of nodes is realized using several different network paths to route the connections (i.e., path flows, either non-bifurcated or bifurcated) in the normal (failure-free) state.

When a failure occurs, the affected primary connections are restored using backup connections (again, by means of either non-bifurcated or bifurcated path flows) along the surviving routes. In any failure state the total capacity of the temporarily established backup flows and the primary flows that survive is equal to the requested volume of the traffic demand.

The backup flows can be established using the separate protection (backup) capacity of the links so that the protection link capacity is separated from the working link capacity used by primary flows that traverse a given link. In effect, the working and protection link capacity form two separate pools of resources, so the backup flows do not use the working capacity released on links as a by-product of a failure. It is said that backup flows do not exploit the phenomenon of stub-release. Another possibility is when backup flows are allowed to use also the working capacity that is released by the failed primary connections on surviving links, so that the backup flows can exploit stub-release. This in fact leads to the usage of links' capacity as a common pool of resources. In both cases it is important that backup capacity is shared between restoration flows established in different failure states for different traffic demands, so the path restoration is not the dedicated hot-standby protection.

The restoration of primary flows can be either failure-independent or failure-dependent.

In the first case the path flows have to be restored in exactly the same way whatever is the reason of their failure. In the second case, the backup flows used to restore a given primary flow can be different in different failure situations.

In general, the complexity of optimization problems corresponding to a restoration mechanism can depend on the assumed failure scenario, in particular whether the failure scenario contains only a set of single element (link) failures or a set of failures consisting of multiple elements' failures; multiple failures are often referred to as shared risk resource (link) groups.

In the first part the following thesis is verified.

Most of resilient multi-commodity flow network optimization problems are

N P-hard, even when flows are allowed to be bifurcated.

To this aim, complexity of various variants of the multi-commodity flow network optimization problems related to the above described PP and PR mechanisms is studied. All the considered problems proved to be either N P-hard or polynomial, and all of them are N P-hard for multiple failures. This fact is not commonly recognized, especially when bifurcated (fractional) flows are admitted. Depending on the problem either N P-hardness or polynomiality proof is given. Some of the results discussed in this thesis can be found in the literature, while others are results of the present thesis.

The complexity issues of resilient network design have been considered by several authors, see [START_REF] Coudert | Shared risk resource group complexity and approximability issues[END_REF][START_REF] Hu | Diverse routing in optical mesh networks[END_REF][START_REF] Maurras | Network synthesis under survivability constraints[END_REF][START_REF] Orlowski | On the complexity of column generation in survivable network design[END_REF][START_REF] Pióro | Routing, Flow, and Capacity Design in Communication and Computer Networks[END_REF][START_REF] Stidsen | Optimal routing with single backup path protection[END_REF][START_REF] Wessäly | Dimensioning Survivable Capacitated NETworks[END_REF]. In fact, the previous results do not directly discuss the complexity of the basic optimization problems but are rather devoted to the complexity of the so called pricing problem required for column generation (see [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF]) in the related non-compact linear formulations of the basic problems (see [START_REF] Orlowski | On the complexity of column generation in survivable network design[END_REF]). These results are important (they will be used while discussing efficient ways of dealing with the considered problems), still they do not decide on the complexity of the basic problems which is the main subject of the first part of the thesis.

Other authors were studying similar problems with only slightly different settings, like [START_REF] Bashllari | A study on two new protection strategies[END_REF][START_REF] Bashllari | The MMF rerouting computation problem[END_REF], where the authors were considering one single failure only, or they were trying to provide good quality lower bounds for the problems considered in the thesis, like in [START_REF] Ben-Ameur | Design of survivable networks based on end-toend rerouting[END_REF].

It is worth noticing that the complexity results for multi-commodity flow optimization problems related to design of resilient networks are important as they help to develop proper algorithms used in network design tools based on contemporary linear/integer programming solvers such as CPLEX or XPRESS.

The second part of the thesis is devoted to the polyhedral traffic demand matrix uncertainty model. The reason was that modern telecommunication networks carry traffic generated by a variety of different applications, and provide services to a large number of users.

This makes prediction of traffic patterns difficult. Moreover, the customers' mobility makes a traffic demand matrix change in short periods of time. All those factors do not allow for considering only one traffic demand matrix. Instead they encourage us to work on traffic demand matrix uncertainty models. Some such models were proposed in the past. The first approach consists in building a traffic matrix based on the worst case for each traffic component. Routing is then computed based on this matrix. While this approach is simple, it can provide expensive solutions, because in fact it does not allow non-coincident traffic components to share resources.

The second approach is based on probabilistic modeling of traffic variations. After specifying such a model, one may look for routing that optimizes a probabilistic criterion: throughput expectation, average delays, blocking probability, etc. The solution obtained in this way is good on average, but can be very bad in some cases. Moreover, it requires knowledge of probability models, and they are usually difficult to obtain. This kind of approach is generally called stochastic programming, and was used for example in [START_REF] Lisser | Capacity planning under uncertain demand in telecommunications networks[END_REF][START_REF] Sen | Network planning with random demand[END_REF], where a finite number of traffic scenarios with a known probability are considered.

A different general approach called robust optimization (see [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF]) takes into account a finite number of possible situations. In this case a solution that supports all situations is of interest. In the networking context, a routing scheme is to be determined such that each traffic matrix belonging to a given finite set of traffic matrices can be carried in the network.

Another robust model was proposed in [START_REF] Fingerhut | Designing least-cost nonblocking broadband networks[END_REF] (and independently in [START_REF] Duffield | A flexible model for resource management in virtual private networks[END_REF]). It assumes that the outgoing traffic of each node is bounded (limitations on the incoming traffic can also be considered). Then the traffic matrix can be any matrix satisfying this kind of constraints.

This uncertainty model is called the hose model. Several network design problems based on this model have received a considerable attention in the literature (see [START_REF] Chekuri | Routing and network design with robustness to changing or uncertain traffic demands[END_REF] and references therein).

A different model is considered in [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF] where the authors assume that not all nodes can generate the maximum amount of traffic simultaneously. In fact this model, and the hose model presented above, are special cases of a more general polyhedral model considered in [START_REF] Ben-Ameur | Between fully dynamic routing and robust stable routing[END_REF][START_REF] Ben-Ameur | Routing of uncertain demands[END_REF][START_REF] Ben-Ameur | New economical virtual private networks[END_REF][START_REF] Ben-Ameur | Routing of uncertain traffic demands[END_REF]. The model assumes that each possible traffic matrix belongs to a polytope D. In [START_REF] Ben-Ameur | Routing of uncertain traffic demands[END_REF] a polynomial time algorithm is proposed to compute a routing scheme that solves this problem.

The routing is robust and stable (robust because it is compatible with all matrices, and stable because it does not change when the matrix changes -it is matrix-independent). Although the model was defined for traffic matrices belonging to a polytope, it can also successfully deal with problems assuming that traffic matrices belong to a union of polytopes.

A different approach to deal with uncertainty consists in allowing a network to change routing in a dynamic way, when there is a considerable change in terms of a traffic matrix.

This problem was intensively studied in the context of circuit-switched networks. Different rules can be applied to connect calls depending on the current situation, e.g., alternate dynamic routing, sequential routing, trunk reservation (see [START_REF] Ash | Dynamic routing in telecommunications networks[END_REF] and references therein). While this kind of routing has many benefits, it is generally difficult to implement, and it is also not optimal because the rules that are used are fixed in advance. However, it can be used as a reference point (lower bound) to evaluate approaches presented earlier. Lately it has been proven that the optimal cost of a network based on robust stable routing (fractional or integral) may be a factor of Ω(log n) larger than the cost required when using dynamic routing [START_REF] Goyal | Dynamic vs. oblivious routing in network design[END_REF]. For a more detailed discussion of different approaches to the problem of uncertainty proposed in the past, readers can consult a recent survey that can be found in [START_REF] Chekuri | Routing and network design with robustness to changing or uncertain traffic demands[END_REF]. What is more, other works related to traffic uncertainty can be found in [START_REF] Altın | Provisioning virtual private networks under traffic uncertainty[END_REF][START_REF] Carpenter | Studies of random demands on network costs[END_REF][START_REF] Feldmann | Dynamics of IP traffic: A study of the role of variability and the impact of control[END_REF][START_REF] Feldmann | Deriving traffic demands for operational IP networks: Methodology and experience[END_REF][START_REF] Lorenz | QoS routing in networks with uncertain parameters[END_REF][START_REF] Nabe | Analysis and modeling of world wide web traffic for capacity dimensioning of internet access lines[END_REF][START_REF] Ouorou | Robust capacity assignment in telecommunications[END_REF][START_REF] Petrou | Robust network design in telecommunications[END_REF][START_REF] Thompson | Wide-area internet traffic patterns and characteristics[END_REF].

In [START_REF] Ben-Ameur | Routing of uncertain traffic demands[END_REF] the following question was raised: given an uncertainty traffic demand polytope D, is it theoretically easy to compute a fully dynamic routing (routing scheme that depends on the current traffic matrix)? Recently, it was proved in [START_REF] Chekuri | Hardness of robust network design[END_REF] that this problem is in general difficult: it is co-N P-hard to decide whether a given network with known capacities is capable of carrying each traffic matrix t ∈ D, when routing is dynamic. Moreover, it is clearly difficult to implement this kind of routing for technical reasons.

Therefore, it is worth considering something between robust stable routing and fully dynamic routing. Instead of computing a robust solution, it is possible to partition the traffic demand polytope into some subsets, and compute a robust routing for each of them.

This class of problems was considered in [START_REF] Ben-Ameur | Between fully dynamic routing and robust stable routing[END_REF]. In the second part of the thesis, algorithms solving problems introduced in [START_REF] Ben-Ameur | Between fully dynamic routing and robust stable routing[END_REF] are presented.

In the sequel of this thesis it is assumed that a direction of a hyperplane dividing the traffic demand polytope is known, but its position is subject to optimization. For example an amount of traffic generated between a pair of nodes (like in the experiments presented in Chapter 10), or an amount of traffic generated by a specific node can be considered as a direction of the hyperplane. In such a situation a position of a threshold that triggers changes in routing is optimized. In other words, two routings are specified, the first is used when the amount of traffic, which was set as a direction of the hyperplane, is smaller than the threshold, otherwise the second routing is used. Another possibility is to consider time as a direction of the hyperplane. In this case time is represented by an additional dimension of the uncertainty set, and the moment when routing should be changed is optimized.

The major problem with this kind of approaches is that a routing can significantly differ between subsets, and implementing those changes can result in serious traffic losses (due to instability). So it is also worth considering something that will make the routing changes less abrupt. Therefore, in the second part the following thesis is verified.

There exist routing mechanisms that are decentralized and simple in implementation, and are capable of dealing with traffic demands described using a polyhedral approach.

To this aim, a novel routing mechanism, called volume oriented routing (and its polyno- The computational complexity of all the introduced models is discussed by summarizing known facts and presenting novel results. The first part of the thesis ends with concluding remarks in Chapter 6.

The second part of the thesis is organized as follows. Chapter 7 begins with Section 7.1, where a notation and formulations of three basic models is presented, i.e., robust routing, no-sharing routing, and dynamic routing. Robust routing assumes that traffic matrices are always routed in the same way regardless of their locations in the traffic demand polytope.

No-sharing routing is a special case of robust routing which assumes that capacities cannot be shared between different demands. The last model, namely dynamic routing, let each traffic matrix from the traffic demand polytope be routed in a different way. It is shown which of these problems are polynomial, and how they can be successfully approached. In Section 7.2, models that were used to create test cases are presented, while in Section 7.3 the basic models are enhanced by introducing two versions of partitioning of the traffic demand polytope: capacities have to be reserved once for the whole traffic demand polytope, or capacities can be rereserved each time the routing changes. In the thesis special features of these partitioning problems and algorithm that solve them are presented.

In Chapter 8, different algorithms solving the presented problems are discussed. In Section Numerical results showing applicability of the algorithms are presented in Chapter 10.

Congestions obtained for the considered basic models are compared first. Secondly, results

showing possible gains while applying different partitioning strategies are provided. Finally, efficiency of volume oriented strategies is discussed. Numerical results are followed by conclusions and suggestions of further research in Chapter 11.

Some of the results discussed in the first part of the thesis have been presented at the 5th Polish-German Teletraffic Symposium (PGTS), Berlin, Germany, in September 2008 [START_REF] Żotkiewicz | Complexity of resilient network optimization[END_REF],

and subsequently in European Transactions on Telecommunications in 2009 [START_REF] Żotkiewicz | Complexity of resilient network optimization[END_REF]. While other results were presented in Networks: an International Journal in 2010 [START_REF] Tomaszewski | On the complexity of resilient network design[END_REF]. Finally, some results were presented at International Symposium on Combinatorial Optimization (ISCO), Hammamet, Tunisia in March 2010 [START_REF] Żotkiewicz | Failure disjoint paths[END_REF], and published in IEEE Communications Letters also in 2010 [START_REF] Żotkiewicz | Finding failure-disjoint paths for path diversity protection in communication networks[END_REF].

The results concerning the partitioning strategies discussed in the thesis were first presented by the author at the 16th Polish Teletraffic Symposium, Łódź, Poland, in September 2009 [START_REF] Żotkiewicz | Adding dynamism to robust stable routing[END_REF], and at GLOBECOM, Honolulu, USA, in December 2009 [START_REF] Żotkiewicz | More adaptive robust stable routing[END_REF]. They are also covered in an article, written by the author and Walid Ben-Ameur, published in International Transactions in Operational Research [START_REF] Ben-Ameur | Robust routing and optimal partitioning of a traffic demand polytope[END_REF]. The results concerning the volume oriented strategies were presented at the 14th International Telecommunications Network Strategy and Planning Symposium, Warsaw, Poland, in September 2010 [START_REF] Żotkiewicz | Volume oriented routing[END_REF].

Part I Complexity Issues

Chapter 2

Notation

The considered network is modeled as a and y ′′ a , a ∈ A will be variables subject to optimization. In the cases when it is not necessary to distinguish between the working and protection capacity, variables y a will be used to denote the total capacity of link a ∈ A.

a directed graph G = (V, A) composed of set V of nodes
Notice that bounds on the capacity variables are not considered. Adding those bounds cannot simplify the considered problems, thus N P-hard problems will remain N P-hard after the modification. However, it is possible that some cases that were in P can become N P-hard when the bound are added.

The family of all failure states (called a failure scenario) considered in a particular design problem is denoted by S where each failure state s ∈ S (also called a failure situation or simply a failure) is identified by the set of failing links, so s ⊂ A. Family S is assumed to include the failure-less state O (formally equal to the empty subset of the set A) in which all links are operational (state O is sometimes called the normal state). It is assumed that links fail totally. The set S a = {s ∈ S : a / ∈ s} will denote the set of all states s ∈ S in which link a ∈ A is available. A failure scenario is called a single-link failure scenario if it admits only states s consisting of singletons (not necessarily all) plus the normal state O.

Otherwise, a scenario is called multiple-link failure scenario.

Node failures are not explicitly considered in this thesis. In fact, they do not add difficulty to the considered problems as they can be modeled as single-link failures through a suitable transformation of the network graph (see Section 4.6.1 in [START_REF] Pióro | Routing, Flow, and Capacity Design in Communication and Computer Networks[END_REF] and Section 9.3 in [START_REF] Orlowski | On the complexity of column generation in survivable network design[END_REF]).

The set of all candidate paths (in general, these are not all possible paths) that can be used for carrying flows is denoted by For a given candidate path p ∈ P d assigned to demand d ∈ D, the set of all candidate backup paths that can be used for protecting path p is denoted by Q p . Certainly, Q p ⊆ P d and s ∈ S q for all s ∈ Sp , i.e., paths p and q never fail simultaneously (and therefore are called failure-disjoint). In this context, path p ∈ P is called the primary path (or working path) and all paths from Q p are called its backup paths (or protection or restoration paths).

The set of all candidate failure-disjoint primary/backup path-pairs r = (p, q) for demand d ∈ D will be denoted by T d , T d = {r = (p, q) : p ∈ P d , q ∈ Q p }. For each link a ∈ A, and demand d ∈ D, the set of all pairs r = (p, q) ∈ T d such that a ∈ p will be denoted by T ′ ad , and the set of all pairs r = (p, q) ∈ T d such that a ∈ q -by T ′′ ad . For the failure-dependent restoration still another path structures will be needed. The set W d , defined for each d ∈ D, contains predefined candidate sequences r = (p, q s : s ∈ Sp ) of paths from u d to w d with the property that path q s works in state s ∈ Sp (i.e., when the primary path p fails). Then, W ′ ad is the set of all sequences r = (p, q s : s ∈ Sp ) ∈ T d such that a ∈ p, and W ′′ ads is the set of sequences r = (p, q s : s ∈ Sp ) ∈ T d such that a ∈ q s for s ∈ Sp .

Depending on a particular optimization problem, the following flow variables will be used:

x p -flow of demand d ∈ D allocated to path p ∈ P d , x ad -flow of demand d ∈ D allocated to link a ∈ A, x dr -flow of demand d ∈ D allocated to pair r = (p, q) ∈ T d or flow of demand d ∈ D allocated to sequence r = (p, q s : s ∈ Sp ) ∈ W d .
Notice that in the thesis both links and demand are directed. Still, the majority of proofs to be presented can be easily transformed to cover undirected cases. However, there exist cases when the transformation is impossible to achieve, e.g., in a proof of Section 4.1.3 2Div-Path problem is used, which is N P-hard for directed cases but remains in P for undirected cases.

Chapter 3

Path Protection Problems

Path protection (PP) mechanisms are passive in the sense that no flows are restored, and hence the flows surviving in any of the considered failure states must be sufficient to realize the demands. In this chapter the basic hot-standby PP mechanism (HS), and its extension called path diversity (PD) are presented. In both cases we do not have to consider protection capacity on the links but rather talk about redundant working capacity.

HS: Hot-Standby

With HS, i.e., 1+1 protection, each demand d ∈ D is realized by means of a single working path p which is protected by a dedicated single path q, r = (p, q) ∈ T d . The two paths are failure-disjoint, i.e., they never fail together (of course for the assumed failure scenario S).

Both paths are assigned flow h d which consumes h d units of capacity on each link along path p, and also h d units along path q, so if there is a link a ∈ A belonging to both paths then the amount of capacity consumed on this link by the considered demand is equal to 2h d .

The design problem corresponding to HS (referred to as problem HS) can be formulated as the following MIP (mixed-integer programming) problem.

Problem HS

minimize

F (y) = a∈A ξ a y a , (3.1a) r∈T d x dr = 1, d ∈ D, (3.1b) d∈D h d ( r∈T ′ ad x dr + r∈T ′′ ad x dr ) y a , a ∈ A, (3.1c) x dr ∈ {0, 1}, d ∈ D, r ∈ T d . (3.1d)
Observe that the use of binary flow variables x dr forces any feasible solution of problem (3.1) to be non-bifurcated (unsplittable) because for each demand d ∈ D it assigns the whole demand volume h d to the pair r = (p, q) ∈ T d for which x dr is equal to 1 (by (3.1b) there is only one such pair). Moreover, due to (3.1c), y a 0 for all a ∈ A. In fact, the above formulation yields a binary (i.e., non-bifurcated) optimal vertex solution even if the integrality condition in (3.1d) is relaxed to 0 x dr 1, i.e., when the linear relaxation is considered instead of the MIP formulation (3.1). In other words, in any optimal vertex solution (x ⋆ , y ⋆ ) of the linear relaxation, for each demand d ∈ D there is exactly one path-pair r ∈ T d with x ⋆ dr = 1, and for the rest of such pairs x ⋆ dr = 0. Note that the linear relaxation of (3.1) is not compact because the number of variables x dr is in general exponential (as the number of path-pairs r = (p, q) is exponential). Hence, to take into account all possible variables we have to use the column generation (path-pair generation in this case) method of LP (see [START_REF] Lasdon | Optimization Theory for Large Systems[END_REF][START_REF] Minoux | Mathematical Programming: Theory and Algorithms[END_REF]), based on solving the so called pricing problem. For the considered problem the pricing problem consists in finding, separately for each demand d ∈ D, a shortest pair r = (p, q) of failure-disjoint paths, i.e., a pair minimizing its primal cost a∈p ξ a + a∈q ξ a . Observe that in this particular case, finding such shortest path-pairs directly resolves the problem (3.1) (see [START_REF] Orlowski | On the complexity of column generation in survivable network design[END_REF]).

When dealing with a single-link failure scenario, finding a shortest pair of failure-disjoint paths for a given demand d ∈ D (and hence solving problem HS (3.1)) can be done in polynomial time using the Suurballe algorithm [START_REF] Suurballe | Disjoint paths in a network[END_REF] or its modification given in [START_REF] Bhandari | Survivable Networks -Algorithms for Diverse Routing[END_REF]. In fact, this problem is equivalent to the single-commodity min-cost-flow problem with flow value 2 and link capacities 1, see [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF].

For the general case of multiple-link failures, however, the problem (3.1) is N P-hard since, as shown in [START_REF] Hu | Diverse routing in optical mesh networks[END_REF], even a simpler problem of finding just any pair of failure-disjoint paths can be reduced from the proven N P-complete problem Set Splitting (see p. 221 in [START_REF] Garey | Computers and Intractability : A Guide to the Theory of NP-Completeness[END_REF]).

PD: Path Diversity

The main disadvantage of HS is that it requires at least twice the capacity of an unprotected network. Therefore, better PP mechanisms in terms of capacity efficiency are of interest. One such mechanism, probably most economical among PP mechanisms in terms of capacity, is called path diversity (PD). PD protects traffic against failing network components by overprovisioning, i.e., by routing more traffic than specified by the demand value in the failureless state O, and ensuring that at least the volume h d survives in each failure state in the considered failure scenario without rerouting any flow. The concept of PD has been studied in the literature under different names, for example diversification [START_REF] Dahl | A cutting plane algorithm for multicommodity survivable network design problems[END_REF] and demand-wise shared protection [START_REF] Koster | Demand-wise shared protection and multiple failures[END_REF][START_REF] Koster | Demand-wise shared protection for meshed optical networks[END_REF][START_REF] Wessäly | Demand-wise shared protection revisited: A new model for survivable network design[END_REF].

Each path p ∈ P d is assigned a flow variable denoted by x p that expresses a part of the required demand volume h d to be carried on path p. Thus, the quantity p∈Pa x p is the load of link a (a ∈ A) expressed in the flow units. For a given flow vector x = (x p : p ∈ P) and with the non-negative cost of carrying one flow unit on link a ∈ A denoted by ξ a (ξ a 0), we can express the cost of using link a as ξ a ( p∈Pa x p ), and the overall cost of the network by F (x) = a ξ a ( p∈Pa x p ). The problem studied in this section, Path Diversity Design (abbreviated by PD), is as follows. Problem PDD (special case of PD)

Problem PD minimize F (x) = a∈A ξ a ( p∈Pa x p ), (3.2a
minimize F (x) = p∈P ξ p x p , (3.3a) p∈P s x p h, s ∈ S, (3.3b) x 0. ( 3

.3c)

Example To illustrate problem PD consider the network depicted in Figure 3.1a with a single demand of volume h from node u to node w. For the failure scenario consisting of single failures of all links the optimal solution consists of three flows equal to x p = h 2 assigned to each of the three link-disjoint shortest paths depicted in Figure 3.1c. The cost F (x) of this solution is 6h. Note that the feasible solution that assigns flow x p = h to each of the two disjoint shortest paths of Figure 3.1b has the cost F (x) = 7h, and the feasible solution that assigns flow x p = h 3 to each of the four disjoint paths of Figure 3.1d has the cost F (x) = 19 3 h, and hence both of them are not optimal.

The character of the optimal solution changes when multiple-link failures are admitted.

Consider the four node network (being a subnetwork of the network from Figure 3.1a) with failure scenario S = {s 1 , s 2 , s 3 , s 4 } as shown in Figure 3.2a. The (unique) optimal solution uses non-disjoint paths, as illustrated in Figure 3.2b. All the three path flows are still equal to each other (they are equal to h). Clearly, the cost of this solution is 15h.

In fact, for any scenario S consisting of single-link failures, S ⊆ {{a} : a ∈ A} (in S not necessarily all links are subject to failure), problem PDD can be expressed in the compact node-link LP formulation, and hence solved in polynomial time taking (indirectly) into account all possible candidate paths (see [START_REF] Orlowski | On the complexity of column generation in survivable network design[END_REF]).

Problem PDD (compact formulation)

minimize

F (x) = a∈A ξ a x a , (3.4a) a∈δ + (v) x a - a∈δ -(v) x a = 0, v ∈ V \ {u, w}, (3.4b) a∈δ + (u) x a - a∈δ -(u) x a = X, (3.4c) X -x a h, {a} ∈ S, (3.4d) x 0. (3.4e)
Above, each variable x a denotes the flow realizing the considered demand (between nodes u, w ∈ V) on link a ∈ A, X is the total flow realized for the demand, and δ + (v) and δ -(v) are the sets of all links, respectively, outgoing from and incoming to node v ∈ V.

Moreover, for the particular failure scenario consisting of single failures of all links (S = {{a} : a ∈ A}) there always exists an optimal solution of PDD that uses only a set of k link-disjoint paths, so that the character of the solution exhibited in the first part of Example 3.2 is general (see [START_REF] Brightwell | Reserving resilient capacity in a network[END_REF]). The optimal solution assigns equal flows x p = h k-1 to each of these paths (note that x p = X k ). Knowing this, it is possible to use the following iterative algorithm to resolve PDD for the scenario that assumes single failures of every link:

Step 0: Set k = 1 and C(k) = +∞.

Step 1: Find a minimum-cost set P (k + 1) of k + 1 link-disjoint paths. If the set does not exist go to Step 3, otherwise denote the total cost of the paths by C(k + 1) = p∈P (k+1) ξ p .

Step 2:

If C(k + 1) • (k -1) < C(k) • k set k = k + 1 and go to Step 1.
Step 3: Assign flow equal to h k-1 to each path from P (k).

The algorithm is effective. Its core (Step 1) consists of finding a minimum-cost set P (k+1)

of k + 1 link-disjoint paths for the consecutive values of k so essentially it is an application of the Suurballe approach [START_REF] Suurballe | Disjoint paths in a network[END_REF] (see its modification in [START_REF] Bhandari | Survivable Networks -Algorithms for Diverse Routing[END_REF]) which finds a shortest set of (k + 1) disjoint paths from the previously found shortest set of k disjoint paths. Consequently, set

P (k + 1
) is determined by finding a shortest "interlacing" path for set P (k). Such a path can be computed using the original Suurballe algorithm or by any shortest path algorithm admitting negative link weights in a graph with no negative cycles. However, a more efficient way is to use the transformation of [START_REF] Edmonds | Theoretical improvements in algorithmic efficiency for network flow problems[END_REF] (before finding a consecutive interlacing path) to assure nonnegative link weights and then apply the classical Dijkstra algorithm to find the interlacing path. Using the transformation, and the fact that there cannot be more than |E| link-disjoint paths, the overall complexity of the algorithm becomes O(|A| 2 log (2+|A|/|V|) |V|) [START_REF] Tarjan | Data structures and network algorithms[END_REF]Chapter 8].

The above result on using disjoint paths (and the resulting algorithm) can be extended to the case when not all links are subject to (single) failures, i.e., when S {{a} : a ∈ A}.

Then there always exists an optimal solution with flows equal to h k-1 assigned to a set of k failure-disjoint paths, i.e., to a set of paths {p 1 , p 2 , . . . , p k } from u to w such that each pair (p i , p j ) (1 i < j k) has no common failing link (i.e., a ∈ p i ∩ p j ⇒ a ∈ A \ S). Such a solution can be found by the above algorithm applied to the network modified for each k by replacing each non-failing link a (a ∈ A \ S) by a set of k parallel links (with the same unit cost equal to ξ a ) that are subject to failure. Certainly, the parallel links are shrunk to the original link upon completion of the algorithm. Note that this solution has to be compared with the best possible solution that uses only one non-failing path (provided such a path exists). Still, the version of Path Diversity Design admitting multiple-link failures and using all possible elementary paths is N P-hard. Proposition 3.2.1. Path Diversity Design is N P-hard when multiple failures are admitted.

v 0 v 1 v 2 v n-1 v n v N t 1 ... ... t 2 t 3 t n-1 t n t n+1 t N b 1 b 2 b 3 b n-1 b n b n+1 b N

N P-hardness proof

Fractional graph coloring problem

Consider a graph G with the set of vertices W. Any non-empty subset of vertices e ⊆ W is called an independent set of graph G if no two vertices in e are connected by an edge. Let E be the family of all independent sets of graph G and let z = (z e 0 : e ∈ E) be a vector of (weight) variables associated with those independent sets. Finally, let

E v = {e ∈ E : v ∈ e}
be the family of all independent sets containing a given vertex v ∈ W. A (non-compact) LP formulation of Fractional Coloring is as follows.

Problem FGC (fractional graph coloring)

minimize

F (z) = e∈E z e , (3.5a
)

e∈E v z e 1, v ∈ W, (3.5b) z 0. (3.5c)
Any optimal solution z ⋆ of problem FGC determines the fractional chromatic number

χ f (G) which is equal to f (z ⋆ ).
Fractional Coloring is known to be N P-hard (its decision version is N P-complete); see [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF][START_REF] Lund | On the hardness of approximating minimization problems[END_REF].

N P-hardness proof

Consider an undirected graph G with the set W = {v 1 , v ∈ e}, it can be observed that Q sn = {p(e) : e ∈ I vn } and therefore for each s n ∈ S we have p∈Q sn x p = e∈I vn x p(e) = e∈I vn z e 1, so the inequalities (3.3b) hold. As every path p in P has the unit cost ξ p = N , the total cost F (x) given by (3.3a) is equal to

N • f (z).
Conversely, each feasible solution Q, x = (x p : p ∈ Q) of P G defines a feasible solution

I = {e(p) : p ∈ Q} ⊆ E, z = (z e(p) : p ∈ Q) of C G ,
N • f (z) = F (x).
The above construction shows that instances F C G and P DD G represent essentially the same optimization problem. Thus, K = χ f (G) if and only if N • K is the optimal objective function value of P DD G .

Non-bifurcated PD

Certainly, LP formulation (3.2) of problem PD is bifurcated as it does not pose any restrictions on assigning path flows x p except (3.2b). A non-bifurcated version of PD would require that each path in p ∈ P d can carry either flow equal to 0 or to h d . This variant of PD can be easily formulated as a MIP using binary flow variables.

The non-bifurcated version of PD is polynomial in the case of single failures because its optimal solution is equivalent to a corresponding solution of HS, i.e., it consists of a pair of failure disjoint paths. To see this assume (without loss of generality) that there is only one demand in a network, and replace all non-failing links with a pair of failing, parallel ones. In this way an equivalent problem in which all links can fail is obtained. Secondly, the capacities allocated to links resulting from a solution to PD (optimal or not) are reduced, so that they do not exceed h d on any link. Now it is possible to observe that the capacity of the minimal cut in the resulting network is at least equal to 2h d (otherwise, all paths of the PD solution would traverse the same failing link). Then we can exclude from the network, one by one, links that do not belong to any of the 2h d -capacity cuts. The resulting network consists only of links that belong to 2h d -capacity cuts and are of capacity h d . In such a network the only way to route 2h d of flow is to allocate it to two arc-disjoint paths. Notice that according to the max-flow min-cut theorem (see [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF]) such paths can always be found in the resulting network.

For multiple failures the non-bifurcated version of PD is N P-hard by the following reduction from the N P-complete problem Vertex Cover (see [START_REF] Karp | Reducibility among combinatorial problems[END_REF]). Consider problem V C G of finding the minimal vertex cover in graph G = (V, A) that consists of |V| vertices and |A| edges. The corresponding instance PD, denoted by P D G , is specified by a network composed of two nodes u and w connected by |V| parallel links. Each link in P D G corresponds to one node in V C G . There is only one demand (between nodes u and w), and the failure scenario consists of |A| failure states. Each of the states corresponds to a link (denoted by a) in V C G and it affects all links in P D G that correspond to nodes which are not adjacent to the considered link a in V C G . Problems P D G and V C G are equivalent, as each feasible solution to P D G can be transformed to a feasible solution V C G with the same cost, and vice versa.

The transformation applies to all feasible solutions to both problems.

Path generation

Recall that the path generation method (called column generation in the general LP context) is a way to generate paths outside the current set of candidate paths P that can possibly improve the solution obtained for the given P, or to find out that such paths do not exist.

By the general separation theorem (see for example [START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF]), N P-hardness of Path Diversity Design implies difficulty (non-polynomiality) of path generation for the non-compact formulation PDD (3.3) (and hence for the more general formulations PD (3.2)). In the case of PDD, however, it is easy to show that path generation is in fact N P-hard itself. N Phardness of path generation for PDD (3.3) follows directly from the hardness of column generation for problem FGC (3.5). The problem dual to FGC is as follows.

Dual to problem FGC

maximize W (π) = v∈W π v , (3.6a) v∈e π v 1, e ∈ E, (3.6b) π 0. (3.6c)
Note that variable π v corresponds to (3.5b). Hence, to generate a new column for the current optimal dual solution π ⋆ = (π ⋆ v : v ∈ W), i.e., a new independent set e to be added to the current set E, we have to solve the problem of finding an independent set in graph G maximizing the sum v∈e π ⋆ v (this problem is N P-hard as it contains the problem of finding a maximal independent set in a graph, see [START_REF] Garey | Computers and Intractability : A Guide to the Theory of NP-Completeness[END_REF]). If the resulting maximum for solution e is greater than 1 then the new independent set e is added to E. Clearly, generating new paths for problem PDD (3.3) is equivalent to generating new columns for FGC (3.5), and hence the former problem must be N P-hard as well.

As explained in [START_REF] Orlowski | On the complexity of column generation in survivable network design[END_REF], path generation for problem PD (3. PP/PD is polynomial for single-link failure scenarios (when links are subject to failures, but only one link can fail at a time), and N P-hard for scenarios admitting states with simultaneous failures of several links (see [START_REF] Orlowski | On the complexity of column generation in survivable network design[END_REF]Section 3]). In the single-link failure case, the pricing problem can be easily solved by means of any classical shortest path algorithm (as for example the Dijkstra algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF]) for link weights given by w a = ξ a + γ a , where γ a = λ {a} d ⋆ if {a} ∈ S, and γ a = 0, otherwise. As shown before PP/PD is N P-hard for multiple-link failures. In fact, it is N P-hard already for double-link failures, S = {{a, a ′ } ∈ A × A : a = a ′ }, as demonstrated in [START_REF] Coudert | Shared risk resource group complexity and approximability issues[END_REF] for a simpler problem called the minimum-color shortest path problem (assuming ξ a = 0, a ∈ A in (3.7)).

For a multiple-link failure scenario the pricing problem can be formulated as a MIP (mixed-integer program), see problem ( 14) in [START_REF] Orlowski | On the complexity of column generation in survivable network design[END_REF], and resolved as such by a MIP solver.

Still, according to computational experience described in [START_REF] Pióro | Path generation issues for survivable network design[END_REF][START_REF] Stidsen | Optimal routing with single backup path protection[END_REF], such a direct MIP approach is not efficient because the MIP model of the pricing problem does not solve well and fails to deliver solutions in a reasonable time already for networks of very moderate size (10 nodes, say). the path length. Using this transformation, it is possible to solve the pricing problem using algorithms developed for SPPRC, for example based on dynamic programming (see [START_REF] Irnich | Shortest path problems with resource constraints[END_REF]).

A general label-setting SPPRC algorithm was used for the pricing problem related to another resilient design problem (state-independent restoration without stub-release) in [START_REF] Stidsen | Optimal routing with single backup path protection[END_REF].

However, as discussed in [START_REF] Pióro | Path generation issues for survivable network design[END_REF], it turns out that using general label-setting SPPRC algorithms for the pricing problems of PD considered in this thesis is not effective either (as the MIP approach). Fortunately, such label-setting algorithms can be improved and made work efficiently for practical communication networks instances. The way how to do it for PD is described in [START_REF] Pióro | Path generation issues for survivable network design[END_REF], where also numerical examples supporting the above observations are discussed. In this chapter it is assumed that failed flows are restored in a failure-independent fashion, i.e., the restoration flow pattern is always the same, and does not depend on the particular failure state that affects a given primary flow. The failure-dependent case is discussed in Chapter 5.

PR mechanisms are considered assuming two cases of capacity use, i.e., with and without stub-release. In the former case, the capacity on surviving parts (stubs) of a failing path can be reused for backup flows. In the latter case, it is reserved exclusively for the primary flows, and cannot be reused in case of any failure.

FI-nSR: no Stub-Release

First the case without stub-release (nSR) will be considered, i.e., when surviving but unused working capacity cannot be reused for backup flows in failure situations. Notice that nSR is typical for transport layers, e.g., for optical or SONET networks. The generic form of the core optimization problem considered in this section (FI-nSR) is denoted by P and is as follows.

Problem FI-nSR

minimize F (y) = a∈A ξ a (y ′ a + y ′′ a ), (4.1a) r∈T d x dr = 1, d ∈ D, (4.1b) d∈D r∈T ′ ad h d x dr y ′ a , a ∈ A, (4.1c) d∈D r∈R ′′ eds h d x dr y ′′ a , a ∈ A, s ∈ S a \ {O}, (4.1d) y ′′ a 0, a ∈ A, (4.1e) x dr 0, d ∈ D, r ∈ T d . (4.1f)
Problem P consists in minimizing the cost of primary and protection capacities installed on the links subject to a number of constraints. Constraint (4.1b) assures that all demand volumes are realized (x dr is a fraction of h d allocated to pair r = (p, q) ∈ T d ) while (4.1c)

states that in the normal state the load of link a ∈ A cannot exceed its primary capacity.

The flow summation on the left-hand side of (4.1d) is taken over all path-pairs whose backup path contains the considered link a and whose primary path fails in the considered failure state s. Clearly, problem (4.1) assumes that the pool of protection capacity y ′′ a , a ∈ A, is shared by the demands in different situations. Note that, y ′ 0 for all a ∈ A dur to (4.1c).

In the balance of this section N P-hardness of different variants of problem (4.1) will be examined. The variants are distinguished according to the following four criteria:

Complexity overview

As When Criterion 1b is assumed instead of 1a so the flow bifurcation is admitted, i.e., vector x = (x dr : d ∈ D, r = (p, q) ∈ T d ) is continuous, then a demand can be routed on many different primary/backup path-pairs simultaneously. How different the IP and the LP versions of the problem are can be seen in Figure 4.1 depicting the network consisting of 1 proved in this section 2 derived from the proof presented in this section 3 proved by Suurballe, see [START_REF] Suurballe | Disjoint paths in a network[END_REF] 4 proved by Hu, see [START_REF] Hu | Diverse routing in optical mesh networks[END_REF] 5 because D = 1 is N P-hard 6 modification of the main proof presented in this section u w a 1 a 2 a N a N+1 two nodes u and w, N + 1 links a 1 , a 2 , . . . , a N +1 , and one demand d between u and w with h d = 1. Suppose that ξ an = 1, for n = 1, 2, . . . , N + 1. Clearly, any optimal solution of the IP version consists (by definition) of just one primary/backup path-pair, and must cost 2 units. On the contrary, an optimal solution of the LP version uses N different primary paths protected by one common backup path. Such a solution is for example obtained by assigning flow x dr = 1 N to each of the N path-pairs (p n , q), for n = 1, 2, . . . , N , where p n = {a n } and q = {a N +1 }. Hence, y ′ an = 1 N , y ′′ an = 0, for n = 1, 2, . . . , N and y ′′ a N +1 = 1 N , y ′ a N +1 = 0, and the backup capacity of link a N +1 is shared among the different backup paths in different failure states (each of these failure states affects exactly one link). The cost of this solution is 1 + 1 N , i.e., almost 50% cheaper than the non-bifurcated solution.

Later in this section it is proved that the 1a, 3a (IP, single failures) variant of problem (4.1) is N P-hard. Moreover, the fact that any approximation of the problem better than a 4 3 -approximation is N P-hard is also proved.

Proceed now to the case with multiple demands and with the single failure scenario (3a, 4b). The N P-hardness of the LP case (variant 1b, 3a, 4b) is directly implied by the N P-hardness of the case with only one demand (Criteria 1b, 3a, 4a), since when something is difficult for the single demand case it has to be difficult also for multiple demands. As far as the IP version is concerned (1a, 3a, 4b), it is impossible to follow the same way of reasoning, because the single demand case can be solved in polynomial time. In fact, the version admitting multiple demands is N P-hard. In order to prove this it is possible to use a simple construction presented in this section, and reduce the Partition problem to the considered variant of problem P. However, since this construction gives weak results concerning the complexity of the problem's approximations, the main proof of this section will be extended to cover the IP variant of the problem admitting multiple demands (variant 1a, 3a, 4b).

As far as the multiple failure variant 1b, 3b, 4a is concerned, its complexity can be deduced from [START_REF] Hu | Diverse routing in optical mesh networks[END_REF] where it is proved that finding any pair of failure-disjoint paths when multiple failures are admitted is N P-hard. As each feasible solution to the problem consists of assigning the demand volume to one or more of such pairs, it is clear that finding any of them cannot be completed in polynomial time.

N P-hardness proof (many demands, IP)

Consider the variant of problem P assuming Criteria 1a, 2a, 3a, and 4b, i.e., IP, limited lists of path-pairs, single failures, and many demands. The N P-hardness of this case can be demonstrated using a reduction of the Partition problem to the considered problem.

Partition was proved to be N P-hard in [START_REF] Garey | Computers and Intractability : A Guide to the Theory of NP-Completeness[END_REF]. Consider a given sequence Proof. It will be first proved that the optimal objective F ⋆ of F I H is not less than 3 2 H. Indeed, it must be that y

H = (h 1 , h 2 , . . . , h D )
′ a 1 + y ′ a 2 + y ′ a 3
H (because the total demand volume to be realized from u to w is equal to H), and that y ′′

a 2 + y ′′ a 3 y ′ a 1 , y ′′ a 1 + y ′′ a 3 y ′ a 2 and y ′′ a 1 + y ′′ a 2 y ′ a 3
(because when link a fails then its primary capacity y ′ a must be restored on the protection capacity of the two remaining links). Summing up the last three inequalities and using the first inequality we get 2

•(y ′′ a 1 +y ′′ a 2 +y ′′ a 3 ) y ′ a 1 +y ′ a 2 +y ′ a 3
H, and hence y ′′ a 1 +y ′′ a 2 +y ′′ a 3 1 2 H. Thus, F ⋆ 3 2 H. Next, it will be shown that a valid partition (D ′ , D ′′ ) yields an optimal solution of F I H . Such a solution is obtained by assigning the path-pair r ′ = (p ′ , q) to all demands from D ′ , and the path-pair r ′′ = (p ′′ , q) to all demands from D ′′ , where the primary path p ′ is composed of link a 1 , the primary path p ′′ is composed of link a 2 , and the common backup path q is composed of link a 3 . Then

y ′ a 1 = y ′ a 2 = y ′′ a 3 = 1 2 , y ′ a 3 = y ′′ a 1 = y ′′ a 2 = 0
, and the resulting objective F (y) is 3 2 H, thus optimal. Finally, it will be proved that any optimal solution of F I H defines a valid partition of D. Let y ′ a , y ′′ a , a ∈ A be such an optimal solution. Introducing the notation y a = y ′ a + y ′′ a , a ∈ A it is possible to write that y a 1 + y a 2 + y a 3 = 3 2 H (because the solution is optimal and hence F (y) = 3 2 H) and y a 2 + y a 3 H, y a 1 + y a 3 H and y a 1 + y a 2 H (because when link a fails then the total demand volume must be carried on the remaining links). The only solution y = (y a 1 , y a 2 , y a 3 ) fulfilling these conditions is y a 1 = y a 2 = y a 3 = 1 2 H. Now consider any fixed link a. Jointly, the primary capacity y ′ a and the backup capacity y ′′ a of this link carry exactly

1 2 d∈D h d of flow. Define D ′ = {d ∈ D : ∃ r = (p, q) ∈ T d , x dr = 1 ∧ (a ∈ p ∨ a ∈ q)} and D ′′ = D \ D ′ . Then, clearly, D ′ = 1 2 H and hence (D ′ , D ′′ ) is a valid partition of D.

N P-hardness proof (one demand, LP)

Now consider the linear relaxation of problem P (i.e., problem (4.1)) admitting all possible path-pairs, with the full single link failure scenario (i.e., all links can fail, one at a time), and with only one demand (D = 1). Below, it is proved that this variant (i.e., variant 1b, 2b, 3a, 4a) is also N P-hard by reducing the 2Div-Path problem to it. 2Div-Path has been proved to be N P-hard in [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF].

Consider a directed graph and two pairs of its vertices (u 1 , w 1 ) and (u 2 , w 2 ). Assume that all four vertices are different. Problem 2Div-Path consists in answering a question whether there exist two arc-disjoint directed paths, one from u 1 to w 1 , and the second from u 2 to w 2 , in a given graph. Notice that the problem cannot be solved using an appropriately modified Suurballe algorithm [START_REF] Suurballe | Disjoint paths in a network[END_REF], since the algorithm cannot assure that in the two resulting paths u 1 will be connected to w 1 and not to w 2 . Moreover, notice that the problem is solvable in polynomial time in undirected graphs [START_REF] Seymour | Disjoint paths in graphs[END_REF]. Thus, the proof cannot be applied to undirected cases.

Consider an instance 2D G of 2Div-Path for a given graph G = (V, A) and u 1 , u Proof. Consider 2D G and suppose that the two disjoint paths from the question exist. Denote these paths by u 1 → w 1 and u 2 → w 2 . Now construct a solution to F I G with the objective function value equal to 3 2 by routing the demand using two primary/backup path-pairs. Each of these pairs carries flow x = 1 2 . The first primary flow traverses links a a , a c , and a f , while its corresponding backup flow is routed through links a b , a d , path u 1 → w 1 , and link a g . The second primary flow travels through links a b , a e , path u 2 → w 2 , and link a g ; its corresponding backup flow passes links a a , a d , path u 1 → w 1 , and link a f . Notice that each primary/backup flow pair is arc-disjoint. Moreover, the two primary paths are also arcdisjoint, and both backup flows use link a d . Therefore, they can share the backup capacity y ′′ a d on it. Thus, we have to reserve 1 2 of primary capacity on links a c and a e , and 1 2 of backup capacity on link a d . It means that the objective of the corresponding solution of F I G is 3 2 . Observe that this solution would not be feasible, if u 1 → w 1 and u 2 → w 2 were not arc-disjoint. Now assume that 2D G has no solution, i.e., it is impossible to route two flows, the first from u 1 to w 1 and the second from u 2 to w 2 , using arc-disjoint paths. Then, several cases can occur, including the existence of two other arc-disjoint paths: one from u 1 to w 2 , and one and from u 2 to w 1 . Below it is proved that in all such cases the objective of F I G cannot be smaller than 2.

Define three sets of links, namely A = {a a , a b }, B = {a c , a d , a e }, and C = {a f , a g }. Notice that each of these sets cuts the network, so removing any of them results in a situation when a path between nodes u and w does not exist. Moreover, the links in the sets are directed in the way making it impossible to traverse more than one link from any of these sets using only one path. Therefore, each path from P d has to pass exactly one link from each of the sets A, B, C.

Divide (all possible) paths in P d into groups with respect to the links they traverse. In effect, distinguish |A| • |B| • |C| = 12 different groups; out of them only 6 are not empty. For instance, there is no path that traverses links a a , a c , and a g . The available groups are shown in Table 4.2. For each of the groups calculate all possible groups of backup paths (certainly, a primary path and its backup path have to be arc-disjoint). The possible backup path groups are also shown in the table. Each group is identified by an appropriate triple. For instance, a group of paths that traverse links a a , a c and a f is denoted by acf . Notice that any simple non-bifurcated solution of F I G that uses just one primary/backup path-pair has the objective function equal to 2, as both the primary and the backup path have to traverse one link from set B, and ξ a = 1 only if a ∈ B. Moreover, it is impossible to reduce

a -c -f b -d -g or b -e -g a -d -f none a -d -g b -e -f b -e -f a -d -g b -e -g a -c -f b -d -f none b -d -g a -c -f
a -c -f b -e -g b -d -g or b -e -g a -c -f a -c -f b -d -g b -d -g or b -e -g a -c -f a -d -g b -e -f b -e -f a -d -g
the cost corresponding to the reserved primary capacity. Therefore, in order to improve the solution, it is inevitable to find a way to reduce the cost corresponding to the reserved backup capacity. It can be done by analyzing all possible arc-disjoint pairs of primary paths, as backup capacity can be shared only by backup flows that belong to primary/backup pathpairs whose primary flows cannot fail simultaneously. In the considered case (single failures) this means that the primary paths have to be arc-disjoint. All possible arc-disjoint primary paths, together with all possible backup paths protecting them, are shown in Table 4.3.

It is clearly visible in the table that when 2D G has no solution it is impossible to find two arc-disjoint primary/backup path-pairs in such a way that the primary paths of these pairs are also arc-disjoint, and their backup paths traverse the same link a ∈ B. Therefore, when 2D G has no solution (or its solution is not known) the cost of F I G cannot be lower than 2.

Complexity of approximation schemes

From the proof of Proposition 4.1.2 it is possible to draw conclusions concerning complexity of various approximation schemes that solve the 1b, 3a, 4a variant (LP, single failures, one demand) of problem P. When a solution to an instance 2D G of 2Div-Path exists (and can be found), the objective of a solution to the corresponding instance F I G is not greater than 3 2 . On the other hand, when a solution to 2D G is not known, solutions to F I G cannot use such a path-pair. Therefore, the corresponding objectives must be equal at least to 2. Thus, since there is no way to solve 2Div-Path in polynomial time, any approximation to the considered variant of P better than a 4 3 -approximation has to be N P-hard. Note that the same reasoning can be applied also to the 1b, 3a, 4b variant (LP, single failures, many demands).

From the proof of Proposition 4.1.1 (IP, single failures, many demands) it is also possible to draw some conclusions concerning complexity of approximation schemes. Suppose that the answer to the considered instance of the Partition problem (P A H ) is NO. In such a case, the quality of a solution to the corresponding instance F I H depends on how precise we can approximate a solution to P A H . Note that Partition is equivalent to a special case of the Subset Sum problem, for which Kellerer et al. in [START_REF] Kellerer | An efficient fully polynomial approximation scheme for the subset-sum problem[END_REF] presented a fully polynomial approximation scheme that solves it within accuracy ε in time O(min{n Consider a special case when demands from the set D can be divided into two subsets D ′ and D ′′ , such that d∈D ′ h d = d∈D ′′ h d . Without loss of generality we can assume that d∈D h d = 1. Now treat the set D as one demand that can be split into halves. Note that in the proof of Proposition 4.1.2 one demand is equally split into two flows. Therefore, it is possible to apply the reasoning from that proof also to the case considered in Proposition 4.1.1. That is why, all polynomial approximations to the 1a, 3a, 4b variant (IP, single failures, many demands) of problem P also cannot be better than a 4 3 -approximation. For variants 3b (multiple failures) of P, the problem is straightforward, as it was proved in [START_REF] Hu | Diverse routing in optical mesh networks[END_REF] that finding a pair of failure-disjoint paths, when multiple failures occur, is N P-hard.

• 1 ε , n + 1 ε 2 log( 1 ε )}).
Therefore, finding any feasible solution to the considered problem is N P-hard. That is why, all approximation schemes that give any guarantee concerning the quality of a solution have to be N P-hard. That concerns both LP and IP variants.

The results concerning the complexity of approximation schemes that solve different variants of the problem P are presented in Table 4.4.

Path generation

The pricing problem for the bifurcated FI-nSR (denoted by Price-FI-nSR) consists in finding, for each demand d ∈ D, a pair of failure-disjoint paths r = (p, q) from u d to w d 4 3 -approximation is N PH any approximation is N PH minimizing the quantity (see also [START_REF] Orlowski | On the complexity of column generation in survivable network design[END_REF])

r = a∈p ξ a + a∈q ( s∈ Sp π s a ⋆ ) (4.2a)
where π s a ⋆ are the optimal dual variables corresponding to constraints (4.1d). Notice that in (4.2a) the link metrics for calculating the length of the primary path p ∈ P d are equal to the true unit link costs ξ a , while the link metrics for calculating the length of the backup path q ∈ Q p are given by the dual cost s∈ Sp π s a ⋆ . Because the bifurcated version of FI-nSR is N P-hard for all failure scenarios, its pricing problem cannot be polynomial. In fact Price-FI-nSR is N P-hard, as demonstrated (for the single link failure case) in [START_REF] Stidsen | Optimal routing with single backup path protection[END_REF] by reduction from 3-Sat (see [START_REF] Garey | Computers and Intractability : A Guide to the Theory of NP-Completeness[END_REF]). Although the pricing problem Price-FI-nSR is N P-hard, FI-nSR can in practice be effectively solved even for large networks by path-pair generation, as discussed for instance in [START_REF] Pióro | Path generation issues for survivable network design[END_REF].

FI-SR: Stub-Release

The case considered in this section assumes failure independent flow restoration using stubrelease (SR), i.e., when surviving but unused working capacity can be reused for backup flows in failure situations.

The use of SR is typical for traffic layers in communication networks, for example for the MPLS sub-layer in IP networks. The non-bifurcated problem for FI-SR assumes that for each d ∈ D, its entire demand volume is allocated to a single primary path, and in each failure state that affects the selected primary path, the flow is moved to another, failure-independent single restoration path.

Problem FI-SR minimize F (y) = a∈A ξ a y a , (4.3a)

r∈T d x r = 1, d ∈ D, (4.3b) d∈D h d ( r∈T ′ ad ∧s∈Sp x r + r∈T ′′ ad ∧s∈ Sp x r ) y a , a ∈ A, s ∈ S a , (4.3c) x dr ∈ {0, 1}, d ∈ D, r ∈ T d , (4.3d) y a 0, a ∈ A. (4.3e)

Complexity overview

The complexity of FI-SR with respect to criteria presented in Section 4.1 is identical to the complexity of FI-nSR. This fact will be proved in the two following sections. An overview of the complexity can be seen in Table 4.1.

Bifurcated flows

The bifurcated version of FI-SR is obtained in the same way as for FI-nSR, leading to a linear relaxation of (4.3), admitting as before, for every d ∈ D, several non-zero primary flows and several backup flows protecting each primary flow. This version is also N P-hard. To prove that, a construction proving N P-hardness of FI-nSR can be used. It is possible because in fact stub-release cannot be effectively used when only state-independent restoration is allowed, single failures of all links are admitted, and one demand is under consideration.

Lemma 4.2.1. Stub-release cannot be effectively used in the presented scenario.

Proof. Consider two flows denoted by α and β consisting of their primary and backup paths denoted by α p , β p , α b , and β b . Assume now that stub-release is effectively used, and the path α b uses, through stub-release, the capacity released by the path β p . Note that the path α b cannot use the capacity released by the path α p , as they have to be failure disjoint.

Because of the state-independent restoration assumption, the path β p has to fail each time the path α p fails, as it has been assumed that (single) failures of all links occur. In this case, the path β p has to consist of at least all the links of the path α p . Since only one demand is considered, flows α and β origin and terminate in the same nodes. Therefore, in order to fulfill the previous observations, the paths α p and β p have to be the same.

Because of the state-independent restoration, the paths α p and α b have to be disjoint. It means that also the path α b and the path β p have to be disjoint, as the paths α p and β p are the same.

On the other hand, when the path α b is supposed to use the capacity released by the path β p those paths cannot be disjoint. That leads to a contradiction, because they cannot be disjoint and not disjoint simultaneously. Therefore, stub-release cannot be effectively used in the considered scenario. This fact allows to use the same construction as in Section 4.1 in order to prove the N P-hardness of the stub-release case.

Non-bifurcated flows

The difficulty of this problem is similar to the difficulty of FI-nSR. For scenarios with multiple failures, the problem is N P-hard already for one demand, as finding a pair of failure disjoint paths is difficult. In the case of multiple demands, problem Partition can be reduced to the considered problem, as demonstrated for FI-nSR in Section 4.1. When only one demand is considered, and only single failures are admitted the problem, as FI-nSR, can be solved in polynomial time. However, this time it is impossible to use the Suurballe algorithm [START_REF] Suurballe | Disjoint paths in a network[END_REF] directly, as it is not able to take the stub-release into account. Therefore, another polynomial algorithm is needed. It will be described in this section.

The considered problem (i.e., FI-SR with one demand, single failures, and non-bifurcated flows), denoted by Failure-Disjoint Paths, is a generalization of the Shortest Path problem and the 2 Arc-Disjoint Path problem. In fact polynomial time algorithm solving those two problems (e.g., Dijkstra's algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF] solving Shortest Path, and Suurballe's algorithm [START_REF] Suurballe | Disjoint paths in a network[END_REF] solving 2 Arc-Disjoint Path) are used as subroutines in the presented approach solving Failure-Disjoint Paths.

Assume two kinds of arcs: perfectly reliable arcs that do not fail, and unreliable arcs that do fail. Suppose that the two paths can share only the reliable arcs, so a pair of failure-disjoint paths is considered. The Minimum Cost Flow problem can cover the notion of reliability by setting capacities of reliable arcs to infinity and capacities of other arcs to 1. However, in this section under consideration is the problem of finding a shortest pair of failure-disjoint paths, where the cost of any reliable arc that is used by both paths is counted only once and not twice like in the Minimum Cost Flow context. Consider a graph presented in Figure 4.3 with arc costs as depicted in the picture and reliable arcs denoted by thick arrows. Assume that u is the source, and w is the sink. The optimal solution to 2 Arc-Disjoint Path has the cost equal to 11, and consists of paths (u, v 1 , w) and (u, v 3 , w).

After adding the notion of reliability, an optimal solution of Minimum Cost Flow is given by sending two units of flow through paths (u, v 1 , v 3 , w) and (u, v 3 , w). The cost is then equal to 10. Finally, the optimal solution to Failure-Disjoint Paths costs 8 and consists of paths (u, v 1 , w) and (u, v 1 , v 3 , w). Moreover, by the max-flow min-cut theorem, it is easy to see that the problem is equivalent to computing a minimum cost set of arcs inducing a graph containing at least one path from u to w when there are no failures, and also one path for any failure of an unreliable arc.

If all arcs are reliable then

Lemma 4.2.2.

There exists an optimal solution to Failure-Disjoint Paths not containing directed cycles.

Proof. If the solution contains a directed cycle, then a flow on this cycle can be decreased, and some arcs of the cycle can be eliminated. This does not decrease the total flow carried from u to w, and does not increase the cost. By repeating this operation a solution without directed cycles is obtained. Now assume that the paths share L (reliable) arcs. Two ordered collections L = (a 1 , a 2 , . . . , a L ) and L ′ = (a ′ 1 , a ′ 2 , . . . , a ′ L ) are introduced. They define the order of the shared arcs from the point of view of the first and the second path, respectively.

Lemma 4.2.3.

There exists an optimal solution to Failure-Disjoint Paths where L = L ′ . Proof. Observe that if L = L ′ then the solution contains directed cycles. According to Lemma 4.2.2 there is at least one optimal solution without directed cycles, thus at least one with L = L ′ From Corollary 4.2.3 we can deduce that there exists an optimal solution containing a sequence L of reliable arcs shared by both paths, and traversed in the same order. Notice that if L = ∅ then the solution is simply a pair of arc-disjoint paths. These arcs are connected with each other, and with u and w, by pairs of arc-disjoint paths. Such an optimal solution can be obtained using the following algorithm.

First, compute a shortest pair of arc-disjoint paths from each vertex i to each vertex j where i is either u or a sink of any reliable arc, and j is either w or a source of any reliable corresponds to paths (u, v 1 , v 3 ) and (u, v 3 ), and its cost is equal to a cost of the pair it represents. Notice that there are no pairs of arc-disjoint paths from or to vertex v 2 . Therefore, this vertex is isolated in the modified graph.

In the resulting modified graph, which consists of pairs of arc-disjoint paths (represented by newly added arcs) and of reliable arcs a shortest path is computed. In the considered example the shortest path is (u, v 1 , w), and it costs 8.

Consider a set L = (a 1 , a 2 , . . . , a L ) (reliable arcs set) consisting of reliable arcs selected by the shortest path algorithm in the previous phase of the algorithm, and a collection of sets Proof. According to Corollary 4.2.3 there exists an optimal solution that consists of either a pair of arc-disjoint paths from u to w or a set of reliable arcs connected by pairs of arc-disjoint paths. Such a solution cannot be cheaper than the cost of the graph G.

A h (path pairs sets), where h ∈ H = {{u, a 1 }, {a 1 , a 2 }, . . . , {a L-1 , a L }, {a L ,
Lemma 4.2.5. G contains a pair of failure-disjoint paths from u to w.

Proof. Transform the graph G to a graph T by adding parallel arcs to those in L. The graph G consists of the collection L = {a 1 , a 2 , . . . , a L } of shared arcs connected by pairs of arc-disjoint paths (sets A h ). Therefore, we know that in T the value of the minimum cuts between u and the source of a 1 , between the sink of a i and the source of a i+1 , where i = 1, 2, . . . , L -1, and between the sink of a L and w is not less than 2 (remember that pairs of arc-disjoint paths between those pairs of vertices exist in T ). Moreover, the value of the minimum cut in T between the source of a i and the sink of a i , where i = 1, 2, . . . , L, is also not less than 2 (all arcs in L are reliable, so they are doubled in T ). Therefore, it is obvious that the minimum cut in T between u and w cannot be smaller than 2. Using the max-flow min-cut theorem it is possible to conclude that the maximum flow in T from u to w cannot be smaller than 2. Since each unit of flow flowing through the network corresponds to a path, we get two paths from u to w. Moreover, only reliable arcs can be utilized by both paths, because only those arcs were doubled during the transformation. Therefore, a pair of failure-disjoint paths in G from u to w has to exist. Proof. The problem can be solved using the presented algorithm. It requires, in the first phase, the computation of shortest pairs of arc-disjoint paths between a polynomial number of pairs of vertices. Then, a shortest path is computed to get G (and also T ). Finally, a shortest pair of arc-disjoint paths in G is computed which gives us the wanted optimal pair of failure-disjoint paths in G. Notice, that the last phase is needed only if some arcs have 0 costs.

In the first phase of the algorithm, in the worst case, pairs of arc-disjoint paths are computed between all possible pairs of nodes. Then a shortest path is computed once in the second phase. The last phase consists in computing a shortest pair of arc-disjoint paths once.

Thus the overall complexity of the algorithm is determined by the complexity of the first phase which is O(|V| • |A| • log (1+|A|/|V|) |V|), i.e., |V| times the complexity of the algorithm presented in [START_REF] Suurballe | A quick method for finding shortest pairs of disjoint paths[END_REF] to compute pairs of arc-disjoint paths from one source to all other vertices in a graph.

Generalizations for non-bifurcated flows

Failure-Disjoint Paths can be extended in many ways. This section contains a few of its interesting generalizations.

Pair of failure-disjoint paths with cost depending on flow

Consider a natural generalization of the problem defined, and studied, earlier, where cost depends on flow. If an arc a is reliable, i.e., a ∈ A/S, then ξ a (0) = 0, ξ a (1) = ξ 1 a and ξ a (2) = ξ 2 a . In other words, if a is used by one path, then we have to pay ξ 1 a , and if both paths use a, we should pay ξ 2 a . Assume that ξ 2 a ξ 1 a . The unreliable arcs cannot be used by more than one path, so only ξ 1 a has to be defined for a ∈ S. The objective function is

a∈A ξ a (f a )
. Now, it is easy to see that this problem can be solved using the algorithm presented earlier. It is enough to use ξ 1 a while computing shortest pairs of arc-disjoint paths in the first phase, and ξ 2 a for reliable arcs while computing the shortest path in the modified graph. Since the correctness proof of the algorithm remains the same, details are skipped.

A general minimum cost flow problem

a∈δ + (i) f a - a∈δ -(i) f a = 0, i ∈ V\{u, w}, (4.4b
) for example, [START_REF] Guisewite | Minimum concave-cost network flow problems: applications, complexity, and algorithms[END_REF] for results related to concave flows. It will be shown that General F-D

a∈δ + (u) f a - a∈δ -(u) f a = k, (4.4c) f a ∈ {0, 1, . . . ,
Paths is N P-hard by proving the N P-hardness of one of its interesting special cases.

Infinite capacities

Consider the problem where all arcs can be either reliable (can accommodate an infinite g , corresponds to one element g from the universe U. The source u is connected to all vertices of the first group using reliable arcs of cost 1. A vertex n ′ h from the first group is connected, using an unreliable arc of zero cost, to a vertex n ′′ g from the second group, if g ∈ h. Finally, each vertex of the second group is connected to w using an unreliable arc of zero cost. In this network |U| paths from u to w are to be found. A sample instance of IC U can be seen in

Limited number of reliable arcs

Assume that the number of reliable arcs (reliable arcs can accommodate an infinite number of paths) is fixed and is not a part of the input. Moreover, ξ a (f a ) is constant and equal to ξ a , if f a > 0. Still ξ a (0) = 0, for all a ∈ A. In such a situation the problem is in P, because it can be solved in polynomial time by enumerating all possibilities, i.e., solving Minimum Cost Flow for all possible vectors x = (x a 1 , x a 2 , . . . , x a N ), where N is the number of reliable arcs and x an = {0, 1}. For each vector x the network is modified as follows. If x a = 1 then c a = k and ξ a is reduced to 0. If x a = 0 then arc a is deleted from the graph. After solving Minimum Cost Flow in such a network, the result is increased by N i=1 ξ a i x a i , which is the cost of using (if x a = 1) reliable arcs. The solution with the smallest modified cost is the optimal solution of the considered version of General F-D Paths.

In fact, the problem is still polynomial even if the cost function is general, and the number of arcs that can carry more than one unit of flow is limited. Indeed, if the value of the flow on these N arcs is considered, the total number of possibilities is less than (k + 1) N which is polynomial if N is constant.

Acyclic graphs

Assume that the number of paths k is given, and is not a part of the input. The cost function is the most general one: F (f ) = a∈A ξ a (f a ). Notice that this function is generally neither convex nor concave. In such a situation General F-D Paths is polynomial for acyclic graphs. It will be proved now.

Assume that N is acyclic, and at least k units of flow can be carried from u to w. If the last is not possible, then General F-D Paths does not have a solution.

Sort A in topological order starting from u and ending at w. This sorted sequence will be denoted by

V ′ = (v 1 , v 2 , . . . , v |V ′ | ). Note that v 1 = u, v |V ′ | = w and V ′ ⊆ V (
G i , 1 i |V ′ |, if v i ∈ M and v j / ∈ M, for all j > i (v i , v j ∈ V ′ ). Call a state M ′ (M ′ ∈ G j ) a predecessor of a state M (M ∈ G i ) if: • j < i, • |M ′ v l | |M v l |, for all l < i, • if |M ′ v l | > |M v l | then an arc (v l , v i ) exists, and c (v l ,v i ) |M ′ v l | -|M v l |, for all l < i.
It is possible to build a state graph that consists of a set of vertices representing states and a set of arcs representing predeceasing relations, i.e., there is an arc from

M ′ to M, if M ′ is
a predecessor of M. The cost of this arc is given by ξ

(M ′ ,M) = v∈M ′ ,(v,v i )∈A ξ (v,v i ) (|M ′ v | - |M v |).
Given an optimal solution of state M ′ , ξ (M ′ ,M) represents the additional cost that is incurred by extending this solution, i.e., by sending

|M ′ v | -|M v | units of flow on arc (v, v i ) ∈ A, for each v ∈ V.
Notice that the state graph does not contain directed cycles. Going back to the example in Figure 4. [START_REF] Ash | Dynamic routing in telecommunications networks[END_REF] where k = 2. The vertices are already sorted there topologically from left to right, i.e., V ′ = (u, v 1 , v 2 , v 3 , w). The corresponding state graph can be seen in Figure 4.6. One can see that state (v 2 , v 2 ) does not have any predecessor.

This simply means that it is not possible to have 2 paths from u to v 2 satisfying capacity constraints. Moreover, states depicted in grey are irrelevant from the point of view of the algorithm, as there is no path connecting them to a state (w, w, . . . , w). Therefore, for sake of clearness of the figure, all arcs entering those irrelevant states are also gray, and their costs are not depicted.

Consider now an optimal solution F ⋆ of state M ∈ G i , where i > 1. Remember that this solution is a set of k paths such that the number of paths ending at v ∈ M is exactly

|M v |. By considering predecessors v of v i , for all |M v i | paths reaching v i and increasing by one values of corresponding |M v |, we get a new state M ′ that is a predecessor of a state M.
Moreover, a feasible solution of this state is obtained. The cost of this solution is equal to

the cost of F ⋆ minus v∈M ′ ,(v,v i )∈A ξ (v,v i ) (|M ′ v | -|M v |).
This feasible solution should also be optimal for state M ′ , since otherwise it is possible to build another solution of M with a cost less than the cost of F ⋆ . Said another way, the cost of an optimal solution of M can be computed by examining optimal costs of the predecessors of M. Consequently, an optimal solution of the problem can be obtained by computing a shortest path from state (u, . . . , u) to state (w, . . . , w).

In the example the shortest path is ((u, u), (v 1 , v 1 ), (v 1 , v 3 ), (w, w)). It costs 8, thus it is optimal.

s,s A similar dynamic programming approach for a minimum concave cost network flow problem in acyclic uncapacitated networks was proposed in [START_REF] Burkard | Linear approximations in a dynamic programming approach for the uncapacitated single-source minimum concave cost network flow problem in acyclic networks[END_REF].

t,t v ,v 1 2 v ,v 1 1 s,v 1 s,v 2 v ,v 3 3 v ,v

Large capacities

Consider General F-D Paths, where c a k 2 and ξ a (f a ) = ξ a , for all a ∈ A, still ξ a (0) = 0. In such a case the algorithm solving FI-SR presented earlier in this section can be used. This fact will be proved now.

Take any solution to the considered General F-D Paths, and a network N = (V ′ , A ′ ) induced by f a variables of the solution and capacities equal to those variables. Now decrease the capacities in the way that c a = 1 if f a < k, and c a = 2 if f a = k. This modified network will be refereed to as N ′ . Lemma 4.2.9. Two units of flow can be carried from u to w in N ′ .

Proof. Using the max-flow min-cut theorem it is possible to deduce that in N the minimum cut has to consist of at least one arc of capacity k or at least two arcs of any capacity. As all arcs of capacity k are transformed to arcs of capacity 2 in N ′ , the minimum cut in N ′ cannot be smaller than 2. It means that the maximum flow also cannot be smaller than 2.

Lemma 4.2.10.

There exists an optimal solution to the considered problem that consists of two sets of paths P and P ′ , such that

|P| = ⌈ k 2 ⌉, |P ′ | = ⌊ k 2 ⌋
, and paths from the same set are identical.

Proof. Consider any optimal solution to the problem, and its corresponding N ′ network. The cost of this network ( a∈A ′ ξ a ) is equal to the cost of the considered solution. From Lemma 4.2.9 we know that in N ′ there exists a pair of paths that can share arcs of capacity k only. By putting ⌈ k 2 ⌉ -1 additional paths identical to the first path, and ⌊ k 2 ⌋ -1 additional paths identical to the second, a new solution is obtained. The solution is feasible, as all capacity constraints are satisfied. Moreover, it cannot be more expensive than the previous solution, thus it is also optimal.

The shortest pair of failure-disjoint set of paths mentioned in Lemma 4.2.10 can be obtained by running the algorithm for Failure-Disjoint Paths in a graph where an arc

a belongs to S, if x a < k. Proposition 4.2.11. General F-D Paths is in P, if c a k 2 and ξ a (f a ) = ξ a (ξ a (0) = 0), for all a ∈ A.
Proof. An optimal solution to this problem can be obtained by having ⌈ k 2 ⌉ identical paths to the first path returned by the algorithm for Failure-Disjoint Paths and ⌊ k 2 ⌋ identical paths to the second path returned by the algorithm. The procedure is polynomial, thus the problem is in P. where optimal dual variables π s a ⋆ correspond to (4.3c). As discussed in [START_REF] Orlowski | On the complexity of column generation in survivable network design[END_REF], already minimizing the first sum under a single link failure scenario is N P-hard; hence, solving the whole problem Price-FI-SR is N P-hard.

Path generation

Chapter 5 Path Restoration Problems with Failure-Dependent Restoration

In this chapter failure-dependent path restoration (FD) is considered. This means that the backup routing of a demand depends on the particular failure state.

FD-nSR: no Stub-Release

In the case without stub-release (nSR), the non-compact MIP formulation of the nonbifurcated version of the FD-nSR problem is as follows.

Problem FD-nSR minimize F (y) = a∈A ξ a (y ′ a + y ′′ a ), (5.1a)

r∈W d x dr = 1, d ∈ D, ( 5
x dr ∈ {0, 1}, d ∈ D, r ∈ W d , (5.1e) y ′′ a 0, a ∈ A. (5.1f)
As explained in Chapter 2, the set W d , defined for each d ∈ D, contains sequences r = (p, q s : s ∈ Sp ) of paths from u d to w d with the property that path q s works in state s ∈ Sp . These sequences are predefined. Therefore, the set W ′ ad of all sequences r = (p, q s : s ∈ Sp ) such that a ∈ p, and the set W ′′ ads of all sequences r = (p, q s : s ∈ Sp ) such that a ∈ q s for s ∈ Sp are known in advance and are used in constraints (5.1c) and (5.1d), respectively, to compute the load of the links in different states. Due to (5.1b), in an optimal solution for each d ∈ D there is exactly one r ∈ W d with x dr = 1, and this particular sequence is used to realize the demand d in the non-bifurcated manner. Note that, due to (5.1c), y ′ a 0 for all a ∈ A.

The non-bifurcated FD-nSR problem can be solved in polynomial time only when single links failures are admitted, and only one demand is considered. In such a case the reasoning of Section 3.2 can be used (showing that HS is a solution to non-bifurcated PD in the single link failure case), so any obtained solution can be transformed to another valid solution of the same or smaller cost that consists of two failure-disjoint paths. The only difference between PD and FD-nSR in this case is that in the latter case link capacities are reduced either to h d or to 2h d (due to the fact that backup flows can share capacity) before the actual procedure is invoked. Notice that the same reduction is performed for the former case in the first step of the algorithm.

In the case of multiple failures the problem becomes N P-hard, as Vertex Cover (see Section 3.2) can be reduced to it. Also in this case it is possible to directly follow considerations presented for PD. In fact, for the network used in those considerations, problems PD and FD-nSR are equivalent.

When more than one demand is admitted the problem also becomes N P-hard. In this case ideas presented for FI-nSR (Section 4.1) can be utilized, and an appropriate reduction from Partition can be used. The proof uses a network that consists of two nodes and three parallel directed links. In this network each possible simple path consists of only one link. Therefore, there is no difference between FI-nSR and FD-nSR, as each path can fail only in one failure state (single link failures are only considered).

Again, the bifurcated version of FD-nSR is obtained by relaxing the binary flow variables.

In the bifurcated version the demand volume h d , for each demand d ∈ D, can be realized on several working paths, and each resulting primary flow can be protected by failure-dependent sets of several backup paths. The bifurcated version of FD-nSR is of polynomial complexity for single link failure scenarios, as a compact formulation can be easily written down in the node-link notation (see (3.4)). For multiple failures, however, problem FD-nSR is N P-hard itself. It will be demonstrated in this section.

Proposition 5.1.1. FD-nSR is N P-hard when multiple failures are admitted.

The proof uses essentially the same construction of network N as the proof of Proposition 3.2.1 given in Section 3.2. The only modifications are as follows.

• One additional node w and one additional directed link (w, v 0 ) are introduced into network N .

• Link (w, v 0 ) is assigned the unit capacity cost equal to 1 (ξ (w,v 0 ) = 1), and the rest of the links t 1 , t 2 x p }, (5.2a)

p∈P x p = 1, (5.2b)
x p 0, p ∈ P.

(5.2c)

Observe that objective (5.2a) minimizes, over all failure states s ∈ S, the maximum amount of the total flow failing in state s since this is the actual cost of protection capacity (the cost of primary capacity is always equal to 1). Certainly, for network N the objective (5.1a) of problem FD-nSR and the objective (5.2a) of problem FDM are related by the equality F (y) = 1 + G(x). In the sequel assume that F D G is an instance of problem (5.2) rather than (5.1).

Lemma 5.1.2. The fractional chromatic number χ f (G) of graph G is equal to K if and only if the cost of an optimal solution of problem

F D G is equal to 1 -1 K . Proof. Let Q, x = (x p : p ∈ Q) be an optimal solution of the instance P DD G of problem PDD (3.3). Due to Lemma 3.2.2, F (x) is equal to N • K. Because F (x) = p∈Q ξ p x p = N • p∈Q x p (
recall that all paths p ∈ P have, by construction, the unit cost ξ p equal to N ), we have

p∈Q x p = K. Putting x ′ p = xp K , p ∈ Q, we obtain a feasible solution of F D G with G(x ′ ) = max s∈S {1 -p∈Q s x ′ p } = 1 -min s∈S { p∈Q s xp K } = 1 -1 K min s∈S { p∈Q s x p } = 1 -1 K .
The last equality follows from the fact that min s∈S { p∈Q s x p } = 1, because in any optimal solution of P DD G one of the constraints (3.3b) must be active. Thus, 1 -1 K is an upper bound for the minimum cost of F D G .

Conversely, suppose that Q,

x ′ = (x ′ p : p ∈ Q) is an optimal solution of F D G with G(x ′ ) < 1 -1 K . Then p∈Q s x ′ p > 1
K , for all s ∈ S, and hence p∈Q s x p > 1, s ∈ S, where

x p = K • x ′ p , p ∈ Q.
This means that x is a feasible solution of P DD G with F (x) = N • K, where K = χ f (G). Thus, due to Lemma 3.2.2, the solution x is optimal. This, however, is a contradiction because, again, a solution for which all constraints (3.3b) are not active cannot be optimal. Thus, 1 -1 K is also the lower bound for F D G , so 1 -1 K is in fact the optimal objective value for this problem.

As PD, FD-nSR is N P-hard already in the single-demand version. (5.3a) Thus, the pricing problem Price-FD-nSR for FD-nSR is essentially the same as the pricing problem for PD, and therefore is polynomial for single link failures (as observed by several authors [START_REF] Orlowski | Local and global restoration of node and link failures in telecommunication networks[END_REF][START_REF] Wessäly | Dimensioning Survivable Capacitated NETworks[END_REF]), and N P-hard for multiple failures.

Path generation

Path generation (and the pricing problem

FD-SR: Stub-Release

The final case assumes failure dependent (FD) flow restoration using stub-release (SR). The corresponding non-bifurcated problem FD-SR is as follows.

Problem FD-SR minimize F (y) = a∈A ξ a y a , (5.4a)

r∈W d x dr = 1, d ∈ D, (5.4b) d∈D h d ( r∈W ′ ad ∧s∈Sp
x dr + r∈W ′′ ads ∧s∈ Sp

x dr ) y a , a ∈ A, s ∈ S a (5.4c)

x dr ∈ {0, 1}, d ∈ D, r ∈ W d , (5.4d) y a 0, a ∈ A. (5.4e)
For the case of multiple failures and many demands, N P-hardness of FD-SR can be proved using the construction presented in Section 5.1 for FD-nSR . The reason is that in both constructions all possible paths consist of only one link, and in effect stub-release cannot be used, as the only link that can be released in a particular situation fails.

The one demand and single failure case is polynomial, still a little bit more complicated.

It can be proved by showing that any feasible solution to this case of FD-SR can be transformed to a solution of FI-SR of the same or lower cost. Follow the considerations for PD, and employ a modified version of the algorithm presented in Section 3.2 showing equivalence of PD and HS for the non-bifurcated single-link failure case. Having a solution to FD-SR add parallel links to those that do not fail, and are present in the solution. Then, reduce the capacity of the used links to h d , and exclude from the resulting network the links that do not belong to any of the 2h d -cuts (one by one). Finally, erase those added links that have not been erased in the previous phase, and whose counterparts are also still in the network.

The resulting network cannot be more expensive than the original solution to FD-SR. Moreover, it is equivalent to a solution to FI-SR. Observe that the optimal solution to FI-SR can be found in polynomial time. The bifurcated relaxation (with continuous flow variables) of FD-SR is most likely N P-hard. Still, the conjecture has not been proved so far.

Path generation

For is demonstrated in [START_REF] Maurras | Network synthesis under survivability constraints[END_REF] (by reduction from the Hamiltonian path problem [START_REF] Garey | Computers and Intractability : A Guide to the Theory of NP-Completeness[END_REF]) and in [START_REF] Orlowski | Local and global restoration of node and link failures in telecommunication networks[END_REF] (by reduction from the max-cut problem [START_REF] Garey | Computers and Intractability : A Guide to the Theory of NP-Completeness[END_REF]) that Price-FD-SR is N P-hard already for single-link failures (see also [START_REF] Orlowski | On the complexity of column generation in survivable network design[END_REF]).

Chapter 6 Conclusions

In the first part of the thesis the problem of designing survivable transport networks was considered. Two methods (mechanisms) of providing survivability of transport connections against either single or multiple failures of links were examined: protecting connections with dedicated standby connections, i.e., path protection, and restoring failed connections using protection capacity of links, i.e., path restoration. A number of constraints that might arise in practice was considered: first, that all connections between any pair of nodes must use the same network path, i.e., non-bifurcated routing; next, that each connection must be restored along the same path independently of which failure occurs, i.e., failure-independent restoration; and finally, that the capacity of links occupied by failed connections can be used for restoration, i.e., stub-release-based restoration.

For each combination of the design constraints and the resilience methods the resulting network design problem was analyzed. It was shown how to formulate each of those optimization problems as either a linear or a mixed-integer programming multi-commodity flow problem; the mixed-integer formulations arise in the situations when the non-bifurcated routing of demands is required. In most of the cases the resulting formulation is a non-compact link-path formulation; a compact, node-link formulation is used only in two cases of the bifurcated routing: in the design of path protection with diverse paths and in the design of failure-dependent path restoration routing without stub-release-based restoration.

Analyzing the complexity of the problems, it is justified to conclude (see Table 6.1) that the majority of problems appear to be N P-hard; only for single failures when only one demand is considered all problems are polynomial. For multiple failures actually all the problems are N P-hard. For single failures the only problems that are not N P-hard are the design of path protection in the case of the non-bifurcated routing and the design of failuredependent path restoration without stub-release in the case of the bifurcated routing. The former problem can be solved with shortest path algorithms, while the latter, being one of few problems featuring a compact linear programming formulation, by linear programming methods. have to be generated using column generation. This, as already known, is in general N Phard as it involves N P-hard pricing problems. Nevertheless, according to the experience, the use of non-compact LP formulations together with column generation is the only practically effective general method that yields (in vast majority of cases) optimal solutions to the considered N P-hard resilient network design problems. This issue is discussed below using the results of [START_REF] Pióro | Path generation issues for survivable network design[END_REF].

In fact, all the N P-hard pricing problems described in the previous chapters of the thesis can be formulated as mixed-integer programming (MIP) problems (such formulations are discussed in [START_REF] Orlowski | On the complexity of column generation in survivable network design[END_REF], see also [START_REF] Pióro | Path generation issues for survivable network design[END_REF][START_REF] Stidsen | Optimal routing with single backup path protection[END_REF]) and solved by a MIP solver in the column generation process. It turns out, however, that this approach is in general not efficient because of excessive time spent in a MIP solver.

Alternatively, the pricing problems (which are in fact complicated shortest path problems with tricky constraints and multiple link metrics) can be solved using methods for Shortest Path Problem with Resource Constraints (SPPRC) [START_REF] Irnich | Shortest path problems with resource constraints[END_REF]. A general SPPRC algorithm was used for FI-nSR in [START_REF] Stidsen | Optimal routing with single backup path protection[END_REF]. Still, as discussed in [START_REF] Pióro | Path generation issues for survivable network design[END_REF], it turns out that using general label-setting SPPRC algorithms for the considered pricing problems is not effective either. Fortunately, such label-setting algorithms can be properly adjusted. The way how to do it for FI-nSR and FD-SR is described in [START_REF] Pióro | Path generation issues for survivable network design[END_REF], where numerical examples illustrating the above observations are also given.

Chapter 7 Notation and problem formulations

Consider a directed graph G = (V, A), where V is a set of nodes and A is a set of arcs. The graph represents a backbone, and the arcs depict the unidirectional transmission links. For each arc a ∈ A an installed capacity c a ∈ IR + and a routing cost ξ a ∈ IR + for one unit of traffic are given.

Let t = (t ij ) i,j∈V be a vector of IR |V|(|V|-1) that specifies values of traffic demands (or capacity requirements) between pairs of nodes of V. This vector will be called a traffic matrix. Note that the size of t can be smaller when it is assumed that t ij = 0, for given i, j ∈ V, and for all t ∈ D. To clarify the notation a demand between nodes i and j is called "demand ij", and its value is denoted by t ij . The traffic matrix is supposed to be variable, and can be any point of a traffic demand polytope D. D is generally defined by some linear constraints involving the variables t ij , for i, j ∈ V. However, it can be also defined by a set of traffic matrices (in this case D is a convex hull of those matrices) or by an oracle.

To express routing problems as mathematical programs the following notation is introduced.

P(i, j) : finite set of acyclic paths of G from i to j (i, j ∈ V).

x ij p : proportion of a traffic demand from i to j (i, j ∈ V) carried through a path p ∈ P(i, j). Note that 0 x ij p 1. For a current traffic matrix t ∈ D, the traffic carried through p is then given by t ij • x ij p . To fulfill the stability property, the variable x ij p does not directly depend on the current traffic matrix.

x ij a : proportion of traffic from i to j flowing through an arc a ∈ A.

f a : maximum amount of traffic carried on an arc a ∈ A. It depends on the polytope D and the routing pattern. The variable f a can also be considered as the minimum capacity that has to be reserved on an arc a to satisfy all the constraints. A vector f is called a reservation vector.

F (D) : routing cost.

Basic problems

In this section basic routing problems are presented. They will be later enhanced by introducing the partitioning of a traffic demand polytope.

Robust routing

The problem of computing the minimum cost robust stable routing of an uncertainty domain D, denoted by Robust Routing (RR), can be formulated as in (7.1).

Problem RR minimize F RR (D) = a∈A ξ a f a , (7.1a) p∈P(i,j) x ij p 1, ∀i, j ∈ V, (7.1b) p∈P(i,j),p∋a x ij p x ij a , ∀i, j ∈ V, ∀a ∈ A, (7.1c) i,j∈V x ij a t ij f a , ∀a ∈ A, ∀t ∈ D, (7.1d) f a c a , ∀a ∈ A, (7.1e) x ij p 0, ∀p ∈ P(i, j), ∀i, j ∈ V. (7.1f)
The objective is to minimize the total routing cost. Inequalities (7.1b) express the fact that traffic demands between every pair of nodes may be split among many paths. Every variable x ij a is defined by (7.1c). For a given traffic matrix t, a traffic on an arc a is given by the left-hand side of (7.1d). Thus, the capacity f a that should be reserved on an arc a must be higher than the traffic carried in all the situations. In other words, inequalities (7.1d) must be valid for each traffic matrix t in the polytope D. Inequality (7.1e) indicates that f a is lower than the capacity of an arc a. Non-negativeness of x ij p is forced by (7.1f). This leads to non-negativeness of x ij a , due to (7.1c), and consequently non-negativeness of f a , due to (7.1d). Note that the variables x ij a can be eliminated from the formulation. However, according to initial experiments eliminating them from the implementation does not improve running times of algorithms presented in the following sections. Therefore, they are kept for the sake of clarity and simplicity.

Presented in this way, Robust Routing seems to be difficult. First, the number of paths P(i, j) can be very high. Second, inequalities (7.1d) are non-linear. Finally, they have to be satisfied for each traffic matrix in D, and D is generally an infinite set.

Fortunately, the problem was proved to be easily solvable using an algorithm based on constraint generation (see [START_REF] Ben-Ameur | New economical virtual private networks[END_REF][START_REF] Ben-Ameur | Routing of uncertain traffic demands[END_REF]). Considering the current solution of the relaxation of Robust Routing (only a finite set of traffic matrices is taken into account instead of the full D), we only have to check wether there is an arc a and a traffic matrix t ∈ D such that (7.1d) is violated for them. This can be easily done by the following linear program:

max t∈D i∈V j∈V\{i} x ij a t ij .
If the maximum is larger than f a the violated inequality is added.

Routing paths can also be generated in an iterative way by solving a shortest path problem for each pair (i, j), where i, j ∈ V, and link weights are given by the values of appropriate dual variables of (7.1c). If there exists a path whose reduced cost is negative it has to be added to an appropriate P(i, j).

Another way of solving Robust Routing, based on duality, was proposed in [START_REF] Altın | Provisioning virtual private networks under traffic uncertainty[END_REF]. The dual of the maximization problem above should be written, and the optimum must be always lower than f a . A similar approach was also used in a previous work [START_REF] Ben-Tal | Robust solutions of uncertain linear programs[END_REF]. Instead of generating constraints, a compact formulation follows from duality, but the number of variables of the problem increases significantly. Moreover, the approach assumes that a traffic demand polytope is given by a set of inequalities, while the approach presented in [START_REF] Ben-Ameur | New economical virtual private networks[END_REF][START_REF] Ben-Ameur | Routing of uncertain traffic demands[END_REF] is more general, and can also deal with polytopes described by their extreme points or by an oracle.

Note that it is possible to use other cost functions for this problem. For instance it is possible to minimize the congestion. In such a situation the cost function has to be replaced by F RR (D) = z, where z is a variable denoting the congestion. Moreover, constraint (7.1e) has to be replaced with f a z • c a . Although the presented algorithms were tested using both cost functions (routing cost and congestion, see Chapter 10) the rest of the models will be presented only for the former one (routing cost).

Notice that the problem difficulty does not change, if either traffic demands or network links are not oriented. It is easy to solve Robust Routing using similar techniques even if either demands or links are undirected.

No sharing routing

Another set of problems emerges when harsher rules on reservation of capacities are imposed, and different demands are forbidden from sharing resources. The core problem of this set is denoted as No Sharing (NS), and is formulated as follows.

Problem NS minimize F N S (D) = a∈A ξ a f a , (7.2a) p∈P(i,j) x ij p 1, ∀i, j ∈ V, (7.2b) p∈P(i,j),p∋a x ij p x ij a , ∀i, j ∈ V, ∀a ∈ A, (7.2c) x ij a t ij f ij a , ∀i, j ∈ V, ∀a ∈ A, ∀t ∈ D, (7.2d) i,j∈V f ij a f a , ∀a ∈ A, (7.2e) f a c a , ∀a ∈ A, (7.2f) x ij p 0, ∀p ∈ P(i, j), ∀i, j ∈ V. (7.2g)
In the formulation variables f ij a denote an amount of capacity reserved on an arc a by traffic generated between nodes i and j. In fact, they [like x ij a -here and in (7.1)] are obsolete and can be eliminated from the formulation. However, they are kept for the sake of clarity and simplicity. Formulation (7.2) is obtained from (7.1) by substituting (7.2d) and (7.2e) for (7.1d).

Constraint (7.2d) results in f ij a = max t∈D x ij a t ij . However, max t∈D x ij a t ij = x ij a max t∈D t ij . Denoting max t∈D t ij as t max ij , we can write that f ij a = x ij a t max ij .
Therefore, the basic No Sharing is equivalent to reserving t max ij of flow for each relation (i, j), i, j ∈ V. Therefore, it is easily solvable by means of an appropriate linear program facilitated by a path generation mechanism. However, it gets more complicated when D is allowed to be partitioned (see Section 7.3).

Dynamic routing

The problem consists in providing routing schemes (possibly different) for all traffic matrices from a traffic demand polytope. In order to formulate the following variables are introduced.

x ij,t p : proportion of a traffic demand from i to j (i, j ∈ V) for a traffic matrix t carried through a path p ∈ P(i, j).

x ij,t a : proportion of traffic from i to j for a traffic matrix t on an arc a ∈ A.

The core problem of this set is denoted as Dynamic Routing (DR), and can be formulated as follows.

Problem DR minimize F DR (D) = a∈A ξ a f a , (7.3a) p∈P(i,j) x ij,t p 1, ∀i, j ∈ V, ∀t ∈ D, (7.3b) p∈P(i,j),p∋a x ij,t p x ij,t a , ∀i, j ∈ V, ∀a ∈ A, ∀t ∈ D, (7.3c) i,j∈V x ij,t a t ij f a , ∀a ∈ A, ∀t ∈ D, (7.3d) f a c a , ∀a ∈ A, (7.3e) x ij,t p 0, ∀p ∈ P(i, j), ∀i, j ∈ V, ∀t ∈ D. (7.3f) Formulation (7.
3) is similar to (7.1). However, it replaces each constraint of (7.1) involving variables x ij p or x ij a with an infinite (in general) number of constraints involving variables x ij,t p and x ij,t a . Although all the traffic matrices t ∈ D are present in the formulation it is enough to consider only extreme points of D in order to solve the problem. Having the optimal routings for all the extreme points it is possible to compute optimal routings for all t ∈ D by calculating appropriate convex combinations of the optimal routings for the extreme points.

The obvious fact is that the problem is solvable in polynomial time if D is defined as a convex hull of a given finite set of traffic matrices. But this is not the only special case when the problem is simple. Proposition 7.1.1. Dynamic Routing can be solved in polynomial time when D is defined by its facets, and the number of demands is less than a known constant K.

Proof. In such a case the number of extreme points of D is limited by O(n K ), where n is the number of facets, because each extreme point can be explicitly defined by a set of K facets. Note that K is here also the dimension of the traffic demand polytope D. The number of possible different sets of K facets is n K , which is obviously smaller than n K . Therefore, it is possible to express the problem as a linear program with a polynomially limited number of variables and constraints.

The problem is co-N P-hard when the number of demands is unlimited [START_REF] Chekuri | Hardness of robust network design[END_REF]. The complexity of the case when the number of demands is limited by K, and the traffic demand polytope is defined by an oracle is still an open question.

Test cases

In this section two different ways of describing a traffic demand polytope in practice are presented. Both of them were used to evaluate the novel routing strategies described in the thesis.

Hose model

In [START_REF] Fingerhut | Designing least-cost nonblocking broadband networks[END_REF] a hose model was presented. It assumes that the outgoing traffic of each node is limited, i.e., j∈V t ij A i , for each i ∈ V, where A i is an upper bound for outgoing traffic from a node i. Moreover, limitations on the incoming traffic can also be considered. In such a case, i∈V t ij B j , for each j ∈ V, where B j is an upper bound for incoming traffic to a node j. The traffic matrix then can be any matrix satisfying this kind of constraints. A polytope satisfying those constraints is called a hose model polytope, and is formally described as follows.

Hose model polytope

j∈V t ij A i , ∀i ∈ V, (7.4a) i∈V t ij B j , ∀j ∈ V, (7.4b) t ij 0, ∀i, j ∈ V. (7.4c)
In addition it is possible to assume that both the maximum and minimum traffic between each pair of nodes are also constrained, i.e., t min ij t ij t max ij . the obtained polytope is called a general hose model polytope, and is formally described as follows.

General hose model polytope

j∈V t ij A i , ∀i ∈ V, ∀t ∈ D, (7.5a) i∈V t ij B j , ∀j ∈ V, ∀t ∈ D, (7.5b) t ij t min ij , ∀i, j ∈ V, ∀t ∈ D, (7.5c) t ij t max ij , ∀i, j ∈ V, ∀t ∈ D. (7.5d)
Note that not all nodes in a network have to generate traffic. Assume that some nodes are transit nodes, and are neither source nor sink nodes of any demand. They are called then non-active nodes, while the rest are called active nodes.

B-S model

In [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF] Bertsimas and Sim presented a traffic demand model in which each demand can assume only either its minimum value t min ij or its maximum value t max ij , and the number of demands that assume their maximum values cannot be greater than k. The model can be modified in a way that all possible traffic demand matrices considered in the original model are treated as extreme points of D in a new model. A polytope satisfying those constraints is called B-S model polytope in this thesis, and is formally described as follows.

B-S model polytope

i,j∈V t ij -t min ij t max ij -t min ij k,
∀t ∈ D, (7.6a)

t ij t min ij , ∀i, j ∈ V, ∀t ∈ D, (7.6b) t ij t max ij , ∀i, j ∈ V, ∀t ∈ D. (7.6c)
Notice that, like in a hose model case, the number of extreme points of this traffic demand polytope is exponential. Moreover, also in this case we can talk about active and non-active nodes. For the sake of simplicity assume that if a node is active, then it generates traffic to all other active nodes.

Partitioning strategies

Assume that a traffic demand polytope D and a normal vector α that defines a direction of Depending on restrictions imposed on the reservation vectors two different strategies can be considered. The reservation vectors on opposite sides of the hyperplane can either be required to be identical, or allowed to differ. The former case models a situation when a user is an owner of a network, and his or her task is to minimize the usage of resources. The latter corresponds to a situation when a user rents capacities from other operators, and he or she cannot renegotiate those renting agreements after each change in the routing.

The reservation vectors can be different

The problem is denoted by Different Reservation, and for Robust Routing (DR/RR) is formulated as follows.

Problem DR/RR

F * DR/RR (D) = min β F DR/RR (D, β),
where the cost function is defined as:

F DR/RR (D, β) = max{F RR (L(D, β)), F RR (R(D, β))}.
The task is to find such a value of β which ensures that the maximum of costs of Robust Routing for LHSP and for RHSP is minimal. Unfortunately, as it is shown in the example below, the function F DR/RR (D, β) as a function of β is not continuous.

Example Consider a network depicted in Figure 7.1 with c (s,b) = 9, c (s,e) = 4 and ξ (s,c) = 1 (an arc from node i to node j is denoted by (i, j)). Other capacities are infinite, and other routing costs are set to zero. The traffic demand polytope D is a convex hull of five traffic matrices: (3, 0, 3) t , (0, 3, 3) t , (0, 9, 1) t , (3, 6, 1) t and (3, 9, 0) t , where (x, y, z) t denotes a traffic matrix characterized as follows: t sa = x, t sb = y and t sc = z. The hyperplane is characterized as t sa + t sb = β.

In the considered network the value of the optimal solution is 0, and is obtained for

β = 9.
If such a hyperplane is used then for LHSP both demands sa and sb can be routed through (s, b), and the demand sc can utilize a path {(s, e), (e, c)}. For RHSP the route for the demand sa changes to a path {(s, e), (e, a)}, but still the demand sc can utilize the same path {(s, e), (e, c)} as for LHSP, because t sa + t sc for RHSP is smaller or equal to c (s,e) . The cost of the solution is 0, because the expensive arc (s, c) is used neither for LHSP nor for RHSP.

However, when β = 9 + γ (γ > 0) the optimal solution is 2 regardless of the actual value of γ. Even a small γ prevents the demand sa from using the path {(s, b), (b, a)} for LHSP, and forces it to use an arc (s, e) (note that a matrix (γ, 9, 1γ/3) t belongs to LHSP, so the whole demand sa has to use an arc (s, e)). As a sum t sa + t sc can be as big as 6 in LHSP, the demand sc cannot only utilize the inexpensive path {(s, e), (e, c)}, and has to also utilize the direct expensive path (s, c).

Another issue is that obtained results (routings and the hyperplane) have to be implemented in actual network equipment, and these devices can only work with finite precision numbers. Taking this into account, and recalling that F DR/RR (D, β) is non-continuous it was decided that β can only assume values of a finite precision, i.e., only values of form n • γ are considered, where n ∈ Z and γ is the precision.

When the finite precision of β is assumed, Different Reservation for Robust Routing can be optimally solved using a polynomial algorithm presented in [START_REF] Ben-Ameur | Between fully dynamic routing and robust stable routing[END_REF]. Knowing that In order to formulate Different Reservation for No Sharing, F N S have to be substituted for F RR . Note that this variant can be solved using the same algorithm, because

F RR (L(D, β)) is a
F N S (L(D, β)) [like F RR (L(D, β))
] is also a non-decreasing function of β, and

F N S (R(D, β)) is a non-increasing function of β.
The problem can be also formulated, and solved, in a similar way for Dynamic Routing.

It is co-N P-hard in general but remains in P for some special cases, e.g., when D is defined as a convex hull of a given set of traffic matrices. Dynamic routing partitioning is discussed in details in Section 8.3.

Although F DR/RR (D, β) is non-continuous in general, there exist special cases when it is continuous, e.g., when capacities are infinite, and a constraints (7.1e) is eliminated from the appropriate formulation. Before proving that, a new notation and some lemmas have to be introduced.

The Hausdorff distance between two polytopes D 1 and D 2 is defined as follows.

d(D 1 , D 2 ) = max( sup t 1 ∈D 1 inf t 2 ∈D 2 ||t 1 -t 2 ||, sup t 1 ∈D 2 inf t 2 ∈D 1 ||t 1 -t 2 ||)
where the norm

||t 1 -t 2 || = i,j∈V |t 1 ij -t 2 ij |.
Note that, since D 1 and D 2 are compact, the distance can be also presented in the following way:

d(D 1 , D 2 ) = max(max t 1 ∈D 1 min t 2 ∈D 2 ||t 1 -t 2 ||, max t 1 ∈D 2 min t 2 ∈D 1 ||t 1 -t 2 ||).
In addition define the polytope D β = D ∩ {t 0 : α • t = β}. Remember also that β min < β < β max . Proof. Assume that β 1 < β 2 (an analogous proof can be given for β 1 > β 2 ), so L(D, β 1 ) ⊆ L(D, β 2 ) and:

d(L(D, β 1 ), L(D, β 2 )) = max t 2 ∈L(D,β 2 ) min t 1 ∈L(D,β 1 ) ||t 1 -t 2 ||.
For given D, β 1 , and t 2 ∈ L(D, β 2 ) define t(t 2 , β 1 ) ∈ L(D, β 1 ), such that ||t(t 2 , β 1 )t 2 || is minimized. Note that D is compact, and thus, according to Weierstrass' theorem, t(t 2 , β 1 ) exists.

Assume now that the lemma is false. It means that there exists t 2 ∈ L(D, β 2 ) and ε > 0 such that for each β 1 ∈]β min , β 2 ] the norm ||t(t 2 , β 1 )t 2 || ε. Moreover, as D is compact and the norm is continuous, there exists β ⋆ ∈]β min , β 2 ], such that ||t(t 2 , β ⋆ )t 2 || = ε. Take a segment joining t(t 2 , β ⋆ ) and t 2 . The segment belongs to D, because D is convex. Now take t 1 in the middle of the segment, and set

β 1 to β ⋆ +β 2 2 . Obviously ||t 1 -t 2 || = ε 2 . Moreover, t 1 belongs to L(D, β 1 ), thus ||t(t 2 , β 1 ) -t 2 || ε 2 .
Therefore, the contradiction is reached, as ε was not the value of the minimum norm.

Lemma 7.3.2. When capacities are infinite

F RR (L(D, β)) is continuous in variable β.
Proof. From the formal point of view the proposition states that if capacities are infinite then:

lim β ′ →β F RR (L(D, β ′ )) = F RR (L(D, β)). (7.7a)
Assume that a solution to Robust Routing for L(D, β) is given, and values of f a correspond to this solution. If we assume that β ′ β then the considered traffic demand polytope, i.e., L(D, β), is extended to L(D, β ′ ). In such a situation some of f a may have to be increased in order to route new traffic matrices. As capacities are unlimited, it is possible to route those new matrices using the routing corresponding to L(D, β). It is obvious that any routing (consisting of loopless paths) cannot cost more than a∈A ξ a for each unit of routed flow. Therefore, it is possible to write that:

F RR (L(D, β)) F RR (L(D, β ′ )) F RR (L(D, β)) + a∈A ξ a • d(L(D, β ′ ), L(D, β)).
Knowing from Lemma 7.3.1 that lim β ′ →β d(L(D, β ′ ), L(D, β)) = 0 it is justified to conclude that (7.7) is true.

Obviously the same fact can be proved for F RR (R(D, β)). Now it is possible to prove the following proposition.

Proposition 7.3.3. When capacities are infinite

F DR/RR (D, β) is continuous in variable β.
Proof. F DR/RR (D, β) for β is just a maximum of two continuous functions, so it also has to be continuous.

The reservation vectors are identical

Assume that the reservation vectors corresponding to the two uncertainty subsets (LHSP and RHSP) should be the same. The problem will be called Identical Reservation (for Robust Routing or No Sharing). Note that Identical Reservation for Dynamic Routing is meaningless, because partitioning in such conditions does not have any effect.

A version that corresponds to Robust Routing (IR/RR) can be formulated as follows.

Problem IR/RR

F * IR/RR (D) = min β F IR/RR (D, β),
where the cost function is defined as follows.

minimize

F IR/RR (D, β) = a∈A ξ a f a , (7.8a)
p∈P(i,j)

x ij p 1, ∀i, j ∈ V, (7.8b)
p∈P(i,j),p∋a

x ij p x ij a , ∀i, j ∈ V, ∀a ∈ A, (7.8c) i,j∈V x ij a t ij f a , ∀a ∈ A, ∀t ∈ L(D, β), (7.8d)
p∈P(i,j)

x ij p 1, ∀i, j ∈ V, (7.8e)
p∈P(i,j),p∋a

x ij p x ij a , ∀i, j ∈ V, ∀a ∈ A, (7.8f)
i,j∈V

x ij a t ij f a , ∀a ∈ A, ∀t ∈ R(D, β), (7.8g
)

f a c a , ∀a ∈ A, ( 7.8h)
x ij p , x ij p 0, ∀p ∈ P(i, j), ∀i, j ∈ V. (7.8i) Formulation (7.8) is an extended version of (7.1). The number of variables and constraints is almost doubled in order to describe two independent routings on both sides of the hyperplane (non-overlined variables correspond to LHSP, and overlined variables correspond to RHSP).

As the reservation vectors on both sides of the hyperplane have to be identical it is possible to describe them using only one set of variables, namely f a , where a ∈ A. Inequalities (7.8d) and (7.8g) assure that both routings can be realized using the reserved capacities.

Notice that the considered problem, with β fixed, can be solved in polynomial time using the way described in [START_REF] Ben-Ameur | Routing of uncertain traffic demands[END_REF], because both constraints and paths can be easily generated in polynomial time.

While dealing with the Identical Reservation version for No Sharing (IR/NS) constraints (7.8d) and (7.8g) have to be replaced with:

x ij a t ij f ij a ∀i, j ∈ V, ∀a ∈ A, ∀t ∈ L(D, β), (7.9a) x ij a t ij f ij a ∀i, j ∈ V, ∀a ∈ A, ∀t ∈ R(D, β), ( 7.9b)
and the following two sets of constraints have to be added.

i,j∈V

f ij a f a ∀a ∈ A, (7.10a) i,j∈V f ij a f a ∀a ∈ A. (7.10b)
Moreover, the cost function has to be replaced with F IR/N S (D, β) = a∈A ξ a f a . Notice that when considering Identical Reservation for No Sharing, if β is fixed, the resulting optimization problem is identical to Dynamic Routing with demand set given as the convex hull of two demand matrices.

F IR/RR (D, β), like F DR/RR (D, β), is non-continuous in β (in order to prove this it is possible to use the same example as in Section 7.3.1). Therefore, also in this case it was decided that β can only assume values of finite precision, i.e., only values of form n • γ are considered, where n ∈ Z and γ is the precision.

The algorithm is polynomial as it requires to solve Different Reservation (this problem is polynomial, see Section 7.3.1) and perform some simple (of polynomial complexity) operations while building the reservation vector.

Algorithm

Consider a simpler problem that consists in answering the question: does there exist a feasible solution to Identical Reservation of cost smaller than or equal to a given value? This simplified problem will be refereed to as Identical Reservation Limit. Obviously, knowing the way of solving Identical Reservation Limit it is possible to solve Identical Reservation relatively fast using a binary search. The question arises how to solve Identical Reservation Limit. In this section an algorithm that can do this for both Robust Routing and No Sharing is presented.

Although its complexity is not polynomial, it performs well, and can solve even medium size problems (see the numerical results in Chapter 10). The key ideas of the approach can be seen in Algorithm 8.1.

Algorithm 8.1 Identical Reservation Limit(F lim )

β 2 = β max while β 2 > β min do β 1 = findMax(β 2 , F lim ) if β 1 = β 2 then return YES else β 2 = β 1 end if end while return NO
The algorithm returns YES, if a solution to Identical Reservation that costs no more than F lim exists. Otherwise, it returns NO. It uses constants β min and β max that define an interval of possible values of β, and the function findMax. The basic idea of the method is to constantly shrink the interval of possible positions of the hyperplane. At the beginning the hyperplane can be anywhere in [β min , β max ]. It means that it is impossible to judge if any t ∈ D has to belong either to LHSP or to RHSP (assume that the interval is sufficiently large, and

D ⊆ {t : α • t β min } ∩ {t : α • t β max }).
Then, in the loop, the interval of possible positions of the hyperplane is limited. More precisely, the set of matrices that have to belong to RHSP is extended.

Having RHSP defined for a particular loop it is possible, using findMax method, to calculate the maximum size of LHSP which satisfies the cost limit. If the whole polytope D can be divided between LHSP and RHSP the problem has been solved. If some matrices cannot be added to LHSP for a given RHSP, it means that they have to belong to RHSP.

They are added to RHSP by changing the value of β 2 , and the loop is repeated.

Consider now a new problem that will facilitate explanation of findMax method. Assume that values β 1 and β 2 are given. The problem, denoted by Two Known Planes, consists in finding the optimal routing when LHSP is defined as L(D, β 1 ) and RHSP is defined as R(D, β 2 ). Note that β 1 and β 2 are constant so the problem can be easily solved using techniques presented in [START_REF] Ben-Ameur | New economical virtual private networks[END_REF][START_REF] Ben-Ameur | Routing of uncertain traffic demands[END_REF], and briefly described in Chapter 7.

The method findMax returns the maximum value of β 1 that lets Two Known Planes be solved for a given β 2 and within a given cost limit F lim . If such a value does not exist it returns -∞. Note that β 1 is a variable subject to optimization and β 2 is constant. In such a situation the objective function of Two Known Planes is non-decreasing in β 1 , as it is impossible to decrease a cost of a solution by adding new traffic matrices to the problem. Therefore, the method can use (and it does) a binary search. A pseudo-code for findMax can be seen in Algorithm 8.2. Algorithm 8.2 findMax(β 2 , F lim )

β 1 = β min β ′ 1 = β 2 while β ′ 1 -β 1 > γ do β mid = β 1 +β ′ 1 2 if Two Known Planes(β mid , β 2 ) F lim then β 1 = β mid else β ′ 1 = β mid end if end while return β ′ 1
Unfortunately, the overall complexity of the whole algorithm is not polynomial. The reason is that the value β 1 found by findMax method can be very close to β 2 . In fact a difference between β 2 and β 1 can be as small as γ. It means that in the worst case the main loop of the algorithm has to be repeated m = ⌈ βmax-β min γ ⌉ times. Apparently, the value of m cannot be expressed as a polynomial function of the size of data. In Figure 8.1 an example network that suffers from this drawback is depicted.

Example Assume that a polytope D is a convex hull of only two traffic matrices. Both matrices consist of four demands. The first is as follows: t ab = 0.1, t cd = 0.9, t ef = 900, t gh = 100, while the second is: t ab = 0.9, t cd = 0.1, t ef = 100, t gh = 900.

Capacities of all arcs but two are unlimited. Only arcs (e, f ) and (g, h) have their capacities (c (e,f ) and c (g,h) , respectively) set to 900. For the majority of arcs, routing costs are set to 0, and only ξ (a,b) = ξ (c,d) = 1. Finally, it is assumed that the hyperplane is defined as

t ab = β.
The optimal solution to this instance of Robust Routing is 1.8, because demands ab and cd have to use expensive (direct) paths. They cannot utilize cheap ({(a, e), (e, f ), (f, b)} and {(c, g), (g, h), (h, d)}) routes, because arcs (e, f ) and (g, h) are fully occupied by demands ef and gh. On the other hand, the optimal solution to Identical Reservation is only 1.0, as D can be divided using the hyperplane t ab = 0.5, and different routings on both sides of it can be used. In such a situation the demand ab has to occupy the arc (a, b) only when t ab 0.5, and the demand cd has to occupy the arc (c, d) only when t cd 0.5. Note that, this instance of the problem has the infinite number of different optimal solutions that can be obtained for all β ∈ [ 100 999 , 899 999 ]. Assume that the presented algorithm is used, existence of a solution of cost 1.0 has been verified, and now a feasible solution of cost 1.0ǫ is of interest. Unluckily, in the considered network a solution to Two Known Planes, when 100 999

β 1 β 2 899 999 , is 1.0-(β 2 -β 1 )
. It means that in order to use the algorithm to verify if a feasible solution of cost 1.0ǫ exists, Two Known Planes has to be solved almost ǫ -1 times, because for β 2 ∈ [ 100 999 + ǫ, 899 999 ] the value of β 1 , resulting from Two Known Planes, will be equal to β 2ǫ. Note that in the worst case ǫ = γ, where γ is the precision for β defined in Section 7.

t max ij λt max ij ′ + (1 -λ)t max ij ′′ , where λ = β 2 -β β 2 -β 1 , t max ij ′ = t max ij (L(D, β 1 )) and t max ij ′′ = t max ij (L(D, β 2 )). Moreover, maximum values of t max ij = t max ij (R(D, β)
) satisfies an inequality:

t max ij λt max ij ′ + (1 -λ)t max ij ′′ , where λ = β 2 -β β 2 -β 1 , t max ij ′ = t max ij (R(D, β 1 )) and t max ij ′′ = t max ij (R(D, β 2 )).
Assume now that the optimal solutions of Identical Reservation (for No Sharing)

for given β 1 and β 2 are provided, and a solution for

β ∈]β 1 , β 2 [ is of interest. Variables of
the solution for β will be denoted as described in Chapter 7. Variables of the solution for β 1 will be additionally followed by a prime, e.g., f ′ a or x ij p ′ , while those corresponding to the solution for β 2 will be followed by a double prime, e.g., f ′′ a . Construct now a routing to the solution for β in the following way.

x ij p = (λx ij p ′ t max ij ′ + (1 -λ)x ij p ′′ t max ij ′′ )/t max ij , (8.1a)
x ij p = (λx ij p ′ t max ij ′ + (1 -λ)x ij p ′′ t max ij ′′ )/t max ij . ( 8.1b)
Lemma 8.2.6. The routing constructed using (8.1) is feasible, i.e., it satisfies (7.8b) and (7.8e).

Proof. Focus on the first equality. Use the first inequality from Corollary 8.2.5, substitute u for λt max ij ′ , and substitute v for (1λ)t max ij ′′ . Summing the obtained inequalities for all p ∈ P(i, j) the following formula is obtained.

p∈P(i,j) x ij p u u + v p∈P(i,j) x ij p ′ + v u + v p∈P(i,j) x ij p ′′ .
Variables x ij p ′ and x ij p ′′ satisfy (7.8b), so x ij p also has to satisfy it. Similar proof can be used to show that x ij p satisfy (7.8e).

Knowing that the routing expressed by (8.1) is feasible, and using (7.9) and (7.8c) in order to substitute f ij a for p∋a x ij p t ij the following corollary is obtained.

Corollary 8.2.7. If a routing of a solution for β satisfies (8.1) then

f ij a λf ij a ′ + (1 -λ)f ij a ′′ and f ij a λf ij a ′ + (1 -λ)f ij a ′′
, for all a ∈ A and i, j ∈ V.

Note that, according to (7.8), the cost function F IR (D, β) depends only on f a . What is more, according to (7.10), f a depends on f ij a only. Therefore, from Corollary 8.2.7 the following can be deduced.

Corollary 8.2.8. Function F IR/N S (D, β) is convex in [β 1 , β 2 ], if D mid = R(D, β 1 )∩L(D, β 2 )
does not contain extreme points of D.

Returning to the algorithm, it is simple to calculate a list of increasing values of β that describes all hyperplanes which contain extreme points of D (note that the polytope is a convex hull of a given set of traffic matrices). Define the list as B = {β 1 , β 2 , . . . , β n } such that β i < β i+1 , for i = 1, 2, . . . , n -1, and each extreme point of D belongs to n i=1 D β i . Knowing from Corollary 8.2.8 that function

F IR/N S (D, β) is convex in [β i , β i+1 ], for i = 1, 2, . . . , n -1,
it is possible to calculate optimal F ⋆IR/N S [β i ,β i+1 ] (D), for i = 1, 2, . . . , n -1, using any known algorithm that can find the minimum of a convex function in polynomial time (e.g., golden ratio or Fibonacci search). Obviously, optimal

F ⋆IR/N S [β min ,βmax] (D) = min i=1,2,...,n-1 F ⋆IR/N S [β i ,β i+1 ] (D).
Therefore, the following proposition can be written. Proposition 8.2.9. Identical Reservation for No Sharing can be solved in polynomial time if the traffic demand polytope is given by a set of its extreme points.

Partitioning and dynamic routing

In this section Different Reservation for Dynamic Routing is considered. The problem can be solved by means of the method of Section 7.3.1. It is co-N P-hard in general but belongs to P when D is defined as a convex hull of a given set of traffic matrices.

The former fact can be concluded from the proof presented in [START_REF] Chekuri | Hardness of robust network design[END_REF] showing that Dynamic Routing alone is co-N P-hard. The latter fact will be proved in this section. But first some lemmas have to be discussed. Consider a traffic demand polytope D divided by a hyperplane α • t = β into a right hand side polytope (RHSP), defined as R(D, β), and a left hand side polytope (LHSP), defined as L(D, β). A strict combination of some points t ∈ T is defined as t∈T λ t t, where t∈T λ t = 1 and λ t > 0 for all t ∈ T . Lemma 8.3.1. If a traffic matrix t r can be expressed as a strict convex combination of more than three affinely independent points of D it can be also expressed as a strict convex combination of exactly three affinely independent points of D.

Proof. Assume that t r is a strict convex combination of K affinely independent points from D.

t r = K k=1 λ k t k .
It can be transformed into:

t r = λ 1 t 1 + λ 2 t 2 + M K k=3 λ k t k M ,
where:

M = K k=3 λ k .
This is obviously a strict convex combination of three affinely independent points belonging to D.

Obviously the same lemma can be proved for a strict convex combination of more than W affinely independent points, where W 3. However, for the purpose of this section, the proof for W = 3 is essential.

Lemma 8.3.2. If a traffic matrix t r ∈ D belonging to the hyperplane α • t r = β has to be expressed as a strict convex combination of three affinely independent points t a , t b , t c ∈ D then t r is an extreme point of neither LHSP nor RHSP.

Proof. First notice that at least one of the points has to belong to LHSP, and at least one has to belong to RHSP (points on the hyperplane belong to both LHSP and RHSP). Assume that t a is in RHSP, and both t b and t c are in LHSP. Note that if all three points belong to LHSP they also have to belong to RHSP (they have to be on the hyperplane). In such a situation t r cannot be an extreme point of LHSP, because it is a convex combination of points belonging to LHSP. The same claim holds for RHSP. Define D 1 as a convex hull of t a , t b , and t c . Then t r ∈ D 2 = D 1 ∩ {t : α • t = β}. D 2 can be also expressed as a convex hull of its two extreme points (first -an intersection of a line connecting t a to t b and the hyperplane, second -an intersection of a line connecting t a to t c and the hyperplane). t r cannot be any of these extreme points so it is an extreme point of neither RHSP nor LHSP. Now the main claims of this section can be presented. Proof. Combining Lemma 8.3.2 and Lemma 8.3.1 it is possible to conclude that any point that has to be a strict convex combination of more than two affinely independent points of D is an extreme point of either LHSP or RHSP. It means that the only way to obtain an extreme point of either RHSP or LHSP is to take either an extreme point of D or a strict convex combination of two extreme points of D. Obviously those two points cannot belong to the same half-space defined by the hyperplane. Therefore, one of them has to belong to RHSP, and the other has to belong to LHSP.

The corollary implies that the number of extreme points of both LHSP and RHSP is limited by O(n 2 ), where n is the number of extreme points of D. Therefore, the following corollary can be written. Proof. The problem can be expressed in form of a linear program with a polynomially limited number of variables and constraints.

Finally, the following proposition can be written. Proof. Knowing from Corollary 8.3.4 that Different Reservation for Dynamic Routing, for given β, can be solved in polynomial time, and that F DR (L(D, β 1 )) F DR (L(D, β 2 )), when β 1 < β 2 , it is possible to conclude that the polynomial time algorithm of Section 7.3.1 based on a binary search can be used in order to solve Different Reservation for Dynamic Routing with β as a variable if the traffic demand polytope D is defined as a convex hull of a given set of traffic matrices.

Implementation details

In this section some enhancements to the presented algorithms are presented. They are not crucial from the point of view of the theoretical complexity of the algorithms. However, they significantly reduce running times of the implementations.

Cost bounds

In Section 8.1 it was assumed that F min = 0 and F max is equal to a cost of either Robust Routing or No Sharing solution, depending on the version of the problem. Note that those bounds can be easily upgraded.

Consider the lower bound first. Obviously, F min = 0 is valid. However, a better lower bound for a cost of a Identical Reservation solution is a cost of a Different Reservation solution. The bound can be relatively easy obtained using the method of Section 7.3.1.

As far as the upper bound is concerned there are at least two different approaches that result in a bound of higher quality than the current upper bound. The straightforward one requires to solve Identical Reservation for any β ∈]β min , β max [. Although the objective function F IR (D, β), for β ∈ [β min , β max ], does not have to be concave, it reaches its maximum for both β min and β max .

The second approach takes advantage of a fact that a solution to Different Reservation provides a 2-approximation to Identical Reservation (see Section 8.1). In the implementation a method that hybridizes those two approaches has been used. First the optimal value of β ⋆ for Different Reservation was found, and then Identical Reservation was solved for this particular value of β ⋆ .

Golden ratio

In the algorithm of Section 8.2 the golden ratio search is used. This method finds the extremum of an unimodal function. The basic idea of the method is to evaluate values of Note that in the algorithm of Section 8.2 we look for all local minima of the cost function, and select the smallest one. In order to accelerate the procedure the following enhancement can be applied. If a lower bound for a local minimum in a considered interval is greater than a value of one of local minima, which has been already found, the consider interval should be abandoned, and the next interval should be considered instead.

Another enhancement is tightly connected to the previous one. The procedure can be additionally accelerated, if the true optimum is found as soon as possible. Having the true optimum, and using the previously presented enhancement it is possible to perform less steps of the golden ratio search. In other words, the order in which intervals are considered matters.

As in the numerical experiments used polytopes consisted of small number of extreme points, any sophisticated way of ordering the intervals was not applied. Therefore, it still remains an open question, how to arrange the intervals in order to accelerate the algorithm.

Column and constraint generation

The algorithms presented in Sections 8.1 and 8.2 consist of steps (subproblems) in which simpler variants of the considered problems are solved. Those subproblems can be solved independently. However, as they are usually strongly related to each other, information obtained during solving one of them should be used in order to facilitate solving another similar subproblem.

While solving the subproblems a column generation is used in order to obtain a set of promising paths. Consider two instances of Identical Reservation. They are identical as far as: network topology, demand polytope, and characteristics of arcs are concerned. The only difference between those two instances is a position of the hyperplane that divides a demand polytope into LHSP and RHSP. In such a situation it is highly probable that sets of promising paths obtained for those instances will be similar (or even identical). Therefore, in the implementation all paths obtained in the process of a column generation are collected, and used as a starting point for all successive subproblems.

Another piece of information obtained during solving the subproblems is a set of vital extreme points of the demand polytope. In this case a slightly different strategy is applied, and not all obtained extreme points are stored. The reason is that not all of them are true extreme points of D, because some of them can be created by the hyperplane, and are extreme points of both LHSP and RHSP but not D. Those extreme points are obsolete when the hyperplane changes its position, because they are either a convex combination of two extreme points of D or a convex combination of an extreme point of D and an extreme point of either the new LHSP or the new RHSP. Therefore, only extreme points that are not on the hyperplane should be stored.

Notation

In order to formulate the problem the notation presented in Chapter 7 has to be extended by the following variables.

h ij : threshold for a demand ij.

t ′ ij : volume of a demand ij corresponding to a traffic demand matrix t that has to be routed using the first routing scheme.

t ′′ ij : volume of a demand ij corresponding to a traffic demand matrix t that has to be routed using the second routing scheme.

x ij p : routing scheme used by a demand ij to route the volume exceeding h ij (second routing scheme).

x ij a : proportion of the volume exceeding h ij flowing through an arc a.

Problem formulation

The problem of computing the minimum cost volume oriented routing of an uncertainty domain D, denoted by VO Routing (VO), can be formulated as follows.

Problem VO minimize F V O (D) = a∈A ξ a f a , (9.1a) p∈P(i,j) x ij p 1, ∀i, j ∈ V, (9.1b) p∈P(i,j) x ij p 1, ∀i, j ∈ V, ( 9.1c)
p∈P(i,j),p∋a

x ij p x ij a , ∀i, j ∈ V, ∀a ∈ A, (9.1d) p∈P(i,j),p∋a x ij p x ij a , ∀i, j ∈ V, ∀a ∈ A, (9.1e) min(t ij , h ij ) = t ′ ij , ∀i, j ∈ V, ∀t ∈ D, (9.1f) max(t ij -h ij , 0) = t ′′ ij , ∀i, j ∈ V, ∀t ∈ D, (9.1g) i,j∈V (x ij a t ′ ij + x ij a t ′′ ij ) f a , ∀a ∈ A, ∀t ∈ D, (9.1h) f a c a , ∀a ∈ A, (9.1i) h ij 0, ∀i, j ∈ V, ( 9.1j)
x ij p , x ij p 0, ∀p ∈ P(i, j), ∀i, j ∈ V. (9.1k) In Problem (9.1) two different routings are considered for each demand (one used for the volume below the threshold and one used for the volume above the thresholds). Therefore, inequalities (7.1b) and (7.1c) have to be doubled into (9.1b), (9.1c) and (9.1d), (9.1e), respectively. The overall routing is expressed using (9.1f-9.1h). The equation (9.1f) defines the volume that has to be routed using the first routing scheme (variables x ij p and x ij a ), the equation (9.1g) defines the volume that has to be routed using the second routing scheme (variables x ij p and x ij a ), while (9.1h) makes those volumes be sent with appropriate routings. Note that, Problems (9.1) and (7.1) are equivalent when h ij = 0, for all i, j ∈ V.

Computational complexity

Unfortunately a decision version of the problem is co-N P-complete, so it is impossible to verify in polynomial time if a given solution is feasible. It will be proved in this section by reducing Subset Sum to the problem of verifying if a given solution is feasible. But first some lemmas will be proved.

Assume that a collection of numbers is given. Subset Sum consists in answering the question: is there a subset of those numbers whose sum is equal to a given limit. Subset Sum is N P-complete and can be considered as a special case of the knapsack problem. [START_REF] Karp | Reducibility among combinatorial problems[END_REF] Consider a collection of integer numbers H = {l 1 , l 2 , . . . , l N } and an integer limit L 1.

The instance of Subset Sum is denoted by SS H .

An instance V O

t st i l i , ∀i ∈ {1, 2, . . . , N }, (9.2a) N i=1 t st i L. (9.2b)
The following solution is considered. The thresholds h st i , for each demand st i , where i = 1, 2, . . . , N , are set to l i • (1ǫ). The first routing scheme (the one used for the volume below the threshold) for each demand uses link d, while the second routing scheme for each demand uses link u.

Let β = (β ij ) i,j∈V , where β ij = 1 or β ij = -1 be any vector. Define D β as follows: and a matrix t ∈ D β for which the routing is not feasible. Given any

D β = D ∩ {t : ∀ i,j∈V β ij (t ij -h ij ) 0}. It is clear that D = β∈{-1,1}
β ∈ {-1, 1} |V|(|V|-1) , the function max(t ij -h ij , 0)) can be replaced by t ij -h ij if β ij = -1, or by 0 if β ij = 1,
while function min(t ij , h ij ) is equal to t ij when β ij = 1, and to h ij in the other case. In other words, constraint (9.1h) is linear in t, and it has the same form for all matrices of D β .

Consequently, the existence of a matrix t ∈ D β for which the solution above is not feasible is equivalent to the existence of an extreme point of D β for which the same holds. To check feasibility, it is then possible to consider only extreme points of the family of polytopes D β where β ∈ {-1, 1} |V| (|V|-1) . This observation will be useful since the extreme points of D β have a very simple structure. Proof. Suppose that the answer to SS H is YES. Then the traffic demand polytope D contains at least one extreme point such that ∀ i=1,2,...,N t st i ∈ {0, l i }, and N i=1 t st i = L. Such an extreme point requires ǫ • L of capacity at the link u, which is 0.5 • ǫ more than the available capacity. Therefore, the given solution to V O H is not feasible. Now assume that the solution is unfeasible. It will be proved that in such a case the answer to SS H is YES. There exists a traffic demand matrix t ∈ D and a routing corresponding to this matrix such that together they require more than ǫ • (L -0.5) of capacity on the link u. According to the observation above, the feasibility has to be only checked for the extreme points of the family of polytopes D β . Each D β is described by sets of constraints but only one of those constraints contains more than one variable. Therefore, for each extreme point of any D β , an equation t st i = {l i , l i • (1ǫ), 0} can be not satisfied only for one t st i , where i = 1, 2, . . . , N . Note that l i • (1ǫ) is the value of the threshold for a demand st i .

Assume that t st 1 = l 1 • (1ǫ). Note that in this case t st 1 = h st 1 so the whole t st 1 is routed using the link d. The rest of the available demands' volume, i.e., at most Ll 1 • (1ǫ) [as a result of (9.2b)], has to be routed in such a way that it will use more than ǫ • (L -0.5) of the capacity of the link u. But max tst i ∈[0,l i ] tst i -hst i tst i = ǫ, for i = 1, 2, . . . , N . Therefore, the remaining volume cannot use more than ǫ • (Ll 1 + ǫ • l 1 ) of the capacity of the link u, and it is less than ǫ • (L -0.5), because it was assumed that l 1 is an integral number and ǫ < 0.5.

Knowing that ∀ i=1,2,...,N t st i = l i • (1ǫ), it is possible to conclude that for any extreme point of any D β for which the routing solution is not feasible, an equation t st i = {l i , 0} has to be satisfied for at least all but one t st i . Assume that the equation is not satisfied for i = N . Then constraint (9.2b) is necessarily saturated. In other terms, we have M + t st N = L, where M is the sum of volumes of the other demands. Notice that this implies that t st N is integer. The demands other than t st N consume at most ǫ • (Lt st N ) of the capacity of the link u, so at least ǫ • (t st N -0.5) has to be consumed by the demand st N . Using (9.2a) and knowing that

h st N = l N • (1 -ǫ) it is possible to write that (t st N -h st N ) ǫ • (t st N -0.5).
In other words, we have l N t st N l N -0.5•ǫ 1-ǫ . The facts that t st N is integer and 0.5•ǫ 1-ǫ < 1 imply that t st N = l N . It means that the answer to SS H is YES.

To finish the proof consider the case where t st i = {l i , 0} is satisfied for each traffic component. If the constraint (9.2b) is saturated, then the answer to SS H is still YES. Suppose that i t st i < L. Since all t st i are integer in this case (either equal to 0 or l i ), the previous inequality becomes i t st i L -1. Then the traffic sent on the link u is less than ǫ • (L -1). However, the routing solution is not feasible implying that this traffic is more than ǫ•(L-0.5). It is clearly a contradiction. Said another way, the answer to SS H is always YES whenever the proposed solution to V O H is not feasible.

Proposition 9.1.2. A decision version of VO Routing is co-N P-complete.

Proof. The feasibility problem is in co-N P since a certificate of a negative response is given by any matrix that cannot be routed according to the proposed thresholds and routing schemes. It is easy to check whether a given matrix can be routing according to some given routing schemes. The reduction proposed in Lemma 9.1.1 ends the proof.

As VO Routing is difficult, it will not be easy to solve it for real world networks in satisfying time. Fortunately, one of its special cases presented in the following section is polynomial. Moreover, according to Chapter 10, the special case (and its modification presented in Section 9.3) is very efficient.

Simplified volume oriented routing

Simplified volume oriented routing is a special case of VO Routing. In the latter case positions of the thresholds are subject to optimization, while in the former case those positions are set to the minimum values of the corresponding demands' volumes. The change makes the problem polynomial. On the other hand, the strategy is not efficient when there are not dominated traffic demand matrices in D that contain zero components.

Notation

In order to formulate the simplified volume oriented routing problem an additional set of constants is introduced.

Problem formulation

The problem of computing the minimum cost simplified volume oriented routing of an uncertainty domain D, denoted by SVO Routing (SVO), can be formulated as in (9.3).

Problem SVO minimize F SV O (D) = a∈A ξ a f a , (9.3a) p∈P(i,j) x ij p 1, ∀i, j ∈ V, (9.3b) p∈P(i,j) x ij p 1, ∀i, j ∈ V, (9.3c) p∈P(i,j),p∋a x ij p x ij a , ∀i, j ∈ V, ∀a ∈ A, (9.3d) p∈P(i,j),p∋a x ij p x ij a , ∀i, j ∈ V, ∀a ∈ A, (9.3e) t min ij = t ′ ij , ∀i, j ∈ V, ∀t ∈ D, (9.3f) t ij -t min ij = t ′′ ij , ∀i, j ∈ V, ∀t ∈ D, (9.3g) i,j∈V (x ij a t ′ ij + x ij a t ′′ ij ) f a , ∀a ∈ A, ∀t ∈ D, (9.3h)
f a c a , ∀a ∈ A, (9.3i)

x ij p , x ij p 0, ∀p ∈ P(i, j), ∀i, j ∈ V. (9.3j)
The formulation (9.3) modifies (9.1) by simplifying definitions of t ′ ij and t ′′ ij , i.e., it replaces (9.1f) with (9.3f), and (9.1g) with (9.3g). Moreover, as threshold variables h ij are not used, inequalities (9.1j) are obsolete in (9.3). Notice that, if t min ij = 0, for all i, j ∈ V, then SVO Routing is equivalent to Robust Routing.

Computational complexity

The problem is polynomial, and can be easily solved using techniques presented in Chapter 7, i.e., using an algorithm based on constraint generation (see [START_REF] Ben-Ameur | New economical virtual private networks[END_REF][START_REF] Ben-Ameur | Routing of uncertain traffic demands[END_REF]), and generating paths in an iterative way.

General volume oriented routing

General volume oriented routing can be seen as an extension of SVO Routing, with modified (more general) division of demands between routings. In fact, it is a generalization of SVO Routing, so it cannot be less efficient. On the other hand, it is more complicated to implement.

Notation

In order to formulate the problem an additional set of constants has to be introduced.

t max ij : defined as t max ij = max t∈D t ij .

Problem formulation

The formulation of the problem of computing the minimum cost general volume oriented routing of an uncertainty domain D, denoted by GVO Routing (GVO), is alike the formulation of SVO Routing, thus alike the formulation of VO Routing. The only differences are in definitions of t ′ ij and t ′′ ij , i.e., constraint (9.3f-9.3g) are replaced by (9.4f-9.4g).

Problem GVO

minimize

F GV O (D) = a∈A ξ a f a , (9.4a)
p∈P(i,j)

x ij p 1, ∀i, j ∈ V, (9.4b)
p∈P(i,j)

x ij p 1, ∀i, j ∈ V, (9.4c)
p∈P(i,j),p∋a

x ij p x ij a , ∀i, j ∈ V, ∀a ∈ A, (9.4d) p∈P(i,j),p∋a x ij p x ij a , ∀i, j ∈ V, ∀a ∈ A, ( 9.4e
)

α ij t ij + β ij = t ′ ij , ∀i, j ∈ V, ∀t ∈ D, (9.4f) (1 -α ij )t ij -β ij = t ′′ ij , ∀i, j ∈ V, ∀t ∈ D, (9.4g) i,j∈V (x ij a t ′ ij + x ij a t ′′ ij ) f a , ∀a ∈ A, ∀t ∈ D, (9.4h) f a c a , ∀a ∈ A, (9.4i) x ij p , x ij p 0, ∀p ∈ P(i, j), ∀i, j ∈ V. (9.4j)
Where vectors α and β are given, and satisfy the following set of constraints.

α ij t min ij + β ij 0, ∀i, j ∈ V, (9.5a) (1 -α ij )t min ij -β ij 0, ∀i, j ∈ V, ( 9.5b
)

α ij t max ij + β ij 0, ∀i, j ∈ V, (9.5c) (1 -α ij )t max ij -β ij 0, ∀i, j ∈ V. (9.5d)
It is obvious that SVO Routing is a special case of GVO Routing, where α ij = 0 and β ij = t min ij , for each i, j ∈ V. An interesting observation is that for each D there exists a simple way to obtain an optimal pair of vectors α and β. Proposition 9.3.1. For a given D vectors α and β defined in (9.6) yield an optimal solution, i.e., there are no cheaper solutions to GVO Routing for a given D and any other α and β.

α ij = -t min ij t max ij -t min ij , ∀i, j ∈ V, ( 9.6a
)

β ij = t max ij t min ij t max ij -t min ij , ∀i, j ∈ V. (9.6b)
Proof. Consider a capacity consumed by only one demand ij. The constraints defining the used capacity on a link a for GVO Routing can be combined into:

x ij a (α ij t ij + β ij ) + x ij a [(1 -α ij )t ij -β ij ]
, and for α and β defined as (9.6) into:

z ij a t min ij t max ij -t ij t max ij -t min ij + z ij a t max ij t ij -t min ij t max ij -t min ij .
For the sake of clearness, in the latter case, z ij a was substituted for x ij a and z ij a for x ij a . Assume that the routing for GVO Routing (with α and β denoted by α ′ and β ′ )is known and expressed using vectors x and x. In order to obtain the same results for all t ∈ D and suggested α and β take:

z ij a = (α ′ ij + β ′ ij t min ij )x ij a + (1 -α ′ ij - β ′ ij t min ij )x ij a , z ij a = (α ′ ij + β ′ ij t max ij )x ij a + (1 -α ′ ij - β ′ ij t max ij )x ij a .
It is an easy exercise to check that the obtained loads on each link will be exactly like for GVO Routing. Moreover, the routing is feasible, because both z ij a and z ij a are convex combinations of x ij a and x ij a , for a ∈ A and i, j ∈ V. Note that 0

α ′ ij + β ′ ij t min ij 1, and
0 α ′ ij + β ′ ij t max ij
1, for all i, j ∈ V, because of (9.5).

The proof contains an observation that will be interesting in the following section of the thesis, and now will be stated as a corollary.

Corollary 9.3.2. Each solution to GVO Routing can be transformed to another solution to GVO Routing with the vectors α and β defined like in (9.6). The solution will be of the same cost, and it will require the same amount of capacity at each link.

Computational complexity

Alike SVO Routing, GVO Routing is polynomial, and can be easily solved using techniques presented in Section 7, i.e., using an algorithm based on constraint generation (see [START_REF] Ben-Ameur | New economical virtual private networks[END_REF][START_REF] Ben-Ameur | Routing of uncertain traffic demands[END_REF]), and generating paths in an iterative way. Having the congestion the efficiency of different partitioning strategies was tested. Moreover, running times of algorithms capable of solving the considered problems were also checked. In this phase routing costs were used as cost functions.

In order to compare the strategies on equal terms the traffic demand polytopes were scaled in such a way that the congestion z for each of them would be 1.1 if those scaled polytopes had been used in the previous phase of the experiments. For instance, for the france network with 56 demands while solving different partitioning problems for Robust Routing all traffic matrices from the traffic demand polytope which is a full hose model polytope (test case #18) are multiplied by 1.1 1.98 , while all traffic matrices from the traffic demand polytope which is a convex hull of 10 extreme points of the full hose polytope (test case #17) are multiplied by 1.1 1.20 . For the same test cases and No Sharing the traffic demand polytope is even more diminished, and all the traffic matrices are multiplied by 1.1 3.91 and 1.1 3.86 , respectively.

In order to handle the insolvability of the test cases (they are built in such a way that all networks are congested) additional uncapacitated arcs are introduced between all pairs of active nodes. Routing costs of these additional arcs are set in such a way that it is approximately twenty times more expensive to use them than paths consisting of arcs in the original network. Those arcs can be considered as possibilities to rent capacity from other operators or as links set up using different, and more expensive, technology, e.g., radio links or satellite links. Note that, those additional expensive links are not included in Table 10.1 (column V).

For each topology and each polytope up to five different directions α of the hyperplane were used. The presented result correspond to the most profitable direction of the hyperplane.

In Table 10.3 the first part of the results is presented. The first column (#) contains identification numbers of test cases, and is the same as in Table 10 Notice that the gain for No Sharing is significant, while the gain for Dynamic Routing is rather small. The reason is that No Sharing in its nature is very restrictive, and any mechanism that can relax its resource reservation rules is of great importance. On the other hand, Dynamic Routing is very flexible. Therefore, there is no place for significant improvements.

As shown in Table 10.3, Different Reservation almost always outperforms Identical Reservation. The only case when these two strategies provide similar results is test case #18 for Robust Routing (gain for both is 0). In other cases the difference in gains seems to be stable, and it oscillates near 5%.

Volume oriented strategies

In the second part of the experiments volume oriented strategies are considered, i.e, SVO Routing and GVO Routing. Notice that VO Routing was not tested because of its complexity.

An evaluation strategy used in this section is similar to the one used for the partitioning strategies. First, the polytopes were scaled in such a way that the congestion, using Robust Routing, obtained for the most loaded link was 110%. Then, in order to handle the insolvability of the test cases additional uncapacitated arcs between all pairs of active nodes were introduced. Routing costs of these additional arcs were set in such a way that it was approximately twenty times more expensive to use them than paths consisting of arcs in the original network.

In this part of the experiments all test cases were used (including B-S polytope model).

As far as the hose model is concerned, the general hose model was considered. What is more, computational times are also very good. They prove that the volume oriented strategies can be successfully implemented in medium size networks. The 9000 second time limit was hit only three times (twice for #18 and once for #20), and in all those cases feasible solutions to the problem had been first obtained (that is a reason why the results are presented using a sign ). The computational complexity of different combinations of these basic models, partitioning strategies, and volume oriented strategies were discussed, e.g., a special case of Dynamic Routing was presented, which is polynomial even when Different Reservation is considered for it.

For the partitioning problems two algorithms were proposed: the double binary search algorithm that solves Identical Reservation, and another (polynomial time) algorithm that solves Identical Reservation for No Sharing when the traffic demand polytope is given by a set of its extreme points. The presented algorithms (and a method that solves Different Reservation introduced earlier in the literature) were thoroughly tested, and proved to be applicable to networks of practical sizes. Differences in network utilization's efficiency of the three basic problems were shown. What is more, possible gains that result from the implementation of different partitioning strategies were also presented.

In the thesis the direction of the hyperplane used for partitioning is assumed to be known (not subject to optimization), and in the experiments hyperplanes of a particular form were used, i.e., traffic between a given pair of nodes is a hyperplane's direction. But, in general, it is possible to use any hyperplane's direction, even one that is not directly connected to traffic, e.g., time.

The presented algorithms can be easily extended to solve a problem when the traffic demand polytope is divided by many hyperplanes of the same direction. However, a more general problem that consists in providing an optimal set of hyperplanes of unknown directions still remains a challenge.

As far as the volume oriented strategies are concerned, it was shown in the thesis that the problem of providing an optimal solution satisfying VO Routing is difficult in general.

However, a way to cope with this difficulty was also presented, i.e., SVO Routing and GVO Routing were introduced, which are polynomially solvable modifications of VO Routing.

It was shown that SVO Routing cannot outperform GVO Routing as far as cost is concerned, but on the other hand, it can be implemented easier. Moreover, those strategies can be equally effective when some special polytopes are considered, e.g., B-S polytope model. Finally, numerical results proving the applicability and efficiency of the introduced volume oriented approaches were presented.

In the thesis different strategies that were to merge the efficiency of the dynamic routing with the simplicity of the robust stable routing were presented. Although the obtained results are satisfactory, there is still a lot of space for improvements. The only theoretical bound for the efficiency of novel strategies to be proposed is the efficiency of the dynamic routing. The bound has not been reached by any solution that is solvable in polynomial time. Thus, the research field is by no mean exhausted. • Les capacités utilisées pour la protection sont disjointes de celles utilisées en régime normal. On est alors dans le cas sans Stub-Release (nSR).

Dans les deux cas, une optimisation fine est nécessaire pour mutualiser les ressources au mieux en tenant compte des possibilités techniques offertes pour chaque variante. Dans les deux cas, il est important que la capacité de protection soit partagée entre les flux restaurés suite à des pannes différentes.

La protection peut:

• Soit dépendre de la panne (failure-dependent, FD). Les chemins de routage utilisés pour restaurer un flux primaire donné peuvent alors être différents en cas de pannes différentes.

• Soit être complètement indépendante de la panne (failure-independant, FI). C'est-àdire qu'il faut définir des chemins de routage qui soient valides quelle que soit la panne qui touche les chemins utilisés en régime normal.

Dans la première partie de la thèse, nous analysons la complexité de différents mécanismes Le problème majeur avec ce type d'approche est que les routages peuvent différer considérablement entre les sous-ensembles obtenus en partitionnant le polytope, et la mise en oeuvre de ces changements peut alors entra îner des pertes graves de trafic (en raison de

a

  -edge (arc); a s , b s -edges from Figure 3.4; b -bottom link; c a -capacity of edge a; d -demand; d(D, D ′ ) -Hausdorff distance between polytopes D and D ′ ; e -subset of vertices; e(p) -independent set defined by the condition: vertex v n belongs to e(p) if and only if path p survives in failure state s n ; f a -flow on edge a; h d -volume of demand d; h ij -threshold for a demand ij; i, j, v -nodes (vertices);

u

  d -source of demand d; w d -sink of demand d;

B

  i -upper bound for incoming traffic for node i; C -maximum size of the cover; D -traffic demand polytope, or number of demands; H -sum of integer numbers from H; L(D, β) -left hand side polytope, i.e., D ∩ {t : α • t β}; xiii M -sufficiently large constant; N -number of nodes; R(D, β) -right hand side polytope, i.e., D ∩ {t : α • t β}; X -total flow realized for a demand; A -set of all edges (arcs); A h -set of edges belonging to a path pair from i to j, where h = {i, j}; B -list of positions of a hyperplane; D -set of all demands, also set of indices; E -family of all independent sets; E v -family of all independent sets containing vertex v; G -graph; H -sequence of positive integer numbers, or a family of subsets; I -support of a feasible solution to C G ; I v -support of a feasible solution to C G containing node v; L -ordered collection of reliable edges; M -state understood as a sorted multiset of vertices; N -network; O -normal state; P -set of all candidate paths; P d -set of candidate paths for demand d; P s d -subset of paths in P d that survive in state s ∈ S;

γ

  a -component of w a defines as: γ a = λ {a} d ⋆ if {a} ∈ S, and γ a = 0 otherwise; δ + (v) -set of all edges leaving node v; δ -(v) -set of all edges entering node v; λ s d -dual variables for (3.2b), or length of the shortest path with respect to π s a ; ξ a -unit cost of edge a; ξ a (f a ) -cost of edge a carrying flow f a ; xv ξ p -unit cost of path p; π s a -dual variables for (4.1d), (4.3c), (5.1d), or for (5.4c); π v -dual variable for (3.5b); χ f (G) -fractional chromatic number of graph G; 2D G -instance of 2Div-Path for G; F C G -instance of Fractional Coloring for G; F D G -instance of FD-nSR, or FDM, corresponding to F C G ; F I G -instance of FI-nSR corresponding to 2D G ; F I H -instance of FI-nSR corresponding to P A H ; IC U -instance of Infinite Capacities F-D Paths corresponding to SC U ; P A H -instance of Partition for H; P D G -instance of PD corresponding to V C G ; P DD G -instance of PDD corresponding to F C G ; SC U -instance of Set Cover for U; SS H -instance of Subset Sum for H; V C G -instance of the Vertex Cover for G; V O H -instance of VO Routing corresponding to SS H ; xvi Chapter 1

  and set A of links (directed arcs). Set D represents directed end-to-end (traffic) demands. The number of all demands, |D|, will be denoted by D. The source and target nodes of demand d ∈ D are denoted by u d and w d , respectively. The volume of demand d ∈ D is given by h d . The demand volumes are realized by means of path flows assigned to (directed) paths form u to w. The cost of realizing one unit of demand on link a ∈ A is denoted by ξ a . Each link a ∈ A has its working (primary, basic) capacity, denoted by y ′ a , used for realizing flows in the normal operating state (i.e., working or primary flows), and the protection or backup capacity y ′′ a used for restoration of failed primary flows by means of backup or restoration flows. Both y ′

  Four failure-disjoint shortest paths.

Figure 3 . 1 :

 31 Figure 3.1: Two, three, and four failure-disjoint shortest paths.

  Non-disjoint paths solution.

Figure 3 . 2 :

 32 Figure 3.2: Simplified network with multiple-link failures.

Figure 3 . 3 :

 33 Figure 3.3: Network N resulting from graph G.

Proof.

  Each feasible solution z = (z e : e ∈ E) of F C G can be identified with its support I = {e ∈ E : z e > 0} and the vector z = (z e : e ∈ I) of positive weights assigned to the independent sets from the support. Analogously, each feasible solution x = (x p : p ∈ P) of P DD G can be identified with its support Q = {p ∈ P : x p > 0} and the vector x = (x p : p ∈ Q) of positive flows assigned to the paths from the support. The subfamily of all independent sets from I containing a given vertex v ∈ W will be denoted by I v , and the set of all paths from Q surviving in a given state s ∈ S by Q s . It will be demonstrated that each feasible solution I, z = (z e : e ∈ I) of F C G corresponds to a feasible solution Q, x = (x p : p ∈ Q) of P DD G such that N • f (z) = F (x), and vice versa. Let I, z = (z e : e ∈ I) be a given feasible solution of F C G . The corresponding feasible solution of P DD G consists of a set Q = {p(e) : e ∈ I} ⊆ P of paths with the flow assignment defined as x p(e) = z e , e ∈ I. For each n (1 n N ), path p(e) uses the top link t n , if v n ∈ e; otherwise, it uses the bottom link b n . In effect, since s n = {b n }∪{t m : v m and v n are adjacent in G} and p(e) = {t n : v n ∈ e}∪{b m : v m /

⋆

  2) is based on the following pricing problem PP/PD, solved separately for each demand d ∈ D. PP/PD consists of finding a path p between the end nodes u d and w d of demand d ∈ D minimizing the generalized path length. denotes the optimal value of the dual variable corresponding to inequality (3.2b) while Sp stands for the set of all failure states s ∈ S that affect path p (p is assumed to be elementary and is identified with the set of links it traverses). Note that λ s d ⋆ 0 so it is clear that p 0. If the resulting p is strictly less than the generalized lengths of all paths in the current candidate set P then p is added to P. If for at least one demand d ∈ D such a path has been added, the resulting (extended by one or more paths)problem PD is resolved, and the pricing problems are reentered.

Figure 3 . 4 :

 34 Figure 3.4: Transformation of the PD pricing problem to Shortest Path Problem with Resource Constraints.

• Criterion 1 .• Criterion 3 .• Criterion 4 .

 134 (a) Non-bifurcated flow (IP): x dr ∈ {0, 1}, d ∈ D, r ∈ T d . (b) Bifurcated flow (LP): x dr ∈ R + , d ∈ D, r ∈ T d . • Criterion 2. (a) Predefined lists of path-pairs: T d are given in advance. (b) All possible elementary path-pairs in T d . (a) Single link failure scenario: |s| = 1, s ∈ S\O. (b) Arbitrary link failure scenario (failures of more than one link at a time are admitted): |s| 1, s ∈ S \ O. (a) Single demand: D = 1. (b) Multiple demands: D 1.

  indicated in Criterion 1, by IP the version of problem P that is characterized by binary flow variables (non-bifurcated flows) is denoted, and by LP-its bifurcated counterpart (linear relaxation of IP) with continuous flows. First observe that the variant specified by Criterion 1b (LP) and Criterion 2a (predefined path-pairs lists) is always polynomial, no matter what Criteria 3 and 4 are. This is because

Figure 4 . 1 :

 41 Figure 4.1: Network of two nodes and N+1 links.

Proposition 4 . 1 . 1 .

 411 of positive integer numbers. Denote by D the sum d∈ D h d defined for any subset D of the set of indices D = {1, 2, . . . , D}. Problem Partition consists in answering the question whether there is a partition (split) of the set D into two subsets D ′ and D ′′ (D ′ ∪ D ′′ = D, D ′ ∩ D ′′ = ∅), such that D ′ is equal to D ′′ . Partition (D ′ , D ′′ ) will be called a valid partition. Consider an instance P A H of Partition for a given sequence H. The corresponding instance F I H of problem (4.1) is specified by means of a network that consists of only two nodes, u and w, connected by three parallel links A = {a 1 , a 2 , a 3 } (see Figure 4.1 with N = 3). The unit capacity costs are all equal to 1, ξ a = 1 for a ∈ A. The set of demands is defined as D = {1, 2, . . . , D}, and each demand d ∈ D has its source in node u and its sink in node w, its volume is given by h d . Also, the (single) failure of each of the three links is included into the considered failure scenario, so the scenario contains the normal state O and the three failure states corresponding to the three links. Let H = D. The optimal objective of F I H is3 2 H if and only if P A H forms a valid partition.

Figure 4 . 2 :

 42 Figure 4.2: Network N resulting from graph G.

  Therefore, it is impossible to conclude from the proof of Proposition 4.1.1 that problem P in the considered variant cannot be approximated within a given accuracy ε in polynomial time. That is why, it is worth to show how to modify the proof of Proposition 4.1.2 to cover the version of the problem considered in Proposition 4.1.1. The modification is simple. Consider set D of demands instead of just one demand d.

Figure 4 . 3 :

 43 Figure 4.3: Network exposing differences between problems.

Figure 4 . 4 :Figure 4 . 4 .

 4444 Figure 4.4: Modified graph corresponding to the graph of Figure 4.3.

Lemma 4 . 2 . 4 .

 424 w}}, consisting of arcs that form pairs of arc-disjoint paths computed earlier and also selected in the previous phase of the algorithm, e.g., a set A {u,a 1 } consists of arcs that form the pair of arc-disjoint paths between u and the source of a 1 , set A {a 1 ,a 2 } connects the sink of a 1 to the source of a 2 , while set A {a L ,w} connects the sink of a L to w. In the example a reliable arc set is L = {(u, v 1 )}, and two path pair sets are A {u,(u,v 1 )} = ∅ and A {(u,v 1 ),w} = {(v 1 , w), (v 1 , v 3 ), (v 3 , w)}. Now consider a graph G = (V, A ′ ), where A ′ = h∈H A h ∪ L. Define a cost of this graph as a∈A ′ ξ a . In the example A ′ = {(u, v 1 ), (v 1 , w), (v 1 , v 3 ), (v 3 , w)}, and a cost of G is 8. The cost of G is a lower bound for the cost of the optimal solution of Failure-Disjoint Paths.

Proposition 4 . 2 . 6 .

 426 Consider the graph T defined in the proof of the previous lemma. Recall that T is obtained from G by doubling the arcs of L, where G and L are given by the previous phase of the algorithm. By computing a shortest pair of arc-disjoint paths in T , a feasible solution of Failure-Disjoint Paths is obtained. The resulting pair of paths cannot cost more than the graph G itself, because it cannot use any arc that is not in G. Therefore, according to Corollary 4.2.4, this solution is necessarily an optimal solution of Failure-Disjoint Paths. Failure-Disjoint Paths can be solved in polynomial time.

  Consider a generalization of Failure-Disjoint Paths, denoted by General F-D Paths, which is as follows. General failure-disjoint path problem minimize F (f ) = a∈A ξ a (f a ), (4.4a)

Figure 4 . 5 :

 45 Figure 4.5: Sample instance of Infinite Capacities F-D Paths.

  number of paths) or unreliable (can accommodate only one path). It means that c a = 1, for a ∈ S, and c a k, otherwise. Assume that ξ a (f a ) is constant and equal to ξ a when f a > 0, for all a ∈ A, still ξ a (0) = 0. Denote the problem as Infinite Capacities F-D Paths.Consider a universe U and a family H of subsets of U. A cover is a subfamily C ⊆ H of sets whose union is U. In the Set Cover decision problem, the input is a universe U, a family H and an integer C. The question is whether there is a cover of size C or less.Consider an instance ofSet Cover denoted by SC U . A corresponding instance of Infinite Capacities F-D Paths, denoted by IC U , is a network consisting of a source u, a sink w, |H| vertices of a first group and |U| vertices of a second group. Each vertex of the first group, denoted by n ′ h , corresponds to one element h from the family H, while each vertex of the second group, denoted by n ′′

Figure 4 . 5 .Proposition 4 . 2 . 7 .

 45427 It is now quite simple to see that a cover of size C exists for SC U if and only if problem IC U has a solution whose cost is less than or equal to C. Since the reduction is polynomial, so Infinite Capacities F-D Paths is N P-hard. General F-D Paths is N P-hard.Note that Infinite Capacities F-D Paths is a special case of General F-D Paths, thus both are N P-hard. Moreover, Set Cover is N P-hard even when the maximum size of elements in H is 3. It means that General F-D Paths is N P-hard even when capacities of arcs do not exceed 3.

  the sequence does not have to contain all the vertices of the network). Define a state as a sorted (according to the topological orderV ′ ) multiset of k vertices M = (n 1 , n 2 , . . . , n k ). A number of occurrences of a vertex v in a multiset M is denoted by |M v |. Note that v∈M |M v | = k. Each stateM points to an associated optimal solution that routes k paths from u to vertices in M satisfying the capacity constraints of the considered problem. Now divide all possible states into |V ′ | groups (V ′ is the topological order mentioned before) in a way that a state M belongs to a group

3 Figure 4 . 6 :Proposition 4 . 2 . 8 .

 346428 Figure 4.6: State graph.

For

  each demand d ∈ D, the pricing problem Price-FI-SR for the bifurcated version of FI-SR consists in finding a pair of failure-disjoint paths r = (p, q) from u d to w d minimizing

•

  , . . . , t N , b 1 , b 2 , . . . , b N are assigned zero unit capacity costs (ξ tn = ξ bn = 0, n = 1, 2, . . . , N ). The considered demand starts in node w and terminates in node v N . Consider an undirected graph G with the set W = {v 1 , v 2 , . . . , v N } of N vertices. Let E be the family of all independent sets of G. The resulting instance of Fractional Coloring (i.e., of problem FGC (3.5)) will be denoted by F C G . The instance F D G of problem FD-nSR (5.1) corresponding to F C G is modeled by means of the resulting modified directed network N = (V, A) and the single demand from node w to node v N with volume equal to 1. In fact, in this special case problem FD-nSR can be equivalently transformed to the following LP. Problem FDM (special case of FD-nSR) minimize G(x) = max s∈S {1 -p∈P s

  Price-FD-nSR), for a given demand d ∈ D, for the bifurcated version of FD-nSR consists first of all in finding the shortest path, separately for each situation s ∈ S \ {O}, with respect to the optimal dual variables π s a corresponding to constraints (5.1d). Then, denoting the length of each such shortest path by λ s d ⋆ , we look for the shortest primary path p from u d to w d minimizing a∈p

⋆

  each demand d ∈ D, the pricing problem Price-FD-SR for the bifurcated version of FD-SR consists essentially in finding a primary path p from u d to w d minimizing p = are optimal dual variables corresponding to constraints (5.4c), and λ s d ⋆ are the lengths of the shortest paths for situations s ∈ S \ {O}, calculated according to the optimal dual variables π s a ⋆ (as in problem Price-FD-nSR, see the previous section). It

a

  hyperplane α • t = β (β is subject to optimization) are given. Note that β min β β max , where β min = min t∈D α • t and β max = max t∈D α • t. Having D and α it is possible to partition D into two subsets L(D, β) = D ∩ {t : α • t β} and R(D, β) = D ∩ {t : α • t β}, called the left hand side polytope (LHSP) and the right hand side polytope (RHSP), respectively. Then, we can consider a robust routing for each of them. Said another way, instead of having only one routing scheme, we will have two schemes: if the current traffic matrix belongs to the first (second) subset it uses the first (second) routing scheme.

  non-decreasing function of β, and F RR (R(D, β)) is a non-increasing function of β we can find, using a binary search, β ⋆ such that F DR/RR (D, β ⋆ ) is minimized. Notice that the binary search should depend in a logarithmic way on γ. Obviously β ⋆ is a solution to Different Reservation.

Figure 7 . 1 :

 71 Figure 7.1: Network exposing non-continuity of the cost function.

Lemma 7 . 3 . 1 .

 731 For each bounded polytope D the condition lim β 1 →β 2 d(L(D, β 1 ), L(D, β 2 )) = 0 holds.

  First upper and lower bounds for the cost F IR/RR (D, β), denoted by F min and F max respectively, have to be known. The simplest lower bound F min is 0, while the simplest upper bound is equal to the value of the solution to Robust Routing or No Sharing depending on the actual version of the considered problem. Obviously those bounds can be upgraded (see Section 8.4.1).

Figure 8 . 1 :

 81 Figure 8.1: Network exposing non-polynomiality of the algorithm.

Corollary 8 . 3 . 3 .

 833 Each extreme point of either LHSP or RHSP belonging to the hyperplane α•t = β has to be either an extreme point of D or a strict convex combination of one extreme point of D belonging to LHSP and one extreme point of D belonging to RHSP.

Corollary 8 . 3 . 4 .

 834 Different Reservation for Dynamic Routing, for given β, can be solved in polynomial time if the traffic demand polytope D is defined as a convex hull of a given set of traffic matrices.

Proposition 8 . 3 . 5 .

 835 Different Reservation for Dynamic Routing can be solved in polynomial time if the traffic demand polytope D is defined as a convex hull of a given set of traffic matrices.

Figure 8 . 2 :

 82 Figure 8.2: Evaluation of the lower bound of a convex function.

  H of VO Routing corresponding to SS L is modeled by means of a graph presented in Figure9.1. Capacities of all links but one are unlimited. Only the capacity of a link u is limited, and is equal to ǫ • (L -0.5), where ǫ is a sufficiently small number, i.e., 0 < ǫ < 0.5. Routing costs are set to 0 (in fact those values are irrelevant, because the feasibility of a solution is being verified, and not its actual cost). The traffic demand polytope D describes possible volumes of N different demands st i , where i = 1, 2, . . . , N , each corresponding to one number from H. The inequalities describing D are as follows.

:

  defined as t min ij = min t∈D t ij .

11 A. 1 •

 111 Première partie: Complexité L'un des mécanismes les plus courants pour la sécurisation des réseaux de transport est la protection de chemin (path protection, PP). Un exemple est le mécanisme de protection 1+1, appelé Hot Standby (HS) dans lequel on définit un chemin primaire utilisé en temps normal et un chemin secondaire disjoint du chemin primaire et portant le même signal. Lorsque le chemin primaire tombe en panne, on reçoit les données à travers le chemin secondaire. Le mécanisme 1+1 est efficace en termes de temps de restauration, mais coûteux en termes de capacités. En effet, les capacités de protection ne sont pas partagées entre les différents chemins primaires et doivent donc être au moins égales aux capacités utilisées en temps normal. Certaines variantes de la protection de chemin (comme la protection n : m et la diversité des chemins) peuvent réduire le coût de la protection d'une manière limitée. Pour réduire les coûts d'une manière plus sensible, des mécanismes actifs de restauration de chemins (PR) sont envisagés. Bien que PR est assez complexe à mettre en oeuvre et peut ralentir les temps de restauration, il permet de mutualiser les ressources et de réduire les coûts. La technique PR consiste à prévoir des chemins de routage utilisés en régime normal (absence de pannes) et d'autres qui sont utilisés en cas de panne. Lorsqu'une panne se produit, les connexions qui utilisaient des chemins affectés par la panne sont reroutés sur des chemins valides. On considère plusieurs variantes de PR: Les capacités utilisées pour la sécurisation peuvent provenir des capacités libérées par les chemins qui étaient utilisés en régime nominal et qui ne le sont plus à cause d'une panne donnée. On est alors dans le cas dit avec Stub-Release (SR).

  de sécurisation des réseaux. La complexité des problèmes d'optimisation sous-jacents dépend également des scénarios de panne considérés. Dans certains cas, on considère uniquement des pannes simples et non-simultanées de quelques éléments du réseau. Dans d'autres cas, on peut avoir des pannes multiples où plusieurs composantes du réseau sont en panne. Le fait de considérer des pannes multiples rend les problèmes d'optimisation plus difficiles.Il est important de conna ître la complexité des problèmes d'optimisation liés à la conception des réseaux résilients. En effet, conna ître cette complexité aide à choisir les bonnes méthodes de résolution pour ces problèmes Notre principale contribution dans ce cadre est le résultat suivant.La plupart des problèmes de réseaux résilients sont N P-difficiles, même lorsque l'on autorise la bifurcation des flux.Les problèmes considérés sont en réalité des variantes des problèmes de multi-flots liés aux mécanismes PP et PR. Nous avons établis que tous les problèmes sont N P-difficiles lorsque des pannes multiples peuvent se produire simultanément, même lorsqu'on autorise sans reroutage. Le concept de la PD a été étudié dans la littérature sous des noms différents, on retrouve par exemple les termes de diversification et de protection partagée en fonction de la demande. La complexité des problèmes de HS-PP et PD est étudiée dans le début de la première partie.La suite de la première partie est consacrée à l'étude de la complexité de la restauration de chemin (PR). Il s'agit de mécanismes actifs, dans le sens où ils restaurent le fonctionnement des flux détruits par une panne. Certes, pour garantir une bonne restauration, des capacités de protection supplémentaires sont nécessaires par rapport à un réseau conçu uniquement pour fonctionner sans panne. Mais le coût des capacités supplémentaires est généralement beaucoup plus faible pour PR que pour les PP, puisque, par définition, les capacités de protection PR sont partagées par différentes demandes et pour des pannes différentes. Dans un premier temps, nous supposons que les flux défaillants sont restaurés de façon indépendante de la panne (FI). Le cas de la restauration dépendant des pannes (FD) est traité dans un deuxième temps.Les mécanismes PR sont étudiés sous deux hypothèses différentes: avec ou sans stubrelease. Avec Stub-Release (SR), la capacité sur les parties survivantes (stubs) d'un chemin de routage qui a été coupé par une panne peut être réutilisée pour la sécurisation. Sans stub-release (nSR), cette capacité est exclusivement réservée pour le routage en absence de panne, et ne peuvent pas être réutilisés en cas de défaillance. Notez que nSR est typique pour les couches de transport, par exemple, pour les réseaux optiques, ou les réseaux SONET.Selon les paramètres considérés, on obtient ainsi quatre problèmes différents de restauration de chemins, à savoir: FI-nSR, FI-SR, FD-nSR, et FD-SR. La variante non-bifurquée (mono-routage) du problème de FI-SR, suppose que chaque demande est routée sur un seul chemin en absence de panne. A chaque panne affectant le chemin primaire choisi, la demande chaque composante du trafic. Le routage est alors calculé sur la base de cette matrice. Cette approche a l'avantage d'être simple, mais elle peut fournir des solutions onéreuses. En effet, elle n'autorise pas le partage des ressources par des composantes de trafic qui n'atteignent pas le pire cas simultanément.La deuxième approche est basée sur une modélisation probabiliste des variations de trafic.Après avoir spécifié un modèle probabiliste pour la prévision du trafic, on peut chercher le routage qui optimise un certain critère probabiliste: le débit moyen, le retard moyen, la probabilité de blocage, etc. La solution obtenue de cette manière est bonne en moyenne, mais peut être très mauvaise dans certains cas. En outre, cette méthode nécessite la connaissance des modèles de probabilité, qui sont généralement difficiles à obtenir. Ce type d'approche est généralement appelé programmation stochastique. Une approche classique différente, l'optimisation robuste, prend en compte un nombre fini de situations possibles. Dans ce cas, on cherche une solution qui prend en charge toutes les situations envisagées. Dans le contexte des réseaux, il s'agit alors de déterminer un schéma de routage, de telle sorte que chacune des matrices de trafic appartenant à un ensemble fini donné de matrices de trafic peut être satisfaite par le réseau. Un autre modèle robuste suppose que le trafic sortant de chaque noeud est borné (la limitation sur le trafic entrant peut également être prise en compte).La matrice de trafic peut être alors n'importe quelle matrice satisfaisant ces contraintes. Ce modèle avec incertitude est appelé hose model. Plusieurs problèmes de conception de réseau basé sur ce modèle ont reçu une attention considérable dans la littérature.Certains auteurs proposent un modèle différent, en supposant que tous les noeuds ne peuvent pas produire la quantité maximale de trafic simultanément. En fait, ce modèle, ainsi que le hose model présenté ci-dessus, sont des cas particuliers d'un modèle polyédral plus général. Le modèle suppose que chaque matrice de trafic possible appartient à un polytope.Dans la littérature un algorithme en temps polynomial a été proposé pour calculer un plan de routage qui résout ce problème. Le routage est robuste et stable (robuste, car il est compatible avec toutes les matrices, et stable, car il ne change pas lorsque des changements de matrice se produisent). Bien que le modèle ait été défini pour les matrices de trafic appartenant à un polytope, il peut également traiter avec succès les problèmes avec des matrices appartenant à une union de polytopes.Une approche différente face à l'incertitude consiste à permettre à un réseau de changer de routage de façon dynamique, quand il y a un changement significatif en termes de matrice de trafic. Ce problème a été intensément étudié dans le cadre des réseaux commutés. Des règles différentes peuvent être appliquées pour connecter des appels en fonction de la situation actuelle, comme par exemple, le routage dynamique alternatif, le routage séquentiel, etc.Bien que ce type de routage présente de nombreux avantages, il est généralement difficile à mettre en oeuvre. De plus il n'est pas optimal car les règles utilisées sont fixées à l'avance.Cependant, il peut être utilisé comme point de référence (borne inférieure) pour évaluer les approches présentées plus tôt. Dernièrement, il a été prouvé que le coût optimal d'un réseau fondé sur les modèles de routage robustes et stables (fractionnel ou intégral) peut être un facteur de (log n) plus grand que le coût requis pour utiliser le routage dynamique.Dans le passé, la question suivante a été posée: étant donné un polytope de demande de trafic avec incertitude, est-il en théorie facile de calculer un routage complètement dynamique (système de routage qui dépend du trafic de la matrice courante)? Récemment, il a été prouvé que ce problème est en général difficile: il est co-N P-difficile de décider si un réseau donné avec des capacités connue est capable de transporter chaque matrice de trafic dans le polytope, lorsque le routage est dynamique. En outre, pour des raisons techniques, il est très difficile de mettre en oeuvre ce type de routage. Par conséquent, il est intéressant de considérer un intermédiaire entre le routage stable et robuste et le routage entièrement dynamique. Au lieu de calculer une solution robuste, il est possible de partitionner le polytope de la demande de trafic en plusieurs sous-ensembles, et de calculer un routage robuste pour chacun d'eux. On peut par exemple faire ce partitionnement à l'aide d'un hyperplan. On suppose que la direction d'un hyperplan divisant le polytope des matrices de trafic est connue, mais sa position est sujette à optimisation. Par exemple, une quantité de trafic généré entre une paire de noeuds, ou une quantité de trafic généré par un noeud spécifique peuvent être pris comme une direction de l'hyperplan. Dans une telle situation, une position d'un seuil qui déclenche des changements dans le routage est optimisée. En d'autres termes, deux stratégies de routage sont spécifiées, la première est utilisée si le volume du trafic, qui a été défini comme une direction de l'hyperplan, est inférieur au seuil, sinon la seconde stratégie de routage est utilisée. Une autre possibilité est de considérer le temps comme une direction de l'hyperplan. Dans ce cas, le temps est représenté par une dimension supplémentaire de l'ensemble de l'incertitude, et le moment où le routage doit être changé est optimisé. En plus du routage robuste stable et le routage dynamique, nous étudions également le routage sans partage. Dans ce mode de routage, les ressources sont réservées par demandes et aucune mutualisation entre les demandes de trafic n'est tolérée. Parmi les différents modes de routage et les différents problèmes sous-jacents, nous avons identifié lesquels de ces problèmes étaient polynomiaux, et comment ils peuvent être résolus avec succès. Nous distinguons par exemple le cas où les capacités sont réservées une seule fois pour l'ensemble du polytope de trafic (i.e., même si le routage change, les capacités réservées ne changent pas). Nous étudions également le cas où les capacités peuvent être re-réservées à chaque modification de routage. Toutes les variantes sont étudiées et comparées.

  The whole thesis is divided into two parts. The first part deals with the complexity of resilient network optimization problems, while the second part is devoted to the polyhedral traffic demand matrix uncertainty model.The first part of the thesis is organized as follows. In Chapter 2 notation is introduced.After that, in Chapter 3 optimization models related to path protection (hot-standby, HS, and path diversity, PD) are discussed. With HS, i.e., 1+1 protection, each demand is realized by means of a single working path which is protected by a dedicated single path. PD can be considered as a generalization of HS. It protects traffic against failing network components by over-provisioning, i.e., by routing more traffic than specified by the demand value in the failure-less state, and ensuring that at least the requested volume survives in each failure state in the considered failure scenario without rerouting any flow.

mially solvable modifications: simplified volume oriented routing and general volume oriented routing), is presented in the thesis. It takes advantage of the simplicity of robust stable routing and the efficiency of dynamic routing. Moreover, it does not involve abrupt changes in network flows. In Chapters 4 and 5, analogous models related to various variants of path restoration mechanisms are considered. Path restoration (PR) are active mechanisms in the sense that they restore the working flows affected by a failure. Certainly, for achieving that, extra protection capacity is required as compared to capacity supporting normal state only. Still, the amount of extra capacity is typically much smaller for PR than for PP because, as a rule, with PR protection capacity is shared by different demands and different failure situations.

  However, it can be applied only to a subset of basic problems presented in a special way. The whole Section 8.3 is devoted to dynamic routing. It is shown when partitioning is useful for this problem, and how it can be solved. The major interest is given to a special polynomial case of the problem, i.e., the traffic demand polytope is defined as a convex hull of a given set of traffic matrices. Finally, Section 8.4 consists of implementation details that accelerate the presented algorithms. It deals with all the problems presented before, and contains enhancements that do not change the theoretical complexity of the presented algorithms but can accelerate actual implementations.In Chapter 9, volume oriented strategies are presented. First, in Section 9.1, unrestricted volume oriented routing is discussed. This novel routing mechanism involves a division of a traffic demand polytope. However, in this case, only a part of flow that exceeds a threshold is routed using a different set of paths. The complexity of this approach is N P-hard in

8.1 the first partitioning problem is discussed. Its complexity is considered, and some of its special features are outlined. Moreover, an algorithm that can solve it is presented. Another (faster) algorithm is presented in Section 8.2.

general. However, it encompasses some special cases that are polynomial even when more that one hyperplane is taken into account. Those special cases, namely simplified volume oriented routing and general volume oriented routing, are presented in Sections 9.2 and 9.3, respectively.

  P = d∈D P d , where P d is the set of candidate paths for demand d ∈ D. It is assumed that the paths are elementary (do not contain loops) so, for each demand d ∈ D, set P d is a subset of the set of all elementary paths from u d to w d , and each path p ∈ P can be identified with the set of the links it traverses, hence p ⊆ A. The subset of paths in P d that survive in state s ∈ S is denoted by P s d , and the subset of paths in P d that contain link a ∈ A by P ad .

Further, S p = {s ∈ S : p ∩ s = ∅}, (S p ⊆ S) denotes the set of all states s ∈ S in which path p ∈ P is available, and Sp = S \S p is the set of all states s ∈ S in which path p ∈ P fails.

  ) = a∈p ξ a , the decomposed problem for each particular demand d ∈ D is of the following form.

	x p	h d ,	d ∈ D, s ∈ S,	(3.2b)
	p∈P s d
	x	0.		(3.2c)
	Problem PD was studied by Koster et al. [41], Wessäly et al. [66], Orlowski and Pióro [51],
	and in a slightly different setting by Dahl and Stoer [21]. Observe that formulation (3.2)
	specifies a linear programming problem, and as such can be effectively treated by LP solvers
	but only when the predefined sets of candidate paths P d , d ∈ D, are of reasonable size.
	Since in general the proper sets of candidate paths are not known in advance, formally all
	possible (elementary) paths in the network have to be considered. Consequently, formulation
	(3.2) is not compact since in general the number of all elementary paths in a graph increase
	exponentially with the number of nodes. Thus, to solve problem (3.2), column generation has
	to be used (see for example [1]) to achieve the proper sets of candidate paths that contain
	all paths required in an optimal solution.
	Path generation issues for problem (3.2) are discussed in [51]. Path generation is known
	to be polynomial for the case when the failure scenario S contains only single-link failures,
	i.e., when S is composed of singletons: S ⊆ {{a} : a ∈ A}. In fact, path generation for
	problem (3.2) remains polynomial even if single-node failures on top of single-link failures
	are also considered. However, in the case of a general multiple-link failure scenario, path
	generation for PD becomes N P-hard [50].
	Due to the linearity of the objective function, problem (3.2) decomposes into |D| in-
	dependent sub-problems, one for each demand d ∈ D. Without loss of generality in each
	such sub-problem h d = h can be assumed. Then, using notations P = P d , P s = P s d and
	ξ p

  G is modeled by means of a directed network N = (V, A) depicted in Figure 3.3. The set of nodes V = {v 0 , v 1 , . . . , v N } consists of N + 1 elements: all vertices from graph G plus the additional node v 0 . The set of links A = {t 1 , t 2 , . . . , t N , b 1 , b 2 , . . . , b N } is composed of 2 • N elements. For each n = 1, 2, . . . , N , links t n (top link number n) and b n (bottom link number n) connect nodes v n-1 and v n . The unit cost ξ a of each link is equal to 1. The (single) demand is defined from node v 0 to node v N , with the requested demand volume equal to 1. The set P of paths consists of all elementary paths from node v 0 to node v N in network N . The set S of failure states consists of N states, S = {s 1 , s 2 , . . . , s N }. Each state s n ∈ S encompasses simultaneous failures of the bottom link b n , and of every top link t m such that in graph G vertices v n and v m are linked by an edge: s n = {b n } ∪ {t m : v m and v n are adjacent in G}. For example, thick links in Figure 3.3 represent the links that fail in state s n under assumption that vertex v n in graph G is adjacent to vertex v 2 and to vertex v n-1 , and to no other vertices.

	The instance P DD G of Path Diversity Design (i.e., of problem PDD (3.3)) corre-
	sponding to F C Lemma 3.2.2. The optimal objective (3.5a) of F C G is equal to K (i.e., χ f (G) = K) if and only if the optimal objective (3.3a) of P DD
	family of all independent sets of G. The resulting instance of Fractional Coloring (i.e.,
	of problem FGC (3.5)) will be denoted by F C G .

2 , . . . , v N } of N vertices. Let E be the G is equal to N • K.

  where z e(p) = x p , p ∈ Q. Each set e(p) ∈ I is defined by the condition: vertex v n belongs to e(p) if and only if path p survives in failure state s n . Each e(p) is an independent set since if v n , v m ∈ e(p) and v n and v m are adjacent in G then path p cannot survive in both states s n and s m because link t n fails in state s m and link b n fails in state s n . Moreover, I vn = {e(p) : p ∈ Q sn } and hence e∈I vn z e = e(p)∈Q sn z e(p) = p∈Q sn x p 1, so the inequalities (3.5b) are fulfilled. Certainly,

Table 4 .

 4 in this case formulation (4.1) becomes a compact linear programming problem, and as such can be solved in time which grows polynomially with the size of the problem (see[START_REF] Khachiyan | A polynomial algorithm for linear programming[END_REF]). On the other hand, when LP with all possible (elementary) path-pairs is considered (variant 1b, 2b) then formulation (4.1) becomes non-compact as the number of path-pairs grows

		single failures multiple failures
	LP, all paths	N PH 1	N PH 2
	D = 1 IP, predefined paths	P 3	N PH 4
	LP, all paths	N PH 5	N PH 5
	D > 1 IP, predefined paths	N PH 6	N PH 5

1: Complexity overview (N PH: N P-hard, P: polynomial) exponentially with the size of the graph. As demonstrated later in this section, this variant is N P-hard, no matter what Criteria 3 and 4 are. The second observation concerns variants assuming Criterion 1a (IP). For the IP case the complexity is already determined by 2a, no matter what variants of Criteria 3 and 4 are considered. When variant 2a is N P-hard, variant 2b is also (automatically) N P-hard. The case when variant 1a can be solved in polynomial time is a bit more tricky. This is in fact variant 1a, 3a, 4a, namely: |s| = 1, for all s ∈ S \ O, D = {d} and x dr ∈ {0, 1}, r ∈ T d .

Consider Criterion 2a, i.e., that T d are given in advance. Then the optimal solution can be found in polynomial time by examining all pairs in T d , and selecting the shortest one. Now consider the second variant (2b). In this case the problem is just to find a shortest pair of disjoint paths in the network, and allocate the whole demand volume h d to this pair. This can be efficiently solved using Suurballe algorithm

[START_REF] Suurballe | Disjoint paths in a network[END_REF]

. Hence, both variants 2a and 2b can be solved in polynomial time.

Thus, although according to Criteria 1-4 there are 16 variants of problem (4.1), because of the above remarks, this number can be reduced to 8. These 8 variants are summarized in Table

4

.1, where Criterion 2b is assumed for LP, and Criterion 2a is assumed for IP.

Table 4 .

 4 2: Possible primary/backup path groups when F G has no solution

	Primary paths	Backup paths

Table 4 .

 4 3: Arc-disjoint primary path group pairs and their possible backup path groups

	Primary path 1 Primary path 2	Backup path 1	Backup path 2

Table 4 . 4 :

 44 Overview of the complexity of approximation schemes

		single failures	multiple failures
	LP, all paths D = 1 IP, predefined paths	< 4 3 -approximation is N PH any approximation is N PH P any approximation is N PH
	LP, all paths D > 1 IP, predefined paths < < 4 3 -approximation is N PH any approximation is N PH

  c a }. Constraint (4.4d) assures that not more than c a paths utilize an arc a. Notice that constants c a can be consider as capacities of arc, and a directed graph with capacities is called a network. Finally, costs of arcs are functions of f a .

	n' h 1	n'' g 1
	a ∈ A Problem (4.4) has to satisfy Kirchhoff's law (4.4b, 4.4c), but k units of flow, instead of (4.4d) just 2, have to leave u. Notice that constraints (4.4d) can be directly integrated in the objective function by t n' h 2 n'' g 2 defining ξ s n' h |H| n'' g |G|

a (f a ) in a suitable way, i.e., by setting ξ a (f a ) = ∞ if f a / ∈ {0, 1, . . . , c a }. However, it is kept for sake of clearness.

The objective function considered here is quite general. It is generally neither convex nor concave. Readers can refer to, for example,

[START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF]

for work on convex flow problems and to,

Table 6 .

 6

			1: General overview of complexity
		single failures (SF)	multiple failures (MF)
		non-bifurcated bifurcated D = 1 D > 1	non-bifurcated bifurcated D = 1 D > 1
	HS	-	P	-	-	N PH	-
	PD	P	P	-	N PH	N PH	-
	FI-nSR	N PH	P	N PH	N PH	N PH N PH
	FI-SR	N PH	P	N PH	N PH	N PH N PH
	FD-nSR	P	P	N PH	N PH	N PH N PH
	FD-SR	?	P	N PH	?	N PH N PH
	All other design problems in the case of the bifurcated routing of demands are N P-hard,

and therefore they cannot have a compact formulation. Still, when the problem is N P-hard then its non-compact LP formulation (in the link-path notation) exists. Certainly, when using such non-compact LP formulations, for exact solutions an appropriate candidate path lists P d , d ∈ D (or path-pair lists T d , d ∈ D, or path-sequences lists W d , d ∈ D) are needed in order to achieve the true optimum of the problem. As such lists are not known in advance they

  3. Both Corollaries 8.2.3 and 8.2.4 can be rewritten taking into account t max ij . Notice that max t∈A t ij is denoted by t max ij (A). For any β ∈]β 1 , β 2 [ maximum values of t max

	Corollary 8.2.5. ij	= t max ij (L(D, β)) satisfies an
	inequality:

  |V|(|V|-1) D β . The solution Figure 9.1: Graph proving that a decision version of VO Routing is co-N P-complete.considered above is not feasible if and only if there exists at least one β ∈ {-1, 1} |V|(|V|-1)

				t 1
	s	u	t	t	2
		d
				t N

Lemma 9.1.1.

  The given solution to V O H is feasible if and only if the answer to SS H is NO.

Table 10 .

 10 Although the partitioning can be meaningless for Robust Routing when minimizing the congestion, it is profitable when minimizing routing cost (see further experiments in Table10.3), especially when appropriate conditions occur, i.e., networks are congested.

			1: Test cases
	# topology |V| |A| dim. D variant
	1			3 pts.
	2			10 pts.
	3		12	hose
	4			B-S 10%
	5	atlanta 15 44	B-S 20%
	6			3 pts.
	7			10 pts.
	8		30	hose
	9			B-S 10%
				B-S 20%
				3 pts.
				10 pts.
			20	hose
				B-S 10%
		f rance	25 90	B-S 20%
				3 pts.
				10 pts.
			56	hose
				B-S 10%
				B-S 20%
			90	3 pts.
		cost266	37 114	10 pts.
			156	3 pts.
				10 pts.

mand polytope for No Sharing, and questions the significance of introducing partitioning for Robust Routing (results for Dynamic Routing are a lower bound for Identical Reservation for Robust Routing).

Table 10 . 3 .

 103 .1. The following five columns present results obtained for five different variants of the problem, i.e., Identical Reservation and Different Reservation both for Robust Routing and No Sharing, and Different Reservation for Dynamic Routing. Assume that u is a cost of an optimal solution to one of the basic problems without any partitioning, and v is a cost of an optimal solution to the same problem with partitioning (either Identical Reservation or Different Reservation). In thetable gains are presented. They are understood as u-v u • 100%. Another table, namely Table 10.4, presents running times of the presented algorithms that solve various partitioning problems. Its construction is similar to the construction of All versions of Different Reservation were solved by means of the method of Section 7.3.1. Identical Reservation for Robust Routing was solved using the double binary search algorithm of Section 8.1, while Identical Reservation for No Sharing was solved using both the double binary search method and the algorithm of Section 8.2. That is why the execution times for this version of the problem are presented as: a/b, where a is time used by the double binary search algorithm, and b is time used by the algorithm of Section 8.2. Note that the algorithm of Section 8.2 cannot be used for the hose model polytopes.

	Table 10.3: Efficiency of the partitioning algorithms-gain [%]
		Robust	No sharing	Dynamic
	# Different Identical Different Identical Different
	1	9.7	5.6	48.3	44.3	1.3
	2	23.6	15.9	52.4	44.8	0.8
	3	19.4	15.9	47.0	44.8	-
	6	15.4	12.8	50.0	46.0	6.2
	7	10.4	0.8	52.5	47.2	8.6
	8	4.6	2.2 -2.5	29.2	27.4	-
	11	11.5	7.9	52.0	45.7	3.2
	12	2.8	1.1	43.1	40.3	1.5
	13	3.8	0.4	41.5	40.0	-
	16	15.5	12.7	50.3	46.3	8.2
	17	15.3	8.2	41.3	39.2	7.3
	18	0.0	0.0	31.2	30.2	-
	21	10.8	5.4	54.8	47.7	4.7
	22	1.1	0.2-0.7	54.5	51.2	2.1
	23	7.5	1.1	66.6	61.1	7.5
	24	2.9	0.0-2.9	53.4	49.5	4.2

The 9000-second time limit has been hit three times. Identical Reservation for Robust Routing has not been solved to optimality for the test cases #8, #22, and #24. In those cases, the gains are presented as: ab, where a is the gain for the best solution found, and b is the upper bound. In other words, the optimal gain belongs to

[a, b]

. Note that time limits were not used for Dynamic Routing.

Table 10 .

 10 4: Running times of the partitioning algorithms[s] It is also worth to notice that the running times of the double binary search algorithm presented in Section 8.1 are not significantly larger than the running times of the polynomial algorithm of Section 8.2 (see Table10.4, Identical Reservation for No Sharing). It justifies the claim that the double binary search algorithm, although non-polynomial, is practical, and can be applied even to medium size networks.

		Robust	No sharing	Dynamic
	# Different Identical Different	Identical	Different
	1	0.4	5.1	0.3	0.5 / 0.2	1.3
	2	0.5	7.0	0.3	0.6 / 0.3	19.4
	3	0.6	8.9	0.4	0.7	-
	6	1.3	20.4	0.8	2.8 / 1.0	6.2
	7	6.2	302.8	0.8	3.4 / 1.5	45.6
	8	31.8	9000.0	1.5	3.6	-
	11	4.3	31.1	1.4	4.0 / 2.0	5.3
	12	9.8	180.4	2.9	5.6 / 3.7	26.0
	13	19.3	1132.9	1.7	2.8	-
	16	13.3	111.6	10.2	17.8 / 8.6	26.7
	17	98.1	2873.3	9.3	17.2 / 11.0	983.0
	18	3016.4	3016.4	10.2	18.8	-
	21	46.1	354.0	13.7	64.4 / 45.3	106.4
	22	517.7	9000.0	39.5	127.7 / 79.5	6808.9
	23	148.3	1771.1	37.3	124.7 / 132.0	669.1
	24	4024.3	9000.0	137.4	594.7 / 350.7 12019.3

  The reason is that both SVO Routing and GVO Routing require lower bounds on demands' volumes in order to work appropriately.The result of this part of the experiments are presented in Table10.5. It consists of nine columns. The first contains identification numbers of test cases, while the rest show execution times and costs for the following cases.

Robust : strategy described in Section 7.1.1. It is the simplest routing strategy and an upper bound on costs of all other strategies. SVO Routing : strategy presented in Section 9.2.

GVO Routing : strategy presented in Section 9.3.

It is clearly seen that both volume oriented strategies are efficient, and they outperform a corresponding partitioning strategy, i.e., Identical Reservation for Robust Routing.

However, they take advantage of a special structure of traffic demand polytopes (lack of non-dominated traffic demand matrices with zero components), and they cannot outperform the partitioning strategies in general test cases. It is also worth to notice that GVO Routing provides better results than SVO Routing only in five cases, and only in two of them (#6 and #17) the difference is not negligible.

Table 10 .

 10 In the thesis two different partitioning strategies were presented, i.e., Identical Reservation and Different Reservation. They were applied to three different basic models, i.e., Robust Routing, No Sharing, and Dynamic Routing. Moreover, three different volume oriented strategies were presented, i.e., VO Routing, SVO Routing, and GVO Routing. They were applied to one basic model, i.e., Robust Routing.

	5: Efficiency and running times of the volume oriented strategies
	Robust		SVO Routing	GVO Routing
	# cost time[s] cost gain[%] time[s]	cost	gain[%] time[s]
	1 723.0	0.1	717.5	0.8	0.4	717.5	0.8	0.2
	2 447.5	0.2	332.0	25.8	0.4	332.0	25.8	0.3
	3 442.3	0.3	380.3	14.0	0.5	380.3	14.0	0.5
	4 361.1	0.1	287.9	20.3	0.2	287.9	20.3	0.2
	5 343.0	0.2	291.8	14.9	0.3	291.8	14.9	0.5
	6 410.7	0.6	395.2	3.8	0.7	393.5	4.2	0.9
	7 448.8	0.7	420.5	6.3	1.6	420.4	6.3	2.5
	8 443.5	3.1	402.2	9.3	7.0	402.1	9.3	9.9
	9 625.7	1.0	350.6	44.0	6.1	350.6	44.0	10.5
	10 506.1	1.4	448.0	11.5	11.0	448.0	11.5	25.9
	11 332.4	0.6	317.8	4.4	0.7	317.8	4.4	0.8
	12 353.6	0.8	324.1	8.3	0.8	324.1	8.3	1.6
	13 357.0	1.6	328.9	7.9	1.9	328.9	7.9	3.0
	14 394.5	1.4	371.5	5.8	2.7	371.5	5.8	4.3
	15 483.6	1.7	477.9	1.2	4.9	477.9	1.2	8.8
	16 652.3	3.6	619.6	5.0	3.7	619.3	5.0	3.4
	17 695.4	8.6	574.2	17.4	22.7	565.1	18.7	37.3
	18 649.2 495.0 525.4	19.1	1336.4 525.4	19.1	3401.0
	19 854.5	33.2	802.8	6.1	177.4	802.8	6.1	765.1
	20 518.7	11.5	516.3	0.0	605.7	516.3	0.0	7200.0

Acknowledgement

First of all, I would like to thank my supervisors Michał Pióro and Walid Ben-Ameur for suggesting unchallenged problems that are solved in this thesis and for their help in approaching those problems. Secondly, I would like to thank Artur Tomaszewski without whom one of the problems presented in the thesis would still be unsolved. Many thanks to Mateusz Dzida and Michał Zagożdżon for their time and help they provided in the initial stages of my PhD studies, and to Mariusz Mycek for his help in the final stages of my studies. Finally, good words to Fernando Solano for upgrading some graphics in the thesis, and to Susann Schrenk for her help with an extended abstract.

restoration with Stub-Release; FGC -Fractional Graph Coloring; FI -Failure-Independent restoration; FI-nSR -Failure-Independent restoration without Stub-Release; FI-SR -Failure-Independent restoration with Stub-Release; GVO -General Volume Oriented routing; HS -Hot-Standby; IP -Internet Protocol, or Integer Programming; IR/NS -Identical Reservation for No Sharing; IR/RR -Identical Reservation for Robust Routing; LHSP -Left Hand Side Polytope; LP -Linear Programming; MIP -Mixed-Integer Programming;

The lists of optimal paths obtained for the bifurcated versions of the considered optimization problems can then be used for solving their non-bifurcated counterparts by means of MIP solvers to maximally limit the number of binary variables used in the branch-andbound process. Certainly, this would be an approximate approach as the optimal paths for the bifurcated problems do not necessarily contain all optimal paths for the non-bifurcated case. To solve the problems exactly, it would actually be required to use branch-and-bound schemes combined with pricing of variables.

The research field presented in the first part of the thesis still contains some interesting problems to solve. The computational complexity of FD-SR with bifurcated flows has been proved neither for the single failure case nor for the multiple failure case. What is more, N P-hardness of FI-nSR and FI-SR with bifurcated flows has been proved by reducing the 2Div-Path problem to it. Notice that 2Div-Path is N P-hard only in directed graphs. Thus, the complexity of both FI-nSR and FI-SR in undirected graphs remains unknown.

Finally, the field contains the enormous number of different special cases and generalizations that can change the complexity of base problems.

Part II

Polyhedral model

Chapter 8

Algorithms

In this chapter algorithms solving the previously presented partitioning problems are discussed. In Section 8.1 an algorithm solving Identical Reservation is presented. Another (faster) algorithm is described in Section 8.2. However, it can be applied only to Identical Reservation for No Sharing when a polytope is defined as a convex hull of a given set of traffic matrices. The whole Section 8.3 is devoted to Dynamic Routing. Finally, Section 8.4 consists of implementation details that accelerate the presented algorithms.

Double binary search algorithm

In this section an algorithm that solves Identical Reservation is presented. It can successfully deal with both viable versions of the problem (Robust Routing and No Sharing) but for the sake of simplicity it concentrates only on the former one. As mentioned earlier Identical Reservation for Dynamic Routing is meaningless.

Computational complexity

The computational complexity of this problem still remains an open question. However, some results dealing with the complexity of its approximation schemes have been already published.

In [START_REF] Ben-Ameur | Between fully dynamic routing and robust stable routing[END_REF] a polynomial time 2-approximation algorithm for Identical Reservation for Robust Routing was presented. The algorithm works as follows. Let β ⋆ be the optimal solution to Different Reservation, f ⋆ the optimal reservation vector used for L(D, β ⋆ ) and f ⋆ the optimal reservation vector used for R(D, β ⋆ ). One can obviously build a new reservation vector defined by the componentwise maximum of f ⋆ and f ⋆ . This vector will allow to carry traffic for each t ∈ D (keep the routing schemes obtained when Different Reservation is solved). It is clear that the cost of this new vector is less than twice the cost of the optimal solution to Identical Reservation.

Proof. Take any point t ∈ D β . As it belongs to D, it can be expressed as a convex combination of extreme points of D. D mid does not contain any extreme points of D, so all of them have to belong either to D lef t or to D right . It means that a convex combination of only those extreme points that belong to D lef t can be calculated, and a point in D lef t (together with its weight) can be obtained. The same operation can be performed on D right . The considered matrix t will be a convex combination of those two points. Obviously, those two points can be connected by a line that is contained in D. What is more, this line also contains one point from D β 1 (denoted by t β 1 ) and one point from D β 2 (denoted by t β 2 ). Certainly, t = λt β 1 + (1λ)t β 2 , and we can take t ′ = t β 1 and t ′′ = t β 2 .

It is possible to think about β 2 as a variable, and write the following lemma.

Lemma 8.2.2. For any

What is more, for those β ′ and β ′ 2 the fraction

Note that D lef t = L(D, β 1 ) and D lef t ⊂ L(D, β 2 ). Therefore, the previous lemma can be extended to also cover points that belong to D lef t .

Corollary 8.2.3. For any

Obviously, it works also in the opposite direction.

Corollary 8.2.4. For any

Chapter 9

Volume oriented strategies

The major problem with the partitioning approaches presented in the previous chapters is that a routing can significantly differ between subsets, and implementing those changes can result in serious traffic fluctuations. Therefore, it is worth considering something that will make the routing changes less abrupt. Another drawback of the partitioning strategies is their centralized nature. They require a central node that has complete and up-to-date knowledge about all demands in a network. Moreover, this central node has to immediately inform all other nodes about routings they are supposed to execute. Those two disadvantages are addressed in this chapter by introducing a novel routing paradigm called the volume oriented strategy.

First, in Section 9.1, unrestricted volume oriented routing is discussed. The complexity of this approach is N P-hard in general. However, it encompasses some special cases that are polynomial even when more that one hyperplane is taken into account. Those special cases, namely simplified volume oriented routing and general volume oriented routing, are presented in Sections 9.2 and 9.3, respectively.

Volume oriented routing

The first strategy, denoted by VO Routing, is an extension of Robust Routing in which demands can be routed differently depending on their actual volumes. In this case the solution consists of two different routings for each demand, and a set of thresholds. If a volume of a demand is smaller than a corresponding threshold the whole demand is routed using the first routing. If the volume is greater than the threshold a part of the demand equal to the threshold is sent using the first routing, while the rest of the demand uses the second routing. Note that the approach can be considered as a modification of Identical Reservation presented in previous sections. Instead of changing the routing for the whole demand after reaching the threshold only the amount of traffic exceeding the threshold is routed differently.

Chapter 10

Numerical results

In this chapter numerical results are presented. They show applicability of the algorithms and strategies presented in the second part of the thesis. The algorithms were implemented using Visual C++ and tested on a one core Intel 2.4 GHz CPU with 3.25 GB RAM using a linear programming solver CPLEX 11.0 [START_REF] Ilog | CPLEX 11.0 User's Manual[END_REF].

Test cases

Example cases were built using real world networks available in SNDlib [START_REF] Orlowski | SNDlib 1.0-Survivable Network Design Library[END_REF]. The following topologies were used: atlanta, france, and cost266. All were tested using two different set of active nodes V act , and three to five different traffic demand polytopes defined for each of the set. The first polytope for each set satisfied restrictions of the hose model presented in [START_REF] Duffield | A flexible model for resource management in virtual private networks[END_REF],

and described in Section 7.2.1. The sets of active nodes, and the bounds for incoming and outgoing traffic, were chosen at random. In the first part of the experiments standard hose model polytopes were used, while in the second part a general hose model was considered.

In the latter case the minimum traffic between a pair of node i and j, where i, j ∈ V act , was set to min(A i ,B j ) 2•|V act | , while the maximum traffic was set to min(A i ,B j )

2

, where A i and B j are defined as in Section 7.2.1. The last two polytopes were built using the B-S polytope model presented in Section 7.2.2. The bounds were set at random, while k was set to 10% or 20% of its maximum value, i.e., 0.1 or 0.2 times |V act | • (|V act | -1), depending on the test case.

Note that B-S model polytopes were used only in the second part of the experiments. The resulting test cases can be seen in Table 10.1. It consists of six columns.

# : identification number of a test case.

topology : name of the topology in SNDLib.

V : number of nodes in a network.

A : number of undirected links in a network. Note that neither the full hose model polytopes nor the B-S model polytopes were considered for cost266 topology. The reason is that the complexity of those polytopes is enormous, and it was impossible to solve the simplest Robust Routing (without any partitioning)

for them in reasonable time. Note that in the thesis the hose models with bounds on both incoming and outgoing traffic for each active node are considered (in [START_REF] Ben-Ameur | New economical virtual private networks[END_REF][START_REF] Ben-Ameur | Routing of uncertain traffic demands[END_REF] only bounds on outgoing traffic were considered). The number of extreme points of those polytopes was also the reason not to consider them for Dynamic Routing.

Partitioning strategies

In