EEL6507sp09L25

From BoykinWiki

Jump to: navigation, search

Contents

EEL6507 Spring 2009, Lecture 25, Monday 2009/03/16 (Notes created by Adam Flynn)

Coefficient of Variation

The coefficient of vartiation (C) is defined as:

C \equiv \frac{\sigma^2}{{\left \langle x \right \rangle}^2}

Exponential

  • pdf: p(x) = λe − λx
  • \sigma^2 = \frac{1}{\lambda^2}
  • \left \langle x \right \rangle = \frac{1}{\lambda}
  • C = 1

Erlangian

  • pdf: b_r(x) = \frac{r\lambda \left(r\lambda x\right)^{r-1}e^{-r\lambda x}}{(r-1)!}\,\!
  • \sigma = \frac{1}{r \lambda}
  • \left \langle x \right \rangle = \frac{1}{\lambda}
  • C = \frac{1}{r^2} < 1 \ for\ r > 1


How do we get C > 1?

  • Answer: parallel servers

Why do we want C > 1?

  • Answer: For Heavy-Tail Distributions.
  • A Heavy-Tail Distribution is useful for systems with large variances (e.g. file sizes in a file system).

Parallel Servers

For each arrival, there is a probability αi of choosing server i with exponentially distributed service time μi.

Flow diagram for parallel servers
Flow diagram for parallel servers

The probability the service time for a given event is less than or equal to t is:

Prob[T\le t]= \sum_{i=1}^k {Prob[go\ to\ i]*Prob[T\le t\ |\ i]}

The second term is just the CDF of the service time, so the pdf of the service time is:

b(t)=\frac{\partial}{\partial t} Prob[T\le t] = \sum_{i=1}^k {\alpha_i \mu_i e^{- \mu_i t}}

This is also known as the hyperexponential distribution.

Proof that C \ge 1 for Parallel Servers

The LaPlace transform of the pdf b(x) above is:

B^*(s) = \sum_{i=1}^k {\alpha_i \left ( \frac{\mu_i}{s + \mu_i} \right ) }

The first derivative is:

B^{*'}(s) = \sum_{i=1}^k {- \alpha_i \mu_i (s + \mu_i)^{-2} }

Thus, the mean is:

\left \langle x \right \rangle = B^{*'}(0) = - \sum_{i=1}^k { \frac{\alpha_i}{\mu_i} }

Now we know the denominator for the coefficient of variation. To determine the numerator (σ2), we can use the following relationships:

\sigma^2 = \left \langle x^2 \right \rangle - \left \langle x \right \rangle^2

\left \langle x^2 \right \rangle = \sum_{i=1}^k { \frac{2 \alpha_i}{\mu_i^2} } for a Markovian distribution.

Thus,

C = \frac{\sigma^2}{\left \langle x \right \rangle^2} = \frac{\left \langle x^2 \right \rangle - \left \langle x \right \rangle^2}{\left \langle x \right \rangle^2} = \frac{\left \langle x^2 \right \rangle}{\left \langle x \right \rangle^2} -1 = 2 \left ( \frac{\sum_{i=1}^k { \alpha_i \frac{1}{\mu_i^2} }}{\left ( \sum_{i=1}^k { \alpha_i \frac{1}{\mu_i} } \right )^2} \right ) -1 .

If f(x) = x^2, C = 2 \left ( \frac{\sum_{i=1}^k {\alpha_i f \left ( \frac{1}{\mu_i}\right )}}{f \left ( \sum_{i=1}^k {\alpha_i \frac{1}{\mu_i} } \right )} \right ) -1.

Since f(x) is convex[1], it can be shown that C \ge 1 for Parallel Servers/hyperexponentials.

M / H2 / 1 Queue

The state of a M / H2 / 1 queue has two components:

  • Number of customers
  • Which server is working
Markov Chain for M / H2 / 1 queue
Markov Chain for M / H2 / 1 queue

lecture voice recording

lecture_voice_recording

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