MURAL - Maynooth University Research Archive Library



    Fully decentralized emulation of best-effort and processor sharing queues


    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

    [img] Download (670kB)


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    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:

      Repository Staff Only(login required)

      View Item Item control page

      Downloads

      Downloads per month over past year