Network loss inference with second order statistics of end-to-end flows

ABSTRACT

We address the problem of calculating link loss rates from end-to-end measurements. Contrary to existing works that use only the average end-to-end loss rates or strict temporal correlations between probes, we exploit second-order moments of end-to-end flows. We first prove that the variances of link loss rates can be uniquely calculated from the covariances of the measured end-to-end loss rates in any realistic topology. After calculating the link variances, we remove the un-congested links with small variances from the first-order moment equations to obtain a full rank linear system of equations, from which we can calculate precisely the loss rates of the remaining congested links. This operation is possible because losses due to congestion occur in bursts and hence the loss rates of congested links have high variances. On the contrary, most links on the Internet are un-congested, and hence the averages and variances of their loss rates are virtually zero. Our proposed solution uses only regular unicast probes and thus is applicable in today's Internet. It is accurate and scalable, as shown in our simulations and experiments on PlanetLab.

References

1. A. Adams, T. Bu, T. Friedman, J. Horowitz, D. Towstey, R. Caceres, N. Duffield, F. L. Presti, S. B. Moon, and V. Paxson. The use of end-to-end multicast measurements for characterizing internal network behavior. IEEE Communications Magazine, May 2000.
2. A. Akella, S. Seshan, and A. Shaikh. An empirical evaluation of wide-area internet bottlenecks. In Proc. IMC 03, 2003.
3. K. Anagnostakis, M. Greenwald, and R. Ryger. Cing: Measuring network internal delays using only existing infrastructure. In Proc. IEEE Infocom, 2003.
4. D. Arifler, G. de Veciana, and B. L. Evans. A factor analysis approach to inferring congestion sharing based on flow level measurements. IEEE/ACM Transactions on Networking, 2007.
5. B. Augustin, X. Cuvellier, B. Orgogozo, F. Viger, T. Friedman, M. Latapy, C. Magnien, and R. Teixeira. Avoiding traceroute anomalies with paris traceroute. In Proc. of the Internet Measurement Conference, October 2006.
6. T. Bu, N. Duffield, F. L. Presti, and D. Towsley. Network tomography on general topologies. In Proceedings ACM Sigmetrics 2002, Marina Del Rey, CA, 2002.
7. R. Caceres, N. G. Duffield, J. Horowitz, and D. Towsley. Multicast-based inference of network-internal loss characteristics. IEEE Transactions on Information Theory, 45:2462--2480, 1999.
8. J. Cao, D. Davis, S. V. Wiel, and B. Yu. Time-varying network tomography: Router link data. Journal of the American Statistical Association, 95(452):1063--1075, Dec. 2000.
9. A. Chen, J. Cao, and T. Bu. Network tomography: Identifiability and fourier domain estimation. In Proceedings of the IEEE Infocom, Alaska, May 2007.
10. Y. Chen, D. Bindel, H. Song, and R. H. Katz. An algebraic approach to practical and scalable overlay network monitoring. In Proceedings of the ACM SIGCOMM, Portland, August-September 2004.
11. M. Coates, A. Hero, R. Nowak, and B. Yu. Internet tomography. IEEE Signal Processing Magazine, 19, May 2002.
12. M. Coates and R. Nowak. Network loss inference using unicast end-to-end measurement. In Proceedings of the ITC Seminar on IP Traffic, Measurements and Modelling, Monterey, September 2000.
13. N. Duffield, F. L. Presti, V. Paxson, and D. Towsley. Inferring link loss using striped unicast probes. In Proceedings of the IEEE Infocom 2001, Alaska, April 2001.
14. N. G. Duffield. Network tomography of binary network performance characteristics. IEEE Transactions on Information Theory, 52(12):5373--5388, Dec. 2006.
15. G. H. Golub and C. F. V. Loan. Matrix Computations. The Johns Hopkins University Press, 1996.
16. L. P. Hansen. Large sample properties of generalized method of moments estimators. Econometrica, 50:1029--1054, 1982.
17. K. Harfoush, A. Bestavros, and J. Byers. Robust identification of shared losses using end-to-end unicast probes. In Proc. of ICNP'00, 2000.
18. V. Jacobson. traceroute, ftp://ftp.ee.lbl.gov/traceroute.tar.z, 1989.
19. M. S. Kim, T. Kim, Y. S. Hin, S. S. Lam, and E. J. Powers. A wavelet-based approach to detect shared congestion. In Proceeding of the ACM SIGCOMM'04, 2004.
20. R. Mahajan, N. Spring, D. Wetherall, and T. Anderson. User-level internet path diagnosis. In Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP'03), pages 106--119, 2003.
21. A. Medina, I. Matta, and J. Byers. On the origin of power-laws in internet topologies. ACM Computer Communication Review, pages 160--163, 2000.
22. H. X. Nguyen and P. Thiran. The boolean solution to the congested IP link location problem: Theory and practice. In Proceedings of IEEE INFOCOM 2007, May 2007.
23. U. of Oregon Route Views Archive Project. http://www.routeviews.org/.
24. V. N. Padmanabhan, L. Qiu, and H. J. Wang. Server-based inference of internet performance. In Proceedings of the IEEE INFOCOM'03, San Francisco, CA, April 2003.
25. M. Roughan. Fundamental bounds on the accuracy of network performance measurements. In Proceedings of ACM SIGMETRICS, June 2005.
26. D. Rubenstein, J. Kurose, and D. Towsley. Detecing shared congestion of flows via end-to-end measurement. IEEE/ACM Transactions on Networking, 10(3), June 2002.
27. J. Sommers, P. Barford, N. Duffield, and A. Ron. Improving accuracy in end-to-end packet loss measurement. In Proceedings of ACM SIGCOMM, August 2005.
28. N. Spring, D. Wetherall, and T. Anderson. Scriptroute: A public internet measurement facility. In USENIX Symposium on Internet Technologies and Systems (USITS), 2003.
29. Y. Tsang, M. Coates, and R. Nowak. Passive network tomography using the EM algorithms. In Proc. IEEE ICASSP., 2001.
30. Y. Vardi. Network tomography: Estimating source-destination traffic intensities. Journal of the American Statistical Association, 91:365--377, 1996.
31. V. Paxson. end-to-end routing behaviour in the internet. In Proceedings of ACM SIGCOMM, Aug 1996.
32. V. Paxson. End-to-end internet packet dynamics. In Proceedings of the ACM SIGCOMM, Sep 1997.
33. www.netdimes.org.
34. www.planet-lab.org.
35. Y. Zhang, N. Duffield, V. Paxson, and S. Shenker. On the constancy of internet path properties. In Proceedings of ACM SIGCOMM Internet Measurement Workshop, San Francisco, 2001.
36. Y. Zhao, Y. Chen, and D. Bindel. Toward unbiased end-to-end network diagnosis. In Proceedings of ACM SIGCOMM, Pisa, Italy, 2006.

Index Terms

• Networks

  • Network services

    • Network management

    • Network monitoring