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

Alice Burlats, Cristel Pelsser, and Pierre Schaus. 2024. An Exploration of Exact Methods for Effective Network Failure Detection and Diagnosis. In Proceedings of the 38th Annual Conference of the Belgian Operational Research Society ORBEL. Antwerp, Belgium.

@inproceedings{Burlats2024b,
	title        = {An Exploration of Exact Methods for Effective Network Failure Detection and Diagnosis},
	author       = {Alice Burlats and Cristel Pelsser and Pierre Schaus},
	year         = 2024,
	month        = feb,
	booktitle    = {Proceedings of the 38th Annual Conference of the Belgian Operational Research Society {ORBEL}},
	address      = {Antwerp, Belgium},
	url          = {http://hdl.handle.net/2078.1/292251},
	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.},
	groups       = {National Conferences},
	keywords     = {Boolean tomography, Network supervision}
}