Research Article
Beyond Shortest Queue Routing with Heterogeneous Servers and General Cost Functions
@INPROCEEDINGS{10.4108/eai.5-12-2017.2274693, author={Esa Hyytia and Rhonda Righter and Sigurður Gauti Sam\^{u}elsson}, title={Beyond Shortest Queue Routing with Heterogeneous Servers and General Cost Functions}, proceedings={11th EAI International Conference on Performance Evaluation Methodologies and Tools}, publisher={ACM}, proceedings_a={VALUETOOLS}, year={2018}, month={8}, keywords={routing jobs jsq sed heterogeneous servers general cost functions}, doi={10.4108/eai.5-12-2017.2274693} }- Esa Hyytia
Rhonda Righter
Sigurður Gauti Samúelsson
Year: 2018
Beyond Shortest Queue Routing with Heterogeneous Servers and General Cost Functions
VALUETOOLS
ACM
DOI: 10.4108/eai.5-12-2017.2274693
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 optimization in numerical examples.