Barath Raghavan
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.
- Packeteer. http://www.packeteer.com.Google Scholar
- Akamai Technologies. Personal communication, June 2007.Google Scholar
- Amazon. Elastic compute cloud. http://aws.amazon.com/ec2.Google Scholar
- G. Appenzeller, I. Keslassy, and N. McKeown. Sizing router buffers. In Proceedings of ACM SIGCOMM, 2004. Google ScholarDigital Library
- B. Babcock and C. Olston. Distributed top-k monitoring. In Proceedings of ACM SIGMOD, 2003. Google ScholarDigital Library
- D. Bertsekas and R. Gallager. Data Networks. Prentice Hall, 1987. Google ScholarDigital Library
- S. Bhatnagar and B. Nath. Distributed admission control to support guaranteed services in core-stateless networks. In Proceedings of IEEE INFOCOM, 2003.Google Scholar
- D. F. Carr. How Google works. Baseline Magazine, July 2006.Google Scholar
- G. Carraro and F. Chong. Software as a service (SaaS): An enterprise perspective. MSDN Solution Architecture Center, Oct. 2006.Google Scholar
- 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. Google ScholarDigital Library
- A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. In Proceedings of ACM SIGCOMM, 1989. Google ScholarDigital Library
- M. Dilman and D. Raz. Efficient reactive monitoring. In Proceedings of IEEE INFOCOM, 2001.Google ScholarCross Ref
- W. Feng, K. Shin, D. Kandlur, and D. Saha. The blue active queue management algorithms. IEEE/ACM Transactions on Networking, 10(4), 2002. Google ScholarDigital Library
- S. Floyd and V. Jacobson. Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on Networking, 1(4), 1993. Google ScholarDigital Library
- S. Floyd and V. Jacobson. Link-sharing and resource management models for packet networks. IEEE/ACM Transactions on Networking, 3(4), 1995. Google ScholarDigital Library
- I. Gupta, A.-M. Kermarrec, and A. J. Ganesh. Efficient epidemic-style protocols for reliable and scalable multicast. In Proceedings of IEEE SRDS, 2002. Google ScholarDigital Library
- D. Hinchcliffe. 2007: The year enterprises open thier SOAs to the Internet? Enterprise Web 2.0, Jan. 2007.Google Scholar
- M. Huang. Planetlab bandwidth limits. http://www.planet-lab.org/doc/BandwidthLimits.php.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation ofaggregate information. In Proceedings of IEEE FOCS, 2003. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- J. Liang, S. Y. Ko, I. Gupta, and K. Nahrstedt. MON: On-demand overlays for distributed system management. In Proceedings of USENIX WORLDS, 2005. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- A. Manjhi, V. Shkapenyuk, K. Dhamdhere, and C. Olston. Finding(recently) frequent items in distributed data streams. In Proceedings of IEEE ICDE, 2005. Google ScholarDigital Library
- P. Marks. Mashup' websites are a hacker's dream come true. New Scientist magazine, 2551:28, May 2006.Google Scholar
- R. Morris. TCP behavior with many flows. In Proceedings of IEEE ICNP, 1997. Google ScholarDigital Library
- J. Musser. Programmable web. http://www.programmableweb.com.Google Scholar
- A. M. Odlyzko. Internet pricing and the history of communications. Computer Networks, 36:493--517, 2001.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- B. Raghavan and A. C. Snoeren. A system for authenticated policy-compliant routing. In Proceedings of ACM SIGCOMM, 2004. Google ScholarDigital Library
- N. Shavit and A. Zemach. Diffracting trees. ACM Transactions on Computer Systems, 14(4), 1996. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- K. Vishwanath and A. Vahdat. Realistic and responsive network traffic generation. In Proceedings of ACM SIGCOMM, 2006. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- R. Wattenhofer and P.Widmayer. An inherent bottleneck in distributed counting. In Proceedings of ACM PODC, 1997. Google ScholarDigital Library
- X. Yang, D. Wetherall, and T. Anderson. A DoS-limiting network architecture. In Proceedings of ACM SIGCOMM, 2005. Google ScholarDigital Library
- Z.-L. Zhang, Z. Duan, and Y. T. Hou. On scalable design of bandwidth brokers. IEICE Transactions on Communications, E84-B(8), 2001.Google Scholar
- T. Zhao and V. Karamcheti. Enforcing resource sharing agreements among distributed server clusters. In Proceedings of IEEE IPDPS, 2002. Google ScholarDigital Library
Index Terms
- Cloud control with distributed rate limiting
Recommendations
Cloud control with distributed rate limiting
SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communicationsToday'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