A Quasi-Optimal Probabilistic Fault Localization Algorithm in Communication Networks

The problem of fault localization, which needs to find the optimal hypothesis from all possible fault hypotheses, is theoretically proven to be NP-hard. In this paper, we propose a quasi-optimal probabilistic fault localization algorithm based on the observation that there are few concurrent faults in real communication systems. A heuristic algorithm is first used to estimate the real number of concurrent faults. According to this estimated number, we then perform exhaustive search over a small specific candidate fault set, in order to obtain the accurate explanation of the observed symptoms. Simulation shows that the algorithm is quasi-optimal, effective and efficient.