Topology Agnostic Bounds on Minimum Requirements for Network Failure Identification

In Boolean Network Tomography (BNT), node identifiability is a crucial property that reflects the possibility of unambiguously classifying the state of the nodes of a network as 'working' or 'failed' through end-to-end measurement paths. Designing a monitoring scheme satisfying network identifiability is an NP problem. In this article, we provide theoretical bounds on the minimum number of necessary measurement paths to guarantee identifiability of a given number of nodes. The bounds take into consideration two different classes of routing schemes (arbitrary and consistent routing) as well as quality of service (QoS) requirements. We formally prove the tightness of such bounds for the arbitrary routing scheme, and provide an algorithmic approach to the design of network topologies and path deployment that meet the discussed limits. Due to the computational complexity of the optimal solution, We evaluate the tightness of our lower bounds by comparing their values with an upper bound, obtained by a state-of-the-art heuristic for node identifiability. For our experiments we run extensive simulations on both synthetic and real network topologies, for which we show that the two bounds are close to each other, despite the fact that the provided lower bounds are topology agnostic.