Fast accurate computation of large-scale IP traffic matrices from link loads

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.

REFERENCES

• 1: 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.
• 2: Matthew Roughan , Albert Greenberg , Charles Kalmanek , Michael Rumsewicz , Jennifer Yates , Yin Zhang, Experience in measuring backbone traffic variability: models, metrics, measurements and meaning, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637213]
• 3: 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.
• 4: J. Kowalski and B. Warfield, "Modeling traffic demand between nodes in a telecommunications network," in ATNAC'95, 1995.
• 5: J. Tinbergen, "Shaping the world economy: Suggestions for an international economic policy." The Twentieth Century Fund, 1962.
• 6: P. Pöyhönen, "A tentative model for the volume of trade between countries," Weltwirtschaftliches Archive, 90, pp. 93--100, 1963.
• 7: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 8: Y. Vardi, "Network tomography: estimating source-destination traffic intensities from link data," J. Am. Statist. Assoc.,91, pp.365--377,1996.
• 9: C. Tebaldi and M. West, "Bayesian inference on network traffic using link count data," J. Amer. Statist. Assoc, 93, pp. 557--576, 1998.
• 10: J. Cao, D. Davis, S. V. Wiel, and B. Yu, "Time-varying network tomography," J. Amer. Statist. Assoc, 95, pp. 1063--1075, 2000.
• 11: 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.
• 12: M. Coates, A. Hero, R. Nowak, and B. Yu, "Internet tomography," IEEE Signal Processing Magazine, May 2002.
• 13: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.265-280, June 2001 [doi>10.1109/90.929850]
• 14: 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.
• 15: 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.
• 16: 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.
• 17: J. Cao, S. V. Wiel, B. Yu, and Z. Zhu, "A scalable method for estimating network traffic matrices from link counts." preprint.
• 18: J. G. Klincewicz. private communications, 2000.
• 19: 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.
• 20: 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.
• 21: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 22: 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.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

General Terms:
Measurement, Performance

Keywords:
SNMP, traffic engineering, traffic matrix estimation