Information Technology Reference
In-Depth Information
1)
Generation of the auxiliary graph (AG):
In the generation phase, the map of each
node
x
and corresponding physical edges of
x
are first added to the physical layer.
Cost of physical edges (
x
p
,y
p
) and (
y
p
, x
p
) are set to infinity if the physical link (
x,y
) is
used by the light tree. Costs of other physical edges in the physical layer are set to the
corresponding link in the physical network. Moreover, the map of each node
x
and
corresponding sharing edges of
x
are added to the sharing layer. The costs of the
corresponding sharing edges are set to zero. Finally, the physical layer and sharing
layer are connected together by adding and dropping edges. The costs of adding and
dropping edges are set to zero.
2)
Finding the most efficient backup paths for leaf nodes:
In the second phase, backup
path for each leaf should be found. For each link on the primary path from source
node to leaf node l, the cost of corresponding FS edge (
x
p
, y
p
) and
RS
edge starting at
x
p
in the sharing layer of
AG
are set to infinity. In order to determine the shortest path
of (
s
p
, l
p
) in the
AG
, the Dijkstra's algorithm is run. For each link over path of (
x, y
),
the cost of corresponding
FS
edge (
x
s
, y
s
) and
RS
edge starting at
x
p
in the sharing
layer of the
AG
are set to zero. The leaf node
u
with minimum protection gain (see
Eq.(9)) is selected. For each physical edge (
x
p
, y
p
) belonging to backup path of
(
s
p
,u
p
), the cost of physical edges (
x
p
, y
p
) and (
y
p
, x
p
) in the physical layer are set to
zero. Then, the corresponding physical link (
x, y
) is added to set
B
. This process is
run for all leaf nodes. Finally, the light tree is removed from the primary light forest,
if the primary light forest is equal to null; the
B
is shown as the backup topology in
order to protect the primary light forest.
Protection gain=
(9)
4.7. Cross-Sharing [10]
In order to protect multicast sessions from any single link failure and to save cost of
backup sources, a new cross-sharing mechanism has been introduced based on link-vector
model in [10] which allows sharing of backup resources among several light-trees. This
algorithm assumes that each link has a weight (
c
mn
) to represent the cost of moving traffic
from one node to another. In addition, all nodes have multicast-capable opaque cross-
connects to convert the signal from optical to electrical and then to optical domain.
In the first step, a minimum-cost primary tree is calculated for each multicast session
j
based on an Integer linear Program (ILP) [34]. In order to keep the topology of the network
for multicast session
j,
matrix
P
j
is used. For each pair nodes
m
and
n
,
is set to 1 if there
is an edge from
m
to
n
; otherwise it is set to 0. Moreover, if this edge carries traffic to
destination
d
j
,
is also set to 1; otherwise it is set to 0. Then, for each
d
j
, a backup path
is determined so that it is link-disjoint to
. In the second step, the link-vector of tree
j
. Note that
is set for edge from
m
to
n
,
and
are node indices where there is a failure
between them. If an idle-backup edge of tree
j
on the edge from
m
to
n
becomes active for any
destination
d
j
,
is set to 1. Then, for every edge from
m
to
n
, the maximum required
