The Library
Analysis of randomized join-the-shortest-queue (JSQ) schemes in large heterogeneous processor-sharing systems
Tools
Tools
Tools
Mukhopadhyay, Arpan and Mazumdar, Ravi R. (2016) Analysis of randomized join-the-shortest-queue (JSQ) schemes in large heterogeneous processor-sharing systems. IEEE Transactions on Control of Network Systems, 3 (2). pp. 116-126. doi:10.1109/TCNS.2015.2428331 ISSN 2325-5870.
|
PDF
WRAP-analysis-randomized-join-shortest-queue-large-sharing-Mukhopadhyay-2016.pdf - Accepted Version - Requires a PDF viewer. Download (540Kb) | Preview |
Official URL: https://doi.org/10.1109/TCNS.2015.2428331
Abstract
In this paper, we investigate the stability and performance
of randomized dynamic routing schemes for jobs based on
the Join-the-Shortest Queue (JSQ) criterion in a heterogeneous
system of many parallel servers. In particular, we consider servers
that use processor sharing but with different server rates, and
jobs are routed to the server with the smallest occupancy among
a finite number of randomly sampled servers. We focus on the
case of two servers that is often referred to as a Power-of-Two
scheme. We first show that in the heterogeneous setting, uniform
sampling of servers can cause a loss in the stability region and thus
such randomized dynamic schemes need not outperform static
randomized schemes in terms of mean delay in opposition to
the homogeneous case of equal server speeds where the stability
region is maximal and coincides with that of the static randomized
routing. We explicitly characterize the stationary distributions
of the server occupancies and show that the tail distribution
of the server occupancy has a super-exponential behavior as in
the homogeneous case as the number of servers goes to infinity.
To overcome the stability issue, we show that it is possible to
combine the static state-independent scheme with a randomized
JSQ scheme that allows us to recover the maximal stability region
combined with the benefits of JSQ, and such a scheme is preferable
in terms of average delay. The techniques are based on a mean field
analysis where we show that the stationary distributions coincide
with those obtained under asymptotic independence of the servers
and, moreover, the stationary distributions are insensitive to the
job-size distribution.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
| Journal or Publication Title: | IEEE Transactions on Control of Network Systems | ||||||||
| Publisher: | IEEE | ||||||||
| ISSN: | 2325-5870 | ||||||||
| Official Date: | June 2016 | ||||||||
| Dates: |
|
||||||||
| Volume: | 3 | ||||||||
| Number: | 2 | ||||||||
| Page Range: | pp. 116-126 | ||||||||
| DOI: | 10.1109/TCNS.2015.2428331 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Reuse Statement (publisher, data, author rights): | © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 12 April 2019 | ||||||||
| Date of first compliant Open Access: | 15 August 2019 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
