Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic

We address a rate control problem associated with a single server Markovian queueing system with customer abandonment in heavy traffic. The controller can choose a buffer size for the queueing system and also can dynamically control the service rate (equivalently the arrival rate) depending on the current state of the system. An infinite horizon cost minimization problem is considered here. The cost function includes a penalty for each rejected customer, a control cost related to the adjustment of the service rate and a penalty for each abandoning customer. We obtain an explicit optimal strategy for the limiting diffusion control problem (the Brownian control problem or BCP) which consists of a threshold-type optimal rejection process and a feedback-type optimal drift control. This solution is then used to construct an asymptotically optimal control policy, i.e. an optimal buffer size and an optimal service rate for the queueing system in heavy traffic. The properties of generalized regulator maps and weak convergence techniques are employed to prove the asymptotic optimality of this policy. In addition, we identify the parameter regimes where the infinite buffer size is optimal.     

Adaptive Stabilization of Nonlinear Stochastic Systems

The purpose of this paper is to study the problem of asymptotic stabilization in probability of nonlinear stochastic differential systems with unknown parameters. With this aim, we introduce the concept of an adaptive control Lyapunov function for stochastic systems and we use the stochastic version of Artstein's theorem to design an adaptive stabilizer. In this framework the problem of adaptive stabilization of a nonlinear stochastic system is reduced to the problem of asymptotic stabilization in probability of a modified system. The design of an adaptive control Lyapunov function is illustrated by the example of adaptively quadratically stabilizable in probability stochastic differential systems. Accepted 9 December 1996     

Asymptotics in a time-dependent renewal risk model with stochastic return

In this paper we study the asymptotic tail behavior for a non-standard renewal risk model with a dependence structure and stochastic return. An insurance company is allowed to invest in financial assets such as risk-free bonds and risky stocks, and the price process of its portfolio is described by a geometric Lévy process. By restricting the claim-size distribution to the class of extended regular variation (ERV) and imposing a constraint on the Lévy process in terms of its Laplace exponent, we obtain for the tail probability of the stochastic present value of aggregate claims a precise asymptotic formula, which holds uniformly for all time horizons. We further prove that the corresponding ruin probability also satisfies the same asymptotic formula.     

Many Sources Asymptotics for Networks with Small Buffers

In this paper, we obtain the overflow asymptotics in a network with small buffers when the resources are accessed by a large number of stationary independent sources. Under the assumption that the network is loop-free with respect to source–destination routes, we identify the precise large deviations rate functions for the buffer overflow at each node in terms of the external input characteristics. It is assumed that each type of source requires a Quality of Service (QoS) defined by bounds on the fraction of offered work lost. We then obtain the admissible region for sources which access the network based on these QoS requirements. When all the sources require the same QoS, we show that the admissible region asymptotically corresponds to that which is obtained by assuming that flows pass through each node unchanged.     

Almost sure stability of linear stochastic differential equations with jumps

 Under the nondegenerate condition as in the diffusion case, see [14, 21, 6], the linear stochastic jump-diffusion process projected on the unit sphere is a strong Feller process and has a unique invariant measure which is also ergodic using the relation between the transition probabilities of jump-diffusions and the corresponding diffusions due to [22]. The unique deterministic Lyapunov exponent can be represented by the Furstenberg-Khas'minskii formula as an integral over the sphere or the projective space with respect to the ergodic invariant measure so that the almost sure asymptotic stability of linear stochastic systems with jumps depends on its sign. The critical case of zero Lyapunov exponent is discussed and a large deviations result for asymptotically stable systems is further investigated. Several examples are treated for illustration. Received: 22 June 2000 / Revised version: 20 November 2001 / Published online: 13 May 2002     

Tail probabilities for M/G/∞ input processes (I): Preliminary asymptotics

The infinite server model of Cox with arbitrary service time distribution appears to provide a large class of traffic models - Pareto and log-normal distributions have already been reported in the literature for several applications. Here we begin the analysis of the large buffer asymptotics for a multiplexer driven by this class of inputs. To do so we rely on recent results by Duffield and O’Connell on overflow probabilities for the general single server queue. In this paper we focus on the key step in this approach: The appropriate large deviations scaling is shown to be related to the forward recurrence time of the service time distribution, and a closed form expression is derived for the corresponding generalized limiting log-moment generating function associated with the input process. Three different regimes are identified. In a companion paper we apply these results to obtain the large buffer asymptotics under a variety of service time distributions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Explicit Solution to a Certain Non-ELQG Risk-sensitive Stochastic Control Problem

A risk-sensitive stochastic control problem with finite/infinite horizon is studied with a 1-dimensional controlled process defined by a linear SDE with a linear control-term in the drift. In the criterion function, a non-linear/quadratic term is introduced by using the solution to a Riccati differential equation, and hence, the problem is not ELQG (Exponential Linear Quadratic Gaussian) in general. For the problem, optimal value and control are calculated in explicit forms and the set of admissible risk-sensitive parameters is given in a concrete form. As applications, two types of large deviations control problems, i.e., maximizing an upside large deviations probability and minimizing a downside large deviations probability, are mentioned.     

Convergence Speed and Asymptotic Distribution of a Parallel Robbins-Monro Method

Very recently, there is a growing interest in studying parallel and distributed stochastic approximation algorithms. Previously, we suggest such an algorithm to find zeros or locate maximum values of a regression function with large state space dimension in [1], and derived the strong consistency property for that algorithm. In the present work, we concern ourselves with the problem of asymptotic properties of such an algorithm. We will study the limit behavior of the algorithm and obtain the rate of convergence and asymptotic normality results.     

Large deviations without principle: join the shortest queue

We develop a methodology for studying “large deviations type” questions. Our approach does not require that the large deviations principle holds, and is thus applicable to a large class of systems. We study a system of queues with exponential servers, which share an arrival stream. Arrivals are routed to the (weighted) shortest queue. It is not known whether the large deviations principle holds for this system. Using the tools developed here we derive large deviations type estimates for the most likely behavior, the most likely path to overflow and the probability of overflow. The analysis applies to any finite number of queues. We show via a counterexample that this system may exhibit unexpected behavior Work of the first author was performed in part while visiting the Technion. Work of the second author was performed in part while visiting the Vrije Universiteit, Amsterdam, and was supported in part by Fund for the promotion of research at the Technion.     

Large Deviations and Importance Sampling for Systems of Slow-Fast Motion

In this paper we develop the large deviations principle and a rigorous mathematical framework for asymptotically efficient importance sampling schemes for general, fully dependent systems of stochastic differential equations of slow and fast motion with small noise in the slow component. We assume periodicity with respect to the fast component. Depending on the interaction of the fast scale with the smallness of the noise, we get different behavior. We examine how one range of interaction differs from the other one both for the large deviations and for the importance sampling. We use the large deviations results to identify asymptotically optimal importance sampling schemes in each case. Standard Monte Carlo schemes perform poorly in the small noise limit. In the presence of multiscale aspects one faces additional difficulties and straightforward adaptation of importance sampling schemes for standard small noise diffusions will not produce efficient schemes. It turns out that one has to consider the so called cell problem from the homogenization theory for Hamilton-Jacobi-Bellman equations in order to guarantee asymptotic optimality. We use stochastic control arguments.     

Explicit Solution for a Network Control Problem in the Large Deviation Regime

We consider optimal control of a stochastic network, where service is controlled to prevent buffer overflow. We use a risk-sensitive escape time criterion, which in comparison to the ordinary escape time criteria heavily penalizes exits which occur on short time intervals. A limit as the buffer sizes tend to infinity is considered. In [2] we showed that, for a large class of networks, the limit of the normalized cost agrees with the value function of a differential game. In this game, one player controls the service discipline (who to serve and whether to serve), and the other player chooses arrival and service rates in the network. The game's value is characterized in [2] as the unique solution to a Hamilton–Jacobi–Bellman Partial Differential Equation (PDE). In the current paper we apply this general theory to the important case of a network of queues in tandem. Our main results are: (i) the construction of an explicit solution to the corresponding PDE, and (ii) drawing out the implications for optimal risk-sensitive and robust regulation of the network. In particular, the following general principle can be extracted. To avoid buffer overflow there is a natural competition between two tendencies. One may choose to serve a particular queue, since that will help prevent its own buffer from overflowing, or one may prefer to stop service, with the goal of preventing overflow of buffers further down the line. The solution to the PDE indicates the optimal choice between these two, specifying the parts of the state space where each queue must be served (so as not to lose optimality), and where it can idle. Referring to those queues which must be served as bottlenecks, one can use the solution to the PDE to explicitly calculate the bottleneck queues as a function of the system's state, in terms of a simple set of equations.     

Biorthogonal M -Channel Compactly Supported Wavelets

We study a class of M -channel subband coding schemes with perfect reconstruction. Along the lines of [8] and [10], we construct compactly supported biorthogonal wavelet bases of L ² (R) , with dilation factor M , associated to these schemes. In particular, we study the case of splines, and obtain explicitly simple expressions for all the relevant filters. The resulting wavelets have arbitrarily large regularity and we also obtain asymptotic estimates for the regularity exponent. September 17, 1998. Date revised: June 14, 1999. Date accepted: June 25, 1999.     

Queueing at large resources driven by long-tailed M/G/∞-modulated processes

We analyze the queue at a buffer with input comprising sessions whose arrival is Poissonian, whose duration is long-tailed, and for which individual session detail is modeled as a stochastic fluid process. We obtain a large deviation result for the buffer occupation in an asymptotic regime in which the arrival rate nr, service rate ns, and buffer level nb are scaled to infinity with a parameter n. This can be used to approximate resources which multiplex many sources, each of which only uses a small proportion of the whole capacity, albeit for long-tailed durations. We show that the probability of overflow in such systems is exponentially small in n, although the decay in b is slower, reflecting the long tailed session durations. The requirements on the session detail process are, roughly speaking, that it self-averages faster than the cumulative session duration. This does not preclude the possibility that the session detail itself has a long-range dependent behavior, such as fractional Brownian motion, or another long-tailed M/G/∞ process. We show how the method can be used to determine the multiplexing gain available under the constraint of small delays (and hence short buffers) for multiplexers of large aggregates, and to compare the differential performance impact of increased buffering as opposed to load reduction. This revised version was published online in June 2006 with corrections to the Cover Date.     

带干扰的积分高斯过程的破产概率

本文研究了带干扰的积分高斯过程的破产概率.利用经典大偏差的方法,在一定的条件下,得到了相应概率的对数渐近式及测度族的大偏差原理.结果表明在不带干扰的情形下与已有结果一致.     

Optimal trajectory to overflow in a queue fed by a large number of sources

We analyse the deviant behavior of a queue fed by a large number of traffic streams. In particular, we explicitly give the most likely trajectory (or optimal path) to buffer overflow, by applying large deviations techniques. This is done for a broad class of sources, consisting of Markov fluid sources and periodic sources. Apart from a number of ramifications of this result, we present guidelines for the numerical evaluation of the optimal path.     

Second order backward stochastic differential equations with quadratic growth

We extend the well posedness results for second order backward stochastic differential equations introduced by Soner, Touzi and Zhang (2012)  [31] to the case of a bounded terminal condition and a generator with quadratic growth in the z$z$ variable. More precisely, we obtain uniqueness through a representation of the solution inspired by stochastic control theory, and we obtain two existence results using two different methods. In particular, we obtain the existence of the simplest purely quadratic 2BSDEs through the classical exponential change, which allows us to introduce a quasi-sure version of the entropic risk measure. As an application, we also study robust risk-sensitive control problems. Finally, we prove a Feynman–Kac formula and a probabilistic representation for fully non-linear PDEs in this setting.     

Asymptotic expansion of stochastic flows

Summary We study the asymptotic expansion in small time of the solution of a stochastic differential equation. We obtain a universal and explicit formula in terms of Lie brackets and iterated stochastic Stratonovich integrals. This formula contains the results of Doss [6], Sussmann [15], Fliess and Normand-Cyrot [7], Krener and Lobry [10], Yamato [17] and Kunita [11] in the nilpotent case, and extends to general diffusions the representation given by Ben Arous [3] for invariant diffusions on a Lie group. The main tool is an asymptotic expansion for deterministic ordinary differential equations, given by Strichartz [14].     

Asymptotics for transient and stationary probabilities for finite and infinite buffer discrete time queues

Consider a discrete time queue with i.i.d. arrivals (see the generalisation below) and a single server with a buffer length m. Let τm be the first time an overflow occurs. We obtain asymptotic rate of growth of moments and distributions of τm as m → ∞. We also show that under general conditions, the overflow epochs converge to a compound Poisson process. Furthermore, we show that the results for the overflow epochs are qualitatively as well as quantitatively different from the excursion process of an infinite buffer queue studied in continuous time in the literature. Asymptotic results for several other characteristics of the loss process are also studied, e.g., exponential decay of the probability of no loss (for a fixed buffer length) in time [0,η], η → ∞, total number of packets lost in [0, η, maximum run of loss states in [0, η]. We also study tails of stationary distributions. All results extend to the multiserver case and most to a Markov modulated arrival process. This revised version was published online in June 2006 with corrections to the Cover Date.     

Convergence rate of solutions toward stationary solutions to a two-phase model with magnetic field in a half line

In this paper, we study an asymptotic behavior of a solution to the outflow problem for a two-phase model with magnetic field. Our idea mainly comes from [1] and [2] which investigate the asymptotic stability and convergence rates of stationary solutions to the outflow problem for an isentropic Navier–Stokes equation. For the two-phase model with magnetic field, we also obtain the asymptotic stability and convergence rates of global solutions towards corresponding stationary solutions if the initial perturbation belongs to the weighted Sobolev space. The proof is based on the weighted energy method.     

Asymptotic Expansions of Large Deviations for Sums of Nonidentically Distributed Random Variables

The work is designated for obtaining asymptotic expansions and determination of structures of the remainder terms that take into consideration large deviations both in Cramer zones and Linnik power zones for the distribution function of sums of independent nonidentically distributed random variables (r.v.). In this scheme of summation of r.v., the results are obtained first by mainly using the general lemma on large deviations considering asymptotic expansions for an arbitrary r.v. with regular behaviour of its cumulants [11]. Asymptotic expansions in the Cramer zone for the distribution function of sums of identically distributed r.v. were investigated in the works [1,2]. Note that asymptotic expansions for large deviations were first obtained in the probability theory by J. Kubilius [3].