Introduction
- Single Hop System, \(L\) Queues
- \(Q_l(t=1)=(Q_l(t)+A_l(t)-S_l(t))^+=Q_l(t)+A_l(t)-S_l(t)+U_l(t)\)
- \(U_l(t)=\max\{0,S_l(t)-A_l(t)-Q_l(t)\}\)
\(~\)
Lemma 1
For an aperiodic and irreducible Markov Chain, over a countable state-space, suppose \(Z:\mathcal{X}\rightarrow{}R\) is a non-negative Lyapunor function. Define
\[\Delta(Z(X))=[Z(X[t+1])-Z(X[t])]I(X(t)=x)\]
Suppose
- \(\exists\eta>0\) and \(k<\infty\) s.t.
\[\mathbb{E}\{\Delta(Z(X))|X(t)=x\}\leq-\eta\text{ for all }X\in\mathcal{X},Z(X)\geq{}k\]
- \(\exists{}D\leq\infty\) s.t.
\[Pr\{|\Delta(Z(X))\leq0\}=1,~\forall{}X\in\mathcal{X}\]
Then \(\exists\theta^*>0\) and \(c^*<\infty\) s.t.
\[\lim\sup_{t\rightarrow\infty}\mathbb{E}\{\exp\{\theta^*Z(X[t])\}\}\leq{}c^*\]
If also \(X(t)\) is positive recurrent, then \(Z(X(t))\) converges in distribution to \(\bar{Z}\) with \(\mathbb{E}\{\exp\{\theta^*\bar{Z}\}\}\leq{}c^*\)
Join the Shortest Queue (JSQ)
- \(A_{\Sigma}(t),S_l(t)\) iid
- \(A_\Sigma(t)\in[0,A_\max],S_l(t)\in[0,S_\max]\)
- \(\lambda_\Sigma=\mathbb{E}\{A_\Sigma(t)\},\sigma_\Sigma^2=D\{A_\Sigma(t)\}\)
- \(\mu_l=\mathbb{E}\{S_l(t)\},v_l^2=D\{S_l(t)\}\)
- \(\mu_\Sigma=\sum_l\mu_l,v_\Sigma^2=\sum_lv_l^2\)
And the policy is \(A(t)=(A_1(t),\cdots,A_L(t))\) \[A(t)=\text{RAND}\{\arg\min_{A\geq0,\sum_lA_l=A_\Sigma(t)}<A,Q(t)>\}\]
Conclusion
- \(\lambda_\Sigma>\mu_\Sigma\), unstable
- \(\lambda_\Sigma<\mu_\Sigma\), JSQ stablizes that system \(\{Q(t)\}\) converges in distribution to a random variable \(\bar{Q}\) whose all moments are bounded, i.e. \(\mathbb{E}\{||\bar{Q}||^r\}=M_r\)
Analysis of Stability
\(Z(X)=V(Q)=||Q||\) \(W(Q)=||Q||^2\) \[e=\mu_\Sigma-\lambda_\Sigma,\frac{e}{L}=\mu_l-\lambda_l\] \[\begin{split}\mathbb{E}\{\Delta(W(Q))|Q\}&=\mathbb{E}\{||Q(t+1)||^2-||Q(t)||^2~|Q\}\\&=\mathbb{E}\{||Q+A-S+U||^2-||Q||^2~|Q\}\\&=\mathbb{E}\{||Q+A-S||^2+2<Q+A_S,U>+||U||^2-||Q||^2~|Q\}\\&\leq{}\mathbb{E}\{||Q+A-S||^2-||Q||^2~|Q\}\\&=\mathbb{E}\{2<Q,A-S>+||A-S||^2~|Q\}\\&=\mathbb{E}\{2<Q,A-S>|Q\}+k_1\\&=2<Q,\mathbb{E}\{A|Q\}-\lambda>-<Q,\mu-\lambda>+k_1\\&=<Q,\mathbb{E}\{A|Q\}-\lambda>-\frac{2e}{L}<Q,1>+k_1\\&=2\mathbb{E}\{A_\Sigma|Q\}Q_\min-2<Q,\lambda>-\frac{2e}{L}||Q||_1+k_1\\&=2\lambda_\Sigma{}Q_\min-2\sum_l\lambda_lQ_l-\frac{2e}{L}||Q||+k_1\\&=-2\sum_l\lambda_l(Q_l-Q_\min)-\frac{2e}{L}||Q||+k_1\\&\leq\frac{2e}{L}||Q||+k_1\end{split}\]
\[\begin{split}\mathbb{E}\{\Delta{}V(Q)|Q(t)=Q\}=&\mathbb{E}\{||Q(t+1)||-||Q(t)||~|Q(t)=Q\}\\\leq&\frac{1}{2||Q||}\mathbb{E}\{||Q(t+1)||^2-||Q(t)||^2~|Q(t)=Q\}\\\leq&\frac{e}{L}+\frac{k_1}{2||Q||}\end{split}\]
Lower Bound
Consider \(Q_\Sigma(t)\) and \(S_\Sigma(t)=\sum{}S_l(t)\) which is a single server, obviously: \[Q_\Sigma(t)\leq\sum_lQ_l(t)\]
- \(\alpha(t)<\alpha_\max\)
- \(\beta(t)<\beta_\max\)
- \(\Phi(t+1)=[\Phi(t)+\alpha(t)-\beta(t)]^+\)
Lemma 2
Suppose \(\{\alpha^e(t)\}\) satisfies \(e=\beta-\alpha^e\). Let the queue process \(\{\Phi^e(t)\}\). Then
- \(\{\Phi^e(t)\}\) is a positive recurrent Markov Chain and \(\{\Phi^e(t)\}\rightarrow{}\bar{\Phi}^e\) with \(\mathbb{E}\{||\bar{\Phi}^e||\}\leq{}M_r\)
- \[\mathbb{E}\{\bar{\Phi}^e\}\geq\frac{\xi^e}{2e}-B_1\]
where \(\xi^e=\sigma_{\alpha^e}^2+\sigma_\beta^2+e^2,B_1=\frac{\beta_\max}{2}\)
- In the heavy traffic limit, \(e\rightarrow0\) \[\lim_{e\rightarrow0}\inf{}e\mathbb{E}\{||\bar{\Phi}^e||\}\geq\frac{\xi}{2}\]
\[\begin{split}\Phi(t+1)=\Phi(t)+\alpha(t)-\beta(t)+\chi(t),\chi(t)=-\max\{0,\beta-\alpha-\Phi\}\end{split}\] \[\begin{split}W(\Phi)=||\Phi||^2\end{split}\] \[\begin{split}\mathbb{E}\{\Delta{}W(\Phi)|\Phi(t)\}&=\mathbb{E}\{(\Phi+\alpha-\beta)^2+2(\Phi+\alpha-\beta)\chi+\chi^2-\Phi^2|\Phi)\}\\&=\mathbb{E}\{(\alpha-\beta)^2|\Phi\}+2\Phi{}\mathbb{E}\{(\alpha-\beta)|\Phi\}-\mathbb{E}\{\chi^2|\Phi\}\end{split}\]
In steady state, \(\mathbb{E}\{\Delta{}W\}=0\), take expectation of both sides:
\[\mathbb{E}\{(\alpha-\beta)^2\}+2\mathbb{E}\{\Phi{}\}e-\mathbb{E}\{\chi^2\}=0\]
Consider \(\mathbb{E}\{\chi^2\}\leq{}e\beta_\max\)
State Space Collapse
Let \(\vec{c}>0\) is a vector with unit form. Let \(Q_{\parallel}=<\vec{c},\vec{Q}>\vec{c}\), \(Q_{\perp}=Q-Q_{\parallel}\)
Lemma 3
Define Lyapunov function
\[V_\perp(Q)=||Q_\perp||,W(Q)=||Q||^2,W_{\parallel}(Q)=||Q_\parallel||^2\] \[\Delta{}V_\perp(Q)=V_\perp(Q(t+1))-V_\perp(Q(t))\]
Then:
- \[\Delta{}V_\perp(Q)\leq\frac{1}{2||Q_\perp||}(\Delta{}W(Q)-\Delta{}W_\parallel(Q))\]
- \[|\Delta{}V_\perp(Q)|\leq2\sqrt{L}\max(A_\max,S_\max)\]
\[\begin{split}\Delta{}V_\perp(Q)&=V_\perp(Q(t+1))-V_\perp(Q(t))\\&=\sqrt{V_\perp(Q(t+1))^2}-\sqrt{V_\perp(Q(t))^2}\\&\leq\frac{1}{2||Q_\perp(t)||}(||Q_\perp(t+1)||^2-||Q_\perp(t)||^2)\\&=\frac{1}{2||Q_\perp(t)||}(\Delta{}W(Q)-\Delta{}W_{\parallel}(Q))\end{split}\] \[\begin{split}|\Delta{}V_\perp(Q)|&=|||Q_\perp(t+1)||-||Q_\perp(t)|||\\&\leq||Q_\perp(t+1)-Q_\perp(t)||\\&\leq||Q(t+1)-Q(t)||+||Q_\parallel(t+1)-Q_\parallel(t)||\\&\leq2||Q(t+1)-Q(t)||\\&\leq2\sqrt{L}\max||Q_l(t+1)-Q_l(t)||\end{split}\]
\[\vec{c}=\vec{1}\cdot\frac{1}{\sqrt{L}}\] \[Q_\parallel^e=\frac{Q_\Sigma}{L}\vec{1},Q_\perp=[Q_l-\frac{1}{L}Q_\Sigma]_{l=1}^L,Q_\Sigma=\sum_lQ_l\]
Proposition
Consider \(\bar{Q}^e\) under JSQ with \(\{A_\Sigma^e\}_t\), and \(e=\mu_\Sigma-\lambda_\Sigma^e\). Then, for any \(\delta\in(0,\mu_\max)\), \(\exists{}\) a sequence of \(\{N_r\}\), s.t. \[\mathbb{E}\{||\bar{Q}_\perp^2||^r\}\leq{}N_r,\forall{}e\in(0,(\mu_\min-\delta)L)\]
\[\begin{split}\mathbb{E}\{\Delta{}W(Q)|Q\}&=\mathbb{E}\{||Q(t+1)||^2-||Q(t)||^2|Q\}\\&\leq{}\mathbb{E}\{||Q+A-S||^2-||Q||^2|Q\}\\&=2\mathbb{E}\{<Q,A-S>|Q\}+K_1\end{split}\] \[\begin{split}\mathbb{E}\{<Q,A-S>|Q\}&=<Q,\mathbb{E}\{A|Q\}-\lambda>-<Q,\mu-\lambda>\\&=\mathbb{E}\{A_\Sigma|Q\}Q_\min-<Q,\lambda>-\frac{e}{\sqrt{L}}<Q,c>\\&=\lambda_\Sigma{}Q_\min-\sum_l\lambda_lQ_l-\frac{e}{\sqrt{L}}||Q_\parallel||\\&=-\sum_l\lambda_l(Q_l-Q_\min)-\frac{e}{\sqrt{L}}||Q_\parallel||\\&\leq\lambda_\min\sum_l|Q_l-Q_\min|-\frac{e}{\sqrt{L}}||Q_\parallel||\\&=-||Q-Q_\min\cdot\vec{1}||\cdot\lambda_\min-\frac{e}{\sqrt{L}}||Q_\parallel||\\&\leq-||Q-Q_\min\cdot\vec{1}||\lambda_\min-\frac{e}{\sqrt{L}}||Q_\parallel||\\&\leq-||Q-\frac{1}{L}Q_\Sigma\cdot\vec{1}||\cdot\lambda_\min-\frac{e}{\sqrt{L}}||Q_\parallel||\\&\leq-\delta||Q_\perp||-\frac{e}{\sqrt{L}}||Q_\parallel||\end{split}\] \[\begin{split}\mathbb{E}\{\Delta{}W_\parallel(Q)|Q\}&=\mathbb{E}\{<c,Q(t+1)>^2-<c,Q(t)>^2|Q\}\\&=\mathbb{E}\{<c,Q+A-S+u>^2-<c,Q>^2|Q\}\\&\cdots\rm{here~I~omit~something}\cdots\\&\geq-\frac{2e}{\sqrt{L}}||Q_\parallel||-K_2\end{split}\]
Max Weight
Assumptions:
- \(\vec{S}(t)=(S_l(t))\in\vec{S}\)
- \(A_l(t)\) independent over \(l\)
- \(A_l(t)\) iid over \(t\)
- \(A_l(t)\leq{}A_\max,S_l(t)\leq{}S_\max\)
Policy:
\[\vec{S}(t)=\text{RAND}\{\arg\max_{s\in\vec{S}}<Q(t),S>\}\]
Capacity Region
\[\mathcal{R}=\text{conv}(\vec{S})\]
Assume finite size and non-negative of \(\vec{S}\), then: \[\mathcal{R}=\{r\geq0,<c^{(k)},r>\leq{}b^{(k)}\}\] \[\mathcal{H}^{(k)}=\{r:<c^{(k)},r>=b^{(k)}\}\] \[\mathcal{F}^{(k)}=\mathcal{H}^{(k)}\cap{}\mathcal{R}\]
Lemma 4
- if \(\lambda\notin\mathcal{R}\), it is unstable
- \(\lambda\in\text{int}\mathcal{R}\), \(\{Q_l(t)\}\rightarrow\bar{Q}\) with \(\mathbb{E}\{||Q||^r\}\leq{}M_r\)
Lower Bound
Define:
\[e^{(k)}=\min_{r\in\mathcal{H}}||\lambda-r||\] \[\lambda^{(k)}=\lambda+e^{(k)}c^{(k)}\] \[K_\lambda=\{K\in\{1,\cdots,k\},\lambda^{(k)}\in\mathcal{R}\}\] \[K_\lambda^\circ=\{k\in{}K_\lambda,\lambda^{(k)}\in\rm{int}\mathcal{F}^{(k)}\}\] \[\alpha^{(k)}(t)=<c^{(k)},A(t)>,\beta^{(k)}(t)=b^{(k)}\] \[Q_\parallel^{(k)}=<c^{(k)},Q(t)>c^{(k)},Q_\perp=Q-Q_\parallel^{(k)}\]
Lemma 5
Assume \(\lambda\in\rm{int}\mathcal{R}\) with set \(e^{(k)}\). Then under MW, for each \(k\in{}K_\lambda^\circ\), \(\exists{}\) finite \(\{N_r^{(k)}\}_{k=1,2,\cdots}\) s.t.
\[\mathbb{E}\{||\bar{Q}_\perp^{(k)}||^r\}\leq{}N_r^{(k)}\]
for all \(e>0\), each Face \(k\) belonging to \(K_\lambda^\circ\) as \(e\rightarrow0\) and each \(r=1,2,\cdots\)
Further proof is available in the reference.
Reference
[1] Eryilmaz A, Srikant R. Asymptotically tight steady-state queue length bounds implied by drift conditions[J]. Queueing Systems, 2012, 72(3-4): 311-359.
