article

COPE: traffic engineering in dynamic networks

Authors:

Yang Richard Yang,

Albert GreenbergAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 36, Issue 4

Pages 99 - 110

https://doi.org/10.1145/1151659.1159926

Published: 11 August 2006 Publication History

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]

S. Agarwal, C.-N. Chuah, S. Bhattacharyya, and C. Diot. The impact of BGP dynamics on intra-domain traffic. In Proceedings of Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), New York, NY, June 2004.

Digital Library

[4]

S. Agarwal, A. Nucci, and S. Bhattacharyya. Measuring the shared fate of IGP engineering and interdomain traffic. In Proceedings of the 13th International Conference on Network Protocols (ICNP) '05, Boston, MA, Nov. 2005.

Digital Library

[5]

R. Ahuja, T. Magnanti, and J. Orlin. Network Flows. Prentice Hall, 1993.

Digital Library

[6]

D. Applegate, L. Breslau, and E. Cohen. Coping with network failures: Routing strategies for optimal demand oblivious restoration. In Proceedings of Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), New York, NY, June 2004.

Digital Library

[7]

D. Applegate and E. Cohen. Making intra-domain routing robust to changing and uncertain traffic demands: Understanding fundamental tradeoffs. In Proceedings of ACM SIGCOMM '03, Karlsruhe, Germany, Aug. 2003.

Digital Library

[8]

D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiao. Overview and Principles of Internet Traffic Engineering, RFC 3272, May 2002.

Digital Library

[9]

D. O. Awduche. MPLS and traffic engineering in IP networks. IEEE Communication Magazine, pages 42--47, Dec. 1999.

Digital Library

[10]

Y. Azar, E. Choen, A. Fiat, H. Kaplan, and H. Racke. Optimal oblivious routing in polynomial time. In Proceedings of the 35th Annual Symposium on Theory of Computing, 2003.

Digital Library

[11]

N. Bansal, A. Blum, S. Chawla, and A. Meyerson. Online oblivious routing. In Proceedings of ACM Symposium in Parallelism in Algorithms and Architectures (SPAA), 2003.

Digital Library

[12]

D. Bertsekas. Nonlinear Programming. Athena Scientific, 2nd edition edition, 1999.

[13]

D. Bertsekas and R. Gallager. Data Networks. Prentice-Hall, Second Edition, 1992.

Digital Library

[14]

D. Bertsimas, D. Pachamanova, and M. Sim. Robust linear optimization under general norms. Operations Research Letters, 2004.

Digital Library

[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.

Digital Library

[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]

N. Feamster, J. Borkenhagen, and J. Rexford. Guidelines for interdomain traffic engineering. ACM SIGCOMM Computer Communications Review, Oct. 2003.

Digital Library

[21]

N. Feamster and J. Rexford. Network-wide BGP route prediction for traffic engineering. In Proceedings of ITCOM, Boston, MA, Aug. 2002.

[22]

N. Feamster, J. Winick, and J. Rexford. A model of BGP routing for network engineering. In Proceedings of Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), pages 331--342, New York, NY, June 2004. ACM Press.

Digital Library

[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.

Digital Library

[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]

S. Kandula, D. Katabi, B. Davie, and A. Charny. Walking the tightrope: Responsive yet stable traffic engineering. In Proceedings of ACM SIGCOMM '05, Philadelphia, PA, Aug. 2005.

Digital Library

[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]

L. Qiu, Y. R. Yang, Y. Zhang, and S. Shenker. Selfish routing in Internet-like environments. In Proceedings of ACM SIGCOMM '03, Karlsruhe, Germany, Aug. 2003.

Digital Library

[31]

H. Racke. Minimizing congestion in general networks. In Proceedings of the 43rd Annual Symposium on Foudations of Computer Science, Oct. 2002.

Digital Library

[32]

J. Rexford, J. Wang, Z. Xiao, and Y. Zhang. BGP routing stability of popular destinations. In Proceedings of Internet Measurement Workshop, Marseille, France, Nov. 2002.

Digital Library

[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]

M. Roughan, M. Thorup, and Y. Zhang. Traffic engineering with estimated traffic matrices. In Proceedings of the Internet Measurement Conference, Miami, FL, Oct. 2003.

Digital Library

[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]

R. Teixeira, S. Agarwal, and J. Rexford. BGP routing changes: Merging views from two ISPs. ACM SIGCOMM Computer Communications Review, Oct. 2005.

Digital Library

[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.

Digital Library

[39]

R. Teixeira, T. Griffin, A. Shaikh, and G. Voelker. Network sensitivity to hot-potato disruptions. In Proceedings of ACM SIGCOMM '04, Portland, OR, Aug. 2004.

Digital Library

[40]

R. Teixeira, A. Shaikh, T. Griffin, and J. Rexford. Dynamics of hot-potato routing in IP networks. In Proceedings of Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), New York, NY, June 2004.

Digital Library

[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.

Digital Library

[43]

H. Wang, H. Xie, Y. R. Yang, L. E. Li, Y. Liu, and A. Silberschatz. Stable egress route selection for interdomain traffic engineering: Model and analysis. In Proceedings of the 13th International Conference on Network Protocols (ICNP) '05, Boston, MA, Nov. 2005.

Digital Library

[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.

Digital Library

[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.

Digital Library

[47]

K. Xu, Z.-L. Zhang, and S. Bhattacharya. Profiling Internet backbone traffic: Behavior models and applications. In Proceedings of ACM SIGCOMM '05, Philadelphia, PA, Aug. 2005.

Digital Library

[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]

C. Zhang, Z. Ge, J. Kurose, Y. Liu, and D. Towsley. Optimal routing with multiple traffic matrices: Tradeoff between average case and worst case performance. In Proceedings of the 13th International Conference on Network Protocols (ICNP) '05, Boston, MA, Nov. 2005.

Digital Library

[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]

Y. Zhang, N. Duffield, V. Paxson, and S. Shenker. On the constancy of Internet path properties. In Proceedings of Internet Measurement Workshop 2001, San Francisco, CA, Nov. 2001.

Digital Library

[52]

Y. Zhang and Z. Ge. Finding critical traffic matrices. In Proceedings of DSN '05, Yokohama, Japan, June 2005.

Digital Library

[53]

Y. Zhang, M. Roughan, C. Lund, and D. L. Donoho. An information-theoretic approach to traffic matrix estimation. In Proceedings of ACM SIGCOMM '03, Karlsruhe, Germany, Aug. 2003.

Digital Library

[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.

Cited By

Dinh LQuang PLeguay J(2025)Safe load balancing in software-defined-networkingComputer Communications10.1016/j.comcom.2024.107985229(107985)Online publication date: Jan-2025
https://doi.org/10.1016/j.comcom.2024.107985
Teh MZhao SCao PBergman K(2023)Enabling Quasi-Static Reconfigurable Networks With Robust Topology EngineeringIEEE/ACM Transactions on Networking10.1109/TNET.2022.321053431:3(1056-1070)Online publication date: Jun-2023
https://doi.org/10.1109/TNET.2022.3210534
Lai ZLi HWang YWu QDeng YLiu JLi YWu J(2023)Achieving Resilient and Performance-Guaranteed Routing in Space-Terrestrial Integrated NetworksIEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10229104(1-10)Online publication date: 17-May-2023
https://doi.org/10.1109/INFOCOM53939.2023.10229104
Show More Cited By

Index Terms

COPE: traffic engineering in dynamic networks
1. Networks
  1. Network protocols
  2. Network services
    1. Network management

Recommendations

COPE: traffic engineering in dynamic networks
SIGCOMM '06: Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications

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 ...
Making routing robust to changing traffic demands: algorithms and evaluation

Intra-domain traffic engineering can significantly enhance the performance of large IP backbone networks. Two important components of traffic engineering are understanding the traffic demands and configuring the routing protocols. These two components ...
RFC 4804: Aggregation of Resource ReSerVation Protocol (RSVP) Reservations over MPLS TE/DS-TE Tunnels

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 36, Issue 4

Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications

October 2006

445 pages

ISSN:0146-4833

DOI:10.1145/1151659

Issue’s Table of Contents

SIGCOMM '06: Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications
September 2006
458 pages
ISBN:1595933085
DOI:10.1145/1159913
General Chair:
Luigi Rizzo
Università di Pisa, Italy
,
Program Chairs:
Tom Anderson
University of Washington, USA
,
Nick McKeown
Stanford University, USA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 August 2006

Published in SIGCOMM-CCR Volume 36, Issue 4

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

210
Total Citations
View Citations
1,852
Total Downloads

Downloads (Last 12 months)135
Downloads (Last 6 weeks)29

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dinh LQuang PLeguay J(2025)Safe load balancing in software-defined-networkingComputer Communications10.1016/j.comcom.2024.107985229(107985)Online publication date: Jan-2025
https://doi.org/10.1016/j.comcom.2024.107985
Teh MZhao SCao PBergman K(2023)Enabling Quasi-Static Reconfigurable Networks With Robust Topology EngineeringIEEE/ACM Transactions on Networking10.1109/TNET.2022.321053431:3(1056-1070)Online publication date: Jun-2023
https://doi.org/10.1109/TNET.2022.3210534
Lai ZLi HWang YWu QDeng YLiu JLi YWu J(2023)Achieving Resilient and Performance-Guaranteed Routing in Space-Terrestrial Integrated NetworksIEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10229104(1-10)Online publication date: 17-May-2023
https://doi.org/10.1109/INFOCOM53939.2023.10229104
Ye MZhang JGuo ZChao H(2023)LARRI: Learning-based Adaptive Range Routing for Highly Dynamic Traffic in WANsIEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10228904(1-10)Online publication date: 17-May-2023
https://doi.org/10.1109/INFOCOM53939.2023.10228904
Weichlein TZhang SLi PZhang X(2023)Data Flow Control for Network Load Balancing in IEEE Time Sensitive Networks for AutomationIEEE Access10.1109/ACCESS.2023.324328611(14044-14060)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3243286
Zhang C(2023)Problem characterization of unique shortest path routingComputers & Industrial Engineering10.1016/j.cie.2023.109110178(109110)Online publication date: Apr-2023
https://doi.org/10.1016/j.cie.2023.109110
Singh RBjørner NKrishnaswamy U(2022)Traffic engineeringProceedings of the Symposium on SDN Research10.1145/3563647.3563652(50-58)Online publication date: 19-Oct-2022
https://dl.acm.org/doi/10.1145/3563647.3563652
Dong XZhao LZhou XLi KGuo DQiu T(2022)An Online Cost-Efficient Transmission Scheme for Information-Agnostic Traffic in Inter-Datacenter NetworksIEEE Transactions on Cloud Computing10.1109/TCC.2019.294168810:1(202-215)Online publication date: 1-Jan-2022
https://doi.org/10.1109/TCC.2019.2941688
Perrot NBenhamiche ACarlinet YGourdin E(2021)Future NetworksResearch Anthology on Developing and Optimizing 5G Networks and the Impact on Society10.4018/978-1-7998-7708-0.ch028(677-706)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-7708-0.ch028
Hwang DJaillet PManshadi V(2021)Online Resource Allocation Under Partially Predictable DemandOperations Research10.1287/opre.2020.201769:3(895-915)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1287/opre.2020.2017
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents