Beyond shortest queue routing with heterogeneous servers and general cost functions

Esa Hyytiä, Rhonda Righter, Sigurur Gauti Samelsson

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

Routing jobs to parallel servers is a common and important task in today's computer systems. Join-the-shortest-queue (JSQ) routing minimizes the mean response time under rather general settings as long as the servers are identical and service times are independent and exponentially distributed. Apart from this, surprisingly few optimality results exist, mainly due to the complexities arising from the infinite state spaces. Indeed, it is difficult to analyze the performance of any given routing policy. In this paper, we consider an elementary job routing problem with heterogeneous servers and general cost structures. By a novel approximation, we reduce the state space to finite size, which enables us to estimate the mean performance, and to determine (practically) optimal routing policies, for a large class of cost structures. We demonstrate the approximation and its application to job routing policy optimization in numerical examples.

Original languageEnglish
Title of host publicationProceedings of the 11th EAI International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2017
PublisherACM
Pages206-213
Number of pages8
ISBN (Print)9781450363464
DOIs
Publication statusPublished - 5 Dec 2017
MoE publication typeA4 Article in a conference publication
EventInternational Conference on Performance Evaluation Methodologies and Tools - Venice, Italy
Duration: 5 Dec 20177 Dec 2017
Conference number: 11

Conference

ConferenceInternational Conference on Performance Evaluation Methodologies and Tools
Abbreviated titleVALUETOOLS
CountryItaly
CityVenice
Period05/12/201707/12/2017

Keywords

  • General cost function
  • Heterogeneous servers
  • JSQ
  • Routing jobs
  • SED

Fingerprint Dive into the research topics of 'Beyond shortest queue routing with heterogeneous servers and general cost functions'. Together they form a unique fingerprint.

  • Cite this

    Hyytiä, E., Righter, R., & Samelsson, S. G. (2017). Beyond shortest queue routing with heterogeneous servers and general cost functions. In Proceedings of the 11th EAI International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2017 (pp. 206-213). ACM. https://doi.org/10.1145/3150928.3150946