Information Technology Reference
In-Depth Information
−
constraints to ensure that every backup path is node-disjoint with its working path:
L
∑
∑
l
l
(
x
+
y
)
≤
1
(4)
k
,
m
k
,
m
l
=
1
m
∈
{
m
:
e
≡
(
n
,
j
)
∈
A
;
m
j
=
1
2
,...,
N
;
j
≠
n
}
L
∑
∑
l
l
(
x
+
y
)
≤
1
(5)
k
,
m
k
,
m
l
=
1
m
∈
{
m
:
e
≡
(
i
,
n
)
∈
A
;
m
i
=
1
2
,...,
N
;
i
≠
n
}
where:
n
≠
s
k
; n
≠
t
k
;
for transit nodes (when both paths consist of at least two arcs);
n
≠
t
k
;
for (4), when the working path consists of one direct arc;
n
≠
s
k
;
for (5), when the working path consists of one direct arc;
−
nonnegativity constraints
all the variables should obtain nonnegative values
Unfortunately, the optimization problem (1) - (5) is NP complete [1]. For that rea-
son we developed an efficient heuristic algorithm.
3 Heuristic SCRP Algorithm
In Fig. 1 we describe the SCRP algorithm finding survivable connections in the con-
text of region protection. Each backup path is node-disjoint with a certain region of
the active path. It's main advantage is the polynomial complexity.
SCRP A
LGORITHM
Step 1.
Find the active path
Π
between nodes
(
s
k
t
,
)
, using Dijkstra's [2] algorithm.
k
k
Step 2.
Set the source node
s
as the starting node
b
.
Step 3a.
Find the shortest path tree
T
from
t
to
b
.
Step 3b.
Start computing the backup path from
b,
using Dijkstra's algorithm, until the
current node (say node
x
) reaches the tree
T
.
Step 3c.
Determine the next part of the backup path as the fragment of the shortest path
tree
T
from node
x
to the first node (say node
y
) that belongs both to the tree
T
and to the active path Π .
Step 3d.
Accept the path between nodes
b
and
y
(calculated in steps
3b
and
3c
) as the
backup path.
Step 3e.
Set
b = z
where
z
is a node of an active path, preceding the node
y
(i.e. placed
upstream towards the source node).
Step 4.
If
b <>
k
t
then go to step
3a
else return the paths for the connection.
Fig. 1.
SCRP algorithm
