Routing in queues with delayed information

Nelli Litvak, Uri Yechiali

Research output: Contribution to journalArticleAcademicpeer-review

14 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