Boolean network tomography is a powerful tool to infer the state (working/failed) of individual nodes from path-level measurements obtained by egde-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. The proposed upper bounds represent a fundamental limit on the identifiability of failures via Boolean network tomography. This 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.
|Title of host publication||INFOCOM 2017 - IEEE Conference on Computer Communications|
|State||Published - Oct 2 2017|
|Event||2017 IEEE Conference on Computer Communications, INFOCOM 2017 - Atlanta, United States|
Duration: May 1 2017 → May 4 2017
|Name||Proceedings - IEEE INFOCOM|
|Conference||2017 IEEE Conference on Computer Communications, INFOCOM 2017|
|Period||5/1/17 → 5/4/17|
Bibliographical noteFunding Information:
This work was supported by the Defense Threat Reduction Agency under the grant HDTRA1-10-1-0085, and by NATO under the SPS grant G4936 SONiCS.
© 2017 IEEE.
ASJC Scopus subject areas
- Computer Science (all)
- Electrical and Electronic Engineering