Topological Constraints on Identifying Additive Link Metrics via End-to-end Paths Measurements
Abstract
We investigate the problem of identifying individual link metrics in a communications network by measuring accumulated end-to-end metrics over selected paths under the assumption that link metrics are additive (e.g., delay) and constant in the measurement duration. Based on linear algebra, we know that all link metrics can be uniquely identified when the number of linearly independent paths is equal to the number of links in the network. However, there lacks a fundamental theory to relate the number of linearly independent paths (and thus link identifiability) to externally observable parameters such as network topology, number of monitoring nodes, and routing restrictions. Therefore, the aim of this paper is to study constraints on the network topology for identifying additive link metrics, conditioned on the number of monitoring nodes being fixed and the cycles being prohibited in constructing measurement paths. Our first main result is that it is impossible to identify all the link metrics in any network with a nontrivial topology (having more than one link) using only two monitoring nodes; nevertheless, the interior links not incident with any monitoring node might be identifiable. Our second main result is a set of necessary and sufficient conditions for identifying all the interior links using two monitoring nodes. Furthermore, we show that these conditions have a natural extension to identifying the entire network using three or more monitoring nodes. To the best of our knowledge, this is the first work providing fundamental constraints on network topology for identifying additive link metrics using end-to-end measurements on cycle-free paths.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 20, 2012
- Accession Number
- ADA565917
Entities
People
- Ananthram Swami
- Don Towsley
- Kin K. Leung
- Liang Ma
- Ting He
Organizations
- IBM Thomas J. Watson Research Center