EEL6507sp09L32

From BoykinWiki

Jump to: navigation, search

Contents

EEL6507 Spring 2009, Lecture 32, Monday 2009/04/06 (Notes created by Dexiang Wang)

  • Solving for expected system size (number of customers) in M/G/1 queues.

Pollaczek-Khinchine

- What is the average system size?

- Dynamics of M/G/1 queues:

\begin{align} q_{n+1}&=v_{n+1}\qquad\qquad\quad if\quad q_n=0\\ &=q_n-1+v_{n+1}\quad if\quad q_n>0 \end{align}

- Introduce Δk :

\begin{align} \Delta_k&=1\qquad if\qquad k>0\\ &=0\qquad if\qquad k=0 \end{align}

- We get:

q_{n+1}=q_n-\Delta_{n}+v_{n+1}\

- Now, we want:

\lim_{n\rightarrow \infty} E[q_n]=average\ number\ in\ system\ in\ steady\ state\

Moments/Expectations

- When system is ergodic, we have following hold (can be proved outside class):

\lim_{n\rightarrow \infty} E[q_n^j]=E[q^j],\quad q=random\ variable\ in\ steady\ state

- How should we use this property?

- Trick: look at moments of the equation!

- We square both sides of q_{n+1}=q_n-\Delta_{q_n}+v_{n+1} :

q_{n+1}^2=(q_n-\Delta_{q_n}+v_{n+1})^2\
q_{n+1}^2=q_n^2+\Delta_{q_n}^2+v_{n+1}^2-2q_n\Delta_{q_n}+2q_nv_{n+1}-2\Delta_{q_n}v_{n+1}\

- Take expectations on both sides:

E[q_{n+1}^2]=E[q_n^2]+E[\Delta_{q_n}^2]+E[v_{n+1}^2]-E[2q_n\Delta_{q_n}]+E[2q_nv_{n+1}]-E[2\Delta_{q_n}v_{n+1}]\

- We need to evaluate following terms:

\begin{align} E[\Delta_{q_n}^2]&=Prob[q_n=0]\times0+Prob[q_n>0]\times1\\ &=Prob[busy] \\ &=\rho \\ E[q_n\Delta_{q_n}]&=\sum_{r=0}^\infty Prob[q_n=r]r\Delta_r\\ &= E[q_n]\\ E[q_nv_{n+1}]&=\sum_{r=0}^\infty \sum_{w=0}^\infty Prob[q_n=r,v_{n+1}=w]rw \\ &= \sum_{r=0}^\infty \sum_{w=0}^\infty Prob[q_n=r]Prob[v_{n+1}=w]rw \\ &= E[q_n]E[v_{n+1}]\\ &(q_n\ independent\ of\ v_{n+1})\\ Similarly,\\ E[\Delta_{q_n}v_{n+1}]&= E[\Delta_{q_n}]E[v_{n+1}]\\ &=\rho E[v_{n+1}] \end{align}

- Plug above evaluations back into above linear incremental equation, we get:

E[q_{n+1}^2]=E[q_n^2]+\rho+E[v_{n+1}^2]-2E[q_n]+2E[q_n]E[v_{n+1}]-2\rho E[v_{n+1}]\

- Take limit on both sides (n\rightarrow \infty):

0=\rho+E[v^2]-2E[q]+2E[q]E[v]-2\rho E[v]\

- And we already know:

E[v]=V'(1)=\left \langle X \right \rangle\lambda=\rho

- Finally, we get:

\begin{align} E[q]&=\frac{\rho}{2(1-\rho)}+\frac{E[v^2]-2\rho^2}{2(1-\rho)}\\ &=\frac{E[v^2]+\rho-2\rho^2-\rho+\rho}{2(1-\rho)}\\ &=\frac{2\rho(1-\rho)+E[v^2]-E[v]}{2(1-\rho)}\\ &=\rho+\frac{E[v^2-v]}{2(1-\rho)}\\ &=V'(1)+\frac{V''(1)}{2(1-V'(1))} \end{align}

Connect Mean Queue Length to B * (s)

- P-K transform equation:

V(z)=B^*((1-z)\lambda)\
V''(1)=B^{*''}(0)\lambda ^2=\left \langle \lambda ^2 X^2 \right \rangle

- So, we have:

E[q]=\rho+\frac{\left \langle (\lambda X) ^2 \right \rangle}{2(1-\rho)}

- Remember:

\sigma_b^2=\left \langle X^2 \right \rangle - \left \langle X \right \rangle ^2

- We can rewrite E[q]\ as:

\begin{align} E[q]&=\rho+\frac{\lambda^2\left \langle X \right \rangle ^2 + \lambda^2\sigma_b^2}{2(1-\rho)}\\ &=\rho+\frac{\rho ^2}{2(1-\rho)}(1+C_b^2) \end{align}

Verification with M/M/1 Queue

- For M/M/1 queue, we have:

C_b=1,\ \sigma=\frac{1}{\mu},\ \left \langle X \right \rangle = \frac{1}{\mu}

- Then,

\begin{align} E[q]&=\rho+\frac{\rho^2}{2(1-\rho)}\\ &=\rho+\frac{\rho ^2}{2(1-\rho)}(1+1^2)\\ &=\frac{\rho}{1-\rho}\\ &=\sum_{k=0}^{\infty}k\rho^k(1-\rho)\\ &=\bar{N}\\ which\ is\ the&\ same\ as\ we\ derived\ before \end{align}

Expected System Size for M/D/1

- For M/D/1 queue, we have:

b(x)=\delta(x-x_0),\ \sigma_b=0,\ C_b=0

- Hence,

\begin{align} E[q]&=\rho+\frac{\rho^2}{2(1-\rho)}\\ &=\frac{2\rho-\rho^2}{2(1-\rho)}\\ &=\frac{\rho}{1-\rho}-\frac{\rho^2}{2(1-\rho)}\\ which\ gives\ us\ a\ smaller&\ expected\ queue\ length\ than\ M/M/1\ queue\ gives\ us \end{align}

Lecture_Voice_Recording

lecture_recording

Retrieved from "http://boykin.acis.ufl.edu/wiki/index.php/EEL6507sp09L32"