Network diagnosis by reasoning in uncertain nested evidence spaces

This paper describes a new diagnostic method and its application to communications network fault diagnosis. This new method uses belief propagation to accumulate evidence which it then uses for diagnosis. It has been successfully applied to the accurate, real-time diagnosis of break faults in large wide area data communications networks where the normal status messages provide very uncertain evidence of a fault and its location. It was tested on simulated WANs of up to 30000 monitored devices, including tests with either SNMP/PING or OSI monitoring, and also on a simulated WAN with an ATM/B-ISDN subnetwork. It achieved 99.96% accuracy in diagnosing 2499 out of 2500 break faults, making no extra false diagnoses, even though up to 127 devices were broken at once. Operational tests and trials were also carried out over which it achieved 99% accuracy. On both simulated and real networks it required approximately 1% of the CPU of a SUN SPARC 2 for every 15000 network devices monitored. It is now in operation in the network operations centre of a large, corporate WAN.<>