For a multiclass G/G/1 queue with finite buffers, admission and scheduling control, and holding and rejection costs, we construct a policy that is asymptotically optimal in the heavy traffic limit. The policy is specified in terms of a single paramet
er which constitutes the free boundary point from the Harrison-Taksar free boundary problem, but otherwise depends explicitly on the problem data. The c mu priority rule is also used by the policy, but in a way that is novel, and, in particular, different than that used in problems with infinite buffers. We also address an analogous problem where buffer constraints are replaced by throughput time constraints.
We study a differential game that governs the moderate-deviation heavy-traffic asymptotics of a multiclass single-server queueing control problem with a risk-sensitive cost. We consider a cost set on a finite but sufficiently large time horizon, and
show that this formulation leads to stationary feedback policies for the game. Several aspects of the game are explored, including its characterization via a (one-dimensional) free boundary problem, the semi-explicit solution of an optimal strategy, and the specification of a saddle point. We emphasize the analogy to the well-known Harrison-Taksar free boundary problem which plays a similar role in the diffusion-scale heavy-traffic literature.
A well-known technique in estimating probabilities of rare events in general and in information theory in particular (used, e.g., in the sphere-packing bound), is that of finding a reference probability measure under which the event of interest has p
robability of order one and estimating the probability in question by means of the Kullback-Leibler divergence. A method has recently been proposed in [2], that can be viewed as an extension of this idea in which the probability under the reference measure may itself be decaying exponentially, and the Renyi divergence is used instead. The purpose of this paper is to demonstrate the usefulness of this approach in various information-theoretic settings. For the problem of channel coding, we provide a general methodology for obtaining matched, mismatched and robust error exponent bounds, as well as new results in a variety of particular channel models. Other applications we address include rate-distortion coding and the problem of guessing.
We consider the problem of minimizing queue-length costs in a system with heterogenous parallel servers, operating in a many-server heavy-traffic regime with nondegenerate slowdown. This regime is distinct from the well-studied heavy traffic diffusio
n regimes, namely the (single server) conventional regime and the (many-server) Halfin-Whitt regime. It has the distinguishing property that waiting times and service times are of comparable magnitudes. We establish an asymptotic lower bound on the cost and devise a sequence of policies that asymptotically attain this bound. As in the conventional regime, the asymptotics can be described by means of a Brownian control problem, the solution of which exhibits a state space collapse.
A multi-class single-server system with general service time distributions is studied in a moderate deviation heavy traffic regime. In the scaling limit, an optimal control problem associated with the model is shown to be governed by a differential g
ame that can be explicitly solved. While the characterization of the limit by a differential game is akin to results at the large deviation scale, the analysis of the problem is closely related to the much studied area of control in heavy traffic at the diffusion scale.
Given a bounded $mathcaligr{C}^2$ domain $Gsubset{mathbb{R}}^m$, functions $ginmathcaligr{C}(partial G,{mathbb{R}})$ and $hinmathcaligr {C}(bar{G},{mathbb{R}}setminus{0})$, let $u$ denote the unique viscosity solution to the equation $-2Delta_{infty}
u=h$ in $G$ with boundary data $g$. We provide a representation for $u$ as the value of a two-player zero-sum stochastic differential game.
This paper introduces and analyzes the notion of throughput suboptimality for many-server queueing systems in heavy traffic. The queueing model under consideration has multiple customer classes, indexed by a finite set $mathcal{I}$, and heterogenous,
exponential servers. Servers are dynamically chosen to serve customers, and buffers are available for customers waiting to be served. The arrival rates and the number of servers are scaled up in such a way that the processes representing the number of class-$i$ customers in the system, $iinmathcal{I}$, fluctuate about a static fluid model, that is assumed to be critically loaded in a standard sense. At the same time, the fluid model is assumed to be throughput suboptimal. Roughly, this means that the servers can be allocated so as to achieve a total processing rate that is greater than the total arrival rate. We show that there exists a dynamic control policy for the queueing model that is efficient in the following strong sense: Under this policy, for every finite $T$, the measure of the set of times prior to $T$, at which at least one customer is in the buffer, converges to zero in probability as the arrival rates and number of servers go to infinity. On the way to prove our main result, we provide a characterization of throughput suboptimality in terms of properties of the buffer-station graph.
A two-player stochastic differential game representation has recently been obtained for solutions of the equation -Delta_infty u=h in a calC^2 domain with Dirichlet boundary condition, where h is continuous and takes values in RRsetminus{0}. Under ap
propriate assumptions, including smoothness of u, the vanishing delta limit law of the state process, when both players play delta-optimally, is identified as a diffusion process with coefficients given explicitly in terms of derivatives of the function u.
