Queue Control Problem
\(A_1(t),A_2(t),Q_1(t),Q_2(t),\mu_1(t),\mu_2(t)\)
- \(A_i(t)\) is iid, \(\mathbb{E}\{A_i(t)\}=\lambda_i\), \(A_i(t)\in[0,A_{\max}]\)
- \(S_i(t)\) is condition of link \(i\), \(S_i(t)\in\{0,1\}\)
- \(P_{xy}=P_r\{S_1(t)=x,S_2(t)=y\}\)
- At every time, serve \(Q_1(t)\) or \(Q_2(t)\)
- \(\mu_i(t)=1\text{ if } S_i(t)=1,Q_i(t)>0\quad0\text{ otherwise}\)
- Goal: stabilize both queues
\(~\)
Linear Program
\[\max~e\] \[\begin{split}s.t.~\lambda_1+e&\leq{}P_{10}+P_{11}\theta\\\lambda_2+e&\leq{}P_{01}+(1-\theta)P_{11}\end{split}\]
- optimal value \(e^\star>0\)
- LP policy is obvious
- If we know all \(\lambda_i\) and \(P_{xy}\)
ALG Max-Weight
- Policy is simple
- \(S(t)=\{1,0\}\), serve \(Q_1\)
- \(S(t)=\{0,1\}\), serve \(Q_2\)
- \(S(t)=\{1,1\}\), serve \(\max\{Q_1,Q_2\}\)
- Without any infomation
\[L(t)=\frac{1}{2}Q_1^2(t)+\frac{1}{2}Q_2^2(t)\] \[Q_i(t+1)=(Q_i(t)-\mu_i(t)+A_i(t))^+\] \[\begin{split}\Delta(t)&=\mathbb{E}\{L(t+1)-L(t)|Q(t)\}\\&=\frac{1}{2}\mathbb{E}\{Q_1^2(t+1)-Q_1^2(t)+Q_2^2(t+1)-Q_2^2(t)|Q(t)\}\\&\leq{}B-\mathbb{E}\{Q_1(t)[\mu_1(t)-A_1(t)]+Q_2(t)[\mu_2(t)-A_2(t)]|Q(t)\}\\&=B+\lambda_1Q_1(t)+\lambda_2Q_2(t)-\mathbb{E}\{Q_1(t)\mu_1(t)+Q_2(t)\mu_2(t)|Q(t)\}\\&\leq{}B+\lambda_1Q_1(t)+\lambda_2Q_2(t)-Q_1(t)[P_{10}+P_{11}\theta]-Q_2(t)[P_{01}+P_{11}(1-\theta)]\\&=B-eQ_1(t)-eQ_2(t)\end{split}\]
Capacity Region
\(\lambda=(\lambda_1,\lambda_2,\dots,\lambda_n)\)
- Def: The capacity region \(\Lambda\) is the closure of \(\lambda\) under which exists an algorithm that can stabilize the system
- Claim: \(\Lambda=\{(\lambda_1,\lambda_2,\dots,\lambda_n)\text{ s.t. }e(\lambda)\geq0\}\)
- Corollary: Max-weight stabilizes the system whenever \(\exists{}e\geq0\text{ s.t. } \lambda+e\in\Lambda\)
- So, in some way, Max-weight is "Throughput Optimal"
Caratheodory's Theorem
Let \(X\) be a subset of \(R^d\). If \(x\in\text{conv}(X)\), then \(\exists~d+1\) points in \(X\) (i.e. \(x_1,\dots,x_{d+1}\)), s.t. \[x=\sum_{i=1}^{d+1}\alpha_ix_i,\alpha_i\geq0,\sum_{i=1}^{d+1}\alpha_i=1\]
Multi-Hop
- \(V=\{1,2,\dots,7\}\)
- \(E\) are linkes
- \(A_n^{(k)(t)}\) is packages entering \(n\) for destination \(k\), \(\mathbb{E}\{A_n^{(k)}(t)\}=\lambda_n^{(k)}\in[0,A_{\max}]\)
- \(S(t)=(S_{nm}(t),[n,m]\in{}E)\), \(S_{n,m}\in\{0,1\}\), iid
- \(\mu_{nm}(t)=1\text{ if }S_{nm}(t)=1\text{ and use link }[n,m]\quad0\text{ otherwise}\)
- No interference
- Queueing: \(Q_n^{(k)}(t)\)
- \(Q_n^{(k)}(t+1)\leq{}(Q_n^{(k)}(t)-\sum_{[n,m]\in{}E}\mu_{nm}^{(k)}(t))^+{}+\sum_{[a,n]\in{}E}\mu_{an}^{(k)}(t)+A_n^{(k)}(t)\)
- \(Q_n^{(0)}(t)=0\)
- Goal: stabilize all queues
Back Pressure
At time \(t\), observe \(Q_n^{(k)}(t)\) for all \(n,k\)
- For each \([n,m]\), define weight \(W_{nm}(t)=\max_k[Q_n^{(k)}(t)-Q_m^{(k)}(t)]^+\) and let \(k^\star=\arg\max{}W_{nm}^{(k)}(t)\)
- If \(W_{nm}(t)>0\), \(\mu_{nm}^{(k)}(t)=\mu_{nm}(t)\text{ if }k=k^\star\quad0\text{ otherwise}\)
- If \(W_{nm}(t)=0\), \(\mu_{nm}^{(k)}(t)=0\)
Analysis
\(Q(t)=(Q_n^{(k)}(t)),L(Q(t))=\frac{1}{2}\sum_{n,k}Q_n^{(k)}(t)^2\) \[\begin{split}\Delta(t)&=\mathbb{E}\{L(t+1)-L(t)|Q(t)\}\\&\leq{}B-\mathbb{E}\{\sum_{n,k}Q_n^{(k)}(t)[\sum_{[n,m]\in{}E}\mu_{nm}^{(k)}(t)-\sum_{[a,n]\in{}E}\mu_{an}^{(k)}(t)-A_n^{(k)}(t)]|Q(t)\}\\&=B-\sum_{n,m,k}\mathbb{E}\{\mu_{nm}^{(k)}(t)[Q_n^{(k)}(t)-Q_m^{(k)}(t)]|Q(t)\}+\sum_{n,k}Q_n^{(k)}(t)\lambda_n^{(k)}\\&\leq{}B-e\sum_{nm}Q_n^{(k)}(t)\end{split}\]
\[\max{}e\] \[\begin{split}s.t.~\lambda_n^{(k)}+e+\sum_{[a,n]}f_{an}^{(k)}&\leq\sum_{[n,m]}f_{nm}^{(k)}\\\sum_kf_{nm}^{(k)}&\leq\mu_{nm}\\f_{nm}^{(k)}&\geq0\end{split}\]
Interference Problem
\[\max~\sum_{n,m,k}\mu_{nm}^{(k)}(t)[Q_n^{(k)}(t)-Q_m^{(k)}(t)]^+\] \[s.t.~\sum_k\mu_{nm}^{(k)}(t)\leq\mu_{nm}(I(t),S(t)),I(t)\text{ feasible}\]
Utility Maximization in Networks
- \(A_n^{(k)}(t)\): # of pkts arrivals to \(n\) for \(k\) at t
- \(R_n^{(k)}(t)\): # of pkts admitted (admission control), \(0\leq{}R_n^{(k)}(t)\leq{}R_{\max}\)
- \(S(t)=(S_{nm}(t),[n,m]\in{}E)\), \(S_{n,m}\in\{0,1\}\), iid
- \(Q_n^{(k)}(t+1)\leq{}(Q_n^{(k)}(t)-\sum_{[n,m]\in{}E}\mu_{nm}^{(k)}(t))^+{}+\sum_{[a,n]\in{}E}\mu_{an}^{(k)}(t)+R_n^{(k)}(t)\)
- \(\bar{r}_n^{(k)}=\lim_{T\rightarrow\infty}\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\{R_n^{(k)}(t)\}\)
- \(g_n^{(k)}(\cdot)\) is utility function which is usually concave increasing
- Goal: \[\max\sum_{n,k}g_n^{(k)}(\bar{r}_n^{(k)}),\text{ s.t. stability}\]
Lyapunov function
\[L(Q(t))=\frac{1}{2}\sum_{n,k}Q_n^{(k)}(t)^2\] \[\begin{split}\Delta(t)&\leq{}B-\mathbb{E}\{\sum_{n,k}Q_n^{(k)}(t)[\sum_{[n,m]\in{}E}\mu_{nm}^{(k)}(t)-\sum_{[a,n]\in{}E}\mu_{an}^{(k)}(t)-R_n^{(k)}(t)]|Q(t)\}\\\text{subtract from both sides the term}& \\ &V\sum_{n,k}\mathbb{E}\{g_n^{(k)}(R_n^{(k)}(t))|Q_n(t)\}\\\Delta(t)-V\sum_{n,k}\mathbb{E}\{g_n^{(k)}(R_n^{(k)}(t))|Q_n(t)\}& \leq{}B-\sum_{n,k}\mathbb{E}\{Vg_n^{(k)}(R_n^{(k)}(t))-Q_n^{(k)}(t)R_n^{(k)}(t)|Q(t)\}\\&-\sum_{n,m,k}\mathbb{E}\{\mu_{nm}^{(k)}(t)[Q_n^{(k)}(t)-Q_m^{(k)}(t)]|Q(t)\}\end{split}\]
Cross-Longer Control
At time \(t\), observe \(S(t)\) and \(Q(t)\)
- Admission control (Application): Choose \(R_n^{(k)}(t)\)
\[\max{}Vg_n^{(k)}(R_n^{(k)}(t))-Q_n^{(k)}(t)R_n^{(k)}(t),\text{ s.t. }0\leq{}R_n^{(k)}(t)\leq{}R_{\max}\]
- Scheduling and Routing (Transport): Define \(W_{nm}(t)=\max_k[Q_n^{(k)}(t)-Q_m^{(k)}(t)]^+\), choose
\[\mu_{nm}^{(k)}(t)=\mu_{nm}(t)\text{ if }k=k^\star\quad0\text{ otherwise}\]
- Resource Allocation (Physical): Choose \(\mu(t)\)
\[\max\sum_{n,m}W_{nm}(t)\mu_{nm}(t),\text{ s.t. }\mu(t)\text{ is feasible}\]
Queue Independent Policy
\[\begin{split}\max&\sum_{n,k}g_n^{(k)}(r_n^{(k)})\\\text{s.t. }r_n^{(k)}+\sum_{a,n}f_{an}^{(k)}&\leq{}f_{nm}^{(k)}\\\sum_kf_{nm}^{(k)}&\leq\mu_{nm}\\\mu=(\mu_{nm},[n,m]\in{}E)&\in\sum_{S}\beta_S\text{conv}(\Gamma_S)\end{split}\]
\(r_n^{(k)\star}\), \(f_{nm}^{(k)\star}\), \(\mu_{nm}^{(k)\star}\) refers to a stationary randomized policy
\[\Rightarrow{}\Delta-V\sum_{n,k}\mathbb{E}\{g_n^{(k)}(R_n^{(k)}(t))|Q_n(t)\}\leq{}B-V\cdot\text{opt}\]
Sum over \(t=0,\cdots,T-1\), take expectation
\[\begin{split}\mathbb{E}\{L(t)\}-\mathbb{E}\{L(0)\}-\sum_tV\sum_{n,k}\mathbb{E}\{g_n^{(k)}(R_n^{(k)}(t))|Q(t)\}&\leq{}BT-VT\cdot{}\text{opt}\\\sum_tV\sum_{n,k}\mathbb{E}\{g_n^{(k)}(R_n^{(k)}(t))|Q(t)\}&\geq{}-BT+VT\cdot{}\text{opt}-\mathbb{E}\{L(0)\}\end{split}\]
If consider \(g_n^{(k)}(\cdot)\) as concave increasing, we can use Jensen Inequality to put the expectation sign inside.
Utility Performance
\[\sum_{n,k}g_n^{(k)}(r_n^{(k)}(t))\geq{}\text{opt}-\frac{B}{V}\]
Delay Bound
Assume \(r_n^{(k)\star}\geq{}e>0\)
\[r_n^{(k)'}=r_n^{(k)\star}-e,~f_{nm}^{(k)'}=f_{nm}^{(k)\star}\] \[\begin{split}\Delta(t)-V\mathbb{E}\{\sum_{n,k}g_n^{(k)}(R_n^{(k)}(t))|Q(t)\}&\leq{}B-e\sum_{n,k}Q_n^{(k)}(t)\\\Delta(t)&\leq{}B+Vg_{\max}-e\sum_{n,k}Q_n^{(k)}(t)\\\bar{Q}(t)&\leq\frac{B+Vg_{\max}}{e}\sim\mathcal{O}(V)\end{split}\]
