Information Technology Reference
In-Depth Information
protected by other leaf nodes of the backup path. Therefore, by decreasing the number of leaf
nodes on the primary tree, the number of backup paths and residual links go down.
Simulation results in [32] indicate that SLR-ARL can improve blocking probability about
10% over OPP-SDP when traffic load is high.
4.2. Multicast Protection through Spanning Paths (MPSP) [33]
The MSPS protection scheme is a path-based protection scheme that derives a backup
path for each spanning path and then selects part of these backup paths to protect the primary
multicast tree. In Figure13a [33], there are
s
destinations (shaded nodes) in the multicast tree
and
S
is the source node. In the multicast tree, there are three leaves, i.e., node
S
, node
C
, and
node
E
. Thus, we can derive three spanning paths.
A Backup Path (BP) for a given spanning path can be derived as follows. The links along
the given spanning path in the multicast tree and all the leaves close the two end nodes in the
spanning path are removed, and then an auxiliary graph is considered. In order to protect the
spanning path, the cost for each link is computed in the auxiliary graph. Finally, in the
auxiliary graph, a least-cost backup path is obtained using a shortest path algorithm.
Figure13.b to Figure13.d show the process of deriving backup paths from spanning paths. For
example, to derive a backup path for the spanning path SP1= (S→A→B→C), links S→A,
A→B, B→E, and the leaf C are deleted.
Now we can choose part of the backup paths to protect the primary multicast tree. Link
Cost Gain of a Backup Path (LGBP) is defined as the ratio of the cost of a backup path over
the cost of the spanning path corresponding to the backup path. For example, the LCGBP for
SP1 in Figure13b [33] is 100/85 since the costs of SP1 and BP1 are 85 and 100, respectively.
If LCGBP is a large number, it means that more spare capacity will be consumed to protect a
given spanning path. With LCGBP, an auxiliary graph is created as follows. First, all leaves
of the multicast tree are added into a graph. Second, for each node pair, if there exists a
backup path for the spanning path between the node pair, add a link between them. Finally,
assign the LCGBP of each backup path to its corresponding link.
Now, in order to choose the backup paths, the minimum spanning tree in the auxiliary
graph should be obtained. The MST (Minimum Spanning Tree) algorithm [34] calculates the
minimum spanning tree in the auxiliary graph. Derived backup paths for protecting the
primary tree are shown in Figure13f [33].
After deriving the primary multicast tree and its backup paths, resources for the primary
multicast tree and its protection paths are allocated as follows:
1)
for each link in the set of links in the primary multicast tree, assign
w
units of
bandwidth as working bandwidth; and
2)
for each link in the set of links in the backup path, we should take intra-request
sharing
4
into consideration in order to consume as small capacity as possible.
4
One type of bandwidth sharing is intra-request sharing defined as follows. In local restoration, since each link on
the primary path needs a backup path, and only one link failure can occur at any given time, the backup paths
for different links in the same primary path can share links. Moreover, backup paths can share the primary
path links.
