EEL6507sp09L19

From BoykinWiki

Jump to: navigation, search

Contents

EEL6507 Spring 2009, Lecture 19, Monday 2009/02/23 (Notes created by Yonggang Liu)

Covered in this lecutre:

  • Introduce method of stages

Talk about Markov model

What are the problems with the Markovian Models?

  • Real systems are often non-Markovian
    • Service has a different pdf
    • arrival has a different pdf
  • Bulk Service
  • Prioritized Customers
  • Queueing Networks

What are good about the Markovian Models?

  • Simple
  • Memoryless (no explicit history)
  • One solution do all B-D models

Method of stages

We want to address the weakness of Markovian Models (typically to deal with the models having pdf that Markovian Models can not solve), as well as keeping the simplicity of the Markovian Models.

Erlangian-r distribution

Consider a new pdf:

b\left(x\right) = 4 \mu^2 x e^{2 \mu x}

Claim:

b_1\left(y\right) = 2 \mu e^{2\mu y}

then:

\begin{align} b(x) &= \int_0^x b_1(x-y)b_1(y)dy\\ &= \int_0^x 4 \mu ^2 e^{-2 \mu (x-y)- 2 \mu y}dy\\ &= \int_0^x 4 \mu ^2 e^{-2 \mu x}dy\\ &= 4 \mu ^2 x e^{-2 \mu x} \end{align}

b(x)is pdf for sum of two random variables each with pdf: 2μe − 2μx,so,E[x] = \frac {1} {\mu}

Erlang-r distribution is:

b_r \left(x \right) = \frac {r \mu (r \mu x)^{r-1}} {(r-1)!} e^{-r \mu x}

Claim: br(x) is pdf for sum of Xr − 1,X1, where Xr − 1distributes as br − 1(x) and X1 is exponential. Then, br(x) is sum of r exponentials.

See the Laplace transform of Erlangian-r distribution:

\begin{align} B_r^*(s) &= \int_0^\infty e^{-sx} \frac{r \mu(r \mu x)^{r-1}}{(r-1)!}e^{-r \mu x}dx\\ &= \frac{(r \mu)^r}{(r-1)!} \int_0^\infty x^{r-1} e^{-(s+r \mu)x}dx \end{align}

First, let's see how to solve:

I_{\alpha ,r} = \int_0^\infty x^r e^{-\alpha x}dx

Approach 1:

\begin{align} I_{\alpha ,r} &= \int_0^\infty x^r e^{-\alpha x}dx\\ &= -\frac{x^r e^{-\alpha x}}{\alpha}|_0^\infty - \int_0^\infty \frac{e^{-\alpha x}}{-\alpha}rx^{r-1} dx\\ &= \frac{r}{\alpha} \int_0^\infty e^{-\alpha x}x^{r-1}dx\\ &= ...\\ &= \frac{r!}{\alpha^{r+1}} \end{align}

Approach 2:

\frac {I_{\alpha,r}}{I_{\alpha,r-1}} = \frac {r}{\alpha}, I_{\alpha,0} = \frac {1}{\alpha}
\prod_{r=1}^{k} \frac{I_{\alpha,r}}{I_{\alpha,r-1}} = \frac{I_{\alpha,k}}{I_{\alpha,0}}= \frac{k!}{\alpha^k}

So,

I_{\alpha,k} = \frac{k!}{\alpha^{k+1}}

Therefore,

\begin{align} B_r^*(s) &= \frac{(r \mu)^r}{(r-1)!} \int_0^\infty x^{r-1} e^{-(s+r \mu)x}dx\\ &= \frac{(r \mu)^r}{(r-1)!} I_{(s+r \mu), r-1}\\ &= \frac{(r \mu)^r}{(r-1)!} \frac{(r-1)!}{(s+r \mu)^r}\\ &= (\frac{r \mu}{s+r \mu})^r \end{align}

See the Laplace transform of exponential distribution:

\begin{align} B^\sigma(s) &= \int_0^\infty e^{-st} \mu' e^{- \mu' t}dt\\ &= \mu' \int_0^\infty e^{-(s+\mu')t}dt &= \frac{\mu'}{s+ \mu'} \end{align}

Set μ' = rμ then,

(B^\sigma(s))^r = (\frac{r\mu}{s+r\mu})^r = B_r^*(s)

Therefore, Erlangian-r is the sum of r-exponential with rate rμ!

Variance of Erlangian distribution

We know the mean of Erlangian distribution is \frac{1}{\mu}, then what is the variance of Erlangian distribution?

\begin{align} B^*(0) &= 1\\ {B^*}'(0) &= -<X>\\ {B^*}''(0) &= <X^2> \end{align}
\begin{align} \frac{\partial B^*(s)}{\partial s} &= -r(\frac{s+r\mu}{r\mu})^{-r-1}(\frac{1}{r\mu})\\ \frac{\partial^2 B^*(s)}{\partial s^2} &= -r(-(r+1))(\frac{s+r\mu}{r\mu})^{-r-2}(\frac{1}{r\mu})^2 \end{align}

So,

<X> = \frac{1}{\mu}
<X^2> = \frac{r(r+1)}{r^2 \mu^2}=(\frac{r+1}{r})\frac{1}{\mu^2}
\sigma_r^2 = (\frac{r+1}{r}){\frac{1}{\mu^2}}-\frac{1}{\mu^2}=\frac{1}{r}\frac{1}{\mu^2}

Markov Model for Erlangian distribution

The r-stage Erlangian server Er
The r-stage Erlangian server Er

Consider the case in which we provide an r-stage service facility, as shown in the left. For this system, the mean time to go though is \frac{1}{\mu}. Consider the First stage,

\frac{dP_1}{dt}=-r\mu P_1

Solve above equation, we get P1(t) = e − μt, which is the CDF for exponential. The time to get through the whole system is Erlangian(x) distributed.

Lecture Voice Recording

lecture_recording

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