# NTUEE 2021 FALL MIDTERM

## 1

Suppose you are given Poisson processes from source-1, source-2 and source-3, with arrival rate $\lambda_1$, $\lambda_2$ and $\lambda_3$ respectively. And there is no arrival at the starting time $t=0$.

1. Please show that the inter-arrival time afer the aggregation of these Poisson processes is exponential with mean equal to $\frac{1}{\lambda_1 + \lambda_2 + \lambda_3}$. (5%)

:::spoiler Answer
Let $T_1$ denote the inter-arrival time for the Poisson process from source 1, $T_2$ for that from source 2, $T_3$ for that from source 3, and $T$ for the aggregated Poisson process of the three.

Obviously, $T = min(T_1, T_2, T_3)$, and we are interested in the probability distribution of $T$ and $E(T)$.

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

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

2. If there is no arrival in interval $(0, a)$, please derive the probability that there is exactly one arrival from any source during $(a,b)$, where $a < b$. (3%)

:::spoiler Answer

By the memoryless property, the desired probability $P$ there is exactly one arrival from any source during $(a,b)$ is the same as that of time interval $(0, b-a)$, and we know that the probability of $k$ arrivals for a Poisson process with arrival rate $\lambda$ during time period of $[t, t+\tau]$ is
$$\frac{e^{-\lambda \tau}(\lambda \tau)^k}{k!}$$

So $P$ has the following form:

$$\begin{aligned}
P &= \frac{e^{-(\lambda_1 + \lambda_2 + \lambda_3)(b-a)}((\lambda_1 + \lambda_2 + \lambda_3)(b-a))}{1!} \newline &= (\lambda_1 + \lambda_2 + \lambda_3)(b-a) \cdot e^{-(\lambda_1 + \lambda_2 + \lambda_3)(b-a)}
\end{aligned}$$

3. If you randomly select a time epoch $t_0$ in the future to observe these 3 arrival processes, what is the expected length of the interval between the previous arival(from any source) $t_0$ and the first arrival(from any source) after $t_0$? And what is the probability that both of these 2 arrivals are both form source-1?(6%)

:::spoiler Answer
By memoryless property, the expected length is
$$2 \cdot \frac{1}{\lambda_1 + \lambda_2 + \lambda_3} = \frac{2}{\lambda_1 + \lambda_2 + \lambda_3}$$

Detail explanation follows the same process in [note of Forward Recurrence Time & Backward Recurrence Time in Poisson Process](https://hackmd.io/5a0BMBLqTdaOrjxfoeqdEg#Forward-Recurrence-Time-amp-Backward-Recurrence-Time-in-Poisson-Process), we can show that the expected length is $\frac{2}{\lambda_1 + \lambda_2 + \lambda_3}$.

The probability that both of these 2 arrivals are both form source-1 is

$$\frac{\lambda_1^2}{(\lambda_1+\lambda_2 + \lambda_3)^2}$$

Detail explanation follows:

We know that the probability of $k$ arrivals for a Poisson process with arrival rate $\lambda$ during time period of $[t, t+\tau]$ being $\frac{e^{-\lambda \tau}(\lambda \tau)^k}{k!}$.

We use $Pr_n(k)$ to denote that there are $k$ arrivals from source $n$ in time period of $[0, T]$, and by memoryless property, whether we observe at time epoch $t_0$, or from another arbitrary time interval $[0, T]$, the results are the same.

Thus, with memoryless property, the desired probability can be expressed as:

$$\begin{aligned}
P &= \frac{Pr_1(2)}{Pr_{1||2||3}(2)} \newline
&= \frac{\frac{e^{-\lambda_1 T}(\lambda_1 T)^2}{2!} \cdot \frac{e^{-\lambda_2 T}(\lambda_2 T)^0}{0!} \cdot \frac{e^{-\lambda_3 T}(\lambda_3 T)^0}{0!} }{\frac{e^{-(\lambda_1+\lambda_2 + \lambda_3) T}((\lambda_1+\lambda_2 + \lambda_3) T)^2}{2!}} \newline
&= \frac{\lambda_1^2}{(\lambda_1+\lambda_2 + \lambda_3)^2}
\end{aligned}$$

## 2

Consider an $M/M/1/4$ queue with arrival rate $\lambda$ and service rate $\mu = \lambda$.

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). (4%)

:::spoiler Answer
$$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. Please then solve its steady-state probability $p_n$ for $n=0,1,2,3,4$ using the generator matrix obtained in 1. (6%)

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

$$\begin{cases}
PQ = 0 \\
Qe = 1
\end{cases}
\Longrightarrow
\begin{cases}
p_1 = \frac{\lambda}{\mu} \cdot p_0 \\
p_2 = (\frac{\lambda}{\mu})^2 \cdot p_0 \\
p_3 = (\frac{\lambda}{\mu})^3 \cdot p_0 \\
p_4 = (\frac{\lambda}{\mu})^4 \cdot p_0 \\
p_0 = (1 + (\frac{\lambda}{\mu}) + (\frac{\lambda}{\mu})^2 + (\frac{\lambda}{\mu})^3 + (\frac{\lambda}{\mu})^4)^{-1}
\end{cases}$$

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

3. Derive the imbedded Markov chain of this $M/M/1/4$ queue and obtain its steady state probability $\pi_n$ for $n=0,1,2,3,4$. (6%)

:::spoiler Answer
The transition matrix：
$$P = \begin{pmatrix}
0 & 1 & 0 & 0 & 0 \\
\frac{\mu}{\lambda + \mu} & 0 & \frac{\lambda}{\lambda + \mu} & 0 & 0 \\
0 & \frac{\mu}{\lambda + \mu} & 0 & \frac{\lambda}{\lambda + \mu} & 0 \\
0 & 0 & \frac{\mu}{\lambda + \mu} & 0 & \frac{\lambda}{\lambda + \mu}\\
0 & 0 & 0 & 1 & 0
\end{pmatrix}$$

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

$$\begin{cases}
\pi P = \pi \\
\pi e = 1
\end{cases}
\Longrightarrow
\begin{cases}
\begin{multline}
\pi_0 = (1 + \frac{\mu + \lambda}{\mu} + \frac{\lambda}{\mu}\frac{\mu + \lambda}{\mu} + (\frac{\lambda}{\mu})^2 \frac{\mu + \lambda}{\mu} + (\frac{\lambda}{\mu})^3)^{-1}
\end{multline}\\
\pi_1 = \frac{\mu + \lambda}{\mu} \cdot \pi_0 \\
\pi_2 = \frac{\lambda}{\mu}\frac{\mu + \lambda}{\mu} \cdot \pi_0 \\
\pi_3 = (\frac{\lambda}{\mu})^2 \frac{\mu + \lambda}{\mu} \cdot \pi_0 \\
\pi_4 = (\frac{\lambda}{\mu})^3 \cdot \pi_0 \\
\end{cases}$$
:::

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

:::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}{\lambda + \mu} \newline
m_3 = \frac{1}{-q_{33}} = \frac{1}{\lambda + \mu} \newline
m_4 = \frac{1}{-q_{44}} = \frac{1}{\mu} \end{cases}$$
:::

5. Use the results of $\pi_n$ in 3. and the mean holding time in 4. to derive the formula for the steady-state probability $p_n$.(Hint: the results should be the same as in 2.)(6%)

:::spoiler Answer
We know that

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

First,

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

So,

$$\begin{aligned} p_0 &= \frac{m_0 \pi_0}{\sum_{i=0}^4 m_j \pi_j} \newline
&= \frac{\frac{1}{\lambda}}{\frac{\mu^4 + \lambda \mu^3 + \lambda^2 \mu^2 + \lambda^3 \mu^2 + \lambda^4}{\lambda \mu^4}} \newline
&= \frac{\mu^4}{\mu^4 + \lambda \mu^3 + \lambda^2 \mu^2 + \lambda^3 \mu^2 + \lambda^4} \newline
&= p_0
\end{aligned}$$

and,

$$\begin{aligned} p_1 &= \frac{m_1 \pi_1}{\sum_{i=0}^4 m_j \pi_j} \newline
&= \frac{\frac{1}{\lambda + \mu} \cdot \pi_1}{\frac{\mu^4 + \lambda \mu^3 + \lambda^2 \mu^2 + \lambda^3 \mu^2 + \lambda^4}{\lambda \mu^4} \cdot \pi_0} \newline
&= \frac{\frac{1}{\lambda + \mu} \cdot \frac{\mu + \lambda}{\mu} \cdot \pi_0}{\frac{\mu^4 + \lambda \mu^3 + \lambda^2 \mu^2 + \lambda^3 \mu^2 + \lambda^4}{\lambda \mu^4} \cdot \pi_0} \newline
&= \frac{\frac{1}{\mu}}{\frac{\mu^4 + \lambda \mu^3 + \lambda^2 \mu^2 + \lambda^3 \mu^2 + \lambda^4}{\lambda \mu^4}} \newline
&= \frac{\lambda}{\mu} \cdot p_0 \newline
&= p_1
\end{aligned}$$

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

## 3

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

1. What is the expected length of its busy cycle and its busy period?(Derivation required, and reuse some M/M/1 formula) (6%)

:::spoiler Answer
Since
$$L - L_q = 1 - p_0 = \rho = \frac{\lambda}{\mu}$$

so
$$\begin{aligned} &\frac{\lambda}{\mu} = 1 - 0.2 = 0.8 \newline &\Rightarrow \lambda = 0.8 \end{aligned}$$

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}] = \frac{1}{\lambda}$$

and by PASTA property

$$\begin{aligned} &\frac{1}{E[N_{bp}]} = p_0 = 0.2 \newline
&\Rightarrow E[N_{bp}] = 5 \end{aligned}$$

So
$$E[T_{bp}] = \frac{1}{\mu} \cdot E[N_{bp}] = 5$$

Hence, the expected length of the busy cycle is

$$E[T_{idle}] + E[T_{bc}] = \frac{5}{4} + 5 = \frac{25}{4}$$
:::

2. What is the average number of customers served in each busy cycle?(4%)

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

## 4

Consider a finite source queue with 2 servers, 3 sources and 1 spare. Assuming exponential service time and arrival rate $\lambda$ for each active source. Mean service time $\frac{1}{\mu}$.

1. Please draw its state transition diagram and write down all global balance equations.(7%)

:::spoiler Answer
Given $M = 3, Y = 1, c = 2$, from [Finite-Source Queues](/ZQIknMLdTLqgehDNQ0gixg), we know that:

$$\lambda_n = \begin{cases} 3\lambda ,\ (0 \le n \lt 1) \\ (3-n+1)\lambda , \ (1 \le n \lt 4) \\ 0, \ (n \ge 4)\end{cases}$$

$$\mu_n = \begin{cases} n\mu ,\ (0 \le n \lt 2) \\ 2\mu,\ (n \ge 2)\end{cases}$$

From above, the state diagram is:


Thus, its global balance equations is:

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

2. Please solve steady state probability $p_n$ form 1.(6%)

:::spoiler Answer
解聯立方程式可得 $p_0, p_1, p_2, p_3, p_4$。（同學考試時不可以直接這樣寫！）
:::

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

:::spoiler Answer
From Textbook page 90:

So
$$q_n =
\begin{cases}
\frac{3p_n}{3 - \sum_{i=1}^4 (i-1)p_n}, (n = 0) \\
\frac{(4-n)p_n}{3 - \sum_{i=1}^4 (i-1)p_n}, (0 \lt n \le 3)
\end{cases}$$
:::

4. If an arriving customer observes 3 customers in the system, what is the expected waiting time before service for this customer? (4%)

:::spoiler Answer

One has to wait at least 2 customers
至少要等待兩個人被服務完才會輪到自己。

$$E(W_q | 3\ customer) = 2 \cdot \frac{1}{2\mu} = \frac{1}{\mu}$$

:::

5. What is the average utilization fo the servers in the system? (You may express the answer in $p_n$) (4%)

:::spoiler Answer
$$\frac{1}{2}p_1 + p_2 + p_3 + p_4$$
:::

6. What is the average no. of customers departing from the queue per unit time? (You may express the answer in $p_n$) (4%)

:::spoiler Answer
Effective arrival rate = Departure rate

$$\sum \lambda_n p_n$$
:::

## 5

Consider a 2-class M/M/2/2 queue. For class-i customers, the arrival rate is $\lambda_i$ and its mean service time is $\frac{1}{\mu}$.

1. Please draw its state transition diagram and write down all global balance equations. We define the system state to be $(n1, n2)$ where $n_i$ is the no. of class-i customers. (8%)

:::spoiler Answer
$p(N_1, N_2) = (\lambda_1^{N_1} \lambda_2^{N_2})/\mu^{N_1 + N_2} \cdot p(0,0)$
:::

2. Please derive the blocking probability for both classes.(4%)

:::spoiler Answer
for both class :
blocking probability = $p(2,0) + p(1,1) + p(0,2)$
:::

3. Please derive $p(n)$, the probability that n customers are in the system (3%)

:::spoiler Answer
$p(n) = \sum_{x = 0}^{n} p(x, n-x) = (p(0,0)/\mu^{n}) \cdot \sum_{x = 0}^{n} (\lambda_1^{x} \lambda_2^{n-x})$
:::

## 6

Consider the following open Jackson queueing network, consisting of 3 single server nodes: $Q_1, Q_2, Q_3$, and there are 2 routing path for all trafic, as shown in the figure.

The external arrival rate is $\gamma, 0 \lt \gamma \lt 1$, and service rate are $\mu_1 = \mu_2 = 2$ for $Q_1, Q_2$, and $\mu_3 = 1$ for $Q_3$.

1. If the external traffic $\gamma$ is equally allocated to these two routing paths(i.e. both 50%), which routing path will provide lower network delay? (7%)

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

$\lambda = r + \lambda \cdot R =
\begin{pmatrix}
\lambda_1 & \lambda_2 & \lambda_3
\end{pmatrix} = \begin{pmatrix}
\gamma/2 & 0 & \gamma/2
\end{pmatrix} + \begin{pmatrix}
\lambda_1 & \lambda_2 & \lambda_3
\end{pmatrix} \cdot \begin{pmatrix}
0 & 1 & 0 \\
0 & 0 & 0 \\
0 & 0 & 0
\end{pmatrix}$

$\Longrightarrow
\lambda_1 = \lambda_2 = \lambda_3 = \gamma/2$

total delay for path pass through $Q_1, Q_2$ is the sum of delay of these two node = $1/(\mu_1 - \lambda_1) + 1/(\mu_2 - \lambda_2) = 4 / (4 - \gamma)$

total delay for path pass through $Q_3$ = $1/(\mu_3 - \lambda_3) = 2 / (2 - \gamma) \gt 4 / (4 - \gamma)$

So the path that pass through $Q_1, Q_2$ has lower network delay.
:::

2. If the routing probability can be arbitrary, how should we arrange the routing probability to minimize the overall network average delay? Please describe the condition required for optimal routing)(8%)

:::spoiler Answer
$\rho_1 = p \cdot \frac{r}{2} = \rho_2, \rho_3 = (1-p) \cdot r$
$L = L_1 + L_2 + L_3 = \frac{\rho_1}{1 - \rho_1} + \frac{\rho_2}{1 - \rho_2} + \frac{\rho_3}{1 - \rho_3}$
$W = \frac{L}{r}$
求解：$\frac{dW}{dp} = 0$ 及為 Optimal routing 的條件，答案應為 $p = \frac{2}{3}$

:::