About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
11th EAI International Conference on Performance Evaluation Methodologies and Tools

Research Article

Beyond Shortest Queue Routing with Heterogeneous Servers and General Cost Functions

Cite
BibTeX Plain Text
  • @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
Esa Hyytia1,*, Rhonda Righter2, Sigurður Gauti Samúelsson3
  • 1: University of Iceland
  • 2: UC Berkeley
  • 3: Aalto University
*Contact email: esa@hi.is

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.

Keywords
routing jobs jsq sed heterogeneous servers general cost functions
Published
2018-08-10
Publisher
ACM
http://dx.doi.org/10.4108/eai.5-12-2017.2274693
Copyright © 2017–2025 ACM
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL