Fundamental limits of failure identifiability by boolean network tomography

N. Bartolini; T. He; H. Khamfroush

doi:10.1109/INFOCOM.2017.8057091

Fundamental limits of failure identifiability by boolean network tomography

N. Bartolini, T. He, H. Khamfroush

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

22 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 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.

Original language	English
Title of host publication	INFOCOM 2017 - IEEE Conference on Computer Communications
ISBN (Electronic)	9781509053360
DOIs	https://doi.org/10.1109/INFOCOM.2017.8057091
State	Published - Oct 2 2017
Event	2017 IEEE Conference on Computer Communications, INFOCOM 2017 - Atlanta, United States Duration: May 1 2017 → May 4 2017

Publication series

Name	Proceedings - IEEE INFOCOM
ISSN (Print)	0743-166X

Conference

Conference	2017 IEEE Conference on Computer Communications, INFOCOM 2017
Country/Territory	United States
City	Atlanta
Period	5/1/17 → 5/4/17

Bibliographical note

Publisher Copyright:
© 2017 IEEE.

Funding

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.

Funders	Funder number
Defense Threat Reduction Agency	HDTRA1-10-1-0085
North Atlantic Treaty Organization
Saudi Pharmaceutical Society	G4936 SONiCS

ASJC Scopus subject areas

General Computer Science
Electrical and Electronic Engineering

Access to Document

10.1109/INFOCOM.2017.8057091

Cite this

@inproceedings{0cf419960eeb419d9671043e80b67c05,

title = "Fundamental limits of failure identifiability by boolean network tomography",

abstract = "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.",

author = "N. Bartolini and T. He and H. Khamfroush",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 2017 IEEE Conference on Computer Communications, INFOCOM 2017 ; Conference date: 01-05-2017 Through 04-05-2017",

year = "2017",

month = oct,

day = "2",

doi = "10.1109/INFOCOM.2017.8057091",

language = "English",

series = "Proceedings - IEEE INFOCOM",

booktitle = "INFOCOM 2017 - IEEE Conference on Computer Communications",

}

TY - GEN

T1 - Fundamental limits of failure identifiability by boolean network tomography

AU - Bartolini, N.

AU - He, T.

AU - Khamfroush, H.

PY - 2017/10/2

Y1 - 2017/10/2

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85034048463&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85034048463&partnerID=8YFLogxK

U2 - 10.1109/INFOCOM.2017.8057091

DO - 10.1109/INFOCOM.2017.8057091

M3 - Conference contribution

AN - SCOPUS:85034048463

T3 - Proceedings - IEEE INFOCOM

BT - INFOCOM 2017 - IEEE Conference on Computer Communications

T2 - 2017 IEEE Conference on Computer Communications, INFOCOM 2017

Y2 - 1 May 2017 through 4 May 2017

ER -

Fundamental limits of failure identifiability by boolean network tomography

Abstract

Publication series

Conference

Bibliographical note

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this