Adaptive algorithms for diagnosing large-scale failures in computer networks
Authors:
- 1 June 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15300889,p. 1-12
Abstract
In this paper, we propose an algorithm to efficiently diagnose large-scale clustered failures. The algorithm, Cluster-MAX-COVERAGE (CMC), is based on greedy approach. We address the challenge of determining faults with incomplete symptoms. CMC makes novel use of both positive and negative symptoms to output a hypothesis list with a low number of false negatives and false positives quickly. CMC requires reports from about half as many nodes as other existing algorithms to determine failures with 100% accuracy. Moreover, CMC accomplishes this gain significantly faster (sometimes by two orders of magnitude) than an algorithm that matches its accuracy. Furthermore, we propose an adaptive algorithm called Adaptive-MAX-COVERAGE (AMC) that performs efficiently during both kinds of failures, i.e., independent and clustered. During a series of failues that include both independent and clustered, AMC results in a reduced number of false negatives and false positives.Keywords
This publication has 9 references indexed in Scilit:
- netCSI: A Generic Fault Diagnosis Algorithm for Large-Scale Failures in Computer Networks2011
- Network survivability in large-scale regional failure scenarios2009
- Towards highly reliable enterprise network services via inference of multi-level dependencies2007
- Detection and Localization of Network Black Holes2007
- Improving BGP Convergence Delay for Large-Scale Failures2006
- Shrink2005
- A survey of fault localization techniques in computer networksScience of Computer Programming, 2004
- Probabilistic fault diagnosis in communication systems through incremental hypothesis updatingComputer Networks, 2004
- Density Estimation for Statistics and Data Analysis1986