• ### Ergodicity of L\'evy-driven SDEs arising from multiclass many-server queues(1707.09674)

Sept. 21, 2018 math.PR
We study the ergodic properties of a class of multidimensional piecewise Ornstein-Uhlenbeck processes with jumps, which contains the limit of the queueing processes arising in multiclass many-server queues with heavy-tailed arrivals and/or asymptotically negligible service interruptions in the Halfin-Whitt regime as special cases. In these queueing models, the It\^o equations have a piecewise linear drift, and are driven by either (1) a Brownian motion and a pure-jump L\'evy process, or (2) an anisotropic L\'evy process with independent one-dimensional symmetric $\alpha$-stable components, or (3) an anisotropic L\'evy process as in (2) and a pure-jump L\'evy process. We also study the class of models driven by a subordinate Brownian motion, which contains an isotropic (or rotationally invariant) $\alpha$-stable L\'evy process as a special case. We identify conditions on the parameters in the drift, the L\'evy measure and/or covariance function which result in subexponential and/or exponential ergodicity. We show that these assumptions are sharp, and we identify some key necessary conditions for the process to be ergodic. In addition, we show that for the queueing models described above with no abandonment, the rate of convergence is polynomial, and we provide a sharp quantitative characterization of the rate via matching upper and lower bounds.
• ### Ergodic control of a class of jump diffusions with finite L\'evy measures and rough kernels(1801.07669)

Jan. 24, 2018 math.AP, math.OC
We study the ergodic control problem for a class of jump diffusions in $\mathbb{R}^d$, which are controlled through the drift with bounded controls. The Levy measure is finite, but has no particular structure; it can be anisotropic and singular. Moreover, there is no blanket ergodicity assumption for the controlled process. Unstable behavior is discouraged' by the running cost which satisfies a mild coercive hypothesis (i.e., is near-monotone). We first study the problem in its weak formulation as an optimization problem on the space of infinitesimal ergodic occupation measures, and derive the Hamilton-Jacobi-Bellman equation under minimal assumptions on the parameters, including verification of optimality results, using only analytical arguments. We also examine the regularity of invariant measures. Then, we address the jump diffusion model, and obtain a complete characterization of optimality.
• ### Infinite horizon asymptotic average optimality for large-scale parallel server networks(1706.03931)

Jan. 23, 2018 math.OC, cs.SY
We study infinite-horizon asymptotic average optimality for parallel server network with multiple classes of jobs and multiple server pools in the Halfin-Whitt regime. Three control formulations are considered: 1) minimizing the queueing and idleness cost, 2) minimizing the queueing cost under a constraints on idleness at each server pool, and 3) fairly allocating the idle servers among different server pools. For the third problem, we consider a class of bounded-queue, bounded-state (BQBS) stable networks, in which any moment of the state is bounded by that of the queue only (for both the limiting diffusion and diffusion-scaled state processes). We show that the optimal values for the diffusion-scaled state processes converge to the corresponding values of the ergodic control problems for the limiting diffusion. We present a family of state-dependent Markov balanced saturation policies (BSPs) that stabilize the controlled diffusion-scaled state processes. It is shown that under these policies, the diffusion-scaled state process is exponentially ergodic, provided that at least one class of jobs has a positive abandonment rate. We also establish useful moment bounds, and study the ergodic properties of the diffusion-scaled state processes, which play a crucial role in proving the asymptotic optimality.
• ### Infinite Horizon Average Optimality of the N-network Queueing Model in the Halfin-Whitt Regime(1602.03275)

Aug. 28, 2017 math.PR, math.OC, cs.SY
We study the infinite horizon optimal control problem for N-network queueing systems, which consist of two customer classes and two server pools, under average (ergodic) criteria in the Halfin-Whitt regime. We consider three control objectives: 1) minimizing the queueing (and idleness) cost, 2) minimizing the queueing cost while imposing a constraint on idleness at each server pool, and 3) minimizing the queueing cost while requiring fairness on idleness. The running costs can be any nonnegative convex functions having at most polynomial growth. For all three problems we establish asymptotic optimality, namely, the convergence of the value functions of the diffusion-scaled state process to the corresponding values of the controlled diffusion limit. We also present a simple state-dependent priority scheduling policy under which the diffusion-scaled state process is geometrically ergodic in the Halfin-Whitt regime, and some results on convergence of mean empirical measures which facilitate the proofs.
• ### Equivalence of Fluid Models for $G_t/GI/N+GI$ Queues(1502.00346)

Aug. 28, 2017 math.PR
Four different fluid model formulations have been recently developed for $G_t/GI/N+GI$ queues, including a two-parameter fluid model in Whitt (2006) by tracking elapsed service and patience times of each customer, a measure-valued fluid model in Kang and Ramanan (2010) and its extension in Zu{\~n}iga (2014) by tracking elapsed service and patience times of each customer, and a measure-valued fluid model in Zhang (2013) by tracking residual service and patience times of each customer. We show that the two fluid models tracking elapsed times (Whitt's and Kang and Ramanan's fluid models) are equivalent formulations for the same $G_t/GI/N+GI$ queue, whereas Zu{\~n}iga's fluid model and Zhang's fluid model are not entirely equivalent under general initial conditions. We then identify necessary and sufficient conditions under which Zu{\~n}iga's fluid model and Zhang's fluid model can be derived from each other for the same system, in which certain measure-valued fluid processes tracking residual service and patience times of each customer derived from Kang-Ramanan and Zu{\~n}iga's fluid models play an important role.The equivalence properties discovered provide important implications for the understanding of the recent development for non-Markovian many-server queues.
• ### Ergodic control of multi-class $M/M/N+M$ queues in the Halfin-Whitt regime(1404.1957)

Oct. 29, 2015 math.PR, math.OC, cs.SY
We study a dynamic scheduling problem for a multi-class queueing network with a large pool of statistically identical servers. The arrival processes are Poisson, and service times and patience times are assumed to be exponentially distributed and class dependent. The optimization criterion is the expected long time average (ergodic) of a general (nonlinear) running cost function of the queue lengths. We consider this control problem in the Halfin-Whitt (QED) regime, that is, the number of servers $n$ and the total offered load $\mathbf{r}$ scale like $n\approx\mathbf{r}+\hat{\rho}\sqrt{\mathbf{r}}$ for some constant $\hat{\rho}$. This problem was proposed in [Ann. Appl. Probab. 14 (2004) 1084-1134, Section 5.2]. The optimal solution of this control problem can be approximated by that of the corresponding ergodic diffusion control problem in the limit. We introduce a broad class of ergodic control problems for controlled diffusions, which includes a large class of queueing models in the diffusion approximation, and establish a complete characterization of optimality via the study of the associated HJB equation. We also prove the asymptotic convergence of the values for the multi-class queueing control problem to the value of the associated ergodic diffusion control problem. The proof relies on an approximation method by spatial truncation for the ergodic control of diffusion processes, where the Markov policies follow a fixed priority policy outside a fixed compact set.
• ### A service system with on-demand agent invitations(1409.7380)

Oct. 23, 2015 math.PR
We consider a service system where agents are invited on-demand. Customers arrive exogenously as a Poisson process and join a customer queue upon arrival if no agent is available. Agents decide to accept or decline invitations after some exponentially distributed random time, and join an agent queue upon invitation acceptance if no customer is waiting. A customer and an agent are matched in the order of customer arrival and agent invitation acceptance under the non-idling condition, and will leave the system simultaneously once matched (service times are irrelevant here). We consider a feedback-based adaptive agent invitation scheme, which controls the number of pending agent invitations, depending on the customer and/or agent queue lengths and their changes. The system process has two components -- the difference between agent and customer queues' and the number of pending invitations', and is a countable continuous-time Markov chain. For the case when the customer arrival rate is constant, we establish fluid and diffusion limits, in the asymptotic regime where the customer arrival rate goes to infinity, while the agent response rate is fixed. We prove the process stability and fluid-scale limit interchange, which in particular imply that that both customer and agent waiting times in steady-state vanish in the asymptotic limit. To do this we develop a novel (multi-scale) Lyapunov drift argument; it is required because the process has non-trivial behavior on the state space boundary. When the customer arrival rate is time-varying, we present a fluid limit for the processes in the same asymptotic regime. Simulation experiments are conducted to show good performance of the invitation scheme and accuracy of fluid limit approximations.
• ### Ergodic Diffusion Control of Multiclass Multi-Pool Networks in the Halfin-Whitt Regime(1505.04307)

Aug. 19, 2015 math.PR, math.OC, cs.SY
We consider Markovian multiclass multi-pool networks with heterogeneous server pools, each consisting of many statistically identical parallel servers, where the bipartite graph of customer classes and server pools forms a tree. Customers form their own queue and are served in the first-come first-served discipline, and can abandon while waiting in queue. Service rates are both class and pool dependent. The objective is to study the limiting diffusion control problems under the long run average (ergodic) cost criteria in the Halfin--Whitt regime. Two formulations of ergodic diffusion control problems are considered: (i) both queueing and idleness costs are minimized, and (ii) only the queueing cost is minimized while a constraint is imposed upon the idleness of all server pools. We develop a recursive leaf elimination algorithm that enables us to obtain an explicit representation of the drift for the controlled diffusions. Consequently, we show that for the limiting controlled diffusions, there always exists a stationary Markov control under which the diffusion process is geometrically ergodic. The framework developed in our earlier work is extended to address a broad class of ergodic diffusion control problems with constraints. We show that that the unconstrained and constrained problems are well posed, and we characterize the optimal stationary Markov controls via HJB equations.
• ### Ergodicity and fluctuations of a fluid particle driven by diffusions with jumps(1502.04440)

Feb. 16, 2015 math.PR
In this paper, we study the long-time behavior of a fluid particle immersed in a turbulent fluid driven by a diffusion with jumps, that is, a Feller process associated with a non-local operator. We derive the law of large numbers and central limit theorem for the evolution process of the tracked fluid particle in the cases when the driving process: (i) has periodic coefficients, (ii) is ergodic or (iii) is a class of L\'evy processes. The presented results generalize the classical and well-known results for fluid flows driven by elliptic diffusion processes.
• ### Golden-rule capacity allocation for distributed delay management in peer-to-peer networks(1402.0214)

Feb. 2, 2014 cs.NI
We describe a distributed framework for resources management in peer-to-peer networks leading to golden-rule reciprocity, a kind of one-versus-rest tit-for-tat, so that the delays experienced by any given peer's messages in the rest of the network are proportional to those experienced by others' messages at that peer.
• ### Two-Parameter Heavy-Traffic Limits for Infinite-Server Queues(0812.0877)

July 9, 2010 math.PR
In order to obtain Markov heavy-traffic approximations for infinite-server queues with general non-exponential service-time distributions and general arrival processes, possibly with time-varying arrival rates, we establish heavy-traffic limits for two-parameter stochastic processes. We consider the random variables $Q^e(t,y)$ and $Q^r(t,y)$ representing the number of customers in the system at time $t$ that have elapsed service times less than or equal to time $y$, or residual service times strictly greater than $y$. We also consider $W^r(t,y)$ representing the total amount of work in service time remaining to be done at time $t+y$ for customers in the system at time $t$. The two-parameter stochastic-process limits in the space $D([0,\infty),D)$ of $D$-valued functions in $D$ draw on, and extend, previous heavy-traffic limits by Glynn and Whitt (1991), where the case of discrete service-time distributions was treated, and Krichagina and Puhalskii (1997), where it was shown that the variability of service times is captured by the Kiefer process with second argument set equal to the service-time c.d.f.
• ### Continuity of a queueing integral representation in the ${M}_{\mathbf{1}}$ topology(1001.2381)

Jan. 14, 2010 math.PR
We establish continuity of the integral representation $y(t)=x(t)+\int_0^th(y(s)) ds$, $t\ge0$, mapping a function $x$ into a function $y$ when the underlying function space $D$ is endowed with the Skorohod $M_1$ topology. We apply this integral representation with the continuous mapping theorem to establish heavy-traffic stochastic-process limits for many-server queueing models when the limit process has jumps unmatched in the converging processes as can occur with bursty arrival processes or service interruptions. The proof of $M_1$-continuity is based on a new characterization of the $M_1$ convergence, in which the time portions of the parametric representations are absolutely continuous with respect to Lebesgue measure, and the derivatives are uniformly bounded and converge in $L_1$.
• ### Martingale proofs of many-server heavy-traffic limits for Markovian queues(0712.4211)

Dec. 27, 2007 math.PR
This is an expository review paper illustrating the `martingale method'' for proving many-server heavy-traffic stochastic-process limits for queueing models, supporting diffusion-process approximations. Careful treatment is given to an elementary model -- the classical infinite-server model $M/M/\infty$, but models with finitely many servers and customer abandonment are also treated. The Markovian stochastic process representing the number of customers in the system is constructed in terms of rate-1 Poisson processes in two ways: (i) through random time changes and (ii) through random thinnings. Associated martingale representations are obtained for these constructions by applying, respectively: (i) optional stopping theorems where the random time changes are the stopping times and (ii) the integration theorem associated with random thinning of a counting process. Convergence to the diffusion process limit for the appropriate sequence of scaled queueing processes is obtained by applying the continuous mapping theorem. A key FCLT and a key FWLLN in this framework are established both with and without applying martingales.