Routing in queues with delayed information

Nelli Litvak, Uri Yechiali

Research output: Contribution to journalArticleAcademicpeer-review

13 Citations (Scopus)

Abstract

We compare two routing-control strategies in a high-speed communication network with c parallel channels (routes), where information on service completions in down-stream servers is randomly delayed. The controller can either hold arriving messages in a common buffer, dispatching them to servers only when the delayed information becomes available (Wait option), or route jobs to the various channels, in a round-robin fashion, immediately upon their arrival. Interpreting the delays as servers's vacations and considering overall queue sizes as a measure of performance, we show that the Wait strategy is superior as long as the mean information delay is below a threshold. We calculate threshold values for various combinations of load and c and show that, for a given load, the threshold increases with c and, for fixed c, the threshold decreases with an increasing load. If information is delayed on arrival instants, rather than on service completions, we show that the system can be viewed as a tandem queue and derive a generalization of a queue-decomposition result obtained by Altman, Kofman and Yechiali.
Original languageUndefined
Pages (from-to)147-165
Number of pages26
JournalQueueing systems
Volume43
Issue number1-2
DOIs
Publication statusPublished - 2003

Keywords

  • Routing
  • METIS-213225
  • Vacation models
  • IR-70722
  • Delayed information
  • EWI-17774
  • Decomposition
  • Multiple-server queues

Cite this

Litvak, Nelli ; Yechiali, Uri. / Routing in queues with delayed information. In: Queueing systems. 2003 ; Vol. 43, No. 1-2. pp. 147-165.
@article{bd5e2e1b5405433d8001bacb8f17c802,
title = "Routing in queues with delayed information",
abstract = "We compare two routing-control strategies in a high-speed communication network with c parallel channels (routes), where information on service completions in down-stream servers is randomly delayed. The controller can either hold arriving messages in a common buffer, dispatching them to servers only when the delayed information becomes available (Wait option), or route jobs to the various channels, in a round-robin fashion, immediately upon their arrival. Interpreting the delays as servers's vacations and considering overall queue sizes as a measure of performance, we show that the Wait strategy is superior as long as the mean information delay is below a threshold. We calculate threshold values for various combinations of load and c and show that, for a given load, the threshold increases with c and, for fixed c, the threshold decreases with an increasing load. If information is delayed on arrival instants, rather than on service completions, we show that the system can be viewed as a tandem queue and derive a generalization of a queue-decomposition result obtained by Altman, Kofman and Yechiali.",
keywords = "Routing, METIS-213225, Vacation models, IR-70722, Delayed information, EWI-17774, Decomposition, Multiple-server queues",
author = "Nelli Litvak and Uri Yechiali",
year = "2003",
doi = "10.1023/A:1021812816979",
language = "Undefined",
volume = "43",
pages = "147--165",
journal = "Queueing systems",
issn = "0257-0130",
publisher = "Springer",
number = "1-2",

}

Routing in queues with delayed information. / Litvak, Nelli; Yechiali, Uri.

In: Queueing systems, Vol. 43, No. 1-2, 2003, p. 147-165.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Routing in queues with delayed information

AU - Litvak, Nelli

AU - Yechiali, Uri

PY - 2003

Y1 - 2003

N2 - We compare two routing-control strategies in a high-speed communication network with c parallel channels (routes), where information on service completions in down-stream servers is randomly delayed. The controller can either hold arriving messages in a common buffer, dispatching them to servers only when the delayed information becomes available (Wait option), or route jobs to the various channels, in a round-robin fashion, immediately upon their arrival. Interpreting the delays as servers's vacations and considering overall queue sizes as a measure of performance, we show that the Wait strategy is superior as long as the mean information delay is below a threshold. We calculate threshold values for various combinations of load and c and show that, for a given load, the threshold increases with c and, for fixed c, the threshold decreases with an increasing load. If information is delayed on arrival instants, rather than on service completions, we show that the system can be viewed as a tandem queue and derive a generalization of a queue-decomposition result obtained by Altman, Kofman and Yechiali.

AB - We compare two routing-control strategies in a high-speed communication network with c parallel channels (routes), where information on service completions in down-stream servers is randomly delayed. The controller can either hold arriving messages in a common buffer, dispatching them to servers only when the delayed information becomes available (Wait option), or route jobs to the various channels, in a round-robin fashion, immediately upon their arrival. Interpreting the delays as servers's vacations and considering overall queue sizes as a measure of performance, we show that the Wait strategy is superior as long as the mean information delay is below a threshold. We calculate threshold values for various combinations of load and c and show that, for a given load, the threshold increases with c and, for fixed c, the threshold decreases with an increasing load. If information is delayed on arrival instants, rather than on service completions, we show that the system can be viewed as a tandem queue and derive a generalization of a queue-decomposition result obtained by Altman, Kofman and Yechiali.

KW - Routing

KW - METIS-213225

KW - Vacation models

KW - IR-70722

KW - Delayed information

KW - EWI-17774

KW - Decomposition

KW - Multiple-server queues

U2 - 10.1023/A:1021812816979

DO - 10.1023/A:1021812816979

M3 - Article

VL - 43

SP - 147

EP - 165

JO - Queueing systems

JF - Queueing systems

SN - 0257-0130

IS - 1-2

ER -