Dual-Link Failure Resiliency Through Backup Link Mutual Exclusion
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
computer science technology
Active In SP
**

Posts: 740
Joined: Jan 2010
#1
20-01-2010, 09:54 AM


Dual-Link 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 dual-link failure resiliency. One of the strategies to recover from dual-link 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 dual-link 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 dual-link 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 dual-link 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/Srini-2004-TR-DualLink.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
Reply
puni
Active In SP
**

Posts: 1
Joined: Apr 2010
#2
05-05-2010, 08:36 PM

pLz....... provide PPT and Report of Dual-Link Failure Resiliency Through Backup Link Mutual Exclusion
Reply
projectsofme
Active In SP
**

Posts: 1,124
Joined: Jun 2010
#3
29-09-2010, 05:07 PM


.doc   Dual link Dual Link Failure Resiliency through Backup Path Mutual Exclusion.doc (Size: 30 KB / Downloads: 76)
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 dual-link failure resiliency. One of the strategies to recover from dual-link 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 ever-increasing transmission speed in the communication networks calls for efficient fault-tolerant 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 high-speed networks.
Reply
projectsofme
Active In SP
**

Posts: 1,124
Joined: Jun 2010
#4
18-10-2010, 10:00 AM


.ppt   Dual Link Failure Resiliency through Backup Path Mutual Exclusion.ppt (Size: 684 KB / Downloads: 86)
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 dual-link failure resiliency. One of the strategies to recover from dual-link 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 single-link 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.


Reply
chandrika89
Active In SP
**

Posts: 1
Joined: Dec 2010
#5
07-12-2010, 02:41 PM

i want the introduction and full details about the dual link falilure and details of paper[/size][/font]
Reply
seminar surveyer
Active In SP
**

Posts: 3,541
Joined: Sep 2010
#6
08-12-2010, 09:34 AM

please download the attachment files given in above posts
Reply
johnson1989
Active In SP
**

Posts: 2
Joined: Dec 2010
#7
03-04-2011, 12:18 PM

i want final project and implimentation documentation pls send me as soon as psossible i have it tomorrow
Reply
seminar class
Active In SP
**

Posts: 5,361
Joined: Feb 2011
#8
02-05-2011, 09:22 AM


.doc   project doc.doc (Size: 282.5 KB / Downloads: 37)
Dual-Link Failure Resiliency Through Backup Link Mutual Exclusion
Introduction

THE ever-increasing transmission speed in the communication networks calls for efficient fault-tolerant 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 high-speed 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 circuit-switched manner as optical header processing and buffering technologies are still in the early stages of research for wide-scale commercial deployment. Protecting the circuits or connections established in such networks against single-link failures may be achieved in two ways: path protection or link protection.
Path protection attempts to restore a connection on an end-to-end 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 link-disjoint with the primary path allows recovery from single-link 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 failure-independent path protection (FIPP) while the latter is referred to as failure-dependent 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 end-nodes, re-initiate 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 single-link 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 single-link failure resiliency is shown to cover a good percentage of dual-link 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 dual-link failures, they may serve as an alternative to recover from independent dual-link 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.
Dual-link 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 end-to-end connections from dual-link 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 dual-link failure resiliency. One of the strategies to recover from dual-link 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 dual-link 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 dual-link 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 dual-link 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 bi-directional. 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
Three-edge-connectivity is a necessary condition for a network to be resilient to dual link failures. It is also sufficient that a network is three-edge-connected 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 Sum-of-Product and Product-of-Sum 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 .Observation-1: 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.Observation-2: If Γl= 0 for some l ∈ L, then the network is one-edge connected. The failure of link l disconnects the network. Conversely, if a network is at least two-edge-connected, 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 of-product and product-of-sum 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 non-zero function, then there exists an input combination for which the function evaluates to 1 (true).
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Message
Type your reply to this message here.


Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  Test case Reduction-An Experimental Analysis through Coverage Techniques seminar addict 1 705 18-03-2014, 02:37 PM
Last Post: Guest
  Mobile Data Offloading through Opportunistic Communications and Social pdf study tips 0 349 14-08-2013, 04:10 PM
Last Post: study tips
  DATA BACKUP AND RECOVERY IN DBMS seminar class 2 5,941 24-07-2013, 10:18 AM
Last Post: study tips
  A LINK ANALYSIS EXTENSION OF CORRESPONDENCE ANALYSIS FOR MINING RELATIONAL REPORT study tips 0 246 03-07-2013, 04:43 PM
Last Post: study tips
  Distributed Mutual Exclusion Algorithms pdf study tips 0 263 27-06-2013, 01:10 PM
Last Post: study tips
  Link Prediction pdf study tips 0 226 19-06-2013, 12:30 PM
Last Post: study tips
  Exposing Postprocessed Copy–Paste Forgeries Through Transform-Invariant Features pdf study tips 0 221 16-05-2013, 11:44 AM
Last Post: study tips
  WRAPS: Denial-of-Service Defense through Web Referrals pdf study tips 0 244 01-05-2013, 03:19 PM
Last Post: study tips
  The Data Link Layer PPT study tips 0 312 28-02-2013, 02:39 PM
Last Post: study tips
  Black Box Backup System pdf study tips 0 385 27-02-2013, 02:48 PM
Last Post: study tips