DualLink Failure Resiliency Through Backup Link Mutual Exclusion
computer science technology Active In SP Posts: 740 Joined: Jan 2010 
20012010, 09:54 AM
DualLink Failure Resiliency Through Backup Link Mutual Exclusion Abstractâ€ Networks employ link protection to achieve fast recovery. While the first link failure can be protected using link protection, there are several alternatives for protecting against the second failure. This paper formally classifies the approaches to duallink failure resiliency. One of the strategies to recover from duallink failures is to employ link protection for the two failed links independently, which requires that two links may not use each other in their backup paths if they may fail simultaneously. Such a requirement is referred to as Backup Link Mutual Exclusion (BLME) constraint and the problem of identifying a backup path for every link that satisfies the above requirement is referred to as the BLME problem. This paper develops the necessary theory to establish the sufficient conditions for existence of a solution to the BLME problem. Solution methodologies for the BLME problem is developed using two approaches by: (1) formulating the backup path selection as an integer linear program; and (2) developing a polynomial time approximation algorithm based on minimum cost path routing. The ILP formulation and heuristic are applied to six networks and their performance is compared to approaches that assume precise knowledge of duallink failure. It is observed that a solution exists for all the six networks considered. The heuristic approach is shown to obtain feasible solutions that are resilient to most duallink failures, although the backup path lengths may be significantly higher than optimal. In addition, the paper illustrates the significance of the knowledge of failure location by illustrating that network with higher connectivity may require lesser capacity than one with a lower connectivity to recover from duallink failures. Srinivasan Ramasubramanian and Amit Chandak TECHNICAL REPORT, ECE, UNIVERSITY OF ARIZONA 1 read full report citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.111.210&rep=rep1&type=pdf ece.arizona.edu/~srini/papers/Srini2004TRDualLink.pdf Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion



puni Active In SP Posts: 1 Joined: Apr 2010 
05052010, 08:36 PM
pLz....... provide PPT and Report of DualLink Failure Resiliency Through Backup Link Mutual Exclusion



projectsofme Active In SP Posts: 1,124 Joined: Jun 2010 
29092010, 05:07 PM
Dual link Dual Link Failure Resiliency through Backup Path Mutual Exclusion.doc (Size: 30 KB / Downloads: 77) Dual Link Failure Resiliency through Backup Path Mutual Exclusion INTRODUCTION Networks employ link protection to achieve fast recovery from link failures. While the first link failure can be protected using link protection, there are several alternatives for protecting against the second failure. This paper formally classifies the approaches to duallink failure resiliency. One of the strategies to recover from duallink failures is to employ link protection for the two failed links independently, which requires that two links may not use each other in their backup paths if they may fail simultaneously. Such a requirement is referred to as backup link mutual Exclusion (BLME) constraint and the problem of identifying a backup path for every link that satisfies the above requirement is referred to as the BLME problem. This paper develops the necessary theory to establish the sufficient conditions for existence of a solution to the BLME problem. Solution methodologies for the BLME problem is developed using two approaches by
1) Formulating the backup path selection as an integer linear program 2) Developing a polynomial time heuristic based on minimum cost Path routing. Problem Description: The everincreasing transmission speed in the communication networks calls for efficient faulttolerant network design. Today’s backbone networks employ optical communication technology involving wavelength division multiplexing (WDM). A link between two nodes comprises of multiple fibers carrying several tens of wavelengths with transmission speed on a wavelength at 40 Gb/s. Due to the large volume of information transported, it is necessary to reduce the resource unavailability time due to failures. Hence, efficient and fast recovery techniques from node and link failures are mandated in the design of highspeed networks. 


projectsofme Active In SP Posts: 1,124 Joined: Jun 2010 
18102010, 10:00 AM
Dual Link Failure Resiliency through Backup Path Mutual Exclusion.ppt (Size: 684 KB / Downloads: 87) Dual Link Failure Resiliency through Backup Path Mutual Exclusion Abstract Networks employ link protection to achieve fast recovery from link failures. While the first link failure can be protected using link protection, there are several alternatives for protecting against the second failure. This paper formally classifies the approaches to duallink failure resiliency. One of the strategies to recover from duallink failures is to employ link protection for the two failed links independently, which requires that two links may not use each other in their backup paths if they may fail simultaneously. Such a requirement is referred to as backup link mutual Exclusion (BLME) constraint and the problem of identifying a backup path for every link that satisfies the above requirement is referred to as the BLME problem. This paper develops the necessary theory to establish the sufficient conditions for existence of a solution to the BLME problem. Solution methodologies for the BLME problem is developed using two approaches by 1) Formulating the backup path selection as an integer linear program 2) Developing a polynomial time heuristic based on minimum cost Path routing. PROBLEM ANALYSIS: Link protection recovers from a single link failure by rerouting connections around the failed link. Such a recovery may be achieved transparent to the source and destination of the connections passing through the failed link. Algorithms for protection against link failures have traditionally considered singlelink failures. Dual link failures are becoming increasingly important due to two reasons. First, links in the networks share resources and the failure of such shared resources result in the failure of multiple links. Second, the average repair time for a failed link is in the order of a few hours to few days and this repair time is sufficiently long for a second failure to occur. 


chandrika89 Active In SP Posts: 1 Joined: Dec 2010 
07122010, 02:41 PM
i want the introduction and full details about the dual link falilure and details of paper[/size][/font]



seminar surveyer Active In SP Posts: 3,541 Joined: Sep 2010 
08122010, 09:34 AM
please download the attachment files given in above posts



johnson1989 Active In SP Posts: 2 Joined: Dec 2010 
03042011, 12:18 PM
i want final project and implimentation documentation pls send me as soon as psossible i have it tomorrow



seminar class Active In SP Posts: 5,361 Joined: Feb 2011 
02052011, 09:22 AM
project doc.doc (Size: 282.5 KB / Downloads: 38) DualLink Failure Resiliency Through Backup Link Mutual Exclusion Introduction THE everincreasing transmission speed in the communication networks calls for efficient faulttolerant network design. Today’s backbone networks employ optical communication technology involving wavelength division multiplexing (WDM). A link between two nodes comprises of multiple fibers carrying several tens of wavelengths with transmission speed on a wavelength at 40 Gb/s. Due to the large volume of information transported, it is necessary to reduce the resource unavailability time due to failures. Hence, efficient and fast recovery techniques from node and link failures are mandated in the design of highspeed networks. As link failures are the most common case of the failures seen in the networks, this paper restricts its scope to link failures alone. Optical networks of today operate in a circuitswitched manner as optical header processing and buffering technologies are still in the early stages of research for widescale commercial deployment. Protecting the circuits or connections established in such networks against singlelink failures may be achieved in two ways: path protection or link protection. Path protection attempts to restore a connection on an endtoend basis by providing a backup path in case the primary (or working) path fails. The backup path assignment may be either independent or dependent on the link failure in the network. For example, a backup path that is linkdisjoint with the primary path allows recovery from singlelink failures without the precise knowledge of failure location. On the other hand, more than one backup path may be assigned for a primary path and the connection is reconfigured on the backup path corresponding to the failure scenario that resulted in the primary path failure. The former is referred to as failureindependent path protection (FIPP) while the latter is referred to as failuredependent path protection (FDPP). Link protection recovers from a single link failure by rerouting connections around the failed link. Such a recovery may be achieved transparent to the source and destination of the connections passing through the failed link. Link protection at the granularity of a fiber switches all of the connections on a fiber to a separate (spare) fiber on the backup path. The time needed to detect the fault, communicate to the endnodes, reinitiate connection requests on the backup paths, and reconfigure the switches at the intermediate nodes could sometimes cause the layers above the optical layer to resort to their own restoration solutions. Link protection reduces the communication requirement as compared to path protection, thus providing fast recovery. However, the downside of link protection is that its capacity requirement is higher than that of path protection, specifically when protection is employed at the connection granularity Algorithms for protection against link failures have traditionally considered singlelink failures [3]–[5] (for a detailed description on protection approaches, refer to [6]). However, dual link failures are becoming increasingly important due to two reasons. First, links in the networks share resources such as conduits or ducts and the failure of such shared resources result in the failure of multiple links. Second, the average repair time for a failed link is in the order of a few hours to few days [6], and this repair time is sufficiently long for a second failure to occur. Although algorithms developed for singlelink failure resiliency is shown to cover a good percentage of duallink failures [7]–[10], these cases often include links that are far away from each other. Considering the fact that these algorithms are not developed for duallink failures, they may serve as an alternative to recover from independent duallink failures. However, reliance on such approaches may not be preferable when the links close to one another in the network share resources, leading to correlated link failures. Duallink failures may be modeled as shared risk link group (SRLG) failures. A connection established in the network may be given a backup path under every possible SRLG failure. This approach assumes a precise knowledge of failure locations to reconfigure the failed connections on their backup paths. An alternative is to protect the connections using link protection, where only the nodes adjacent to the failed link (and those involved in the backup path of the link) will perform the recovery. The focus of this paper is to protect endtoend connections from duallink failures using link protection. Abstract Networks employ link protection to achieve fast recovery from link failures. While the first link failure can be protected using link protection, there are several alternatives for protecting against the second failure. This paper formally classifies the approaches to duallink failure resiliency. One of the strategies to recover from duallink failures is to employ link protection for the two failed links independently, which requires that two links may not use each other in their backup paths if they may fail simultaneously. Such a requirement is referred to as backup link mutual exclusion (BLME) constraint and the problem of identifying a backup path for every link that satisfies the above requirement is referred to as the BLME problem. This paper develops the necessary theory to establish the sufficient conditions for existence of a solution to the BLME problem. Solution methodologies for the BLME problem is developed using two approaches by: 1) formulating the backup path selection as an integer linear program; 2) developing a polynomial time heuristic based on minimum cost path routing. The ILP formulation and heuristic are applied to six networks and their performance is compared with approaches that assume precise knowledge of duallink failure. It is observed that a solution exists for all of the six networks considered. The heuristic approach is shown to obtain feasible solutions that are resilient to most duallink failures, although the backup path lengths may be significantly higher than optimal. In addition, the paper illustrates the significance of the knowledge of failure location by illustrating that network with higher connectivity may require lesser capacity than one with a lower connectivity to recover from duallink failures. THEORY Consider a network represented as a graph G(N, L), where N and L denote a set of nodes and undirected links, respectively. The nodes are numbered from 1 through N. A link l ∈ L is assumed to be bidirectional. Let x1 and yl denote the identifiers of the nodes connected by link l such that x Let A represent the set of directional links, or arcs, in the network. An arc from node i to j is denoted as (i, j). The failure of link l is assumed to affect the arcs in both directions. Let F denote the set of dual link failures to be tolerated. An element f ∈ F consists of exactly two undirected links, or correspondingly four directed arcs. Sufficient condition for existence of a solution Threeedgeconnectivity is a necessary condition for a network to be resilient to dual link failures. It is also sufficient that a network is threeedgeconnected in order to obtain a solution for BLME problem, proved as follows. Assume that the given network is divided into L auxiliary graphs. An auxiliary graph Xl is constructed by removing link l from the original network: Xl= G(N, L − {l}). In each auxiliary graph Xl, the goal is to identify a path Pl from node xl to yl. Let θll be a binary variable that indicates whether link l is present in the backup path of link l: 1 if true, 0 otherwise. Let Γl be the boolean function that denotes the connectivity between nodes xl and yl in the auxiliary graph Xl, represented as a function of the variable set {θll: l ∈ Xl}. Consider the example network shown in Figure 5(a). The auxiliary graph corresponding to link 1 is shown in Figure 5(b). The boolean function representing the connectivity between nodes A and B is shown in Equations (1) and (2) in SumofProduct and ProductofSum forms, respectively It may be observed that Γl is an unate function, hence has a trivial solution. If the function Γl evaluates to 1 (true) for some input combination of {θll: l ∈ Xl}, then there exists a path between the nodes xl and yl in Xl .Observation1: The connectivity functions Γl and Γl are independent of each other for any two distinct links l, l ∈ L, i.e. the functions Γl and Γl do not have any variables in common.Observation2: If Γl= 0 for some l ∈ L, then the network is oneedge connected. The failure of link l disconnects the network. Conversely, if a network is at least twoedgeconnected, then Γl = 0, ∀l ∈ L. The different connectivity functions are related to each other through the BLME constraint. The BLME constraint corresponding to a dual link failure f ∈ F is written in the sum ofproduct and productofsum forms as shown Equations (3) and (4), respectively The BLME problem is then written as a boolean satisfia bility problem, denoted by Θ, as shown in Equation (5). It is observed that Θ is a function of the set of variables {θll: l ∈ Xl, l ∈ L}. If the boolean function Θ is identically 0for all input combinations, then the BLME problem does not have a feasible solution. If Θ evaluates to a nonzero function, then there exists an input combination for which the function evaluates to 1 (true). 


