research-article

WCMP: weighted cost multipathing for improved fairness in data centers

Authors:

Malveeka Tewari,

Leon Poutievski,

Amin VahdatAuthors Info & Claims

EuroSys '14: Proceedings of the Ninth European Conference on Computer Systems

Article No.: 5, Pages 1 - 14

https://doi.org/10.1145/2592798.2592803

Published: 14 April 2014 Publication History

Abstract

Data Center topologies employ multiple paths among servers to deliver scalable, cost-effective network capacity. The simplest and the most widely deployed approach for load balancing among these paths, Equal Cost Multipath (ECMP), hashes flows among the shortest paths toward a destination. ECMP leverages uniform hashing of balanced flow sizes to achieve fairness and good load balancing in data centers. However, we show that ECMP further assumes a balanced, regular, and fault-free topology, which are invalid assumptions in practice that can lead to substantial performance degradation and, worse, variation in flow bandwidths even for same size flows.

We present a set of simple algorithms that achieve Weighted Cost Multipath (WCMP) to balance traffic in the data center based on the changing network topology. The state required for WCMP is already disseminated as part of standard routing protocols and it can be readily implemented in the current switch silicon without any hardware modifications. We show how to deploy WCMP in a production OpenFlow network environment and present experimental and simulation results to show that variation in flow bandwidths can be reduced by as much as 25X by employing WCMP relative to ECMP.

References

[1]

J. H. Ahn, N. Binkert, A. Davis, M. McLaren, and R. S. Schreiber. HyperX: Topology, Routing, and Packaging of Efficient Large-Scale Networks. In Proc. of SC, November 2009.

Digital Library

[2]

M. Al-Fares, A. Loukissas, and A. Vahdat. A Scalable, Commodity Data Center Network Architecture. In Proc. of ACM SIGCOMM, August 2008.

Digital Library

[3]

M. Al-Fares, S. Radhakrishnan, B. Raghavan, N. Huang, and A. Vahdat. Hedera: Dynamic Flow Scheduling for Data Center Networks. In Proc. of Usenix NSDI, April 2010.

Digital Library

[4]

D. Applegate, L. Breslau, and E. Cohen. Coping with Network Failures: Routing Strategies for Optimal Demand Oblivious Restoration. In Proc. of SIGMETRICS, June 2004.

Digital Library

[5]

L. A. Barroso, J. Dean, and U. Hölzle. Web Search for a Planet: The Google Cluster Architecture. IEEE Micro, Volume 23, March-April 2003.

Digital Library

[6]

Broadcom's OpenFlow Data Plane Abstraction. http://www.broadcom.com/products/Switching/Software-Defined-Networking-Solutions/OF-DPA-Software.

[7]

T. Benson, A. Akella, and D. A. Maltz. Network Traffic Characteristics of Data Centers in the Wild. In Proc. of ACM IMC, November 2010.

Digital Library

[8]

M. Chowdhury, M. Zaharia, J. Ma, M. I. Jordan, and I. Stoica. Managing Data Transfers in Computer Clusters with Orchestra. In Proc. of ACM SIGCOMM, August 2011.

Digital Library

[9]

T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 2nd edition, 2001.

Digital Library

[10]

A. R. Curtis, W. Kim, and P. Yalagandula. Mahout: Low-Overhead Datacenter Traffic Management using End-Host-Based Elephant Detection. In Proc. of IEEE INFOCOM, April 2011.

[11]

A. R. Curtis, J. C. Mogul, J. Tourrilhes, P. Yalagandula, P. Sharma, and S. Banerjee. DevoFlow: Scaling Flow Management For High-Performance Networks. In Proc. of ACM SIGCOMM, August 2011.

Digital Library

[12]

J. Dean and S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. In Proc. of Usenix OSDI, December 2004.

Digital Library

[13]

Gnu Linear Programming Kit. http://www.gnu.org/software/glpk.

[14]

A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta. VL2: A Scalable and Flexible Data Center Network. In Proc. of ACM SIGCOMM, August 2009.

Digital Library

[15]

C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, and S. Lu. BCube: A High Performance, Server-centric Network Architecture for Modular Data Centers. In Proc. of ACM SIGCOMM, August 2009.

Digital Library

[16]

B. Heller, S. Seetharaman, P. Mahadevan, Y. Yiakoumis, P. Sharma, S. Banerjee, and N. McKeown. ElasticTree: Saving Energy In Data Center Networks. In Proc. of Usenix NSDI, April 2010.

Digital Library

[17]

C. Hopps. Analysis of an Equal-Cost Multi-Path Algorithm. RFC 2992, IETF, November 2000.

Digital Library

[18]

HP SDN Ecosystem. http://h17007.www1.hp.com/us/en/networking/solutions/technology/sdn/.

[19]

MPTCP htsim implementation. http://nrg.cs.ucl.ac.uk/mptcp/implementation.html.

[20]

J. Kim and W. J. Dally. Flattened Butterfly: A Cost-Efficient Topology for High-Radix Networks. In ISCA, June 2007.

Digital Library

[21]

M. Kodialam, T. V. Lakshman, and S. Sengupta. Efficient and Robust Routing of Highly Variable Traffic. In Proc. of ACM HotNets, November 2004.

[22]

T. Koponen, M. Casado, N. Gude, J. Stribling, L. Poutievski, M. Zhu, R. Ramanathan, Y. Iwata, H. Inoue, T. Hama, and S. Shenker. Onix: A Distributed Control Platform for Large-scale Production Networks. In Proc. of Usenix OSDI, October 2010.

Digital Library

[23]

V. Liu, D. Halperin, A. Krishnamurhty, and T. Anderson. F10: A Fault-Tolerant Engineered Network. In Proc. of Usenix NSDI, April 2013.

Digital Library

[24]

Memcached. http://www.memcached.org.

[25]

J. Moy. OSPF Version 2. RFC 2328, Internet Engineering Task Force, April 1998.

[26]

MPLS-TE. http://blog.ioshints.info/2007/02/unequal-cost-load-sharing.html.

[27]

Openflow. www.openflow.org.

[28]

C. Raiciu, S. Barre, C. Pluntke, A. Greenhalgh, D. Wischik, and M. Handley. Improving Datacenter Performance and Robustness with Multipath TCP. In Proc. of ACM SIGCOMM, August 2011.

Digital Library

[29]

C. Villamizar. OSPF Optimized Multipath (OSPF-OMP), draft-ietf-ospf-omp-02, February 1999.

[30]

H. Wu, G. Lu, D. Li, C. Guo, and Y. Zhang. MDCube: A High Performance Network Structure for Modular Data Center Interconnection. In Proc. of ACM CoNEXT, December 2009.

Digital Library

[31]

X. Xiao, A. Hannan, and B. Bailey. Traffic Engineering with MPLS in the Internet. IEEE Network Magazine, 2000.

Digital Library

[32]

Y. Zhang and Z. Ge. Finding Critical Traffic Matrices. In Proc. of DSN, June 2005.

Digital Library

Cited By

Cao PCheng WZhao SXiong Y(2024)Network Load Balancing with Parallel Flowlets for AI Training ClustersProceedings of the 2024 SIGCOMM Workshop on Networks for AI Computing10.1145/3672198.3673794(18-25)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3672198.3673794
Chen CYe JGao YLiu SXu Y(2024)HF^2T: Host-Based Flowlet Fine-Tuning for RDMA Load BalancingProceedings of the 8th Asia-Pacific Workshop on Networking10.1145/3663408.3663410(9-15)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.1145/3663408.3663410
Li JGong HDe Marchi FGong ALei YBai WXia YSekar VYu MSeneviratne AVeitch D(2024)Uniform-Cost Multi-Path Routing for Reconfigurable Data Center NetworksProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672245(433-448)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672245
Show More Cited By

Index Terms

WCMP: weighted cost multipathing for improved fairness in data centers
1. Networks
  1. Network protocols

Recommendations

Pathlet routing
SIGCOMM '09: Proceedings of the ACM SIGCOMM 2009 conference on Data communication

We present a new routing protocol, pathlet routing, in which networks advertise fragments of paths, called pathlets, that sources concatenate into end-to-end source routes. Intuitively, the pathlet is a highly flexible building block, capturing policy ...
BGP-XM: BGP eXtended Multipath for transit Autonomous Systems

Multipath interdomain routing has been proposed to enable flexible traffic engineering for transit Autonomos Systems (ASes). Yet, there is a lack of solutions providing maximal path diversity and backwards compatibility at the same time. The BGP-XM (...
Hash-based routing for scalable datacenters
ANCS '09: Proceedings of the 5th ACM/IEEE Symposium on Architectures for Networking and Communications Systems

Most datacenter networks are based on specialized edge-core topologies, which are costly to build, difficult to maintain and consume too much power. We propose enhancements to layer-two (L2) Ethernet switches to enable multipath L2 routing in scalable ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EuroSys '14: Proceedings of the Ninth European Conference on Computer Systems

April 2014

388 pages

ISBN:9781450327046

DOI:10.1145/2592798

General Chairs:
Dick Bultermann
CWI
,
Herbert Bos
Vrije Universiteit Amsterdam
,
Program Chairs:
Ant Rowstron
Microsoft Research Cambridge
,
Peter Druschel
MPI SWS

Copyright © 2014 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

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 April 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EuroSys 2014

Sponsor:

SIGOPS

EuroSys 2014: Ninth Eurosys Conference 2014

April 14 - 16, 2014

Amsterdam, The Netherlands

Acceptance Rates

EuroSys '14 Paper Acceptance Rate 27 of 147 submissions, 18%;

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

172
Total Citations
View Citations
1,366
Total Downloads

Downloads (Last 12 months)121
Downloads (Last 6 weeks)9

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cao PCheng WZhao SXiong Y(2024)Network Load Balancing with Parallel Flowlets for AI Training ClustersProceedings of the 2024 SIGCOMM Workshop on Networks for AI Computing10.1145/3672198.3673794(18-25)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3672198.3673794
Chen CYe JGao YLiu SXu Y(2024)HF^2T: Host-Based Flowlet Fine-Tuning for RDMA Load BalancingProceedings of the 8th Asia-Pacific Workshop on Networking10.1145/3663408.3663410(9-15)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.1145/3663408.3663410
Li JGong HDe Marchi FGong ALei YBai WXia YSekar VYu MSeneviratne AVeitch D(2024)Uniform-Cost Multi-Path Routing for Reconfigurable Data Center NetworksProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672245(433-448)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672245
Gui FWang SLi DChen LGao KMin CWang YSekar VYu MSeneviratne AVeitch D(2024)RedTE: Mitigating Subsecond Traffic Bursts with Real-time and Distributed Traffic EngineeringProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672231(71-85)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672231
Liu SGao YChen ZYe JXu HLiang FYan WTian ZSun QGuo ZXu Y(2024)Halflife: An Adaptive Flowlet-based Load Balancer with Fading Timeout in Data Center NetworksProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650062(66-81)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650062
Liu ZZhao YFan ZYang TLi XZhang RYang KJiang ZZhong ZHuang YLiu CHu JXie GCui B(2024)BurstBalancer: Do Less, Better Balance for Large-Scale Data Center TrafficIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.329545435:6(932-949)Online publication date: Jun-2024
https://doi.org/10.1109/TPDS.2023.3295454
Medagliani PMartin SMagnouche YLeguay JDecraene B(2024)Distributed Tactical TE With Segment RoutingIEEE Transactions on Network and Service Management10.1109/TNSM.2024.342468421:5(4974-4987)Online publication date: Oct-2024
https://doi.org/10.1109/TNSM.2024.3424684
Zhang YHuang HAbdelmoniem AZeng GZheng CQue XWang WXu K(2024)FLAIR: A Fast and Low-Redundancy Failure Recovery Framework for Inter Data Center NetworkIEEE Transactions on Cloud Computing10.1109/TCC.2024.339373512:2(737-749)Online publication date: Apr-2024
https://doi.org/10.1109/TCC.2024.3393735
Mahfod KBogatyrev V(2024)Q- Learning Based Adaptive Multipath Routing Algorithm for Data Centre Networks2024 International Russian Automation Conference (RusAutoCon)10.1109/RusAutoCon61949.2024.10694010(960-966)Online publication date: 8-Sep-2024
https://doi.org/10.1109/RusAutoCon61949.2024.10694010
Nakamura REbisawa KHayashi HFujiwara TOkuzawa T(2024)Exploiting SRv6 for Stateless and Per-Connection-Consistent Load BalancingIEEE Access10.1109/ACCESS.2024.341301612(83525-83537)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3413016
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 Table of Contents