Performance evaluation of networks: class #4

# Queues

## Queue M|M|1

It is a Birth and death process. Packets arriving forming a poisson process with parameter λ.

(1)
\begin{align} \{X(t) = #\textrm{customers at time}\ t\} \textrm{C-MC} \end{align}
(2)
\begin{align} \lambda_i = \lambda \qquad \textrm{(throughput)} \end{align}
(3)
\begin{align} \mu_i = \mu \qquad \textrm{(service time)} \end{align}
(4)
\begin{align} \pi_i = P(X(\infty) = i) = (1 - \rho) \rho^i, i \geq 0 \end{align}
(5)
\begin{align} \rho = \lambda \frac 1 \mu < 1 \qquad \textrm{(traffic intensity)} \end{align}
(6)
\begin{eqnarray} P(X \geq k) & = & \sum^\infty_{i=k} P(X=i) \qquad [\pi_i = P(X = i)] \\ & = & \sum^\infty_{i=k} (1 - \rho) \rho^i \\ & = & (1 - \rho) \rho^k \sum^\infty_{i=k} p^{i - k} \qquad [j = i - k] \\ & = & (1 - \rho) \rho^k \sum^\infty_{j=0} p^j \\ & = & (1 - \rho) \rho^k \frac 1 {1 - \rho} = \rho^k \end{eqnarray}
(7)
\begin{eqnarray} E[X] & = & \sum^\infty_{i=0} i \pi_i \\ & = & \sum^\infty_{i=0} i (i - \rho) \rho^i \\ & = & (1 - \rho) \rho \sum^\infty_{i=0} i \rho^{i-1} \\ & = & (1 - \rho) \rho \frac 1 {(1 - \rho) ^ 2} \\ & = & \frac \rho {1 - \rho} \end{eqnarray}
(8)
\begin{align} var(X) = E(X^2) - [E(X)]^2 = \sum_{i=0}^\infty i^2 \pi_i - \left( \frac \rho {1 - \rho} \right) ^ 2 \end{align}

Comments on practical systems where they reach 50% usage and they need to be changed.

PASTA: Poisson Arrivals See Time Averages

If I want to be alone in the system,

(9)
\begin{eqnarray} E[X] & \leq & 1 \\ \frac \rho {1 - \rho} & \leq & 1 \\ \rho & \leq & 1 - \rho \\ 2 \rho & \leq & 1 \\ \rho & \leq & \frac 1 2 \end{eqnarray}

So, the average the traffic intensity should be lower than 50%.

## Non infinite queue: M|M|1|k

Packets arriving as Poisson process, k - 1 customers waiting and one being served.

(10)
\begin{align} P(S \leq x) = 1 - e^{-\mu\lambda}, E[X] = \frac 1 \mu \end{align}

When the queue is full, new packets are lost. We want to calculate the same values as before. Let see if this is a C-MC:

(11)
\begin{align} {X(t), t \geq 0} \end{align}

For state $i = 0$, we use rule #1 $\rightarrow \exp(\lambda), 0 \rightarrow 1$.
For state $i = k$ (system full), with rule #1 $\rightarrow \exp(\mu), k \rightarrow k - 1$
For $1 \leq i \leq k - 1$, two possible events:

1. $Y_{i, 1}, \exp(\lambda), i \rightarrow i + 1$
2. $Y_{i, 1}, \exp(\mu), i \rightarrow i - 1$

So it is a C-MC, moreover, it is a Birth & death process with birth rate $\lambda_i$, and death rate $\mu_i, i \geq 1$.

(12)
\begin{align} \lambda_i = \left\{ \begin{array}{ll} 0 & \textrm{if}\ i = k \\ \lambda & \textrm{if}\ i = {0, 1 \dots k - 1} \end{array} \right. \end{align}
(13)
\begin{align} \mu_i = \mu, i = {1 \dots k} \end{align}
(14)
\begin{align} \pi_i = \frac { \lambda_0 \lambda_1 \dots \lambda_{i-1} } { \mu_1 \mu_2 \dots \mu_i } \frac 1 C \end{align}
(15)
\begin{align} \rho_i = \frac { \lambda_0 \lambda_1 \dots \lambda_{i-1} } { \mu_1 \mu_2 \dots \mu_i } \end{align}
(16)
\begin{align} C = \sum^k_{i=0} \frac { \lambda_0 \lambda_1 \dots \lambda_{i-1} } { \mu_1 \mu_2 \dots \mu_i } = \sum^k_{i=0} \left( \frac \lambda \mu \right)^i = \frac { 1 - \rho^{k+1} } {1 - \rho} \end{align}
(17)
\begin{align} \pi_i = \left\{ \begin{array}{ll} 0 & i > k \\ \frac { \rho^i (1 - \rho) } {1 - \rho^{k + 1}} & i = 0, 1 \dots k \end{array} \right. \end{align}

The rate of packets entering the queue is not lambda, as some are lost:

(18)
\begin{eqnarray} \lambda (1 - \pi_k) & = & \lambda \left( 1 - \frac {\rho^k (1 - \rho)} {1 - \rho ^{k+1}} \right) \\ & = & \lambda \frac { 1 - \rho^2 } { 1 - \rho^{k + 1} } \qquad \textrm{Throughput} \end{eqnarray}

We can obtain the same result if we calculate $\mu (1 - \pi_0)$, which corresponds to taking into account the empty states.

(19)
\begin{align} E[X] = \sum_{i=0}^k i \pi_i = \dots = \frac \rho {1 - \rho^{k+1}} \left[ \frac { -(k+1)\rho^k (1-\rho) + 1 - \rho^{k+1} } { 1 - \rho} \right] \end{align}

Section 6.3

Section 6.4

# Leaky bucket

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