Heavy-traffic queue length behavior in a switch under Markovian arrivals

Abstract

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.

1. Introduction

The big data and machine learning revolution has been powered by large-scale data centers. With the growing size of data centers, it has become important to study the design and operation of efficient networks that facilitate the exchange of data [29]. One goal in the design of a data center network is to create a network that has full bisection bandwidth [1, 25] or a network that is logically equivalent to an input-queued switch. An operational challenge in such a data center is to schedule packets in order to maximize throughput and minimize delay.

In this paper, we study the problem of scheduling packets in an input-queued switch. In addition to serving as a model for data center networks, input-queued switches are important because they form the building blocks of any data network. An input-queued switch can be modeled as a matrix of queues operating in discrete time. Packets arrive into each of the queues according to a stochastic process. Each packet needs exactly one time slot of service. The key constraint is that at each time, exactly one packet can be served from each row or column. Thus the set of allowed schedules at each time forms a permutation matrix.

A popular algorithm for scheduling in an input-queued switch is the MaxWeight algorithm [32], which was first proposed in the context of wireless networks. In this algorithm, at each time, the permutation matrix with the maximum weight is chosen, using queue lengths as weights. While MaxWeight is known to maximize throughput in an input-queued switch [23], understanding the delay or queue-length performance is much more challenging, and so one uses asymptotic analysis. In this paper, we consider the heavy-traffic regime, where the total arrival rate in each row and column approaches the maximum possible value of one. The mean queue length in heavy traffic under the MaxWeight algorithm was characterized in [21, 22], where it was also shown that MaxWeight has the optimal scaling.

The key limitation of the work in [21, 22] is that it assumes that the arrivals are independent and identically distributed (i.i.d.). However, it is known that real data centers experience short bursts of high traffic [3]. The focus of this paper, therefore, is to consider arrivals that are modulated by a Markov chain, which can model a rich class of arrival patterns. For instance, in a continuous-time setting, it is known that a Markovian arrival process approximates any marked point process to an arbitrary degree of accuracy [2].

1.1. Main contributions

The main contribution of this paper is the exact characterization of the mean sum of queue lengths in heavy traffic in an input-queued switch operating under the MaxWeight algorithm. By Little’s law, such a result immediately implies a result on the mean delay. The key difference relative to the result in [22] under i.i.d. traffic is that the mean queue lengths depend not only on the instantaneous variance in steady state, but the entire autocovariance function of the arrival process. In addition to the heavy-traffic results, we obtain upper and lower bounds on the mean queue lengths under any traffic, and show that these match in the heavy-traffic regime. We also obtain a universal lower bound under any algorithm, and show that it is within a factor of at most two in the heavy-traffic limit.

An input-queued switch does not satisfy the so-called complete resource pooling (CRP) condition, and to the best of our knowledge, this is the first result on heavy-traffic characterization of a non-CRP system. Methods based on fluid and diffusion limits [8, 10, 11, 12, 31, 35] allow for natural generalization beyond i.i.d. arrivals, but except in special cases, there are no known results on non-CRP systems using these methods. The drift method was introduced in [21, 22] to analyze non-CRP systems such as the switch, but was crucially limited to i.i.d. arrivals. A key methodological contribution of this paper is to extend the drift method to Markovian arrivals, and thus obtain the first result on a non-CRP system under a non-i.i.d. arrival process.

The main ingredient in the drift method is to consider the one-step drift, i.e., the expected change in the value, of a test function. Under i.i.d. arrivals, the future arrivals are independent of the current queue length, and this property plays a crucial role in bounding the one-step drift. The key challenge in the study of Markovian arrivals is that such an independence property does not hold, because both the current queue length and future arrivals are correlated to the past arrivals. In order to overcome this challenge, we recursively expand the current queue length to express it in terms of the queue length m slots ago, as well as the arrivals and service over the last m time slots. If m is large enough, the old queue length is approximately independent of the current arrivals, because of the fast (geometric) mixing of the Markov chain that modulates the arrivals. However, this recursive expansion also introduces certain error terms, which are small only if m is small. We carefully choose m as a function of the heavy-traffic parameter $\epsilon$ , to optimally trade off between these two competing phenomena; i.e., our choice of m ensures approximate independence between the old queue length and the current arrivals while also ensuring that the resultant error terms go to zero in the heavy-traffic regime.

In order to illustrate our generalization of the drift method, in Section 3 we present a study of a single-server queue operating in discrete time under Markovian arrivals. We first present the Markovian generalization of Kingman’s bound [17] on the mean queue length. In the case of a single-server queue, in addition to the mean queue length, it is possible to obtain the complete distribution of the queue length in heavy traffic. We show that, similarly to the i.i.d. case, it is an exponential distribution, albeit with a modified mean that depends on the autocovariance function. We show this result using the transform method [13], a generalization of the drift method based on exponential test functions.

1.2. Related literature

Heavy-traffic analysis of queueing systems has been carried out in the literature using fluid and diffusion limits [8, 10, 11, 12, 31, 35]. Systems with Markovian arrivals can naturally be studied using such an approach, and the results on single-server queues that we present in Section 3 are known in that setting. However, most of these results are applicable only when the systems satisfy a condition called complete resource pooling (CRP). Under the CRP condition, the system behaves as a single-server queue. This is usually proved formally via a state-space collapse result, which shows that in the heavy-traffic limit, the multidimensional queue size vector stays close to a one-dimensional subspace. Except in some special cases, there is no literature using the diffusion limit approach to study systems that do not satisfy the CRP condition. The switch system considered in this paper does not satisfy the CRP condition, and it exhibits a multidimensional state-space collapse; that is, the queue size vector stays close to a multidimensional subspace.

An alternate method for heavy-traffic analysis based on drift arguments was introduced in [6] to study CRP systems. This drift method was generalized to study the switch system when the CRP condition is not met, in [21, 22]. The literature on the drift method so far is limited to an i.i.d. arrival process.

The switch under non-i.i.d. traffic was studied in [24] and [28]. A loose upper bound on queue lengths was obtained in [24] and a state-space collapse result was established in [28]. To the best of our knowledge, this is the first work that exactly characterizes the heavy-traffic queue lengths for a system without CRP, under a non-i.i.d. arrival process.

An input-queued switch is one of the simplest systems that does not satisfy CRP, and so has served as a guidepost for the study of general queueing systems [27]. The drift method that was developed in [22] was used to study a variety of stochastic processing networks in a flurry of follow-up works, all of them under i.i.d. traffic. An input-queued switch with prioritized customers was studied in [19, 20], a switch under novel low-complexity scheduling algorithms was studied in [16], and an optical switch that incurs queueing delay was studied in [33]. The so-called generalized switch model was studied in [14], and it subsumes a rich class of stochastic networks, including wireless networks, cloud computing, data center networks, production systems, and mobile base stations. These methods have also been used to study load balancing, in [15, 36], and the bandwidth sharing network, in [34].

1.3. Notation

Throughout the paper, we denote a random variable by an uppercase letter, for example, X; we denote the realization of a random variable X by the corresponding lowercase letter x. If they are vectors, we use the corresponding boldface letter, for example, $\boldsymbol{X}$ and $\boldsymbol{x}$ . We write $X \sim \pi$ if X follows the distribution $\pi$ , and $X \stackrel{d}{=} Y$ if X follows the same distribution as Y. We use $\mathcal{I}({\cdot})$ to denote the indicator function. We denote by $E_{X \sim \pi}[\cdot]$ and $Var_{X \sim \pi}[\cdot]$ the expectation and variance calculated with respect to the distribution $X \sim \pi$ . Finally, we denote by $\mathbb{N}_+$ the set of positive integers, by $\mathbb{N}$ the set of non-negative integers, and by $\mathbb{R}_+$ the set of positive real numbers.

The rest of the paper is organized as follows. In Section 2 we present a few preliminary results that are essential for the proofs. In Section 3 we introduce the single-server queue model, and present heavy-traffic results for it, in order to illustrate the drift method for Markovian arrivals. In Section 4 we introduce the switch model and present the main result of the paper, on the heavy-traffic behavior of the switch under Markovian arrivals. These results are obtained by using the ideas developed in Section 3 in conjunction with the broad outline from [21]. In particular, we first present a state-space collapse result, then use it to characterize the heavy-traffic mean sum queue length. Section 5 concludes the paper.

2. Preliminaries

In this section we present a few preliminary results on Markov chains that will be used throughout the paper.

2.1. Moment bounds from Lyapunov-type drift conditions

The results in this paper are based on studying the drift of functions of Markov chains. A lemma from [9] is usually used to obtain moment bounds based on conditions on the one-step drift. However, in this paper we will instead work with the m-step drift, and so we need the following generalization of the lemma from [9], which is proved in Appendix B.1.

Lemma 1. Let $\left\{\boldsymbol{Q}^t ,\boldsymbol{X}^t \right\}_{t \geq 0}$ be an irreducible, positive recurrent, and aperiodic Markov chain over a countable state space $ (\mathcal{Q},\mathcal{X} )$ . Suppose $Z\,:\, \mathcal{X}\to \mathbb{R}_+$ is a non-negative Lyapunov function. We define the m-step drift of Z at $ (\boldsymbol{q},\boldsymbol{x} )$ as

(1) \begin{equation} \Delta^m Z (\boldsymbol{q}, \boldsymbol{x} ) \triangleq \left[Z \left(\boldsymbol{Q}^{t+m},\boldsymbol{X}^{t+m} \right)-Z \left(\boldsymbol{Q}^t,\boldsymbol{X}^t \right) \right]\mathcal{I} \left(\left(\boldsymbol{Q}^{t},\boldsymbol{X}^{t} \right) = (\boldsymbol{q},\boldsymbol{x} ) \right), \end{equation}

where $\mathcal{I} (\cdot )$ is the indicator function. Thus, $\Delta^m Z (\boldsymbol{q},\boldsymbol{x} )$ is a random variable that measures the amount of change in the value of Z in m steps, starting from state $ \left(\boldsymbol{q},\boldsymbol{x}\right)$ . This drift is assumed to satisfy the following conditions, for any m:

1. 1. There exist an $\eta(m) > 0$ and a $\kappa(m) >0$ such that for any $t = 1, 2, \ldots$ and for all $ (\boldsymbol{q},\boldsymbol{x}) \in (\mathcal{Q},\mathcal{X} )$ with $Z (\boldsymbol{q},\boldsymbol{x} ) \geq \kappa(m)$ ,

   \begin{equation*} E \left[\Delta^m Z (\boldsymbol{q}, \boldsymbol{x} )\mid \left(\boldsymbol{Q}^t,\boldsymbol{X}^t \right) = (\boldsymbol{q},\boldsymbol{x} ) \right] \leq -\eta(m). \end{equation*}

2. 2. There exists a $D(m) < \infty$ such that for all $ \left(\boldsymbol{q},\boldsymbol{x} \right) \in (\mathcal{Q},\mathcal{X} )$ ,

   \begin{equation*} P \big(\lvert{ \Delta^m Z (\boldsymbol{q}, \boldsymbol{x} )}\rvert \leq D(m) \big) =1. \end{equation*}

3. 3. For any $t_0 \in [0,m]$ , there exists a $\hat{D}(t_0) < \infty$ such that for all $ \left(\boldsymbol{q},\boldsymbol{x} \right) \in (\mathcal{Q},\mathcal{X} )$ ,

   \begin{equation*} { P \big(\lvert{ Z (\boldsymbol{q}, \boldsymbol{x} )}\rvert \leq \hat{D}(t_0)\big)=1.} \end{equation*}

Then there exist a $\theta^*(m)>0$ and a $C^*(m) < \infty$ such that

\begin{equation*} \limsup_{t \to \infty} E \big[e^{\theta^*(m)Z \left(\boldsymbol{Q}^t,\boldsymbol{X}^t \right)} \big] \leq C^{\star}(m). \end{equation*}

If the Markov chain is positive recurrent, then $Z \left(\boldsymbol{Q}^t,\boldsymbol{X}^t\right)$ converges in distribution to a random variable $\overline{Z}$ for which

\begin{equation*} E \big[e^{\theta^*\overline{Z} } \big] \leq C^{\star}(m), \end{equation*}

which implies that all moments of $\overline{Z}$ exist and are finite.

Remark 1. If $\lvert{ \Delta Z (\boldsymbol{q}, \boldsymbol{x} )}\rvert \leq D^{\prime}$ is satisfied, then Conditions 2 and 3 are satisfied with $D(m) = mD^{\prime}$ and $\hat{D} = D^{\prime}$ .

2.2. Geometric mixing of finite-state Markov chains

The following two lemmas on geometric mixing of finite-state Markov chains will be exploited to obtain the results in the paper.

Lemma 2. Let $\{X^t\}_{\ t\geq 0}$ be an irreducible, positive recurrent, and aperiodic Markov chain on a finite state space $\Omega$ . Let $\pi$ denote its stationary distribution. Let $f({\cdot})$ be a real-valued function, i.e., $f\,:\,\Omega \to \mathbb{R}_+$ . Let $\lambda$ be the stationary mean of $f(X^t)$ , i.e.,

\begin{equation*} \lambda = E_{X\sim\pi}\left[f(X)\right]. \end{equation*}

Then there exist constants $\alpha \in (0,1 )$ and $C > 0$ such that, for any $m \in \mathbb{N}_+$ , for any initial distribution $X^0 \sim \pi^0$ , we have

\begin{equation*} \big\vert E_{ X^0 \sim \pi^0 } [ (f(X^m)-\lambda ) ] \big\vert \leq 2LC \alpha^m, \end{equation*}

where $ L = \max_{x \in \Omega} f(x) $ .

The lemma is proved in Appendix B.2.

Lemma 3. Let $\{X^t\}_{\ t\geq 0}$ be an irreducible, positive recurrent, and aperiodic Markov chain with finite state space $\Omega$ and stationary distribution $\pi$ . Let $f({\cdot})$ be a real-valued function bounded above by $A_{max}$ , i.e., $f\,:\,\Omega \to \mathbb{R}_+, f(x)\leq A_{max},\ \forall x\in \Omega$ . Let $\lambda$ be the stationary mean of $f(X^t)$ , i.e.,

\begin{equation*} \lambda = E_{\pi}\left[f(X)\right]. \end{equation*}

Then

\begin{align*} &\lim_{m \to \infty} \frac{Var_{ X^0 \sim \pi^0 } \left(\sum_{t=1}^m f(X^t) \right)}{m} \\ &= \gamma(0)+2\lim_{m \to \infty}\sum_{t=1}^{m}\frac{m-t}{m}\gamma(t) = \gamma(0)+2\lim_{m \to \infty}\sum_{t=1}^{m}\gamma(t),\end{align*}

where

\[ \gamma(t) = E_{X^0 \sim \pi}\big[ \big(f\big(X^t\big)-\lambda \big) \big(f\big(X^0\big)-\lambda \big)\big] \]

is the autocovariance function.

The lemma is proved in Appendix B.3.

Remark 2. There are several known equivalent formulations of the asymptotic variance. For instance, it can be shown (see Theorem 21.2.5 in [5]) that under appropriate assumptions,

(2) \begin{align}\lim_{m \to \infty} \frac{Var_{ X^0 \sim \pi^0 } \left(\sum_{t=1}^m f(X^t) \right)}{m} =2 E_{X \sim \pi}\big[ (f(X)-\lambda )\hat{f}(X)\big]-E_{X \sim \pi}\big[ (f(X)-\lambda )^2\big] ,\end{align}

where $\hat{f}({\cdot})$ is a solution of the Poisson equation of the Markov chain, $\hat{f}(x) = f(x) + E\big[\hat{f}(X^1)|X^0=x\big] - \lambda$ . In this paper, we will state all the results in terms of the asymptotic variance in Lemma 3; our results can easily be reformulated in terms of equivalent expressions such as (2).

Remark 3. The assumption of a finite state space is used primarily for establishing the positive-recurrence result for the single-server queue and the switch system in the heavy-traffic regime. All other results still hold for general state space. Another way of stating the heavy-traffic results in this paper would be to allow for a general state space and assume positive recurrence of the system (and then to prove positive recurrence in the case of a finite state space). However, we feel that such a presentation would be confusing, and so we present only the finite-state-space case in the following sections.

3. Single-server queue

In this section, we consider a single-server queue operating in discrete time. Under i.i.d. arrivals, the queue length in such a system is equivalent to the waiting time in a G/G/1 queue. Drift arguments were used to study the heavy-traffic mean queue length in [6, 17, 30], and the transform method was used to study the heavy-traffic stationary distribution in [13]. In this section, we consider the discrete-time single-server queue under Markovian arrivals, and extend both the drift method and the transform method. The key ingredients are to consider the dynamic m-step drift and exploit the geometric mixing of irreducible, positive recurrent, aperiodic finite-state-space Markov chains.

3.1. Mathematical model

Consider a single-server queue operating in discrete time. Let $Q^t$ be the number of customers in the system at the beginning of time slot t. Arrivals occur according to an underlying Markov chain $\{X^t\}_{\ t\geq 0}$ where the number of arrivals in the time slot t is given by $A^t = f (X^t )$ for some non-negative integer-valued function $f({\cdot})$ . The potential service $S^t$ is assumed to be i.i.d. with mean $\mu$ and variance $\sigma_s^2$ .

Assume that $\{X^t\}_{\ t\geq 0}$ is irreducible, positive recurrent, and aperiodic on a finite state space $\Omega$ . Thus $\{X^t\}_{\ t\geq 0}$ converges to its stationary distribution $\pi$ at a geometric rate. Further assume that $A^t$ and $S^t$ are bounded above by $A_{max}$ and $S_{max}$ respectively.

In each time slot, we assume that the service occurs after arrivals, and the system evolves as follows: for each $t = 1,\ 2,\ldots$ ,

(3) \begin{align} Q^{t+1}& = \max\left\{Q^t + A^t - S^t,0\right\}=Q^t + A^t - S^t+ U^t, \end{align}

where $U^t$ denotes the unused service and is defined by $U^t = Q^{t+1} -\left(Q^t + A^t - S^t \right) $ . From the definition of the unused service, we have

(4) \begin{align} Q^{t+1}U^t=0.\end{align}

In order to study the heavy-traffic behavior of the single-server queue, we will consider a sequence of arrival processes such that the arrival rate approaches the service rate $\mu$ . To this end, let $\{X^t\}^{ (\epsilon )}_{t\geq 0}$ be a set of irreducible, positive recurrent, and aperiodic underlying Markov chains indexed by the heavy-traffic parameter $\epsilon \in (0,\mu )$ . Assume that the arrival process is such that the two-dimensional Markov chain $ \big\{ \big((Q^t)^{ (\epsilon )},\ (X^t)^{ (\epsilon )} \big)\big\}_{t\geq 0 } $ is irreducible and aperiodic. For any fixed $\epsilon$ , let $\overline{X}^{ (\epsilon )}$ be the steady-state variable to which $(X^t)^{ (\epsilon )}$ converges in distribution with $E\big[\overline{A}^{(\epsilon)} \big] = E\big[f\big(\overline{X}^{ (\epsilon )}\big)\big] = \lambda^{(\epsilon)} = \mu -\epsilon$ .

Let $\gamma^{(\epsilon)}(t)$ be the autocovariance function of the arrival process starting from steady state $X^0 \stackrel{d}{=}\overline{X}^{ (\epsilon )}$ , $\overline{A}^{(\epsilon)}= f\big(\overline{X}^{ (\epsilon )}\big)$ and $(A^t)^{(\epsilon)} = f\left((X^t)^{(\epsilon)}\right)$ indexed by $\epsilon$ , i.e.,

\[ \gamma^{(\epsilon)}(t) = E \big[ \big((A^t)^{(\epsilon)}-\lambda \big) \big(\big(A^0\big)^{(\epsilon)}-\lambda \big) \big]. \]

Let

\[ \big(\sigma_a^{(\epsilon)}\big)^2 = \lim_{m \to \infty} \frac{Var \left(\sum_{t=1}^m (A^t)^{(\epsilon)} \right)}{m}=\gamma^{(\epsilon)}(0)+2\lim_{m \to \infty}\sum_{t=1}^{m}\gamma^{(\epsilon)}(t), \]

where the equality follows from Lemma 3. We will call $\big(\sigma_a^{(\epsilon)}\big)^2$ the effective variance. Assume that for every $t \in \mathbb{N}$ ,

(5) \begin{align} \lim_{\epsilon \to 0}\gamma^{(\epsilon)}(t) = \gamma(t).\end{align}

Define

\begin{align*} \sigma_a^2 = \gamma(0)+2\lim_{m \to \infty}\sum_{t=1}^{m}\gamma(t). \end{align*}

Then we have the following claim, which establishes an interchange of limit, and so we call $\sigma_a^2 $ the limiting effective variance.

Claim 1. $\lim_{\epsilon \to 0} \big(\sigma_a^{(\epsilon)}\big)^2 = \sigma_a^2.$

The claim is proved in Appendix C.

3.2. Heavy-traffic limit of the mean queue length

We now present the generalization of Kingman’s heavy-traffic bound [17] in a single-server queue under Markovian arrivals. In other words, we characterize the steady-state mean queue length in a single-server queue in the heavy-traffic regime.

Theorem 1. Let $(A^t)^{ (\epsilon )}$ be a set of arrival processes determined by the corresponding Markov chains $\left\{(X^t)^{(\epsilon)}\right\}_{\ t\geq 0}$ as described before, with steady-state arrival rates $\lambda^{ (\epsilon )} = \mu -\epsilon$ . Let $\alpha^{ (\epsilon )}$ and $C^{ (\epsilon )} $ be the corresponding geometric mixing parameters as mentioned in Lemma 2. Assume $\sup_\epsilon \alpha^{ (\epsilon )} \leq \alpha <1$ and $\sup_\epsilon C^{ (\epsilon )} \leq C < \infty$ . Then we have the following:

1. 1. For each $\epsilon \in (0,\mu )$ , the two-dimensional Markov chain

   \begin{align*}\Big\{ \Big((Q^t)^{ (\epsilon )},\ (X^t)^{ (\epsilon )} \Big)\Big\}_{t\geq 0 } \end{align*}
   is positive recurrent.

2. 2. Let $\overline{Q}^{ (\epsilon )}$ be a steady-state random variable to which the queue length process $\left\{Q^t\right\}^{ (\epsilon )}_{t \geq 1}$ converges in distribution. We have

   \begin{equation*} \lim_{\epsilon \to 0} E \left[\epsilon \overline{Q}^{ (\epsilon )} \right]=\frac{\sigma_a^2+\sigma_s^2}{2}. \end{equation*}

Proof of Theorem 1. To prove the first part of the theorem, we use m-step Foster–Lyapunov theorem (Proposition 2.2.4 in [7]). We consider the quadratic Lyapunov function, $\left(Q^{(\epsilon)}\right)^2$ , and show that its m-step drift is negative except in a finite set. Consider a fixed $\epsilon \in (0,\mu)$ . For ease of exposition, we suppress the superscript $ ({\cdot})^{(\epsilon )}$ .

Claim 2. For any $\epsilon \in (0,\mu)$ and $m \in \mathbb{N}_+$ ,

\begin{align*} \begin{aligned} & E \left[\left(Q^{t+m}\right)^2-(Q^t)^2\mid \left(Q^t,X^t \right)= (q,x ) \right]\\ & \leq E \left [2Q^t\left(\sum_{i=1}^{m} (A^{t+m-i}-\lambda )\right)-2m\epsilon Q^t+m K_0 (m )\mid \left(Q^t,X^t \right)= (q,x ) \right],\\ \end{aligned}\end{align*}

where

\begin{align*} K_0 (m ) = 2m \big(A_{max}+S_{max} \big) \big(A_{max}+S_{max} \big)+ \big(A_{max}+S_{max} \big)^2.\end{align*}

The proof of Claim 2 is in Appendix D.1.

We now consider the first term on the right-hand side. The main challenge in bounding this term is the correlation between queue length and arrivals at the same time slot, because of the Markovian nature of the arrival process. We use the geometric mixing of the underlying Markov chain as stated in Lemma 2 to get

(6) \begin{align} &E \left[2Q^t \left(A^{t+m}-\lambda \right )\big| \left(Q^t,X^t \right)= (q,x ) \right]\nonumber\\[5pt] &\leq \big\lvert{E \left[2Q^t \left(A^{t+m}-\lambda \right )\big| \left(Q^t,X^t \right)= (q,x ) \right]}\big\rvert \leq 4A_{max}C\alpha^m q .\end{align}

Thus,

\begin{align*} & E \left [2Q^t\left(\sum_{i=1}^{m} \big(A^{t+m-i}-\lambda \big)\right)-2m\epsilon Q^t\mid \left(Q^t,X^t \right)= (q,x ) \right]\\ &\leq 2q \left[ \left(2A_{max}C\frac{1-\alpha^m}{1-\alpha} \right)-m\epsilon \right].\end{align*}

Define

\begin{equation*}m (\epsilon )= \min\left\{m \in \mathbb{N}_+\,:\, 2A_{max}C\frac{1-\alpha^m}{1-\alpha}<\frac{1}{2}m\epsilon \right\}.\end{equation*}

Such an $m (\epsilon )$ exists because $2A_{max}C\frac{1-\alpha^m}{1-\alpha}$ is finite and $\frac{1}{2}m\epsilon \to \infty$ as $m \to \infty$ . Let $K_1(\epsilon) = \frac{\epsilon m(\epsilon)}{2}$ . Then we have

\begin{align*} & E \left[\left(Q^{t+m(\epsilon)}\right)^2-(Q^t)^2\mid \left(Q^t,X^t \right)= (q,x ) \right] \leq -2K_1(\epsilon)q +m(\epsilon) K_0 (m(\epsilon) ).\end{align*}

Let $\mathcal{B} = \left\{q\,:\, q \leq \frac{m(\epsilon) K_0 (m(\epsilon) )}{K_1({\epsilon})}\right\}$ denote a finite set. Then we have

\begin{align*} & E \left[\left(Q^{t+m(\epsilon)}\right)^2-(Q^t)^2\mid \left(Q^t,X^t \right)= (q,x ) \right] \\ &\leq -m(\epsilon) K_0 (m(\epsilon) )\mathcal{I} (q \in \mathcal{B}^c ) + m(\epsilon) K_0 (m(\epsilon) )\mathcal{I}(q \in \mathcal{B}).\end{align*}

The positive recurrence of the two-dimensional Markov chain $\big\{ \big(Q^t,\ X^t \big),\ t\geq 0\big\}$ then follows from the m-step Foster–Lyapunov theorem.

Therefore, using the irreducibility and aperiodicity of the two-dimensional Markov chain $\big\{ \big(Q^t,\ X^t \big),\ t\geq 0\big\}$ , we know that a unique stationary distribution exists. To prove the second part of the theorem, we will set the m-step drift of the quadratic test function to zero under the stationary distribution. In order to do this, we must first make sure that the stationary expectation of the quadratic function is finite, which is given by the following claim.

Claim 3. For any $\epsilon >0$ in steady state,

\begin{align*} E \Big[ \Big(\overline{Q}^{ (\epsilon )} \Big)^2 \Big] < \infty.\end{align*}

The proof of Claim 3 is in Appendix D.2.

In the rest of the proof, we consider the system in its steady state, and so for every time t, $(Q^t)^{(\epsilon)} \stackrel{d}= \overline{Q}^{(\epsilon)}$ (equivalently, this can be thought of as initializing the system in its steady state). For ease of exposition, we again drop the superscript $({\cdot})^{(\epsilon)}$ and just use $Q^t$ . Then $A^t$ denotes the arrivals in steady state, and the queue length at time $t+m$ is

\begin{equation*}Q^{t+m}=Q^t+\sum_{l=0}^{m-1} A^{t+l}-\sum_{l=0}^{m-1} S^{t+l}+\sum_{l=0}^{m-1} U^{t+l},\end{equation*}

which has the same distribution as $Q^t$ for all $m \in \mathbb{N}_+$ . We can set the one-step drift equal to zero:

(7) \begin{align} 0=E \Big[\big(Q^{t+1} \big)^2-\left(Q^{t} \right)^2 \Big]=E \Big[\!\left(Q^t+A^t-S^t+U^t \right)^2-\left(Q^{t} \right)^2 \Big], \end{align}

where the last equation follows from (3). Expanding (7) and applying (4), we have

(8) \begin{align} 2\epsilon E \left[Q^t \right]=E \left[2Q^t (A^t-\lambda ) \right]-E \big[\left(U^t\right)^2 \big] + E \big[ (A^t-\lambda )^2 \big]+\sigma_s^2+ \epsilon^2. \end{align}

Equation (8) can be obtained using standard arguments. The heavy-traffic limit of the scaled queue length $\epsilon E \left[Q^t \right]$ is typically obtained by bounding the right-hand side and then letting $\epsilon \to 0$ . The main challenge here is bounding the $E \left[2Q^t (A^t-\lambda ) \right]$ term, since the queue length and the arrivals are correlated because the arrival process is Markovian. We bound this term by recursively expanding $Q^t$ using (3), and using the Markov chain mixing result from Lemma 2. We then obtain the following claim, the proof of which can be found in Appendix D.3.

Claim 4. For any $\epsilon \in (0,\mu)$ and $m \in \mathbb{N}_+$ , we have

\begin{align*} 2\left(1-2A_{max}C\frac{\alpha^m}{\epsilon}\right) E\left[\epsilon Q^t\right] &\leq \gamma(0) + 2\sum_{i=1}^{m}\gamma(i) + \sigma_s^2 + 2m \big(A_{max}+\lambda \big) \epsilon + \epsilon^2,\\ 2\left(1+2A_{max}C\frac{\alpha^m}{\epsilon}\right) E\left[\epsilon Q^t\right] &\geq \gamma(0) + 2\sum_{i=1}^{m}\gamma(i) + \sigma_s^2- 2m \big(A_{max}+\lambda \big)\epsilon\\& \quad - S_{max}\epsilon + \epsilon^2. \end{align*}

Note that the claim is true for all $\epsilon$ and m. Put ${ (\cdot )}^{ (\epsilon )}$ back. For a given $\epsilon$ , we now set $m = \left\lfloor \frac{1}{\sqrt{\epsilon}} \right\rfloor$ , and we take the limit as $\epsilon \to 0$ to get

(9) \begin{align} \lim_{\epsilon \to 0} E \big[\epsilon\overline{ Q}^{(\epsilon)}\big]=\frac{\lim_{\epsilon \to 0} \gamma^{(\epsilon)}(0) + \lim_{m(\epsilon) \to \infty} 2\sum_{t=1}^{m(\epsilon)}\gamma^{(\epsilon)}(t)+\sigma_s^2}{2}. \end{align}

Discussion. The key challenge in the proof is in handling the $E \left[Q^t (A^t-\lambda ) \right]$ term. When the arrivals are i.i.d., the expectation can simply be written as a product of expectations. Under Markovian arrivals, this cannot be done because of the correlation between the queue length and the arrivals at the same time slot. A multistep drift approach is usually used [26] to overcome this type of difficulty while establishing positive recurrence. We adopt the same approach in the first part of the proof to establish positive recurrence. However, it is unclear whether such a multistep drift argument is refined enough to provide an exact expression for the mean heavy-traffic queue length. So, in the second part of the proof, we simply use the one-step drift, and use a different approach to bound the term $E \left[Q^t (A^t-\lambda ) \right]$ . Essentially, we recursively apply (3) m times to expand $Q^t$ in terms of $Q^{t-m}$ and eventually get a term of the form $E \left[2Q^{t-m} (A^t-\lambda ) \right]$ . Now, for large enough m, $Q^{t-m}$ and $A^t$ are approximately independent, thanks to the fast mixing of the Markov chain underlying the arrival process, and so we can approximate the expectation by the product of expectations. This recursive expansion yields several other terms of the form $E \left[ (A^{t-i}-\lambda ) (A^t-\lambda ) \right]$ , which give us the autocovariance of the arrival process in Claim 4, and eventually in Theorem 1.

Note that for the argument to work, m needs to be chosen carefully. In particular, it should be large enough to ensure independence between the queue length and the arrival; on the other hand, it should be small enough to ensure that the error terms introduced by the recursive expansion are negligible in the heavy-traffic regime. It turns out that any m that is between $\Omega\left( \ln \frac{1}{\epsilon} \right)$ and $O(\frac{1}{\epsilon})$ works, and we choose $m = \left\lfloor \frac{1}{\sqrt{\epsilon}} \right\rfloor$ arbitrarily within the range.

The following claim, which is proved in Appendix D.4, is useful for evaluating

\begin{align*} \lim_{m(\epsilon) \to \infty}\sum_{t=1}^{m(\epsilon)}\gamma^{(\epsilon)}(t). \end{align*}

Claim 5. For any $\epsilon \in (0,\mu)$ and $m(\epsilon) = \left\lfloor \frac{1}{\sqrt{\epsilon}} \right\rfloor$ , we have

(10) \begin{equation} \begin{aligned} \lim_{m(\epsilon) \to \infty}\sum_{t=1}^{m(\epsilon)}\gamma^{(\epsilon)}(t) = \lim_{M \to \infty} \sum_{t=1}^{M} \gamma(t). \end{aligned} \end{equation}

Finally, combining (9) and Claim 5, we have

\begin{equation*} \begin{aligned} \lim_{\epsilon \to 0} E \left[\epsilon \overline{Q}^{(\epsilon)}\right] &=\frac{ 2\lim_{M \to \infty} \sum_{i=1}^{M} \gamma(t)+\lim_{\epsilon \to 0} \gamma^{(\epsilon)}(0) +\sigma_s^2}{2} = \frac{\sigma_a^2+\sigma_s^2}{2}. \end{aligned} \end{equation*}

Note that the key idea in the proof is to consider the m-step drift, where m is chosen to be a function of the heavy-traffic parameter $\epsilon$ . In addition, mixing time bounds on the underlying Markov chain are exploited.

Moreover, we also derive the heavy-traffic limiting distribution of the scaled queue length, which is in Appendix A.

4. Input-queued switch

In this section, we will study an input-queued switch operating under Markovian arrivals, and present an exact characterization of the mean sum of the queue lengths in heavy traffic. We first introduce the mathematical model of a switch under Markovian arrivals, and we present the MaxWeight algorithm. We then establish throughput optimality, state-space collapse, and asymptotically tight upper and lower bounds under the MaxWeight scheduling algorithm, which are proved using the m-step Lyapunov-type drift argument developed in the previous section. For completeness, the universal lower bound with Markovian arrivals under any feasible scheduling algorithm is also presented here.

Note on notation. We adopt the notation and definitions in [22]. We restrict our discussion to Euclidean space $\mathbb{R}^{N^2}$ . For ease of exposition and understanding, we express an element $\boldsymbol{x}$ of $\mathbb{R}^{N^2}$ in two equivalent ways: first, as an $N^2$ -dimensional vector, which is the standard representation in Euclidean space; and second, as an $N\times N$ matrix, with the (i, j) element denoted by $\boldsymbol{x}_{ij}$ . For any two vectors $\boldsymbol{x}$ and $\boldsymbol{y}$ , the inner product is defined by

\begin{equation*} \left\langle \boldsymbol{x}, \boldsymbol{y} \right \rangle \triangleq \sum_{i=1}^N\sum_{j=1}^N x_{ij}y_{ij}.\end{equation*}

We say that $\boldsymbol{X}=\boldsymbol{Y}$ if $X_{ij}=Y_{ij}$ for all $i,j \in\{1,2,\ldots, N\}$ . The vector consisting of all ones is denoted by ${\textbf{1}}$ . Define $\boldsymbol{e}^{(i)}$ as the matrix with ones in the ith row and zeros everywhere else; similarly, $\tilde{\boldsymbol{e}}^{(j)}$ is the matrix with ones in the jth column and zeros everywhere else. That is,

(11) \begin{equation} \begin{aligned} &\boldsymbol{e}^{(i)}_{i,j}=1\ \forall j, &\boldsymbol{e}^{(i)}_{i^{\prime},j}=0\ \forall i^{\prime}\neq i,\ \forall j;\\ &\tilde{\boldsymbol{e}}^{(j)}_{i,j}=1\ \forall i, &\tilde{\boldsymbol{e}}^{(j)}_{i,j^{\prime}}=0\ \forall j^{\prime}\neq j,\ \forall i.\\ \end{aligned}\end{equation}

4.1. Mathematical model of a switch

An $ N \times N $ crossbar switch, also known as an input-queued switch, has N input ports and N output ports with a separate queue for each input–output pair. Such a system can be modeled as an $N\times N$ matrix of queues, where the (i, j)th queue corresponds to packets entering input port i and intended for output port j. The four key elements in the mathematical model of a switch under Markovian arrivals are as follows:

• • $\boldsymbol{A}^t \in \mathbb{R}^{N^2}$ : the vector of all arrivals at time slot t, of which the (i, j)th element corresponds to the number of packets arriving at the ith input port and to be delivered to the jth output port.

• • $\boldsymbol{S}^t \in \mathbb{R}^{N^2}$ : the vector of all services at time slot t. In each time slot, in each column and row, at most one queue can be served and the service is at most 1.

• • $\boldsymbol{U}^t \in \mathbb{R}^{N^2}$ : the vector of unused services at time slot t.

• • $\boldsymbol{Q}^t \in \mathbb{R}^{N^2}$ : the vector of all queue lengths at time slot t.

The arrival process $A_{ij}^t$ is determined by an underlying Markov chain $\left\{\boldsymbol{X}^t\right\}_{t\geq 0 }$ , with $A_{ij}^t= {{}f_{ij}} \big(X_{ij}^t \big)$ . The multidimensional Markov chain $\left\{\boldsymbol{X}^t\right\}_{t\geq 0 }$ is assumed to be irreducible, positive recurrent, and aperiodic on a finite state space $\Omega$ . Thus $\left\{\boldsymbol{X}^t\right\}_{t\geq 0}$ converges to its stationary distribution $\boldsymbol{\pi}$ with geometric rate. Let $\boldsymbol{f}=({{}f_{ij}})$ and $\boldsymbol{\lambda} = E \big[\overline{\boldsymbol{A}} \big] = E \big[\boldsymbol{f} \big(\overline{\boldsymbol{X}} \big) \big]$ , where $\overline{\boldsymbol{A}}$ and $\overline{\boldsymbol{X}}$ are the steady-state variables to which $\boldsymbol{A}^t$ and $\boldsymbol{X}^t$ converge in distribution.

The set of feasible schedules $\mathcal{S}$ can be written as

\begin{equation*} \mathcal{S} = \left\{\boldsymbol{s} \in\{0,1\}^{N^2}\,:\, \sum_{i=1}^N s_{ij}\leq 1, \sum_{j=1}^N s_{ij}\leq 1\ \forall i,j\in\{1,2,\ldots, N\} \right\}.\end{equation*}

The system operates as follows.

At the beginning of every time slot, the service $\boldsymbol{S}^t$ is determined based on the queue length $\boldsymbol{Q}^t$ , according to the scheduling algorithm. Then the arrivals $\boldsymbol{A}^t$ occur according to the underlying Markov chain. Finally the packets are served; this may result in an unused service if there are no packets in a scheduled queue. The queue length evolves as follows:

\begin{equation*} \begin{aligned} Q_{ij}^{t+1} & = \big[Q_{ij}^t+A_{ij}^t-S_{ij}^t\big]^+=Q_{ij}^t+A_{ij}^t-S_{ij}^t +U_{ij}^t, \end{aligned}\end{equation*}

or

\begin{equation*} \boldsymbol{Q}^{t+1} = \boldsymbol{Q}^{t}+ \boldsymbol{A}^{t}-\boldsymbol{S}^{t}+\boldsymbol{U}^t,\end{equation*}

where $[x]^+ = \max\!(0,x)$ . Assume that the Markov chain $\left\{\left(\boldsymbol{Q}^t,\boldsymbol{X}^t\right)\right\}_{t\geq 0 }$ is irreducible.

For the unused service $\boldsymbol{U}^t$ , we have the following natural constraints on $U_{ij}^t$ :

\begin{gather*} U_{ij}^t \leq S_{ij}^t,\\ \sum_{i}U_{ij}^t \in \{0,1\}\ \forall j \in \{1,2,\ldots,N\},\\ \sum_{j}U_{ij}^t \in \{0,1\}\ \forall i \in \{1,2,\ldots,N\}.\end{gather*}

Moreover, for all $i,j \in\{1,2,\ldots,N\}$ we have

\begin{equation*} U_{ij}^t A_{ij}^t =0,\ \ \ U_{ij}^t {{}Q_{ij}^t} =0,\ \ \ U_{ij}^t Q_{ij}^{t+1} =0.\end{equation*}

The first two equations can be derived as follows. If $U^t_{ij}=0$ , then $U^t_{ij}A^t_{ij}=0$ and $U^t_{ij}Q^t_{ij}=0$ . Conversely, if $U^t_{ij}\neq0$ , we know that the service is at most 1, so $U^t_{ij}=1$ . Considering the system operation, the only possible case is when the queue length at the current time slot is zero $\big(Q_{ij}^t = 0\big)$ and there are no arrivals during the current time slot $\big(A_{ij}^t = 0\big)$ . Consequently, we have $U^t_{ij}A^t_{ij}=0$ and $U^t_{ij}Q^t_{ij}=0$ .

4.2. MaxWeight algorithm

The MaxWeight algorithm is a well-studied scheduling algorithm for switches [30]. In each time slot, the MaxWeight algorithm picks a service vector $S^t$ such that the weighted summation of service is maximized, where the weight vector is the current queue length vector, i.e.,

\begin{equation*} \boldsymbol{S}^t = \arg \max_{\boldsymbol{s}\in \mathcal{S}} \sum_{ij}Q_{ij}(t)s_{ij} = \arg \max_{\boldsymbol{s}\in \mathcal{S}}\big\langle \boldsymbol{Q}^t, \boldsymbol{s}\big\rangle.\end{equation*}

In the MaxWeight algorithm, ties are broken uniformly at random. The set of maximal feasible schedules or perfect matchings, $\mathcal{S}^*$ , is defined as follows:

\begin{equation*} \mathcal{S}^* = \left\{\boldsymbol{s} \in\{0,1\}^{N^2}\,:\, \sum_{i=1}^N s_{ij}= 1, \sum_{j=1}^N s_{ij} = 1\ \forall i,j\in\{1,2,\ldots, N\} \right\}.\end{equation*}

Without loss of generality, we assume that the MaxWeight algorithm always picks a perfect matching, i.e.,

\begin{equation*} \boldsymbol{S}^t \in \mathcal{S}^*,\ \forall t>0.\end{equation*}

Note that this is without loss of generality because under the MaxWeight scheduling algorithm, we can always choose the maximal schedule. Only when the queue length at some queue (i, j) is zero do we have $s_{ij} = 0$ and $s^*_{ij}=1$ . In this case, we can pretend that $s_{ij} = 1$ and $u_{ij} = 1$ .

Once a Markovian scheduling algorithm is fixed, the switch can be modeled by the Markov chain $\left\{\left(\boldsymbol{Q}^t,\boldsymbol{X}^t\right)\right\}_{t\geq 0 }$ . We assume that the arrival process is such that under the MaxWeight algorithm, this Markov chain is irreducible and aperiodic. A switch is said to be stable under a scheduling algorithm if the Markov chain $\left\{\left(\boldsymbol{Q}^t,\boldsymbol{X}^t\right)\right\}_{t\geq 0 }$ is positive recurrent. The capacity region is defined as the set of arrival rates $\boldsymbol{\lambda}$ under which the switch is stabilizable by some algorithm.

For a switch under i.i.d. arrivals, it is known [30] that the capacity region $\mathcal{C}$ is the convex hull of the feasible schedule set, i.e., $\mathcal{C} = \text{Conv}(\mathcal{S})$ . It can also be written as

\begin{equation*} \begin{aligned} \mathcal{C} & = \left\{\boldsymbol{\lambda} \in \mathbb{R}^{N^2}_+\,:\, \sum_{i=1}^N \lambda_{ij}\leq 1,\sum_{j=1}^N \lambda_{ij} \leq 1\ \forall i,j \in \{1,2,\ldots,N\} \right\}\\ & = \left\{\boldsymbol{\lambda} \in \mathbb{R}^{N^2}_+\,:\, \big\langle \boldsymbol{\lambda}, \boldsymbol{e}^{(i)} \big\rangle\leq1, \big\langle \boldsymbol{\lambda}, \boldsymbol{\tilde{e}}^{(j)} \big\rangle \leq1\ \forall i,j \in \{1,2,\ldots,N\} \right\}. \end{aligned}\end{equation*}

If a scheduling algorithm stabilizes the switch under any arrival rate in the capacity region, then it is said to be throughput optimal. Moreover, it is known that the MaxWeight algorithm is throughput optimal [30]. We will establish similar results under Markovian arrivals in Section 4.3. Before that, we present some geometric observations about the capacity region from [22].

4.2.1. Some geometric observations

The capacity region $\mathcal{C}$ is a convex polytope with dimension $N^2$ . Let $\mathcal{F}$ denote the face of $\mathcal{C}$ where all input and output ports are all saturated, defined by

\begin{equation*} \begin{aligned} \mathcal{F} & = \left\{\boldsymbol{\lambda} \in \mathbb{R}^{N^2}_+\,:\, \sum_{i=1}^N \lambda_{ij}= 1,\sum_{j=1}^N \lambda_{ij}= 1 \forall i,j \in \{1,2,\ldots,N\} \right\}\\ & = \left\{\boldsymbol{\lambda} \in \mathbb{R}^{N^2}_+\,:\, \big\langle \boldsymbol{\lambda}, \boldsymbol{e}^{(i)} \big\rangle = 1, \big\langle \boldsymbol{\lambda}, \boldsymbol{\tilde{e}}^{(j)} \big\rangle = 1\ \forall i,j \in \{1,2,\ldots,N\} \right\}. \end{aligned}\end{equation*}

Note that $\mathcal{F} = \text{Conv}(\mathcal{S^*})$ . Let $\mathcal{K}$ denote the normal cone of the face $\mathcal{F}$ , which can be written explicitly as

\begin{equation*} \mathcal{K} = \left\{ \boldsymbol{x} \in \mathbb{R}^{N^2}\,:\, \boldsymbol{x} = \sum_{i=1} ^N w_i\boldsymbol{e}^{(i)}+\sum_{j=1} ^N \tilde{w}_j\tilde{\boldsymbol{e}}^{(j)},\ w_i, \tilde{w}_j \in \mathbb{R}_+ \forall i,j\right\}. \end{equation*}

It can be verified that this is indeed the normal cone, and so, for all $\boldsymbol{x},\boldsymbol{y} \in \mathcal{F}$ and all $\boldsymbol{z} \in \mathcal{K}$ , we have

(12) \begin{equation} \left\langle \boldsymbol{x}-\boldsymbol{y},\boldsymbol{z}\right\rangle =0. \end{equation}

The polar cone $\mathcal{K}^o$ of the cone $\mathcal{K}$ is defined as

\begin{equation*} \mathcal{K}^o = \Big\{ \boldsymbol{x} \in \mathbb{R}^{N^2}\,:\, \left\langle\boldsymbol{x},\boldsymbol{y}\right\rangle\leq 0 \ \forall \boldsymbol{y}\in \mathcal{K} \Big\}.\end{equation*}

Let $\mathcal{L}$ denote the subspace spanned by the cone $\mathcal{K}$ :

\begin{equation*} \mathcal{L} = \left\{ \boldsymbol{x} \in \mathbb{R}^{N^2}\,:\, \boldsymbol{x} = \sum_{i=1} ^N w_i\boldsymbol{e}^{(i)}+\sum_{j=1} ^N \tilde{w}_j\tilde{\boldsymbol{e}}^{(j)},\ \text{where} \ w_i,\ \tilde{w}_j \in \mathbb{R},\ \forall i,j\right\}, \end{equation*}

For any $ \boldsymbol{x} \in \mathbb{R}^{N^2}$ and any convex set $\mathcal{W}$ , the projection of $\boldsymbol{x}$ onto the set $\mathcal{W}$ is denoted by $\boldsymbol{x}_{{\parallel} \mathcal{W}}$ and defined as

\begin{equation*} \boldsymbol{x}_{{\parallel} \mathcal{W}} = \arg\min_{\boldsymbol{y} \in \mathcal{W}}\lvert\lvert{\boldsymbol{y} - \boldsymbol{x}}\rvert\rvert;\end{equation*}

consequently,

\begin{equation*} \boldsymbol{x}_{{\perp} \mathcal{W}} = \boldsymbol{x}- \boldsymbol{x}_{{\parallel} \mathcal{W}}.\end{equation*}

The projection of $ \boldsymbol{x}$ onto the subspace $\mathcal{L}$ is given by

\begin{equation*} \left(\boldsymbol{x}_{{{\parallel}\mathcal{L}}}\right)_{ij} = \frac{\sum_{i}{x}_{ij}}{N} + \frac{\sum_{j}{x}_{ij}}{N} - \frac{\sum_{ij} {x}_{ij}}{N^2},\end{equation*}

and its $\ell_2$ norm is

\begin{equation*} \lvert\lvert{\boldsymbol{x}_{{\parallel}\mathcal{L}} }\rvert\rvert^2= \frac{1}{N}\Bigg( \sum_j \Bigg( \sum_{i}{x}_{ij}\Bigg)^2 + \sum_i \Bigg(\sum_{j}{x}_{ij}\Bigg)^2 - \frac{1}{N} \Bigg(\sum_{ij}{x}_{ij}\Bigg)^2 \Bigg).\end{equation*}

For any $\boldsymbol{x}_{{\parallel}\mathcal{L}}$ and $\boldsymbol{y}_{{\parallel}\mathcal{L}}$ , we have

(13) \begin{align} \big\langle \boldsymbol{x}_{{\parallel}\mathcal{L}}, \boldsymbol{y}_{{\parallel}\mathcal{L}}\big\rangle = \big\langle \boldsymbol{x}, \boldsymbol{y}_{{\parallel}\mathcal{L}}\big\rangle = \sum_{ij}x_{ij}\left[\frac{1}{N}\sum_{j^{\prime}}y_{ij^{\prime}}+\frac{1}{N}\sum_{i^{\prime}}y_{i^{\prime}j}-\frac{1}{N^2}\sum_{i^{\prime}j^{\prime}}y_{i^{\prime}j^{\prime}}\right].\end{align}

4.3. Throughput optimality

In this section, we show that under Markovian arrivals, $\mathcal{C}$ is indeed the capacity region, and MaxWeight is throughput optimal.

Proposition 1. If $\lambda \notin \mathcal{C}$ , then no scheduling algorithm can support arrival rate matrix $\boldsymbol{\lambda}$ .

The proof follows from Theorem 4.2.1 in [30], using the Markov chain ergodic theorem instead of the strong law of large numbers.

Proposition 2. For an input-queued switch operating under Markovian arrivals, the MaxWeight scheduling algorithm can support any arrival rate matrix $\boldsymbol{\lambda}$ in the interior of $\mathcal{C}$ , i.e., $\boldsymbol{\lambda}\in int(\mathcal{C})$ . Thus, MaxWeight is throughput optimal.

Proof. Note that $\left\{\left(\boldsymbol{Q}^t,\boldsymbol{X}^t\right)\right\}_{t\geq 0 }$ is an irreducible Markov chain under MaxWeight scheduling. We prove this theorem by demonstrating that $\left\{\left(\boldsymbol{Q}^t,\boldsymbol{X}^t\right)\right\}_{t\geq 0 }$ is positive recurrent, which can be done using the Foster–Lyapunov theorem (Proposition 2.2.4 in [7]). Consider the Lyapunov function

\begin{equation*} V \left(\boldsymbol{Q}^t,\boldsymbol{X}^t \right)=\lvert\lvert{\boldsymbol{Q}^t}\rvert\rvert^2.\end{equation*}

We will consider the m-step drift of this Lyapunov function, and bound it as follows.

Claim 6. Let $C_{max} = \max_{ij}C_{ij}$ and $\alpha_{max} = \max_{ij}\alpha_{ij}$ , where $C_{ij}$ and $\alpha_{ij}$ are the geometric mixing parameters given by Lemma 2 for the (i, j)th underlying Markov chain $\big\{ X^t_{ij} \big\}_{t\geq 0}$ . There exists $\epsilon >0$ such that $\boldsymbol{\lambda}+\epsilon {\textbf{1}} \in \mathcal{C}$ . Let

\begin{align*} m(\epsilon ) = \min \left\{m \in \mathbb{N}_+\mid 2NA_{max}C_{max}\frac{1-\alpha_{max}^m}{1-\alpha_{max}} < \frac{m\epsilon }{2} \right\}; \end{align*}

then

\begin{equation*} \begin{aligned} & E \left[V \left(\boldsymbol{Q}^{t+m(\epsilon)} , \boldsymbol{X}^{t+m(\epsilon)} \right)-V \left(\boldsymbol{Q}^t,\boldsymbol{X}^t \right)\mid \left(\boldsymbol{Q}^t ,\boldsymbol{X}^t \right)=(\boldsymbol{q},\boldsymbol{x}) \right]\\ & \leq -\frac{m(\epsilon )\epsilon }{2}\lvert\lvert{\boldsymbol{q} }\rvert\rvert+\frac{K_2 (m(\epsilon ) )}{2} , \end{aligned} \end{equation*}

where

\begin{align*} K_2 (m(\epsilon ) ) & = m(\epsilon )N^2 \big(A_{max}+S_{max} \big)^2\\ & \quad + 2m(\epsilon )^2 N^2 \big(A_{max}+S_{max}\big)\big(\epsilon +A_{max}+\lambda_{max} \big). \end{align*}

The theorem then follows from the Foster–Lyapunov theorem (Proposition 2.2.4 in [7]). A detailed proof of the claim is in Appendix E.

4.4. Heavy-traffic analysis

We will now study the switch in heavy traffic, as the arrival rate approaches the face $\mathcal{F}$ on the boundary of the capacity region $\mathcal{C}$ . To this end, consider $\left\{\boldsymbol{X}^t\right\}^{ (\epsilon )}_{t\geq 0}$ , a set of irreducible, positive recurrent, and aperiodic underlying vector-valued Markov chains indexed by the heavy-traffic parameter $\epsilon \in (0,1)$ taking values in $\Omega^{N^2}$ . The arrival process for the system indexed by $\epsilon$ is given by $\big(A_{ij}^t\big)^{(\epsilon)} = {{}f_{ij}}\big(\big(X_{ij}^t\big)^{(\epsilon)}\big)$ for a non-negative-valued function ${{}f_{ij}}({\cdot})$ . For any fixed $\epsilon$ , let $\overline{\boldsymbol{X}}^{ (\epsilon )}$ be the steady-state variable to which $\left(\boldsymbol{X}^t\right)^{ (\epsilon )}$ converges in distribution, with $E\big[\overline{\boldsymbol{A}}^{(\epsilon)} \big] = E\big[\boldsymbol{f}\big(\overline{\boldsymbol{X}}^{ (\epsilon )}\big)\big] = \boldsymbol{\lambda}^{(\epsilon)} = (1 -\epsilon)\boldsymbol{v}$ , where $\boldsymbol{v}$ is an arrival rate on the boundary of the capacity region $\mathcal{C}$ such that $v_{ij} > 0$ for all i, j, and all the input and output ports are saturated. In other words, we assume $\boldsymbol{v} \in \mathcal{F}$ . Let $\gamma_{ij,kl}^{(\epsilon)}(t)$ be the spatiotemporal correlation function of the arrival process between the ijth port at time t and the klth port at time 0, starting from steady state $\boldsymbol{X}^{\textbf{0}} \stackrel{d}{=}\overline{\boldsymbol{X}}^{ (\epsilon )}$ , i.e.,

\[ {} \gamma_{ij,kl}^{(\epsilon)}(t) = E \Big[ \Big(\big(A_{ij}^t\big)^{(\epsilon)}-\lambda_{ij} \Big) \Big(\big(A_{kl}^0\big)^{(\epsilon)}-\lambda_{kl} \Big) \Big]. \]

Assume that for all $t \in \mathbb{N}$ ,

(14) \begin{equation} {} \lim_{\epsilon \to 0}\gamma_{ij,kl}^{(\epsilon)}(t) = \gamma_{ij,kl}(t).\end{equation}

Let

\[{} \sigma_{ij,kl}^2 = \gamma_{ij,kl}(0)+2\lim_{m \to \infty}\sum_{t=1}^{m}\gamma_{ij,kl}(t), \]

and let $\boldsymbol{\sigma}=(\sigma_{ij,kl}) \in \mathbb{R}^{N^2\times N^2}$ be the limiting effective covariance matrix. For any scheduling algorithm under which the switch system is stable, let $\Big( \big(\overline{\boldsymbol{Q}}\big)^{(\epsilon )},\big(\overline{\boldsymbol{X}}\big)^{(\epsilon )} \Big)$ be a steady-state random variable to which the process $\left\{ \left( \left(\boldsymbol{Q}^t \right)^{(\epsilon)},\left(\boldsymbol{X}^t \right)^{(\epsilon)} \right)\right\}_{t\geq 0}$ converges in distribution. Assume that for any $\epsilon \in (0,1)$ and for any i, j, $\sup_\epsilon \alpha^{(\epsilon)}_{ij}<\alpha_{max}<1$ and $\sup_{\epsilon}C^{(\epsilon)}_{ij} < C_{max} < \infty$ .

4.4.1. Universal lower bound

In this section, we will give a lower bound on the average queue length under heavy traffic, which is valid under any stable scheduling algorithm.

Proposition 3. Consider a set of switch systems parameterized by the heavy-traffic parameter $\epsilon\in (0,1)$ as described before. Consider a scheduling algorithm under which the switch system is stable. Then, under heavy traffic, we have

\begin{equation*} \liminf_{\epsilon \to 0} \epsilon E\Bigg[\sum_{ij}\overline{\boldsymbol{Q}^{(\epsilon)}} \Bigg] \geq \frac{\lvert\lvert{\boldsymbol{\sigma}}\rvert\rvert^2}{2}. \end{equation*}

Using a coupling argument, it was shown in [22] that the row sum of the queue lengths under any policy is bounded below by a single-server queue with an arrival process that is the sum of the arrivals to all the queues in the row. The result then follows from using Theorem 1 for a single-server queue, and so we omit the proof.

4.4.2. State-space collapse under MaxWeight policy

A key step in characterizing the heavy-traffic behavior is to establish state-space collapse. It was shown in [22] that under the MaxWeight algorithm, the queue lengths collapse into the cone $\mathcal{K}$ in heavy traffic. In this subsection, we establish the same result under Markovian arrivals. More formally, we show that under the MaxWeight algorithm, $\overline{\boldsymbol{q}}_{{\perp\mathcal{K}}}^{(\epsilon)}$ can be bounded by some constant independent of $\epsilon$ . Thus, when the heavy-traffic parameter $\epsilon$ goes to zero (the mean arrival rate vector $\boldsymbol{\lambda}$ approaches the boundary $\mathcal{F}$ of the capacity region $\mathcal{C}$ ), $\overline{\boldsymbol{q}}_{{\perp\mathcal{K}}}^{(\epsilon)}$ is negligible compared to $\overline{\boldsymbol{q}}_{{\parallel\mathcal{K}}}^{(\epsilon)}$ .

We define the following quadratic Lyapunov functions and their corresponding m-step drifts:

\begin{align*} V (\boldsymbol{q},\boldsymbol{x} ) & \triangleq \lvert\lvert{\boldsymbol{q}}\rvert\rvert^2 = \sum_{ij}q_{ij}^2, &W_{{\perp\mathcal{K}}} (\boldsymbol{q},\boldsymbol{x} ) &\triangleq \lvert\lvert{\boldsymbol{q}_{\perp\mathcal{K}}}\rvert\rvert, \\ V_{\perp\mathcal{K}} (\boldsymbol{q},\boldsymbol{x} ) &\triangleq \lvert\lvert{\boldsymbol{q}_{\perp\mathcal{K}}}\rvert\rvert^2 = \sum_{ij}q_{{\perp\mathcal{K}} ij}^2, &V_{\parallel\mathcal{K}} (\boldsymbol{q} ,\boldsymbol{x} ) &\triangleq \lvert\lvert{\boldsymbol{q}_{\parallel\mathcal{K}}}\rvert\rvert^2 = \sum_{ij}q_{{\parallel\mathcal{K}} ij}^2,\end{align*}

\begin{equation*} \begin{aligned} & \Delta^m V (\boldsymbol{q},\boldsymbol{x} ) \triangleq \left[V \left(\boldsymbol{Q}^{t+m },\boldsymbol{X}^{t+m} \right)-V \left(\boldsymbol{Q}^t,\boldsymbol{X}^t \right) \right] \mathcal{I} \left( (\boldsymbol{Q}^t ,\boldsymbol{X}^t \right) = (\boldsymbol{q},\boldsymbol{x} ) ),\\ & \Delta^m W_{\perp\mathcal{K}} (\boldsymbol{q},\boldsymbol{x} ) \triangleq \left[W_{\perp\mathcal{K}} \left( \boldsymbol{Q}^{t+m},\boldsymbol{X}^{t+m} \right) -W_{\perp\mathcal{K}} \left(\boldsymbol{Q}^t ,\boldsymbol{X}^t \right) \right] \mathcal{I} \left( \left(\boldsymbol{Q}^t ,\boldsymbol{X}^t \right) = (\boldsymbol{q},\boldsymbol{x} ) \right),\\ & \Delta^m V_{\perp\mathcal{K}} (\boldsymbol{q},\boldsymbol{x} ) \triangleq \left[V_{\perp\mathcal{K}} \left(\boldsymbol{Q}^{t+m} ,\boldsymbol{X}^{t+m} \right)-V_{\perp\mathcal{K}} \left(\boldsymbol{Q}^t ,\boldsymbol{X}^t \right) \right] \mathcal{I} \left( \left(\boldsymbol{Q}^t ,\boldsymbol{X}^t \right ) = (\boldsymbol{q},\boldsymbol{x} ) \right),\\ & \Delta^m V_{\parallel\mathcal{K}} (\boldsymbol{q} ,\boldsymbol{x} ) \triangleq \left[V_{\parallel\mathcal{K}} \left(\boldsymbol{Q}^{t+m},\boldsymbol{X}^{t+m} \right)-V_{\parallel\mathcal{K}} \left(\boldsymbol{Q}^t ,\boldsymbol{X}^t \right) \right] \mathcal{I} \left( \left(\boldsymbol{Q}^t ,\boldsymbol{X}^t \right) = (\boldsymbol{q},\boldsymbol{x} ) \right).\\ \end{aligned}\end{equation*}

The next proposition gives the state-space collapse.

Proposition 4. Consider a set of switch systems under the MaxWeight scheduling algorithm, parameterized by the heavy-traffic parameter $0<\epsilon<1$ as described before. Further assume that $v_{\min} \triangleq \min_{ij}v_{ij}>0$ . Then, for each system with $\epsilon < v_{\min}/2\lvert\lvert{\boldsymbol{v}}\rvert\rvert$ , the steady-state queue length vector satisfies

\begin{equation*} E \left[\Big\lvert\Big\lvert{\left(\overline{\boldsymbol{Q}}_{\perp\mathcal{L}} \right)^{(\epsilon )}}\Big\rvert\Big\rvert^2 \right]\leq E \left[\Big\lvert\Big\lvert{\left(\overline{\boldsymbol{Q}}_{\perp\mathcal{K}} \right)^{(\epsilon )}}\Big\rvert\Big\rvert^2 \right] \leq K^{\star\star}, \end{equation*}

where $K^{\star\star}$ is a constant that does not depend on $\epsilon$ .

To prove the proposition, we need the following two lemmas.

Lemma 4. Under the MaxWeight algorithm, for any $\boldsymbol{q} \in \mathbb{R}^{N^2}$ ,

\begin{equation*} \boldsymbol{v} +\frac{v_{\text{min}}}{\lvert\lvert{\boldsymbol{q}_{\perp\mathcal{K}}}\rvert\rvert}\boldsymbol{q}_{\perp\mathcal{K}} \in \mathcal{C}. \end{equation*}

This lemma was proved in [22, Claim 2].

Lemma 5. The drift of $W_{{\perp\mathcal{K}}} (\cdot )$ can be bounded in terms of the drift of $V (\cdot )$ and $V_{\parallel\mathcal{K}} (\cdot )$ as follows:

\begin{equation*} \Delta^m W_{\perp\mathcal{K}} (\boldsymbol{q},\boldsymbol{x} ) \leq \frac{1}{2\lvert\lvert{\boldsymbol{q}_{\perp\mathcal{K}}}\rvert\rvert} \left(\Delta^m V (\boldsymbol{q},\boldsymbol{x} )-\Delta^m V_{\perp\mathcal{K}} (\boldsymbol{q},\boldsymbol{x} ) \right), \quad \forall \left(\boldsymbol{q},\boldsymbol{x}\right) \in \boldsymbol{R}^{N^2}. \end{equation*}

The proof of this lemma is almost identical to that of Lemma 7 in [6], and so we skip it here.

Proof of Proposition 4. For ease of exposition, the superscript $\epsilon$ in this proof is skipped, i.e., we will use $\boldsymbol{Q}^t$ and $\lambda$ to denote $\left(\boldsymbol{Q}^t\right)^{(\epsilon)}$ and $\boldsymbol{\lambda}^{(\epsilon)}$ respectively. The proof is based on applying Lemma 1, by verifying that the three conditions are satisfied. We start with the following claim, which is proved in Appendix F.1.

Claim 7. For any $m\in \mathbb{N}_+$ ,

\begin{equation*} \begin{aligned} {\lvert{ \Delta^m W_{\perp\mathcal{K}} (\boldsymbol{q},\boldsymbol{x} )}\rvert \leq m \lvert{ \Delta W_{\perp\mathcal{K}} (\boldsymbol{q},\boldsymbol{x} )}\rvert \leq N m \big(A_{max}+S_{max} \big).} \end{aligned} \end{equation*}

Therefore, Conditions 2 and 3 are satisfied with $D(m) = Nm\big(A_{max}+S_{max}\big)$ and $\hat{D}(t_0) =N \big(A_{max}+S_{max} \big) $ . To verify Condition 1, we need the following claim, which is proved in Appendix F.2.

Claim 8. For any $m\in \mathbb{N}_+$ ,

\begin{equation*} \begin{aligned} &E \left[\Delta^m W_{\perp\mathcal{K}} (\boldsymbol{q},\boldsymbol{x} ) \mid \left(\boldsymbol{Q}^t ,\boldsymbol{X}^t \right) = (\boldsymbol{q},\boldsymbol{x} )\right]\\ & \leq E \left[\sum_{l=1}^m\big\lvert\big\lvert{\boldsymbol{A}^{t+m-l} -\boldsymbol{\lambda}}\big\rvert\big\rvert \mid \left(\boldsymbol{Q}^t ,\boldsymbol{X}^t \right) = (\boldsymbol{q},\boldsymbol{x} ) \right]+ \frac{K_3(m)}{2\lvert\lvert{\boldsymbol{q}_{\perp\mathcal{K}} }\rvert\rvert}+m \big(\epsilon\lvert\lvert{\boldsymbol{v}}\rvert\rvert-v_{\min} \big),\\ \end{aligned} \end{equation*}

where

\begin{equation*} \begin{aligned} K_3(m) &= 2Nm^2\big(A_{max}+S_{max} \big) \big(N\big(A_{max}+\lambda\big)+\epsilon\lvert\lvert{\boldsymbol{v}}\rvert\rvert +v_{\min} \big)\\&+N^2m \big(A_{max}+S_{max} \big)^2. \end{aligned} \end{equation*}

We can use Lemma 2 to bound the first term on the right-hand side above as follows:

\begin{equation*} \begin{aligned} &E \left[\sum_{l=1}^m\big\lvert\big\lvert{\boldsymbol{A}^{t+m-l} -\boldsymbol{\lambda}}\big\rvert\big\rvert\mid \left(\boldsymbol{Q}^t ,\boldsymbol{X}^t \right) = (\boldsymbol{q},\boldsymbol{x} ) \right] \\ &\leq \sum_{l=1}^{m}\sqrt{\sum_{ij} 4A_{max}^2C_{ij}^2\alpha_{ij}^{2 (m-l )}}\\ & \leq \sum_{l=0}^{m-1}2N A_{max} C_{max}\alpha_{max}^l\\ & = 2N A_{max} C_{max} \frac{1-\alpha_{max}^m}{1-\alpha_{max}}.\\ \end{aligned} \end{equation*}

Let

\begin{equation*} \begin{aligned} &m_0 = \min\Bigg \{m \in \mathbb{N}_+ \mid \frac{2 N\ A_{max} C_{max}}{1-\alpha_{max}} \leq \frac{m v_{\min}}{4} \Bigg \}. \end{aligned} \end{equation*}

Clearly, such an $m_0 \in \mathbb{N}_+$ exists.

Therefore, for $m\geq m_0$ we have

\begin{align*} E \left[\sum_{l=1}^m\big\lvert\big\lvert{\boldsymbol{A}^{t+m-l} -\boldsymbol{\lambda}}\big\rvert\big\rvert\mid \left(\boldsymbol{Q}^t ,\boldsymbol{X}^t \right) = (\boldsymbol{q},\boldsymbol{x} ) \right] \leq \frac{m v_{\min}}{4}.\end{align*}

Combining this with Claim 8, when $\epsilon \leq \frac{v_{\min}}{4\lvert\lvert{\boldsymbol{v}}\rvert\rvert}$ , we have

\begin{equation*} \begin{aligned} E \left[\Delta^{m_0} W_{\perp\mathcal{K}} (\boldsymbol{q},\boldsymbol{x} ) \mid \left(\boldsymbol{Q}^t ,\boldsymbol{X}^t \right) = (\boldsymbol{q},\boldsymbol{x} ) \right] &\leq \frac{K_3(m_0)}{2\lvert\lvert{\boldsymbol{q}_{\perp\mathcal{K}} }\rvert\rvert} -\frac{m_0 v_{\min}}{2} \leq -\frac{v_{\min}}{4}, \end{aligned} \end{equation*}

for all $\boldsymbol{q}\ \text{such that}\ W_{\perp\mathcal{K}} (\boldsymbol{q},\boldsymbol{x} )\geq \frac{2K_3 (m_0 )}{m_0v_{\min}}$ . Let

\begin{align*} Z (\boldsymbol{q},\boldsymbol{x} ) = W_{\perp\mathcal{K}} (\boldsymbol{q},\boldsymbol{x} ). \end{align*}

Define $\kappa(m_0) = \frac{2K_3 (m_0 )}{m_0v_{\min}}$ , $\eta = \frac{v_{\min}}{4}$ , $D(m_0) = N m_0 \big(A_{max}+S_{max} \big)$ , and $\hat{D}(t_0) = N\big(A_{max}+S_{max} \big)$ . This verifies the three conditions in Lemma 1. We have that there exists a $K^{\star\star}(m_0)$ such that

\begin{equation*} E \left[\Big\lvert\Big\lvert{\left(\overline{\boldsymbol{Q}}_{\perp\mathcal{K}} \right)^{(\epsilon )}}\Big\rvert\Big\rvert^2 \right] \leq K^{\star\star}(m_0). \end{equation*}

Since $\mathcal{K} \in \mathcal{L}$ , we conclude that

\begin{align*} E \left[\Big\lvert\Big\lvert{\left(\overline{\boldsymbol{Q}}_{\perp\mathcal{L}} \right)^{(\epsilon )}}\Big\rvert\Big\rvert^2 \right] \leq E \left[\Big\lvert\Big\lvert{\left(\overline{\boldsymbol{Q}}_{\perp\mathcal{K}} \right)^{(\epsilon )}}\Big\rvert\Big\rvert^2 \right] \leq K^{\star\star}(m_0). \end{align*}

Since the parameters $ \eta$ , $\kappa(m_0)$ , $D(m_0),$ and $\hat{D}(t_0)$ in the three conditions of Lemma 1 do not involve $\epsilon$ , we have that $K^{\star\star}(m_0)$ does not depend on $\epsilon$ . To simplify the notation, we will use $K^{\star\star}$ to represent $K^{\star\star}(m_0)$ .

4.4.3. Asymptotically tight upper and lower bounds under MaxWeight policy

We now use the state-space collapse result from the previous section to obtain an exact expression for the heavy-traffic scaled mean sum of the queue lengths in an input-queued switch under Markovian arrivals. In particular, we will obtain lower and upper bounds on the steady-state mean queue lengths that differ by only $o(1/\epsilon)$ , and so are negligible in the heavy-traffic limit. We will again use the m-step drift argument from Section 3. We will use $V^{\prime}(\boldsymbol{q},\boldsymbol{x}) = \lvert\lvert{\textbf{q}_{{\parallel}\mathcal{L}}}\rvert\rvert^2$ as the Lyapunov function to this end. This Lyapunov function was introduced in the i.i.d. case in [21].

The one-step drift of V ^′(q) is defined as

(15) \begin{equation} \Delta V^{\prime} (\boldsymbol{q} ,\boldsymbol{x} ) \triangleq \left[V^{\prime} \left(\boldsymbol{Q}^{t+1},\boldsymbol{X}^{t+1} \right)-V^{\prime} \left(\boldsymbol{Q}^t,\boldsymbol{X}^t \right) \right]\mathcal{I} \left(\left(\boldsymbol{Q}^t,\boldsymbol{X}^t\right) =(\boldsymbol{q},\boldsymbol{x}) \right).\end{equation}

Lemma 6. For any arrival rate vector $\boldsymbol{\lambda}$ in the interior of the capacity region $\boldsymbol{\lambda} \in int (\mathcal{C} )$ , the steady-state mean $E\big[\lvert\lvert{\overline{\boldsymbol{Q}}}\rvert\rvert^2\big]$ is finite, and consequently $E [V^{\prime} (\boldsymbol{Q} ,\boldsymbol{X} ) ]$ is finite for the input-queued switch under the MaxWeight algorithm.

This lemma is needed to set the drift of $V^{\prime} (\boldsymbol{q},\boldsymbol{x})$ to zero in steady state. The lemma is proved in Appendix G. We will now state and prove the main result of this paper.

Theorem 2. Consider a set of switch systems under the MaxWeight scheduling algorithm, parameterized by the heavy-traffic parameter $0<\epsilon<1$ as described before. For each system with $\epsilon < v_{\min}/2\lvert\lvert{\boldsymbol{v}}\rvert\rvert$ , in the heavy-traffic limit, as $\epsilon \to 0$ , we have

(16) \begin{equation} {} \lim_{\epsilon \to 0}\epsilon E\Bigg[\sum_{ij}\overline{Q}_{ij}^\epsilon \Bigg] = \sum_{ij}\left(\frac{1}{N} \sum_{j^{\prime}} \sigma^2_{ij,ij^{\prime}}+\frac{1}{N} \sum_{i^{\prime}}\sigma^2_{ij,i^{\prime}j}-\frac{1}{N^2} \sum_{i^{\prime}j^{\prime}} \sigma^2_{ij,i^{\prime}j^{\prime}}\right). \end{equation}

Corollary 1. If the underlying Markov chains are independent across input–output pairs, i.e., $\sigma_{ij,kl}=0\ \forall ij\neq kl$ , then Equation (16) can be simplified as

\begin{equation*}\lim_{\epsilon \to 0}\epsilon E\Bigg[\sum_{ij}\overline{Q}_{ij}^\epsilon \Bigg]= \left(1-\frac{1}{2N} \right)\lvert\lvert{\boldsymbol{\sigma}}\rvert\rvert^2.\end{equation*}

Corollary 2. If the arrival processes are i.i.d. across time, i.e., $\gamma_{ij,kl} (t)=0\ \forall t\in\{1,2,\ldots\}$ , then Equation (16) can be simplified as

\begin{equation*}\lim_{\epsilon \to 0}\epsilon E\Bigg[\sum_{ij}\overline{Q}_{ij}^\epsilon \Bigg]= \sum_{ij}\left(\frac{1}{N} \sum_{j^{\prime}} \gamma^2_{ij,ij^{\prime}}(0)+\frac{1}{N} \sum_{i^{\prime}}\gamma^2_{ij,i^{\prime}j}(0)-\frac{1}{N^2} \sum_{i^{\prime}j^{\prime}} \gamma^2_{ij,i^{\prime}j^{\prime}}(0)\right),\end{equation*}

which matches the result in [14, Corollary 1, p. 13].

Remark 4. Although Theorem 2 and Corollaries 1 and 2 present the results in the heavy-traffic limit as $\epsilon \to 0$ , our approach provides upper and lower bounds on $E\left[\sum_{ij}\overline{Q}_{ij}^\epsilon \right]$ for all $\epsilon \in(0, v_{\min}/2\|\boldsymbol{v}\|)$ . See Equations (25) and (26) for the explicit bounds.

Proof of Theorem 2. Fix an $\epsilon \in (0, v_{\min}/2\lvert\lvert{\boldsymbol{v}}\rvert\rvert)$ and consider the system with index $\epsilon$ . In the rest of the proof, we consider the system in its steady state, and so for every time t, $\left(\boldsymbol{Q}^t\right)^{(\epsilon)} \stackrel{d}= \overline{\boldsymbol{Q}}^{(\epsilon)}$ . We again skip the superscript ${({\cdot})}^{(\epsilon)}$ in this proof and use $\boldsymbol{Q}^t$ to denote the steady-state queue length vector. Then $\boldsymbol{A}^t$ denotes the arrival vector in steady state and $\boldsymbol{Q}^{t+m}$ denotes the queue length at time $t+m$ ,

\begin{equation*}\boldsymbol{Q}^{t+m} = \boldsymbol{Q}^t+\sum_{l=0}^{m-1} \boldsymbol{A}^{t+l}-\sum_{l=0}^{m-1} \boldsymbol{S}^{t+l}+\sum_{l=0}^{m-1} \boldsymbol{U}^{t+l},\end{equation*}

which has the same distribution as $\boldsymbol{Q}^t$ for all $m \in \mathbb{N}_+$ .

The steady-state mean $V^{\prime} (\boldsymbol{Q}^t )$ is finite from Lemma 6. Therefore, we can set the mean drift of $V^{\prime} (\cdot )$ in steady state to zero:

(17) \begin{align} E \left[\Delta V^{\prime} (\boldsymbol{q} ,\boldsymbol{x} ) \right]& = -\underbrace{2E \left[\left\langle \boldsymbol{Q}^t_{{\parallel}\mathcal{L}},\boldsymbol{S}^t_{{\parallel}\mathcal{L}}-\boldsymbol{A}^t_{{\parallel}\mathcal{L}} \right\rangle \right]}_{\mathcal{T}_{1}} +\underbrace{E\left[ \big\lvert\big\lvert{\boldsymbol{A}^t_{{\parallel}\mathcal{L}}-\boldsymbol{S}^t_{{\parallel}\mathcal{L}}}\big\rvert\big\rvert^2 \right]}_{\mathcal{T}_{2}} \nonumber \\ &-\underbrace{E \Big[ \big\lvert\big\lvert{\boldsymbol{U}^t_{{\parallel}\mathcal{L}}}\big\rvert\big\rvert^2 \Big]}_{\mathcal{T}_{3}}+\underbrace{2E\left[ \left \langle \boldsymbol{Q}^{t+1}_{{\parallel}\mathcal{L}}, \boldsymbol{U}^t_{{\parallel}\mathcal{L}} \right \rangle \right]}_{\mathcal{T}_{4}} =0. \end{align}

We will now bound each of these four terms. In steady state we have

\begin{equation*} E \left[ \big\langle\boldsymbol{Q}^{t},\boldsymbol{A}^{t} \big\rangle \right] =E \left[\big\langle\boldsymbol{Q}^{t+m},\boldsymbol{A}^{t+m} \big\rangle \right],\end{equation*}

since the steady-state mean $E \left[ \big\langle\boldsymbol{Q}^{t},\boldsymbol{A}^{t} \big\rangle \right] \leq \sqrt{E\left[ \lvert\lvert{\boldsymbol{Q}^{t}}\rvert\rvert^2\right]E\left[ \lvert\lvert{\boldsymbol{A}^{t}}\rvert\rvert^2 \right]}< \infty $ according to Lemma 6. Then we have

(18) \begin{align} \mathcal{T}_{1} & = 2E \left[\left\langle \boldsymbol{Q}^t_{{\parallel}\mathcal{L}},\boldsymbol{S}^t_{{\parallel}\mathcal{L}}-\boldsymbol{\lambda}_{{\parallel}\mathcal{L}} \right\rangle \right]+2E \left[\left\langle \boldsymbol{Q}^t_{{\parallel}\mathcal{L}},\boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{A}^t_{{\parallel}\mathcal{L}} \right\rangle \right] \nonumber\\ & = 2E \left[\left\langle \boldsymbol{Q}^t_{{\parallel}\mathcal{L}},\boldsymbol{S}^t_{{\parallel}\mathcal{L}}-\boldsymbol{\lambda}_{{\parallel}\mathcal{L}} \right\rangle \right]+2E \left[\left\langle \boldsymbol{Q}^{t+m}_{{\parallel}\mathcal{L}},\boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{A}^{t+m}_{{\parallel}\mathcal{L}} \right\rangle \right] \nonumber \\ & =2E \left[\left\langle \boldsymbol{Q}^t_{{\parallel}\mathcal{L}},\boldsymbol{S}^t_{{\parallel}\mathcal{L}}-\boldsymbol{\lambda}_{{\parallel}\mathcal{L}} \right\rangle \right] \nonumber\\ & +2E \left[\left\langle \boldsymbol{Q}^{t}_{{\parallel}\mathcal{L}}+\sum_{l=1}^m \boldsymbol{A}^{t+m-l}_{{\parallel}\mathcal{L}}-\boldsymbol{S}^{t+m-l}_{{\parallel}\mathcal{L}}+\boldsymbol{U}^{t-m+l}_{{\parallel}\mathcal{L}},\boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{A}^{t+m}_{{\parallel}\mathcal{L}} \right\rangle \right] \nonumber\\ & =2E \left[\left\langle \boldsymbol{Q}^t_{{\parallel}\mathcal{L}},\boldsymbol{S}^t_{{\parallel}\mathcal{L}}-\boldsymbol{\lambda}_{{\parallel}\mathcal{L}} \right\rangle \right]+2E \left[\left\langle \boldsymbol{Q}^{t}_{{\parallel}\mathcal{L}},\boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{A}^{t+m}_{{\parallel}\mathcal{L}} \right\rangle \right] \nonumber\\ & +2E \left[\left\langle\sum_{l=1}^m \boldsymbol{A}^{t+m-l}_{{\parallel}\mathcal{L}}-\boldsymbol{\lambda}_{{\parallel}\mathcal{L}},\boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{A}^{t+m}_{{\parallel}\mathcal{L}} \right\rangle \right] \nonumber\\ & +2E \left[\left\langle\sum_{l=1}^m \boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{S}^{t+m-l}_{{\parallel}\mathcal{L}},\boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{A}^{t+m}_{{\parallel}\mathcal{L}} \right\rangle \right] \nonumber\\ & +2E \left[\left\langle\sum_{l=1}^m \boldsymbol{U}^{t-m+l}_{{\parallel}\mathcal{L}}, \boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{A}^{t+m}_{{\parallel}\mathcal{L}} \right\rangle \right]. \end{align}

We will now bound each of the terms on the right-hand side of (18). The first term can be simplified as follows. Since we assumed that the schedule is always a perfect matching, we have $\sum_i s_{ij}=\sum_j s_{ij}=1$ . Since $\boldsymbol{\lambda}^\epsilon = (1-\epsilon )\boldsymbol{v}$ and $\boldsymbol{v} \in \mathcal{F}$ , we have $\sum_i \lambda_{ij}=\sum_j \lambda_{ij}=1-\epsilon$ , so by (13),

\begin{equation*} \begin{aligned} E \left[\left\langle \boldsymbol{Q}^t_{{\parallel}\mathcal{L}},\boldsymbol{S}^t_{{\parallel}\mathcal{L}}-\boldsymbol{\lambda}_{{\parallel}\mathcal{L}} \right\rangle \right]= \frac{\epsilon}{N} E \Bigg[\sum_{ij}Q_{ij}^t\Bigg]. \end{aligned} \end{equation*}

For the second term in the right-hand side of (18), according to (13) we have

\begin{align*} & E \left[\left\langle \boldsymbol{Q}^{t}_{{\parallel}\mathcal{L}},\boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{A}^{t+m}_{{\parallel}\mathcal{L}} \right\rangle \right] \\ & = \frac{1}{N}E \Bigg[\sum_{ij} Q_{ij}^t \Bigg(\sum_{j^{\prime}} \left(\lambda_{ij^{\prime}}-A^{t+m}_{ij^{\prime}} \right) \Bigg) \Bigg]\\ &+ \frac{1}{N}E \Bigg[\sum_{ij} Q_{ij}^t \Bigg(\sum_{i^{\prime}} \left(\lambda_{i^{\prime}j}-A^{t+m}_{i^{\prime}j} \right) \Bigg) \Bigg]\\ &-\frac{1}{N^2}E \Bigg[ \sum_{ij} Q_{ij}^t \Bigg(\sum_{i^{\prime}j^{\prime}} \left(\lambda_{i^{\prime}j^{\prime}}-A^{t+m}_{i^{\prime}j^{\prime}} \right) \Bigg) \Bigg]. \end{align*}

According to Lemma 2, by the geometric mixing of the Markov chain underlying the arrivals, we have

\begin{equation*} \begin{aligned} \left \vert E \Bigg[\sum_{ij}Q_{ij}^t \Bigg(\sum_{j^{\prime}} \left(\lambda_{ij^{\prime}}-A^{t+m}_{ij^{\prime}} \right) \Bigg) \Bigg] \right\vert &\leq E \Bigg[\sum_{ij} Q_{ij}^t \Bigg(\sum_{j^{\prime}}2A_{max}C_{ij}\alpha_{ij}^m \Bigg) \Bigg]\\ &\leq 2NA_{max}C_{max}\alpha_{max}^m E \Bigg[ \sum_{ij} Q_{ij}^t \Bigg], \end{aligned} \end{equation*}

where $C_{max} = \max_{ij}\{C_{ij}\}$ and $\alpha_{max} = \max_{ij}\{\alpha_{ij}\}$ . Thus the second term in the right-hand side of (18) can be bounded as follows:

\begin{equation*} \Big\lvert{E \left[\left\langle \boldsymbol{Q}^{t}_{{\parallel}\mathcal{L}},\boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{A}^{t+m}_{{\parallel}\mathcal{L}} \right\rangle \right]}\Big\rvert \leq 6A_{max}C_{max}\alpha_{max}^m E \Bigg[ \sum_{ij} Q_{ij}^t \Bigg]. \end{equation*}

For the third term in the right-hand side of (18), according to (13) we have

\begin{equation*} {} \begin{aligned} &E \left[\left\langle\sum_{l=1}^m \boldsymbol{A}^{t+m-l}_{{\parallel}\mathcal{L}}-\boldsymbol{\lambda}_{{\parallel}\mathcal{L}},\boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{A}^{t+m}_{{\parallel}\mathcal{L}} \right\rangle \right]\\ & = -\sum_{ij}\sum_{l=1}^{m}E \Bigg[ \sum_{j^{\prime}}\frac{1}{N}\Big(A_{ij}^{t+m}-\lambda_{ij} \Big) \Big(A_{ij^{\prime}}^{t+m-l}-\lambda_{ij^{\prime}}\Big)\\ &\quad\quad\quad\quad\quad\quad +\sum_{i^{\prime}}\frac{1}{N}\Big(A_{ij}^{t+m}-\lambda_{ij} \Big) \Big(A_{i^{\prime}j}^{t+m-l}-\lambda_{i^{\prime}j}\Big)\\ &\quad\quad\quad\quad\quad\quad -\sum_{i^{\prime}j^{\prime}} \frac{1}{N^2} \Big(A_{ij}^{t+m}-\lambda_{ij} \Big)\Big(A_{i^{\prime}j^{\prime}}^{t+m-l}-\lambda_{i^{\prime}j^{\prime}}\Big) \Bigg]\\ & = -\sum_{ij}\sum_{l=1}^{m}\left(\frac{1}{N} \sum_{j^{\prime}} \gamma_{ij,ij^{\prime}}(l)+\frac{1}{N} \sum_{i^{\prime}} \gamma_{ij,i^{\prime}j}(l)-\frac{1}{N^2} \sum_{i^{\prime}j^{\prime}} \gamma_{ij,i^{\prime}j^{\prime}}(l) \right). \end{aligned} \end{equation*}

For the fourth term in the right-hand side of (18), since the future arrivals are independent of past service, and the Markov chain is in steady state, according to (13) we have

\begin{equation*} \begin{aligned} E \left[\left\langle\sum_{l=1}^m \boldsymbol{\lambda}^{t+m-l}_{{\parallel}\mathcal{L}}-\boldsymbol{S}^{t+m-l}_{{\parallel}\mathcal{L}},\boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{A}^{t+m}_{{\parallel}\mathcal{L}} \right\rangle \right] =0. \end{aligned} \end{equation*}

Now we bound the fifth term in the right-hand side of (18). From Lemma 6, we have $E\big[\lvert\lvert{{\overline{\boldsymbol{Q}}}}\rvert\rvert_2\big] < \infty$ . Since $\big\lvert{E\big[ \sum_{ij} \overline{Q}_{ij} \big]}\big\rvert = \lvert\lvert{{\overline{\boldsymbol{Q}}}}\rvert\rvert_1 \leq N^2E\big[\lvert\lvert{{\overline{\boldsymbol{Q}}}}\rvert\rvert_2\big]$ , we conclude that $E\left[ \sum_{ij} \overline{Q}_{ij} \right]$ is finite. Thus the drift is zero in steady state,

\begin{align*} E \Bigg[ \sum_{ij} \left( Q^{t+1}_{ij} - Q^{t}_{ij}\right) \Bigg] &= E \Bigg[ \sum_{ij} \left( A^t_{ij} - S^t_{ij} +U^t_{ij} \right) \Bigg]\\ &= E \Bigg[ N(1-\epsilon) - N+ \sum_{ij} U^t_{ij} \Bigg] =0, \end{align*}

which gives $E \left[ \sum_{ij} U_{ij}^t \right] = N\epsilon. $

Since $\left\lvert{\sum_{j^{\prime}} \left(\lambda_{ij^{\prime}}-A^{t+m}_{ij^{\prime}} \right) }\right\rvert\leq 1+N A_{max}$ , according to (13) we have

\begin{equation*} \begin{aligned} \left\lvert{E \left[\left\langle\sum_{l=1}^m \boldsymbol{U}^{t-m+l}_{{\parallel}\mathcal{L}}, \boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{A}^{t+m}_{{\parallel}\mathcal{L}} \right\rangle \right]}\right\rvert \leq 3m\epsilon \big(1+NA_{max}\big). \end{aligned} \end{equation*}

Putting all of these terms back into (18), we conclude that

(19) \begin{equation} {} \begin{aligned} \mathcal{T}_{1} \geq & 2\left (\frac{1}{N}-6A_{max}C_{max}\frac{\alpha_{max}^m}{\epsilon}\right) E \bigg[\epsilon\sum_{ij} Q_{ij}^t\bigg]\\ &-2\sum_{ij}\sum_{l=1}^{m}\left(\frac{1}{N} \sum_{j^{\prime}} \gamma_{ij,ij^{\prime}}(l)+\frac{1}{N} \sum_{i^{\prime}} \gamma_{ij,i^{\prime}j}(l)-\frac{1}{N^2} \sum_{i^{\prime}j^{\prime}} \gamma_{ij,i^{\prime}j^{\prime}}(l) \right)\\ &-6m\epsilon \big(1+NA_{max} \big), \end{aligned} \end{equation}

and

(20) \begin{equation} {} \begin{aligned} \mathcal{T}_{1} & \leq2\left (\frac{1}{N}+6A_{max}C_{max}\frac{\alpha_{max}^m}{\epsilon}\right) E \bigg[\epsilon\sum_{ij} Q_{ij}^t\bigg]\\ &-2\sum_{ij}\sum_{l=1}^{m}\left(\frac{1}{N} \sum_{j^{\prime}} \gamma_{ij,ij^{\prime}}(l)+\frac{1}{N} \sum_{i^{\prime}} \gamma_{ij,i^{\prime}j}(l)-\frac{1}{N^2} \sum_{i^{\prime}j^{\prime}} \gamma_{ij,i^{\prime}j^{\prime}}(l) \right)\\ &+6m\epsilon \big(1+NA_{max} \big). \end{aligned} \end{equation}

In bounding $\mathcal{T}_{2}$ , $\mathcal{T}_{3}$ , and $\mathcal{T}_{4}$ , we do not have to deal with the correlation between $\boldsymbol{Q}$ and $\boldsymbol{A}$ , and so they can be bounded in the same manner as in [22]. We present a brief overview here. It can be shown as in [21, 22] that

(21) \begin{equation} {} \begin{aligned} \mathcal{T}_{2}&=E\left[ \lvert\lvert{\boldsymbol{A}^t_{{\parallel}\mathcal{L}}-\boldsymbol{S}^t_{{\parallel}\mathcal{L}}}\rvert\rvert^2 \right]\\ & = E\left[ \lvert\lvert{\boldsymbol{\lambda}_{{\parallel}\mathcal{L}}-\boldsymbol{S}^t_{{\parallel}\mathcal{L}}}\rvert\rvert^2 \right]+E\left[ \lvert\lvert{\boldsymbol{A}^t_{{\parallel}\mathcal{L}}-\boldsymbol{\lambda}_{{\parallel}\mathcal{L}}}\rvert\rvert^2 \right]\\ &= \epsilon^2+ \sum_{ij}\left(\frac{1}{N} \sum_{j^{\prime}} \gamma_{ij,ij^{\prime}}(0)+\frac{1}{N} \sum_{i^{\prime}} \gamma_{ij,i^{\prime}j}(0)-\frac{1}{N^2} \sum_{i^{\prime}j^{\prime}} \gamma_{ij,i^{\prime}j^{\prime}}(0) \right). \end{aligned} \end{equation}

The term $\mathcal{T}_{3}$ can be bounded as

(22) \begin{equation} 0\leq \mathcal{T}_{3} = E \left[ \lvert\lvert{\boldsymbol{U}^t_{{\parallel}\mathcal{L}}}\rvert\rvert^2 \right] \leq E \left[ \lvert\lvert{\boldsymbol{U}^t}\rvert\rvert^2 \right]=E \Bigg[ \sum_{ij}\left(U_{ij}^t\right)^2 \Bigg] \stackrel{(a)}= E \bigg[ \sum_{ij}U_{ij}^t \bigg] =N\epsilon, \end{equation}

where (a) follows from $u_{ij} \in\{0,1\}$ , and the last equality follows from (33). Now, for the term $\mathcal{T}_{4}$ , we have

(23) \begin{align} \mathcal{T}_{4} = 2E\left[ \left \langle \boldsymbol{Q}^{t+1}_{{\parallel}\mathcal{L}}, \boldsymbol{U}^t_{{\parallel}\mathcal{L}} \right \rangle \right] =2E\left[ \left \langle \boldsymbol{Q}^{t+1}_{{\parallel}\mathcal{L}}, \boldsymbol{U}^t \right \rangle \right]\notag & = 2E\left[ \left \langle \boldsymbol{Q}^{t+1}, \boldsymbol{U}^t \right \rangle \right]-2E\left[ \left \langle \boldsymbol{Q}^{t+1}_{{\perp}\mathcal{L}}, \boldsymbol{U}^t\right \rangle \right]\notag\\& \stackrel{(a)}= -2E\left[ \left \langle \boldsymbol{Q}^{t+1}_{{\perp}\mathcal{L}}, \boldsymbol{U}^t\right \rangle \right], \end{align}

where (a) follows from the definition of unused service. Using the Cauchy–Schwartz inequality, we have

(24) \begin{align} \Big\lvert{2E\left[ \left \langle \boldsymbol{Q}^{t+1}_{{\perp}\mathcal{L}}, \boldsymbol{U}^t\right \rangle \right]}\Big\rvert\leq 2\sqrt{E\left[\lvert\lvert{\boldsymbol{Q}^{t+1}_{{\perp}\mathcal{L}}}\rvert\rvert^2 \right]E\left[\lvert\lvert{\boldsymbol{U}^t}\rvert\rvert^2 \right]} \leq 2\sqrt{K^{\star\star}N\epsilon}, \end{align}

where the last inequality follows from Proposition 4. Substituting (19)–(24) into (17), putting back the superscript ${({\cdot})}^{(\epsilon)}$ , and taking $m(\epsilon)=\lfloor1/\sqrt{\epsilon}\rfloor$ , we get

(25) \begin{align} &2\left (\frac{1}{N}-6A_{max}C_{max}\frac{\alpha_{max}^{m(\epsilon)}}{\epsilon}\right) E \bigg[\epsilon\sum_{ij} \overline{Q}^{(\epsilon)}_{ij}\bigg] \nonumber \\ & \leq2\sum_{ij}\sum_{l=1}^{m(\epsilon)}\left(\frac{1}{N} \sum_{j^{\prime}} \gamma^{(\epsilon)}_{ij,ij^{\prime}}(l)+\frac{1}{N} \sum_{i^{\prime}} \gamma^{(\epsilon)}_{ij,i^{\prime}j}(l)-\frac{1}{N^2} \sum_{i^{\prime}j^{\prime}} \gamma^{(\epsilon)}_{ij,i^{\prime}j^{\prime}}(l) \right) +6m(\epsilon)\epsilon \big(1+NA_{max} \big)\nonumber \\ &+\epsilon^2+ \sum_{ij}\left(\frac{1}{N} \sum_{j^{\prime}} \gamma^{(\epsilon)}_{ij,ij^{\prime}}(0)+\frac{1}{N} \sum_{i^{\prime}} \gamma^{(\epsilon)}_{ij,i^{\prime}j}(0)-\frac{1}{N^2} \sum_{i^{\prime}j^{\prime}} \gamma^{(\epsilon)}_{ij,i^{\prime}j^{\prime}}(0) \right)+N\epsilon+2\sqrt{K^{\star\star}N\epsilon}, \end{align}

and

(26) \begin{align} &2\left (\frac{1}{N}+6A_{max}C_{max}\frac{\alpha_{max}^{m(\epsilon)}}{\epsilon}\right) E \bigg[\epsilon\sum_{ij} \overline{Q}^{(\epsilon)}_{ij}\bigg]\nonumber \\ \geq&2\sum_{ij}\sum_{l=1}^{m(\epsilon)}\left(\frac{1}{N} \sum_{j^{\prime}} \gamma^{(\epsilon)}_{ij,ij^{\prime}}(l)+\frac{1}{N} \sum_{i^{\prime}} \gamma^{(\epsilon)}_{ij,i^{\prime}j}(l)-\frac{1}{N^2} \sum_{i^{\prime}j^{\prime}} \gamma^{(\epsilon)}_{ij,i^{\prime}j^{\prime}}(l) \right) -6m(\epsilon)\epsilon \big(1+NA_{max} \big) \nonumber \\ &+\epsilon^2+ \sum_{ij}\left(\frac{1}{N} \sum_{j^{\prime}} \gamma^{(\epsilon)}_{ij,ij^{\prime}}(0)+\frac{1}{N} \sum_{i^{\prime}} \gamma^{(\epsilon)}_{ij,i^{\prime}j}(0)-\frac{1}{N^2} \sum_{i^{\prime}j^{\prime}} \gamma^{(\epsilon)}_{ij,i^{\prime}j^{\prime}}(0) \right) -2\sqrt{K^{\star\star}N\epsilon}. \end{align}

Letting $\epsilon \to 0$ , we have

\begin{equation*} {} \begin{aligned} &\lim_{\epsilon \to 0}\epsilon E\bigg[ \sum_{ij}\overline{Q}^{(\epsilon)}_{ij} \bigg] \\ &= \lim_{\epsilon \to 0} \sum_{ij}\left(\frac{1}{N} \sum_{j^{\prime}} \gamma^{(\epsilon)}_{ij,ij^{\prime}}(0)+\frac{1}{N} \sum_{i^{\prime}} \gamma^{(\epsilon)}_{ij,i^{\prime}j}(0)-\frac{1}{N^2} \sum_{i^{\prime}j^{\prime}} \gamma^{(\epsilon)}_{ij,i^{\prime}j^{\prime}}(0)\right)\\ &+ 2\sum_{ij}\sum_{t=1}^{\frac{1}{\lfloor1/\sqrt{\epsilon}\rfloor}}\left(\frac{1}{N} \sum_{j^{\prime}} \gamma^{(\epsilon)}_{ij,ij^{\prime}}(l)+\frac{1}{N} \sum_{i^{\prime}} \gamma^{(\epsilon)}_{ij,i^{\prime}j}(l)-\frac{1}{N^2} \sum_{i^{\prime}j^{\prime}} \gamma^{(\epsilon)}_{ij,i^{\prime}j^{\prime}}(l) \right) . \end{aligned} \end{equation*}

The proof is now complete after using Claim 5.

5. Conclusion

In this paper, we have analyzed the heavy-traffic behavior in a switch operating under the MaxWeight scheduling algorithm when the arrivals are Markovian. We have obtained the steady-state sum queue length, which is consistent with the result in the i.i.d. case. Our arguments generalize the drift method that was developed in [6, 22] and the transform method in [13] to the case of Markovian arrivals. The key ideas are to consider drift over a time window whose size depends on the heavy-traffic parameter, and to exploit geometric mixing of Markov chains to get a handle on the Markovian correlations.

There are several possible directions for future research. One immediate direction is to extend the result to the so-called ‘generalized switch model’ [14, 31] when the complete resource pooling condition is not satisfied. (This is the case for a general queueing model that includes a switch that is incompletely saturated, a switch where the arrivals across the ports are saturated, wireless networks under interference and fading, cloud-computing scheduling, etc.) A second future direction is to establish the generality of Markovian arrivals in discrete-time systems. It was shown in [2] that Markovian arrival processes approximate any marked point process to an arbitrary degree of accuracy. Exploring the validity of such a result for discrete-time arrival processes is an open problem.