On Fundamental Bounds on Failure Identifiability by Boolean Network Tomography

Boolean network tomography is a powerful tool to infer the state (working/failed) of individual nodes from path-level measurements obtained by edge-nodes. We consider the problem of optimizing the capability of identifying network failures through the design of monitoring schemes. Finding an optimal solution is NP-hard and a large body of work has been devoted to heuristic approaches providing lower bounds. Unlike previous works, we provide upper bounds on the maximum number of identifiable nodes, given the number of monitoring paths and different constraints on the network topology, the routing scheme, and the maximum path length. These upper bounds represent a fundamental limit on identifiability of failures via Boolean network tomography. Our analysis provides insights on how to design topologies and related monitoring schemes to achieve the maximum identifiability under various network settings. Through analysis and experiments we demonstrate the tightness of the bounds and efficacy of the design insights for engineered as well as real networks.

I. Introduction and Motivation

The capability to assess the states of network nodes in the presence of failures is fundamental for many functions in network management, including performance analysis, route selection, and network recovery. In modern networks, the traditional approach of relying on built-in mechanisms to detect node failures is no longer sufficient, as bugs and configuration errors in various customer software and network functions often induce “silent failures” that are only detectable from end-to-end connection states [1]. Boolean network tomography (BNT) [2] is a powerful tool to infer the states of individual nodes of a network from binary measurements taken along selected paths. We consider the problem of Boolean network tomography in the framework of graph-constrained group testing [3]. Classic group testing [4], [5] studies the problem of identifying defective items in a large set by means of binary measurements taken on subsets (). Close to the problem of group testing, Boolean network tomography aims at identifying defective network items, i.e. nodes or links, in a large set including all the network components, by performing binary measurements over subsets , i.e., monitoring paths. As in graph-based group testing, the composition of the testing sets conforms to the structure of the network.