EEL6507sp09L12

From BoykinWiki

Jump to: navigation, search

Contents

EEL6507 Spring 2009, Lecture 12, Monday 2009/02/04 (Notes created by Ryan C.W.Wong)

  • More on Birth-Death Equilibrium
  • M/M/I Queue
  • Little's result revisit

Ergodic, Transient and Recurrent Classification of Birth-Death Equilibrium

Recalled

P_n=P_0 \prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}},

and since we should have

\sum_{n=0}^{\infin} P_n = 1,

hence,

P_0 = \left(\sum_{n=0}^{\infin} \prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}}\right)^{-1} = \frac{1}{S_1}.

Let

S_2 = \sum_{n=0}^{\infin} \left(\lambda_n \prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}}\right)^{-1}

We then can make the following classifications about the states of the Birth-Death process

  • Transient

S_1 = \infin , S_2 < \infin

  • Recurrent null

S_1 = \infin , S_2 = \infin

  • Ergodic

S_1 < \infin , S_2 = \infin

It should also be pointed that the above conditions are both necessary and sufficient.

Among them, the ergodic case is of most interest to our studies and the condition for ergodicity is met whenever the sequence {\frac{\lambda_k}{\mu_k}} remains below unity from some \ k onwards, that is, if there exists some \ k_0 such that for all k \leq k_0 we have \frac{\lambda_k}{\mu_k} < 1 .

The classical M/M/1 Queueing System

Recalled from the previous lecture, M/M/1 queue with following parameters:

  • Customer arrival rate: \ \lambda
  • Service rate: \ \mu

Then

\begin{align} P_k&=Prob\left[k\ customers\ in\ queue\ in\ limit \right]\\ &=P_0 \left(\frac{\lambda}{\mu}\right)^k \end{align}

and

\begin{align} P_0 &= \left(\sum_{k=0}^{\infin}\left(\frac{\lambda}{\mu}\right)^k\right)^{-1} &= 1- \frac{\lambda}{\mu} \end{align}


In M/M/1 queue, customers arrives with Markovian process with parameter \ \lambda and the service also modeled as a Markovian process with parameter \ \mu, that is

\begin{align} Prob \left[ time\ between\ arrivals\ \geq t \right] &= e^{-\lambda t}\\ Prob \left[ services\ take\ \geq t \right] &= e^{-\mu t}\\. \end{align}

Then the average interarrival time is

\begin{align} <interarrival\ time> = \int\limits_{0}^{\infin} t\lambda e^{-\lambda t} dt = \frac{1}{\lambda}, \end{align}

and average service time is

\begin{align} <service\ time> = \int\limits_{0}^{\infin} t\mu e^{-\mu t} dt = \frac{1}{\mu}. \end{align}

Next, we classify Transient, Recurrent and Ergodic for M/M/1 queue based on different value of \ \lambda and \ \mu.

We have

\begin{align} S_1 &= \sum_{n=0}^{\infin} \prod_{k=0}^{n-1} \frac{\lambda_k}{\mu_{k+1}} &= \sum_{n=0}^{\infin} \left(\frac{\lambda}{\mu}\right)^n \end{align}

and

\begin{align} S_2 &= \sum_{n=0}^{\infin} \left(\lambda_n \prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}}\right)^{-1} &= \sum_{n=0}^{\infin} \frac{1}{\lambda} \left(\frac{\mu}{\lambda}\right)^n \end{align}

then from basic calculus we know that

\begin{align} S_1 &= \infin\ if\ \lambda \geq \mu \\ S_1 &< \infin\ if\ \lambda < \mu \\ \end{align}

and

\begin{align} S_2 &= \infin\ if\ \lambda \leq \mu \\ S_2 &< \infin\ if\ \lambda > \mu \\ \end{align}

According the classification rules provided by the previous section, we then have,

  • Transient

\ \lambda > \ \mu

  • Recurrent null

\ \lambda = \ \mu

  • Ergodic

\ \lambda < \ \mu

Little's result revisit

We have previously showed that for G/G/1

\ P_0 = 1 - \rho

with \ \rho being known as the traffic intensity or probability of busy of the system.

For M/M/1, we have \rho = \frac{\lambda}{\mu}.

We can also make the same classifications based on the value of \ \rho

  • Transient

\ \rho > 1

  • Recurrent null

\ \rho = 1

  • Ergodic

\ \rho < 1

Next we find out the average number of customers in the system, \ \bar{N} ,

\begin{align} \bar{N} &= \sum_{k=0}^{\infin} k P_k \\ &= (1-\rho)\sum_{k=0}^{\infin} k \rho^{k} \\ &= (1-\rho)\frac{\rho}{(1-\rho)^2} \\ &= \frac{\rho}{1-\rho} \\ &= \frac{\lambda}{\mu-\lambda} \end{align}

According to Little's result, we know that

\begin{align} \bar{N} &= \lambda \bar{T} \end{align}

where \ \bar{T} is the average system time. Hence, it is easy to see that

\begin{align} \bar{T} &= \frac{1}{\mu} \frac{1}{1-\rho} \\ &= \frac{1}{\lambda} \frac{\rho}{1-\rho} \\ \end{align}

then the average waiting time \ \tilde{T} can be found as the difference between the average system time and the average service time, that is,

\begin{align} \tilde{T} &= \bar{T} - \frac{1}{\mu} \\ &= \frac{1}{\mu} \left( \frac{1}{1-\rho} -1 \right) \\ &= \frac{1}{\mu} \frac{\rho}{1-\rho} \\ &= \frac{1}{\mu} \bar{N} \end{align}

It says that the average waiting time is equal to average number of customers in the queue times the average service time, which matches our intuition.

Lecture Voice Recording

lecture_recording

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