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 - Publisher Copyright: © 2017 ACM.
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 contribution
SN - 9781450363464
T3 - ACM International Conference Proceeding Series
SP - 206
EP - 213
BT - Proceedings of the 11th EAI International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2017
PB - Association for Computing Machinery (ACM)
T2 - 11th EAI International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2017
Y2 - 5 December 2017 through 7 December 2017
ER -