Article

Free access

COPE: traffic engineering in dynamic networks

Authors:

Yang Richard Yang,

Albert GreenbergAuthors Info & Claims

SIGCOMM '06: Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications

August 2006

Pages 99 - 110

https://doi.org/10.1145/1159913.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

Zhang YHan NZhu TZhang JYe MDou SGuo Z(2024)Prophet: Traffic Engineering-Centric Traffic Matrix PredictionIEEE/ACM Transactions on Networking10.1109/TNET.2023.329309832:1(822-832)Online publication date: Feb-2024
https://doi.org/10.1109/TNET.2023.3293098
Denis MYao YHatch AZhang QLim CZhang SSugrue KKwok HFernandez MLapukhov PHebbani SNagarajan GBaldonado OGao LZhang YSchulzrinne HKohler EMaltz DMisra V(2023)EBB: Reliable and Evolvable Express Backbone Network in MetaProceedings of the ACM SIGCOMM 2023 Conference10.1145/3603269.3604860(346-359)Online publication date: 10-Sep-2023
https://dl.acm.org/doi/10.1145/3603269.3604860
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
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
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 ...
Read More
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 ...
Read More
RFC 4804: Aggregation of Resource ReSerVation Protocol (RSVP) Reservations over MPLS TE/DS-TE Tunnels
Read More

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

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

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 August 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGCOMM06

Sponsor:

SIGCOMM06: ACM SIGCOMM 2006 Conference

September 11 - 15, 2006

Pisa, Italy

Acceptance Rates

Overall Acceptance Rate 554 of 3,547 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

205
Total Citations
View Citations
1,783
Total Downloads

Downloads (Last 12 months)107
Downloads (Last 6 weeks)10

Other Metrics

View Author Metrics

Citations

Cited By

Zhang YHan NZhu TZhang JYe MDou SGuo Z(2024)Prophet: Traffic Engineering-Centric Traffic Matrix PredictionIEEE/ACM Transactions on Networking10.1109/TNET.2023.329309832:1(822-832)Online publication date: Feb-2024
https://doi.org/10.1109/TNET.2023.3293098
Denis MYao YHatch AZhang QLim CZhang SSugrue KKwok HFernandez MLapukhov PHebbani SNagarajan GBaldonado OGao LZhang YSchulzrinne HKohler EMaltz DMisra V(2023)EBB: Reliable and Evolvable Express Backbone Network in MetaProceedings of the ACM SIGCOMM 2023 Conference10.1145/3603269.3604860(346-359)Online publication date: 10-Sep-2023
https://dl.acm.org/doi/10.1145/3603269.3604860
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
Liang X(2023)Auction Pricing for Bandwidth across Multiple Datacenters with Traffic Engineering2023 IEEE International Conference on Control, Electronics and Computer Technology (ICCECT)10.1109/ICCECT57938.2023.10141016(1216-1224)Online publication date: 28-Apr-2023
https://doi.org/10.1109/ICCECT57938.2023.10141016
Weichlein TZhang SLi PZhang X(2023)Data Flow Control for Network Load Balancing in IEEE Time Sensitive Networks for AutomationIEEE Access10.1109/ACCESS.2023.3243286(1-1)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3243286
Kinsey STuck WSinha ANguyen T(2023)An Exploration of Poisoning Attacks on Data-Based Decision MakingDecision and Game Theory for Security10.1007/978-3-031-26369-9_12(231-252)Online publication date: 9-Feb-2023
https://doi.org/10.1007/978-3-031-26369-9_12
Teh MWu ZGlick MRumley SGhobadi MBergman K(2022)Performance trade-offs in reconfigurable networks for HPCJournal of Optical Communications and Networking10.1364/JOCN.45176014:6(454)Online publication date: 11-May-2022
https://doi.org/10.1364/JOCN.451760
Schmid SSchou MSrba JVanerio JBianchi GMei A(2022)R-MPLSProceedings of the 18th International Conference on emerging Networking EXperiments and Technologies10.1145/3555050.3569140(276-292)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3555050.3569140
Jiang CLi ZRao STawarmalani MBianchi GMei A(2022)FlexileProceedings of the 18th International Conference on emerging Networking EXperiments and Technologies10.1145/3555050.3569119(110-125)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3555050.3569119
Poutievski LMashayekhi OOng JSingh ATariq MWang RZhang JBeauregard VConner PGribble SKapoor RKratzer SLi NLiu HNagaraj KOrnstein JSawhney SUrata RVicisano LYasumura KZhang SZhou JVahdat AKuipers FOrda A(2022)Jupiter evolvingProceedings of the ACM SIGCOMM 2022 Conference10.1145/3544216.3544265(66-85)Online publication date: 22-Aug-2022
https://dl.acm.org/doi/10.1145/3544216.3544265
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents