Minimizing probing cost and achieving identifiability in probe-based network link monitoring

Qiang Zheng, Guohong Cao

Research output: Contribution to journalArticlepeer-review

42 Scopus citations

Abstract

Continuously monitoring link performance is important to network diagnosis. In this paper, we address the problem of minimizing the probing cost and achieving identifiability in probe-based network link monitoring. Given a set of links to monitor, our objective is to select the minimum number of probing paths that can uniquely determine all identifiable links and cover all unidentifiable links. We propose an algorithm based on a linear system model to find out all irreducible sets of probing paths that can uniquely determine an identifiable link, and we extend the bipartite model to reflect the relationship between a set of probing paths and an identifiable link. Since our optimization problem is NP-hard, we propose a heuristic-based algorithm to greedily select probing paths. Our method eliminates two types of redundant probing paths, i.e., those that can be replaced by others and those without any contribution to achieving identifiability. Simulations based on real network topologies show that our approach can achieve identifiability with very low probing cost. Compared with prior work, our method is more general and has better performance.

Original languageEnglish (US)
Article number6109244
Pages (from-to)510-523
Number of pages14
JournalIEEE Transactions on Computers
Volume62
Issue number3
DOIs
StatePublished - 2013

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Minimizing probing cost and achieving identifiability in probe-based network link monitoring'. Together they form a unique fingerprint.

Cite this