Robust network tomography: K-Identifiability and monitor assignment
Authors:
- 1 April 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-9
Abstract
Network tomography is an attractive approach for inferring internal network states at edge nodes. Recently, there is a growing interest in the basic understanding of the topological conditions that ensure identifiability in a general network. Un, existing works assume an ideal network model where all network elements are reliable. In this paper, we are aiming to propose topological conditions to ensure identifiability in the presence of any k link failures (k ≥ 0), using measurement paths and cycles. We propose a novel concept called k-identifiability. We propose sufficient and necessary topological conditions to ensure k-identifiability. Based on the established theoretical foundations, we propose two efficient polynomial-time algorithms for addressing two closely related questions. (1) Given a network with specified monitors, which links are k-identifiable? (2) Given a network and κ monitors, where should these monitors be placed such that the number of k-identifiable links is maximized? Simulation results on real ISP network topologies show the effectiveness of our algorithms.Keywords
This publication has 18 references indexed in Scilit:
- Explicit Path Control in Commodity Data Centers: Design and ApplicationsIEEE/ACM Transactions on Networking, 2015
- Node Failure Localization via Network Tomography2014
- Preferential Link Tomography: Monitor Assignment for Inferring Interesting Link Metrics2014
- Monitor placement for maximal identifiability in network tomography2014
- Efficient Identification of Additive Link Metrics via Network Tomography2013
- On Identifying Additive Link Metrics Using Linearly Independent Cycles and PathsIEEE/ACM Transactions on Networking, 2011
- SRLG Failure Localization in All-Optical Networks Using Monitoring Cycles and Paths2008
- Practical Beacon Placement for Link Monitoring Using Network TomographyIEEE Journal on Selected Areas in Communications, 2006
- A Simple 3-Edge-Connected Component AlgorithmTheory of Computing Systems, 2005
- Network Tomography: Estimating Source-Destination Traffic Intensities from Link DataJournal of the American Statistical Association, 1996