DocumentCode :
679031
Title :
Efficient probing method for active diagnosis in large scale network
Author :
Lu Guan ; Ying Wang ; Wenjing Li ; Congxian Yan
Author_Institution :
State Key Lab. of Networking & Switching Technol., Beijing Univ. of Posts & Telecommun., Beijing, China
fYear :
2013
fDate :
14-18 Oct. 2013
Firstpage :
198
Lastpage :
202
Abstract :
Adaptive active diagnosis method is widely adopted for fault diagnosis in networks. In active diagnosis, appropriate probes are selected sequentially and fault diagnosis is made by inference from results of selected probes. It is very important to select active probes with low cost and less impact on network performance. However, the selection of the most informative set of probes with limited cost is an NP-hard problem. The computational complexities of existing probe selection algorithms are still too high for large scale networks. In this paper, a lemma about mutual information provided by probes is proved based on the property of conditional entropy. Then an approximate method derived from this lemma is introduced to compute mutual information of probe. With this approximate method an efficient probe selection algorithm for active diagnosis is proposed. At last, the efficiency and effectiveness of the proposed algorithm is verified through simulation.
Keywords :
computational complexity; computer network reliability; entropy; fault diagnosis; NP-hard problem; active probes; adaptive active diagnosis method; computational complexity; computer network; conditional entropy property; fault diagnosis; large scale network; mutual information; probe selection algorith; probing method; Algorithm design and analysis; Approximation algorithms; Approximation methods; Bayes methods; Fault diagnosis; Probes; Uncertainty; Active probing; Bayesian network; information theory;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Network and Service Management (CNSM), 2013 9th International Conference on
Conference_Location :
Zurich
Type :
conf
DOI :
10.1109/CNSM.2013.6727837
Filename :
6727837
Link To Document :
بازگشت