Fast parameter estimation in loss tomography for networks of general topology

DOI10.1214/15-AOAS883MaRDI QIDQ288566zbMATH OpenOpenAlexFDO

Authors Ke Deng, Jun S. Liu, Weiping Zhu, Yang Li

Publication date 27 May 2016

Published in The Annals of Applied Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.07158, https://projecteuclid.org/euclid.aoas/1458909911

zbMATH Keywords

general topologylikelihood equationloss tomographynetwork tomographypattern-collapsed EM algorithm

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Applications of graph theory to circuits and networks (94C15) Network design and communication in computer systems (68M10) Applications of design theory to circuits and networks (94C30)

Abstract: As a technique to investigate link-level loss rates of a computer network with low operational cost, loss tomography has received considerable attentions in recent years. A number of parameter estimation methods have been proposed for loss tomography of networks with a tree structure as well as a general topological structure. However, these methods suffer from either high computational cost or insufficient use of information in the data. In this paper, we provide both theoretical results and practical algorithms for parameter estimation in loss tomography. By introducing a group of novel statistics and alternative parameter systems, we find that the likelihood function of the observed data from loss tomography keeps exactly the same mathematical formulation for tree and general topologies, revealing that networks with different topologies share the same mathematical nature for loss tomography. More importantly, we discover that a re-parametrization of the likelihood function belongs to the standard exponential family, which is convex and has a unique mode under regularity conditions. Based on these theoretical results, novel algorithms to find the MLE are developed. Compared to existing methods in the literature, the proposed methods enjoy great computational advantages.

Recommendations

• Estimating Network Loss Rates Using Active Tomography
• Explicit Loss Inference in Multicast Tomography
• Network tomography: recent developments
• Network tomography: a review and recent developments
• Network Tomography: Estimating Source-Destination Traffic Intensities from Link Data

Cites work

• scientific article; zbMATH DE number 5454664 (Why is no real title available?)
• scientific article; zbMATH DE number 3567782 (Why is no real title available?)
• scientific article; zbMATH DE number 1220667 (Why is no real title available?)
• scientific article; zbMATH DE number 1900305 (Why is no real title available?)
• A Network Based Model for Traffic Sensor Location with Implications on O/D Matrix Estimates
• Bayesian Inference on Network Traffic Using Link Count Data
• Estimating Latent Processes on a Network From Indirect Measurements
• Estimating point-to-point and point-to-multipoint traffic matrices: an information-theoretic approach.
• Explicit Loss Inference in Multicast Tomography
• Multicast topology inference from measured end-to-end loss
• Multicast-based inference of network-internal loss characteristics
• Network Delay Tomography using Flexicast Experiments
• Network Tomography: Estimating Source-Destination Traffic Intensities from Link Data
• Network Tomography: Identifiability and Fourier Domain Estimation
• Network tomography: recent developments
• On Delay Tomography: Fast Algorithms and Spatially Dependent Models
• The computation of fixed points and applications

Cited in

(3)

• Estimating Network Loss Rates Using Active Tomography
• Bayesian experimental design for network loss tomography
• Explicit Loss Inference in Multicast Tomography

Describes a project that uses

Uses Software

• ns-2

This page was built for publication: Fast parameter estimation in loss tomography for networks of general topology

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