From BoykinWiki

EEL6507 Spring 2009, Lecture 27, Friday 2009/03/20 (Notes created by Kyungyong Lee)

Prove Jackson Theorem

$\begin{alignat}{2} F_k(t)& =Prob[N(t)=k, T>t]\\ F_k(t+\Delta t) & =Prob[N(t + \Delta t)=k,T>t+\Delta t] \\ & = \sum_{j=0}^\infty Prob[N(t+\Delta t)=k,\ T>t+\Delta t\ and\ T>t,\ N(t)=j](\text {marginalization})\\ & = \sum_{j=0}^\infty Prob[N(t)=j,\ T>t]Prob[N(t+\Delta t)=k,\ T>t+\Delta t | \underbrace{N(t)=j}_{=0,if\ k<j},T>t](\text {conditional prob.})\\ & = \sum_{j=0}^kF_j(t)Prob[N(t+\Delta t)=k,T>t+\Delta t|N(t)=j,T>t] \\ & = F_k(t)Prob[N(t+\Delta t)=k, T>t+\Delta t|N(t)=k, T>t](\text{no arrival, no departure})\\ & \ \ \ + F_{k-1}(t)Prob[N(t+\Delta t)=k, t>t+\Delta t|N(t)=k-1,T>t](\text{one arrival, no departure}) \\ & = F_k(t)(1-\Delta t\lambda)(1-\mu_k\Delta t)+F_{k-1}(t)(1-\mu_{k-1}\Delta t)\Delta t \lambda \\ & = F_k(t)-\Delta t(\lambda + \mu_k)F_k(t)+\lambda \Delta tF_{k-1}(t) + O(\Delta t^2) \\ \frac{F_k(t+\Delta t)-F_k(t)}{\Delta t} & = -(\lambda+\mu_k)F_k(t)+\lambda F_k(t)+\lambda F_{k-1} + O(\Delta t)\\ \text {If we let} \lim_{\Delta t\rightarrow 0}\ \ \text{then} \\ \frac{d}{dt}F_k(t) &=-(\lambda+\mu_k)F_k(t)+\lambda F_{k-1}(t)\\ \text {To solve above equation,}\\ \text {Let} \ F_k(t) =P_kg(t) \\ F_k(0) & =P_kg(0)=P_k \\ \frac{d}{dt}F_k(t) & =P_kg'(t)=-(\lambda + \mu_k)P_kg(t)+\lambda P_{k-1}g(t) \\ P_kg'(t) & =P_k(-\lambda g(t))+(\lambda P_{k-1}-\mu_kP_k)g(t) \\ g'(t) & = (-\lambda g(t))+\frac{\overbrace{(\lambda P_{k-1} - \mu_kP_k)}^{ = 0 \because\text{(flow in = flow out)}}}{P_k}g(t) \\ g'(t) & =-\lambda g(t) \\ g(t) & = e^{-\lambda t} \\ \end{alignat}$

General Queueing Network

$\begin{alignat}{2} r_{i,j}= \text {Prob(go into queue j, after queue i)} \\ \end{alignat}$

$\begin{alignat}{2} \gamma_i= \text {rate entering into queue i from outside} \end{alignat}$

$\begin{alignat}{2} l_i & = \text {Prob(leave from the network after completing service in the i node)} \\ & = 1-\sum_{j=1}^N r_{i,j} \\ \end{alignat}$

$\begin{alignat}{2} & \lambda_i \equiv \text {total incoming rate at queue } i \\ & \Rightarrow \lambda_i = \gamma_i + \sum_{j=1}^N \lambda_jr_{ji} \\ & \overrightarrow{\lambda} = [\lambda_1,\ \lambda_2,\ \cdots \ ,\lambda_N] \\ & \overrightarrow{\gamma} = [\gamma_1,\ \gamma_2,\ \cdots \ ,\gamma_N] \\ & \overrightarrow{\lambda} = \overrightarrow{\gamma}+\overrightarrow{\lambda}R \ ([R]_{ij}=r_{ij}\\ & \overrightarrow{\lambda}(I-R)=\overrightarrow{\gamma} \\ & \overrightarrow{\lambda}=\overrightarrow{\gamma}(I-R)^{-1} \text { ,for all nodes, } \lambda_i < \mu_im_i \\ \end{alignat}$

Example

networks of queue

$\begin{alignat}{2} & R=\begin{bmatrix} 0 & \frac{1}{2} \\ \frac{1}{2} & 0 \end{bmatrix} \\ & [\lambda_1\ \lambda_2]=[1\ \ \ 1]\begin{bmatrix} 1 & -\frac{1}{2} \\ -\frac{1}{2} & 1 \end{bmatrix}^{-1} \\ \Rightarrow \lambda_1 = \lambda_2 = 2 \\ \end{alignat}$

lecture voice recording

lecture_voice_recording

EEL6507sp09L27

From BoykinWiki

Contents

EEL6507 Spring 2009, Lecture 27, Friday 2009/03/20 (Notes created by Kyungyong Lee)

Prove Jackson Theorem

General Queueing Network

Example

lecture voice recording

Views

Personal tools

Navigation

Search

Toolbox