DocumentCode :
2404327
Title :
Design and Analysis of Networks with Large Components in Presence of Region-Based Faults
Author :
Banerjee, Sujogya ; Shirazipourazad, Shahrzad ; Sen, Arunabha
Author_Institution :
Sch. of Comput., Inf. & Decision Syst. Eng., Arizona State Univ., Tempe, AZ, USA
fYear :
2011
fDate :
5-9 June 2011
Firstpage :
1
Lastpage :
6
Abstract :
Connectivity k(G) of a network G is traditionally considered to be the primary metric for evaluation of its fault tolerance capability. However, connectivity as a metric has several limitations - e.g., it has no mechanism to distinguish between localized and random faults. Also it does not provide any information about the network state, if number of failures exceed k(G). The network state information that might be of interest in such a scenario is the size of the largest connected component. In this paper, we address both these limitations and introduce a new metric called region-based largest component size (RBLCS), that provides the largest size of the component in which the network decomposes once all the nodes of a region fail. We study the computational complexity of finding RBLCS for a given network. In addition, we study the problem of least cost design of a network with a target value of RBLCS. We prove that the optimal design problem is NP-complete and present a heuristic to solve the problem. We evaluate our heuristic by comparing its solutions with the optimal solutions. Experimental results demonstrate that our heuristic produces near optimal solution in a fraction of time needed to find the optimal.
Keywords :
computational complexity; fault tolerance; optimisation; telecommunication network reliability; NP-complete problem; RBLCS metric; computational complexity; fault tolerance capability; network connectivity; network design; network state information; region-based faults; region-based largest component metric; Algorithm design and analysis; Complexity theory; Layout; Measurement; Peer to peer computing; Polynomials; Wireless networks;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Communications (ICC), 2011 IEEE International Conference on
Conference_Location :
Kyoto
ISSN :
1550-3607
Print_ISBN :
978-1-61284-232-5
Electronic_ISBN :
1550-3607
Type :
conf
DOI :
10.1109/icc.2011.5962427
Filename :
5962427
Link To Document :
بازگشت