On Fundamental Bounds on Failure Identifiability by Boolean Network Tomography

Novella Bartolini, Ting He, Viviana Arrigoni, Annalisa Massini, Federico Trombetti, Hana Khamfroush

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

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.

Original languageEnglish
Article number9003530
Pages (from-to)588-601
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume28
Issue number2
DOIs
StatePublished - Apr 2020

Bibliographical note

Funding 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: bartolini@di.uniroma1.it; arrigoni@di.uniroma1.it; massini@di.uniroma1.it).

Publisher Copyright:
© 1993-2012 IEEE.

Keywords

  • Computer network management
  • fault detection
  • fault location
  • network tomography

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'On Fundamental Bounds on Failure Identifiability by Boolean Network Tomography'. Together they form a unique fingerprint.

Cite this