Michal Pióro
email: m.pioro@tele.pw.edu.pl

Micha� L Pióro

Ilya Kalesnikau

Michael Poss
email: michael.poss@lirmm.fr

An optimization model for quadratic flow thinning -a traffic protection mechanism for FSO networks

Keywords: Resilient networks, free space optics, variable link capacity, linear and mixed-integer programming, multicommodity flows, quadratic and affine routing, path generation

HAL is

Introduction

Flow thinning (FT) is an active traffic protection mechanism for communication networks whose links experience fluctuations in available capacity. Since in general the links composing such networks do not achieve their nominal (maximum) capacity simultaneously, in a typical network state only some links are fully available while on each of the remaining links only a fraction of its maximum capacity is usable. The considered fluctuations are common in wireless networks, in particular in Wireless Mesh Networks (WMN). Thus, an interesting application of FT are WMNs carrying IP packet traffic over the MPLS tunnels realized along the free space optical (FSO) links [START_REF] Chan | Free-space optical communications[END_REF]. The FSO links are set up by means of laser beams between transponders in the line of sight, commonly placed on top of high buildings in a city [START_REF] Li | Optimization of free space optical wireless network for cellular backhauling[END_REF].

The concept of FT was introduced in [START_REF] Pióro | Optimizing flow thinning protection in multicommodity networks with variable links capacity[END_REF]. FT copes with the phenomenon of variable link capacity by using logical tunnels for the end-to-end traffic demands. Each end-to-end traffic demand is assigned a set of such logical tunnels whose total capacity is dedicated to carry the demand's traffic. The nominal (i.e., maximum) capacity of the tunnels, supported by the nominal (maximum) link capacity, is subject to state-dependent thinning to account for variable capacity of the links, fluctuating below the maximum. The current capacity of the tunnels is controlled at their source nodes on the basis of the knowledge of the current link availability state. In consequence, the capacity available on the tunnels is also fluctuating below their nominal levels, and hence the instantaneous traffic sent between the demand's end nodes must accommodate to the current total capacity available on its dedicated tunnels.

In the paper we deal with a (potentially) practical version of FT where the capacity of each tunnel is thinned according to a tunnel-dependent quadratic function whose arguments are link availability coefficients (for a given link such a coefficient is the fraction of the maximal link capacity available in a given link availability state), and not in a arbitrary way as in the original FT mechanism. We consider a general form of the quadratic flow thinning formula (and call the resulting mechanism Quadratic Flow Thinning -QFT), and develop a network dimensioning optimization model for QFT (and, for that matter, its variants, including the so called Affine Flow Thinning (AFT) considered in [START_REF] Pióro | Optimizing flow thinning protection in multicommodity networks with variable links capacity[END_REF][START_REF] Pióro | Path generation for affine flow thinning[END_REF][START_REF] Pióro | An optimization model for affine flow thinning -a traffic protection mechanism for FSO networks[END_REF]) -a fairly complicated issue not yet studied. As the optimization process is based on the path generation approach we derive a relevant pricing problem and present a numerical study illustrating efficiency of the resulting optimization algorithm as such, and effectiveness, in terms of the network cost, of QFT as compared with effectiveness of FT and a well known benchmark protection mechanism called Global Rerouting (called also Unrestricted Reconfiguration, see [START_REF] Orlowski | Complexity of column generation in network design with pathbased survivability mechanisms[END_REF][START_REF] Pióro | Routing, Flow, and Capacity Design in Communication and Computer Networks[END_REF]). All the derivations and results of the paper related to QFT are original and have not been published before.

We mention here that FT is a generalization of the Demand-Wise Shared Protection (DWSP) strategy [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] devised for multiple total link failures (multiple total link failures are sometimes called shared risk link groups -SRLG). In fact, FT mechanism is a non-trivial extension of DWSP since thinning becomes trivial in the SRLG case: the affected tunnels are entirely lost and non-affected tunnels are preserved. Since the network dimensioning problem for DWSP is N P-hard (as shown in [START_REF] Tomaszewski | On the complexity of resilient network design[END_REF]), the problem is N P-hard also for FT, and hence, most likely, for QFT.

The paper is organized as follows. We start with introducing basic notation in Section 2, followed by Section 3 where a non-compact linear programming formulation of the network dimensioning problem with FT and of its dual are presented, together with a solution algorithm based on path-generation. In Section 4, we reformulate the dimensioning problem for quadratic flow thinning (the variant of FT crucial to this paper) and discuss important variants of quadratic flow thinning dealt with in the paper, including affine flow thinning. Then, in Section 5, which is crucial to the paper's considerations, we derive the pricing problems (used for path generation) for quadratic flow thinning and its variants (some derivations related to Section 5 are moved to Appendix A). Next, in Section 6, we present and discuss the results of an extensive numerical study illustrating the efficiency of the optimization algorithms and effectiveness of various variants of flow thinning. Finally, we give concluding remarks and comment on future work in Section 7.

Notation

Although the considerations of the paper are valid for both directed and undirected network graphs, for the space saving reason the presented optimization model will assume the undirected case. Thus, the network graph G = (V, E) is composed of the set of nodes V and the set of links E, where each (undirect) link represents an undirected pair {v, w} of nodes for some v, w ∈ V, v � = w.

The maximal (referred to as nominal in the following) capacity of link e ∈ E is denoted by y 0 e and its unit capacity cost by ξ(e). It follows that the network cost (to be minimized) is expressed as F = � e∈E ξ(e)y 0 e . Yet, as in our network model the capacity of links can vary, typically not all links reach their nominal capacity simultaneously. Thus, at any time instant, nominal link capacities y 0 e , e ∈ E, are achieved only for a subset of links, while for the remaining links their capacity is reduced with respect to the nominal value. To handle this, we consider a set of link availability states S. Each state s ∈ S is described by link availability coefficients α(e, s) (0 ≤ α(e, s) ≤ 1), e ∈ E. By definition, the capacity of link e available in state s is equal to α(e, s)y 0 e . In the following we will also use the notion of link failure coefficients defined as β(e, s) := 1α(e, s). The subset of states s in S for which a particular link e ∈ E is not fully available (α(e, s) < 1) will be denoted by S(e); symmetrically, the subset of links in E that are not fully available in state s ∈ S will be denoted by E(s). The nominal link capacities, described by the vector y 0 := (y 0 e , e ∈ E), are optimization variables. In general, not all nominal path-flows x 0 dp , d ∈ D, p ∈ P(d), can be realized when the network is in a state s ∈ S, since for some links the available capacity α(e, s)y 0 e can be decreased with respect to their nominal link capacity y 0 e . To account for that, the nominal flows are thinned (decreased) to accommodate to the reduced link capacity. Still, the thinned flows must be sufficient to carry the demands h(d, s), d ∈ D. The thinned nominal pathflows for state s ∈ S are denoted by x s dp . These flows are reserved on the allowable paths for the duration of the state. As only thinning of nominal flows is allowed, the following inequalities must hold:

x s dp ≤ x 0 dp , d ∈ D, p ∈ P(d), s ∈ S.
In the following the path-flow vectors x 0 := (x 0 dp , d ∈ D, p ∈ P(d)) and x s := (x s dp , d ∈ D, p ∈ P(d)), s ∈ S, will be treated, together with the capacity vector y 0 , as optimization variables. For specifying the optimization variables we will use the following abbreviations: R -the set of all real numbers (for continuous variables unconstrained in sign), R + -the set of non-negative real numbers (for non-negative continuous variables), B -the two-element set {0, 1} (for binary variables).

FTOP -flow thinning optimization problem

Formulation of FTOP and its dual

For a given set of allowable paths P = � d∈D P(d), problem FTOP is denoted by P(P). It is represented by the non-compact link-path linear programming (LP) formulation (1) involving variables y 0 , x 0 , and x s (s ∈ S). In the following formulation the quantities indicated in the square brackets are dual variables that will be used in [START_REF] Li | Optimization of free space optical wireless network for cellular backhauling[END_REF].

Problem P(P): Objective (1a) minimizes the cost of links. The first capacity constraint (1b) makes sure that the nominal link loads do not exceed the nominal link capacities. Next, the demand constraint (1c) assures that in each state s ∈ S, the thinned nominal flows are sufficient to realize the volume of each demand d ∈ D assumed for this state. Then, the second capacity constraint (1d) ensures that the capacity of each link e ∈ E available in each state s ∈ S(e) is not exceeded (recall that S(e) denotes the set of states in which α(e, s) < 1). Finally, inequalities (1e) ensure that in case of link failures the nominal flows are actually thinned.

F (P) = min � e∈E ξ(e)y 0 e (1a) [π 0 e ≥ 0] � d∈D � p∈R(d,e) x 0 dp ≤ y 0 e , e ∈ E (1b) [λ s d ≥ 0] � p∈P(d) x s dp ≥ h(d, s), d ∈ D, s ∈ S (1c)
Note that constraint (1d) is, for each link e ∈ E, written down only for s ∈ S(e), and not for all s ∈ S. This is because for any state s ∈ S \ S(e) (in which the capacity of the considered link e is fully available, α(e, s) = 1) constraint (1d) is implied by (1b) and (1e).

The following formulation, crucial for its solution algorithm based on path generation, describes the dual to FTOP (1):

Problem D(P):

W (P) = max � d∈D � s∈S h(d, s)λ s d (2a) [y 0 e ≥ 0] π 0 e + � s∈S (

Solving FTOP through path generation

Although in the following we will assume that the number of states in S is polynomial with the number of links in E, the link-path LP formulation (1) of FTOP remains noncompact because of exponentially many routing paths in the maximum path-set � P. In fact, we cannot hope for finding a compact LP formulation since, as shown in [START_REF] Pióro | Optimizing flow thinning protection in multicommodity networks with variable links capacity[END_REF], FTOP is N P-hard. Since in practice formulation (1) cannot be solved directly (as we are not able to include all elementary paths in the path-sets), in order to consider all paths in � P we need to apply path generation (PG, see [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF][START_REF] Orlowski | Complexity of column generation in network design with pathbased survivability mechanisms[END_REF][START_REF] Pióro | Routing, Flow, and Capacity Design in Communication and Computer Networks[END_REF]) -a classical technique in multicommodity flow networks related to column generation in linear programming (cf. [START_REF] Minoux | Mathematical Programming: Theory and Algorithms[END_REF]). With PG, starting from some initial path-sets P(d), d ∈ D, we iteratively generate new paths, one per demand, and add to the path-sets those paths that may improve the solution. Generating new paths is done by solving an appropriate pricing problem (PP) using, as parameters, an optimal solution (λ * , π * ) of the current dual D(P). Adding new paths to the path-sets to the problem P(P) consists in adding the corresponding variables and constraints to the problem formulation, i.e., we generate new columns and rows in [START_REF] Chan | Free-space optical communications[END_REF].

PP for FTOP is obtained as follows (for a detailed derivation see Section 4 of [START_REF] Pióro | Optimizing flow thinning protection in multicommodity networks with variable links capacity[END_REF]). Consider a given demand d ∈ D and a given path q ∈ � P(d) \ P(d). Introducing such a new path q to the dual (2) introduces both new (we call them local in the following) dual variables σ s , s ∈ S, and new constraints (2c)-(2d). It can happen that some of the new constraints will be violated by the optimal dual solution (λ * , π * ) of D(P) for any non-negative values of the local variables σ s , s ∈ S. In such a case, those constraints in the set of constraints (2c)-(2d) that are violated for a given vector σ s , s ∈ S, will separate (λ * , π * ) from the dual polyhedron of D(P ∪ {q}). The minimum of the sum of such violations is expressed through the quantity

P (q) = min σ s ∈R + , s∈S � max � � s∈S σ s -|q| 0 , 0 � + � s∈S max � λ s d * -σ s -|q| s , 0 � � (3)
where |q| 0 := � e∈E(d,q) π 0 e * (nominal dual length of q), and |q| s := � e∈E(d,q)∩E(s) π s e * , s ∈ S (state-dependent dual length of q). Thus, the pricing problem PP (defined for each demand d ∈ D) consists in maximizing P (q) over q ∈ � P(d). If the resulting maximum is attained by a path q(d) ∈ � P(d) and the maximum is greater than 0 (note that this implies q(d) / ∈ P(d)), then path q(d) is added to the problem: P(d) := P(d) ∪ {q(d)}. For undirected networks the so posed PP can be stated by means of the following mixed-integer (MIP) formulation (where δ(v) denotes the set of links incident to v ∈ V and the superscript * in π * , λ * is skipped).

P (u) = min � � e∈E π 0 e u e + � s∈S � � e∈E(s) π s e u e -λ s d � Y s � (4a) � e∈δ(v) u e = 1, v ∈ {o(d), t(d)}; � e∈δ(v) u e = 2w v , v ∈ V \ {o(d), t(d)} (4b) u e ∈ B, e ∈ E; w v ∈ B, v ∈ V \ {o(d), t(d)}; Y s ∈ B, s ∈ S.
Equations (4b) define, through variables u e (and w v ) equal to 1, a routing path q linking o(d) and t(d). Note that in any optimal solution, Y s = 0 when the length, with respect to π s , of the constructed path q (i.e., |q s |) is greater than λ s d , and Y s = 1 when |q s | < λ s d . This is easily seen from the form of the objective function (4a), which in order to be minimized should have all the terms � e∈E π s e u eλ s d cancelled (through Y s = 0) when positive, and maintained (through Y s = 1) when negative. It turns out that an optimal solution u * , W * , Y * , L of (4) defines a path q(d) := {e ∈ E : u * e = 1} maximizing the value P (q) defined by (3). Hence, q(d), d ∈ D, should be added to FTOP when L * > 0.

To get rid of bi-linearities u e Y s in the objective function (4a) we can introduce binary variables Z s e , s ∈ S, e ∈ E(s), rewrite the objective as

� e∈E π 0 e u e + � s∈S � e∈E(s) π s e Z s e - � s∈S λ s d Y s , (5)
and add the constraints

Z s e ≤ u e , Z s e ≤ Y s , Z s e ≥ 0, Z s e ≥ u e + Y s -1, s ∈ S, e ∈ E(s). (6)
For binary u e and Y s these constraints force the equalities Z s e = u e Y s , s ∈ S, e ∈ E(s) (hence, variables Z can formally be assumed continuous).

The PP counterpart for directed networks (with constraints (4b) replaced by the standard load-conservation equations) is formulated in [START_REF] Pióro | Optimizing flow thinning protection in multicommodity networks with variable links capacity[END_REF].

Flow thinning formulae

A solution of FTOP minimizes the cost of network links using optimized state-dependent path-flow patterns x s that can be thinned with respect to the nominal path-flow pattern x 0 in an arbitrary way (i.e., obeying only the inequality in (1e)). In this section we will assume that the nominal path-flows are thinned according to a fixed flow thinning formula of a given form depending on the link failure coefficients.

General quadratic formula (Q/G)

The most general form of the flow thinning formula considered in this paper is expressed as a quadratic form of the link failure coefficients. It defines the flow on path p ∈ � P(d) of demand d ∈ D in state s ∈ S as follows:

x s dp = z 0 dp - � e∈ � E(d,p) β(e, s)z e dp + � {e,e � }∈ � E |2| (d,p) β(e, s)β(e � , s)z ee � dp . (7)
Above, the set � E(d, p) ⊆ E is a (predefined) subset of links whose failure coefficients influence the thinning formula for a given path p ∈ P(d), d ∈ D. (In [START_REF] Pióro | Routing, Flow, and Capacity Design in Communication and Computer Networks[END_REF], � E |2| (d, p) denotes the set of all 2-element subsets of � E(d, p).) For such a path, the quantities

z dp := (z 0 dp ; z e dp , e ∈ � E(d, p); z ee � dp , {e, e � } ∈ � E |2| (d, p))
will be used as optimization variables which are continuous and unrestricted in sign. When optimized (and fixed) they will define flow thinning formulae: for each path p ∈ P(d), d ∈ D, such a formula is a quadratic form in β(e, s), e ∈ � E(d, p), determining the path's flow for each state s ∈ S. Note that since z dp are unconstrained in sign, we could as well add the first sum on the right-hand side of ( 7) instead of subtracting it. We used the subtraction just to make the formula analogous to the simple flow thinning formula (S) introduced in Section 4.2.2.

Inserting the thinning formula [START_REF] Pióro | Routing, Flow, and Capacity Design in Communication and Computer Networks[END_REF] into FTOP results in the following LP formulation:

Problem P(P):

F (P) = min � e∈E ξ(e)y 0 e (8a) [π 0 e ≥ 0] � d∈D � p∈R(d,e) x 0 dp ≤ y 0 e , e ∈ E (8b) [λ s d ≥ 0] � p∈P(d) x s dp ≥ h(d, s), d ∈ D, s ∈ S (8c) [π s e ≥ 0] � d∈D � p∈R(d,e) x s dp ≤ α(e, s)y 0 e , e ∈ E, s ∈ S(e) (8d) [ϕ s dp ] x s dp = z 0 dp - � e∈ � E(d,p) β(e, s)z e dp + � {e,e � }∈ � E |2| (d,p) β(e, s)β(e � , s)z ee � dp , d ∈ D, p ∈ P(d), s ∈ S (8e) [σ s dp ≥ 0] x s dp ≤ x 0 dp , d ∈ D, p ∈ P(d), s ∈ S (8f)
y 0 e ∈ R + , e ∈ E; x 0 dp ∈ R + , d ∈ D, p ∈ P(d); x s dp ∈ R + , d ∈ D, p ∈ P(d), s ∈ S; z 0 dp , z e dp , z ee � dp ∈ R, d ∈ D, p ∈ P(d), e ∈ � E(d, p), {e, e � } ∈ � E |2| (d, p).
As in FTOP, the quantities indicated in the square brackets are dual variables.

Variants of the flow thinning formula

Various specific cases of the thinning formula [START_REF] Pióro | Routing, Flow, and Capacity Design in Communication and Computer Networks[END_REF] considered in the following will differ in the three aspects listed below. All twelve combinations implied by these aspects lead to valid flow thinning formulae and will be considered in the numerical study described in Section 6.

Form

Two basic forms of the thinning formula are considered:

• (Q) quadratic (7): x s dp = z 0 dp - � e∈ � E(d,p) β(e, s)z e dp + � {e,e � }∈ � E |2| (d,p) β(e, s)β(e � , s)z ee � dp .
• (A) affine (no quadratic terms):

x s dp = z 0 dp - � e∈ � E(d,p) β(e, s)z e dp .

Structure

The structure of the thinning formula is twofold:

• (G) general: no constraints on z 0 dp and z dp (as in [START_REF] Pióro | Routing, Flow, and Capacity Design in Communication and Computer Networks[END_REF]).

• (S) simple: z 0 dp = x 0 dp and nonnegative z dp and, i.e.,

x s dp = x 0 dp - � e∈ � E(d,p) β(e, s)z e dp + � {e,e � }∈ � E |2| (d,p) β(e, s)β(e � , s)z ee � dp , z dp ≥ 0. ( 9
) v w t β = 1 4 β = 1 2 Figure 1: A two-link network.
Above z dp denotes (for p ∈ P(d), d ∈ D) the vector of all z e dp (in affine formulae) or the vector of all z e dp and z ee � dp (in quadratic formulae). With nonnegative coefficients z dp in the simple formula (S), the signs of the summations on the right-hand side of ( 9) are important. To illustrate this point let us consider a very simple network with two links (e = 1 between nodes v and w, and e = 2 between nodes w and t) in series depicted in Figure 1, and one demand between nodes v and t. Both links have capacity 1. We consider four states in S described in the first three columns in Table 1, where the link failure coefficients for a particular state s ∈ S are specified in column 2 (for link e = 1) and in column 3 (for link e = 2). Clearly, the maximum nominal flow for the demand is x 0 = 1 (the subscripts in x 0 are skipped as there is only one demand d = 1 with only one path p = 1 composed of links e = 1 and e = 2). With the simple affine formula (with � E(d, p) = E) the maximum feasible flows in the remaining states (given in column 4) are achieved with

z 1 = z 2 = 1 (i.e., x s = 1 -β(1, s) -β(2, s)).
For the simple quadratic formula the maximum flows (given in column 5) are achieved with

z 1 = z 2 = z 12 = 1 (i.e., x s = 1 -β(1, s) -β(2, s) + β(1, s) • β(2, s)).
Note that the maximum flow in state s = 3 is greater for the quadratic formula (x 3 = 3 8 ) than for the affine formula (x 3 = 1 4 ). Note also that for FT (column 6) the maximum flow in state s = 3 is equal to 1 2 (of course, this value cannot be further increased due to capacity constraints). The presented example clearly shows why the sign before the first sum in (9) must be subtracted from x 0 (to have feasible flows), and the second sum added (to maximize the achievable flows).

s β(1, s) β(2, s) AFT: x s QFT: x s FT: x s 0 0 0 1 1 1 1 1 4 0 3 4 3 4 3 4 2 0 1 2 1 2 1 2 1 2 3 1 4 1 2 1 4 3 8 1 2
Table 1: Affine and quadratic flows with simple formula.

Range

The range of the thinning formula is the set � E(d, p) ⊆ E. As discussed in [START_REF] Pióro | Optimizing flow thinning protection in multicommodity networks with variable links capacity[END_REF], typical examples of the sets � E(d, p) are:

• (E(d, p)) path's links: � E(d, p) = E(d, p) -the formula depends only on the failure coefficients of the links along the path.

• (E + (d, p)) link's incident to path's nodes: � E(d, p) = � v∈V(d,p) δ(v) (where δ(v)
is the set of links incident with v) -the formula depends on the failure coefficients of the links incident to the nodes along the path; in the following the set of links � v∈V(d,p) δ(v) will be denoted with E + (d, p).

• (E) all links: � E(d, p) = E -the formula depends on the failure coefficients of all links.

Pricing problems

The counterparts of FTOP corresponding to the thinning formulae described in Section 4.2 are solved through path-generation (see Section 3.2). For that, appropriate pricing problems are required. Below we will derive the pricing problems (PP) for the simple affine formula case (A/S) and for the general affine formula case (A/G). Both of them turn out to be more complicated than their FT counterpart derived in Section 3.2. We will also discuss the pricing problems for the quadratic forms.

PP for simple affine formula

We start with deriving the pricing problem for the simple affine formula A/S.

A/S -PP derivation for arbitrary range � E(d, p)

The optimization problem for the simple affine formula (a counterpart of ( 8)), i.e., Problem P(P):

F (P) = min � e∈E ξ(e)y 0 e (10a) [π 0 e ≥ 0] � d∈D � p∈R(d,e) x 0 dp ≤ y 0 e , e ∈ E (10b) [λ s d ≥ 0] � p∈P(d) x s dp ≥ h(d, s), d ∈ D, s ∈ S (10c) [π s e ≥ 0]
y 0 e ∈ R + , e ∈ E; x 0 dp ∈ R + , d ∈ D, p ∈ P(d); x s dp ∈ R + , d ∈ D, p ∈ P(d), s ∈ S; z e dp ∈ R + , d ∈ D, p ∈ P(d), e ∈ � E(d, p)
has the following dual:

Problem D(P):

W (P) = max � d∈D � s∈S h(d, s)λ s d (11a) [y 0 e ≥ 0] π 0 e + � s∈S(e) α(e, s)π s e ≤ ξ(e), e ∈ E (11b) [x 0 dp ≥ 0] � s∈S ϕ s dp ≤ � e∈E(d,p) π 0 e , d ∈ D, p ∈ P(d) (11c) [x s dp ≥ 0] λ s d ≤ ϕ s dp + � e∈E(d,p)∩E(s) π s e , s ∈ S, d ∈ D, p ∈ P(d) (11d)
[z e dp ≥ 0]

� s∈S β(e, s)ϕ s dp ≥ 0, d ∈ D, p ∈ P(d), e ∈ � E(d, p) (11e)
π 0 e ∈ R + , e ∈ E; π s e ∈ R + , e ∈ E, s ∈ S(e); λ s d ∈ R + , d ∈ D, s ∈ S; ϕ s dp ∈ R, d ∈ D, p ∈ P(d), s ∈ S.
As in the derivation of PP for FT in Section 3.2, consider a given demand d ∈ D and a given path q ∈ � P(d) \ P(d). Adding such a new path q to the dual [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF] introduces new local variables ϕ s , s ∈ S, and new constraints (11c)-(11e). If the new constraints (11c)-(11e) are violated by the optimal solution (λ * , π * ) of the dual [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF] for any values of the local variables, then the violated constraints will separate (λ * , π * ) from the dual polyhedron. The minimum of the sum of such violations (taken over all feasible local dual variables) is expressed through the quantity

P (q) = min ϕ s ∈R, s∈S � max �� s∈S ϕ s -|q| 0 , 0 � + � s∈S max � λ s d * -|q| s -ϕ s , 0 � + + � e∈ � E(d,q) max � - � s∈S β(e, s)ϕ s , 0 � � .
(recall that |q| 0 := � e∈E(d,q) π 0 e * and |q| s := � e∈E(d,q)∩E(s) π s e * , s ∈ S) which can be calculated as the solution of the following LP.

P (q) = min � Z + � s∈S Y s + � e∈ � E(d,q) X e � (13a) [g ≥ 0] Z ≥ � s∈S ϕ s -|q| 0 (13b) [a s ≥ 0] Y s ≥ λ s d * -|q| s -ϕ s , s ∈ S (13c) [b e ≥ 0] X e ≥ - � s∈S β(e, s)ϕ s , e ∈ � E(d, q) (13d)
Z ∈ R + ; Y s ∈ R + , s ∈ S; X e ∈ R + , e ∈ � E(d, q); ϕ s ∈ R, s ∈ S. (13e)
In order to solve PP, we first notice that we can as well maximize the value of P (q) over all paths q ∈ � P(d) since for all p ∈ P(d) the value P (p) is equal to zero, and a new path q will be added to the current list P(d) only when P (q) is greater than zero. Hence, PP turns out to be the max-min problem of the form

max q∈ � P(d) min X,Y,Z,ϕ � Z + � s∈S Y s + � e∈ � E(d,q) X e � (14a) subject to constraints (13b)-(13e) (14b)
(where Y and X are appropriate vectors of variables). As such, problem (14) cannot be solved directly. A way to resolve this issue is to consider the problem dual to (13), formulated using the dual variables specified in the square brackets in constraints (13b)-(13d):

P (q) = max � -g|q| 0 + � s∈S (g - � e∈ � E(d,q) β(e, s)b e )(λ s d * -|q| s )) � (15a) g ≤ 1; b e ≤ 1, e ∈ � E(d, q); � e∈ � E(d,q) β(e, s)b e ≤ g, s ∈ S (15b) g ∈ R + ; b e ∈ R + , e ∈ � E(d, q). ( 15c
)
Note that in (15), dual variables a s , s ∈ S, have been eliminated. This is possible because variables x s dp , for all d, p, s, are auxiliary, and can be expressed through x 0 dp and z e dp , e ∈ � E(d, p), on the condition

x 0 dp ≥ � e∈ � E(d,p)
β(e, s)z e dp . Now we introduce binary quantities u e , e ∈ E, that represent the path q: E(d, q) = {e ∈ E : u e = 1}. Also, from now on we will skip superscript * in π * and λ * in the derivations, i.e., we will denote the optimal dual solution simply by π, λ. Hence, |q| 0 = � e∈E π 0 e u e and |q| s = � e∈E(s) π s e u e , s ∈ S, and, in consequence, we can rewrite (15):

P (u) = max � -g( � e∈E π 0 e u e ) + � s∈S � g - � e � ∈ � E(d,q) β(e � , s)b e � )(λ s d - � e∈E(s) π s e u e ) � (16a) g ≤ 1; b e � ≤ 1, e � ∈ � E(d, q); � e � ∈ � E(d,q) β(e � , s)b e � ≤ g, s ∈ S (16b) g ∈ R + ; b e � ∈ R + , e � ∈ � E(d, q). (16c)
Finally, by transforming objective (16a), treating u e , e ∈ E, as variables, and adding appropriate path-defining constraints (for undirected links) we arrive at the following formulation of the pricing problem for problem [START_REF] Tomaszewski | On the complexity of resilient network design[END_REF].

P = max � - � e∈E π 0 e gu e + ( � s∈S λ s d )g - � s∈S � e∈E(s) π s e gu e + + � s∈S � e � ∈ � E(d,q) � e∈E(s) β(e � , s)π s e b e � u e - � s∈S � e � ∈ � E(d,q) λ s d β(e � , s)b e � � (17a) � e∈δ(v) u e = 1, v ∈ {s(d), t(d)}; � e∈δ(v) u e = 2z v , v ∈ V \ {s(d), t(d)} (17b) g ≤ 1; b e � ≤ 1, e � ∈ � E(d, q); � e � ∈ � E(d,q) β(e � , s)b e � ≤ g, s ∈ S (17c) g ∈ R + ; b e � ∈ R + , e � ∈ � E(d, q); u e ∈ B, e ∈ E; z v ∈ B, v ∈ V, (17d)
where δ(v) denotes the set of all links incident to node v ∈ V. In the formulation, (17b) are path-defining constraints so that an optimal solution u * of (17) defines the path q with E(d, q) := {e ∈ E : u * e = 1} (and, for that matter, with V(d, q) := {v ∈ V : z * v = 1}) that should be added to [START_REF] Tomaszewski | On the complexity of resilient network design[END_REF], provided P (q) > 0. Note that any feasible set U := {e ∈ E : u e = 1} will necessarily contain an elementary path between s(d) and t(d) and, possibly, a set of disjoint isolated loops. The path is elementary because variables z v , v ∈ V, are binary (note that assuming these variables to be integer-valued would allow the path to contain loops as well). In fact, such loops may appear in optimal PP solutions because of a tradeoff related to the number of elements in the set U: the more elements the more flexible formulae (10e), and the less elements the lower link capacities.

Certainly, formulation (17) can be easily modified for directed networks (with links in E directed) using the node-arc formulation with load conservation equations instead of (17b):

� e∈δ -(t(d)) u e - � v∈V\{s(d),t(d)} u e = 1 (18a) � e∈δ + (v) u e - � a∈δ -(v) u e = 0, e ∈ E. (18b)
In fact, formulation ( 17) is incomplete as it makes use of the set � E(d, q) (specifying the range of the thinning formula) which in general is path-dependent and not known in advance. It also contains multiplication of variables. Thus, in order to obtain a proper MIP formulation, an appropriate representation of � E(d, q) is required (by means of optimization variables), along with linearization of variables' multiplication. The particular forms of such a MIP depend on the assumed thinning formula range, as shown below.

Case

� e∈δ(v) u e = 2z v , v ∈ V \ {s(d), t(d)} (19b)
T ee � ∈ R + , e, e � ∈ E (19g) u e ∈ {0, 1}, e ∈ E; z v ∈ {0, 1}, v ∈ V \ {s(d), t(d)}. ( 19h
)
The extra variables in the above formulation are used to eliminate multiplication of variables and have the following meaning:

B e = b e • u e , G e = g • b e , T e � e = b e � • u e � • u e .
In order to eliminate the (isolated) loops in {e ∈ E : u e = 1} we introduce the bi-directed version G � = (V, A) of the original undirected network graph G = (V, E), where the set of (directed) arcs is defined as A := {(v, w), (w, v) : {v, w} ∈ E}, i.e., each undirected link e ∈ E is substituted by two oppositely directed arcs a � (e) and a �� (e). Below, δ -(v) denotes the set of all arcs incoming to node v, and δ + (v) -the set of all arcs outgoing from node v (v ∈ V). Adding aggregated arc-flow variables f a ≥ 0, a ∈ A, and the following constraints to (19) will eliminate the loops in question.

� a∈δ -(t(d)) f a = � v∈V\{s(d),t(d)} z v (20a) � a∈δ + (s(d)) f a = � a∈δ -(s(d)) f a (20b) � a∈δ + (v) f a = � a∈δ -(v) f a + z v , v ∈ V \ {s(d), t(d)} (20c) f a � (e) + f a �� (e) ≤ (|V| -2)u e , e ∈ E.. (20d)
We note that this case was considered in [START_REF] Pióro | An optimization model for affine flow thinning -a traffic protection mechanism for FSO networks[END_REF].

5.1.3. Case � E(d, p) = E + (d, p) The version of PP for � E(d, p) = E + (d, p) (more complicated than (19)
) is given in formulation (A.1) presented in Section Appendix A.1.1 of Appendix A. We note that formulation (A.1) requires loop-elimination constraints (20). It is also computationally less efficient than its counterparts for � E(d, p) = E(d, p) and � E(d, p) = E. For this reason, the cases for range E + (d, p) reported in Section 6 were optimized using the sets of paths generated for the corresponding cases assuming range E.

Case � E(d, p) = E

The PP formulation for the considered full range case is given by (A.2) in Section Appendix A.1.2. In the considered full range case, the PP formulation becomes simpler than (A.2) since now variables B e � are equal to b e � rather than to b e � u e � , and variables T e � e express the product u e � b e � rather than u e � u e b e � . Moreover, the loops in the optimal path will not appear due to the maximal range of the thinning formula. We observe that formulation (A.2) is simpler and computationally more efficient than its counterpart (19) for � E(d, p) = E(d, p).

PP for general affine formula A/G

Now we consider problem formulation [START_REF] Tomaszewski | On the complexity of resilient network design[END_REF] with equation (10e) substituted by its general affine version

x s dp = z 0 dp -

� e∈ � E(d,p) β(e, s)z e dp ( 21
)
where the affine coefficients z 0 dp , z e dp , d ∈ D, p ∈ P(d), e ∈ � E(d, p), are continuous and unrestricted in sign. Not surprisingly, it turns out that pricing for such obtained formulations (for different thinning formula ranges) is more complicated than for their counterparts described in Section 5.1 and Appendix A. [START_REF] Chan | Free-space optical communications[END_REF]

PP for quadratic formulae

The formulations of pricing problems for the thinning formulae containing the quadratic terms as in the general formula Q/G (8e) or its simplified version Q/S can be derived analogously as for the affine cases. Yet, the resulting PP formulations require much more variables and become computationally inefficient. For example, products of the form u e • u e � • u e �� • b e appearing in the non-linear versions will have to eliminated, and this will involve |E| 3 auxiliary variables. To resolve this issue, we simply use the sets of paths generated for the affine counterparts of the quadratic problem in question (see Section 6.2.3).

Numerical study

In this section we will present optimization results obtained for medium size network instance. The study illustrates efficiency of the considered versions of the flow thinning formulae (in terms of the network cost), as well as of the path generation algorithm (in terms of the computation time).

Network instance

The study was performed for a network described in the communication network instances library SNDlib (sndlib.zib.de, see [START_REF] Orlowski | SNDlib 1.0 -survivable network design library[END_REF]) under the name polska. In the study we used the data from the first instance (i.e. , polska-D-B-M-N-C-A-N-N). The networks is composed of |V | = 12 nodes, |E| = 18 (undirected) links, and |D| = 66 (undirected) demands. The link unit capacity cost ξ(e) is equal to the link's <module cost> divided by <module capacity> for the first pair of these values. Thus, for the first link (between Gdansk and Warsaw) ξ(1) = 156/155 = 1.0645, and the entire vector ξ of the unit capacity costs is as follows: 1.0645, 1.7548, 1.0064, 1.2000, 1.7548, 1.5290, 1.3419, 1.1677, 1.3419, 1.6129, 2.0903, 2.0903, 1.6129, 1.0645, 1.9677, 0.9161, 1.2581, 1.8968 (the order of the links is the same as in the SNDlib file). We note that the same network instance was used in the case study for A/S presented in [START_REF] Pióro | Path generation for affine flow thinning[END_REF].

We consider three link availability state scenarios:

(SL) Single link failure scenario: SL contains the nominal state s(0) (all links fully available), and all states with exactly one failing link (note that SL contains |E| + 1 states). The traffic demands in state s(0), h(d, s(0)), d ∈ D, are specified in SNDlib. In SL, 100% traffic protection is assumed, i.

Network cost and algorithm efficiency

The results of the numerical study for polska are presented in Tables 2,3, and 4. All the reported calculations were executed on a PC-class computer (Windows 10 64-bit, 8 GB RAM, Processor Intel Core i5-3210M, 4 logical processors, 2.5GHz) using CPLEX 12.4.0.0. In the calculations, the initial path-lists for the PG algorithm contain only one path per demand -the shortest path with respect to the link unit costs ξ(e), e ∈ E (66 paths in total). Note that assigning the entire nominal demand volume h(d, s(0)) for each demand d to its shortest path will result in the optimally dimensioned network when protection is not considered. For the examined network example this cost turns out to be F 0 = 30275 (as indicated in Table 2).

Results for GR and FT

Table 2 compares results obtained by means of the PG algorithm for GR (Global Rerouting, see [START_REF] Orlowski | Complexity of column generation in network design with pathbased survivability mechanisms[END_REF][START_REF] Pióro | Routing, Flow, and Capacity Design in Communication and Computer Networks[END_REF]), and FT (Flow Thinning). The results for FT are obtained by solving problem [START_REF] Chan | Free-space optical communications[END_REF]. The analogous problem for GR is obtained from (1) simply by deleting constraints (1b) and (1e). Note that because of that GR, as the least constrained, and thus least costly, protection mechanism is used as a benchmark since it provides the lower bound for the network cost achievable with any other mechanism.

For each failure scenario (SL, DL, TL), the rows in Table 2 contain the results for GR and FT, and the consecutive columns describe:

-F 0 : cost of unprotected network dimensioned for h(d, s(0)), d ∈ D -F * : cost of the optimal solution resulting from the PG algorithm -ΔF 0 : cost increase with respect to unprotected network (ΔF 0 = F * -F 0 -number of iterations (iter), total computation time (total), time per iteration (t/iter), computation time spent in problem P(P) (called the master problem, MP, in this context) per iteration (t/MP), and pricing problem computation time per iteration (t/PP). The results show that lower bound for the cost of protection (achieved with GR) for the considered instance is between 18% (SL) and 26% (DL). Certainly, FT requires more capacity but the cost increase as compared to GR is not significant (between 2% for TL and 12% for SL. The number of generated paths is lower for GR than for FT, but the number of the paths used in the final (optimal) solution is higher (which could be expected). In both cases the computation times are negligible for SL and low for DL. For TL, the algorithm applied to GR is still quite fast, while for FT it starts to be more time consuming, both for MP and PP. We note here that the PG algorithm for GR works differently than for FT (and, for that matter, for QFT and AFT). In the former case in each iteration a new path is considered for each demand d ∈ D and each state s ∈ S, while for FT only one path demand is considered. This is why GR requires less iterations than FT. Yet, even for FT the number of iterations is small and the PG algorithm converges very quickly.

F 0 F * ΔF 0 [%] ΔF * [%] |P * | |P u |

Results for AFT

Table 3 gives the results for AFT, i.e., for flow thinning with affine thinning formulae. For each failure scenario, all six combinations of the range and the structure considered for the thinning formulae of form A (see Section 4.2) are examined (and specified in columns "range" and "structure"). Now, column "ΔF * " expresses the increase in the network cost for a given variant of AFT with respect to the corresponding solution F * for FT given in Table 2. The meaning of the remaining columns is the same as before.

Regarding the network cost F * achievable by the considered AFT formulae, we first of all observe that in the SL case (single link failures), the minimal cost (i.e., the cost of FT) is achieved already with the simplest form of the thinning formula, that is with A/S/E(d, p). range structure The reason is as follows. Suppose x 0 dp * and x s dp * are optimal for FT. Then the thinning formula , e ∈ E(d, p)

F * ΔF * [%] |P * | |P u |
will give the optimal values of x s dp , that is those found for FT. In the formula, s(e) denotes the particular state s ∈ S in which link e is affected with the failure coefficient β(e, s(e)) > 0 (in the remaining states, i.e., for s ∈ S \ {s(e)}, β(e, s) = 0). (Recall that in the considered example β(e, s(e)) = 0.5.)

For DL and for TL this is no longer the case. Assuming the range E(d, p), the increase in F * given by ΔF * is quite high: for DL it is equal to 18% for both structures G (general) and S (simple) while for TL it is equal to 13% for both structures. For the two other ranges (E + (d, p) and E), the difference between G and S becomes visible. For E + (d, p) the considered increase for G is roughly 2 times smaller than for S, while for E it is 3.25 (TL) to 3.6 (DL) times smaller. Finally, we note that the cost increase ΔF * for the case A/G/E is only 4%, while for A/G/E + (d, p) it rises to 7%.

Note that for E + (d, p) Table 3 reports one computation time (t/MP). This is because this particular range case was not treated by the path generation algorithm because of excessive computation time (of the order of hours) required for the pricing problem (see the discussion in the last paragraph of Section 5.1.3). Instead, we just solved the appropriate variant of the master problem [START_REF] Tomaszewski | On the complexity of resilient network design[END_REF], assuming the path-sets P * generated for E. For the same reason the number of iterations is not reported (-in column "iter"). Although this makes the optimization approach heuristic, the obtained solutions are clearly near-optimal.

It is also interesting to note that the case A/S gives the same value of F * for all the three ranges, and this means that the solution for E + (d, p) is optimal, as it is always less than or equal to the optimal solution for E(d, p), and greater than or equal to the optimal solution for E. Let us also note that in all the considered scenarios the costs of A/S/E(d, p) and A/G/E(d, p) happen to be equal. Yet, this is not always true. We have found some (randomly generated) state scenarios (with the states containing 4-9 links affected with the failure coefficient equal to 0.4) for the polska network where the costs for these two cases are different. Still, the difference is small, of the order of 1.5%. The numbers of paths generated by the PG algorithm (column "|P * |") and the number of paths used in the optimal solution (column "|P u |") do not exhibit any particular properties, except that sometimes |P u | is considerably smaller than |P * | (even more than two times for SL and E(d, p)).

The number of iterations performed by the PG algorithm varies from 6 to 10 and this is a reasonable number indicating fast convergence. The computation time spent in pricing is also reasonable although this requires solving MIP formulations. The time spent in the master problem is typically smaller than the time required for pricing. Certainly, the computation time increases with the number of states in S, but even for TL the total computation times are acceptable. Table 4 shows the results for QFT, i.e., for flow thinning with quadratic thinning formulae. As for the AFT case, all the six combinations of range/structure (see Section 4.2) are considered for each failure scenario. As already mentioned in Section 5.3, all the QFT cases were directly optimized through solving an appropriate version of the master problem [START_REF] Koster | Demand-wise shared protection for meshed optical networks[END_REF] for the sets of paths obtained for the corresponding AFT cases -this is due to excessive pricing time for QFT. (Therefore, Table 4 has a reduced set of columns as compared with Table 3.) This near-optimal procedure has already been applied for the E + (d, p) range of the AFT.

Clearly, the QFT cost values given in Table 4 for SL are the same as for AFT (and, for that matter, for FT), since AFT is a special case of QFT. Note that corresponding total solution times are much shorter since no pricing is involved.

However, for DL and TL, the cost of the QFT solutions is considerably smaller than for the corresponding AFT solutions. In fact, the case Q/G/E (general quadratic form with full range) indicates virtually the same cost as FT (arbitrary flow thinning): cost increase 0.03% for DL, and 0.2% for TL. At the same time, the simplified quadratic form with full range (Q/S/E) is only marginally worse: cost increase 0.5% for DL, and 1.3% for TL. With respect to E, the costs obtained with range E + (d, p) are not much greater. For DL the cost increase is 2.6% for Q/G and 3.0% for Q/S, while for TL it is equal to 4.5% for Q/G and 6.1% for Q/S. For E(d, p) further cost increase is observed, reaching 7.6% for Q/S and TL.

As far as computation time is concerned, the SL and DL cases are optimized very quickly, yet the computation time becomes substantially longer for TL. The reason is excessive number of variables and constraints in the LP formulation.

Implementation issues and suggested formula

The flow thinning mechanisms assume that the capacity of each (MPLS) tunnel is controlled at its source node by a packet admission control mechanism based on the on-line knowledge of the currently available link capacity. Therefore, some signalling mechanism for interchanging information concerning the current state of link capacities must be applied. In the case of FT, and of QFT and AFT with the full range E, this requires some kind of a flooding protocol since the source nodes of the tunnels need to be aware of the current availability state of all links. Since flooding signalling takes time, the capacity adjustment process may lead to unprecise tunnel capacity control and, in consequence, to traffic losses. Moreover, flooding may be excessively complex to implement. This actually means that feasibility of FT, QFT/E and AFT/E is problematic.

On the other hand, in the case of QFT and AFT with the E(d, p) range, the signalling in question is simple and fast: when availability of a link is changed, an appropriate message is propagated backwards to the source nodes of all the tunnels traversing the considered link, resulting in efficient and timely message delivery for link availability state monitoring. For the E + (d, p) range the signalling is similar, only more information is propagated.

Another issue is how the tunnel capacity control performs for the states not considered in optimization, i.e., the states in the set S. For such a purpose the most cost effective flow thinning mechanism, i.e., FT, is not satisfactory, as it does not provide consistent means for this kind of control. Thus, since inappropriate setting of tunnel capacity can lead to link overloads, the FT mechanism is risky in this aspect. On the contrary, the QFT and AFT mechanisms can simply apply the flow thinning formula also for the unforeseen states, modifying the tunnel capacity to 0 or x 0 dp when necessary, i.e., when the value obtained from the flow thinning formula is below 0 or above x 0 dp , respectively. (Traffic efficiency of such extended thinning is addressed in Section 8.2 of [START_REF] Pióro | Optimizing flow thinning protection in multicommodity networks with variable links capacity[END_REF] for AFT/G.) We may also expect that the larger the range of the affine formula, the better approximation of the proper tunnel capacity in the states not considered in optimization -this, however, needs to be verified.

Here, the simple structure (S) of the flow thinning formula seems more safe than the general structure (G) because the former does not allow to exceed the nominal tunnel capacity in any state.

FT is the most general flow thinning mechanism and therefore it results in the lowest cost of link capacity. In fact, in this aspect FT is quite close to the benchmark GR mechanism, which provides the lower bound on the link capacity cost for any protection/restoration mechanism (see [START_REF] Pióro | Routing, Flow, and Capacity Design in Communication and Computer Networks[END_REF]). Tables 2, 3 and 4 show that the network cost achieved with QFT/G with range E is almost the same as the cost of FT, while the cost for QFT/G with range E + (d, p) is higher but to a reasonable extent (4.5% of cost increase with respect to FT at most). The network cost achieved with QFT/G with the smallest range E(d, p) is up to 7.4% higher than the cost for FT. As far as AFT is concerned, the network cost increase is significantly higher than for QFT.

Having in mind that the optimization of flow thinning is performed off-line, the total computation times are acceptable in all the considered cases, besides QFT with the ranges E and E + (d, p). This, however, is not a big issue taking into account that the results shown in the tables were obtained using a plain laptop, and the efficiency of the optimization algorithm could be improved (if really needed) by exploiting specific properties of its master problem. The above observations (summarized in Table 5) suggest that QFT/G/E + (d, p) (the mechanism with the general quadratic thinning formula encompassing all links adjacent to the nodes of the tunnel) is a reasonable traffic protection mechanism to be considered for implementation in FSO networks.

Concluding remarks and future work

In the paper we have presented an original optimization model for the quadratic flow thinning (QFT) traffic protection mechanism. The solution algorithm (based on path generation) developed for the model was tested in a numerical study and its time efficiency turned out to be satisfactory. In the numerical study we have examined a medium-size network in order to compare the cost of various variants of QFT, including its simpler affine version (AFT). Clearly, in comparison with the original FT mechanism, the thinning formula used in QFT introduces an additional constraint on thinning (recall that with FT, (1e) is the only constraint on flow thinning). In effect, QFT requires more link capacity than FT. Still this extra cost can be made acceptable (of the order of few percent) when the proper range (the set of all links, or the set of all links incident to the nodes of the path) of the quadratic formula is adopted. Taking into account all the observations gathered in Table 5, we conclude that the variant Q/G/E + (d, p) delivers the best compromise protection solution out of all the considered thinning options.

As far the future research directly related to the presented considerations is concerned, it is important to examine the following issues:

• Add modularity of link capacity (parallel FSO links); this will involve integer variables y 0 in problem FTOP (1) and its QFT counterpart [START_REF] Koster | Demand-wise shared protection for meshed optical networks[END_REF].

• Test effectiveness of applying path-sets generated for AFT to QFT (this is done in the paper) instead of using the exact approach with the QFT pricing problems.

• Improve efficiency of the path-generation algorithm for QFT with the E + (d, p) range.

• Repeat the numerical study for other network instances to verify the conclusions of this paper. where |q| 0 := � e∈E(d,q) π 0 e (nominal dual length of q), and |q| s := � e∈E(d,q)∩E(s) π s e (statedependent dual length of q), s ∈ S. The LP formulation for computing P (q) is as follows: are used to eliminate the products (bilinearities and tri-linearities) of the original variables -this is indicated in (A.7b). We note that this particular case was considered in [START_REF] Pióro | Path generation for affine flow thinning[END_REF].

P (q) = min � Z + � s∈S Y s + � e∈ � E(d,q) (X � e + X �� e ) + W + W � � (A.5a) [g ≥ 0] Z ≥ � s∈S σ s -|q| 0 (A.

  Traffic demands are represented by the set D. Each demand d ∈ D is characterized by an undirected pair of the demand's end nodes {o(d), t(d)}, and given traffic volumes h(d, s) to be realized in each of the considered link availability states s ∈ S. Traffic volumes and link capacities are expressed in the same units (e.g., Mbps). Each demand d is equipped with a set of allowable paths P(d) (called the path-set) composed of selected elementary paths between o(d) and t(d). Only the paths in P(d) can be used to realize the demand (traffic) volumes and each such path p ∈ P(d) carries the nominal flow x 0 dp . More precisely, each x 0 dp specifies the nominal capacity (expressed in the same units as link capacity and demand volume) reserved on the tunnel realized along path p ∈ P(d). The set of all allowable paths is denoted by P := � d∈D P(d). The maximum path-sets, i.e., path-sets P(d) containing all the elementary paths between o(d) and t(d), are denoted by � P(d), d ∈ D, and � P := � d∈D � P(d). Clearly, the number of paths in � P grows exponentially with the size of the network graph. Since we consider elementary paths, we can identify each of them with the set E(d, p) of the links it traverses (E(d, p) ⊆ E). Similarly, V(d, p) will denote the set of nodes traversed by the path. For a given path-set P(d), its subset containing a given link e will be denoted with R(d, e), i.e., R(d, e) := {p ∈ P(d) : e ∈ E(d, p)}, d ∈ D, e ∈ E. The sets of allowable paths P(d) are parameters in the problem formulations considered in the following.

  ,e) x s dp ≤ α(e, s)y 0 e , e ∈ E, s ∈ S(e) (1d) [σ s dp ≥ 0] x s dp ≤ x 0 dp , d ∈ D, p ∈ P(d), s ∈ S (1e) y 0 e ∈ R + , e ∈ E; x 0 dp ∈ R + , d ∈ D, p ∈ P(d); x s dp ∈ R + , d ∈ D, p ∈ P(d), s ∈ S.

  � d∈D � p∈R(d,e) x s dp ≤ α(e, s)y 0 e , e ∈ E, s ∈ S(e) (10d) [ϕ s dp ] x s dp = x 0 dp -� e∈ � E(d,p) β(e, s)z e dp , d ∈ D, p ∈ P(d), s ∈ S (10e)

B

  e ≤ u e , B e ≤ b e , B e ≥ b e + u e -1, e ∈ E (19c) g ≤ 1; b e ≤ 1, e ∈ E; � e∈E β(e, s)B e ≤ g, s ∈ S (19d) G e ≤ g, G e ≤ u e , G e ≥ g + u e -1, e ∈ E (19e) T e � e ≤ u e � , T e � e ≤ u e , T e � e ≤ b e � , T e � e ≥ b e � + u e � + u e -2, e � , e ∈ E (19f) g ∈ R + ; b e , B e , G e ∈ R + , e ∈ E;

  e., h(d, s) = h(d, s(0)), d ∈ D, for all single link failure states s. Link failure coefficients of the affected links are assumed to be β(e, s) = 0.5. (DL) Double link failure scenario: DL contains SL and all states with exactly two failing links (hence DL contains |E|(|E| -1)/2 + |E| + 1) states). Link failure coefficients in the double link failure states are assumed to be β(e, s) = 0.4. For the double link failure states the demand volumes are reduced to 95% of h(d, s(0)) for all d ∈ D. (TL) Triple link failure scenario: TL contains SL and DL, and all states with exactly three failing links (TL contains |E|(|E| -1)(|E| -2)/6 + |E|(|E| -1)/2 + |E| + 1 states). Link failure coefficients of the failing links in the triple link failure states are assumed to be β(e, s) = 0.3 and the reduction of h(d, s(0)) is equal to 90%.

F 0 ×

 0 100%) -ΔF * : cost increase of FT with respect to GR (ΔF * = F * (F T )-F * (GR) F * (GR) × 100%) -|P * |: final number of generated paths -|P u |: number of paths used in the final solution (i.e., paths with positive optimal x 0 dp )

�

  over all feasible local dual variables σ = (σ s , s ∈ S) and ϕ = (ϕ s , s ∈ S)) is expressed through the quantityP (q) = min σ≥0,ϕ � max � � s∈S σ s -|q| 0 , 0 � + � s∈S max � λ s dϕ sσ s -|q| s , s∈S β(e, s)ϕ s | + | � s∈S ϕ s | � ,

�

  5b) [a s ≥ 0] Y s ≥ λ s dϕ sσ s -|q| s , s ∈ S (A.5c) [b � e ≥ 0] X � e ≥ � s∈S β(e, s)ϕ s , e ∈ � E(d, q) (A.5d) [b �� e ≥ 0] X �� e ≥ -� s∈S β(e, s)ϕ s , e ∈ � E(d, q) (A.5e) [c � ≥ 0] W � ≥ � s∈S ϕ s (A.5f) [c �� ≥ 0] W �� ≥ -� s∈S ϕ s (A.5g) σ s ∈ R + , s ∈ S; ϕ s ∈ R, s ∈ S (A.5h) Z, W � , W �� ∈ R + ; Y s ∈ R + , s ∈ S; X � e , X �� e ∈ R + , e ∈ � E(d, q). (A.5i)Next we formulate the problem dual to (A.5), using the dual variables specified in the square brackets in constraints (A.5b)-(A.5g).P (q) = max � -g|q| 0 + � s∈S a s (λ s -|q| s ) � (A.6a) 0 ≤ g ≤ 1, 0 ≤ c � ≤ 1, 0 ≤ c �� ≤ 1 (A.6b) 0 ≤ a s ≤ g, s ∈ S (A.6c) 0 ≤ b � e ≤ 1, 0 ≤ b �� e ≤ 1, e ∈ � E(d, q) (A.6d) a s = c �c �� + � e∈ � E(d,q) β(e,s)(b � eb �� e ), s ∈ S. (A.6e) Below we formulate the pricing problem for the considered general affine formula case only for � E(d, p) = E(d, p) (and undirected networks). Appendix A.2.2. Case � E(d, p) = E Proceeding as in Section 5.1 (and eliminating variables a s , s ∈ S, in (A.6)) we obtain the following formulation. e∈E β(e, s)λ s B �� e ���� b �� e u e -� s∈S � e � ∈E(s) � e∈E β(e, s)π s e � T � e � e � �� � b � e u e u e � + (A.7a) ) u e = 1, v ∈ {s(d), t(d)};� e∈δ(v) u e = 2z v , v ∈ V \ {s(d), t(d)} (A.7b) 0 ≤ g ≤ 1, 0 ≤ c � ≤ 1, 0 ≤ c �� ≤ 1; 0 ≤ b e ≤ 1, 0 ≤ b �� e ≤ 1, e ∈ E (A.7c) 0 ≤ c �c �� + � e∈E β(e,s)(B � e -B �� e ) ≤ g, s ∈ S (A.7d) G e ≤ g, G e ≤ u e , G e ≥ g + u e -1, e ∈ E (A.7e) B � e ≤ u e , B � e ≤ b � e , B � e ≥ b �

  . In Appendix A.2.1we give a general derivation of PP in the considered A/G case, following the derivation for A/S presented in Section 5.1.1. Then, in Section Appendix A.2.2, we present the proper MIP formulation (A.7) for the range � E(d, p) = E(d, p). As for the simple affine formula case, PP formulations for the two remaining cases of thinning formula range are analogous to (A.7). As before, the PP formulation for �

E(d, p) = E + (d, p) is more complicated (and less time consuming) while the PP formulation for � E(d, p) = E is less complicated (and less time consuming) than (A.7). Besides, formulations for � E(d, p) = E(d, p) and � E(d, p) = E + (d, p) require loop-elimination.

Table 2 :

 2 Results for GR and FT.

Table 3 :

 3 Results for affine thinning formulae (A).

Table 4 :

 4 Results for quadratic thinning formulae (Q).

Table 5 :

 5 Summary of the results.

	GR FT	range structure implementation states not in S capacity cost optimization time -infeasible not covered very low very short E -problematic not covered low medium E G feasible covered high medium E(d, p) S feasible+ covered high short
	A	E + (d, p)	G S	feasible feasible	covered+ covered+	medium high	medium-medium
		E	G S	flooding flooding	covered++ covered++	medium high	medium short+
		E(d, p)	G S	feasible feasible+	covered covered	medium medium	medium-medium-
	Q	E + (d, p)	G S	feasible feasible	covered+ covered+	low low	excessive medium
		E	G S	flooding flooding	covered++ covered++	low low	excessive excessive

  e + u e -1, e ∈ E (A.7f) B �� e ≤ u e , B �� e ≤ b �� e , B �� e ≥ b �� e + u e -1, e ∈ E (A.7g) T � e � e ≤ u e � , T � e � e ≤ u e , T � e � e ≤ b � e , T � e � e ≥ b � e + u e � + u e -2, e � , e ∈ E (A.7h) T �� e � e ≤ u e � , T �� e � e ≤ u e , T �� e � e ≤ b �� e , T �� e � e ≥ b �� e + u e � + u e -2, e � , e ∈ E K � e ≤ c � , K � e ≤ u e , K � e ≥ c � + u e -1, e ∈ E (A.7i) K �� e ≤ c �� , K e ≤ u e , K �� e ≥ c �� + u e -1, e ∈ E (A.7j) B � e , B �� e , G e , K � e , K �� e ∈ R + , e ∈ E (A.7k) T � e � e , T �� e � e ∈ R + , e � , e ∈ E (A.7l) u e ∈ {0, 1}, e ∈ E; z v ∈ {0, 1}, v ∈ V \ {o(d), t(d)}. (A.7m) Above, variables G � e , B � e , T � e � e , K � e and G �� e , B �� e , T �� e � e , K �� e

Acknowledgement: M. Pióro and I. Kalesnikau were supported by the National Science Center (Poland) [Grant 2015/17/B/ST7/03910 "Logical tunnel capacity control -a traffic routing and protection strategy for communication networks with variable link capacity"]. Research of M. Poss was supported by the ANR project ROBUST [ANR-16-CE40-0018].

Appendix A.1. Simple affine formula Appendix A.1.1. Case � E(d, p) = E + (d, p) In this case the PP formulation is obtained using the following equality which is valid for an arbitrary vector of link-dependent quantities (A(e), e ∈ E).

where

The formulation is more complicated than (19).

Case � E(d, p) = E In the considered case the PP formulation becomes simpler than (19) since now variables B e � are equal to b e � rather than to b e � • u e � , and variables T e � e express the product u e � • b e � rather than u e � • u e • b e � . Moreover, the loops in the optimal path will not appear due to the maximal range of the thinning formula.

The above formulation is computationally more efficient than its counterpart (19) for � E(d, p) = E(d, p). As before, we consider a given demand d ∈ D and a given path q ∈ � P(d) \ P(d) and an optimal solution π, λ of the dual (A.3). The minimum of the sum of such violations (taken