On Delay Tomography: Fast Algorithms and Spatially Dependent Models
- 30 July 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 60 (11) , 5685-5697
Abstract
As an active branch of network tomography, delay tomography has received considerable attentions in recent years. However, most methods in the literature assume that the delays of different links are independent of each other, and pursuit sub-optimal estimate instead of the maximum likelihood estimate (MLE) due to computational challenges. In this paper, we propose a novel method to implement the EM algorithm widely used in delay tomography analysis for multicast networks. The proposed method makes use of a “delay pattern database” to avoid all redundant computations in the E-step, and is much faster than the traditional implementation. With the help of this new implementation, finding MLE for large networks, which was considered impractical previously, becomes an easy task. Taking advantage of this computational breakthrough, we further consider models for potential spatial dependence of links, and propose a novel adaptive spatially dependent model (ASDM) for delay tomography. In ASDM, Markov dependence among nearby links is allowed, and spatially dependent links (SDLs) can be automatically recognized via model selection. The superiority of the new methods is confirmed by simulation studies.Keywords
This publication has 22 references indexed in Scilit:
- Multicast inference of temporal loss characteristicsPerformance Evaluation, 2007
- Moment estimation in delay tomography with spatial dependencePerformance Evaluation, 2007
- Explicit Loss Inference in Multicast TomographyIEEE Transactions on Information Theory, 2006
- A bottom-up inference of loss rateComputer Communications, 2005
- Multiple source, multiple destination network tomography2004
- A Fast Method to Estimate Loss RateLecture Notes in Computer Science, 2004
- Traffic matrix estimationACM SIGCOMM Computer Communication Review, 2002
- Multicast-based loss inference with missing dataIEEE Journal on Selected Areas in Communications, 2002
- Bayesian Inference on Network Traffic Using Link Count DataJournal of the American Statistical Association, 1998
- The estimation of origin-destination matrices by constrained generalised least squaresTransportation Research Part B: Methodological, 1991