Performance evaluation of networks: class #5

Little's formula

Wikipedia article, and something I've found about it's application.

(1)
\begin{align} 0 < t_1 < \dots < t_n \qqad \textrm{the time of arrival of each object} \end{align}
(2)
\begin{align} \bar{N} = \textrm{expected number of objects/customers/packets in steady-state.} \end{align}
(3)
\begin{align} \bar{T} = \textrm{expected sujourn in steady-state.} \end{align}
(4)
\begin{align} \lambda = \textrm{expected number of objects/customers/packets arriving to the system} \end{align}
(5)
\begin{align} \lim_{N \rightarrow \infty} \frac 1 N \sum^N_{i=0} (t_{i+1} - t_i) = \frac 1 \lambda \end{align}

Lambda can be deterministic:

(6)
\begin{align} t_i = i, \lambda = 1 \end{align}

Or exponential:

(7)
\begin{align} \{t_i\}_i, P( (t_{i+1} - t_i) \leq x ) = 1 - e^{-\lambda_i x} \end{align}

So, if lambda exists, Little's formula holds:

(8)
\begin{align} \bar{N} = \lambda \bar{T} \end{align}

So, we can understand the departure rate (not rigurous!) as:

(9)
\begin{align} \bar{N} \frac 1 {\bar{T}} = \lambda \end{align}

Simple proof

We assume FIFO behaviour (if not, it is a mess to prove). We find a $c > 0$, such as the system is empty at that time, and we consider the objects that entered and left the system before c.

(10)
\begin{align} a_i = \textrm{arrival time of object i} \end{align}
(11)
\begin{align} d_i = \textrm{departure time of object i} \end{align}
(12)
\begin{align} k=k(c) = \textrm{number of arrivals in} (0, c) \end{align}
(13)
\begin{align} a_1 = t_1 < t_2 < \dots < t_{2k} = d_k \qquad \textrm{(if the objects are served FIFO)} \end{align}
(14)
\begin{align} \bar{N}(c) = \textrm{expected number of objects/customers/packets in steady-state in (0, c).} \end{align}
(15)
\begin{align} \bar{T}(c) = \textrm{expected sujourn in steady-state in (0, c).} \end{align}
(16)
\begin{align} \bar{N}(c) = \frac 1 c \int_0^k N(t) dt = \frac 1 c \sum_{i=1}^{2k-1} N(t_i^+) (t_{i+1} - t_i) \end{align}
(17)
\begin{align} \bar{T}(c) = \frac 1 k \sum_{i=1}^k (d_i - a_i) \end{align}

It can be shown that the two sums represent the same (this needs the system to be empty at c), so:

(18)
\begin{align} \frac k c \bar{T}(c) = \bar{N}(c) \end{align}

So, we have made three assumptions:
- The system is FIFO
- That lambda exists.
- There are infinite times where the system is empty.

So, we make c grow to infinity, and then we have:

(19)
\begin{align} \lambda = \frac {k(c)} c \bar{T} = \bar{N} \end{align}

We could relax the requirement of the system being empty infinite times, to just have a recursive point, where it always returns to.

Go back to M | M | 1

In: poisson($\lambda$), Out: Exp($\mu$)

(20)
\begin{align} \pi(i) = (1 - \rho) \rho^i, \rho = \frac \lambda \mu \end{align}

(FIXME: didn't completely follow this)

(21)
\begin{eqnarray} \bar{N} &=& \frac \rho {1 - \rho} \\ \bar{T} &=& \frac {\bar{N}} \lambda = \frac 1 {\mu - \lambda} \\ \bar{W} &=& \bar{T} - \frac 1 \rho = \frac 1 {\mu - \lambda} - \frac 1 \mu = \frac \lambda {\mu - \lambda} \mu \end{eqnarray}

Example application

FIXME: couldn't copy in time.

Let's compare a M|M|1 with a M|M|2 (with half the speed).

For the M|M|2 queue, we have both servers at rate $\mu$. For the M|M|1, one server at rate $2\mu$. For both, the arrival rate is $2\lambda$.

M|M|2 case:

Aloha

page revision: 10, last edited: 07 Dec 2009 06:41
Unclear, need to ask the teachers, since most is obviously derived works.