Probabilistic probe selection algorithm for fault diagnosis in communication networks

摘要

Since faults unavoidably occur in communication networks, it is important to quickly and accurately localize the faults to ensure the stability, consistency and reliability of communication networks. Most existing works are focused on probe selection for fault diagnosis in the deterministic environment (DE). However, the information about communication networks in real applications is not deterministic due to disturbance, noise and so on, especially large scale networks. Therefore, it is urgent to solve the problem of localizing faults for communication networks in the non-deterministic environment (NDE). In this paper, we propose a probabilistic probe selection (PRPS) algorithm for network fault diagnosis in the NDE. Combining the probability language and node coverage, we use the probabilistic greedy probe selection approach to select the probes for fault detection with less probing cost to cover all network nodes in the NDE. When one or more faults are detected in the network, the probabilistic min search probe selection approach will be triggered to localize the faults. This approach uses min search method to select probes that pass through the minimum number of suspicious nodes and the maximum sum of coverage of suspicious nodes. In order to improve the ability to resist the uncertain factors, this approach updates the node state sets for multiple iterations according to the states of identified nodes. Extensive simulation experiments are conducted to compare our PRPS algorithm with the existing works and evaluate the performance on various network topologies with different parameters. The simulation results show that PRPS algorithm has satisfactory fault localization accuracy, low probing cost and strong adaptability to resist the uncertain factors in the NDE.