Stanojević, Rade and Shorten, Robert N. (2008) Fully decentralized emulation of best-effort and processor sharing queues. In: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems. ACM, New York. ISBN 978-1-60558-005-0

Download (670kB)

Abstract

Control of large distributed cloud-based services is a chal- lenging problem. The Distributed Rate Limiting (DRL) paradigm was recently proposed as a mechanism for tack- ling this problem. The heuristic nature of existing DRL solutions makes their behavior unpredictable and analyti- cally untractable. In this paper we treat the DRL prob- lem in a mathematical framework and propose two novel DRL algorithms that exhibit good and predictable perfor- mance. The ¯rst algorithm Cloud Control with Constant Probabilities (C3P) solves the DRL problem in best e®ort environments, emulating the behavior of a single best-e®ort queue in a fully distributed manner. The second problem we approach is the DRL in processor sharing environments. Our algorithm, Distributed Deficit Round Robin (D2R2), parameterized by parameter ®, converges to a state that is, at most, O( 1 ®) away from the exact emulation of central- ized processor sharing queue. The convergence and stability properties are fully analyzed for both C3P and D2R2. An- alytical results are validated empirically through a number of representative packet level simulations. The closed-form nature of our results allows simple design rules which, to- gether with extremely low communication overhead, makes the presented algorithms practical and easy to deploy.

Item Type:	Book Section
Keywords:	Rate limiting; CDN; Cloud control; Consensus agreement; Stability and convergence; Hamilton Institute.
Academic Unit:	Faculty of Science and Engineering > Research Institutes > Hamilton Institute Faculty of Science and Engineering > Mathematics and Statistics
Item ID:	1732
Depositing User:	Hamilton Editor
Date Deposited:	10 Dec 2009 15:10
Publisher:	ACM
Refereed:	Yes
URI:
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads