Fast parameter estimation in loss tomography for networks of general topology. (English) Zbl 1362.94073

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

Ann. Appl. Stat. 10, No. 1, 144-164 (2016).

Summary: 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.

MSC:

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

Keywords:

network tomography; loss tomography; general topology; likelihood equation; pattern-collapsed EM algorithm

Software:

ns-2

References:

[1]	Airoldi, E. M. and Blocker, A. W. (2013). Estimating latent processes on a network from indirect measurements. J. Amer. Statist. Assoc. 108 149-164. · Zbl 06158332 · doi:10.1080/01621459.2012.756328
[2]	Arya, V., Duffield, N. G. and Veitch, D. (2007). Multicast inference of temporal loss characteristics. Perform. Eval. 64 1169-1180.
[3]	Arya, V., Duffield, N. G. and Veitch, D. (2008). Temporal delay tomography. In INFOCOM 2008. The 27 th Conference on Computer Communications . IEEE, New York.
[4]	Bell, M. G. H. (1991). The estimation of origin-destination matrices by constrained generalised least squares. Transportation Res. Part B 25 13-22. · doi:10.1016/0191-2615(91)90010-G
[5]	Bianco, L., Confessore, G. and Reverberi, P. (2001). A network based model for traffic sensor location with implications on O/D matrix estimates. Transp. Sci. 35 50-60. · Zbl 1069.90503 · doi:10.1287/trsc.35.1.50.10140
[6]	Bu, T., Duffield, N., Presti, F. L. and Towsley, D. (2002). Network tomography on general topologies. Proc. of ACM SIGMETRICS 30 21-30.
[7]	Cáceres, R., Duffield, N. G., Moon, S. B. and Towsley, D. (1999a). Inference of internal loss rates in the MBone. In Global Telecommunications Conference , 1999 3 1853-1858.
[8]	Cáceres, R., Duffield, N. G., Moon, S. B. and Towsley, D. (1999b). Inferring link-level performance from end-to-end multicast measurements. Global Internet, Rio de Janiero.
[9]	Cáceres, R., Duffield, N. G., Horowitz, J. and Towsley, D. F. (1999c). Multicast-based inference of network-internal loss characteristics. IEEE Trans. Inform. Theory 45 2462-2480. · Zbl 0961.94002 · doi:10.1109/18.796384
[10]	Cao, J., Wiel, S. V., Yu, B. and Zhu, Z. (2001). A scalable method for estimating network traffic matrices from link counts. Technical Report, Vol. 41, Bell Labs, Murray Hill, NJ.
[11]	Cao, J., Cleveland, W. S., Lin, D. and Sun, D. X. (2002). The effect of statistical multiplexing on the long-range dependence. Nonlinear Estimation and Classification 95 979-985.
[12]	Cascetta, E. and Nguyen, S. (1988). A unified framework for estimating or updating origin/destination matrices from traffic counts. Transportation Res. Part B 22 437-455. · doi:10.1016/0191-2615(88)90024-0
[13]	Castro, R., Coates, M., Liang, G., Nowak, R. and Yu, B. (2004). Network tomography: Recent developments. Statist. Sci. 19 499-517. · Zbl 1100.62628 · doi:10.1214/088342304000000422
[14]	Chen, A., Cao, J. and Bu, T. (2010). Network tomography: Identifiability and Fourier domain estimation. IEEE Trans. Signal Process. 58 6029-6039. · Zbl 1392.94136 · doi:10.1109/TSP.2010.2068294
[15]	Coates, M. and Nowak, R. (2000a). Network loss inference using unicast end-to-end measurement. Proc. ITC Conf. IP Traffic , Modeling and Management 28-1. Monterey, CA.
[16]	Coates, M. and Nowak, R. (2000b). Unicast network tomography using EM algorithms. In Proceedings of the IEEE International Conference on Acoustics , Speech , and Signal Processing 3 1469-1472. IEEE, New York.
[17]	de Dios Ortuzar, J. and Willumsen, L. G. (2011). Modelling Transport . Wiley, New York.
[18]	Dempster, A. P., Laird, N. M. and Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Statist. Soc. Ser. B 39 1-38. · Zbl 0364.62022
[19]	Deng, K., Li, Y., Zhu, W., Geng, Z. and Liu, J. S. (2012). On delay tomography: Fast algorithms and spatially dependent models. IEEE Trans. Signal Process. 60 5685-5697. · Zbl 1393.94208 · doi:10.1109/TSP.2012.2210712
[20]	Dinwoodie, I. H. and Vance, E. A. (2007). Moment estimation in delay tomography with spatial dependence. Perform. Eval. 64 613-628.
[21]	Duffield, N. G., Horowitz, J., Presti, F. L. and Towsley, D. (2001). Network delay tomography from end-to-end unicast measurements. In Evolutionary Trends of the Internet 576-595. Springer, Berlin. · Zbl 1010.68764
[22]	Duffield, N. G., Horowitz, J., Towsley, D., Wei, W. and Friedman, T. (2002a). Multicast-based loss inference with missing data. IEEE J. Sel. Areas Commun. 20 700-713.
[23]	Duffield, N. G., Horowitz, J., Lo Presti, F. and Towsley, D. (2002b). Multicast topology inference from measured end-to-end loss. IEEE Trans. Inform. Theory 48 26-45. · Zbl 1059.94050 · doi:10.1109/18.971737
[24]	Duffield, N. G., Horowitz, J., Lo Presti, F. and Towsley, D. (2006). Explicit loss inference in multicast tomography. IEEE Trans. Inform. Theory 52 3852-3855. · Zbl 1309.94197 · doi:10.1109/TIT.2006.878228
[25]	Fang, J., Vardi, Y. and Zhang, C.-H. (2007). An iterative tomogravity algorithm for the estimation of network traffic. In Complex Datasets and Inverse Problems . 54 12-23. IMS, Beachwood, OH. · doi:10.1214/074921707000000030
[26]	Harfoush, K., Bestavros, A. and Byers, J. (2000). Robust identification of shared losses using end-to-end unicast probes. In Proceedings 2000 International Conference on Network Protocols , IEEE 22-33.
[27]	Lawrence, E., Michailidis, G. and Nair, V. N. (2006). Network delay tomography using flexicast experiments. J. R. Stat. Soc. Ser. B Stat. Methodol. 68 785-813. · Zbl 1110.62163 · doi:10.1111/j.1467-9868.2006.00567.x
[28]	Lehmann, E. L. and Casella, G. (1998). Theory of Point Estimation , 2nd ed. Springer, New York. · Zbl 0916.62017
[29]	Liang, G., Taft, N. and Yu, B. (2006). A fast lightweight approach to origin-destination IP traffic estimation using partial measurements. IEEE Trans. Inform. Theory 52 2634-2648. · Zbl 1317.94165 · doi:10.1145/1148663.1148686
[30]	Liang, G. and Yu, B. (2003). Maximum pseudo likelihood estimation in network tomography. IEEE Trans. Signal Process. 51 2043-2053.
[31]	Lo, H. P., Zhang, N. and Lam, W. H. (1996). Estimation of an origin-destination matrix with random link choice proportions: A statistical approach. Transp. Res. , Part B : Methodol. 30 309-324.
[32]	McCanne, S., Floyd, S., Fall, K., Varadhan, K. et al. (1997). Network simulator ns-2.
[33]	Medina, A., Taft, N., Salamatian, K., Bhattacharyya, S. and Diot, C. (2002). Traffic matrix estimation: Existing techniques and new directions. ACM SIGCOMM Computer Communication Review 32 161-174.
[34]	Presti, F. L., Duffield, N. G., Horowitz, J. and Towsley, D. (2002). Multicast-based inference of network-internal delay distributions. IEEE/ACM Transactions on Networking 10 761-775.
[35]	Rabbat, M., Nowak, R. and Coates, M. (2004). Multiple source, multiple destination network tomography. In INFOCOM 2004. Twenty-Third AnnualJoint Conference of the IEEE Computer and Communications Societies 3 1628-1639.
[36]	Shih, M.-F. and Hero III, A. O. (2003). Unicast-based inference of network link delay distributions with finite mixture models. IEEE Trans. Signal Process. 51 2219-2228.
[37]	Tebaldi, C. and West, M. (1998). Bayesian inference on network traffic using link count data. J. Amer. Statist. Assoc. 93 557-576. · Zbl 1072.62650 · doi:10.2307/2670105
[38]	Todd, M. J. (2013). The Computation of Fixed Points and Applications 124 . Springer Science & Business Media. · Zbl 0332.54003
[39]	Tsang, Y., Coates, M. and Nowak, R. D. (2003). Network delay tomography. IEEE Trans. Signal Process. 51 2125-2136.
[40]	Vardi, Y. (1996). Network tomography: Estimating source-destination traffic intensities from link data. J. Amer. Statist. Assoc. 91 365-377. · Zbl 0871.62103 · doi:10.2307/2291416
[41]	Yang, H., Sasaki, T., Iida, Y. and Asakura, Y. (1992). Estimation of origin-destination matrices from link traffic counts on congested networks. Transp. Res. , Part B : Methodol. 26 417-434.
[42]	Zhang, Y., Roughan, M., Lund, C. and Donoho, D. (2003). An information-theoretic approach to traffic matrix estimation. In Proceedings of the 2003 Conference on Applications , Technologies , Architectures , and Protocols for Computer Communications 301-312. ACM, New York. · Zbl 1288.94028
[43]	Zhu, W. and Geng, Z. (2004). A fast method to estimate loss rate. In Information Networking. Networking Technologies for Broadband and Mobile Networks 473-482. Springer, Berlin.
[44]	Zhu, W. and Geng, Z. (2005). A bottom-up inference of loss rate. Comput. Commun. 28 351-365.