Minimizing the netw ork a v ailability upgrade cost
with geodi v ersity guarantees
Amaro de Sousa
Instituto de T elecomunicac ¸ ˜
oes, 3810-193 A v eiro, Portugal
Departamento de Eletr ´
onica, T elecomunicac ¸ ˜
oes e Inform ´
atica,
Uni versidade de A veiro, 3810-193 A veiro, Portug al
Email: [email protected]
T eresa Gomes, Rita Gir ˜
ao-Silv a and L ´
ucia Martins
Department of Electrical and Computer Engineering,
Uni versity of Coimbra, 3030-290 Coimbra, Portug al
INESC Coimbra, 3030-290 Coimbra, Portugal
Email: { teresa,rita,lucia } @deec.uc.pt
Abstract —As telecommunication networks ar e a critical infras-
tructure of our society , they must ev olve to pr ovide high end-
to-end a vailability and high r esilience to large-scale disasters.
Path pr otection mechanisms can impr ove end-to-end a vailability
b ut, in general, might not be enough to reach the a vailability
requir ed by critical services. Moreo ver , adding geodiversity to the
routing paths (i.e., selecting p ath pairs with higher geographical
distance between them) enhances the network disaster r esilience
b ut also makes it mor e challenging to reach a high end-to-
end a vailability as the r esulting paths tend to be longer . So,
f or a network wher e each link is characterized by its current
a vailability and by the cost of upgrading its a vailability to a new
value, this paper pr oposes some strategies aiming to determine a
set of links to be upgraded at a minimum cost ensuring a desired
lev el of a vailability and geodiv ersity . The problem is defined as
an integer non-linear programming model, a solving algorithm
based on different gr eedy strategies is proposed and the r elative
perf ormance of the different strategies is e valuated on a set of
problem instances.
Index T erms —av ailability; path geodiv ersity; resilience; disas-
ter .
I . I NTR ODUCTION
It is well kno wn that telecommunication networks are cur -
rently one of the critical infrastructures upon which our society
depends and services are expected to be al ways-on. Moreo ver ,
disaster -based failures are becoming more frequent in time and
wider in scope, degrading drastically the services supported by
telecommunication networks [1] (a surv ey of strate gies to pro-
tect networks against lar ge-scale natural disasters is presented
in [2]). Thus, it is imperati v e that telecommunication networks
become both highly a v ailable and resilient to disasters.
Networks need to guarantee that all node pairs of interest
(i.e., node pairs in volv ed in critical services such as emer gency
calls, smart grid communications, financial transactions, etc.)
ha ve a high end-to-end a v ailability [3], [4], [5]. Moreover ,
when a disaster -based failure occurs, it is important not only
to quickly recov er the network in the disaster area b ut also
to minimize the disaster impact for node pairs outside the
disaster area. Here, we explore the idea of path geodi versity ,
i.e., ho w to take into consideration the geographical di versity
of the network topology when making routing decisions. P ath
geodi versity has been used to improv e services a v ailability [6]
and disaster resilience [7].
Consider a network topology such that the geographical
distance between any tw o network elements (nodes or links)
is kno wn. Like in [8], [9], we consider a path geodi versity
strategy where the routing between two netw ork nodes is based
on two paths geographically separated by at least a minimum
distance D , so that, if a disaster with a geographical cov erage
whose diameter is lo wer than D af fecting one intermediate
element of one path cannot af fect the other path. Here, we
follo w [9] which considers intermediate elements both as
nodes and links, while [8] considers only intermediate nodes.
Note that the lar ger the v alue D is, the more resilient the
network is to disasters b ut the more dif ficult it becomes to
reach high end-to-end a v ailability since the resulting paths tend
to be longer .
In this work, we consider jointly the end-to-end a v ailability
and the disaster resilience of a gi ven netw ork topology . W e
address the network a v ailability upgrade problem where the
a v ailability of some links must be upgraded to provide the
required end-to-end a v ailability and disaster resilience for a
set of node pairs of interest. In [10], the authors also select
a set of links to be upgraded (shielded, so that they become
in vulnerable). Ho we ver only end-to-end connecti vity against
geographic based attacks is ensured, without considering a v ail-
ability requirements.
The upgraded network must guarantee that each node pair
of interest is provided with at least one path pair fulfilling
two requirements. Concerning end-to-end a v ailability , at least
one path pair with a minimum tar get av ailability of Λ must
be provided to each node pair . As pointed out in [9], the
maximum geodi versity value that can be provided by a path
pair to a gi v en node pair is constrained by the geographical
locations of the nodes and the geographical paths of the links.
Hence, concerning disaster resilience, a tar get geodi versity
v alue D with a soft requirement is used: at least one path pair
with a minimum geodi versity of D must be pro vided to each
node pair whose maximum geodi versity v alue is at least D ;
for node pairs such that the network topology cannot pro vide
D , the maximum possible geodi versity v alue is used.
The paper is or ganized as follo ws. In section II, the network
a v ailability upgrade problem is described. In section III, a solv-
ing algorithm based on dif ferent greedy strategies is proposed.
Section IV presents the computational results comparing the
© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other
uses, in any current or future media, including reprinting/repub lishing this material for advertising or promotional
purposes, creating new collect ive works, for resale or redistribution to servers or lists, or reuse of any
copyrighted component of this work in other works.
ef ficiency of the dif ferent greedy strate gies. Finally , section V
presents the main conclusions, along with some further work.
I I . P R O B L E M D E FI N I T I O N
Consider two gi ven parameters: a minimum a v ailability pa-
rameter Λ and a minimum geodi versity parameter D . Consider
a gi ven biconnected netw ork defined by an undirected graph
G = ( N , E ) where N is the set of nodes and E is the set of
edges representing node pairs connected by a direct link. Each
edge e ∈ E is characterized by its current a v ailability a e , its
upgraded a v ailability a u
e and the cost c e required to upgrade
its a v ailability from a e to a u
e . The aim is to determine a set
of edges to be upgraded at a minimum cost. For a gi ven set
of node pairs of interest K , the upgraded a v ailability solution
must guarantee the existence of at least one pair of paths for
each node pair ( s, t ) ∈ K with (i) a minimum a v ailability of
Λ and (ii) a minimum geodi v ersity of D , if the topology of G
allo ws it, or the maximum possible geodi v ersity v alue if it is
lo wer than D .
For each node pair ( s, t ) ∈ K , consider the set of all pairs
of paths a v ailable in G defined by R st where each path pair
r ∈ R st is defined by two sets of edges: S r 1 (the edge set of
the first path of r ) and S r 2 (the edge set of the second path
of r ). Then, consider the follo wing binary v ariables:
x e is equal to 1 if edge e ∈ E is upgraded; 0 otherwise.
y str is equal to 1 if node pair ( s, t ) ∈ K may be pro vided
with path pair r ∈ R st ; 0 otherwise.
Using these v ariables, the a v ailability of a path pair r ∈ R st ,
represented by Λ r , is gi ven by:
Λ r = 1 − 1 − Y
e ∈ S r 1
((1 − x e ) a e + x e a u
e ) ! ×
1 − Y
e ∈ S r 2
((1 − x e ) a e + x e a u
e ) ! (1)
Follo wing [9], the geodi versity of a path pair is the mini-
mum distance between any intermediate node or edge of one
path and any node or edge of the other path. In [9], it is
sho wn that the geodi v ersity of a path pair can be modelled
based only on geographical distances between edges provided
that these distances are defined as follo ws. For each r ∈ R st
between s and t , the geographical distance between one edge
e i ∈ S r 1 and one edge e j ∈ S r 2 , represented by δ ( e i , e j ) , is
defined as (i) the minimum distance between any point in the
geographical path of e i and any point in the geographical path
of e j if they do not share s or t or (ii) the minimum distance
between one edge and the non-common end node of the other
edge if they share either s or t . Fig. 1 sho ws part of a network
with the source node s , fi v e other nodes ( 2 to 6 ) and fi ve edges
( a to e ) illustrating the geographical distances between edges
in the dif ferent cases. Examples of case (i) are the distances
δ ( a, e ) and δ ( b, e ) . Note that the zero distances δ ( a, b ) , δ ( c, d )
and δ ( d, e ) also illustrate this case, because each pair of edges
shares a node, which is neither s nor t . As for case (ii), the
distance δ ( a, c ) between edges a and c , since they share the
Fig. 1: Geographical distances between edges (adapted from
[9])
source node s , is the minimum between the distance between
node 2 (the non-common end node of a ) and edge c and the
distance between node 3 (the non-common end node of c ) and
edge a . In this work, it will be considered that links follo w
the shortest path ov er a sphere that represents Earth.
Then, the geodi versity v alue of r ∈ R st , represented by D r ,
is gi ven by:
D r = min
e i ∈ S r 1 ,e j ∈ S r 2
δ ( e i , e j ) (2)
Note that the geodi versity v alue of a path pair only depends
on the geographical path of each edge. Moreov er , for each
node pair ( s, t ) ∈ K , there is a maximum geographical
distance, which we represent by D M ax
st , abov e which a pair
of paths is infeasible (these v alues can be computed in
adv ance using [9]). Therefore, we consider the geodi v ersity
requirement using D st = min( D , D M ax
st ) , i.e., we require D
if D M ax
st ≥ D or we require D M ax
st , if D M ax
st < D .
The network upgrade problem is, then, defined by the
follo wing integer non-linear programming model:
Minimize X
e ∈ E
c e x e (3)
Subject to:
X
r ∈ R st
y str ≥ 1 ( s, t ) ∈ K (4)
Λ r ≥ Λ y str ( s, t ) ∈ K, r ∈ R st (5)
D r ≥ D st y str ( s, t ) ∈ K, r ∈ R st (6)
x e ∈ { 0 , 1 } e ∈ E (7)
y str ∈ { 0 , 1 } ( s, t ) ∈ K, r ∈ R st (8)
The objecti ve function (3) is the minimization of the total
cost of all upgraded edges. Constraints (4) guarantee that each
( s, t ) ∈ K is provided with at least one path pair (i.e., the
paths r ∈ R st such that the v ariable y str is set to 1) and
each of these path pairs has an a v ailability v alue not lo wer
than Λ , guaranteed by constraints (5), and a geodi v ersity v alue
not lo wer than D st , guaranteed by constraints (6). Finally ,
constraints (7)-(8) are the v ariable domain constraints.
Note that, in constraints (5), Λ r is gi v en by expression
(1). These constraints relate v ariables x e with v ariables y str
in a non-linear way which turns the proposed formulation
in an integer non-linear programming model. In this case,
standard solution techniques are not v alid and appropriate
exact methods (i.e., able to compute the optimal solutions)
must be in vestigated.
III. S O L V I N G A LGORITHM
The solving algorithm proposed here, named Minimum
Upgrade Cost with A vailability and Geodi versity (MUCA G),
uses an iterati v e approach based on a greedy strategy . Starting
with the network configuration without an y upgraded edge, the
algorithm selects iterati vely one edge to be upgraded until the
resulting network configuration pro vides at least a pair of paths
for each node pair ( s, t ) ∈ K with a minimum a v ailability of
Λ and a minimum geodi versity of D st .
W e designate a pair of paths with a minimum geodi versity
D st as a pair of geodi verse paths. As already e xplained, a
pair of geodi verse paths is al ways feasible for all ( s, t ) ∈ K ,
as D st = min( D , D M ax
st ) . Ne vertheless, the existence of
a pair of geodi v erse paths with a minimum av ailability Λ
depends on the set of upgraded edges. So, a nuclear task
of MUCA G is, for a gi ven netw ork configuration and a
gi ven ( s, t ) ∈ K , to compute a pair of geodi verse paths r
whose a v ailability Λ r is at least Λ . This task is implemented
through an algorithm, named Guaranteed A vailable P air of
Geodi verse P aths (GAPGP), which is an adaptation of the
algorithm in [11] for calculating the most reliable pair of link
disjoint paths. For reasons that will be explained in the detailed
description of MUCA G, algorithm GAPGP also computes the
pair of geodi verse paths with the highest a vailability v alue if
such v alue is lo wer than the required Λ .
In the follo wing three subsections, we describe separately
first the GAPGP algorithm, then, the MUCA G algorithm and,
finally , the dif ferent greedy strategies tested in practice.
A. GAPGP algorithm description
GAPGP is specified in Algorithm 1. F or a gi ven node pair
( s, t ) ∈ K , minimum a v ailability v alue Λ , minimum geodi-
versity v alue D st and network configuration (defined by the
v alues assigned to the binary v ariables x e ), GAPGP computes
a pair of geodi verse paths r ∈ R st with an a vailability v alue
Λ r which is either not lo wer than Λ , if such path pair e xists,
or is maximal if max r ∈ R st Λ r ≤ Λ .
GAPGP starts by computing an edge cost c 0
e for all e ∈ E
(lines 1–3) such that enumerating the k shortest paths using
these costs corresponds to the enumeration of the k paths with
the highest a v ailability.
Then, in the main while cycle (lines 6–27), the algorithm
iterati vely generates a ne w first path p with function ne xt-
shortest-path (line 7) by non-increasing order of a v ailability
v alue ( ne xt-shortest-path corresponds to the iterati ve use of
Y en’ s [12] k -shortest path algorithm or of the loopless ver -
sion [13] of the MPS algorithm [14]). For each first path p ,
a second path q is computed by function path-geo-distance
(line 16) as the path with the highest av ailability and a
geodi versity of D st with p (function path-g eo-distance runs
a shortest path algorithm in an auxiliary graph gi ven by G
without the edges of p and the edges with a distance from any
edge of p belo w D st ). If the second path q e xists ( q 6 = ∅ in
line 17), the a v ailability of path pair r 0 = ( p, q ) is ev aluated to
check if the current best solution r must be updated (lines 18–
21).
The algorithm stops (line 6) when either the a v ailability
of the current best path pair r is at least Λ or if v ariable
opt becomes true (which means that the path pair with the
highest a v ailability has been reached). V ariable opt becomes
true in one of two cases. The first case (line 25) is when
function ne xt-shortest-path (line 7) returns no path (i.e. p = ∅
in line 8), which means that all possible paths hav e already
been enumerated. The second case (line 12) is when the
a v ailability of the current best path pair cannot be further
improv ed (line 11) (condition also used in [11]).
T o understand the condition of line 11, let Av ( p ) represent
the a v ailability of a path p , i.e., Av ( p ) = e − c 0 ( p ) , where
c 0 ( p ) = P e ∈ p c 0
e . Consequently , the av ailability of a path pair
( p, q ) is Av ( p ) + (1 − Av ( p )) Av ( q ) . Let the current best path
pair be r = ( p w , q w ) with a v ailability Λ r , where w is the order
of generation of the first element of the pair (path p obtained in
line 7) and q w is the second path (path q obtained in line 16).
Finally , let the ne w first path generated by next-shortest-path
be p i (with i > w ). If Av ( p i ) + (1 − Av ( p i )) Av ( p i ) ≤ Λ r
(line 11), then r = ( p w , q w ) is optimal. The verification
of this statement is straightforward. F ollo wing [11], notice
first that Av ( p i ) ≤ Av ( p w ) . Let q i be the path with the
highest a v ailability which guarantees a geodi versity of D st
with p i . If Av ( q i ) > Av ( p i ) , this path pair w ould hav e
already been obtained when p = q i . On the other hand, if
Av ( q i ) ≤ Av ( p i ) , this path pair has an a vailability which
is at most Av ( p i ) + (1 − Av ( p i ))) Av ( p i ) and, by the abov e
condition, lo wer than Λ r . So, any path pair obtained from this
point onwards has an a v ailability not better than Λ r .
B. MUCA G algorithm description
MUCA G is specified in Algorithm 2. At the beginning
(lines 1-3), the algorithm sets all v ariables x e to 0, representing
the network with no upgraded edges.Then, the algorithm runs
a while cycle (lines 4-19). At the beginning of each c ycle, set
K has the node pairs ( s, t ) for which there is still no pair of
geodi verse paths with the required a vailability Λ . The while
cycle runs until set K is empty (line 4).
In the first step of each c ycle (line 5), the auxiliary sets K 0
and R are first initialized empty (note that at the end of each
cycle, R includes all the best pairs of geodi verse paths, which
still do not attain Λ ). Then, for each ( s, t ) ∈ K (lines 6-12),
algorithm GAPGP (line 7) computes a pair of geodi verse paths
r with an a v ailability Λ r (recall the description in the pre vious
subsection) that, if belo w the required v alue Λ (line 8), makes
node pair ( s, t ) to be added to K 0 (line 9) and path pair r to
be added to R (line 10). Note that when Λ r < Λ , r is the
path pair with the highest a v ailability of the current network
configuration for node pair ( s, t ) . So, the edges in volv ed in
such path pairs are likely to be the most promising ones to
be upgraded to reach the required network configuration in
subsequent cycles.
Algorithm 1 GAPGP
Requir e: G , s , t , Λ , D st , ( a e , a u
e , x e ) : ∀ e ∈ E , δ ( e i , e j ) :
∀ e i , e j ∈ E
Ensur e: ( r , Λ r )
1: f or all e ∈ E do
2: c 0
e = − log( a e )(1 − x e ) − log ( a u
e ) x e . Ne w edge cost
3: end f or
4: r ← ( ∅ , ∅ ) ; Λ r ← 0
5: opt ← f al se . r is not yet the most av ailable path pair
6: while Λ > Λ r ∧ ¬ opt do
7: p ← next-shortest-path ( s, t, G, c 0 )
8: if p 6 = ∅ then
9: if Λ r 6 = 0 then
10: g ← e − c 0 ( p )
11: if g (2 − g ) ≤ Λ r then . Av ( p ) , Av ( q )
12: opt ← tr ue . r is the optimal solution
13: end if
14: end if
15: if ¬ opt then
16: q ← path-geo-distance ( δ , D st , p, G, c 0 )
17: if q 6 = ∅ then
18: r 0 ← ( p, q )
19: if Λ r 0 > Λ r then
20: r ← r 0 . Updates solution
21: end if
22: end if
23: end if
24: else
25: opt ← tr ue . No more improv ement possible
26: end if
27: end while
Then, K is set with K 0 (line 13), i.e., the ne w set K has
only the node pairs ( s, t ) for which there is still no pair of
geodi verse paths compliant with the av ailability requirement.
Finally , if set K is not empty (lines 14-18): (i) function
selectEdge (line 15) selects one edge e (among the non-
upgraded ones belonging to path pairs in R ) and calculates the
end nodes K 0 of the path pairs whose a v ailability becomes at
least Λ with the selected edge (this set can be an empty set),
(ii) the selected edge e is upgraded (line 16) and (iii) K 0 is
remov ed from K (line 17).
Note that if all the edges in set R (see line 15) ha ve
already been upgraded, the algorithm ends without achie ving
the desired end-to-end a v ailability for the demands currently
in set K . For simplicity , this situation is not considered in the
algorithm description.
C. V ariants for the gr eedy algorithm
In line 15 of Algorithm 2, the edge to be upgraded next may
be selected according to dif ferent greedy strate gies. Consider
first that E ( R ) represents the set of edges, among the ones
still not upgraded, that belong to at least one of the path pairs
in R . The edge to be upgraded next is one edge of E ( R ) . The
Algorithm 2 MUCA G
Requir e: G , K , Λ , ( a e , a u
e , c e ) : ∀ e ∈ E , D st : ∀ ( s, t ) ∈ K
Ensur e: x e : ∀ e ∈ E
1: f or all e ∈ E do
2: x e ← 0
3: end f or
4: while K 6 = ∅ do
5: K 0 ← ∅ , R←∅
6: f or all ( s, t ) ∈ K do
7: ( r , Λ r ) ← − GAPGP ( s, t, D st , Λ , x e : e ∈ E )
8: if Λ r < Λ then
9: K 0 ← K 0 ∪ { ( s, t ) }
10: R ← R ∪ { r }
11: end if
12: end f or
13: K ← K 0
14: if | K | > 0 then
15: ( e, K 0 ) ← selectEdge ( R , K , x e : e ∈ E )
16: x e ← 1
17: K ← K \ K 0
18: end if
19: end while
dif ferent strategies described ne xt use one (or a combination)
of the follo wing subsets of E ( R ) :
E M ( R ) is defined as follo ws: first, a counter is associated
to each edge in E ( R ) with the number of times it is
in the path pairs of R ; then, E M ( R ) is composed by
the edges with maximum counter v alue (i.e. the edges
whose upgrade improv es the a v ailability of more path
pairs).
E O ( R ) is defined as follo ws: first, a counter is associated
to each edge in E ( R ) with the number of path pairs
of R whose a v ailability becomes at least Λ if the
edge is upgraded; then, E O ( R ) is composed by the
edges with maximal counter v alue or is empty if the
maximal counter v alue is 0 (i.e. when not empty ,
it contains the edges whose upgrade results in the
highest number of path pairs fulfilling the required
a v ailability).
In the follo wing, we describe dif ferent greedy strategies,
creating dif ferent v ariants for the greedy algorithm:
• Min-Cost: Select the minimum upgrade cost edge in
E ( R ) .
• Min-Cost–Max-Count: Select the minimum upgrade
cost edge in E M ( R ) .
• Min-Cost–Max-On: Select the minimum upgrade cost
edge in E O ( R ) if E O ( R ) is not empty , or in E M ( R ) if
E O ( R ) is empty .
• Max-On–Max-Count: Select the edge in E M ( R ) that,
if upgraded, maximizes the number of path pairs whose
a v ailability becomes at least Λ . If no such edge exists,
select any edge in E M ( R ) .
• Max-Count–Max-On: Select among the edges in
E O ( R ) the one whose upgrade improv es the a v ailability
of more path pairs, or any edge in E M ( R ) if E O ( R ) is
empty .
I V . C O M P U T A T I O NA L R E S U L T S
The computational results presented in this section consider
two netw ork topologies (also used in [9]) representati ve of
typical telecommunication transport networks: the German y50
topology (geographical location of nodes a v ailable at [15]) and
the COR ONET CONUS topology (geographical location of
nodes a v ailable at http://www .monarchna.com/topology .html),
referred to as Coronet in this section. Since there is no
a v ailable information on the geographical path of each link,
we ha ve considered that links follo w the shortest path over
the terrestrial surface assuming that Earth is a sphere, as
already mentioned in section II. For both topologies, the in-
formation concerning edge lengths and geographical distance
between edge-edge pairs and node-edge pairs is a v ailable at
http://www .av .it.pt/asou/geodiv erse.htm.
In both topologies, we ha ve considered the w orst case of
set K composed by all node pairs. Then, for each ( s, t ) ∈ K ,
the maximum geodi versity v alue D M ax
st was obtained solving
the Maximum Distance D of Geodi v erse Paths (MDDGP)
optimization problem proposed in [9]. T able I sho ws the
topology characteristics of both networks.
Concerning the edge a v ailability v alues, we ha ve considered
the current a v ailability a e of e ∈ E based on its length [16]:
a e = 1 − M T T R
M T B F e
(9)
with
M T B F e [hrs] = C C × 365 × 24
cable length e
(10)
where M T B F and M T T R are the mean time between
failures and mean time to repair in hours, respecti vely (as in
in [4], we consider M T T R = 24 and C C = 450 ). C C is the
cable cut metric in km (cable lengths also in km). Moreov er ,
we ha ve assumed an upgraded a vailability a u
e for each edge
e ∈ E equi v alent to the addition of a parallel edge of the same
length. i.e., a u
e = a e (2 − a e ) .
Concerning the upgrade cost v alues, note first that in the
general case, the upgrade cost c e of each edge e ∈ E should be
composed by a fixed cost and a cost per unit length of the edge.
Since the expression to calculate the actual cost is uncertain
(it depends on many dif ferent factors), here, we analyze the
results of the dif ferent greedy strategies for the tw o extreme
cases: (1) the upgrade cost is the number of upgraded edges
(equi v alent to consider a cost of 1 per upgraded edge) and (2)
T ABLE I: Network characteristics ( | N | , | E | , d – a v erage node
degree, max L – maximum edge length, a vg L – av erage edge
length, max st D M ax
st ) – All lengths are in km.
Network | N | | E | d max L a vg L max st D M ax
st
Germany50 50 88 3.52 252 100.67 166
Coronet 75 99 2.64 1017 329.72 707
the upgrade cost of each edge is gi ven by its length (equi v alent
to consider a cost of 1 per length unit of each edge).
In the follo wing two subsections, we present and discuss
separately the computational results obtained to each network
topology .
A. Results for the Germany50 network
Due to its geographical cov erage and the considered edge
a v ailability v alues, Germany50 already pro vides four nines
( 0 . 9999 ) a v ailability between all node pairs e ven in the case
of requiring a geodi versity v alue D M ax
st for all node pairs
( s, t ) ∈ K . So, we ha ve considered a minimum a v ailability
Λ=0 . 99999 . T able II presents the number of upgraded edges,
the upgrade cost (length based) and the CPU time for the
geodi versity v alues D of 40 km, 80 km, 120 km and 160 km
(solutions providing the minimum number of upgraded edges
and/or the minimum upgrade cost highlighted in bold).
T able II shows that, in terms of number of upgraded edges,
the Min-Cost–Max-On has the best results, on a verage, b ut
both Max-On–Max-Count and Max-Count–Max-On are only
slightly worse. On the other hand, in terms of upgrade cost,
Max-On–Max-Count is clearly the best strategy . So, the main
conclusion is that Max-On–Max-Count is the best compromise
strategy for German y50, as it finds solutions with the lo west
costs and a number of upgraded edges at most 16% abov e the
minimum v alues found by any strate gy .
Moreov er , the simplest Min-Cost strategy is, by f ar , the
worst strate gy both in terms of number of upgraded edges
and upgrade cost, sho wing that considering the number of
path pairs whose a v ailability is improv ed by the selected edge
(as exploited by the other strate gies) leads to more ef ficient
algorithms. The Min-Cost strategy w as considered because it
is strongly associated with the objecti ve function in equation
(3). As expected, it resulted in a lar ge number of short edges
being selected for upgrade.
Finally , two e xpected observ ations are that, in the ov erall:
(1) higher geodi versity v alues D impose upgrade solutions
with both higher number of upgraded edges and cost (with
only a fe w exceptions); (2) the CPU times are also higher
since the number of iterations of MUCA G (see Algorithm 2)
gro ws with the number of upgraded edges.
Fig. 2 presents the solutions found by the best compromise
Max-On–Max-Count strategy for the four considered v alues
of D . Besides illustrating that higher v alues of D impose a
higher number of required upgraded edges, it also sho ws that
the set of upgraded edges required by a gi ven D is not a subset
of the set of upgraded edges required by a geodi versity v alue
higher than D . So, in practice, the right choice of parameter
D is of paramount importance since if later on the required
v alue D becomes lar ger , the previous upgraded edges might
not be the best choices.
Fig. 3 presents the solutions found by the other four
strategies for D = 80 km (the solution of Max-On–Max-Count
is in Fig. 2b). The Min-Cost solution (Fig. 3a) illustrates
the inef ficiency of this strate gy since it gi v es preference to
many shorter upgraded edges, some of them with a minor
T ABLE II: No. of upgraded edges, cost and CPU time for achieving Λ=0 . 99999 between all node pairs in German y50
Min-Cost Min-Cost–Max-Count Min-Cost–Max-On Max-On–Max-Count Max-Count–Max-On
D Edges Cost CPU(s) Edges Cost CPU(s) Edges Cost CPU(s) Edges Cost CPU(s) Edges Cost CPU(s)
40 40 2561 77.9 18 1507 13.5 15 1842 12.1 16 1469 12.7 14 1688 11.1
80 52 3684 3731.5 25 2289 139.8 20 2664 153.5 22 2260 137.9 21 2563 155.2
120 52 3684 5261.0 32 2843 447.0 25 3355 324.5 28 2839 428.3 27 3389 358.8
160 55 4046 6730.5 37 3285 648.0 26 3405 353.4 29 2914 573.0 25 3190 358.3
(a) D = 40 km (b) D = 80 km
(c) D = 120 km (d) D = 160 km
Fig. 2: Max-On–Max-Count: upgraded edges for achie ving
a v ailability Λ=0 . 99999 between all node pairs in Germany50
contrib ution to the av ailability improv ement of the dif ferent
path pairs, which ultimately leads to a higher upgrade cost.
The solutions of the other four strategies highlight tw o main
characteristics also observ able in the results of T able II. First,
strategies that consider the edges in E M ( R ) (i.e., the most
frequent edges in the path pairs of R ), namely , the Max-On–
Max-Count (Fig. 2b) and the Min-Cost–Max-Count (Fig. 3b),
find solutions with lo wer upgrade costs. Second, strategies that
consider the edges in E O ( R ) (i.e., edges whose upgrade makes
the a v ailability of more path pairs of R to become at least Λ ),
namely , the Min-Cost–Max-On (Fig. 3c) and the Max-Count–
Max-On (Fig. 3d), find solutions with a lo wer number of short
edges, leading to solutions with a lo wer number of upgraded
edges.
(a) Min–Cost (b) Min-Cost–Max-Count
(c) Min-Cost–Max-On (d) Max-Count–Max-On
Fig. 3: Upgraded edges for achie ving a v ailability Λ=0 . 99999
between all node pairs in Germany50, when D = 80 km
B. Results for the Cor onet network
The Coronet network has a much wider geographical co v-
erage and cannot provide four nines ( 0 . 9999 ) a vailability to
many node pairs wi thout upgraded edges. So, in this case, we
ha ve considered tw o minimum a v ailability v alues. T able III
(for Λ=0 . 9999 ) and T able IV (for Λ=0 . 99999 ) present the
number of upgraded edges, the upgrade cost and the CPU time
for the geodi versity v alues D of 100 km, 200 km, 400 km
and 600 km (as before, solutions providing the minimum
number of upgraded edges and/or the minimum upgrade cost
highlighted in bold).
T able III shows that for Λ=0 . 9999 the Max-On–Max-
Count and Max-Count–Max-On strategies are the best com-
promise between the number of upgraded edges and the
(a) Min-Cost; D = 200 km
(b) Min-Cost–Max-Count; D = 200 km
(c) Min-Cost–Max-On; D = 200 km
(d) Max-On–Max-Count; D = 200 km
(e) Max-Count–Max-On; D = 200 km
Fig. 4: Upgraded edges for achie ving a v ailability Λ=0 . 9999
between all node pairs in Coronet, when D = 200 km
upgrade cost: the Max-On–Max-Count obtains the lo west (or
very close to the lo west) upgrade costs with a number of
upgraded edges at most 16% higher than the lo west v alues
and the Max-Count–Max-On obtains the lo west number of
upgraded edges with an upgrade cost at most 18% higher
than the lo west v alues. On the other hand, T able IV sho w
that for Λ=0 . 99999 , with the exception of Min-Cost, which
is much worse, none of the other strate gies represents a better
compromise between the number of upgraded edges and the
upgrade cost.
The results of both tables reinforce the observ ations already
made for Germany50, namely , (1) Min-Cost is always the
worst strate gy , (2) the Max-Cost–Max-Count and Max-On–
Max-Count strategies (that gi ve preference to the most fre-
quent edges in the path pairs of R ) find solutions with lo wer
upgrade costs and (3) the Min-Cost–Max-On and the Max-
Count–Max-On strategies (that gi ve preference to edges whose
upgrade makes the a v ailability of more path pairs to become at
least Λ ) find solutions with a lo wer number of upgraded edges.
Fig. 4 presents the solutions found by the fi ve strate gies for
Λ=0 . 9999 and D = 200 km. In this figure, it is possible to
check that the Min-Cost strate gy selects a much higher number
of upgraded edges. Due to the lar ger dimension of this network
(when compared to the dimension of the Germany50 netw ork),
the dif ferences between the lengths of the selected edges are
not so clear . Howe ver , it is possible to observe that the Min-
Cost–Max-On (Fig. 4c) and the Max-Count–Max-On (Fig. 4e)
strategies tend to ha ve less short length edges.
V . C ONCLUSIONS AND F U RT H E R W O R K
T elecommunication networks must pro vide high end-to-
end a v ailability and high resilience to lar ge-scale disasters.
Path protection impro v es end-to-end av ailability but might be
not enough to reach the a v ailability required by critical ser -
vices. Moreov er , adding path geodi versity to enhance disaster -
resilience of networks mak es the provision of high end-to-end
a v ailability e ven more challenging.
Here, we ha ve addressed the problem of selecting a set of
edges to be upgraded at a minimum cost ensuring a required
le vel of a vailability and geodi versity . W e hav e proposed a
solving algorithm which uses an iterati v e approach based on
a greedy strategy: starting with the netw ork configuration
without upgraded edges, the algorithm selects iterati vely one
edge to be upgraded until the resulting network configuration
fulfils the required a v ailability and geodi versity le vels. Dif-
ferent edge selection strategies were proposed and tested on
a set of problem instances. The computational tests sho wed
that a simple strategy of edge selection only based on edge
cost is very inef ficient, while strategies taking into account the
improv ement impact of the selected edge on the end-to-end
a v ailability of node pairs lead to more ef ficient algorithms.
Reg arding future work, an e xact resolution approach and/or
lo wer bounds for the cost of the solutions will be pursued for
small network instances, which will allo w to gain some insight
into the quality of the approximate solutions and also to allo w
some tuning of the heuristics.
T ABLE III: No. of upgraded edges, cost and CPU time for achieving Λ=0 . 9999 between all node pairs in Coronet
Min-Cost Min-Cost–Max-Count Min-Cost–Max-On Max-On–Max-Count Max-Count–Max-On
D Edges Cost CPU(s) Edges Cost CPU(s) Edges Cost CPU(s) Edges Cost CPU(s) Edges Cost CPU(s)
100 84 21758 14491.2 45 13439 425.3 34 14593 297.3 38 13598 385.9 33 13494 472.2
200 88 23877 38019.7 53 15493 616.6 39 17237 600.1 44 15130 580.6 38 17031 603.3
400 91 26084 44959.8 56 18194 1126.6 45 19610 1002.2 46 17860 1036.8 44 19376 955.7
600 92 26718 46632.4 56 18482 1149.4 47 20584 1024.5 47 17865 1082.5 46 21066 984.7
T ABLE IV: No. of upgraded edges, cost and CPU time for achieving Λ=0 . 99999 between all node pairs in Coronet
Min-Cost Min-Cost–Max-Count Min-Cost–Max-On Max-On–Max-Count Max-Count–Max-On
D Edges Cost CPU(s) Edges Cost CPU(s) Edges Cost CPU(s) Edges Cost CPU(s) Edges Cost CPU(s)
100 91 26409 72949.7 82 24534 1482.1 66 26499 1775.3 68 23083 1139.6 66 26499 1812.9
200 94 28182 166467.9 86 25966 2125.3 69 26939 13086.8 72 24495 1649.9 67 26949 4101.8
400 97 30679 189654.7 88 27617 6223.4 72 28274 16829.8 79 28045 4218.5 72 28696 15630.1
600 98 31625 197249.8 89 28350 7070.0 71 28786 13718.6 79 28542 4688.7 72 29247 17911.4
A CKNO WLEDGMENT
A. de Sousa was supported by Fundac ¸ ˜
ao para a Ci ˆ
encia
e a T ecnologia (FCT) under project UID/EEA/50008/2013.
T . Gomes, R. Gir ˜
ao-Silv a and L. Martins were supported
by FCT under project UID/MUL TI/00308/2013 of INESC
Coimbra. This article is based upon work from COST Action
CA15127 (“Resilient communication services protecting end-
user applications from disaster -based failures – RECODIS”)
supported by COST (European Cooperation in Science and
T echnology).
R EFERENCES
[1] J. Rak, D. Hutchison, E. Calle, T . Gomes, M. Gunkel, P . Smith,
J. T . S. V erbrugge, and L. W osinska, “Recodis: Resilient communication
services protecting end-user applications from disaster-based f ailures, ”
in 18th International Confer ence on T ranspar ent Optical Networks
(ICTON) , July 10-14 2016. In vited paper .
[2] T . Gomes, J. T apolcai, C. Esposito, D. Hutchison, F . Kuipers, J. Rak,
A. de Sousa, A. Iossifides, R. T ra vanca, J. Andr ´
e, L. Jorge, L. Martins,
P . O. Ugalde, A. Pa ˇ
si ´
c, D. Pezaros, S. Jouet, S. Secci, and M. T ornatore,
“ A surve y of strategies for communication networks to protect ag ainst
large-scale natural disasters, ” in 8th International W orkshop on Resilient
Networks Design and Modeling (RNDM) , pp. 11–22, Sept 2016.
[3] D. T ipper , “Resilient network design: challenges and future directions, ”
T elecommunication Systems , vol. 56, no. 1, pp. 5–16, 2014.
[4] A. Alashaikh, T . Gomes, and D. T ipper , “The spine concept for improv-
ing network a v ailability , ” Computer Networks , vol. 82, no. 0, pp. 4 –
19, 2015.
[5] A. Alashaikh, D. T ipper , and T . Gomes, “Supporting dif ferentiated
resilience classes in multilayer networks, ” in 12th International Con-
fer ence on the Design of Reliable Communication Networks (DRCN) ,
pp. 31–38, March 2016.
[6] J. Rohrer , A. Jabbar , and J. P . G. Sterbenz, “Path di versification: a multi-
path resiliency mechanism, ” in 7th International W orkshop on the Design
of Reliable Communication Networks – DRCN 2009 , (W ashington, DC,
USA,), pp. 343–351, October 25-28 2009.
[7] Y . Cheng, M. T . Gardner , J. Li, R. May , D. Medhi, and J. P . Sterbenz,
“ Analysing geopath div ersity and improving routing performance in
optical networks, ” Computer Networks , vol. 82, pp. 50–67, 2015.
[8] S. T rajanovski, F . A. Kuipers, A. Ili ´
c, J. Cro wcroft, and P . V . Mieghem,
“Finding critical regions and re gion-disjoint paths in a network, ”
IEEE/A CM T ransactions on Networking , v ol. 23, pp. 908–921, June
2015.
[9] A. de Sousa, D. Santos, and P . Monteiro, “Determination of the
minimum cost pair of D -geodi verse paths, ” in The 2017 International
Confer ence on Design of Reliable Communication Networks (DRCN
2017) , (Munich), March 8-10 2017.
[10] J. Zhang, E. Modiano, and D. Hay , “Enhancing network rob ustness via
shielding, ” in Design of Reliable Communication Networks (DRCN),
2015 11th International Confer ence on the , pp. 17–24, March 2015.
[11] T . Gomes and J. Crav eirinha, “Efficient calculation of the most reliable
pair of link disjoint paths in telecommunication networks, ” Eur opean
J ournal of Operational Resear ch , vol. 182, no. 3, pp. 1055–1064, 2007.
[12] J. Y . Y en, “Finding the k shortest loopless paths in a network, ”
Management Science , v ol. 17, pp. 712–716, July 1971.
[13] E. Martins, M. Pascoal, and J. Santos, “ An algorithm for ranking loopless
paths, ” T ech. Rep. 99/007, CISUC, 1999.
[14] E. Martins, M. Pascoal, and J. Santos, “De viation algorithms for rank-
ing shortest paths, ” International Journal of F oundations of Computer
Science , vol. 10, no. 3, pp. 247–263, 1999.
[15] S. Orlo wski, R. W ess ¨
aly , M. Pi ´
oro, and A. T omaszewski, “SNDlib 1.0–
Survi vable Netw ork Design library , ” Networks , vol. 55, no. 3, pp. 276–
286, 2010. http://sndlib .zib .de.
[16] J.-P . V asseur , M. Picka vet, and P . Demeester , Network Recovery –
Pr otection and Restoration of Optical, SONET -SDH, IP, and MPLS .
Else vier , 2004.
