NDLI: Region-based connectivity - a new paradigm for design of fault-tolerant networks

Content Provider	IEEE Xplore Digital Library
Author	Sen, A. Murthy, S. Banerjee, S.
Copyright Year	2009
Description	Author affiliation: Department of Computer Science and Engineering, Arizona State University, Tempe, 85281, USA (Sen, A.; Murthy, S.; Banerjee, S.)
Abstract	The studies in fault-tolerance in networks mostly focus on the connectivity of the graph as the metric of faulttolerance. If the underlying graph is k-connected, it can tolerate up to k — 1 failures. In measuring the fault tolerance in terms of connectivity, no assumption regarding the locations of the faulty nodes are made - the failed nodes may be close to each other or far from each other. In other words, the connectivity metric has no way of capturing the notion of locality of faults. However in many networks, faults may be highly localized. This is particularly true in military networks, where an enemy bomb may inflict massive but localized damage to the network. To capture the notion of locality of faults in a network, a new metric region-based connectivity (RBC) was introduced in [1]. It was shown that RBC can achieve the same level of fault-tolerance as the metric connectivity, with much lower networking resources. The study in [1] was restricted to single region fault model (SRFM), where faults are confined to one region only. In this paper, we extend the notion of RBC to multiple region fault model (MRFM), where faults are no longer confined to a single region. As faults in MRFM are still confined to regions, albeit multiple of them, it is different from unconstrained fault model where no constraint on locality of faults is imposed. The MRFM leads to several new concepts, such as region-disjoint paths and region cuts. We show that the classical result, the maximum number of node-disjoint paths between a pair of nodes is equal to the minimum number of nodes whose removal disconnects the pair, is no longer valid when region-disjoint paths and region cuts are considered. We prove that the problems of finding (i) the maximum number of region-disjoint paths between a pair of nodes, and (ii) minimum number of regions whose removal disconnect a pair of nodes, are both NP-complete. We provide heuristic solution to these two problems and evaluate their efficacy by comparing the results with optimal solutions.
Starting Page	1
Ending Page	7
File Size	6033671
Page Count	7
File Format	PDF
ISBN	9781424451746
DOI	10.1109/HPSR.2009.5307417
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-06-22
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Fault tolerance Weapons Computer science Design engineering Wireless sensor networks US Government Vehicles
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A new metric for fault-tolerance in sensor networks

Fault-Tolerant Algorithms for Connectivity Restoration in Wireless Sensor Networks

A new fault-tolerant method for wireless sensor network design

Coverage-connectivity based fault tolerance procedure in wireless sensor networks

Distributed weighting fault-tolerant algorithm for event region detection in wireless sensor networks

A Fault Tolerant Protocol for Wireless Sensor Networks

A Trust-Based Framework for Fault-Tolerant Data Aggregation in Wireless Multimedia Sensor Networks

Research on Fault-Tolerant Target Detection algorithm in wireless Sensor Networks

Fault-Tolerance in Sensor Networks: A New Evaluation Metric

Region-based connectivity - a new paradigm for design of fault-tolerant networks

Similar Documents

A new metric for fault-tolerance in sensor networks

Fault-Tolerant Algorithms for Connectivity Restoration in Wireless Sensor Networks

A new fault-tolerant method for wireless sensor network design

Coverage-connectivity based fault tolerance procedure in wireless sensor networks

Distributed weighting fault-tolerant algorithm for event region detection in wireless sensor networks

A Fault Tolerant Protocol for Wireless Sensor Networks

A Trust-Based Framework for Fault-Tolerant Data Aggregation in Wireless Multimedia Sensor Networks

Research on Fault-Tolerant Target Detection algorithm in wireless Sensor Networks

Fault-Tolerance in Sensor Networks: A New Evaluation Metric

Region-based connectivity - a new paradigm for design of fault-tolerant networks