From BoykinWiki

EEL6507 Spring 2009, Lecture 31, Friday 2009/04/3 (Notes created by Vishnu Vijayakumar)

M/G/1
Find $P_i\!$ for M/G/1

M/G/1

Last time we had determined the following:

$p_k = Prob[k\ in\ the\ system]$

$\begin{align} \vec p &= [p_o,p_1, \cdots]\\ \vec p &= \vec p \cdot P\\ \end{align}$

where, $P = \begin{bmatrix} \alpha_0 &\alpha_1 &\alpha_2 &\cdots \\ \alpha_0 &\alpha_1 &\alpha_2 &\cdots \\ 0 &\alpha_0 &\alpha_1 &\cdots \\ 0 &0 &\alpha_0 &\cdots \\ \vdots &\vdots &\vdots &\vdots \\ \end{bmatrix}$

$p_{ij} = \begin{cases} \alpha_j, &i=0 \\ \alpha_{j-(i-1)}, &i>0,j>i \\ 0, &\mbox{otherwise}\\ \end{cases}$

Solving the Eigenvalue-Eigenvector equation,

$\begin{align} p_j &= \sum_{i=0}^\infty p_i P_{ij} \\ &= p_0 P_{0j} + \sum_{i=1}^\infty p_i P_{ij}\\ p_j &= p_o P_{0j} + \sum_{i=1}^\infty p_i \alpha_{j-i+1}\\ \end{align}$

We now define the Z-Transform as: $P(z) = \sum_{i=0}^\infty p_j z^j$

Taking the Z-Transform,

$\begin{align} P(z) &= p_0 \sum_{j=0}^\infty \alpha_j z^j + \sum_{i=1}^\infty \sum_{j=0}^\infty p_i \alpha_{j-i+1} z^j \\ &= \underbrace{p_0 \sum_{j=0}^\infty \alpha_j z^j}_{v(z)} + \sum_{i=1}^\infty \sum_{\color{Red}j=i-1}^\infty p_i \alpha_{j-i+1}z^j\\ \end{align}$ since, $\alpha_k = 0, k<0\!$

Recall, $\alpha_k = Prob[\text{k arrivals in a service}]\!$

$\begin{align} P(z) &= p_0 v(z) + \sum_{i=1}^\infty \sum_{j=i-1}^\infty p_i z^i(\alpha_{j-i+1} z^{j-i})\\ &= p_0 v(z) + \sum_{i=1}^\infty \sum_{j'=0}^\infty p_i z^i(\alpha_{j'} z^{j'-1})\\ \Rightarrow P(z) &= p_0 v(z) + (p(z)-p_0)\frac{v(z)}{z}\\ \end{align}$

Equilibrium Generating Function

$P(z) = \frac{p_0 (z-1)v(z)}{z-v(z)},\ v(z) = \sum_{k=0}^\infty \alpha_k z^k$

We know that: $\alpha_k = \int\limits_0^\infty \frac{(\lambda x)^k e^{-\lambda x}}{k!}b(x) dx$

$\begin{align} v(z) &= \sum_{k=0}^\infty \alpha_k z^k \\ &=\int\limits_0^\infty (\sum_{k=0}^\infty \frac{(\lambda x z)^k}{k!})\\ &=\int\limits_0^\infty e^{-\overbrace{(1-z)\lambda}^{s} x}b(x)dx\\ \end{align}$

Expected number of arrivals per service

$\begin{align} \sum_k \alpha_k &= \int\limits_0^\infty \sum_k \frac{k(\lambda x)^k e^{-\lambda x}}{k!} b(x) dx \\ &= \int\limits_0^\infty (\lambda x) b(x)dx \\ &= \lambda \int\limits_0^\infty x b(x) dx \\ &= \lambda < x > \end{align}$

From Little's Result

$\begin{align} \lambda \bar{x} &= \rho \qquad \leftarrow \text{Utilization Factor} \\ &= Prob[\text{server is busy}] \\ &= 1-\rho_0 \end{align}$

Example 1: M/M/1 queue

$\begin{align} b(x) &= \mu e^{-\mu x} \\ B^*(s) &= \frac{\mu}{s+\mu} \\ v(z) &= \frac{\mu}{(1-z)\lambda +\mu} \\ P(z) &= \frac{(1-\rho)(z-1)\frac{\mu}{(1-z)\lambda+\mu}}{z-\frac{\mu}{(1-z)\lambda+\mu}} \\ &= \frac{(1-\rho)(z-1)\mu}{z(1-z)\lambda + z\mu -\mu} \\ &= \frac{(1-\rho)\mu}{\mu-z\lambda}\\ &= \frac{1-\rho}{1-\rho z}\\ \end{align}$

$\Rightarrow p_k = (1-\rho)\rho^k$

Example 2: M/D/1 queue

$\begin{align} b(x) &= \delta (x-x_0) \\ B^*(s) &= e^{-sx_0}\\ \end{align}$

$B^*((1-z)\lambda) = e^{-(1-z)\lambda x_0}$

$\begin{align} p(z) &= \frac{(1-\rho)(z-1)e^{-(1-z)\lambda x_0}}{z-e^{-(1-z)\lambda x_0}} \\ &= \frac{(1-\rho)(1-z)}{1-ze^{-(1-z)\lambda x_0}} \\ \end{align}$