Statistical estimation of delays in a multicast tree using accelerated EM. (English) Zbl 1203.62111

Summary: Tomography is one of the most promising techniques today to provide spatially localized information about internal network performance in a robust and scalable way. The key idea is to measure performance at the edge of the network, and to correlate these measurements to infer the internal network performance. This paper focuses on a specific delay tomographic problem on a multicast diffusion tree, where end-to-end delays are observed at every leaf of the tree, and mean sojourn times are estimated for every node in the tree. The estimation is performed using the Maximum Likelihood Estimator (MLE) and the Expectation-Maximization (EM) algorithm.
Using queuing theory results, we carefully justify the model we use in the case of rare probing. We then give an explicit EM implementation in the case of i.i.d. exponential delays for a general tree. As we work with non-discretized delays and a full MLE, EM is known to be slow. We hence present a very simple but, in our case, very effective speed-up technique using Principal Component Analysis (PCA). MLE estimations are provided for a few different trees to evaluate our technique.


62H25 Factor analysis and principal components; correspondence analysis
60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
62F10 Point estimation
94A99 Communication, information
90B22 Queues and service in operations research
65C60 Computational problems in statistics (MSC2010)
Full Text: DOI


[1] Baccelli, F., Kauffmann, B., Veitch, D.: Inverse problems in queueing theory and internet probing. Queueing Syst. 63(1–4), 59–107 (2009) · Zbl 1209.90104 · doi:10.1007/s11134-009-9150-9
[2] Chen, A., Cao, J., Bu, T.: Network tomography: identifiability and Fourier domain estimation. In: IEEE INFOCOM, pp. 1875–1883 (2007)
[3] Chrétien, S., Hero, A.O.: Kullback proximal algorithms for maximum likelihood estimation. Inria report 3756 (2009) · Zbl 1021.68101
[4] Coates, M., Nowak, R.: Network tomography for internal delay estimation. In: Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Salt Lake City, Utah (2001)
[5] Cramér, H.: Mathematical Methods of Statistics. Princeton University Press, Princeton (1946) · Zbl 0063.01014
[6] Dalibard, S., Laumond, J.P.: Control of probabilistic diffusion in motion planning. In: 8th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2008) (2008)
[7] Duffield, N., Presti, F.L.: Multicast inference of packet delay variance at interior network links. In: IEEE INFOCOM, Tel Aviv, Israel, pp. 1351–1360 (2000)
[8] Huang, H.S., Yang, B.H., Hsu, C.N.: Triple jump acceleration for the EM algorithm. In: IEEE International Conference on Data Mining (ICDM’05) (2005)
[9] Jamshidian, M., Jennrich, R.I.: Conjugate gradient acceleration of the EM algorithm. J. Am. Stat. Assoc. (1993) · Zbl 0775.65025
[10] Kauffmann, B., Baccelli, F., Veitch, D.: Towards multihop available bandwidth estimation–inverse problems in queueing networks. In: Proc. ACM Sigmetrics/Performance’09, Seattle, WA, USA (2009) · Zbl 1209.90104
[11] Kelly, F.: Reversibility and Stochastic Networks. Wiley, New York (1979) · Zbl 0422.60001
[12] Lawrence, E., Michailidis, G., Nair, V.N.: Network delay tomography using flexicast experiments. J. R. Stat. Soc., Ser. B 68, 785–813 (2006) · Zbl 1110.62163 · doi:10.1111/j.1467-9868.2006.00567.x
[13] Lawrence, E., Michailidis, G., Nair, V.N.: Statistical inverse problems in active network tomography. In: Complex Datasets and Inverse Problems: Tomography, Networks and Beyond. IMS Lecture Notes-Monograph Series, vol. 54, pp. 24–44. IMS, Beachwood (2007). doi: 10.1214/074921707000000049
[14] Liang, G., Yu, B.: Maximum pseudo likelihood estimation in network tomography. IEEE Trans. Signal Process. 51(8), 2043–2053 (2003) (Special Issue on Data Networks) · doi:10.1109/TSP.2003.814464
[15] McLachlan, G.J., Krishnan, T.: The EM Algorithm and Extensions, 2nd edn. Wiley Series in Probability and Statistics. Wiley, New York (2008)
[16] Presti, F.L., Duffield, N.G., Horowitz, J., Towsley, D.: Multicast-based inference of network-internal delay distributions. IEEE/ACM Trans. Netw. 10(6), 761–775 (2002) · doi:10.1109/TNET.2002.805026
[17] Salakhutdinov, R., Roweis, S.: Adaptive overrelaxed bound optimization methods. In: International Conference on Machine Learning (ICML-2003) (2003)
[18] Shih, M.F., Hero, A.O.: Unicast-based inference of network link delay distributions with finite mixture models. IEEE Trans. Signal Process. 51(8), 2219–2228 (2003) (Special Issue on Data Networks) · doi:10.1109/TSP.2003.814468
[19] Tsang, Y., Coates, M., Nowak, R.: Network delay tomography. IEEE Trans. Signal Process. 51(8), 2125–2136 (2003) (Special Issue on Data Networks) · doi:10.1109/TSP.2003.814520
[20] Wu, C.J.: On the convergence properties of the EM algorithm. Ann. Stat. 11(1), 95–103 (1983) · Zbl 0517.62035 · doi:10.1214/aos/1176346060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.