Yin Zhang
Matthew Roughan
Albert Greenberg
Abstract
A matrix giving the traffic volumes between origin and destination in a network has tremendously potential utility for network capacity planning and management. Unfortunately, traffic matrices are generally unavailable in large operational IP networks. On the other hand, link load measurements are readily available in IP networks. In this paper, we propose a new method for practical and rapid inference of traffic matrices in IP networks from link load measurements, augmented by readily available network and routing configuration information. We apply and validate the method by computing backbone-router to backbone-router traffic matrices on a large operational tier-1 IP network -- a problem an order of magnitude larger than any other comparable method has tackled. The results show that the method is remarkably fast and accurate, delivering the traffic matrix in under five seconds.
- M. Grossglauser and J. Rexford, "Passive traffic measurement for IP operations," in The Internet as a Large-Scale Complex System (K.Park and W. Willinger, eds.), Oxford University Press, 2002.Google Scholar
- M. Roughan, A. Greenberg, C. Kalmanek, M. Rumsewicz, J. Yates, and Y. Zhang, "Experience in measuring backbone traffic variability: Models, metrics, measurements and meaning (extended abstract)," in ACM SIGCOMM Internet Measurement Workshop, 2002. Google ScholarDigital Library
- D. Lam, D. Cox, and J. Widom, "Teletraffic modeling for personal communications services," IEEE Communications Magazine: Special Issues on Teletraffic Modeling Engineering and Management in Wireless and Broadband Networks, 35, pp. 79--87, February 1997. Google ScholarDigital Library
- J. Kowalski and B. Warfield, "Modeling traffic demand between nodes in a telecommunications network," in ATNAC'95, 1995.Google Scholar
- J. Tinbergen, "Shaping the world economy: Suggestions for an international economic policy." The Twentieth Century Fund, 1962.Google Scholar
- P. Pöyhönen, "A tentative model for the volume of trade between countries," Weltwirtschaftliches Archive, 90, pp. 93--100, 1963.Google Scholar
- A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, and C. Diot, "Traffic matrix estimation: Existing techniques and new directions," in ACM SIGCOMM, (Pittsburg, USA), August 2002. Google ScholarDigital Library
- Y. Vardi, "Network tomography: estimating source-destination traffic intensities from link data," J. Am. Statist. Assoc.,91, pp.365--377,1996.Google ScholarCross Ref
- C. Tebaldi and M. West, "Bayesian inference on network traffic using link count data," J. Amer. Statist. Assoc, 93, pp. 557--576, 1998.Google ScholarCross Ref
- J. Cao, D. Davis, S. V. Wiel, and B. Yu, "Time-varying network tomography," J. Amer. Statist. Assoc, 95, pp. 1063--1075, 2000.Google ScholarCross Ref
- A. Adams, T. Bu, R. Cáceres, N. Duffield, T. Friedman, J. Horowitz, F. L. Presti, S. Moon, V. Paxson, and D. Towsley, "The use of end-to-end multicast measurements for characterizing internal network behavior," IEEE Communications Magazine, May 2000. Google ScholarDigital Library
- M. Coates, A. Hero, R. Nowak, and B. Yu, "Internet tomography," IEEE Signal Processing Magazine, May 2002.Google ScholarCross Ref
- A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, and F. True, "Deriving traffic demands for operational IP networks: Methodology and experience," IEEE/ACM Transactions on Networking, pp. 265--279, June 2001. Google ScholarDigital Library
- W. Fang and L. Peterson, "Inter-AS traffic patterns and their implications," in Proceedings of IEEE GLOBECOM '99, (Rio de Janeiro, Brazil), pp. 1859--1868, 1999.Google Scholar
- N. Feamster, J. Borkenhagen, and J. Rexford, "Controlling the impact of BGP policy changes on IP traffic," Tech. Rep. 011106-02-TM, AT&T Labs -- Research, Nov 2001.Google Scholar
- A. Dempster, N. Laird, and D. Rubin, "Maximum likelihood from incomplete data via the em algorithm (with discussion)," J. Roy. Statist. Soc. Ser., 39, pp. 1--38, 1977.Google Scholar
- J. Cao, S. V. Wiel, B. Yu, and Z. Zhu, "A scalable method for estimating network traffic matrices from link counts." preprint.Google Scholar
- J. G. Klincewicz. private communications, 2000.Google Scholar
- A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford, "Netscope: Traffic engineering for IP networks," IEEE Network Magazine, pp. 11--19, March/April 2000. Google ScholarDigital Library
- A. Medina, C. Fraleigh, N. Taft, S. Bhattacharyya, and C. Diot, "A taxonomy of IP traffic matrices," in SPIE ITCOM: Scalability and Traffic Control in IP Networks II, (Boston, USA), August 2002.Google Scholar
- E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. D. Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorense, LAPACK Users' Guide. SIAM, 3rd ed., 1999. Google ScholarDigital Library
- B. Fortz and M. Thorup, "Optimizing OSPF/IS-IS weights in a changing world," To appear in IEEE JSAC Special Issue on Advances in Fundamentals of Network Management, Spring 2002. Google ScholarDigital Library
Index Terms
- Fast accurate computation of large-scale IP traffic matrices from link loads
Recommendations
Traffic matrix estimation on a large IP backbone: a comparison on real data
IMC '04: Proceedings of the 4th ACM SIGCOMM conference on Internet measurementThis paper considers the problem of estimating the point-to-point traffic matrix in an operational IP backbone. Contrary to previous studies, that have used a partial traffic matrix or demands estimated from aggregated Netflow traces, we use a unique ...
An information-theoretic approach to traffic matrix estimation
SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communicationsTraffic matrices are required inputs for many IP network management tasks: for instance, capacity planning, traffic engineering and network reliability analysis. However, it is difficult to measure these matrices directly, and so there has been recent ...
Fast accurate computation of large-scale IP traffic matrices from link loads
SIGMETRICS '03: Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systemsA matrix giving the traffic volumes between origin and destination in a network has tremendously potential utility for network capacity planning and management. Unfortunately, traffic matrices are generally unavailable in large operational IP networks. ...
Comments