# NTUEE 2020 FALL MIDTERM

## 1

Consider a FCFS $M/M/1/3$ queue with the service rate $\mu$ for all customers. For this queue, there are 2 Poisson arrival processes from source-1, source-2, with arrival rate $\lambda_1$ and $\lambda_2$ respectively. And there is no arrival at the starting time $t = 0$. There is no priority and all customers are served in a FCFS discipline. Please answer the following questions.

1. Please show that the arrival time for the first customer after the aggregation of these 2 Poisson processes is exponential with mean equal to $\frac{1}{\lambda_1 + \lambda_2}$ (4%)
:::spoiler Answer
Let $T_1$ denote the inter-arrival time for the Poisson process from source 1, $T_2$ for that from source 2, and $T$ for the aggregated Poisson process of the three.

Obviously, $T = min(T_1, T_2)$, and we are interested in the probability distribution of $T$ and $E(T)$, and we know that the arrival from source-1 and the arrival from source-2 are independent of each other.

$$\begin{aligned} P(T > t)
&= P(min(T_1, T_2) \gt t) \\
&= P(T_1 \gt t \cap T_2 \gt t) \\
&= P(T_1 \gt t) \cdot P(T_2 \gt t) \\
&= e^{-\lambda_1 t} \cdot e^{-\lambda_2 t}\\
&= e^{-(\lambda_1+\lambda_2) t}
\end{aligned}$$

So $T$ is a exponential random variable with parameter $\lambda_1 + \lambda_2$, thus the mean of $T = E[T]$ is $\frac{1}{\lambda_1 + \lambda_2}$.

Denote $\lambda = \lambda_1 + \lambda_2$ throughout problem 1.
:::

2. Please write down all its global balance equations.(4%)

:::spoiler Answer

$$ \begin{cases} p_0 \cdot \lambda = p_1 \cdot \mu \newline
p_1 \cdot (\lambda + \mu) = p_2 \cdot \mu + p_0 \cdot \lambda \newline
p_2 \cdot (\lambda + \mu) = p_3 \cdot \mu + p_1 \cdot \lambda \newline
p_3 \cdot \mu = p_2 \cdot \lambda \end{cases}$$
:::

3. What is the probability of observing an idle server if you are an admitted customer?

:::spoiler Answer
The probability of observing an idle server is $q_0$, follow the formula of $q_n$ in [M/M/c/K](/KT6BmHc_R7m3H8n2Ghk0jQ), it is equal to
$$\frac{p_0}{1 - p_3}$$
:::

4. What is its blocking probability? What is the server utilization? Please derive their formula.(4%)

:::spoiler Answer
blocking probability is

$$p_3 = (\frac{\lambda}{\mu})^3 \cdot p_0$$

server utilization is

$$\frac{\lambda(1 - p_3)}{\mu} = 1 - p_0$$
:::

5. Please derive $W$ and $W_q$ of this $M/M/1/3$ queue via the Little's formula.(4%)

:::spoiler Answer
$$\begin{aligned} L_q &= \sum_{n=2}^3 (n-1)p_n \newline
&= p_2 + 2p_3 \newline
&= \frac{r^2(1-r) + 2r^3(1-r)}{1 - r^4} \end{aligned}$$

where $r = \frac{\lambda}{\mu}, p_0 =\frac{1-r}{1 -r^4}$

$$\begin{aligned} &\Rightarrow L = L_q + \frac{\lambda_{eff}} {\mu} \newline
&\Rightarrow W = \frac{L}{\lambda_{eff}} \newline
&\Rightarrow W_q = \frac{L_q}{\lambda_{eff}}
\end{aligned}$$

where $\lambda_{eff} = \lambda \cdot (1 - p_3)$
:::

## 2

Consider an $M/M/2/2$ queue with arrival rate $\lambda$ and service rate $\mu$ for each server.

1. Please write down the generator matrix $Q$ for its continuous time Markov Chain, which represents its system size(the number of customers in the system.)(5%)

:::spoiler Answer
$$Q =
\begin{pmatrix}
-\lambda & \lambda & 0 \\
\mu & -(\mu + \lambda ) & \lambda \\
0 & 2\mu & -2\mu
\end{pmatrix}$$
:::

2. Please then derive its steady-state probability $p_n$ for $n = 0,1,2$ based on generator matrix obtained in (i).(5%)

:::spoiler Answer
let $P = (p_0, p_1, p_2), e = (1,1,1)$
solve:

$$\begin{aligned}
&\begin{cases}
PQ = 0 \\
Qe = 1
\end{cases} \newline
\Rightarrow
&\begin{cases}
p_0(-\lambda) + p_1 \mu = 0 \\
p_1\lambda - p_2(2\mu) = 0 \\
p_0 + p_1 + p_2 = 1
\end{cases} \newline
\Rightarrow
&\begin{cases}
p_1 = \frac{\lambda}{\mu} \cdot p_0 \\
p_2 = \frac{\lambda}{2\mu} \cdot p_1 = \frac{\lambda^2}{2\mu^2} \cdot p_0 \\
p_0 + p_1 + p_2 = 1
\end{cases} \newline
\Rightarrow
&\begin{cases}
p_0 = (1 + \frac{\lambda}{\mu} + \frac{\lambda^2}{2\mu^2})^{-1} \\
p_1 = \frac{\lambda}{\mu} \cdot p_0 \\
p_2 = \frac{\lambda^2}{2\mu^2} \cdot p_0 \\
\end{cases} \end{aligned}$$

$$p_0 = \frac{2\mu^2}{2\mu^2 + 2\lambda \mu + \lambda^2}$$
:::

3. Please determine the mean holding time for state 0, 1, and 2.(5%)

:::spoiler Answer
let $m_i$ denote the mean holding time(mean state sojourn time) for state $i$.

$$\begin{cases} m_0 = \frac{1}{-q_{00}} = \frac{1}{\lambda} \newline
m_1 = \frac{1}{-q_{11}} = \frac{1}{\lambda + \mu} \newline
m_2 = \frac{1}{-q_{22}} = \frac{1}{2\mu} \end{cases}$$
:::

4. Solve the imbedded Markov chain of this M/M/2/2 queue and obtain its steady state probability $\pi_n$ for $n=0,1,2$ (5%)
:::spoiler Answer
The transition matrix is

$$P = \begin{pmatrix}
0 & 1 & 0 \\
\frac{\mu}{\lambda + \mu} & 0 & \frac{\lambda}{\lambda + \mu} \\
0 & 1 & 0
\end{pmatrix}$$

let $\pi = (\pi_0, \pi_1, \pi_2), e = (1,1,1)$
solve:

$$\begin{aligned}
&\begin{cases}
\pi P = \pi \\
\pi e = 1
\end{cases} \newline
\Rightarrow
&\begin{cases}
\pi_1 \frac{\mu}{\mu + \lambda} = \pi_0 \\
\pi_1 \frac{\lambda}{\mu + \lambda} = \pi_2 \\
\pi_0 + \pi_1 + \pi_2 = 1
\end{cases} \newline
\Rightarrow
&\begin{cases}
\pi_1 = \frac{\mu + \lambda}{\mu} \cdot \pi_0 \\
\pi_2 = \frac{\lambda}{\mu + \lambda} \cdot \pi_1 = \frac{\lambda}{\mu} \cdot \pi_0 \\
\pi_0 + \pi_1 + \pi_2 = 1
\end{cases} \newline
\Rightarrow
&\begin{cases}
\pi_0 = (1 + \frac{\mu + \lambda}{\mu} + \frac{\lambda}{\mu} )^{-1} \\
\pi_1 = \frac{\mu + \lambda}{\mu} \cdot \pi_0 \\
\pi_2 = \frac{\lambda}{\mu} \cdot \pi_0 \\
\end{cases}
\end{aligned}$$
:::

5. Use the results of $\pi_n$ in 4. and the mean holding time in 3. to derive the formula for the steady-state probability $p_0$ and show the obtained results to be the same as that obtained in 2.(5%)

:::spoiler Answer
We know that

$$p_i = \frac{m_i \pi_i}{\sum_{i=0}^2 m_j \pi_j}$$

First,

$$\begin{aligned}
\sum_{i=0}^2 m_j \pi_j &= (\frac{1}{\lambda} + \frac{1}{\mu} + \frac{\lambda}{2\mu^2}) \cdot \pi_0 \newline
&= \frac{2\mu^2 + 2\lambda \mu + \lambda^2}{2\lambda \mu^2} \cdot \pi_0
\end{aligned}$$

So,

$$\begin{aligned} p_0 &= \frac{m_0 \pi_0}{\sum_{i=0}^2 m_j \pi_j} \newline
&= \frac{\frac{1}{\lambda}}{\frac{2\mu^2 + 2\lambda \mu + \lambda^2}{2\lambda \mu^2}} \newline
&= \frac{2\mu^2}{2\mu^2 + 2\lambda \mu + \lambda^2} \newline
&= p_0
\end{aligned}$$
which is the same as in 2.

and follow the same reasoning, we can verify $p_1, p_2$ are the same as in 2. （同學請自行化簡，考試時不可省略此過程）
:::

## 3

Please show that for an $M/M/c/k$ queue and and $M/M/c/k+1$ queue with the same $\lambda$ and $\mu$(with $\lambda \gt 0, \mu \gt 0, \frac{\lambda}{c\mu} < 1$), the $M/M/c/k+1$ queue always have higher server utilization.(6%)

:::spoiler Answer
Consider $p_k, p_{k+1}$, which is the blocking probability for $M/M/c/k, M/M/c/k+1$ queue, respectively.

We know that

$$\rho_{M/M/c/k} = \frac{\lambda(1 - p_k)}{c\mu} , \rho_{M/M/c/k+1} = \frac{\lambda(1 - p_{k+1})}{c\mu}$$

which is the server utilization for $M/M/c/k$ and $M/M/c/k+1$ queue, respectively.

We can prove $\rho_{M/M/c/k+1} \gt \rho_{M/M/c/k}$ by showing $p_k \gt p_{k+1}$, which is the blocking probability for both queue, respectively.

First, denote $r = \frac{\lambda}{\mu}, \rho = \frac{r}{c}$.

Consider M/M/c/k queue:

$$\begin{aligned}
p_0
&= (\sum_{n=0}^{c-1} \frac{r^n}{n!} + \sum_{n=c}^{k} \frac{r^n}{c! c^{n-c}})^{-1} \\
&=(\sum_{n=0}^{c-1} \frac{r^n}{n!} + \frac{r^c}{c!}(\frac{1 - \rho^{k-c+1}}{1 - \rho}) )^{-1}
\end{aligned}$$

here we denote

$$\begin{cases} \sum_{n=0}^{c-1} \frac{r^n}{n!} = M \newline \frac{r^n}{c!}(\frac{1 - \rho^{k-c+1}}{1 - \rho}) = N \end{cases}$$

So,
$$p_k = p_0 \cdot \frac{r^k}{c! c^{k-c}} = \frac{1}{M + N} \cdot \frac{r^k}{c! c^{k-c}}$$

Consider M/M/c/k+1 queue:

$$\begin{aligned}
p_0
&= (\sum_{n=0}^{c-1} \frac{r^n}{n!} + \sum_{n=c}^{k+1} \frac{r^n}{c! c^{n-c}})^{-1} \\
&=(\sum_{n=0}^{c-1} \frac{r^n}{n!} + \frac{r^c}{c!}(\frac{1 - \rho^{k-c+2}}{1 - \rho}) )^{-1}
\end{aligned}$$

then,
$$\begin{aligned} p_{k+1} &= p_0 \cdot \frac{r^{k+1}}{c! c^{k-c+1}} \newline
&= \frac{1}{(M + N) \cdot \frac{1 - \rho^{k-c+2}}{1 - \rho^{k-c+1}}} \cdot \frac{r^k}{c! c^{k-c}} \cdot \rho \newline
&= p_k \cdot \frac{\rho(1 - \rho^{k-c+1})}{1 - \rho^{k-c+2}} \newline
&= p_k \cdot \frac{\rho - \rho^{k-c+2}}{1 - \rho^{k-c+2}}
\end{aligned}$$

when $\rho \lt 1$,

$$\frac{\rho - \rho^{k-c+2}}{1 - \rho^{k-c+2}} \lt 1 \Rightarrow p_{k} \gt p_{k+1}$$

which is to say that the server utilization is higher for M/M/c/k+1.
:::

## 4

Compare and M/M/1 queue and an M/M/3 queue with the same $\rho(\rho \lt 1$) and the same arrival rate $\lambda$.

1. Which queue has higher server utilization?(4%)

:::spoiler Answer

We know that server utilization for M/M/c queue is

$$\frac{\lambda}{c\mu} = \rho$$

so server utilization is the same for both queue.
:::

2. Which queue has larger $p_0$?(5%)

:::spoiler Answer
Since two queue has the same $\rho$ and $\lambda$, which means

$$\frac{\lambda}{\mu_{M/M/1}} = \frac{\lambda}{3 \mu_{M/M/3}} \Rightarrow \mu_{M/M/1} = 3\mu_{M/M/3}$$

So,
$$r = \frac{\lambda}{\mu_{M/M/1}}\ ,\ r' = \frac{\lambda }{\mu_{M/M/3}} = 3r$$

Consider M/M/1 queue:

$$p_0 = (1 + r + r^2 + r^3 + \cdots)^{-1}$$

Consider M/M/3 queue:

$$\begin{aligned}
p_0
&= (1 + r' + \frac{1}{2!}(r')^2 + \frac{1}{3!}(r')^3 + \frac{1}{3!3}(r')^4 + \cdots)^{-1} \\
&= (1 + (3r) + \frac{9}{2!}r^2 + \frac{27}{3!}r^3 + \frac{81}{3!3}r^4 + \cdots)^{-1}
\end{aligned}$$

compare the coefficient of the two equation, since each coefficient of M/M/3 is larger or equal to that of M/M/1, so the inverse of it is smaller than that of M/M/1, hence we can say that $p_0$ for M/M/1 is larger.
:::

3. Which queue has larger mean busy cycle?(5%)

:::spoiler Answer
From [Busy-Period Analysis: Take M/M/1 as an Example](/1CiLXdwCS_uqCVx-WQqXmw), we know that the mean of the length of busy cycle is

$$E[T_{bc}] = E[T_{idle}] + E[T_{bp}]$$

since arrival rate $\lambda$ is the same for both M/M/1 and M/M/3, so their $E[T_{idle}] = \frac{1}{\lambda}$ are the same.

We also know that, given mean service rate as $\mu$

$$E(T_{bp}) = \frac{1}{\mu} \cdot E(N_{bp})$$

and given server utilization $\rho$

$$p_0 = 1 - \rho = \frac{1}{E(N_{bp})}$$

From 2., we know that $p_0$ for M/M/1 is larger, so $E(N_{bp})$ for M/M/1 is smaller. And from 2. we also know that the mean service rate for M/M/1 is larger than that of M/M/3, so the mean service time for M/M/1 is smaller, therefore, $E(T_{bp})$ is smaller for M/M/1.

And since $E[T_{idle}]$ are the same for both queue, $E[T_{bc}]$ is smaller for M/M/1, in other words, M/M/3 has larger busy cycle.
:::

## 5

Consider a finite source queue with 2 servers and 3 sources.(i.e. M=3) Assuming exponential service time and arrival rate $\lambda$ per source. Mean service time is $1/\mu$.

1. Please draw its state transition diagram.(5%)

:::spoiler Answer
上圖中取 M = 3 以及 c = 2 及為答案。
:::

2. Please solve $p_n$ form (i)(8%)

:::spoiler Answer
define $r = \lambda / \mu$。
$p_0 = (1 + 3r + 3r^2 + (3/2)r^3)^{-1}$
$p_1 = p_0\cdot 3r$
$p_2 = p_0\cdot 3r^2$
$p_3 = p_0\cdot (3/2)r^3$
:::

3. Please derive $q_n$, the probability that an arriving customer observes population n in the system.(7%)

:::spoiler Answer
$L = \sum_{n=0}^3 np_n = 3p_0(r + 2r^2 + (3/2)r^3)$

$q_n = (M-n)\cdot p_n / (M-L) = (3-n)\cdot p_n / (3-(3p_0(r + 2r^2 + (3/2)r^3)))$
:::

## 6

Consider the following open Jackson network, consisting of node 1 and node 2. Suppose the arrival rate from the external source is $\lambda$ and the service rate is $\mu$ for both nodes. In addition, with probability $p, 0 \lt p \lt 1$, a customer completing its service will rejoin node 1.

1. What is the actual arrival rate for these two nodes?(6%)

:::spoiler Answer
let $\lambda_1$ denote the actual arrival rate for node 1, and $\lambda_2$ for node 2.

Solve the traffic equation for this network:

$\lambda = r + \lambda \cdot R =
\begin{pmatrix}
\lambda_1 & \lambda_2
\end{pmatrix} = \begin{pmatrix}
\lambda & 0
\end{pmatrix} + \begin{pmatrix}
\lambda_1 & \lambda_2
\end{pmatrix} \cdot \begin{pmatrix}
p & (1-p) \\
p & 0
\end{pmatrix}$

\begin{cases}
\lambda_1 = \lambda / (1-p)^2 \\
\lambda_2 = \lambda / (1-p)
\end{cases}
:::

2. What is the valid range for $\lambda$ so that all nodes in the network can remain stable?(7%)

:::spoiler Answer
All nodes in the network can remain stable as long as each node can remain stable, and since each node in open Jackson network behaves like a M/M/1 queue, so this is to say that all M/M/1 queues must remain stable(reach steady state), and thus we have the following condition for node 1 and node 2 resepctively:

$$\lambda_1 / \mu \lt 1 \Longrightarrow \lambda / \mu (1-p)^2 \lt 1 \Longrightarrow \lambda \lt \mu (1-p)^2$$

$$\lambda_2 / \mu \lt 1 \Longrightarrow \lambda / \mu (1-p) \lt 1 \Longrightarrow \lambda \lt \mu (1-p)$$

Since $1-p \lt 1$, So the network can remain stable if $\lambda \lt \mu (1-p)^2$
:::

3. What is the mean population in this network if all nodes are stable?

:::spoiler Answer
mean population in this network is $L = L_1 + L_2 = \rho_1/(1-\rho_1) + \rho_2/(1-\rho_2)$, where $\rho_1 = \lambda_1 / \mu$ and $\rho_2 = \lambda_2 / \mu$.
:::