Maximum likelihood network topology identification from edge-based unicast measurements

ABSTRACT

Network tomography is a process for inferring "internal" link-level delay and loss performance information based on end-to-end (edge) network measurements. These methods require knowledge of the network topology; therefore a first crucial step in the tomography process is topology identification. This paper considers the problem of discovering network topology solely from host-based, unicast measurements, without internal network cooperation. First, we introduce a novel delay-based measurement scheme that does not require clock synchronization, making it more practical than other previous proposals. In contrast to methods that rely on network cooperation , our methodology has the potential to identify layer two elements (provided they are logical topology branching points and induce some measurable delay). Second, we propose a maximum penalized likelihood criterion for topology identification. This is a global optimality criterion, in contrast to other recent proposals for topology identification that employ suboptimal, pair-merging strategies. We develop a novel Markov Chain Monte Carlo (MCMC) procedure for rapid determination of the most likely topologies. The performance of our new probing scheme and identification algorithm is explored through simulation and Internet experiments.

REFERENCES

• 1: C. Andrieu, A. Doucet, W. Fitzgerald, and J. Peréz. Bayesian computational approaches to model selection. In Nonlinear and Non Gaussian Signal Processing, Cambridge: Newton Institute Series. Cambridge University Press, 2000.
• 2: Azer Bestavros , John Byers , Khaled Harfoush, Inference and Labeling of Metric-Induced Network Topologies, Boston University, Boston, MA, 2001
• 3: R. Cáceres, N. Duffield, J. Horowitz, and D. Towsley. Multicast-based inference of network-internal loss characteristics. IEEE Trans. Info. Theory, 45(7):2462-2480, November 1999.
• 4: H. Chipman, E. George, and R. McCulloch. Bayesian CART model search (with discussion). J. Am. Stat. Assoc., 93(6):937-960, 1998.
• 5: M. Coates and R. Nowak. Network loss inference using unicast end-to-end measurement. In ITC Seminar on IP Traffic, Measurement and Modelling, Monterey, CA, Sep. 2000.
• 6: M. Coates and R. Nowak. Network delay distribution inference from end-to-end unicast measurement. In Proc. IEEE Int. Conf. Acoust., Speech, and Signal Proc., Salt Lake City, UT, May 2001.
• 7: M. Coates and R. Nowak. Sequential Monte Carlo inference of internal delays in nonstationary data networks. IEEE Trans. Signal Processing, 50(2):366-376, Feb. 2002.
• 8: N. Duffield, J. Horowitz, and F. L. Presti. Adaptive multicast topology inference. In Proceedings of IEEE INFOCOM 2001, Anchorage, Alaska, April 2001.
• 9: N. Duffield, J. Horowitz, F. L. Presti, and D. Towsley. Multicast topology inference from end-to-end measurements. In ITC Seminar on IP Traffic, Measurement and Modelling, Monterey, CA, Sep. 2000.
• 10: N. Duffield, J. Horowitz, F. L. Presti, and D. Towsley. Multicast topology inference from measured end-to-end loss. IEEE Trans. Info. Theory, 48(1):26-45, January 2002.
• 11: N. Duffield, F. L. Presti, V. Paxson, and D. Towsley. Inferring link loss using striped unicast probes. In Proceedings of IEEE INFOCOM 2001, Anchorage, Alaska, April 2001.
• 12: S. Geman and D. Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. PAMI, 6(6):721-741, 1984.
• 13: P. Green. Reversible jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika, 82:711-732, 1995.
• 14: 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
• 15: Khaled Harfoush , Azer Bestavros , John Byers, Measuring Bottleneck Bandwidth of Targeted Path Segments, Boston University, Boston, MA, 2001
• 16: W. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57:97-109, 1970.
• 17: 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
• 18: N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller. Equations of state calculations by fast computing machines. J. Chem. Phys., 21:1087-1091, 1953.
• 19: UCB/LBNL/VINT network simulator ns (version 2). www.isi.edu/nsnam/ns/.
• 20: Vern Paxson, End-to-end internet packet dynamics, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.277-292, June 1999 [doi>10.1109/90.779192]
• 21: F. LoPresti , N. G. Duffield , J. Horowitz , D. Towsley, Multicast-Based Inference of Network-Internal Delay Distributions TITLE2:, University of Massachusetts, Amherst, MA, 1999
• 22: S. Ratnasamy and S. McCanne. Inference of multicast routing trees and bottleneck bandwidths using end-to-end measurements. In Proceedings of IEEE INFOCOM 1999, New York, NY, March 1999.
• 23: S. Richardson and P. Green. On Bayesian analysis of mixtures with an unknown number of components. J. Roy. Stat. Soc. B, 59:731-792, 1997.
• 24: Jorma Rissanen, Stochastic Complexity in Statistical Inquiry Theory, World Scientific Publishing Co., Inc., River Edge, NJ, 1989
• 25: Christian P. Robert , George Casella, Monte Carlo Statistical Methods (Springer Texts in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 26: Dan Rubenstein , Jim Kurose , Don Towsley, Detecting shared congestion of flows via end-to-end measurement, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.145-155, June 18-21, 2000, Santa Clara, California, United States