Information Technology Reference
In-Depth Information
individually protected area in a link protection technique. In this scheme a given
backup path protects a single link of an active path (against the failure of a link) or
two adjacent links of an active path (against the failure of a node).
In the region protection scheme each backup path protects a certain region of an
active path. Size of this region is a compromise between appropriate lengths of indi-
vidually protected areas in link and path protection schemes, respectively. Compared
to the path protection, backup paths are expected to be shorter, which causes the faster
restoration process. The level of resource utilization remains smaller than for the link
restoration scheme, since for each connection less backup paths are needed.
The rest of the paper is organized as follows. Section 2 is devoted to ILP problem
formulation, while Section 3 to the description of our heuristic algorithm. In Section 4
we compare our heuristic results of the US National Science Foundation (NSF) net-
work modeling to the exact results of the CPLEX program. The convergence is al-
most ideal. Results of U.S. Long-Distance Network modeling for all three protec-
tion/restoration schemes are discussed in the concluding part of the paper.
2 ILP Model to Find Node-Disjoint Path Pairs
(Dedicated Backup)
We consider a directed network
(N,A), where: N - set of nodes; |N| = N; A - set of
directed arcs; |A| = M. Each arc em
Γ
A is characterized by length, cost and offers L
channels, each of a standard capacity. Source-destination pairs of nodes (sk, tk) (de-
mands) are given, where: k = 1, 2,…, K; 1< K
∈
(N-1).
It is to find paths transporting required flows from sources to destinations, protect-
ing them against a single node failure and minimizing the linear cost:
≤
N
×
K
L
M
=
∑∑∑
== =
l
l
(1)
ϕ
(
x
)
κ
(
x
+
y
)
k
,
m
k
,
m
k
,
m
k
11 1
l
m
e
m
∈
A
;
where:
κ
= cost per unit flow of the
k
-th commodity on the arc
k
,
m
e
m
∈
l
(
) =
k
-th demand flow on the
l
-th channel on the arc
A
of
x
,
l
y
,
m
m
a working (backup) path, respectively;
subject to:
flow conservation constraints for the l-th channel
on working (backup)
3
paths:
−
1
if
n
=
s
⎧
k
⎨
(2)
∑
∑
l
l
x
−
x
=
−
1
if
n
=
t
k
,
m
k
,
m
k
⎩
m
∈
{
m
:
e
≡
(
n
,
j
)
∈
A
;
m
∈
{
m
:
e
≡
(
i
,
n
)
∈
A
;
0
otherwise
m
m
j
=
1
2
,...,
N
;
j
≠
n
}
i
=
1
2
,...,
N
;
i
≠
n
}
where:
e
m
= (
i, n
) = arc incident into node
n
;
e
m
= (
n, j
) = arc incident out of node
n
;
k=
1, 2,. .,
K; l=
1, 2,. .,
L; n=
1, 2,. .,
N;
−
finite arc capacity constraints:
L
K
∑
==
l
l
(3)
(
x
+
y
)
≤
c
=
L
k
,
m
k
,
m
m
l
11
k
where:
m=
1, 2, …,
M;
3
Equations for backup paths are similar to (
2
) with
l
l
x
.
y
.
replaced with
m
m
