Self-learning threshold-based load balancing
| Autor: | Diego Goldsztajn, Debankur Mukherjee, Philip Whiting, Johan S. H. van Leeuwaarden, Sem Borst |
|---|---|
| Přispěvatelé: | Stochastic Operations Research, Econometrics and Operations Research, Research Group: Operations Research |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
C.4 Computer science G.3 02 engineering and technology 01 natural sciences 010104 statistics & probability FOS: Mathematics 0202 electrical engineering electronic engineering information engineering many-server asymptotics 0101 mathematics Service system Computer Science - Performance fluid and diffusion limits business.industry Probability (math.PR) General Engineering 020206 networking & telecommunications Load balancing (computing) Performance (cs.PF) 60F17 60K25 (Primary) 68M20 (Secondary) business adaptive load balancing Mathematics - Probability Computer network |
| Zdroj: | INFORMS Journal on Computing, 34(1), 39-54. INFORMS Institute for Operations Research and the Management Sciences INFORMS Journal on Computing, 34(1), 39-54. INFORMS Inst.for Operations Res.and the Management Sciences |
| ISSN: | 1091-9856 |
| DOI: | 10.1287/ijoc.2021.1100 |
| Popis: | We consider a large-scale service system where incoming tasks have to be instantaneously dispatched to one out of many parallel server pools. The user-perceived performance degrades with the number of concurrent tasks and the dispatcher aims at maximizing the overall quality-of-service by balancing the load through a simple threshold policy. We demonstrate that such a policy is optimal on the fluid and diffusion scales, while only involving a small communication overhead, which is crucial for large-scale deployments. In order to set the threshold optimally, it is important, however, to learn the load of the system, which may be unknown. For that purpose, we design a control rule for tuning the threshold in an online manner. We derive conditions which guarantee that this adaptive threshold settles at the optimal value, along with estimates for the time until this happens. In addition, we provide numerical experiments which support the theoretical results and further indicate that our policy copes effectively with time-varying demand patterns. Comment: 51 pages, 6 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|