COPE: traffic engineering in dynamic networks

ABSTRACT

Traffic engineering plays a critical role in determining the performance and reliability of a network. A major challenge in traffic engineering is how to cope with dynamic and unpredictable changes in traffic demand. In this paper, we propose COPE, a class of traffic engineering algorithms that optimize for the expected scenarios while providing a worst-case guarantee for unexpected scenarios. Using extensive evaluations based on real topologies and traffic traces, we show that COPE can achieve efficient resource utilization and avoid network congestion in a wide variety of scenarios.

REFERENCES

• 1: Abilene topology and traffic dataset. http://www.cs.utexas.edu~yzhang/research/AbileneTM/.
• 2: Abilene Observatory. http://abilene.internet2.edu/observatory/.
• 3: Sharad Agarwal , Chen-Nee Chuah , Supratik Bhattacharyya , Christophe Diot, The impact of BGP dynamics on intra-domain traffic, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 4: Sharad Agarwal , Antonio Nucci , Supratik Bhattacharyya, Measuring the Shared Fate of IGP Engineering and Interdomain Traffic, Proceedings of the 13TH IEEE International Conference on Network Protocols (ICNP'05), p.236-245, November 06-09, 2005 [doi>10.1109/ICNP.2005.22]
• 5: R. Ahuja, T. Magnanti, and J. Orlin. Network Flows. Prentice Hall, 1993.
• 6: David Applegate , Lee Breslau , Edith Cohen, Coping with network failures: routing strategies for optimal demand oblivious restoration, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 7: 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]
• 8: D. Awduche , A. Chiu , A. Elwalid , I. Widjaja , X. Xiao, Overview and Principles of Internet Traffic Engineering, RFC Editor, 2002
• 9: D. O. Awduche. MPLS and traffic engineering in IP networks. IEEE Communication Magazine, pages 42--47, Dec. 1999.
• 10: Yossi Azar , Edith Cohen , Amos Fiat , Haim Kaplan , Harald Racke, Optimal oblivious routing in polynomial time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780599]
• 11: Nikhil Bansal , Avrim Blum , Shuchi Chawla , Adam Meyerson, Online oblivious routing, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777420]
• 12: D. Bertsekas. Nonlinear Programming. Athena Scientific, 2nd edition edition, 1999.
• 13: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 14: D. Bertsimas, D. Pachamanova, and M. Sim. Robust linear optimization under general norms. Operations Research Letters, 2004.
• 15: T. Bressoud, R. Rastogi, and M. Smith. Optimal configuration for BGP route selection. In Proceedings of IEEE INFOCOM '03, San Francisco, CA, Apr. 2003.
• 16: T. C. Bressoud, R. Rastogi, and M. A. Smith. Optimal configuration for BGP route selection. In Proceedings of IEEE INFOCOM '02, New York, NY, June 2002.
• 17: M. Caesar and J. Rexford. BGP routing policies in ISP networks. IEEE Network Magazine, Nov. 2005.
• 18: ILOG CPLEX: optimization software. http://www.ilog.com/products/cplex/.
• 19: A. Elwalid, C. Jin, S. Low, and I. Widjaja. MATE: MPLS adaptive traffic engineering. In Proceedings of IEEE INFOCOM '01, Anchorage, AK, Apr. 2001.
• 20: Nick Feamster , Jay Borkenhagen , Jennifer Rexford, Guidelines for interdomain traffic engineering, ACM SIGCOMM Computer Communication Review, v.33 n.5, October 2003 [doi>10.1145/963985.963988]
• 21: N. Feamster and J. Rexford. Network-wide BGP route prediction for traffic engineering. In Proceedings of ITCOM, Boston, MA, Aug. 2002.
• 22: Nick Feamster , Jared Winick , Jennifer Rexford, A model of BGP routing for network engineering, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 23: V. Firoiu, I. Yeom, and X. Zhang. A framework for practical performance evaluation and traffic engineering in IP networks. In IEEE ICT 2001, 2001.
• 24: B. Fortz, J. Rexford, and M. Thorup. Traffic engineering with traditional IP routing protocols. IEEE Communication Magazine, Oct. 2002.
• 25: B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In Proceedings of IEEE INFOCOM '00, Tel Aviv, Israel, Mar. 2000.
• 26: Srikanth Kandula , Dina Katabi , Bruce Davie , Anna Charny, Walking the tightrope: responsive yet stable traffic engineering, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 27: M. Kodialam, T. V. Lakshman, and S. Sengupta. Efficient and robust routing of highly variable traffic. In Proceedings of Third Workshop on Hot Topics in Networks (HotNets-III), San Diego, CA, Nov. 2004.
• 28: Y. Li, J. Harms, and R. Holte. A simple method for balancing network utilization and quality of routing. In Proceedings of ICCCN, San Diego, CA, 2005.
• 29: Z. Ma, H. Wang, A. Krishnamurthy, A. Silberschatz, and Y. R. Yang. Achieving robust and optimal traffic engineering in current Internet. Technical report, Yale University, 2006.
• 30: Lili Qiu , Yang Richard Yang , Yin Zhang , Scott Shenker, On selfish routing in internet-like environments, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863974]
• 31: 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
• 32: Jennifer Rexford , Jia Wang , Zhen Xiao , Yin Zhang, BGP routing stability of popular destinations, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637232]
• 33: M. Roughan. First order characterization of Internet traffic matrices. In Proceedings of the 55th Session of the International Statistics Institute, Sydney, Australia, Apr. 2005.
• 34: Matthew Roughan , Mikkel Thorup , Yin Zhang, Traffic engineering with estimated traffic matrices, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948237]
• 35: N. Spring, R. Mahajan, and D. Wetherall. Rocketfuel: An ISP topology mapping engine. Available from http://www.cs.washington.edu/research/networking/rocketfuel/.
• 36: A. Sridharan, R. Guerin, and C. Diot. Achieving near optimal traffic engineering solutions in current OSPF/ISIS networks. In Proceedings of IEEE INFOCOM '03, San Francisco, CA, Apr. 2003.
• 37: Renata Teixeira , Sharad Agarwal , Jennifer Rexford, BGP routing changes: merging views from two ISPs, ACM SIGCOMM Computer Communication Review, v.35 n.5, October 2005 [doi>10.1145/1096536.1096548]
• 38: R. Teixeira, N. Duffield, J. Rexford, and M. Roughan. Traffic matrix reloaded: Impact of routing changes. In Proceedings of Passive and Active Measurement, Mar. 2005.
• 39: Renata Teixeira , Aman Shaikh , Tim Griffin , Geoffrey M. Voelker, Network sensitivity to hot-potato disruptions, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 40: Renata Teixeira , Aman Shaikh , Tim Griffin , Jennifer Rexford, Dynamics of hot-potato routing in IP networks, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 41: S. Uhlig and O. Bonaventure. Implications of interdomain traffic characteristics on traffic engineering. In J. Crowcroft and A. Feldmann, editors, Special issue on traffic engineering of European Transactions on Telecommunications. 2002.
• 42: L. G. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11(7):350--361, 1982.
• 43: Hao Wang , Haiyong Xie , Yang Richard Yang , Avi Silberschatz Silberschatz , Li Erran Li , Yanbin Liu, Stable Egress Route Selection for Interdomain Traffic Engineering: Model and Analysis, Proceedings of the 13TH IEEE International Conference on Network Protocols (ICNP'05), p.16-29, November 06-09, 2005 [doi>10.1109/ICNP.2005.39]
• 44: Z. Wang, Y. Wang, and L. Zhang. Internet traffic engineering without full mesh overlaying. In Proceedings of IEEE INFOCOM '01, Anchorage, AK, Apr. 2001.
• 45: J. Wu, Z. M. Mao, J. Rexford, and J. Wang. Finding a needle in a haystack: Pinpointing significant BGP routing changes in an IP network. In Proceedings of USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI '05), San Francisco, CA, May 2005.
• 46: X. Xiao, A. Hannan, B. Bailey, and L. Ni. Traffic engineering with MPLS in the Internet. IEEE Network Magazine, pages 28--33, Mar. 2000.
• 47: Kuai Xu , Zhi-Li Zhang , Supratik Bhattacharyya, Profiling internet backbone traffic: behavior models and applications, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 48: T. Ye, H. Kaur, S. Kalyanaraman, K. Vastola, and S. Yadav. Optimization of OSPF weights using online simulation. In Proceedings of International Workshop on Quality of Service (IWQoS)), 2002.
• 49: Chun Zhanga , Jim Kurosea , Don Towsley , Zihui Ge , Yong Liu, Optimal Routing with Multiple Traffic Matrices Tradeoff between Average andWorst Case Performance, Proceedings of the 13TH IEEE International Conference on Network Protocols (ICNP'05), p.215-224, November 06-09, 2005 [doi>10.1109/ICNP.2005.30]
• 50: C. Zhang, Y. Liu, W. Gong, J. Kurose, R. Moll, and D. Towsley. On optimal routing with multiple traffic matrices. In Proceedings of IEEE INFOCOM '05, Miami, FL, Apr. 2005.
• 51: Yin Zhang , Nick Duffield, On the constancy of internet path properties, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505228]
• 52: Finding Critical Traffic Matrices, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.188-197, June 28-July 01, 2005 [doi>10.1109/DSN.2005.51]
• 53: Yin Zhang , Matthew Roughan , Carsten Lund , David Donoho, An information-theoretic approach to traffic matrix estimation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863990]
• 54: R. Zhang-Shen and N. McKeown. Designing a predictable Internet backbone network. In Proceedings of Third Workshop on Hot Topics in Networks (HotNets-III), San Diego, CA, Nov. 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

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

General Terms:
Algorithms, Design, Management, Performance, Reliability

Keywords:
COPE, oblivious routing, optimization, traffic engineering, unpredictable traffic