@inproceedings{298c1f3b3f134664a472133d8654ec4d,
title = "Monitor placement for maximal identifiability in network tomography",
abstract = "We investigate the problem of placing a given number of monitors in a communication network to identify the maximum number of link metrics from end-to-end measurements between monitors, assuming that link metrics are additive, and measurement paths cannot contain cycles. Motivated by our previous result that complete identification of all link metrics can require a large number of monitors, we focus on partial identification using a limited number of monitors. The basis to our solution is an efficient algorithm for determining all identifiable links for a given monitor placement. Based on this algorithm, we develop a polynomial-time greedy algorithm to incrementally place monitors such that each newly placed monitor maximizes the number of additional identifiable links. We prove that the proposed algorithm is optimal for 2-vertex-connected networks, and demonstrate that it is near-optimal for several real ISP topologies that are not 2-vertex-connected. Our solution provides a quantifiable tradeoff between level of identifiability and available monitor resources.",
author = "Liang Ma and Ting He and Leung, {Kin K.} and Ananthram Swami and Don Towsley",
year = "2014",
doi = "10.1109/INFOCOM.2014.6848079",
language = "English (US)",
isbn = "9781479933600",
series = "Proceedings - IEEE INFOCOM",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1447--1455",
booktitle = "IEEE INFOCOM 2014 - IEEE Conference on Computer Communications",
address = "United States",
note = "33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014 ; Conference date: 27-04-2014 Through 02-05-2014",
}