On Round-Robin routing with FCFS and LCFS scheduling

Esa Hyytiä*, Samuli Aalto

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

8 Citations (Scopus)
139 Downloads (Pure)

Abstract

We study the Round-Robin (RR) routing to a system of parallel queues, which serve jobs according to FCFS or preemptive LCFS scheduling disciplines. The cost structure comprises two components: a service fee and a queueing delay related component. With Poisson arrivals, the inter-arrival time to each queue obeys the Erlang distribution. This allows us to study the mean and transient behavior of the queues separately. The service fee is independent of the scheduling and queueing, and we obtain the corresponding mean cost rate and value function in closed forms. With respect to queueing delay, we first derive integral expressions enabling efficient computation of the corresponding size-aware value functions. By decomposition, these yield also the value function for the whole system of m parallel queues fed by RR. Given the value function, one can carry out the first policy iteration step with arbitrary holding cost rates (e.g., delay, slowdown, etc.) yielding efficient size-, cost- and state-aware policies. Moreover, the mean waiting and sojourn times in the corresponding systems get resolved at the same time. The results are demonstrated in the numerical examples, where we compute near optimal job routing policies for sample systems.

Original languageEnglish
Pages (from-to)83-103
Number of pages21
JournalPerformance Evaluation
Volume97
DOIs
Publication statusPublished - Mar 2016
MoE publication typeA1 Journal article-refereed

Keywords

  • Erl/G/1-queue
  • FCFS
  • LCFS
  • M/G/m-RR-system
  • Round-Robin
  • Task assignment

Fingerprint Dive into the research topics of 'On Round-Robin routing with FCFS and LCFS scheduling'. Together they form a unique fingerprint.

  • Projects

    Faster Queues for Big Data - Nopeammat jonot suurten tietomassojen käsittelyyn

    Hyytiä, E., Aalto, S., Viitasaari, L., Osti, P., Wu, X. & Bilenne, O.

    01/01/201631/12/2017

    Project: Academy of Finland: Other research funding

    Towards Optimal Performance-Energy Trade-off in Server Farms

    Aalto, S., Gebrehiwot, M., Hyytiä, E., Lassila, P. & Osti, P.

    01/09/201331/08/2017

    Project: Academy of Finland: Other research funding

    Cite this