Accession Number : ADA565917


Title :   Topological Constraints on Identifying Additive Link Metrics via End-to-end Paths Measurements


Descriptive Note : Conference paper


Corporate Author : IBM THOMAS J WATSON RESEARCH CENTER HAWTHORNE NY


Personal Author(s) : Ma, Liang ; He, Ting ; Leung, Kin K ; Swami, Ananthram ; Towsley, Don


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a565917.pdf


Report Date : 20 Sep 2012


Pagination or Media Count : 10


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.


Descriptors :   *COMMUNICATIONS NETWORKS , *LINKAGES , *MEASUREMENT , *METRICS , *NETWORK TOPOLOGY , *NODES , *PATHS , ALGORITHMS , DELAY , GRAPHS , JOINT MILITARY ACTIVITIES , LINEAR ALGEBRAIC EQUATIONS , MONITORING , NETWORK ANALYSIS(MANAGEMENT) , ROUTING , SYMPOSIA


Subject Categories : Computer Systems
      Radiofrequency Wave Propagation
      Radio Communications


Distribution Statement : APPROVED FOR PUBLIC RELEASE