Network tomography on general topologies

ABSTRACT

In this paper we consider the problem of inferring link-level loss rates from end-to-end multicast measurements taken from a collection of trees. We give conditions under which loss rates are identifiable on a specified set of links. Two algorithms are presented to perform the link-level inferences for those links on which losses can be identified. One, the minimum variance weighted average (MVWA) algorithm treats the trees separately and then averages the results. The second, based on expectation-maximization (EM) merges all of the measurements into one computation. Simulations show that EM is slightly more accurate than MVWA, most likely due to its more efficient use of the measurements. We also describe extensions to the inference of link-level delay, inference from end-to-end unicast measurements, and inference when some measurements are missing.

REFERENCES

• 1: A. Adams, T. Bu, R. Caceres, N. G. Duffield, T. Friedman, J. Horowitz, F. Lo Presti, S. B. Moon, V. Paxson, and D. Towsley. "The Use of End-to-End Multicast Measurements for Characterizing Internal Network Behavior", IEEE Communications Magazine, May 2000.
• 2: Micah Adler , Tian Bu , Ramesh K. Sitaraman , Donald F. Towsley, Tree Layout for Internal Network Characterizations in Multicast Networks, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.189-204, November 07-09, 2001
• 3: T. Bu, N. G. Duffield, F. Lo Presti, and D. Towsley. "Network Tomography on General Topologies". UMass CMPSCI Technique Report.
• 4: R. Cáceres, N. G. Duffield, J. Horowitz, and D. Towsley. "Multicast-Based Inference of Network Internal Loss Characteristics" IEEE Trans. on Information Theory, vol. 45, pp. 2462-2480, 1999.
• 5: R. Caceres, N. G. Duffield, J. Horowitz, D. Towsley, and T. Bu. "Multicast-Based Inference of Network-Internal Characteristics: Accuracy of Packet Loss Estimation". Proceedings of INFOCOM'99.
• 6: M. Coates and R. Nowak. "Network loss inference using unicast end-to-end measurement", Proc. ITC Conf. IP Traffic, Modeling and Management, Monterey, CA, September 2000.
• 7: M. Coates and R. Nowak. "Sequential Monte Carlo Inference of Internal Delays in Nonstationary Communication Networks," submitted for publication, Jan 2001.
• 8: M. J. Coates and R. Nowak. "Network Delay Distribution Inference from End-to-end Unicast Measurement," Proc. of the IEEE International Conference on Acoustics, Speech, and Signal Processing, May 2001.
• 9: Nick G. Duffield , Joseph Horowitz , Francesco Lo Presti , Donald F. Towsley, Network Delay Tomography from End-to-End Unicast Measurements, Proceedings of the Thyrrhenian International Workshop on Digital Communications: Evolutionary Trends of the Internet, p.576-595, September 17-20, 2001
• 10: N. G. Duffield, J. Horowitz, D. Towsley, W. Wei, and T. Friedman. "Multicast-based loss inference with missing data", to appear in IEEE Journal of Selected Areas in Communications
• 11: N. G. Duffield, F. Lo Presti, V. Paxson, and D. Towsley. "Inferring Link Loss Using Striped Unicast Probes", Proc. IEEE INFOCOM 2001, Anchorage, AK, April 2001.
• 12: Omer Gurewitz and Moshe Sidi. "Estimating One-way Delays from Cyclic-Path Delay Measurements", Proc. IEEE INFOCOM 2001, Anchorage, AK, April 2001.
• 13: K. Harfoush , A. Bestavros , J. Byers, Robust identification of shared losses using end-to-end unicast probes, Proceedings of the 2000 International Conference on Network Protocols, p.22, November 14-17, 2000
• 14: Kevin Lai , Mary Baker, Measuring link bandwidths using a deterministic model of packet delay, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.283-294, August 28-September 01, 2000, Stockholm, Sweden
• 15: Geoffrey J. McLachlan and Thriyambakam Krishnan. The EM algorithm and extensions. John Wiley, New York (1997)
• 16: R. Penrose. "A Generalized Inverse for Matrices." Proc. Cambridge Phil. Soc. 51, 406-413, 1955.
• 17: F. Lo Presti, N. G. Duffield, J. Horowitz, and D. Towsley. "Multicast-Based Inference of Network-Internal Delay Distributions", submitted for publication, September 1999.
• 18: ns --- Network Simulator. See http://www-mash.cs.berkeley.edu/ns/ns.html
• 19: Y. Shavitt, X. Sun, A. Wool, and B. Yener. "Computing the unmeasured: an algebraic approach to mapping the Internet," Proc. IEEE INFOCOM 2001, Anchorage, AK, April 2001.
• 20: C. F. Jeff Wu. "On the convergence properties of the EM algorithm", Annals of Statistics, vol. 11, pp. 95-103, 1982.
• 21: Abilene Network Operations Center. http://www.abilene.iu.edu/
• 22: The Abilene network multicast deployment. http://www.abilene.iu.edu/images/ab-mcast.pdf