Dual-Link Failure Resiliency Through Backup Link Mutual Exclusion
#1

Dual-Link Failure Resiliency Through Backup Link Mutual Exclusion

Abstract”
Networks employ page link protection to achieve fast recovery. While the first page link failure can be protected using page 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 page 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 page 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
http://citeseerx.ist.psu.edu/viewdoc/dow...1&type=pdf
http://ece.arizona.edu/~srini/papers/Sri...alLink.pdf
Reply
#2
pLz....... provide PPT and Report of Dual-Link Failure Resiliency Through Backup Link Mutual Exclusion
Reply
#3
[attachment=4631]
Dual Link Failure Resiliency through Backup Path Mutual Exclusion


INTRODUCTION


Networks employ page link protection to achieve fast recovery from page link failures. While the first page link failure can be protected using page 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 page 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 page link mutual Exclusion (BLME) constraint and the problem of identifying a backup path for every page 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 page 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 page link failures are mandated in the design of high-speed networks.
Reply
#4
Brick 
[attachment=6367]
Dual Link Failure Resiliency through
Backup Path Mutual Exclusion



Abstract


Networks employ page link protection to achieve fast recovery from page link failures. While the first page link failure can be protected using page 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 page 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 page link mutual Exclusion (BLME) constraint and the problem of identifying a backup path for every page 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 page 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 page link failures have traditionally considered single-link failures.


Dual page 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 page 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
#5
i want the introduction and full details about the dual page link falilure and details of paper[/size][/font]
Reply
#6
please download the attachment files given in above posts
Reply
#7
i want final project documentation pls send me as soon as psossible i have it tomorrow
Reply
#8

[attachment=13177]
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 page 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 page link failures are mandated in the design of high-speed networks. As page link failures are the most common case of the failures seen in the networks, this paper restricts its scope to page 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 page 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 page 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 page 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 page 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 page link failures have traditionally considered single-link failures [3]–[5] (for a detailed description on protection approaches, refer to [6]). However, dual page 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 page 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 page link failures.
Dual-link failures may be modeled as shared risk page 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 page link protection, where only the nodes adjacent to the failed page 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 page link protection.
Abstract
Networks employ page link protection to achieve fast recovery from page link failures. While the first page link failure can be protected using page 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 page 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 page link mutual
exclusion (BLME) constraint and the problem of identifying a backup path for every page 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 page link l ∈ L is assumed to be bi-directional. Let x1 and yl denote the identifiers of the nodes connected by page 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 page link l is assumed to affect the arcs in both directions. Let F denote the set of dual page 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 page 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 page link l is present in the backup path of page 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 page 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 page 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 page 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
Popular Searches: bit stuffing data link layer, stepper motor control wirelessly using rf link, mortal kombat project download link, link between physical education and, link access protocol d, east link engineering company, mutual exclusion project code,

[-]
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
  Wimax Broadband wireless access through 802 16 nit_cal 1 1,829 02-11-2012, 04:10 PM
Last Post: seminar details
  Controlling IP Spoofing Through Inter-Domain Packet Filters seminar surveyer 1 2,479 29-02-2012, 12:51 PM
Last Post: seminar paper
  E-Learning: Learning Through Internet project topics 2 3,271 27-10-2011, 09:44 AM
Last Post: seminar addict
  Dual-Quorum Replication System for Edge Services summer project pal 1 1,774 23-04-2011, 03:44 PM
Last Post: seminar class
  dual core processors shibin.sree 4 4,391 21-04-2011, 03:39 PM
Last Post: seminar class
  DATA BACKUP AND RECOVERY IN DBMS seminar class 0 3,128 21-04-2011, 10:00 AM
Last Post: seminar class
  Face Detection Through Neural Analysis seminar project explorer 0 631 14-03-2011, 09:40 PM
Last Post: seminar project explorer
  An Application to ensure Security through Bit-level Encryption seminar surveyer 0 1,132 14-10-2010, 09:56 AM
Last Post: seminar surveyer
  ELEMENTARY DATA LINK PROTOCOLS projectsofme 0 4,981 29-09-2010, 11:08 AM
Last Post: projectsofme
  Data transfer through skin by human area networking full report project topics 4 12,457 30-07-2010, 03:06 PM
Last Post: sumaya shawkath

Forum Jump: