Beyond shortest queue routing with heterogeneous servers and general cost functions

Esa Hyytiä; Rhonda Righter; Sigurur Gauti Samelsson

doi:10.1145/3150928.3150946

Beyond shortest queue routing with heterogeneous servers and general cost functions

Esa Hyytiä
, Rhonda Righter
, Sigurur Gauti Samelsson

Performance analysis

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

2 Citations (Scopus)

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 language	English
Title of host publication	Proceedings of the 11th EAI International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2017
Publisher	ACM
Pages	206-213
Number of pages	8
ISBN (Print)	9781450363464
DOIs	https://doi.org/10.1145/3150928.3150946
Publication status	Published - 5 Dec 2017
MoE publication type	A4 Conference publication
Event	International Conference on Performance Evaluation Methodologies and Tools - Venice, Italy Duration: 5 Dec 2017 → 7 Dec 2017 Conference number: 11 http://valuetools.org/2017/

Conference

Conference	International Conference on Performance Evaluation Methodologies and Tools
Abbreviated title	VALUETOOLS
Country/Territory	Italy
City	Venice
Period	05/12/2017 → 07/12/2017
Internet address	http://valuetools.org/2017/

Keywords

General cost function
Heterogeneous servers
JSQ
Routing jobs
SED

Access to Document

10.1145/3150928.3150946

Cite this

@inproceedings{cb77f9d478394e1985a98b320c09d2eb,

title = "Beyond shortest queue routing with heterogeneous servers and general cost functions",

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.",

keywords = "General cost function, Heterogeneous servers, JSQ, Routing jobs, SED",

author = "Esa Hyyti{\"a} and Rhonda Righter and Samelsson, \{Sigurur Gauti\}",

year = "2017",

month = dec,

day = "5",

doi = "10.1145/3150928.3150946",

language = "English",

isbn = "9781450363464",

pages = "206--213",

booktitle = "Proceedings of the 11th EAI International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2017",

publisher = "ACM",

address = "United States",

note = "International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS ; Conference date: 05-12-2017 Through 07-12-2017",

url = "http://valuetools.org/2017/",

}

Hyytiä, E, Righter, R & Samelsson, SG 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. ACM, pp. 206-213, International Conference on Performance Evaluation Methodologies and Tools, Venice, Italy, 05/12/2017. https://doi.org/10.1145/3150928.3150946

Beyond shortest queue routing with heterogeneous servers and general cost functions. / Hyytiä, Esa; Righter, Rhonda; Samelsson, Sigurur Gauti.
Proceedings of the 11th EAI International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2017. ACM, 2017. p. 206-213.

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Beyond shortest queue routing with heterogeneous servers and general cost functions

AU - Hyytiä, Esa

AU - Righter, Rhonda

AU - Samelsson, Sigurur Gauti

N1 - Conference code: 11

PY - 2017/12/5

Y1 - 2017/12/5

N2 - 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.

AB - 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.

KW - General cost function

KW - Heterogeneous servers

KW - JSQ

KW - Routing jobs

KW - SED

UR - https://www.scopus.com/pages/publications/85051631167

U2 - 10.1145/3150928.3150946

DO - 10.1145/3150928.3150946

M3 - Conference article in proceedings

AN - SCOPUS:85051631167

SN - 9781450363464

SP - 206

EP - 213

BT - Proceedings of the 11th EAI International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2017

PB - ACM

T2 - International Conference on Performance Evaluation Methodologies and Tools

Y2 - 5 December 2017 through 7 December 2017

ER -

Beyond shortest queue routing with heterogeneous servers and general cost functions

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this