Network Tomography Based on Additive Metrics

Jian Ni, Sekhar Tatikonda

IEEE Transactions on Information Theory · 2011 · 37 citations · 32 references

DOIFull text

Open access

Concepts

Abstract

Network tomography studies the inference of network structure and dynamics based on indirect measurements when direct measurements are unavailable or difficult to collect. In this paper, we design and analyze routing tree topology and link performance inference algorithms for communication networks using tools from phylogenetic inference in evolutionary biology. We develop polynomial-time distance-based inference algorithms and derive sufficient conditions for the correctness of the algorithms. We show that the algorithms are consistent and robust. In particular, the algorithms achieve the optimal <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</i> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sub> -radius 1/2 for binary trees and 1/4 for general trees when a threshold neighbor selection criterion is used.

References

32