Monitor placement for maximal identifiability in network tomography

Liang Ma, Ting He, Kin K. Leung, Ananthram Swami, Don Towsley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

41 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationIEEE INFOCOM 2014 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages9
ISBN (Print)9781479933600
StatePublished - 2014
Event33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014 - Toronto, ON, Canada
Duration: Apr 27 2014May 2 2014

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014
CityToronto, ON

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Monitor placement for maximal identifiability in network tomography'. Together they form a unique fingerprint.

Cite this