FAST PARAMETER ESTIMATION IN LOSS TOMOGRAPHY FOR NETWORKS OF GENERAL TOPOLOGY

• 成果类型: Article
• 署名作者: Deng, Ke; Li, Yang; Zhu, Weiping; Liu, Jun S.
• 署名单位: Tsinghua University; Harvard University; Australian Defense Force Academy; Australian Defense Force Academy; University of New South Wales Sydney
• 刊物名称: ANNALS OF APPLIED STATISTICS
• ISSN/ISSBN: 1932-6157
• DOI: 10.1214/15-AOAS883
• 发表日期: 2016
• 页码: 144-164
• 关键词: origin-destination matrices; delay tomography; loss inference; likelihood

摘要

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 reparametrization 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.