Institute of Electrical and Electronics Engineers
Continuously monitoring link performance is important to network diagnosis. In this paper, the authors address the problem of minimizing the probing cost and achieving identifiability in probe based network link monitoring. Given a set of links to monitor, their objective is to select the minimum number of probing paths that can uniquely determine all identifiable links and cover all unidentifiable links. They 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 they extend the bipartite model to reflect the relationship between a set of probing paths and an identifiable link. Since their optimization problem is NP-hard, they propose a heuristic based algorithm to greedily select probing paths.