On Round-Robin routing with FCFS and LCFS scheduling

Esa Hyytiä*, Samuli Aalto

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

8 Sitaatiot (Scopus)
129 Lataukset (Pure)

Abstrakti

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.

AlkuperäiskieliEnglanti
Sivut83-103
Sivumäärä21
JulkaisuPerformance Evaluation
Vuosikerta97
DOI - pysyväislinkit
TilaJulkaistu - maaliskuuta 2016
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Sormenjälki Sukella tutkimusaiheisiin 'On Round-Robin routing with FCFS and LCFS scheduling'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

  • Projektit

    • 2 Päättynyt

    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

    Projekti: Academy of Finland: Other research funding

    Jonoteorian menetelmin kohti energiatehokasta ja suorituskykyistä palvelinkeskusta

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

    01/09/201331/08/2017

    Projekti: Academy of Finland: Other research funding

    Siteeraa tätä