Network Tomography Based on Additive Metrics

DOI10.1109/TIT.2011.2168901MaRDI QIDQ5272202zbMATH OpenOpenAlexFDO

Authors Jian Ni, Sekhar Tatikonda

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0809.0158

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Communication networks in operations research (90B18)

Abstract: Inference of the network structure (e.g., routing topology) and dynamics (e.g., link performance) is an essential component in many network design and management tasks. In this paper we propose a new, general framework for analyzing and designing routing topology and link performance inference algorithms using ideas and tools from phylogenetic inference in evolutionary biology. The framework is applicable to a variety of measurement techniques. Based on the framework we introduce and develop several polynomial-time distance-based inference algorithms with provable performance. We provide sufficient conditions for the correctness of the algorithms. We show that the algorithms are consistent (return correct topology and link performance with an increasing sample size) and robust (can tolerate a certain level of measurement errors). In addition, we establish certain optimality properties of the algorithms (i.e., they achieve the optimal $l_{i}nfty$-radius) and demonstrate their effectiveness via model simulation.

Cited in

(4)

• Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem
• An empirical approach to demographic inference with genomic data
• Network delay inference from additive metrics
• Topology reconstruction using time series data in telecommunication networks

This page was built for publication: Network Tomography Based on Additive Metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5272202)