Reasoning under Uncertainty for Overlay Fault Diagnosis

The performance and reliability of overlay services rely on the underlying overlay network's ability to effectively diagnose and recover from faults such as link failures and overlay node outages. However, overlay networks bring to fault diagnosis new challenges such as large-scale deployment, inaccessible underlay network information, dynamic symptom-fault causality relationship, and multi-layer complexity. In this paper, we develop an evidential overlay fault diagnosis framework called DigOver to tackle these challenges. Firstly, DigOver identifies a set of potential faulty components based on shared end-user observed negative symptoms. Then, each potential faulty component is evaluated to quantify its fault likelihood and the corresponding evaluation uncertainty. Finally, DigOver dynamically constructs a plausible fault graph to locate the root causes of end-user observed negative symptoms. Both simulation and Internet experiments demonstrate that DigOver can effectively and accurately diagnose overlay faults based on end-user observed negative symptoms.