Parsimonious tomography: Optimizing cost-identifiability trade-off for probing-based network monitoring

Diman Zad Tootaghaj, Ting He, Thomas La Porta

Research output: Contribution to journalConference articlepeer-review

7 Scopus citations

Abstract

Network tomography using end-to-end probes provides a powerful tool for monitoring the performance of internal network elements. However, active probing can generate tremendous traffic, which degrades the overall network performance. Meanwhile, not all the probing paths contain useful information for identifying the link metrics of interest. This observation motivates us to study the optimal selection of monitoring paths to balance identifiability and probing cost. Assuming additive link metrics (e.g., delays), we consider four closely-related optimization problems: 1) Max-IL-Cost that maximizes the number of identifiable links under a probing budget, 2) Max-Rank-Cost that maximizes the rank of selected paths under a probing budget, 3) Min-Cost-IL that minimizes the probing cost while preserving identifiability, and 4) Min-Cost-Rank that minimizes the probing cost while preserving rank. While (1) and (3) are hard to solve, (2) and (4) are easy to solve, and the solutions give a good approximation for (1) and (3). Specifically, we provide an optimal algorithm for (4) and a (1 1/e)-approximation algorithm for (2). We prove that the solution for (4) provides tight upper/lower bounds on the minimum cost of (3), and the solution for (2) provides upper/lower bounds on the maximum identifiability of (1). Our evaluations on real topologies show that solutions to the rank-based optimization (2, 4) have superior performance in terms of the objectives of the identifiability-based optimization (1, 3), and our solutions can reduce the total probing cost by an order of magnitude while achieving the same monitoring performance.

Original languageEnglish (US)
Pages (from-to)43-55
Number of pages13
JournalPerformance Evaluation Review
Volume45
Issue number3
DOIs
StatePublished - Mar 20 2018
Event35th IFIP International Symposium on Computer Performance, Modeling, Measurements and Evaluation, IFIP WG 7.3 Performance 2017 - New York, United States
Duration: Nov 13 2017Nov 17 2017

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Parsimonious tomography: Optimizing cost-identifiability trade-off for probing-based network monitoring'. Together they form a unique fingerprint.

Cite this