Robust Network Tomography: k-identifiability and Monitor Assignment

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. Unfortunately, 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.