A lower bound on the queueing delay in resource constrained load balancing
© 2020 Institute of Mathematical Statistics. All rights reserved. We consider the following distributed service model: Jobs with unit mean, general distribution, and independent processing times arrive as a renewal process of rate λn, with 0 < λ < 1, and are immediately dispatched to one of se...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Mathematical Statistics
2021
|
| Online Access: | https://hdl.handle.net/1721.1/133724 |
| _version_ | 1811077940670103552 |
|---|---|
| author | Gamarnik, David Tsitsiklis, John N Zubeldia, Martin |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Gamarnik, David Tsitsiklis, John N Zubeldia, Martin |
| author_sort | Gamarnik, David |
| collection | MIT |
| description | © 2020 Institute of Mathematical Statistics. All rights reserved. We consider the following distributed service model: Jobs with unit mean, general distribution, and independent processing times arrive as a renewal 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 queueing delay in steadystate of a typical job to zero, as n increases. We develop a novel approach to show that, within a certain broad class of "symmetric" policies, every dispatching policy with a message rate of the order of n, and with a memory of the order of log n bits, results in an expected queueing delay which is bounded away from zero, uniformly as n→∞. This complements existing results which show that, in the absence of such limitations on the memory or the message rate, there exist policies with vanishing queueing delay (at least with Poisson arrivals and exponential service times). |
| first_indexed | 2024-09-23T10:50:42Z |
| format | Article |
| id | mit-1721.1/133724 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:50:42Z |
| publishDate | 2021 |
| publisher | Institute of Mathematical Statistics |
| record_format | dspace |
| spelling | mit-1721.1/1337242023-09-27T17:56:04Z A lower bound on the queueing delay in resource constrained load balancing Gamarnik, David Tsitsiklis, John N Zubeldia, Martin Sloan School of Management Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © 2020 Institute of Mathematical Statistics. All rights reserved. We consider the following distributed service model: Jobs with unit mean, general distribution, and independent processing times arrive as a renewal 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 queueing delay in steadystate of a typical job to zero, as n increases. We develop a novel approach to show that, within a certain broad class of "symmetric" policies, every dispatching policy with a message rate of the order of n, and with a memory of the order of log n bits, results in an expected queueing delay which is bounded away from zero, uniformly as n→∞. This complements existing results which show that, in the absence of such limitations on the memory or the message rate, there exist policies with vanishing queueing delay (at least with Poisson arrivals and exponential service times). 2021-10-27T19:56:21Z 2021-10-27T19:56:21Z 2020 2021-04-01T14:18:27Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/133724 en 10.1214/19-AAP1519 Annals of Applied Probability Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Mathematical Statistics arXiv |
| spellingShingle | Gamarnik, David Tsitsiklis, John N Zubeldia, Martin A lower bound on the queueing delay in resource constrained load balancing |
| title | A lower bound on the queueing delay in resource constrained load balancing |
| title_full | A lower bound on the queueing delay in resource constrained load balancing |
| title_fullStr | A lower bound on the queueing delay in resource constrained load balancing |
| title_full_unstemmed | A lower bound on the queueing delay in resource constrained load balancing |
| title_short | A lower bound on the queueing delay in resource constrained load balancing |
| title_sort | lower bound on the queueing delay in resource constrained load balancing |
| url | https://hdl.handle.net/1721.1/133724 |
| work_keys_str_mv | AT gamarnikdavid alowerboundonthequeueingdelayinresourceconstrainedloadbalancing AT tsitsiklisjohnn alowerboundonthequeueingdelayinresourceconstrainedloadbalancing AT zubeldiamartin alowerboundonthequeueingdelayinresourceconstrainedloadbalancing AT gamarnikdavid lowerboundonthequeueingdelayinresourceconstrainedloadbalancing AT tsitsiklisjohnn lowerboundonthequeueingdelayinresourceconstrainedloadbalancing AT zubeldiamartin lowerboundonthequeueingdelayinresourceconstrainedloadbalancing |