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.
Cristel Pelsser
Critical embedded systems, Computer networking, Researcher, Professor
The focus of my research is on network operations, routing, Internet measurements, protocols and security.