CaltechTHESIS
  A Caltech Library Service

Scheduling for Heavy-Tailed and Light-Tailed Workloads in Queueing Systems

Citation

Nair, Jayakrishnan U. (2012) Scheduling for Heavy-Tailed and Light-Tailed Workloads in Queueing Systems. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/AAXJ-EX10. https://resolver.caltech.edu/CaltechTHESIS:06012012-134536732

Abstract

In much of classical queueing theory, workloads are assumed to be light-tailed, with job sizes being described using exponential or phase type distributions. However, over the past two decades, studies have shown that several real-world workloads exhibit heavy-tailed characteristics. As a result, there has been a strong interest in studying queues with heavy-tailed workloads. So at this stage, there is a large body of literature on queues with light-tailed workloads, and a large body of literature on queues with heavy-tailed workloads. However, heavy-tailed workloads and light-tailed workloads differ considerably in their behavior, and these two types of workloads are rarely studied jointly.

In this thesis, we design scheduling policies for queueing systems, considering both heavy-tailed as well as light-tailed workloads. The motivation for this line of work is twofold. First, since real world workloads can be heavy-tailed or light-tailed, it is desirable to design schedulers that are robust in their performance to distributional assumptions on the workload. Second, there might be scenarios where a heavy-tailed and a light-tailed workload interact in a queueing system. In such cases, it is desirable to design schedulers that guarantee fairness in resource allocation for both workload types.

In this thesis, we study three models involving the design of scheduling disciplines for both heavy-tailed as well as light-tailed workloads. In Chapters 3 and 4, we design schedulers that guarantee robust performance across heavy-tailed and light-tailed workloads. In Chapter 5, we consider a setting in which a heavy-tailed and a light-tailed workload complete for service. In this setting, we design scheduling policies that guarantee good response time tail performance for both workloads, while also maintaining throughput optimality.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:queueing; scheduling; heavy tails; light tails; robustness; response time tail
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Low, Steven H. (advisor)
  • Wierman, Adam C. (advisor)
Thesis Committee:
  • Low, Steven H. (chair)
  • Chandy, K. Mani
  • Hassibi, Babak
  • Ho, Tracey C.
  • Wierman, Adam C.
Defense Date:1 May 2012
Non-Caltech Author Email:jayakrishnan.u (AT) gmail.com
Record Number:CaltechTHESIS:06012012-134536732
Persistent URL:https://resolver.caltech.edu/CaltechTHESIS:06012012-134536732
DOI:10.7907/AAXJ-EX10
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7121
Collection:CaltechTHESIS
Deposited By: Jayakrishnan Nair
Deposited On:01 Jun 2012 22:26
Last Modified:07 Jun 2023 17:27

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

1MB

Repository Staff Only: item control page