Nicolás Jara
email: nicolas.jara@usm.cl

Hermann Pempelfort
email: hermann.pempelfort@usm.cl

Gerardo Rubino
email: gerardo.rubino@inria.fr

Reinaldo Vallejos
email: reinaldo.vallejos@usm.cl

A fault-tolerance solution to any set of failure scenarios on Dynamic WDM Networks with wavelength continuity constraints

Keywords: Dynamic WDM Optical Networks, Blocking Probability, Wavelength Continuity, Wavelength Dimensioning, Wavelength Assignment, Routing, Fault Tolerance

Survivability of internet services is a significant and crucial challenge in designing optical networks. A robust infrastructure and transmission protocols are needed to maintain communications, despite the existence of one or more failed components on the system. Here, we present a generalized approach to tolerate any set of failure scenarios, to the extent the user can still communicate with the remaining components, where a scenario is an arbitrary set of links in a non-operational state.

To assess the survivability problem, we propose a joint solution to the issues listed next: the set of primary routes, a collection of alternate routes associated to each failure scenario, and the capacity required on the network to allow communication between all users, in spite of any considered failure scenario, while satisfying for each user a specific predefined quality of service threshold, defined in the Service Level Agreement (SLA).

Numerical results show that the proposed approach not only enjoys the advantages of low complexity and ease of implementation, but it is also able to achieve significant resource savings compared to existing methods. The savings are higher than 30% on single link failures and more than a 100% on two simultaneous link failures scenarios or in more complex failure scenarios.

I. INTRODUCTION

A remarkable issue to be solved in designing WDM optical networks is to ensure that the network will still be able to provide its transmission service after the failure of one or more of its links. The solution to this problem consists in providing the necessary infrastructure to rapidly re-establish communications between all source-destination pair of nodes affected by these link failures. This type of mechanism is known as "Fault Tolerance".

The frequency of link failures occurrences is significant. For instance, [START_REF] To | Unavailability analysis of long-haul networks[END_REF], [START_REF] Schupke | Survivability of Multiple Fiber Duct Failures[END_REF] reports measures of the mean time between failures of about 367 year/km. This failure frequency explains why failures on links may significantly impact the performance of the optical networks. For example, in a 26,000 km-long network such as NSFNet [START_REF] Ramaswami | Design of logical topologies for wavelength-routed all-optical networks[END_REF], there is an average of one fiber cut every 5 days. Moreover, the frequency with which two simultaneous links failures occur is high enough to be considered in the design process. In fact, Schupke [START_REF] Schupke | Survivability of Multiple Fiber Duct Failures[END_REF] reported that the probability of two simultaneous failures occurring in a network like NSFNet is approximately 0.0027, implying a downtime of about 24 hours per year, on average, which in addition to the high transmission rate of this kind of networks, means an unacceptable data loss.

The previous elements justify the need to provide an efficient methodology for multiple fault tolerance, which should ensure (with a certain probabilistic guarantee) successful communications among all network users, despite the occurrence of failures in some of the links, and at the lowest possible cost regarding the network infrastructure. Note that node failure may be modeled as the failure of all the links connected to the node, so the general problem can be modeled as a set of link failures.

The fault tolerance methods proposed so far generally have been devoted to finding alternative paths considering single link failure (one bidirectional link), affecting all the users with routes passing through the failed link in both directions. Then, the number of wavelengths in the network is dimensioned to tolerate this situation [START_REF] Schupke | Survivability of Multiple Fiber Duct Failures[END_REF], [START_REF] Ahuja | Single-link failure detection in all-optical networks using monitoring cycles and paths[END_REF]- [START_REF] Chu | Congestion-aware single link failure recovery in hybrid SDN networks[END_REF]. However, as already pointed out, the probability of occurrence of two or more simultaneous failures is high enough that it is needed to consider this kind of event in the design of the network. Some studies have focused on this 2-failures scenario [START_REF] Mukherjee | Alternate Strategies for Dual Failure Restoration Using p-Cycles[END_REF]- [START_REF] Jinno | Enhanced survivability of translucent elastic optical network employing shared protection with fallback[END_REF]. Also, some studies have considered more complex cases of failures, such as Disaster risk constraints and Shared-Risk-Group scenarios. Disaster risk constraints [START_REF] Serre | Assessing and mapping urban resilience to floods with respect to cascading effects through critical infrastructure networks[END_REF]- [START_REF] Ferdousi | Disaster-aware dynamic content placement in optical cloud networks[END_REF] considers the possible service disruptions in case of a natural disaster or a targeted attack, in which case, the failures affect various links simultaneously. The case of Shared-Risk-Group (SRG) [START_REF] Shao | Best Effort SRLG Failure Protection for Optical WDM Networks[END_REF], [START_REF] Babarczi | Optimal dedicated protection approach to shared risk link group failures using network coding[END_REF] considers cases where some fibers are placed physically together, even if they are connecting different optical nodes. This situation makes those fibers liable to physical cuts since they can be cut together at the same time.

The previous discussion supports the need to produce an adequate strategy concerning multiple fault tolerance scenarios, which should ensure (with a certain probabilistic guarantee) successful communications among all network users, notwithstanding the existence of failures in some of the links, with the lowest cost regarding the network infrastructure.

Here we propose a new fault-tolerance scheme, which we call the "Cheapest Shared Alternate Paths" method CSAP. In this approach, we go one step further concerning previous works, and we take into account the case of arbitrary sets of links failures scenarios, where a failure scenario is composed by a set of links in failure state. This means that we solve the fault-tolerance problem in its more general aspects.

The method also evaluates the number of wavelengths for each link of the network, ensuring that the blocking probability of any user request, of any user, is lower than a given corresponding predefined threshold (β c ), despite the possible occurrence of those simultaneous link failures. The value of β c is defined on the Service Level Agreement (SLA), signed by the service providers and their clients, which defines the minimum quality of service (QoS) acceptable for each user, measured here as a probabilistic guarantee. The definition of these bounds is obtained considering objective criteria, such as: different quality of service requirements [START_REF] Liao | Providing service differentiation for opticalburst-switched networks[END_REF]- [START_REF] Sam | Study of Qos Performance in Optical Burst Switched Networks (OBS)[END_REF]; and subjective decisions, such as network scalability requirements. Based on these QoS agreements, engineers must design the network fulfilling said QoS requirements. Thus, we assume that the β c values are given and acknowledge by the users and the network service providers.

The remainder of this paper is as follows. In Section III, we summarize the state of art of fault tolerance strategies. In Section III, we present the proposed method. In section IV we compare some results obtained by the proposed algorithm with those obtained with the current best methods in a set of different scenarios. Finally, the conclusions are given in Section V.

II. STATE OF ART

Next, we briefly describe the most common methods currently used to provide fault tolerance in optical networks with wavelength continuity constraints.

One of the most frequent ways used to address simple and double fault tolerance, called "1+1", can be found in [START_REF] Singh | Fault Tolerant Congestion Based Algorithms in OBS Network[END_REF], [START_REF] Ramamurthy | Survivable WDM mesh networks[END_REF], [START_REF] Wang | Performance Analysis of Circuit Switched Multi-Service Multi-Rate Networks With Alternative Routing[END_REF]. In this technique, a secondary route is associated with each primary one (with the restriction that they don't share any link), and the information is transmitted simultaneously through both of them, avoiding restoration delays in case of a failure. To dimension the number of wavelengths of each link -a task usually done by simulation-, each secondary route is considered as just another network route with a load equal to the corresponding primary one. The 1+1 method is also scalable to provide tolerance to K ≥ 1 simultaneous failures. In this case, for each user, K + 1 supplementary disjoint routes must be found, one as the primary route and the remaining K as secondary routes. Observe that a necessary and sufficient condition that allows this scheme to work is that the graph defined by the set of nodes and links is (K + 1)-connected.

Another fault tolerance strategy is known as "Shared Path Protection" (SPP) [START_REF] Jinno | Enhanced survivability of translucent elastic optical network employing shared protection with fallback[END_REF], [START_REF] Schupke | Capacity Efficiency and Restorability of Path Protection and Rerouting in WDM Networks Subject to Dual Failures[END_REF]- [START_REF] Pereira | A new algorithm for dimensioning resilient optical networks for shared-mesh protection against multiple link failures[END_REF]. In this scheme, the extra resources (wavelengths) assigned to the secondary routes can be shared by different users, and are assigned only when a fault occurs. The SPP can be executed in two different ways. The first one consists of running the algorithm offline, which means that the routes are calculated prior to the operation of the network (off-line SPP). The second way is the on-line implementation (on-line SPP). In this last case, the primary routes are computed before the network is operating, however, it must be executed again every time that one or more simultaneous failures occur, to compute alternate paths to the affected communications. For this reason, it is said that this is a proactive and reactive approach at the same time.

In [START_REF] Mukherjee | Alternate Strategies for Dual Failure Restoration Using p-Cycles[END_REF], [START_REF] Yadav | Intercycle switching (ICS)-based dynamic reconfiguration of p-cycle for dual-failure survivability of WDM networks[END_REF], [START_REF] Schupke | Multiple failure survivability in WDM networks with p-cycles[END_REF]- [START_REF] Ji | Dynamic pcycle configuration in spectrum-sliced elastic optical networks[END_REF] another method of fault tolerance called "p-cycle" is discussed, which provides survivability through fixed secondary routes that have a cyclic form. These cyclic routes are shared between several primary routes. One problem associated with this approach is that its applicability is very dependent on the size of the network, because it may introduce an excessive additional delay for a user in protection state on large networks. Also, to perform multiple fault tolerance, it requires a large number of cycles (e.g., hundreds of cycles for the 11 nodes pan-European COST 239 network [START_REF] Schupke | Multiple failure survivability in WDM networks with p-cycles[END_REF]), which is impractical from various points of view.

III. THE PROPOSED FAULT TOLERANCE METHOD

A. Model

The network topology is represented by a graph G = (N , L), where N is the set of network nodes or vertices and L is the set of unidirectional links (the arcs in G), with respective cardinalities |N | = N and |L| = L. The set of users X ⊆ N 2 , with cardinality |X | = X, is composed by all the source-destination pairs with communication between them.

We use an ON-OFF model (as in [START_REF] Jara | How much the wavelength dimensioning methods and a tightened qos provision impact on the dynamic wdm optical networks capacity?[END_REF]- [START_REF] Zukerman | On teletraffic applications to {OBS}[END_REF]) to represent the traffic between a given source-destination pair. Consider user c. During any of its ON periods, whose average length is t ON c , the source transmits at a constant rate (which is the rate associated with the wavelength). During an OFF period, with average length t OFF c , the source refrains from transmitting data. Observe that we address here the general case where the load can be different for each user, the socalled heterogeneous situation.

The used technology determines the constant transmission rate during the ON periods, but to simplify the presentation, it is our rate unity. Consequently, the traffic load of user c, denoted by c , is given by:

c = t ON c t ON c + t OFF c . (1)
Let R = {r c | c ∈ X } be the set of routes that enable communications among the different users, where r c is the route associated with user c ∈ X . The set R is known as the set of primary routes, since this set alone does not offer any fault tolerance to the possible failure of network links.

Let W = {W | ∈ L} be the set containing the number of wavelengths of each unidirectional network link, where W , ∈ L, is the number of wavelengths on link . The value W , for every ∈ L, must be evaluated so that the blocking probability BP c of each user c ∈ X is less than or equal to a given pre-specified threshold β c , and the total number of available network wavelengths is as small as possible (saving resources).

Remark that the pre-defined threshold value β c can be different for each network user, which means that we treat the general case where there are classes of users with different quality of services (QoS).

As in several works [START_REF] Zapata-Beghelli | Dynamic Versus Static Wavelength-Routed Optical Networks[END_REF], [START_REF] Ramaswami | Optical Networks: A Practical Perspective[END_REF], [START_REF] Jara | A method for joint routing, wavelength dimensioning and fault tolerance for any set of simultaneous failures on dynamic WDM optical networks[END_REF], in this proposal the total network cost C net is defined as the sum of all wavelengths of all network links, that is, C net = ∈L W . Because we are considering fault tolerance capabilities, this cost must includes all the additional wavelengths needed to provide tolerance to the desired failures scenarios.

Let Ω be the set of every possible failure scenarios, where each scenario is a subset F, with F ⊂ L, a set of links in failure state. The method explained below can be applied to any possible set of failure scenarios. For example, every possible single failure scenario (|F| = 1); every possible double link failure scenario (|F| = 2); a node failure, where all the links connected to that node are considered non-operational; disaster risk constraints [START_REF] Dikbiyik | Minimizing the disaster risk in optical telecom networks[END_REF], [START_REF] Ferdousi | Disasteraware data-center and content placement in cloud networks[END_REF] where all the links affected by the disaster are considered nonoperational; Shared-Risk-Group (SRG) [START_REF] Zang | Path-protection routing and wavelength assignment in WDM mesh networks under shared-risk-group constraints[END_REF], where F is composed by every link that can be affected by the same physical cut. Note that the previous examples consider all kind of failure scenarios already treated in the literature, however the method proposed here is applicable to any set of failure scenarios, with the condition that the network remains connected after any of the failure scenarios considered, which implies that the method can provide alternative routes for all affected users.

B. Definitions and sub-procedures needed by our method

Since the graph representing the network topology and the set of users are fixed data, as well as the upper bounds β c , ∀c ∈ X (the maximum acceptable blocking probabilities of the users), we omit them in the list of the parameters of the procedures. For simplicity, when we refer to the network capacity, we write C net , because we must change the capacities of the links many times during the computational process.

Some definitions required for the explanation of the method are presented in the following list:

• G -F = (N , L \ F), is the partial graph of G (same
nodes, part of the edges), containing only the non-failed links, where F contains the set of failed links;

• X F = {c ∈ X | r c ∩ F = φ},is the set of users c
affected by the failure F;

• A F = {r c ∈ R | r c ∩ F = φ},
is the subset of the routes in R disables because of the failure F; • R F is a set of routes that replace those in A F when all links in F are failed; • S F is the total set of routes guaranteeing fault tolerance to the failure event "all links in F fail". That is, the set defined by

S F = R \ A F ∪ R F ; • C F = {C |
for all L \ F } is the costs (to be defined later) of each link non-affected by the failure F.

The method also needs a few sub-procedures to work. They are described next.

• PrimaryRoutes(). A procedure that computes a set of primary routes. The selection of the routes can be made by any available technique, e.g., Dijkstra algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF].

To represent the execution of this sub-procedure, let us symbolically write {R, W} := PrimaryRoutes() • SecondaryRoutes(). Considering that we have a set of failure links F, the set of costs C F , and a set of users X F affected by the failure of the links in F. We want to find a new set of routes allowing to connect each user in X F despite the failure scenario F, while still satisfying the QoS required by each user.

The search for the new routes is done as follows. We run Dijkstra's algorithms looking, for each user c ∈ X , the cheapest route, where the link costs are now given by the link costs in C F (explained later in the algorithm). This procedure creates a new set of routes, that we denote R F . Symbolically, the execution of this sub-procedure is done by calling R F := SecondaryRoutes(X F , F, C F ). • Dimensioning(). This procedure consists in finding, for each link ∈ L, a capacity W such that the endto-end blocking probability BP c of every user c ∈ X passing through the link is less than the given threshold β c . For different reasons, the usual dimensioning procedures consider homogeneity in the links' capacities, that is, look for the minimum capacity W, the same on all links, such that the performance objective is reached [START_REF] Zhang | Dimensioning WDM Networks for Dynamic Routing of Evolving Traffic[END_REF]- [START_REF] Koganti | Analysis of routing and wavelength assignment in large WDM networks[END_REF]. We will then follow here the same approach, because this can facilitate further comparisons with existing methods. The idea is simple: we are given the operational links of the networks, the set of routes R (because the procedure is used for a diverse set of routes), and the set of quality of service bounds β c . We then initialize the network capacity W by value 1 and we evaluate the blocking probabilities per user; then, we check if the blocking probability of each user is less than the one defined on the SLA. If the condition is satisfied, we stop the algorithm. If not, we increase W by 1 and we repeat the procedure. Let us define Q ⊆ X , as the set of users with their QoS constraint satisfied (maximum acceptable blocking probability). Then, symbolically we evaluate the dimensioning sub-procedure by writing: Dimensioning(L, R, β c ). Figure 1 contains in pseudoalgorithmic form the procedure just described.

{W} = function Dimensioning(L, R, β c ) 1 Q := φ; 2 foreach link 3 W := 1; 4 do 5 BP c := Blocking(G, R); 6 foreach user c / ∈ Q 7 if BP c ≤ β c 8 Q := Q ∪ {c}; 9 if Q ≡ X 10 for all ∈ L 11 W := W + 1; 12 until Q ≡ X 13 return W

C. Fault Tolerance method

Figure 2 contains a diagram with the inputs required, the condition to be guaranteed, and the outputs obtained by the method execution.

The inputs are: the network topology G = (N , L), which can be any network topology; each user traffic load c , for all users in c ∈ X (notice that, the value c of each user c can be different); and the set Ω = {F|F ⊂ L} composed by all the link failure scenarios to be considered by the method execution.

The constraint to be satisfied by the method is to guarantee a given blocking probability β c to each network user c, predefined on the Service Level Agreement (SLA).

The method's outputs are the set of primary routes R, allowing to provide communication to each network user c, for all c ∈ X , under the condition of no link failure; the set of alternative routes S F , for each failure scenarios F ∈ Ω, which allow communicating in spite of the links in F are not operational; and the amount of wavelength W necessary on each network link , for all ∈ L (considering every possible failure scenario in Ω), fulfilling the QoS constraints to each user in spite of the failure occurrence of any scenario in Ω.

We use LIBPE method [START_REF] Jara | Blocking Evaluation and Wavelength Dimensioning of Dynamic WDM Networks Without Wavelength Conversion[END_REF] to compute the users' blocking probabilities necessary to evaluate the quality of service offered to each user c. This procedure is an accurate and fast technique to evaluate the blocking probability of each user, on networks with wavelength continuity constraints. Note that fast evaluation of the QoS is significant, since solving the previously listed problems (the routing of the primary and secondary paths, with the corresponding dimensioning of each failure scenario), it is necessary to compute the blocking probability a lot of times (hundreds) considering all failure cases of the set Ω, and in each of these cases to execute the dimensioning procedure. Therefore, simulation techniques are not a possibility due to the time-consuming task involved.

Additionally, the method depends of the wavelength assignment scheme used during the network operation. These problem refers to the procedure to search for an available wavelength during network operation [START_REF] Ramaswami | Optical Networks: A Practical Perspective[END_REF], [START_REF] Mukherjee | Optical WDM networks[END_REF]. The wavelength assignment problem has been widely covered in the literature [START_REF] Ramaswami | Optical Networks: A Practical Perspective[END_REF], [START_REF] Koganti | Analysis of routing and wavelength assignment in large WDM networks[END_REF]- [START_REF] Chatterjee | Review and Performance Analysis on Routing and Wavelength Assignment Approaches for Optical Networks[END_REF], and First-Fit is the most popular procedure in the literature since it performs better in terms of blocking probabilities, with low complexity. As a consequence, on our research we use this procedure to allocate the wavelengths.

In algorithmic form, the CSAP method is presented in Figure 3.

In line 1, by using the sub-procedure PrimaryRoutes, we use Dijkstra algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF] to obtain an initial set of primary routes R. However, it must be noted that the fault-tolerance mechanism presented here, is not associated to any particular routing decision, thus any routing method can be applied to obtain the primary routes.

Then in line 2, we include the set of every possible failure scenarios Ω, where each of these scenarios is a subset of failed network links F. To explain how the procedure works, initially, assume that the only possible failure scenario is the simultaneous failures of all links in a specific subset F of L.

In lines 3 to 7, we first start by finding replacement routes in case of the failure of all links in the subset of links F. If a route r c does not use any link of F, it is not changed. However, for all users c whose route r c ∈ R uses at least one link of F (that is, for all c ∈ X F ), we must find a new route that avoids the links of F. To this end, for every link ∈ L \ F, we define its cost C through the expression:

C = e -, (2)
where is the traffic load offered to the link by the users non-affected by the failed links, and is the mean traffic load on all the links , such that ∈ L \ F (the non affected links). Said cost function (C ) stands for one of many ways to represent how unbalance the traffic load is on the network, function CSAP() // ---input: the graph (the network), the users, // the bounds on the blocking probabilities, // and the set Ω of links failure scenarios, // where at most one of the events 'all links in F // fail simultaneously' occurs, all seen as global variables // ---output: the primary routes, the secondary routes // and the wavelengths per link // first compute the primary routes therefore seeking to balance the network traffic load, since balancing the network load may achieve remarkable savings by using network resources as even as possible [START_REF] Neghabi | Load Balancing Mechanisms in the Software Defined Networks: A Systematic and Comprehensive Review of the Literature[END_REF], [START_REF] Vallejos | Join routing and dimensioning heuristic for dynamic WDM optical mesh networks with wavelength conversion[END_REF] Then, with these C values as weights, we run the Dijkstra's algorithm to find the cheapest route for each user c ∈ X F . The set of all these routes are denoted by R F . Symbolically, we execute the call: R F := SecondaryRoutes(X F , F, C F ).

After that, line 9 defines the set of routes S F :

S F = R \ A F ∪ R F .
In words, S F is the set of routes to be used when all links in F are failed. Under this condition, we must dimension the links again, because we must always respect the QoS constraints. For this purpose, we restrict the analysis to the graph G -F , that is, we remove the links in F from L. Then in line 10, we run a dimensioning phase. In pseudoalgorithmic form, we execute the function call

W F := Dimensioning(L \ F, S F , {β c , ∀c ∈ X \ X F }).
Repeating the steps explained above for each different failure scenario (line 2 to 9), we obtain a set of secondaries routes for each failure scenario F of Ω, and the corresponding links dimensioning for each failure scenario.

To finish, in lines 11 to 12, we compare each W F , , the number of wavelengths of link under each failure scenario F, for all ∈ L, and the procedure determines the capacity of the link as the maximum between them. Formally, we add a procedure Max (), that performs this task. We symbolically write W := Max (W ,1 , ..., W ,|Ω| ), where W ,F is the link capacity when failure scenario F takes place. Together each final link capacity W , ∈ L conform the final dimensioning set W.

IV. NUMERICAL RESULTS

To quantify the quality of the CSAP method, the proposed solution should be compared against the optimal solution. However, it is known that the Routing and Wavelength Dimensioning (RWD) problem is an NP-complete problem [START_REF] López | Elastic Optical Networks. Optical Networks[END_REF]. In fact, those who solved this problem optimally only have been able to achieve it to very small networks (with less than 10 nodes) [START_REF] Meza | Routing and spectrum assignment for elastic, static, and without conversion optical networks with ring topology[END_REF], [START_REF] Vallejos | Joint routing and dimensioning of optical burst switching networks[END_REF]. Consequently, for real network topologies (dozens to hundreds of nodes), the faulttolerance problem cannot be optimally solved, since it solves the RWD problem multiple times. Given this situation, our best alternative was to compare the CSAP method with those methods considered as the most competitive at this moment.

In order to make a comparison, the most important metrics on the survivability problem are the capacity of the network, and the delay in the restoration procedure in case of the occurrence of failures. Next, we analyze which are the most suitable methods to be compare with.

As mentioned in the introduction, there are several types of fault tolerance algorithms proposed so far, such as Shared Path Protection, p-Cycle, and 1+1. Hereafter, we discuss the pertinence in comparing CSAP with each of these different types of algorithms. Shared Path Protection (SPP) Method. As discussed in this paper introduction, this strategy provides tolerance to multiple network links failure. There are two methods for implementing this algorithm (on-line and off-line). Both methods require between 40 to 80% of additional wavelengths (compared to the case without fault tolerance) to provide single link fault tolerance capability [START_REF] Schupke | Capacity Efficiency and Restorability of Path Protection and Rerouting in WDM Networks Subject to Dual Failures[END_REF]. Another aspect that must be considered is that the SPP off-line method has the additional weakness that the percentage of restoration obtained (percentage of users that remain connected in case of link failure) is deficient (80% to 90% [START_REF] Schupke | Capacity Efficiency and Restorability of Path Protection and Rerouting in WDM Networks Subject to Dual Failures[END_REF]), which means that it does not provide complete fault-tolerance to the network. Therefore, it is not a possible competitor to the method proposed in this work, which ensures that the blocking probability pre-established by the network designer is satisfied. On the other hand, the implementation of the SPP-online method requires to run on demand a route search algorithm (whenever one or more links fail) to find an alternative route to each affected user. Evidently, this on-line strategy causes a slow re-routing, which added to the fact that many of the applications that use computer networks require swift on-line responses in case of failures [START_REF] Saleh | Technology and architecture to enable the explosive growth of the internet[END_REF], which implies that this type of method does not represent a practical fault-tolerant mechanism for many practical applications. Due to the facts just commented, the SPP method was not considered for comparison. The p-cycle Method. As discussed early, to provide tolerance to multiple failures, this method requires a large number of cycles (which implies a high cost when defining secondary routes), so it is not scalable for multiple faults. Given the fact that in this paper, we consider the multiple fault-tolerant cases, it is unreasonable to compare our method with the pcycle one. Method 1+1. This method provides tolerance to multiple failures, using as many disjoint routes as simultaneous link failures considered. It solves the problem of primary and secondary routes before the network dimensioning (off-line) sub-task. Then, the number of wavelengths is computed, having as a constraint to provide enough resources to all routes, and providing sufficient information to re-route each user in case of failure. Consequently, 1+1 is a suitable faulttolerance method to compare with our algorithm.

In summary, the most appropriate methods for comparison is the 1+1 for the fault-tolerance mechanism. Additionally, reviewing current methods of Routing, we notice that the algorithms most commonly referenced today, and considered the best so far, use the shortest path, together with a First Fit wavelength assignment scheme. This is SP-FF (Shortest Path with First-Fit allocation scheme) [START_REF] Zapata-Beghelli | Dynamic Versus Static Wavelength-Routed Optical Networks[END_REF], [START_REF] Ramaswami | Optical Networks: A Practical Perspective[END_REF], [START_REF] Koganti | Analysis of routing and wavelength assignment in large WDM networks[END_REF], [START_REF] Chatterjee | Review and Performance Analysis on Routing and Wavelength Assignment Approaches for Optical Networks[END_REF], [START_REF] Charbonneau | A survey of advance reservation routing and wavelength assignment in wavelength-routed WDM networks[END_REF]. Therefore, the routing strategy used on the 1+1 faulttolerance method is the SPFF. Both methods together are denoted SPFF1+1 in the text.

To assess the blocking probabilities in both SPFF1+1 and CSAP strategies we use the mathematical method called LIBPE [START_REF] Jara | Blocking Evaluation and Wavelength Dimensioning of Dynamic WDM Networks Without Wavelength Conversion[END_REF], and the final results were validated by simulation.

As previously discussed, the Wavelength Dimensioning method most commonly used nowadays is the homogeneous dimensioning, that is, all links have the same amount of wavelengths. Consequently, in this work, we consider a homogeneous dimensioning strategy on both fault-tolerance mechanisms.

To evaluate the performance of the methods under different scenarios, the algorithms were executed for different real network topologies, having different sizes and different degrees of connection d, where d is the average number of neighbors of a node in the network. Some of the selected topologies and their respective parameters N , L and d are shown in Figure 4.

The total network capacity C net is one of the metric chosen to compare the algorithms, which is given by the total number of wavelengths necessary, to satisfy the users QoS constraints, including the primary and secondary routes needed on each different failure scenario F ∈ Ω. Thus, in Figure 5 we show the total cost C net obtained by the CSAP and SPFF1+1 methods for the case of a single link failure, as a function of the traffic load, for different network topologies, and a maximum acceptable blocking user of 10 -3 . In Figure 6 we show the C net value for

C net

UKNet, Simple Fault Tolerance, β c = 10 -3

CSAP SPFF1+1

Figure 5. Total number of wavelengths Cnet obtained with our method (CSAP) and SPFF1+1 on Eurocore, NSFNet, EON and UKNet real mesh network topologies, for different connection traffic loads, with a blocking probability threshold βc equal to 10 -3 in the single fault tolerance case.

the same methods, but double-link failures (i.e., any pair of simultaneous link failure possible). We show only single and double link failure scenarios. This is because to appropriately represent another kind of failures scenarios, such as SRG or Disaster Risk constraint may be hard to replicate and may achieve a disconnected network. However, as stated before, the algorithm developed can quickly evaluate any fault tolerance scenario.

Note that, for all the scenarios evaluated in our experiments for the case of single link failure, the SPFF1+1 method requires in general 30% more wavelengths (for = 0.3, which is a representative network load [START_REF] Saleh | Technology and architecture to enable the explosive growth of the internet[END_REF]) than the cost of the method proposed herein. Moreover, in the case of tolerance to two simultaneous failures of links (Figure 6), the CSAP method also significantly outperforms the SPFF1+1 technique. In this case, the SPFF1+1 method requires in the order of 160% more wavelengths (always for = 0.3 [START_REF] Saleh | Technology and architecture to enable the explosive growth of the internet[END_REF]) than our proposal. Remark that for each scenario analyzed herein, both compared methods achieve to connect the same users with the same QoS requirements (maximum acceptable blocking probability), but our proposal requires significantly fewer resources than SPFF1+1 to do so.

To provide a more in-depth discussion of the results obtained by CSAP, next we present an analysis about the memory size the methods need, and the time required to access the memory during the network operation (Sub-Section IV-B and IV-C respectively).

A. Complexity Analysis

The total computational complexity of the CSAP method depends on the wavelength dimensioning algorithm used to compute the network links capacities, which in turn depends on the blocking probability evaluation techniques used. This

CSAP SPFF1+1

Figure 6. Total number of wavelengths Cnet obtained with our method (CSAP) and SPFF1+1 on Eurocore, NSFNet, EON and UKNet real mesh network topologies, for different connection traffic loads, with a blocking probability threshold βc equal to 10 -3 in the simultaneous double fault tolerance case.

dependency is important since the dimensioning procedure is executed as many times as failure scenarios considered in the set Ω. Even more, the dimensioning algorithm executes several times the blocking probability procedure to calculate the network capacity. Therefore, the computational complexity of the proposed strategy is calculated in three stages: the Blocking probability evaluation, the wavelength dimensioning solution, and the survivability solution. a) Blocking Probability: As mentioned in this work, we used the method LIBPE [START_REF] Jara | Blocking Evaluation and Wavelength Dimensioning of Dynamic WDM Networks Without Wavelength Conversion[END_REF] to compute the blocking probability of each network user for a given network capacity W . LIBPE procedure is an iterative procedure, thus let the value I be the number of iterations that the method executes to converge in a solution, and r be the mean length of all the users path. The iterative solution executes sequentially:

• an update of the t OFF values of all the network users c ∈ X (complexity O(X));

• per network link ∈ L (O(L)), the method solves the links blocking probability. It solves a Markov chain covering all the users passing through the given link, thus the complexity is given by the mean number of user per link O( X•r L ). Then, the stage complexity is given by O(X • r);

• and finally the method evaluates the blocking probability for all the users c ∈ X , with complexity O(X • r).

In a nutshell, the blocking probability then iterates I times executing the 3 sequential stages on all the wavelengths W , thus with a complexity O(I • W • (X + X • r + X • r)). This leads to a computational complexity of

O(I • W • X • r). (3)
b) Wavelength Dimensioning: the computational complexity of the algorithm displayed in Algorithm 1 is as follows. From line 2 to 3 the complexity is O(L). Then, the iterative section starts from line 4 to 12, solving the blocking probability (complexity O(I •W •X •r) IV-A0a); then checking for each user if they succeeded their blocking threshold O(X); and finally updating the links capacity (O(L)). The iterative section is executed until the wavelength dimensioning is computed, thus W times. Consequently, the computational complexity together is (O(W (X + I

• W • X • r + L), leading to O(W 2 • I • X • r). (4)
For instance, in an Eurocore topology, the number of nodes is N = 11, L = 100 unidirectional links, X = 110 users, and the mean length of users' routes is r = 2 using Dijkstra algorithm to compute the users' path. Now, for a mean traffic load = 0.3 scenario, the wavelength dimensioning obtain is C net = 400, thus W = 4, and the number of iterations performed were I = 5. This leads us to 17600 instructions. In a common PC nowadays, the instructions are measured in MIPS (millions of instructions per second), leading to 1.76 • 10 -2 seconds. In LIBPE's article [START_REF] Jara | Blocking Evaluation and Wavelength Dimensioning of Dynamic WDM Networks Without Wavelength Conversion[END_REF], the dimensioning procedure execution time was measured, obtaining for the exact same example 3.20 • 10 -2 seconds. Consequently, the computation complexity is well obtained. c) CSAP method: the computational complexity of this method (shown in Algorithm 3) is then presented.

• In line 1, the primary routing problem is solved using Floyd-Warshall's (or Dijkstra's) algorithm, known to have an O(N 3 ) computational complexity; • from line 2 to 9 the secondary paths are computed.

Be Z the number of failure scenarios in Ω, and F the maximum number of simultaneous links in failure state on a given scenario in Ω. We iterate for all the failure scenarios considered Z (line 2), computing the cost to all the operational links from line 3 to 6, with O(L • X•r L in line 3 to 4, O(L) in line 5, and O(L) in line 6 to 7. Later, the secondary routes are computed, executing Dijkstra (O(N 2 ) for each user affected by the failure scenario (O(F • X•r L )). Finally, in line 9 the dimensioning is executed with the previously calculated complexity O(W 2 • I • X • r).

• The last stage (line 10 to 11) computes the final wavelength dimensioning, comparing the dimensioning obtained on all the Z scenarios in Ω, then the complexity is O(L • Z).

Summarizing, the complexity is given then by the sum of the 3 stages. This is:

O(N 3 )+ O Z L • X • r L + L + L + N 2 • F • X • r L + O(Z • W 2 • I • X • r)+ +O(L • Z). (5)
Consequently, the final computation complexity of the complete CSAP procedure is as follows:

O Z • F • X • r L • N 2 + Z • W 2 • I • X . (6)

B. Memory size

Other aspects that influence the network performance are the storage size used by the routing tables, and the delay imposed by the routing procedure when each user attempts to transmit over a path.

The routing tables storage size depends on how many routes are computed to each user by the implemented procedure. If the 1+1 method provides fault tolerance to a single link failure, it computes only one secondary path for each user. Likewise, to offer fault tolerance to simultaneous double link failure, the 1+1 technique provides two secondary routes per user. Therefore, the number of entries stored on the routing tables are two and three times the number of users in X , to provide single and double fault tolerance, respectively (with centralized management).

On our method, the number of paths computed changes based on the different failure scenarios and the network topology (size and node degree) evaluated. This situation occurs because, on each failure case, our method searches a new route to each user affected by the failed links on that scenario. In the executed experiments, our method required a similar number of alternate paths to provide single and fault tolerance than 1+1. For example, on the Eurocore network topology, to provide single and double fault tolerance, our method computed the same number of alternate paths than 1+1. Moreover, on a bigger network such as Arpanet, our methods required, on average, three and four paths per user to provide single and double fault tolerance, respectively.

C. Routing delay

During network operation, there is a delay incurred by the routing procedure, due to the time required to find the corresponding path and to transmit by it successfully, or to be finally blocked. We define this delay as τ (A), where A is the algorithm considered (SPFF1+1 or CSAP). Since both methods compared in this work use fixed predefined routes, the delay is mainly composed by the time needed to access the routing table and the corresponding transmission. Note that one access can be considered as a constant T , then, τ (A) measures how many times it is required to access the routing tables to have successful communication, or to be blocked, using the routing scheme obtained by the method A.

Note that both methods store the alternate paths in routing tables, but the technique to route each user on every communication request differs. The 1+1 fault tolerance scheme sends the information on each alternate path every time the user attempts to transmit; thus the access to routing tables requires to read two routes per user on single fault tolerance and three routes per user on simultaneous double fault tolerance. On the other hand, our method has only one route per link failure case; thus, it requires to read only one entry on the routing table on each attempt of transmission.

In a nutshell, the τ (A) value per method is:

• τ (SPFF1 + 1 ) = 2 • T , considering tolerance to single link failure. • τ (SPFF1 + 1 ) = 3 • T , considering tolerance to simultaneous double link failure. • τ (CSAP ) = T , for any link failure scenario. showing the advantage of the CSAP method respect to the routing delay.

V. CONCLUSIONS

A novel method was proposed to solve the fault-tolerance problem for any possible set of scenarios, where each scenario is defined by a specific set of link failures.

The method differs considerably from those published so far, obtaining better results in terms of the necessary number of wavelengths and delay. Additionally, the dimensioning method does not make any distinction between primary and alternative routes, with the constraint that it only evaluates scenarios that may happen during the network operation (for each user, it considers either a primary or a secondary route, not both simultaneously). Consequently, the method allows sharing the resources between all the secondary routes, while guaranteeing a maximum blocking probability to each network user.

The proposed fault tolerance technique is scalable to any set of simultaneous link failures, as long as the network topology allows re-connection via the links that remain operational. This scheme is executed before the network operation, requiring a few seconds to solve the task. This fast execution also allows to quickly solve any link failure scenario during network operation if needed (for example, traffic load variations). Additionally, the network operation based on our approach is fast and straightforward, since the routes (both primary and secondary) are stored in routing tables and consulted only on demand.

Figure 1 .Figure 2 .

 12 Figure 1. Dimensioning procedure to compute the number of wavelengths on the network.

1 RFigure 3 .

 13 Figure 3. Algorithm for solving the fault tolerance problem, providing alternative routes to any failure scenario in Ω.

Figure 4 .

 4 Figure 4. Some of the mesh networks evaluated. The number of links refers to the amount of bi-directional arcs. For instance, the picture shows the EON network topology with 39 edges, which corresponds to 78 arcs. The parameter d is a measure of density: if the graph has a arcs (twice the number of edges) and n nodes, d = a/ n(n -1) .

  Fault Tolerance, β c = 10 -3

ACKNOWLEDGMENTS

This work received financial support from FONDEF ID14I20129, CONICYT and STICAMSUD 19STIC-01. These projects are then gratefully acknowledged.