Queueing with future information

Joel Spencer, Madhu Sudan, Kuang Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We study an admissions control problem, where a queue with service rate 1 ? p receives incoming jobs at rate ? ? (1?p, 1), and the decision maker is allowed to redirect away jobs up to a rate of p, with the objective of minimizing the time-average queue length. We show that the amount of information about the future has a significant impact on system performance, in the heavy-traffic regime. When the future is unknown, the optimal average queue length diverges at rate ? log 1 1p 11, as 1. In sharp contrast, when all future arrival and service times are revealed beforehand, the optimal average queue length converges to a finite constant, (1 ? p)/p, as ? ? 1. We further show that the finite limit of (1 ? p)/p can be achieved using only a finite lookahead window starting from the current time frame, whose length scales as O(log 1 1 ), as ? ? 1. This leads to the conjecture of an interesting duality between queuing delay and the amount of information about the future.

Original languageEnglish (US)
Title of host publicationPerformance Evaluation Review
PublisherAssociation for Computing Machinery
Number of pages3
StatePublished - 2014

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Hardware and Architecture


Dive into the research topics of 'Queueing with future information'. Together they form a unique fingerprint.

Cite this