Scheduling jobs with unknown duration in clouds

Siva Theja Maguluri, R. Srikant

Research output: Contribution to journalArticlepeer-review

Abstract

We consider a stochastic model of jobs arriving at a cloud data center. Each job requests a certain amount of CPU, memory, disk space, etc. Job sizes (durations) are also modeled as random variables, with possibly unbounded support. These jobs need to be scheduled nonpreemptively on servers. The jobs are first routed to one of the servers when they arrive and are queued at the servers. Each server then chooses a set of jobs from its queues so that it has enough resources to serve all of them simultaneously. This problem has been studied previously under the assumption that job sizes are known and upper-bounded, and an algorithm was proposed that stabilizes traffic load in a diminished capacity region. Here, we present a load balancing and scheduling algorithm that is throughput-optimal, without assuming that job sizes are known or are upper-bounded.

Original languageEnglish (US)
Article number6672027
Pages (from-to)1938-1951
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume22
Issue number6
DOIs
StatePublished - Dec 1 2014

Keywords

  • Cloud computing
  • performance evaluation
  • queueing theory
  • resource allocation
  • scheduling

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Scheduling jobs with unknown duration in clouds'. Together they form a unique fingerprint.

Cite this