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.
|Number of pages||14|
|Journal||IEEE/ACM Transactions on Networking|
|State||Published - Apr 2020|
Bibliographical noteFunding Information:
Manuscript received March 25, 2019; revised September 3, 2019 and November 26, 2019; accepted December 27, 2019; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor P. P. C. Lee. Date of publication February 19, 2020; date of current version April 16, 2020. This work was supported in part by the Defense Threat Reduction Agency under Grant HDTRA1-10-1-0085 and in part by NATO under SPS Grant G4936 SONiCS. (Corresponding author: Novella Bartolini.) Novella Bartolini, Viviana Arrigoni, Annalisa Massini, and Federico Trombetti are with the Department of Computer Science, Sapienza University of Rome, 00185 Rome, Italy (e-mail: email@example.com; firstname.lastname@example.org; email@example.com).
© 1993-2012 IEEE.
- Computer network management
- fault detection
- fault location
- network tomography
ASJC Scopus subject areas
- Computer Science Applications
- Computer Networks and Communications
- Electrical and Electronic Engineering