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

Burlats, Alice;Schaus, Pierre;Pelsser, Cristel
(2024) 21st International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research — Location: Uppsala, Sweden (28.May.2024)

Files

cpaior2024_monitor_nodes.pdf
  • Open Access
  • Adobe PDF
  • 509.62 KB
Download

Details

Authors
Abstract
In computer networks, swift recovery from failures requires prompt detection and diagnosis. Protocols such as Bidirectional For- warding 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 be- tween the number of monitor nodes and the monitoring quality. Here, we examine two monitoring challenges from the Boolean network to- mography 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-hard problems. We present integer linear programming (ILP), constraint programming (CP) and MaxSAT formulations for these problems and compare their performance. Using 625 real 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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Burlats, A., Schaus, P., & Pelsser, C. (2024). An Exploration of Exact Methods for Effective Network Failure Detection and Diagnosis. An Exploration of Exact Methods for Effective Network Failure Detection and Diagnosis, p. 153-169. https://doi.org/10.1007/978-3-031-60597-0_11