Search for: All records

Consider a queuing system with K parallel queues in which the server for each queue processes jobs at rate n and the total arrival rate to the system is [Formula: see text], where [Formula: see text] and n is large. Interarrival and service times are taken to be independent and exponentially distributed. It is well known that the join-the-shortest-queue (JSQ) policy has many desirable load-balancing properties. In particular, in comparison with uniformly at random routing, the time asymptotic total queue-length of a JSQ system, in the heavy traffic limit, is reduced by a factor of K. However, this decrease in total queue-length comes at the price of a high communication cost of order [Formula: see text] because at each arrival instant, the state of the full K-dimensional system needs to be queried. In view of this, it is of interest to study alternative routing policies that have lower communication costs and yet have similar load-balancing properties as JSQ. In this work, we study a family of such rank-based routing policies, which we will call Marginal Size Bias Load-Balancing policies, in which [Formula: see text] of the incoming jobs are routed to servers with probabilities depending on their ranked queue length and the remaining jobs are routed uniformly at random. A particular case of such routing schemes, referred to as the marginal JSQ (MJSQ) policy, is one in which all the [Formula: see text] jobs are routed using the JSQ policy. Our first result provides a heavy traffic approximation theorem for such queuing systems in terms of reflected diffusions in the positive orthant [Formula: see text]. It turns out that, unlike the JSQ system, where, due to a state space collapse, the heavy traffic limit is characterized by a one-dimensional reflected Brownian motion, in the setting of MJSQ (and for the more general rank-based routing schemes), there is no state space collapse, and one obtains a novel diffusion limit which is the constrained analogue of the well-studied Atlas model (and other rank-based diffusions) that arise from certain problems in mathematical finance. Next, we prove an interchange of limits ([Formula: see text] and [Formula: see text]) result which shows that, under conditions, the steady state of the queuing system is well approximated by that of the limiting diffusion. It turns out that the latter steady state can be given explicitly in terms of product laws of Exponential random variables. Using these explicit formulae, and the interchange of limits result, we compute the time asymptotic total queue-length in the heavy traffic limit for the MJSQ system. We find the striking result that, although in going from JSQ to MJSQ, the communication cost is reduced by a factor of [Formula: see text], the steady-state heavy traffic total queue-length increases by at most a constant factor (independent of n, K) which can be made arbitrarily close to one by increasing a MJSQ parameter. We also study the case where the system is overloaded—namely, [Formula: see text]. For this case, we show that although the K-dimensional MJSQ system is unstable, unlike the setting of random routing, the system has certain desirable and quantifiable load-balancing properties. In particular, by establishing a suitable interchange of limits result, we show that the steady-state difference between the maximum and the minimum queue lengths stays bounded in probability (in the heavy traffic parameter n). Funding: Financial support from the National Science Foundation [RTG Award DMS-2134107] is gratefully acknowledged. S. Banerjee received financial support from the National Science Foundation [NSF-CAREER Award DMS-2141621]. A. Budhiraja received financial support from the National Science Foundation [Grant DMS-2152577]. 

We study two problems. First, we consider the large deviation behavior of empirical measures of certain diffusion processes as, simultaneously, the time horizon becomes large and noise becomes vanishingly small. The law of large numbers (LLN) of the empirical measure in this asymptotic regime is given by the unique equilibrium of the noiseless dynamics. Due to degeneracy of the noise in the limit, the methods of Donsker and Varadhan [Comm. Pure Appl. Math. 29 (1976), pp. 389–461] are not directly applicable and new ideas are needed. Second, we study a system of slow-fast diffusions where both the slow and the fast components have vanishing noise on their natural time scales. This time the LLN is governed by a degenerate averaging principle in which local equilibria of the noiseless system obtained from the fast dynamics describe the asymptotic evolution of the slow component. We establish a large deviation principle that describes probabilities of divergence from this behavior. On the one hand our methods require stronger assumptions than the nondegenerate settings, while on the other hand the rate functions take simple and explicit forms that have striking differences from their nondegenerate counterparts. 

Consider a massive (inert) particle impinged from above by N Brownian particles that are instantaneously reflected upon collision with the inert particle. The velocity of the inert particle increases due to the influence of an external Newtonian potential (e.g. gravitation) and decreases in proportion to the total local time of collisions with the Brownian particles. This system models a semi-permeable membrane in a fluid having microscopic impurities (Knight in Probab Theory Relat Fields 121:577–598, 2001). We study the long-time behavior of the process (V , Z), where V is the velocity of the inert particle and Z is the vector of gaps between successive particles ordered by their relative positions. The system is not hypoelliptic, not reversible, and has singular form interactions. Thus the study of stability behavior of the system requires new ideas. We show that this process has a unique stationary distribution that takes an explicit product form which is Gaussian in the velocity component and exponential in the other components. We also show that convergence in total variation distance to the stationary distribution happens at an exponential rate. We further obtain certain law of large numbers results for the particle locations and intersection local times.