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

Auguste Burlats, Pierre Schaus, and Cristel Pelsser. 2024. An Exploration of Exact Methods for Effective Network Failure Detection and Diagnosis. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer Nature Switzerland, Cham, 153–169.

@inproceedings{Burlats2024,
	title        = {An Exploration of Exact Methods for Effective Network Failure Detection and Diagnosis},
	author       = {Burlats, Auguste and Schaus, Pierre and Pelsser, Cristel},
	year         = 2024,
	month        = may,
	booktitle    = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research},
	publisher    = {Springer Nature Switzerland},
	address      = {Cham},
	pages        = {153--169},
	isbn         = {978-3-031-60597-0},
	url          = {https://link.springer.com/chapter/10.1007/978-3-031-60597-0_11},
	editor       = {Dilkina, Bistra},
	abstract     = {In computer networks, swift recovery from failures requires prompt detection and diagnosis. Protocols such as Bidirectional Forwarding Detection (BFD) exists to probe the liveliness of a path and endpoint. These protocols are run on specific nodes that are designated as network monitors. Monitors are responsible for continuously verifying the viability of communication paths. It is important to carefully select monitors as monitoring incurs a cost, necessitating finding a balance between the number of monitor nodes and the monitoring quality. Here, we examine two monitoring challenges from the Boolean network tomography research field: coverage, which involves detecting failures, and 1-identifiability, which additionally requires identifying the failing link or node. We show that minimizing the number of monitors while meeting these requirements constitutes NP-complete problems. We present integer linear programming (ILP), constraint programming (CP) and Maximum Satisfiability (MaxSAT) formulations for these problems and compare their performance. Using 625 network topologies, we demonstrate that employing such exact methods can reduce the number of monitors needed compared to the existing state-of-the-art greedy algorithm.},
	groups       = {International Conferences}
}