Information Technology Reference
In-Depth Information
number of idle-backup edges (
v
mn
) is determined. Finally, using an ILP and an appropriate
solver (e.g, CPLEX [39]), the cost of idle-backup edges
∑
is optimized.
4.8. Protection Algorithms under Reliability Constraints [40]
Most protection schemes provide 100% reliability that may not be necessary for some
users. In other words, it is possible that some users only require lower connection reliability.
The probability that a connection will work correctly in a period of time is called reliability
and is determined based on environmental and man-made factors such as humidity, fires, and
so on. The reliability of a multicast session is the least reliability of the paths from a source to
relevant destinations. Three protection algorithms under reliability constraints have been
proposed in [40] as follows, where Pruned Prim's Heuristic (PPH) [34] and Minimum-cost
Path heuristic (MPH) [41] are used to establish a required minimum-cost Steiner tree [42]:
a.
The first proposed algorithm is the ARC-disjoint tree with differentiated reliability
(ADT_DiR). Arcs are unidirectional edges and arc-disjoint paths are paths that may
share a link in the opposite direction. Moreover, two arc-disjoint trees may traverse a
common link only in an opposite direction. ADT_DiR is run as follows:
•
A primary tree is created using either PPH or MPH.
•
The reliability of the primary tree is checked, if it is not smaller than the user's
requirement, the multicast request is accepted; otherwise the arcs along the
primary tree is removed and a backup tree is constructed in the remaining graph
using either PPH or MPH.
b.
Partial tree protection (PTP) is the second protection algorithm suggested in [40]:
•
A primary tree is created using either PPH or MPH.
•
The reliability of the primary tree is checked. If it is not smaller than the user's
requirement, the multicast request is accepted and waits for another multicast
request. Otherwise, to create a small tree, unwanted branches of the primary tree
are pruned on which the destination satisfies the user's requirement without any
effect on other destinations.
•
An arc-disjoint tree is built for the small tree.
c.
The third proposed algorithm is Segment Protection with Most-likely Failure Link
(SP_MFL). Note that MFL means the fiber link whose reliable probability is the
lowest in the path. SP_MFL is executed as follows:
•
A primary tree is created using either PPH or MPH.
•
The reliability of the primary tree is checked, if it is not smaller than the user's
requirement, the multicast request is accepted and waits for another multicast
request; otherwise, go to the next step.
•
The primary segments on the primary tree are identified.
•
The set T is created, where it involves the paths that have lower reliability than
required reliability.
•
The least reliability path of T is selected and divided into several segments.
•
In order to meet the required reliability, the segments are chosen to be protected
by the segment protection algorithm (see Section 2.1.5).
