This is a post-peer-review, pre-copyedit version of an article published in Third International Congress on Information and Communication Technology. Advances in Intelligent Systems and Computing. The final authenticated version is available online at: https://doi.org/10.1007/978- 981-13-1165-9_73 Improving network availability – A design perspective Rita Girão-Silva1 , Lúcia Martins1 , Teresa Gomes1 , Abdulaziz Alashaikh2 , and David Tipper2 1 Department of Electrical and Computer Engineering, University of Coimbra, 3030-290 Coimbra, Portugal INESC Coimbra, 3030-290 Coimbra, Portugal {rita,lucia,teresa}@deec.uc.pt 2 University of Pittsburgh, Pittsburgh, PA, USA
[email protected],
[email protected]Abstract. The availability of the resources in communication networks is critical, due to the impact that possible disruptions of communication services may have in the society. Therefore providing adequate levels of availability for every demand in a network is of paramount importance. In this work, we focus on the topological structure of a network to select a set of links that provide a high availability path to be used by the different end-to-end demands. This set of links constitutes a high avail- ability structure (the spine) and is used as the working path for each demand. The backup path for each demand is edge-disjoint with the cor- responding working path. This path pair provides end-to-end protection for critical service demands in the network. An exact formulation of the problem is presented and solved for small instances networks. A heuristic resolution approach with centrality measures is also put forward, with an experimental study comparing the exact and the approximate results. Keywords: availability, network design, path protection, heuristics, cen- trality measures 1 Introduction Communication networks are a critical infrastructure of our society, as is recog- nized in PDP-21 [1]. Hence improving network resilience and ensuring critical services are maintained in the presence of challenges [2] has been the object of extensive research [3–8]. The concept of Quality of Resilience was introduced in [9] for service differen- tiation based on its availability and other related parameters. QoR can be used for adequately and quantitatively compare network recovery schemes deployed in a given network architecture [10]. Some works seek to route demands taking into account a desired availabil- ity. In [11] the authors propose an algorithm for dynamic traffic, called 3W- availability aware routing (3WAR), assuming historical data allows to know the availability of the links depending on their location, month and time of day. A mathematical model is developed for calculating the availability of a shared- protected connection in [12] and the problem of provisioning connections cost effectively while satisfying the connections’ availability requirements is addressed in optical wavelength-division multiplexing (WDM) meshed networks. A theo- retical analysis on service availability in elastic optical networks (EONs) is pre- sented in [13]. An availability-aware differentiated protection (ADP) algorithm and a service availability-aware backup reprovisioning strategy are proposed. The use of different recovery or protection techniques leads to different re- covery time and service availability values. However in [14] the values obtained for the availability of three classes (gold, silver and bronze) were not significantly different for gold (with dedicated protection) and silver (with shared protection). Also relevant, was the fact that the gold class availability was significantly below the required value (i.e. four to six 9’) for mission-critical services. Improving the availability of selected network elements (nodes and/or links) is a different approach to achieve high availability. In [15] the authors select some links to be shielded, making them resilient to failures. Given a desired end-to-end availability, several variants of a heuristic for selecting links for an availability upgrade is proposed in [16]. In [7, 17, 18] the problem of cost efficiently achieving jointly high levels of availability and service differentiation to traffic flows was addressed. The basic idea is to consider that there is a high availability portion of the network and its elements (nodes and edges) may have an increased availability by using for instance more reliable equipment and/or redundant equipment in parallel. This portion of the network was designated the spine. The spine was designed to be a spanning tree at the physical layer, and should be used to route flows of higher QoR classes [7, 17, 18]. The concept of the spine is explored in [18] as a strategy to ensure a high availability to critical services, while providing different levels of resiliency for other (less demanding) services. In [17] a first approach on how the structural properties of the network topol- ogy could be used in a heuristic to select a suitable spine, was presented. In that work the availability of edges was not considered in the spine selection. If the minimum cost spanning tree was not admissible, link pruning was performed until an admissible tree was found (a tree is only admissible if for all working paths in the spine a edge disjoint backup can be found). Hence in [17, 18], after the first tree, no assurance is given with respect to the order of the generated spanning trees for the considered edges weights. In the present work an exact formulation to design the spine according to a specific function is proposed, and several metrics for enumerating the possible spanning trees are evaluated. Note that no cost function is considered in this work, as it is very difficult to obtain realistic cost functions for improving availability. Moreover the objective of the work is to check the adequacy of the proposed metrics, using a small number of spanning trees (generated by non-decreasing cost based on the relevant met- ric), for obtaining in a reasonable time a spine, with a performance close to the solution of the formulated optimization problem. The paper is organized as follows: after this introductory section which in- cludes the description of related work, an exact formulation to devise the spine according to a specific function to be optimized is described in section 2. In section 3, we present the used heuristic for the spine calculation and the corre- sponding paths availabilities. The experimental results are presented in section 4, followed by the conclusions section, where further work is also proposed. 2 Exact formulation We present an exact formulation for finding an edge-disjoint path pair for each demand in the network, taking into account the availability of each edge. The set of edges used in the working paths (WPs) of all the demands constitutes a spanning tree. For each WP in the spine, an edge-disjoint path will be devised, which will be the backup path (BP) for the corresponding demand. The devised formulation focuses in finding the spine, i.e. in finding the most available WPs, as these are the paths used in regular conditions. Only in the case of failures in any of the components of the WP (a node or an edge) will the BP be used. Therefore, the focus is not in the path pair (WP and BP) and we only require an edge-disjoint path pair to be found for each demand (not necessarily the most available path pair). This is the reason why the objective functions in both exact formulations are related with the availability for the WP only. Moreover, in [18] the maximization of the WP availability was shown to be closely related to the maximization of the path pair availability. In this section, we begin by defining the notation, followed by the presentation of the exact formulation problems. 2.1 Notation Sets – N is the set of physical nodes in the graph. – E is the set of physical undirected edges in the graph. – L is the set of directed links in the graph. We may consider an undirected edge with end nodes i and j as a pair of directed and opposite links (i, j) ∈ L and (j, i) ∈ L. – F is the set of end-to-end demands or flows. A flow f ∈ F between nodes s ∈ N and t ∈ N may be identified by its source node s and its destination node t, i.e. we assume f ≡ (s, t) ∈ F. Availability – a(l) is the availability of edge l ∈ E. If an edge is identified by the cor- responding directed and opposite links (i, j) ∈ L and (j, i) ∈ L, we may identify the availability of each link as aij and aji , respectively. In our prob- lem, we will assume the availability of each edge l depends on the length (distance between the end nodes) of each edge, given by d(l). In particular, a(l) = 0.99987d(l)/(250×1.6093) , as in [19]. – AW P Q (s,t) = l∈W P(s,t) a(l) is the availability of the WP of flow (s, t). Performance measures related to the availability – AW P = |F1 | (s,t)∈F AW P P a (s,t) is the average value of the availability for the WP WPs A(s,t) of all the flows. – AWm P = min(s,t)∈F AW P (s,t) is the minimum value of the availability for the WP WPs A(s,t) of all the flows. Variables to be used in the exact formulation of the problem: – zij is 1 if the link (i, j) is in the spine and 0 otherwise. – xst ij is 1 if the link (i, j) is in the WP of the flow (s, t) ∈ F and 0 otherwise. st – yij is 1 if the link (i, j) is in the BP of the flow (s, t) ∈ F and 0 otherwise. 2.2 Problem 1: Maximization of the sum of availabilities of the WPs of all the flows In problem 1, the objective function is the maximization of the sum of availabil- ities of the WPs of all the flows, which is equivalent to the maximization of the average value of the availability for the WPs of all the flows. The problem is formulated as: X max AW P (s,t) (1) (s,t)∈F subject to X X 1 if h = s xst hj − x st ih = −1 if h = t ∀h ∈ N , (s, t) ∈ F (2) 0 otherwise (h,j)∈L (i,h)∈L X X 1 if h = s st st yhj − yih = −1 if h = t ∀h ∈ N , (s, t) ∈ F (3) 0 otherwise (h,j)∈L (i,h)∈L xst st ij + xji ≤ 1 ∀(i, j) ∈ L with i < j, (s, t) ∈ F (4) st st yij + yji ≤1 ∀(i, j) ∈ L with i < j, (s, t) ∈ F (5) X X xst hj + xst ih ≤ 2 ∀h ∈ N , (s, t) ∈ F (6) (h,j)∈L (i,h)∈L X X st st yhj + yih ≤2 ∀h ∈ N , (s, t) ∈ F (7) (h,j)∈L (i,h)∈L xst st ij + yij ≤ 1 ∀(i, j) ∈ L, (s, t) ∈ F (8) xst ij st + yji ≤1 ∀(i, j) ∈ L, (s, t) ∈ F (9) zij ≥ xst ij ∀(i, j) ∈ L, (s, t) ∈ F (10) zij = zji ∀(i, j) ∈ L with i < j (11) X zij ≤ |N | − 1 (12) (i,j)∈L,i<j Y AW P (s,t) = aij ∀(s, t) ∈ F (13) (i,j)∈W P(s,t) xst st ij , yij , zij binary (14) Constraints (2) and (3) represent flow conservation constraints for the WP and the BP, respectively. Constraints (4)-(7) guarantee a loop free routing for the WPs. Constraints (8)-(9) ensure the WP and the BP are link-disjoint. Constraints (10)-(12) deal with the formation of a minimum spanning tree in the network, which is the spine (composed of all the links in the WPs of all the flows). Constraint (13), which is used to calculate the availability of the WP of each flow, has to be linearized, which is accomplished by applying logarithms to both sides of the equality. Let LAW P (s,t) = − log A WP (s,t) . Therefore, constraint (13) is replaced by: X LAW P (s,t) + xst ij log (aij ) = 0, ∀(s, t) ∈ F (15) (i,j)∈L The problem may now be formulated as: X min LAW P (s,t) (16) (s,t)∈F subject to constraints (2)-(12), (14) and (15). 2.3 Problem 2: Maximization of the minimization of the availability for the WPs of all the flows The problem formulation is similar to the previous one, except for the objective function, which in this case is max min(s,t)∈F AW P (s,t) . Therefore, the problem is formulated as: max AW P (17) subject to AW P ≤ AW P (s,t) ∀(s, t) ∈ F (18) constraints (2)-(14) To avoid non-linearities, let LAW P = − log AW P (non-negative). Con- straint (18) is replaced by: LAW P − LAW P (s,t) ≥ 0, ∀(s, t) ∈ F (19) The problem may now be formulated as: min LAW P (20) subject to constraints (2)-(12), (14), (15) and (19). 3 Heuristic resolution approach We present a heuristic for generation of edge-disjoint path pairs for the demands in the network, taking into account the availability of each edge. As already mentioned, the set of edges forming the WPs constitutes a spanning tree and the BP for each demand must be edge-disjoint. Considering the information on the spine and the WP for each node pair, then the performance measures (maximal availability, for instance) may be calculated. In this section, we explain how the WPs are devised using an algorithm for enumeration of K trees in non-decreasing order of a cost metric. Different cost metrics are proposed. As for the BP, it suffices to find an edge-disjoint path pair for each demand. 3.1 Generation of WPs The algorithm in [20] is used to iteratively generate spanning trees by non- decreasing order of a cost metric. Different cost metrics were taken into account. The WP for each demand (source-destination pair) is given by edges in the spanning tree. In this work, we reserve the term ‘edge cost’ to the value assigned to each edge during the calculation of spanning trees, and the term ‘edge length’ to the value assigned to each edge during the calculation of shortest paths. It is not necessarily an actual distance. The enumeration of shortest paths for each node pair may be necessary for the calculation of some of the cost metrics described in this section. Once a specific cost metric is considered, the enumeration of candidate spines (spanning trees) is performed and only the spanning trees for which an edge-disjoint BP may be found for every node pair are admissible. We discard the spines for which there is at least one demand without an edge-disjoint BP. Metric {A} In this situation, the final cost of edge l is simply calculated as c{A} (l) = − log(a(l)) (21) which means that the edge cost is directly related to the availability of edge l. Metrics related to an edge betweenness centrality measure Let the length of an edge l be given by − log (a(l)), where a(l) is the availability of edge l. In this case, enumerating the K shortest paths between nodes s and t using these lengths corresponds to the enumeration of the K most available paths between nodes s and t. Therefore, in the path enumeration algorithm, the paths are generated by non-increasing order of availability. Note that different edges may have different lengths and the graph is considered to be weighted. Given the paths enumerated by non-increasing order of availability, a measure of the betweenness centrality for each edge l, B(l), may be calculated. The final cost of edge l is calculated as the symmetrical of the centrality measure, with an additional transformation that guarantees that all the costs are positive. We define 3 different betweenness centrality measures for an edge, which lead to different edge costs. Metric {B} We consider P(s, t), which is the set of shortest paths between nodes s and t, i.e. the set of paths with length equal to the length of the shortest path between nodes s and t. By equal length, we consider a length within a given tolerance , i.e. two paths with length L1 and L2 respectively, have equal length if |L1 − L2 | ≤ . Likewise, the two paths have different length if |L1 − L2 | > . We define σ(s, t) = |P(s, t)| and σ(s, t|l) as the number of paths in the set P(s, t) that include edge l. Given these parameters, then the betweenness centrality for edge l is X σ(s, t|l) B {B} (l) = (22) σ(s, t) (s,t)∈F Metric {C} For the calculation of this cost, we again start by enumerating the K shortest paths between nodes s and t using the length of an edge l as − log (a(l)). Let Pδ (s, t) be the set of paths between nodes s and t, whose length is not higher than the length of the shortest path (L0 ) plus δ (real-valued). The length of the path is related to its availability, i.e. the shortest path is the most available. The availability of each edge l ∈ L, a(l), is related to the edge length d(l) (in km), as explained earlier. Given the set Pδ (s, t), we may define σδ (s, t) = |Pδ (s, t)| and σδ (s, t|l), which is the number of paths in the set Pδ (s, t) that include edge l. A topological structural measure defined by [21] is the δ-betweenness cen- trality for edge l, given by {C} X σδ (s, t|l) Bδ (l) = (23) σδ (s, t) (s,t)∈F In the performed experiments, the considered value for δ must be tuned for each network. Metric {D} This metric is a variant of the previous one, which allows to decrease the centrality of the edges that are present in (almost) all of the shortest paths for each demand. The idea behind this metric is to decrease the probability of such edges being in the spine, which should allow to find more edge-disjoint BPs. This is especially relevant and noticeable in sparser networks, where the number of possible edge-disjoint path pairs may be critical. {C} This cost involves a structural measure similar to Bδ (l). However, rather than considering σδ (s, t|l) (the number of paths in the set Pδ (s, t) that include edge l), we have to consider two parameters: σ 0 (s, t|l), which is the number of paths in Pδ (s, t) with the same length L0 as the shortest path and that include edge l; σδ+ (s, t|l), which is the number of paths in Pδ (s, t) with length L such that L0 < L ≤ L0 + δ and that include edge l. Note that σ 0 (s, t|l) = σ(s, t|l) and that σδ (s, t|l) = σ 0 (s, t|l) + σδ+ (s, t|l). We define {D} X σ 0 (s, t|l) − ασ + (s, t|l) δ Bδ,α (l) = (24) σδ (s, t) (s,t)∈F In the performed experiments, the considered values for δ and α must be tuned for each network. 4 Experimental results Experiments were conducted with different real-world reference networks (geant, polska, newyork3 , germany50) from the SNDlib [22], whose topology features are described in Table 1. The other networks are epan16 [23] and telia-sonera [24]. Given the information on the nodes of each network (that represent cities), it was possible to find out the length of each edge in km. For the smaller networks, an exact result was obtained by solving prob- lems 1 and 2 with CPLEX 12.5, i.e. the spines for which the maximum AW a P and the maximum AW m P were obtained. Experiments with the different cost metrics were performed and for each experiment, a set of trees was obtained. A maximum number of |N | · |E| trees was calculated. The total number of spanning trees that can be found in each |N |·|E| network may be calculated, giving the proportion of considered trees # trees displayed in Table 1. Note that this proportion is quite different depending on the network. The |N | · |E| calculated trees are the trees which are candidates to becoming spines. As mentioned previously, all the candidate spines (spanning trees) for which an edge-disjoint backup path can be found in the network for each working path in the spine are considered admissible. Given the set of admissible trees obtained in each experiment, information on the tree leading to the best value 3 Note that in the case of newyork the latitude and longitude are in fact V and H, respectively, of the V&H coordinate system created by AT&T. Table 1. Network characteristics (|N |, |E|, ν – average node degree, D – diameter, d – average link length [km]) |N |·|E| Network |N | |E| ν |N | · |E| D # trees d polska 12 18 3.00 216 4 4.2% 188.06 epan16 16 23 2.88 368 6 0.84% 325.22 newyork 16 49 6.13 784 3 5.4E-8 105.53 telia-sonera 21 25 2.38 525 9 21.88% 643.80 geant 22 36 3.27 792 5 3.2E-5 1053.17 germany50 50 88 3.52 4400 9 9.6E-17 100.59 of AW a P and on the tree leading to the best value of AW m P is obtained. For the cost metrics {C} and {D}, experiments were run for different values of δ (real-valued); for {D}, α took values between 0.0 and 1.0, with a step of 0.1. Note that metric {D} makes sense for sparser networks, for which it is difficult to find edge-disjoint BPs for all the flows. In this situation, the centrality measure of metric {C} is too demanding and metric {D}, which tries to decrease the importance of central edges, should perform better. Therefore, metric {D} was only used in the polska, epan16 and telia-sonera networks. The choice of δ depends on the network. We calculated for each demand, the difference in cost of the first and the second shortest paths using the length of an edge l as − log (a(l)). Let ∆(s, t) be that difference. With this infor- mation for all the demands (s, t) ∈ F, we calculated the values of ∆m = min(s,t)∈F ∆(s, t), ∆a = avg(s,t)∈F ∆(s, t) and ∆M = max(s,t)∈F ∆(s, t). Note P δ and ∆ are expressed in terms of the length of edges − log(a(l)) and paths that l∈ path (− log(a(l))). We will define the corresponding values δ and ∆ as dis- tances in km, displayed in Table 2. In Tables 3-8, information on the values of the performance measures ob- tained in the experiments considering the exact formulation and the cost metrics is provided. The percentage of discarded trees (i.e. spines for which an edge- disjoint path pair could not be found for at least one demand) is also presented. For metrics {C} and {D}, the best results are displayed, with the indication of one value of δ [km] (corresponding to the δ used in the metric) and the range of α (for {D} only) for which they were found. For metric {D}, the percentage of discarded trees is an average of the percentages obtained for the different values of α in the table. Note that different values of δ and α may lead to the same final result. For the exact formulation problems, we present the optimal value in bold for the corresponding problem (i.e. AW a P for problem 1 and AW m P for problem WP 2). For the heuristics, we present in bold the value of Aa for one of the trees which led to the best value of that parameter; likewise for AW P m . In terms of solver execution times, the resolution of problem 1 only takes a few seconds (the maximum is 40s for the geant network) and the resolution of problem 2 can take between a few seconds (eg. the polska and telia-sonera Table 2. Values related to the difference in distance [km] of the first and the second shortest paths Network ∆m ∆a ∆M polska 2.00 175.77 634.39 epan16 2.00 324.93 1420.42 newyork 1.00 36.52 128.12 telia-sonera 2.00 1525.64 5446.51 geant 6.00 312.56 2537.58 germany50 4.02E-11 51.99 479.66 Table 3. Performance results for the polska network polska %disc AWa P AWm P Problem 1 0.9998417777 0.9996972610 Problem 2 0.9998417777 0.9996972610 0.9998408580 0.9996752942 Cost {A} 73.15% 0.9998379941 0.9996856314 Cost {B} 82.87% 0.9998417777 0.9996972610 {C}, δ = 185.68 68.98% 0.9998417777 0.9996972610 {D}, δ = 1237.84 α = 0.0 82.87% 0.9998417777 0.9996972610 any α 53.54% 0.9998414347 0.9996972610 Table 4. Performance results for the epan16 network epan16 %disc AWa P AWm P Problem 1 0.9996742529 0.9992554330 Problem 2 0.9996325619 0.9992861092 0.9996632651 0.9991924691 Cost {A} 95.92% 0.9996505403 0.9992554330 Cost {B} 96.20% 0.9996632651 0.9991924691 {C}, δ = 804.60 97.55% 0.9996734190 0.9992554330 {D}, δ = 3651.64 72.96% 0.9996742529 0.9992554330 0.1 ≤ α ≤ 0.2 Table 5. Performance results for the newyork network newyork %disc AWa P AWm P Problem 1 0.9999335993 0.9998827060 Problem 2 0.9999318975 0.9998875526 Cost {A} 0% 0.9999294824 0.9998675202 0.9999274629 0.9998607351 Cost {B} 0% 0.9999268382 0.9998749515 {C}, δ = 30.95 0% 0.9999323985 0.9998736591 {C}, δ = 27.85 0% 0.9999292696 0.999882706 Table 6. Performance results for the telia-sonera network telia-sonera %disc AWa P AWm P Problem 1 0.9989526565 0.9972957260 Problem 2 0.9989101636 0.9975090909 0.9989526565 0.9972957260 Cost {A} 96.76% 0.9989101636 0.9975090909 No solution with edge-disjoint path Cost {B} 100% pairs in the first |N | · |E| trees. {C}, δ = 1547.30 99.81% 0.9989204946 0.9970769294 {C}, δ = 1856.76 99.99% 0.9989169741 0.9973914445 {D}, δ = 11140.58 α ≥ 0.3 98.40% 0.9989526565 0.9972957260 α ≥ 0.2 98.92% 0.9989101636 0.9975090909 Table 7. Performance results for the geant network geant %disc AWa P AWm P Problem 1 0.9992753570 0.9969158432 Problem 2 0.9990333026 0.9970263455 0.9992577379 0.9969493470 Cost {A} 57.95% 0.9992218088 0.9970244124 0.9992719789 0.9969158432 Cost {B} 10.35% 0.9992467344 0.9970263455 {C}, δ = 340.41 54.17% 0.9992753570 0.9969158432 {C}, δ = 154.73 34.47% 0.9992454430 0.9970263455 Table 8. Performance results for the germany50 network germany50 %disc AWa P AW m P Due to the network size, the Problems 1& 2 exact algorithm could not be run. 0.9998374813 0.9996103656 Cost {A} 43.45% 0.9998371234 0.9996158569 Cost {B} 96.18% 0.9998373995 0.9996313620 {C}, δ = 123.78 85.61% 0.9998419336 0.9996313620 {C}, δ = 34.04 95.70% 0.9998308936 0.9996649570 networks), a few minutes (eg. epan16 and geant) and a few hours (eg. the newyork network with 3h40m). These are all networks of small/medium dimension. For a network of larger dimension (the germany50 network), the problem remained unsolved after a few days of execution. As for the heuristics, they can take between a few seconds for the smaller networks and a few minutes for the larger networks. As expected in terms of execution times, the use of the heuristics is much more advantageous for larger size networks. In fact, for the germany50 network, for which an exact solution could not be found for problem 1 (the quickest for the other networks) even after a few days of execution, it was possible to find an approximate solution in about 30m with metric {C} (depending on the value of δ). Considering the results, it is noticeable that the telia-sonera network has a different trend of results, when compared to the other networks. The fact that this is a very sparse network may help to explain the disparity between the results in Table 6 and the results for the remaining networks. For metric {B}, we could not even get any feasible solution (i.e. a spine with the WPs and edge-disjoint BPs for all the demands) among the first |N | · |E| trees found by the used K-shortest trees enumeration algorithm. A metric that managed to find results equal to the exact ones was metric {A}, unlike what happened for the other networks. Note that metric {A} does not take into consideration the topological structure of the network, as it disregards the centrality of the edges. Therefore, it works well for sparser networks, for which it is not possible to identify elements with greater centrality. Metric {D} with high δ should allow to take into consideration a larger number of shortest paths in the calculation of the cost (24). An appropriate value for δ was close to 2 ∗ ∆M . With a large value of the tuning parameter α (unlike what happens in other networks), we are decreasing the importance of more central edges (which appear in the shortest paths). Therefore, the created trees from the costs {D} should tend to produce longer paths for the node pairs, which is appropriate for sparser networks. In this case metric {D} manages to find a solution equal to the optimum. For the other networks, the results are quite different from these. Unless otherwise stated, the following comments regarding the analysis of results hold for the other networks (i.e. except telia-sonera). The metrics which consistently lead to the best results for both the perfor- mance measures (AWa P and AW P m ) are metrics {C} and {D} (only for the polska and the epan16 networks). For the least sparsed networks, metric {C} tends to lead to the best results, as the trees tend to include more central edges with a high node degree. For these networks, there is no need to consider a metric such as {D} that leads to trees with longer paths for each node pair so that edge-disjoint BPs may be found. The behavior of parameter δ in metric {C} depends on the network. For most of the networks, it seems that a δ between ∆a and ∆M works better, which means that in the calculation of expression (23), it suffices to find the shortest paths and the paths with length close to these ones for most of the demands. For the polska and epan16 networks, metric {D} (with appropriate δ ≥ 2∗∆M and low α) found solutions with AWa P and AWm P equal to the respective exact value. For germany50, the exact results are not known. Still, metric {C} is the one that led to the best results of the two performance measures. For newyork, none of the variants of the heuristic managed to find results equal to the exact ones. For this network, we notice that there is a long edge that is part of the spine in the optimal solution. As the metrics considered in the heuristic focus on finding shortest paths for each demand (for subsequent calculation of the edge costs to be used in the tree enumeration algorithm), this very long edge is seldom selected to be in the spine. This is the reason why the optimal solution could not be found for this network. If more trees were considered (and notice that in this network only 5.4E-8 – see Table 1 – of the total possible number of spanning trees were considered), then eventually trees including this edge should appear and the results should be better. In Figures 1-2, the variation of the WP availability measures is displayed as a function of δ [km], corresponding to the value of δ in metric {C} and for two different numbers of trees. It is noticeable that with more trees the heuristic manages to find solutions with better values for both availability measures. Obviously considering more trees will entail an increase in the running time of the heuristic, which is not desirable. WP Availability 0.999933 784 trees 7840 trees 0.999932 0.999931 0.999930 0.999929 0.999928 0.999927 0 10 20 30 40 50 60 70 _δ Fig. 1. newyork network: AW a P for metric {C} WP minimum Availability 0.99989 784 trees 0.99989 7840 trees 0.99988 0.99988 0.99988 0.99988 0.99988 0.99987 0.99987 0.99987 0 10 20 30 40 50 60 70 _δ Fig. 2. newyork network: AW m P for metric {C} The main conclusion is that enumerating the first |N | · |E| trees in non- increasing order of the centrality metrics {C} and {D} (with appropriate δ and low α) should allow us to find solutions with the exact value (or close to it) of the availabilities AWa P and AW P m , in a short time (when compared with the execution of an exact algorithm), in particular for large networks. For the smallest network (polska), solutions with the exact value of the avail- abilities can also be found with metric {B}. For this network, a solution with an exact value was also found for metric {D} with α = 0.0, which is similar to metric {B}. Metric {D} is a variation of metric {C} which should allow to find more edge-disjoint paths. Therefore, a smaller number of possible spanning trees is discarded, as it is more likely to find edge-disjoint path pairs for all the demands. This is noticeable in the tables, where the percentage of discarded trees is shown. Except for the polska network with α = 0.0, the percentage of discarded trees is always higher for metric {C} than for metric {D}. For the telia-sonera, this is especially critical as it is a sparse network: for metric {C} only a small number of admissible trees were found for many instances of δ, but it was possible to find more admissible trees and better solutions for metric {D}. For the newyork network, which is the least sparsed, it was always possible to find an edge-disjoint path pair for all the demands (0% of discarded trees). Although the germany50 network is not a sparse network, it presents a high number of discarded trees. This is due to some specific demands for which the source and/or the destination are nodes with degree 2. For these demands, it is difficult to find edge-disjoint BPs considering that the WPs are in a spanning tree (the spine). Metric {A} tends to present the worst results. Note that metric {A} disre- gards the centrality of the edges, leading to results where the WPs in the spine tend to be longer which leads to worse availabilities for the WP. For the epan16 and newyork networks, it was not possible to find any solution (among the first |N | · |E| trees) with a value of AW m P equal to the exact one. For WP the other networks, the solution with the best Am tends to be found after the solution with the best AW a P . This shows that the algorithm for enumeration of K trees in non-increasing order of a centrality cost metric tends to favour the solutions with the best AW a P . A different tree enumeration algorithm based on finding the trees with the edge that causes the smallest bottleneck in the tree might be a possibility for favouring trees with a better AW P m . With the current tree enumeration algorithm, it would be necessary to consider a larger number of trees to be able to find the solution with best AW P m . 5 Conclusions In this work, we focus on the topological structure of a network taking into account centrality measures to select a high availability spine to be used as the WP for each demand. Considering an edge-disjoint BP for each demand, the obtained path pair provides end-to-end protection for critical service demands in the network. An exact formulation to design the spine according to the most available WPs is proposed and solved for small instances networks. Different centrality measures were studied and used in a heuristic approach based on the enumeration of spanning trees in non-increasing order of central- ity costs. As the results show, the centrality measures lead to solutions with high availability. Even if a small number of spanning trees was considered, it was possible to find the optimal solution in most of the tested networks. These centrality measures may be used in the context of other approaches for devising the spine, possibly using meta-heuristics for a more efficient calculation of ap- propriate spanning trees, leading to a higher availability, namely in terms of the availability of the path pair. Acknowledgment R. Girão-Silva, L. Martins and T. Gomes were supported by FCT under project UID/MULTI/00308/2013 of INESC-Coimbra. The authors thank Dr. Jaime Silva for writing part of the code used in this paper. References 1. The White House, Office of the Press Secretary (2013) Presidential pol- icy directive – critical infrastructure security and resilience – PPD-21. URL https://obamawhitehouse.archives.gov/the-press-office/2013/02/12/ presidential-policy-directive-critical-infrastructure-security-and-resil 2. Çetinkaya, E.K., Sterbenz, J.P.: A taxonomy of network challenges. In: 9th In- ternational Conference on Design of Reliable Communication Networks (DRCN), Budapest, Hungary, pp. 322–330 (2013) 3. Marzo, J.L., Calle, E., Scoglio, C., Anjali, T.: QoS online routing and MPLS mul- tilevel protection: a survey. Communications Magazine 41(10), 126–132 (2003) 4. Cholda, P., Mykkeltveit, A., Helvik, B., Wittner, O., Jajszczyk, A.: A survey of resilience differentiation frameworks in communication networks. IEEE Communi- cations Surveys Tutorials, 9(4), 32–55 (2007) 5. Sterbenz, J.P., Hutchison, D., Çetinkaya, E.K., Jabbar, A., Rohrer, J.P., Schöller, M., Smith, P.: Resilience and survivability in communication networks: Strategies, principles, and survey of disciplines. Computer Networks 54(8), 1245 – 1265 (2010) 6. Kuipers, F.A.: An overview of algorithms for network survivability. ISRN Commu- nications and Networking 2012(Article ID 932456), 19 pages (2012) 7. Tipper, D.: Resilient network design: challenges and future directions. Telecommu- nication Systems 56(1), 5–16 (2014) 8. Rak, J., Pickavet, M., Trivedi, K.S., Lopez, J.A., Koster, A., Sterbenz, J., Çetinkaya, E.K., Gomes, T., Gunkel, M., Walkowiak, K., Staessens, D.: Future research directions in design of reliable communication systems. Telecommunica- tion Systems 60(4), 423–450 (2015) 9. Tapolcai, J., Cholda, P., Cinkler, T., Wajda, K., Jajszczyk, A., Autenrieth, A., Bodamer, S., Colle, D., Ferraris, G., Lonsethagen, H., Svinnset, I.E., Verchere, D.: Quality of resilience (QoR): NOBEL approach to the multi-service resilience characterization. In: BroadNets 2005, 2nd International Conference on Broadband Networks, vol. 2, pp. 1328–1337 (2005) 10. Cholda, P., Tapolcai, J., Cinkler, T., Wajda, K., Jajszczyk, A.: Quality of resilience as a network reliability characterization tool. IEEE Network 23(2), 11–19 (2009) 11. Tornatore, M., Dikbiyik, F., Mukherjee, B.: (3W-)availability-aware routing in op- tical WDM networks: when, where and at what time. In: 13th International Con- ference on Transparent Optical Networks, pp. 1–5 (2011) 12. Zhang, Q., Sun, J., Xiao, G., Tsang, E.: Evolutionary algorithms refining a heuris- tic: A hybrid method for shared-path protections in WDM networks under SRLG constraints. IEEE Transactions on Systems, Man and Cybernetics - Part B: Cy- bernetics 37(1), 51–61 (2007) 13. Chen, X., Tornatore, M., Zhu, S., Ji, F., Zhou, W., Chen, C., Hu, D., Jiang, L., Zhu, Z.: Flexible availability-aware differentiated protection in software-defined elastic optical networks. Journal of Lightwave Technology 33(18), 3872–3882 (2015) 14. Verbrugge, S., Colle, D., Demeester, P., Huelsermann, R., Jaeger, M.: General avail- ability model for multilayer transport networks. In: 5th International Workshop on Design of Reliable Communication Networks (DRCN) (2005) 15. Zhang, J., Modiano, E., Hay, D.: Enhancing network robustness via shielding. IEEE/ACM Transactions on Networking 25(4), 2209–2222 (2017) 16. de Sousa, A., Gomes, T., Girão-Silva, R., Martins, L.: Minimizing the network availability upgrade cost with geodiversity guarantees. In: 9th International Work- shop on Resilient Networks Design and Modeling (RNDM) (2017) 17. Gomes, T., Tipper, D., Alashaikh, A.: A novel approach for ensuring high end-to- end availability: The spine concept. In: 10th International Conference on Design of Reliable Communication Networks - DRCN 2014, Ghent, Belgium (2014) 18. Alashaikh, A., Gomes, T., Tipper, D.: The spine concept for improving network availability. Computer Networks 82, 4–19 (2015) 19. Kounev, V., Lévesque, M., Tipper, D., Gomes, T.: Reliable communication net- works for smart grid transmission systems. Journal of Network and Systems Man- agement 24(3), 629–652 (2016) 20. Katoh, N., Ibaraki, T., Mine, H.: An algorithm for finding k minimum spanning trees. SIAM Journal on Computing 10, 247–255 (1981) 21. Jiang, K., Ediger, D., Bader, D.A.: Generalizing k-betweenness centrality using short paths and a parallel multithreaded implementation. In: 2009 International Conference on Parallel Processing (ICPP’09), pp. 542–549 (2009) 22. Orlowski, S., Wessäly, R., Pióro, M., Tomaszewski, A.: SNDlib 1.0–Survivable Net- work Design library. Networks 55(3), 276–286 (2010) 23. Maesschalck, S., Colle, D., Lievens, I., Pickavet, M., Demeester, P., Mauz, C., Jaeger, M., Inkret, R., Mikac, B., Derkacz, J.: Pan-European Optical Transport Networks: An Availability-Based Comparison. Photonic Network Communications 5(3), 203–225 (2003) 24. Sterbenz, J.P., Rohrer, J.P., Çetinkaya, E.K., Alenazi, M.J., Cosner, A., Rolfe, J.: KU-Topview network topology tool. The University of Kansas (2010). http: //www.ittc.ku.edu/resilinets/maps/