An information-theoretic approach to traffic matrix estimation

ABSTRACT

Traffic 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 interest in inferring traffic matrices from link measurements and other more easily measured data. Typically, this inference problem is ill-posed, as it involves significantly more unknowns than data. Experience in many scientific and engineering fields has shown that it is essential to approach such ill-posed problems via "regularization". This paper presents a new approach to traffic matrix estimation using a regularization based on "entropy penalization". Our solution chooses the traffic matrix consistent with the measured data that is information-theoretically closest to a model in which source/destination pairs are stochastically independent. We use fast algorithms based on modern convex optimization theory to solve for our traffic matrices. We evaluate the algorithm with real backbone traffic and routing data, and demonstrate that it is fast, accurate, robust, and flexible.

REFERENCES

• 1: M. Bertero, T. Poggio, and V. Torre. Ill-posed problems in early vision. In Proc. of the IEEE, 76:869--889, 1988.
• 2: I. J. Craig and J. C. Brown. Inverse Problems in Astronomy: A Guide to Inversion Strategies for Remotely Sensed Data. Adam Hilger, Boston, 1986.
• 3: J. Cao, D. Davis, S. V. Wiel, and B. Yu. Time-varying network tomography. J. Amer. Statist. Assoc, 95(452):1063--1075, 2000.
• 4: J. Cao, S. V. Wiel, B. Yu, and Z. Zhu. A scalable method for estimating network traffic matrices from link counts. Preprint. Available at http://stat-www.berkeley.edu/binyu/publications.html.
• 5: Scott Shaobing Chen , David L. Donoho , Michael A. Saunders, Atomic Decomposition by Basis Pursuit, SIAM Review, v.43 n.1, p.129-159, 2001 [doi>10.1137/S003614450037906X]
• 6: B. Efron and C. Morris. Stein's paradox in statistics. Scientific American, 236(5):119--127, 1977.
• 7: A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford. Netscope: Traffic engineering for IP networks. IEEE Network Magazine, pages 11--19, March/April 2000.
• 8: 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]
• 9: P. C. Hansen. Regularization tools for Matlab. http://www.imm.dtu.dk/pch/Regutools/index.html.
• 10: P. C. Hansen. Regularization tools: A Matlab package for analysis and solution of discrete ill-posed problems. Numerical Algorithms, 6:1--35, 1994.
• 11: Per Christian Hansen, Rank-deficient and discrete ill-posed problems: numerical aspects of linear inversion, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 12: G. Jumarie, Relative information: theories and applications, Springer-Verlag New York, Inc., New York, NY, 1990
• 13: E. Lehmann. Theory of Point Estimates. Wiley, New York, 1983.
• 14: Ratul Mahajan , Neil Spring , David Wetherall , Tom Anderson, Inferring link weights using end-to-end measurements, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637237]
• 15: 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.
• 16: 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
• 17: Arnold Neumaier, Solving Ill-Conditioned and Singular Linear Systems: A Tutorial on Regularization, SIAM Review, v.40 n.3, p.636-666, Sept. 1998 [doi>10.1137/S0036144597321909]
• 18: R. Parker. Geophysical Inverse Theory. Princeton University Press, Princeton, NJ, 1994.
• 19: Aman Shaikh , Chris Isett , Albert Greenberg , Matthew Roughan , Joel Gottlieb, A case study of OSPF behavior in a large enterprise network, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637236]
• 20: J. Skilling. The axioms of maximum entropy. In G. J. Erickson and C. R. Smith, editors, Maximum-Entropy and Bayesian Methods in Science and Engineering, Volume 1: Foundations, pages 173--187. Kluwer Academic Publishers, 1988.
• 21: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 22: N. Spring, R. Mahajan, D. Wetherall, and H. Hagerstrom. Rocketfuel: An ISP topology mapping engine. http://www.cs.washigton.edu/research/networking/rocketfuel/.
• 23: C. Tebaldi and M. West. Bayesian inference on network traffic using link count data. J. Amer. Statist. Assoc, 93(442):557--576, 1998.
• 24: Y. Vardi. Network tomography: estimating source-destination traffic intensities from link data. J. Am. Statist. Assoc., 91:365--377, 1996.
• 25: G. Varghese and C. Estan. The measurement manifesto. Technical Report CS2003-0747, UCSD, 2003.
• 26: G. Wahba. Constrained regularization for ill posed linear operator equations, with applications in meteorology and medicine. In Statistical Decision Theory and Related Topics III, 2:383--418, Academic Press, 1982.
• 27: B. Yu. Maximum pseudo likelihood estimation in network tomography. In NISS Internet Tomography Technical Day, Research Triangle Park, March 28 2003. Available at http://www.niss.org/affiliates/internet030328/presentations20030328.html.
• 28: Yin Zhang , Matthew Roughan , Nick Duffield , Albert Greenberg, Fast accurate computation of large-scale IP traffic matrices from link loads, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

General Terms:
Measurement, Performance

Keywords:
SNMP, information theory, minimum, mutual information, regularization, traffic engineering, traffic matrix estimation