Network tomography on correlated links

ABSTRACT

Network tomography establishes linear relationships between the characteristics of individual links and those of end-to-end paths. It has been proved that these relationships can be used to infer the characteristics of links from end-to-end measurements, provided that links are not correlated, i.e., the status of one link is independent from the status of other links.

In this paper, we consider the problem of identifying link characteristics from end-to-end measurements when links are "correlated," i.e., the status of one link may depend on the status of other links. There are several practical scenarios in which this can happen; for instance, if we know the network topology at the IP-link or at the domain-link level, then links from the same local-area network or the same administrative domain are potentially correlated, since they may be sharing physical links, network equipment, even management processes.

We formally prove that, under certain well defined conditions, network tomography works when links are correlated, in particular, it is possible to identify the probability that each link is congested from end-to-end measurements. We also present a practical algorithm that computes these probabilities. We evaluate our algorithm through extensive simulations and show that it is accurate in a variety of realistic congestion scenarios.

References

1. Boston University Representative Internet Topology Generator. http://www.cs.bu.edu/brite/.
2. 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.
3. V. Arya, N. Duffield, and D. Veitch. Temporal Delay Tomography. In Proceedings of the IEEE INFOCOM Conference, 2008.
4. T. Bu, N. Duffield, F. L. Presti, and D. Towsley. Network Tomography on General Topologies. In Proceedings of the ACM SIGMETRICS Conference, 2002.
5. 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.
6. 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.
7. A. Chen, J. Cao, and T. Bu. Network Tomography: Identifiability and Fourier Domain Estimation. In Proceedings of the IEEE INFOCOM Conference, 2007.
8. M. Coates and R. Nowak. Network Loss Inference Using Unicast End-to-End Measurement. In Proceedings of the ITC Specialist Seminar on IP Traffic Measurement, Modeling and Management, 2000.
9. N. Duffield, F. L. Presti, V. Paxson, and D. Towsley. Inferring Link Loss Using Striped Unicast Probes. In Proceedings of the IEEE INFOCOM Conference, 2001.
10. N. G. Duffield. Network Tomography of Binary Network Performance Characteristics. IEEE Transactions on Information Theory, 52(12):5373--5388, December 2006.
11. H. X. Nguyen and P. Thiran. Network Loss Inference with Second Order Statistics of End-to-End Flows. In Proceedings of the IEEE Internet Measurement Conference (IMC), 2007.
12. H. X. Nguyen and P. Thiran. The Boolean Solution to the Congested IP Link Location Problem: Theory and Practice. In Proceedings of the IEEE INFOCOM Conference, 2007.
13. V. N. Padmanabhan, L. Qiu, and H. J. Wang. Server-based Inference of Internet Performance. In Proceedings of the IEEE INFOCOM Conference, 2003.
14. H. Singhal and G. Michailidis. Identifiability of Flow Distributions from Link Measurements with Applications to Computer Networks. Inverse Problems, 23:1821--1850, 2007.
15. J. Sommers, P. Barford, N. Duffield, and A. Ron. Accurate and Efficient SLA Compliance Monitoring. In Proceedings of the ACM SIGCOMM Conference, 2007.
16. H. H. Song, L. Qiu, and Y. Zhang. NetQuest: A Flexible Framework for Large-Scale Network Measurement. In Proceedings of the ACM SIGMETRICS Conference, 2006.
17. Y. Tsang, M. Coates, and R. Nowak. Passive Network Tomography Using the EM Algorithms. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2001.
18. Y. Vardi. Network Tomography: Estimating Source-Destination Traffic Intensities. Journal of the American Statistical Association, 91:365--377, 1996.
19. Y. Zhao, Y. Chen, and D. Bindel. Toward Unbiased End-to-End Network Diagnosis. In Proceedings of the ACM SIGCOMM Conference, 2006.

Index Terms

• Networks

  • Network services

    • Network monitoring