Traffic engineering with estimated traffic matrices

ABSTRACT

Traffic engineering and traffic matrix estimation are often treated as separate fields, even though one of the major applications for a traffic matrix is traffic engineering. In cases where a traffic matrix cannot be measured directly, it may still be estimated from indirect data (such as link measurements), but these estimates contain errors. Yet little thought has been given to the effects of inexact traffic estimates on traffic engineering. In this paper we consider how well traffic engineering works with estimated traffic matrices in the context of a specific task; namely that of optimizing network routing to minimize congestion, measured by maximum link-utilization. Our basic question is: how well is the real traffic routed if the routing is only optimized for an estimated traffic matrix? We compare against optimal routing of the real traffic using data derived from an operational tier-1 ISP. We find that the magnitude of errors in the traffic matrix estimate is not, in itself, a good indicator of the performance of that estimate in route optimization. Likewise, the optimal algorithm for traffic engineering given knowledge of the real traffic matrix is no longer the best with only the estimated traffic matrix as input. Our main practical finding is that the combination of a known traffic matrix estimation technique and a known traffic engineering technique can get close to the optimum in avoiding congestion for the real traffic. We even demonstrate stability in the sense that routing optimized on data from one day continued to perform well on subsequent days. This stability is crucial for the practical relevance to off-line traffic engineering, as it can be performed by ISPs today.

REFERENCES

• 1: 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]
• 2: 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]
• 3: 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]
• 4: 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
• 5: 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
• 6: D. Mitra and K.G.Ramakrishnan, "A case study of multiservice, multipriority traffic engineering design for data networks," in Proc. IEEE GLOBECOM, pp. 1077--1083, 1999.
• 7: B. Fortz and M. Thorup, "Internet traffic engineering by optimizing OSPF weights," in Proc. IEEE INFOCOM, pp. 519--528, 2000.
• 8: K. Ramakrishnan and M. Rodriguez, "Optimal routing in shortest-path data networks," Lucent Bell Labs Technical Journal, vol. 6, no. 1, 2001.
• 9: F. Lin and J. Wang, "Minimax open shortest path first routing algorithms in networks supporting the SMDS services," in Proc. IEEE International Conference on Communications (ICC), vol. 2, pp. 666--670, 1993.
• 10: M. Ericsson, M. Resende, and P. Pardalos, "A genetic algorithm for the weight setting problem in OSPF routing," J. Combinatorial Optimization, vol. 6, no. 3, pp. 299--333, 2002.
• 11: L. S. Buriol, M. G. C. Resende, C. C. Ribeiro, and M. Thorup, "A memetic algorithms for OSPF routing," in Proc. 6th INFORMS Telecom, pp. 187--188, 2002.
• 12: B. Fortz and M. Thorup, "Optimizing OSPF/IS-IS weights in a changing world," IEEE Journal on Selected Areas in Communications (Special Issue on Recent Advances on Fundamentals of Network Management), vol. 20, no. 4, pp. 756--767, 2002.
• 13: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 14: E. C. Rosen, A. Viswanathan, and R. Callon, "Multiprotocol label switching architecture." Network Working Group, Request for Comments, http://search.ietf.org/rfc/rfc3031.txt, 2001.
• 15: J. T. Moy, "OSPF version 2." Network Working Group, Request for Comments: 2328, http://search.ietf.org/rfc/rfc2328.txt, April 1998.
• 16: R. Callon, "Use of OSI IS-IS for routing in TCP/IP and dual environments." Network Working Group, Request for Comments: 1195, http://search.ietf.org/rfc/rfc1195.txt, December 1990.
• 17: Cisco, "Configuring OSPF," 2001. Documentation at http://www.cisco.com/univercd/cc/td/doc/product/software/ios121/121cgcr/ip_c/ipcprt2/1cdospf.htm.
• 18: Emile Aarts , Jan K. Lenstra, Local Search in Combinatorial Optimization, John Wiley & Sons, Inc., New York, NY, 1997
• 19: J. Kowalski and B. Warfield, "Modeling traffic demand between nodes in a telecommunications network," in ATNAC'95, 1995.
• 20: J. Tinbergen, "Shaping the world economy: Suggestions for an international economic policy." The Twentieth Century Fund, 1962.
• 21: P. Poyhonen, "A tentative model for the volume of trade between countries," Weltwirtschaftliches Archive, vol. 90, pp. 93--100, 1963.
• 22: A. Dwivedi and R. Wagner, "Traffic model for USA long-distance optimal network," in Proc. Optical Fiber Communication Conference (OFC), pp. 156--158, 2000.
• 23: A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford, "Netscope: Traffic engineering for IP networks," IEEE Network Magazine, special issue on Internet traffic engineering, pp. 11--19, March/April 2000.
• 24: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 25: David Applegate , Edith Cohen, Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863991]
• 26: 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
• 27: K. Calvert, M. Doar, and E. W. Zegura, "Modeling internet topology," IEEE Communications Magazine, vol. 35, no. 6, pp. 160--163, June 1997.
• 28: P. L. Toint. Transportation modeling and operations research: A fruitful connection. In M. Labbe, G. Laporte, K. Tanczos, and P. L. Toint, editors, Operations Research and Decision Aid Methodologies in Traffic and Transportation Management, volume 166 of NATO ASI series: Ser. F, Computer and systems sciences, pages 1--27. Springer, 1998.

INDEX TERMS

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

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

General Terms:
Measurement, Performance

Keywords:
MPLS, OSPF, SNMP, traffic engineering, traffic matrix estimation