Network delay inference from additive metrics

DOI10.1002/RSA.20305MaRDI QIDQ3055890zbMATH OpenOpenAlexFDO

Authors Shankar Bhamidi, Ram Rajagopal, Sebastien Roch

Publication date 10 November 2010

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

optimizationadvection-diffusionfast solversmultiphysics

Mathematics Subject Classification ID

Numerical analysis or methods applied to Markov chains (65C40) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10)

Abstract: We demonstrate the use of computational phylogenetic techniques to solve a central problem in inferential network monitoring. More precisely, we design a novel algorithm for multicast-based delay inference, i.e. the problem of reconstructing the topology and delay characteristics of a network from end-to-end delay measurements on network paths. Our inference algorithm is based on additive metric techniques widely used in phylogenetics. It runs in polynomial time and requires a sample of size only $poly(logn)$.

Recommendations

• Multicast topology inference from measured end-to-end loss
• Network Delay Tomography using Flexicast Experiments
• Network tomography: recent developments
• scientific article; zbMATH DE number 1900305
• scientific article; zbMATH DE number 1893559

Cites work

• scientific article; zbMATH DE number 5003309 (Why is no real title available?)
• scientific article; zbMATH DE number 2079368 (Why is no real title available?)
• scientific article; zbMATH DE number 3448387 (Why is no real title available?)
• A few logs suffice to build (almost) all trees. II
• A signal-to-noise analysis of phylogeny estimation by neighbor-joining: Insufficiency of polynomial length sequences
• Full reconstruction of Markov models on evolutionary trees: identifiability and consistency.
• Multicast-based inference of network-internal loss characteristics
• Network Tomography Based on Additive Metrics
• Network delay inference from additive metrics
• Network tomography: recent developments
• Phylogenies without branch bounds: contracting the short, pruning the deep
• The performance of neighbor-joining methods of phylogenetic reconstruction
• Time-Varying Network Tomography: Router Link Data

Cited in

(13)

• Multicast topology inference from measured end-to-end loss
• The tightness of the Kesten-Stigum reconstruction bound of symmetric model with multiple mutations
• Information reconstruction on an infinite tree for a \(4\times 4\)-state asymmetric model with community effects
• Large degree asymptotics and the reconstruction threshold of the asymmetric binary channels
• Network topology inference based on round trip time
• scientific article; zbMATH DE number 2247706 (Why is no real title available?)
• Phase transition of the reconstructability of a general model with different in-community and out-community mutations on an infinite tree
• Gibbs measures and phase transitions on sparse random graphs
• Reconstructibility of a general DNA evolution model
• Network delay inference from additive metrics
• Finding spatial and temporal features of delay propagation via multi-layer networks
• Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem
• A calculus for network delay. II. Network analysis

This page was built for publication: Network delay inference from additive metrics

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