An official website of the United States government
This paper studies the Heavy Traffic (HT) joint distribution of queue lengths in an Input-queued switch (IQ switch) operating under the MaxWeight scheduling policy. IQ switchserve as representative of SPNs that do not satisfy the socalled Complete Resource Pooling (CRP) condition, and consequently exhibit a multidimensional State Space Collapse (SSC). Except in special cases, only mean queue lengths of such non-CRP systems is known in the literature. In this paper, we develop the Transform method to study the joint distribution of queue lengths in non-CRP systems. The key challenge is in solving an implicit functional equation involving the Laplace transform of the HT limiting distribution. For the general n x n IQ switch that has n2 queues, under a conjecture on uniqueness of the solution of the functional equation, we obtain an exact joint distribution of the HT limiting queue-lengths in terms of a non-linear combination of 2n iid exponentials.
more »
« less
Heavy-traffic queue length behavior in a switch under Markovian arrivals
This paper studies the input-queued switch operating under the MaxWeight algorithm when the arrivals are according to a Markovian process. We exactly characterize the heavy-traffic scaled mean sum queue length in the heavy-traffic limit, and show that it is within a factor of less than 2 from a universal lower bound. Moreover, we obtain lower and upper bounds that are applicable in all traffic regimes and become tight in the heavy-traffic regime. We obtain these results by generalizing the drift method recently developed for the case of independent and identically distributed arrivals to the case of Markovian arrivals. We illustrate this generalization by first obtaining the heavy-traffic mean queue length and its distribution in a single-server queue under Markovian arrivals and then applying it to the case of an input-queued switch. The key idea is to exploit the geometric mixing of finite-state Markov chains, and to work with a time horizon that is chosen so that the error due to mixing depends on the heavy-traffic parameter.
more »
« less
- PAR ID:
- 10516552
- Publisher / Repository:
- Cambridge
- Date Published:
- Journal Name:
- Advances in Applied Probability
- ISSN:
- 0001-8678
- Page Range / eLocation ID:
- 1 to 47
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Motivated by applications to wireless networks, cloud computing, data centers, etc., stochastic processing networks have been studied in the literature under various asymptotic regimes. In the heavy traffic regime, the steady-state mean queue length is proved to be $$\Theta({1}/{\epsilon})$$ , where $$\epsilon$$ is the heavy traffic parameter (which goes to zero in the limit). The focus of this paper is on obtaining queue length bounds on pre-limit systems, thus establishing the rate of convergence to heavy traffic. For the generalized switch, operating under the MaxWeight algorithm, we show that the mean queue length is within $$\textrm{O}({\log}({1}/{\epsilon}))$$ of its heavy traffic limit. This result holds regardless of the complete resource pooling (CRP) condition being satisfied. Furthermore, when the CRP condition is satisfied, we show that the mean queue length under the MaxWeight algorithm is within $$\textrm{O}({\log}({1}/{\epsilon}))$$ of the optimal scheduling policy. Finally, we obtain similar results for the rate of convergence to heavy traffic of the total queue length in load balancing systems operating under the ‘join the shortest queue’ routeing algorithm.more » « less
-
Dispatching systems, where arriving jobs are immediately assigned to one of multiple queues, are ubiquitous in computer systems and service systems. A natural and practically relevant model is one in which each queue serves jobs in FCFS (First-Come First-Served) order. We consider the case where the dispatcher is size-aware, meaning it learns the size (i.e. service time) of each job as it arrives; and state-aware, meaning it always knows the amount of work (i.e. total remaining service time) at each queue. While size- and state-aware dispatching to FCFS queues has been extensively studied, little is known about optimal dispatching for the objective of minimizing mean delay. A major obstacle is that no nontrivial lower bound on mean delay is known, even in heavy traffic (i.e. the limit as load approaches capacity). This makes it difficult to prove that any given policy is optimal, or even heavy-traffic optimal. In this work, we propose the first size- and state-aware dispatching policy that provably minimizes mean delay in heavy traffic. Our policy, called CARD (Controlled Asymmetry Reduces Delay), keeps all but one of the queues short, then routes as few jobs as possible to the one long queue. We prove an upper bound on CARD's mean delay, and we prove the first nontrivial lower bound on the mean delay of any size- and state-aware dispatching policy. Both results apply to any number of servers. Our bounds match in heavy traffic, implying CARD's heavy-traffic optimality. In particular, CARD's heavy-traffic performance improves upon that of LWL (Least Work Left), SITA (Size Interval Task Assignment), and other policies from the literature whose heavy-traffic performance is known.more » « less
-
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].more » « less
-
We characterize heavy-traffic process and steady-state limits for systems staffed according to the square-root safety rule, when the service requirements of the customers are perfectly correlated with their individual patience for waiting in queue. Under the usual many-server diffusion scaling, we show that the system is asymptotically equivalent to a system with no abandonment. In particular, the limit is the Halfin-Whitt diffusion for the [Formula: see text] queue when the traffic intensity approaches its critical value 1 from below, and is otherwise a transient diffusion, despite the fact that the prelimit is positive recurrent. To obtain a refined measure of the congestion due to the correlation, we characterize a lower-order fluid (LOF) limit for the case in which the diffusion limit is transient, demonstrating that the queue in this case scales like [Formula: see text]. Under both the diffusion and LOF scalings, we show that the stationary distributions converge weakly to the time-limiting behavior of the corresponding process limit. Funding: This work was supported by the National Natural Science Foundation of China [Grant 72188101] and the Division of Civil, Mechanical and Manufacturing Innovation [Grants 1763100 and 2006350].more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/apr.2023.60
