text: We study the necessity of predictive information in a class of queueing admission control problems, where a system manager is allowed to divert incoming jobs up to a fixed rate, in order to minimize the queueing delay experienced by the admitted jobs. (2014) show that the system's delay performance can be significantly improved by having access to future information in the form of a lookahead window, during which the times of future arrivals and services are revealed. They prove that, while delay under an optimal online policy diverges to infinity in the heavy-traffic regime, it can stay bounded by making use of future information. However, the diversion polices of (2014) require the length of the lookahead window to grow to infinity at a non-trivial rate in the heavy-traffic regime, and it remained open whether substantial performance improvement could still be achieved with less future information. We resolve this question to a large extent by establishing an asymptotically tight lower bound on how much future information is necessary to achieve superior performance, which matches the upper bound of (2014) up to a constant multiplicative factor. Our result hence demonstrates that the system's heavy-traffic delay performance is highly sensitive to the amount of future information available. Our proof is based on analyzing certain excursion probabilities of the input sample paths, and exploiting a connection between a policy's diversion decisions and subsequent server idling, which may be of independent interest for related dynamic resource allocation problems.
  @cite_5: We study an admissions control problem, where a queue with service rate @math receives incoming jobs at rate @math , and the decision maker is allowed to redirect away jobs up to a rate of @math , 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 @math , as @math . In sharp contrast, when all future arrival and service times are revealed beforehand, the optimal average queue length converges to a finite constant, @math , as @math . We further show that the finite limit of @math can be achieved using only a finite lookahead window starting from the current time frame, whose length scales as @math , as @math . This leads to the conjecture of an interesting duality between queuing delay and the amount of information about the future.
summary: Unfortunately, these arguments employed in the Markov setting do not seem to carry over easily when the lookahead window is taken into account. While our setting can still be cast as an MDP by incorporating the lookahead window into the state space, the structure of the state space is now considerably more complex (and increasingly so, as @math ), and it is not so clear as to whether any monotonicity property continues to hold. Our proof techniques circumvent this complexity by focusing on the macroscopic'' sample-path characteristics of the system, instead of the more refined details of the Bellman equations. As a trade-off, our analysis is more coarse'' by nature, and it provides neither a characterization of the multiplicative in the delay scaling, nor a concrete diversion policy that achieves the lower bound of the necessary amount of future information (which, fortunately, has already been given in @cite_5 ).