Topology Agnostic Bounds on Minimum Requirements for Network Failure Identification
Open Access
- 1 January 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 9, 6076-6086
Abstract
In Boolean Network Tomography (BNT), node identifiability is a crucial property that reflects the possibility of unambiguously classifying the state of the nodes of a network as 'working' or 'failed' through end-to-end measurement paths. Designing a monitoring scheme satisfying network identifiability is an NP problem. In this article, we provide theoretical bounds on the minimum number of necessary measurement paths to guarantee identifiability of a given number of nodes. The bounds take into consideration two different classes of routing schemes (arbitrary and consistent routing) as well as quality of service (QoS) requirements. We formally prove the tightness of such bounds for the arbitrary routing scheme, and provide an algorithmic approach to the design of network topologies and path deployment that meet the discussed limits. Due to the computational complexity of the optimal solution, We evaluate the tightness of our lower bounds by comparing their values with an upper bound, obtained by a state-of-the-art heuristic for node identifiability. For our experiments we run extensive simulations on both synthetic and real network topologies, for which we show that the two bounds are close to each other, despite the fact that the provided lower bounds are topology agnostic.Keywords
Funding Information
- North Atlantic Treaty Organization (NATO), under the Science for Peace and Security grant (SPS G4936)
This publication has 17 references indexed in Scilit:
- Fundamental limits of failure identifiability by boolean network tomography2017
- Network Capability in Localizing Node Failures via End-to-End Path MeasurementsIEEE/ACM Transactions on Networking, 2016
- Service Placement for Detecting and Localizing Failures Using End-to-End Observations2016
- On optimal monitor placement for localizing node failures via network tomographyPerformance Evaluation, 2015
- Adaptive boolean network tomography for link failure detection2015
- Node Failure Localization via Network Tomography2014
- Robust monitoring of link delays and faults in IP networks2004
- Simple network performance tomography2003
- The use of end-to-end multicast measurements for characterizing internal network behaviorIEEE Communications Magazine, 2000
- Critical Power for Asymptotic Connectivity in Wireless Networks1999