Fully decentralized emulation of best-effort and processor sharing queues

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