Optimal Scheduling in Multiserver Queues

Isaac Grosof*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Scheduling theory is a key tool for reducing latency (i.e. response time) in queueing systems. Scheduling, i.e. choosing the order in which to serve jobs, can reduce response time by an order of magnitude with no additional resources. Scheduling theory is well-developed in single-server systems, where one job is processed at a time. However, little is known about scheduling in multiserver systems, where many jobs are processed at once. Results are especially limited in stochastic multiserver scheduling theory. Today’s data-centers have thousands of servers, and scheduling theory is unable to analyze such systems. My thesis proves the first optimality results and first closed-form bounds on mean response time for scheduling policies in stochastic multiserver models which reflect the behavior of modern computing systems. My thesis proves novel optimality results in each of three areas: I start by studying one-server-per-job multiserver models, and prove the first results on optimal scheduling in that setting. Next, I study the multiserver-job (MSJ) model, where different jobs require different amounts of resources to be served. I prove the first characterization of mean response time for any scheduling policy in the MSJ model, as well as the first optimality results. Finally, I study the effects of scheduling on the tail of response time, rather than mean response time. I invent a novel scheduling policy, Nudge, which I prove to be the first policy to outperform FCFS’s asymptotic tail of response time. This extended abstract briefly outlines the main contributions of my thesis, describing my novel performance bounds and optimality results in each of these three areas.

Original languageEnglish (US)
Pages (from-to)29-32
Number of pages4
JournalPerformance Evaluation Review
Volume51
Issue number3
DOIs
StatePublished - Jan 5 2024

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Optimal Scheduling in Multiserver Queues'. Together they form a unique fingerprint.

Cite this