An Exploration of Exact Methods for Effective Network Failure Detection and Diagnosis

Abstract: In computer networks, rapid recovery from failures requires fast detection and diagnosis. Using protocols such as Bidirectional Forwarding Detection (BFD), it is possible to probe the state of a route. These protocols are executed on specific nodes designated as network monitors. Monitors are responsible for continuously checking the viability of communication paths. It is crucial to carefully select the monitors, as monitoring incurs costs, requiring a balance between the number of monitors and the quality of the supervision. In this context, we explore two supervision challenges from the field of Boolean network tomography: coverage, which involves detecting failures, and 1-identifiability, which also requires identifying the failing link or node. We examine three exact approaches to solve this problem: an Integer Linear Programming (ILP) model, a Constraint Programming (CP) model, and a Maximum Satisfiability (MaxSAT) model. Using 625 real network topologies, we demonstrate that employing these exact methods can reduce the number of monitors needed compared to the state-of-the-art greedy algorithm.