Queue
Definition
- Arrival: \(A(t)\)
- Cumulative arrival: \[X[t_1,t_2]=\int_{t_1}^{t_2}A(t)dt\]
- Service: \(\mu(t)\)
- Cumulative departure: \[Y[t_1,t_2]=\int_{t_1}^{t_2}Y(t)dt\leq\int_{t_1}^{t_2}\mu(t)dt\]
- \(Y(t)=Q(t)~if~Q(t)>0\quad0~otherwise\)
- \(Q(t)=X[0,t]-Y[0,t],Q(0)=0\)
Interval and Conserving
- Def: An interval \(I=[t_1,t_2]\) is a busy period if \(Y(t)>0,\forall{}t\in{}I\) and \(Y(t_1^-)=Y(t_2^+)=0\)
- Def: A work conserving single server system is one where \(Y(t)=\mu(t)\) wherever \(Q(t)>0\)
If we start from an empty system, and \(Q(t)>0\), then \[\exists{}t^* \text{ with } Q(t^*)=0 \text{ s.t. } Q(t)=X[t^*,t]-\int_{t^*}^t\mu(t)dt\]
Stability
- Def: \(X[0,t]\) has a rate \(\lambda\) if \(\lim_{t\rightarrow\infty}\frac{X[0,t]}{t}=\lambda\) w.p.1
- Def: \(\mu(t)\) has rate \(\mu\) if \(\lim_{t\rightarrow\infty}\frac{\int_0^t\mu(t)}{t}=\mu\) w.p.1
- Def: \(Q(t)\) is rate stable if \(\lim_{t\rightarrow\infty}\frac{Q(t)}{t}=0\) w.p.1
- Def: \(Q(t)\) is mean rate stable if \(\lim_{t\rightarrow\infty}\frac{E[Q(t)]}{t}=0\)
Theorem-Rate Stability
Suppose \(Q(t)=X[0,t]-Y[0,t]\), and \(X[0,t]\) has rate \(\lambda\) and \(\mu(t)\) has rate \(\mu\), then \(Q(t)\) is rate stable if and only if \(\lambda\leq\mu\)
\[Q(t)\text{ stable } \rightarrow\lambda\leq\mu\] \[\frac{Q(t)}{t}=\frac{X[0,t]}{t}-\frac{Y[0,t]}{t}\geq\frac{X[0,t]}{t}-\frac{\int_0^t\mu(t)}{t}\]
\[Q(t)\text{ stable } \leftarrow\lambda\leq\mu\]
Little's law
\[Q_{av}=\lim_{t\rightarrow\infty}\frac{1}{t}\int_{\tau=0}^tQ(\tau)d\tau,D_{av}=\lim_{k\rightarrow\infty}\frac{1}{k}\sum_{k=1}^kD_k\] \[\Rightarrow{}Q_{av}=\lambda{}D_{av}\]
Lyapunov Analysis
Definition
Denote \(\vec{Q}(t)=(Q_1(t),\dots,Q_k(t))\), Def \(L(\vec{Q}(t))\) is a Lyapunov-function if
- \(L(\vec{Q}(t))\geq0\)
- \(L(0)=0\)
Define one-slot conditional Lyapunov drift \[\Delta(t)=E\{L(\vec{Q}(t+1))-L(\vec{Q}(t))|\vec{Q}(t)\}\]
Theorem
Suppose \(L(\vec{Q}(t))\) is a Lyapunov function and satisifes \(\Delta(t)\leq{}B-e\sum_kQ_k(t)\) and \(L(\vec{Q}(0))<\infty\), then
- \(e>0\rightarrow{}Q(t)\) is strongly stable \[\lim_{T\rightarrow\infty}\sup\frac{1}{T}\sum_{t=0}^{T-1}\sum_kE\{Q_k(t)\}\leq\frac{B}{e}\]
- \(e\geq0\) and \(L(\vec{Q})=\sum_k{}w_kQ_k\), then \[\lim_{t\rightarrow\infty}\frac{E\{Q_k(t)\}}{t}=0,\forall{}k\]
Proof is made by list the inequality from \(t=0\) to \(t=T\) and sum them up. For the first one, divide by \(T\) then is obvious. For the second one, put exception into square, the left side is \(O(\sqrt{T})\).
Example
\(A(t), \mu(t), \sim{}Bernoulli~\lambda,\mu\) \[Q(t+1)=(Q(t)-\mu(t)+A(t))^+,L(Q(t))=\frac{1}{2}Q^2(t)\] \[\Delta(t)=\frac{1}{2}E\{Q^2(t+1)-Q^2(t)|Q(t)\}\leq\cdots=E\{\frac{1}{2}(\mu(t)-A(t))^2-Q(t)(\mu(t)-A(t))|Q(t)\}\leq\frac{1}{2}-Q(t)(\mu-\lambda)\] \[\bar{Q}(t)\leq\frac{1}{2(\mu-\lambda)}\]
