The Library
Asymptotic optimality of speed-aware JSQ for heterogeneous service systems
Tools
Tools
Tools
Bhambay, Sanidhay and Mukhopadhyay, Arpan (2022) Asymptotic optimality of speed-aware JSQ for heterogeneous service systems. Performance Evaluation . 102320. doi:10.1016/j.peva.2022.102320 ISSN 0166-5316. (In Press)
|
PDF
WRAP-Asymptotic-optimality-of-speed-aware-JSQ-for-heterogeneous-service-systems-Mukhopadhyay-2022.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (823Kb) | Preview |
Official URL: https://doi.org/10.1016/j.peva.2022.102320
Abstract
The Join-the-Shortest-Queue (JSQ) load-balancing scheme is known to minimise the average delay of jobs in homogeneous systems consisting of identical servers. However, it performs poorly in heterogeneous systems where servers have different processing rates. Finding a delay optimal scheme remains an open problem for heterogeneous systems. In this paper, we consider a speed-aware version of the JSQ scheme for heterogeneous systems and show that it achieves delay optimality in the fluid limit. One of the key issues in establishing this optimality result for heterogeneous systems is to show that the sequence of steady-state distributions indexed by the system size is tight in an appropriately defined space. The usual technique for showing tightness by coupling with a suitably defined dominant system does not work for heterogeneous systems. To prove tightness, we devise a new technique that uses the drift of exponential Lyapunov functions. Using the non-negativity of the drift, we show that the stationary queue length distribution has an exponentially decaying tail - a fact we use to prove tightness. Another technical difficulty arises due to the complexity of the underlying state-space and the separation of two time-scales in the fluid limit. Due to these factors, the fluid-limit turns out to be a function of the invariant distribution of a multi-dimensional8 Markov chain which is hard to characterise. By using some properties of this invariant distribution and using the monotonicity of the system, we show that the fluid limit is has a unique and globally attractive fixed point.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics T Technology > TK Electrical engineering. Electronics Nuclear engineering |
||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
| Library of Congress Subject Headings (LCSH): | Cloud computing, Heterogeneous computing, Probabilities, Computer networks, Queuing theory | ||||||||
| Journal or Publication Title: | Performance Evaluation | ||||||||
| Publisher: | Elsevier Science BV | ||||||||
| ISSN: | 0166-5316 | ||||||||
| Official Date: | 2022 | ||||||||
| Dates: |
|
||||||||
| Article Number: | 102320 | ||||||||
| DOI: | 10.1016/j.peva.2022.102320 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | In Press | ||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||
| Date of first compliant deposit: | 3 October 2022 | ||||||||
| Date of first compliant Open Access: | 14 October 2022 | ||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
