article

Cloud control with distributed rate limiting

Authors:

Barath Raghavan,

Kashi Vishwanath,

Sriram Ramabhadran,

Alex C. SnoerenAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 37, Issue 4

Pages 337 - 348

https://doi.org/10.1145/1282427.1282419

Published: 27 August 2007 Publication History

Abstract

Today's cloud-based services integrate globally distributed resources into seamless computing platforms. Provisioning and accounting for the resource usage of these Internet-scale applications presents a challenging technical problem. This paper presents the design and implementation of distributed rate limiters, which work together to enforce a global rate limit across traffic aggregates at multiple sites, enabling the coordinated policing of a cloud-based service's network traffic. Our abstraction not only enforces a global limit, but also ensures that congestion-responsive transport-layer flows behave as if they traversed a single, shared limiter. We present two designs - one general purpose, and one optimized for TCP - that allow service operators to explicitly trade off between communication costs and system accuracy, efficiency, and scalability. Both designs are capable of rate limiting thousands of flows with negligible overhead (less than 3% in the tested configuration). We demonstrate that our TCP-centric design is scalable to hundreds of nodes while robust to both loss and communication delay, making it practical for deployment in nationwide service providers.

References

[1]

Packeteer. http://www.packeteer.com.

[2]

Akamai Technologies. Personal communication, June 2007.

[3]

Amazon. Elastic compute cloud. http://aws.amazon.com/ec2.

[4]

G. Appenzeller, I. Keslassy, and N. McKeown. Sizing router buffers. In Proceedings of ACM SIGCOMM, 2004.

Digital Library

[5]

B. Babcock and C. Olston. Distributed top-k monitoring. In Proceedings of ACM SIGMOD, 2003.

Digital Library

[6]

D. Bertsekas and R. Gallager. Data Networks. Prentice Hall, 1987.

Digital Library

[7]

S. Bhatnagar and B. Nath. Distributed admission control to support guaranteed services in core-stateless networks. In Proceedings of IEEE INFOCOM, 2003.

[8]

D. F. Carr. How Google works. Baseline Magazine, July 2006.

[9]

G. Carraro and F. Chong. Software as a service (SaaS): An enterprise perspective. MSDN Solution Architecture Center, Oct. 2006.

[10]

A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic algorithms for replicated database maintenance. In Proceedings of ACM PODC, 1987.

Digital Library

[11]

A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. In Proceedings of ACM SIGCOMM, 1989.

Digital Library

[12]

M. Dilman and D. Raz. Efficient reactive monitoring. In Proceedings of IEEE INFOCOM, 2001.

[13]

W. Feng, K. Shin, D. Kandlur, and D. Saha. The blue active queue management algorithms. IEEE/ACM Transactions on Networking, 10(4), 2002.

Digital Library

[14]

S. Floyd and V. Jacobson. Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on Networking, 1(4), 1993.

Digital Library

[15]

S. Floyd and V. Jacobson. Link-sharing and resource management models for packet networks. IEEE/ACM Transactions on Networking, 3(4), 1995.

Digital Library

[16]

I. Gupta, A.-M. Kermarrec, and A. J. Ganesh. Efficient epidemic-style protocols for reliable and scalable multicast. In Proceedings of IEEE SRDS, 2002.

Digital Library

[17]

D. Hinchcliffe. 2007: The year enterprises open thier SOAs to the Internet? Enterprise Web 2.0, Jan. 2007.

[18]

M. Huang. Planetlab bandwidth limits. http://www.planet-lab.org/doc/BandwidthLimits.php.

[19]

A. Jain, J. M. Hellerstein, S. Ratnasamy, and D. Wetherall. A wakeup call for internet monitoring systems: The case for distributed triggers. In Proceedings of HotNets-III, 2004.

[20]

R. Jain, D. M. Chiu, and W. Hawe. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. Technical report, DEC Research Report TR-301, 1984.

[21]

S. Jamin, P. Danzig, S. Shenker, and L. Zhang. A measurement-based admission control algorithm for integrated services packet networks. In Proceedings of ACM SIGCOMM, 1995.

Digital Library

[22]

D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation ofaggregate information. In Proceedings of IEEE FOCS, 2003.

Digital Library

[23]

A. Kumar, R. Rastogi, A. Siberschatz, and B. Yener. Algorithms for provisioning virtual private networks in the hose model. IEEE/ACM Transactions on Networking, 10(4), 2002.

Digital Library

[24]

J. Liang, S. Y. Ko, I. Gupta, and K. Nahrstedt. MON: On-demand overlays for distributed system management. In Proceedings of USENIX WORLDS, 2005.

Digital Library

[25]

J. Ma, K. Levchenko, C. Kriebich, S. Savage, and G. M. Voelker. Automated protocol inference: Unexpected means of identifying protocols. In Proceedings of ACM/USENIX IMC, 2006.

Digital Library

[26]

A. Manjhi, V. Shkapenyuk, K. Dhamdhere, and C. Olston. Finding(recently) frequent items in distributed data streams. In Proceedings of IEEE ICDE, 2005.

Digital Library

[27]

P. Marks. Mashup' websites are a hacker's dream come true. New Scientist magazine, 2551:28, May 2006.

[28]

R. Morris. TCP behavior with many flows. In Proceedings of IEEE ICNP, 1997.

Digital Library

[29]

J. Musser. Programmable web. http://www.programmableweb.com.

[30]

A. M. Odlyzko. Internet pricing and the history of communications. Computer Networks, 36:493--517, 2001.

[31]

A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: the single-node case. IEEE/ACM Transactions on Networking, 1(3), 1993.

Digital Library

[32]

B. Raghavan and A. C. Snoeren. A system for authenticated policy-compliant routing. In Proceedings of ACM SIGCOMM, 2004.

Digital Library

[33]

N. Shavit and A. Zemach. Diffracting trees. ACM Transactions on Computer Systems, 14(4), 1996.

Digital Library

[34]

I. Stoica, S. Shenker, and H. Zhang. Core-stateless fair queueing: a scalable architecture to approximate fair bandwidth allocations in high speed networks. In Proceedings of ACM SIGCOMM, 1998.

Digital Library

[35]

A. Vahdat, K. Yocum, K. Walsh, P. Mahadevan, D. Kostić, J. Chase, and D. Becker. Scalability and accuracy in a large-scale network emulator. In Proceedings of USENIX OSDI, 2002.

Digital Library

[36]

K. Vishwanath and A. Vahdat. Realistic and responsive network traffic generation. In Proceedings of ACM SIGCOMM, 2006.

Digital Library

[37]

L. Wang, K. Park, R. Pang, V. S. Pai, and L. Peterson. Reliability and security in the CoDeeN content distribution network. In Proceedings of USENIX, 2004.

Digital Library

[38]

R. Wattenhofer and P.Widmayer. An inherent bottleneck in distributed counting. In Proceedings of ACM PODC, 1997.

Digital Library

[39]

X. Yang, D. Wetherall, and T. Anderson. A DoS-limiting network architecture. In Proceedings of ACM SIGCOMM, 2005.

Digital Library

[40]

Z.-L. Zhang, Z. Duan, and Y. T. Hou. On scalable design of bandwidth brokers. IEICE Transactions on Communications, E84-B(8), 2001.

[41]

T. Zhao and V. Karamcheti. Enforcing resource sharing agreements among distributed server clusters. In Proceedings of IEEE IPDPS, 2002.

Digital Library

Cited By

Wu YWu HJia CPeng BZhang ZYang TChen PYang KCui B(2024)Scalable Overspeed Item Detection in Streams2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00094(1157-1170)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00094
Burke QMcDaniel PLa Porta TYu MHe T(2024)Misreporting Attacks Against Load Balancers in Software-Defined NetworkingMobile Networks and Applications10.1007/s11036-023-02156-028:4(1482-1497)Online publication date: 9-Jan-2024
https://doi.org/10.1007/s11036-023-02156-0
Li ZSun HXiong ZHuang QHu ZLi DRuan SHong HGui JHe JXu ZFang Y(2023)Noah: Reinforcement-Learning-Based Rate Limiter for Microservices in Large-Scale E-Commerce ServicesIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.326403834:9(5403-5417)Online publication date: Sep-2023
https://doi.org/10.1109/TNNLS.2023.3264038
Show More Cited By

Index Terms

Cloud control with distributed rate limiting
1. Networks
  1. Network services
    1. Network management

Recommendations

Cloud control with distributed rate limiting
SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications

Today's cloud-based services integrate globally distributed resources into seamless computing platforms. Provisioning and accounting for the resource usage of these Internet-scale applications presents a challenging technical problem. This paper ...
Capacity and token rate estimation for networks with token bucket shapers

Many cloud computing applications are bandwidth-intensive, and thus the cloud bandwidth information is important for their tenants to manage and troubleshoot the application performance. However, current bandwidth estimation methods face great ...
Using Burstable Instances in the Public Cloud: Why, When and How?

Amazon EC2 and Google Compute Engine (GCE) have recently introduced a new class of virtual machines called "burstable" instances that are cheaper than even the smallest traditional/regular instances. These lower prices come with reduced average capacity ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 37, Issue 4

October 2007

420 pages

ISSN:0146-4833

DOI:10.1145/1282427

Issue’s Table of Contents

SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications
August 2007
432 pages
ISBN:9781595937131
DOI:10.1145/1282380
General Chairs:
Jun Murai
Keio University, Japan
,
Kenjiro Cho
IIJ, Japan

Copyright © 2007 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: 27 August 2007

Published in SIGCOMM-CCR Volume 37, Issue 4

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

166
Total Citations
View Citations
3,239
Total Downloads

Downloads (Last 12 months)322
Downloads (Last 6 weeks)31

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wu YWu HJia CPeng BZhang ZYang TChen PYang KCui B(2024)Scalable Overspeed Item Detection in Streams2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00094(1157-1170)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00094
Burke QMcDaniel PLa Porta TYu MHe T(2024)Misreporting Attacks Against Load Balancers in Software-Defined NetworkingMobile Networks and Applications10.1007/s11036-023-02156-028:4(1482-1497)Online publication date: 9-Jan-2024
https://doi.org/10.1007/s11036-023-02156-0
Li ZSun HXiong ZHuang QHu ZLi DRuan SHong HGui JHe JXu ZFang Y(2023)Noah: Reinforcement-Learning-Based Rate Limiter for Microservices in Large-Scale E-Commerce ServicesIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.326403834:9(5403-5417)Online publication date: Sep-2023
https://doi.org/10.1109/TNNLS.2023.3264038
Nawab IKulkarni S(2023)Toward Next-Generation Distributed Rate-limiters2023 IEEE/ACM 23rd International Symposium on Cluster, Cloud and Internet Computing Workshops (CCGridW)10.1109/CCGridW59191.2023.00083(354-356)Online publication date: May-2023
https://doi.org/10.1109/CCGridW59191.2023.00083
Schuller PSiedl JGetto NSchork SZirpins C(2023)Optimized Throttling for OAuth-Based Authorization ServersEnterprise Design, Operations, and Computing. EDOC 2022 Workshops10.1007/978-3-031-26886-1_15(251-267)Online publication date: 24-Feb-2023
https://doi.org/10.1007/978-3-031-26886-1_15
Ahuja SDangui VPatil KSomasundaram MGupta VSanchez MYan GNoormohammadpour MRazmjoo ASmith GZhong HTriguna ABali SXiang YChen YGanesan PFernandez MLapukhov PLiu GZhang YKuipers FOrda A(2022)Network entitlementProceedings of the ACM SIGCOMM 2022 Conference10.1145/3544216.3544245(250-263)Online publication date: 22-Aug-2022
https://dl.acm.org/doi/10.1145/3544216.3544245
Melissaris TNabar KRadut RRehmtulla SShi AChandrashekar SPapapanagiotou IGavrilovska AAltınbüken DBinnig C(2022)Elastic cloud servicesProceedings of the 13th Symposium on Cloud Computing10.1145/3542929.3563483(142-157)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3542929.3563483
Berenberg ACalder B(2022)Deployment Archetypes for Cloud ApplicationsACM Computing Surveys10.1145/349833655:3(1-48)Online publication date: 3-Feb-2022
https://dl.acm.org/doi/10.1145/3498336
Tao XOta KDong MBorjigin WQi HLi K(2022)Congestion-Aware Traffic Allocation for Geo-Distributed Data CentersIEEE Transactions on Cloud Computing10.1109/TCC.2020.300119210:3(1675-1687)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TCC.2020.3001192
He YWu W(2022)Consistent and Fine-Grained Rule Update with In-Network Control for Distributed Rate Limiting2022 IEEE/ACM 30th International Symposium on Quality of Service (IWQoS)10.1109/IWQoS54832.2022.9812884(1-10)Online publication date: 10-Jun-2022
https://doi.org/10.1109/IWQoS54832.2022.9812884
Show More Cited By

View Options

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.

Figures

Tables

Media

View Issue’s Table of Contents