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