# NTUEE 2020 FALL PRACTICE MIDTERM

## 1

Consider a FCFS M/M/1/4 queue with 2 classes of customers, and the service rate for all classes is $\mu$(cusotmers/min). The arrival rate for class-i is $\lambda_i$(customers/min), and arrival processes for both classes are Poisson. There is no priority among these two classes and all customers are served in a FCFS discipline. Please answer the following questions.

1. If we define the number of customers in the system as system state, please write its generator matrix.

:::spoiler Answer
define $\lambda = \lambda_1 + \lambda_2$.

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

2. What is its blocking probability? Please derive its formula.

:::spoiler Answer
define $\lambda = \lambda_1 + \lambda_2$.
define $r = \lambda / \mu$.
$p_0 = (1 + r + r^2 + r^3 + r^4)^{-1} = (1-r) / (1 - r^5)$
$p_n = r^n \cdot p_0$
so, blocking probability $p_b$ = $p_4 = p_0 \cdot r^4 = (1-r)r^4 / (1 - r^5)$
:::

3. What is the effective arrival rate and the server utilization?

:::spoiler Answer
effective arrival rate $\lambda_{eff}$ = $\lambda \cdot (1 - p_b) = \lambda \cdot (1 - p_4)$
:::

4. What is the average duration (holding time) when the system is in a blocking state?

:::spoiler Answer
Since the system is block when the system size is equal to 4, so the mean holding time is $1 / \mu$ (which is related to $Q_{44}$, where Q is the generator matrix we derived in 1.)
:::

5. What is the average time interval between 2 departing events?

:::spoiler Answer
$1 / \lambda_{eff}$, can view this outcome by the reversibility of all birth-death Markov processes(with some little tweak).
:::

6. What is the probability that the second arriving customer is class-2, when the first customer is class-1?

:::spoiler Answer
$\lambda_2 / (\lambda_1 + \lambda_2)$

7. Please write the transition matrix of its embedded Markov Chain.

:::spoiler Answer
$P =
\begin{pmatrix}
0 & 1 & 0 & 0 & 0 \\
\mu / (\lambda + \mu) & 0 & \lambda / (\lambda + \mu) & 0 & 0 \\
0 & \mu / (\lambda + \mu) & 0 & \lambda / (\lambda + \mu) & 0 \\
0 & 0 & \mu / (\lambda + \mu) & 0 & \lambda / (\lambda + \mu) \\
0 & 0 & 0 & 1 & 0
\end{pmatrix}$
:::

## 2

Consider an M/M/c/c queue with service rate $\mu$ (customers/min).

1. Please derive $q_n$, the probability that an admitted customer could see system size n upon its arrival.

:::spoiler Answer
we can simply use the formula of $q_n$ that we derive in [M/M/c/K](/KT6BmHc_R7m3H8n2Ghk0jQ), and substitute K for c, and get the result down below:
$q_n = p_n / (1 - p_c)$
:::

2. If we compare this M/M/c/c queue with an M/M/c'/c' queue, where $c' = 2c$ and the arrival rate is $2\lambda$, service rate is $\mu$ for each server, which queue will have lower blocking probability?

:::spoiler Answer
Denote $r = \frac{\lambda}{\mu}$.

for M/M/c/c, the blocking probability is $p_c$:

$$p_c = (r^c/c!) / (\sum_{n=0}^c r^n/n!)$$

for M/M/2c/2c, the blocking probability is $p_{c^{'}}$:

$$\begin{aligned} p_{c^{'}} &= p_{2c} = \frac{\frac{(2r)^{2c}}{(2c)!}}{\sum_{n=0}^{2c}\frac{(2r)^n}{n!}} \newline
&= \frac{\frac{r^c}{c!} \cdot \frac{(4r)^c}{(c+1)(c+2) ... (2c)}}{\sum_{n=0}^c \frac{r^n}{n!}} \cdot \frac{\sum_{n=0}^c \frac{r^n}{n!}}{\sum_{n=0}^{2c} \frac{(2r)^n}{n!}} \newline
&= p_c \cdot \frac{(4r)^c}{(c+1)(c+2) ... (2c)} \cdot \frac{\sum_{n=0}^c \frac{r^n}{n!}}{\sum_{n=0}^{2c} \frac{(2r)^n}{n!}}
\end{aligned}$$

where
$$\frac{\sum_{n=0}^c \frac{r^n}{n!}}{\sum_{n=0}^{2c} \frac{(2r)^n}{n!}} \lt 1$$

and
$$\frac{(4r)^c}{(c+1)(c+2) ... (2c)} \lt 1$$
, if $\frac{4r}{c} \lt 1$.

So if $\frac{4r}{c} \lt 1$, M/M/c'/c' has lower blocking probability.

:::

## 3

Consider an M/D/1 queue with $p_0 = 0.3$, service rate $\mu = 1$ customer/min(per server).

1. What is the expected length of its busy cycle? Derivation required.

:::spoiler Answer
From [M/D/1 wiki](https://en.wikipedia.org/wiki/M/D/1_queue), $L - L_q = 1 - p_0 = \rho = \lambda / \mu$ still holds, so $\lambda / \mu = 1 - 0.3 = 0.7$, and we know that $\mu = 1$, so $\lambda = 0.7$

define $E[N_{bp}]$ as the average customer served in a busy period, $E[T_{bp}]$ as the expected length of the busy people, $E[T_{idle}]$ as the expected length of the idle period.

Since the arrival process is Poisson, $E[T_{idle}] = 1 / \lambda$.
By PASTA property, $1 / E[N_{bp}] = p_0 = 0.3$, so $E[N_{bp}] = 10/3$, and we know $E[T_{bp}] = 1 / \mu \cdot E[N_{bp}] = 10/3$, so the expected length of the busy cycle is $E[T_{idle}] + E[T_{bc}] = (10 / 7) + (10 / 3) = 100 /21$

2. What is the average number of customers served in each busy cycle?

:::spoiler Answer
Since customers don't get served during idle period, so the answer is the same as $E[N_{bp}]$, which is $10/3$.
:::

## 4

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

1. Please draw its state transition diaram.

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

2. Please sovle $p_n$ from 1.

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

3. Please derive $q_n$, the probability that an arriving customer see population n in the system.

:::spoiler Answer
$L = \sum_{n=0}^4 np_n$

$q_n = (M-n)\cdot p_n / (M-L) = (4-n)\cdot p_n / (4-L)$
:::

4. What is the average utilization of the servers?

:::spoiler Answer
since $c=2$, so average utilization of the servers = $(1/2)p_1 + p_2 + p_3 + p_4$
:::

5. If you randomly arrive at this queue and find the server is busy, what is the expected waiting time before the service is started?

:::spoiler Answer
$(1\cdot q_2 + 2 \cdot q_3) / 2\mu (1 - q_0 - q_1)$

## 5

Consider the following single server queue with exponential servicevtime and Poisson arrival from an external source. Suppose the arrival rate from the external source is $\lambda$ and the service rate for the server is $\mu$. In addition, with probability $p$, $0\lt p \lt 1$, a customer completing it service will rejoin the queue.


1. What is the acutal arrival rate for this queue?

:::spoiler Answer
Solve the traffic equation for this network:

$\lambda = r + \lambda \cdot R =
\begin{pmatrix}
\lambda_1
\end{pmatrix} = \begin{pmatrix}
\lambda
\end{pmatrix} + \begin{pmatrix}
\lambda_1
\end{pmatrix} \cdot \begin{pmatrix}
p & 0
\end{pmatrix}$

$\therefore \lambda_1 = \lambda / (1-p)$

2. Why the arrival process for this queue is NOT Poisson?

:::spoiler Answer
Because customer completing its service will rejoin the queue(feedback)
:::

3. What is the valid range for $\lambda$ so that the queue can remain stable?

:::spoiler Answer
for the system to reach steady state: $\lambda_1 / \mu \lt 1 \Longrightarrow \lambda / \mu (1-p) \lt 1 \Longrightarrow \lambda \lt \mu (1-p)$
:::

4. Can we apply detailed balance equations to solve the steady state probability for this queue?

:::spoiler Answer
No, as in 2., we know that the arrival process is not Poisson, so the queue is not a birth-death process, hence we can not use detailed balance equations.
:::