Link identifiability in communication networks with two monitors

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

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

9 Scopus citations


We investigate the problem of identifying individual link performance metrics in a communication network by measuring end-to-end metrics of selected paths between monitors, under the assumption that link metrics are additive and constant during the measurement, and measurement paths cannot contain cycles. In a previous work, we developed an algorithm that places the minimum number of monitors to identify all link metrics. However, even the minimum number can be large in some practical networks (e.g., 60% of all the nodes), suggesting high monitor deployment cost. In this paper, we study the dual problem where given a fixed number of monitors, we want to place them to maximize the number of identifiable link metrics, with concrete results for the case of two monitors. The significance of the two-monitor case is that all the tomographic computation can be performed at the destination monitor without shipping measurements to a central node, thus enabling endhost-based network monitoring. We develop an efficient algorithm to determine all identifiable links in an arbitrary network with a given placement of two monitors, based on which we propose an optimal two-monitor placement algorithm to maximize the number of identifiable links. Our evaluation on real ISP topologies shows that although a large number of monitors is needed to identify all link metrics, we can usually identify a substantial portion (up to 97%) of the links using a single pair of optimally placed monitors.

Original languageEnglish (US)
Title of host publication2013 IEEE Global Communications Conference, GLOBECOM 2013
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Print)9781479913534
StatePublished - Jan 1 2013
Event2013 IEEE Global Communications Conference, GLOBECOM 2013 - Atlanta, GA, United States
Duration: Dec 9 2013Dec 13 2013

Publication series

NameGLOBECOM - IEEE Global Telecommunications Conference


Other2013 IEEE Global Communications Conference, GLOBECOM 2013
Country/TerritoryUnited States
CityAtlanta, GA

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering


Dive into the research topics of 'Link identifiability in communication networks with two monitors'. Together they form a unique fingerprint.

Cite this