From BoykinWiki

Jump to: navigation, search

EEL6507 Spring 2009, Lecture 33, Wednesday 2009/04/08 (Notes created by Ryan C.W.Wong)

Solving the distribution of the waiting time for M/G/1 queue.

Little's results revisit

[Little's results] state that

$\bar{N} = \lambda \bar{T}$

where

$\bar{N}$ is the expected number in queue
$\ \lambda$ is the limit of arrival rate
$\bar{T}$ is the average of system time, which is equal to the sum of average of waiting time ( $\bar{w}$ ) and service time ( $\bar{x}$ )

Average Waiting time

From [Little's results], we then have

$\begin{align} \bar{w} &= \frac{\lambda \bar{T} - \lambda \bar{x}}{\lambda} &= \frac{\bar{N} - \rho}{\lambda} &= \frac{E\left[ q \right] - \rho}{\lambda} \end{align}$

where

$E[q] =\rho+\frac{\rho ^2}{2(1-\rho)}(1+C_b^2)$

is given in [previous lecture].

Thus, the average waiting time is then given by

$\begin{align} \bar{w} &= \frac{\rho ^2}{2\lambda(1-\rho)}(1+C_b^2) \\ &= \bar{x}\frac{\rho}{2(1-\rho)}(1+C_b^2) \end{align}$

Examples:

M/M/1 queue in which $\ C_b = 1$ , thus

$\begin{align} \bar{w} &= \bar{x}\frac{\rho}{(1-\rho)} \\ &= \bar{x}\bar{N} \end{align}$

M/D/1 queue in which $\ C_b = 0$ , thus

$\begin{align} \bar{w} &= \bar{x}\frac{\rho}{2(1-\rho)} \\ \end{align}$

We can see that the average waiting time of M/D/1 is only half of that of M/M/1

Distribution of Waiting Time

Time diagram of queue and service

The above figure represents the arrivals and departures of the queue and service, which we have seen in [previous lecture]. As pointed out before, the number of arrivals during $\ X_n$ is denoted as $\ v_n$ . It can be seen that the number of arrivals during $\ T_n$ is actually equal to the number of customers left behind by $\ C_n$ when he leaves the system, i.e., $\ q_n$ .

Thus as an analogy to what we have derived for the relation between $\ B^{*}(s)$ and $\ V(z)$ , which is the Laplace transform of the distribution of $\ X_n$ and the z-transform of the distribution of $\ v_n$ respectively, we can also show that

$Q(z) = S^{*}\left(\lambda(1-z)\right)$

where $\ S^{*}(s)$ and $\ Q(z)$ is the laplace transform of the distribution of $\ T_n$ and the z-transform of the distribution of $\ q_n$ respectively.

On the other hand, we have

$\begin{align} Q(z) &= \frac{(1-\rho)(z-1)V(z)}{z-V(z)} \\ &= \frac{(1-\rho)(z-1)B^{*}\left(\lambda(1-z)\right)}{z-B^{*}\left(\lambda(1-z)\right)} \end{align}$

from [previous lecture]..

Moreover, it is known that $\ T_n = X_n + W_n$ and $\ W_n$ and $\ X_n$ are independent random variables. Thus, the distribution of $\ T_n$ is equal to the convolution of the distribution of $\ W_n$ and $\ X_n$ . In other words, the Laplace transform of the distribution of $\ T_n$ simply equals the product of the Laplace transform of the distribution of $\ W_n$ and $\ X_n$ . That is

$\ S^{*}(s)=W^{*}(s)B^{*}(s)$

Hence, the Laplace transform of the distribution of waiting time is

$\begin{align} W^{*}\left(\lambda(1-z)\right) &= \frac{S^{*}\left(\lambda(1-z)\right)}{B^{*}\left(\lambda(1-z)\right)} \\ &= \frac{(1-\rho)(z-1)}{z-B^{*}\left(\lambda(1-z)\right)} \end{align}$

Let $\ z = 1-s/\lambda$ and after some simple manipulations, we have