Delay, Memory, and Messaging Tradeoffs in Distributed Service Systems

Abstract : We consider the following distributed service model: jobs with unit mean, exponentially distributed, and independent processing times arrive as a Poisson process of rate λ N, with 0<λ<1, and are immediately dispatched to one of several queues associated with N identical servers with unit processing rate. We assume that the dispatching decisions are made by a central dispatcher endowed with a finite memory, and with the ability to exchange messages with the servers. We study the fundamental resource requirements (memory bits and message exchange rate), in order to drive the expected steady-state queueing delay of a typical job to zero, as N increases. We propose a certain policy and establish (using a fluid limit approach) that it drives the delay to zero when either (i) the message rate grows superlinearly with N, or (ii) the memory grows superlogarithmically with N. Moreover, we show that any policy that has a certain symmetry property, and for which neither condition (i) or (ii) holds, results in an expected queueing delay which is bounded away from zero. Finally, using the fluid limit approach once more, we show that for any given α>0 (no matter how small), if the policy only uses a linear message rate α N, the resulting asymptotic (as N->∞) expected queueing delay is positive but upper bounded, uniformly over all λ>1. This is a significant improvement over the popular "power-of-d-choices" policy, which has a limiting expected delay that grows as log ←(1/(1-λ)→) when λ↑ 1.
Type de document :
Communication dans un congrès
Sara Alouf; Alain Jean-Marie. ACM SIGMETRICS / IFIP Performance 2016, 13th Joint International Conference on Measurement and Modeling of Computer Systems, Jun 2016, Antibes Juan-Les Pins, France. ACM New York, NY, USA, pp.1-12, 2016, Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science. 〈10.1145/2896377.2901478〉
Liste complète des métadonnées

https://hal-preprod.archives-ouvertes.fr/hal-01046198
Contributeur : Hal Ifip <>
Soumis le : mardi 18 juillet 2017 - 17:47:34
Dernière modification le : mardi 18 juillet 2017 - 17:52:34

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale 4.0 International License

Identifiants

Citation

David Gamarnik, John N. Tsitsiklis, Martin Zubeldia. Delay, Memory, and Messaging Tradeoffs in Distributed Service Systems. Sara Alouf; Alain Jean-Marie. ACM SIGMETRICS / IFIP Performance 2016, 13th Joint International Conference on Measurement and Modeling of Computer Systems, Jun 2016, Antibes Juan-Les Pins, France. ACM New York, NY, USA, pp.1-12, 2016, Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science. 〈10.1145/2896377.2901478〉. 〈hal-01046198〉

Partager

Métriques