WCFS: a new framework for analyzing multiserver systems

Isaac Grosof (), Mor Harchol-Balter () and Alan Scheller-Wolf ()
Additional contact information
Isaac Grosof: Carnegie Mellon University
Mor Harchol-Balter: Carnegie Mellon University
Alan Scheller-Wolf: Carnegie Mellon University

Queueing Systems: Theory and Applications, 2022, vol. 102, issue 1, No 8, 143-174

Abstract: Abstract Multiserver queueing systems are found at the core of a wide variety of practical systems. Many important multiserver models have a previously-unexplained similarity: identical mean response time behavior is empirically observed in the heavy traffic limit. We explain this similarity for the first time. We do so by introducing the work-conserving finite-skip (WCFS) framework, which encompasses a broad class of important models. This class includes the heterogeneous M/G/k, the Limited Processor Sharing policy for the M/G/1, the Threshold Parallelism model and the Multiserver-Job model under a novel scheduling algorithm. We prove that for all WCFS models, scaled mean response time $$E[T](1-\rho )$$ E [ T ] ( 1 - ρ ) converges to the same value, $$E[S^2]/(2E[S])$$ E [ S 2 ] / ( 2 E [ S ] ) , in the heavy-traffic limit, which is also the heavy traffic limit for the M/G/1/FCFS. Moreover, we prove additively tight bounds on mean response time for the WCFS class, which hold for all load $$\rho $$ ρ . For each of the four models mentioned above, our bounds are the first known bounds on mean response time.

Keywords: Queueing; Response time; Bounds; Heavy traffic; Multiserver; M/G/k; Scheduling; 68M20 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11134-022-09848-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:102:y:2022:i:1:d:10.1007_s11134-022-09848-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-022-09848-6

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().