DateNetwork Review, chapter 3.

Chapter3: Delay model:
//-------------------------------------------------------------------------
3.1 introduction
multiplexing: TDM, FDM, statistical multiplexing.
//-------------------------------------------------------------------------
3.2 queuing models - little's theorem
Very general, very important
$$N = \lambda T$$
N: average/typical number of customers in the system
T: average delay in the system
$\lambda$: arrival rate.

example1:
P{a server is busy} = $\lambda$ * {average service time}

//-------------------------------------------------------------------------
3.3 MM1
TOOL: Markov chain.
main results:
$$\rho = \frac{\lambda}{\mu} \\ p_0 =  1 - \rho \\ p_n = \rho^n (1-\rho) \\ N = \frac{\rho}{1-\rho} \\ T = \frac{N}{T} \\ W = T - \frac{1}{\mu} \\ N_Q = N - \rho = \lambda W$$


An every interesting question to ask is: 
"is the queue typical seen by an arrival?".
it is possible to be non-typical, for example, deterministic arrival 1/min, service time 0.5 min,
average system N = 0.5
however, the customer in system seen by an arrival is always 0.
conclusion:
$a_n$ : occupancy distribution upon arrival
$p_n$ : steady state  occupancy distribution
$d_n$ :  occupancy distribution upon departure.
if arrival process is poisson: $a_n = p_n$.
if markov process is a birth death process: $d_n = a_n$.

//-------------------------------------------------------------------------
3.4 MMm, MMinfty, MMmm
MMm
Markov chain solve for steady state distribution, $p_n$.
define queueing probability:
$P_{queueing} = \sum_{n = m}^{\infty} p_n$
known as Erlang C formula, honoring Denmark's A.K. Erlang.

$$\rho = \frac{\lambda}{m \mu} \\ N_Q = P_Q \frac{\rho}{1-\rho} \\ W =  N_Q / \lambda \\ T = W + \frac{1}{\mu} \\ N  = \lambda T \\ $$
note the connection with MM1 here.
explanation: for those who come and join the queue, the system works like $m\mu$ superserver. Write down the MarkovChain for the number of customers waiting in the queue, then it is same as MM1 system.

$M/M/\infty$
This case is very interesting, because:
$$p_n  = (\frac{\lambda}{\mu})^n \frac{e^{-\frac{\lambda}{\mu}}}{n!} \Rightarrow Poisson(\frac{\lambda}{\mu})$$
What is system delay? No queuing time !!!! W = 0
$$T = \frac{1}{\mu} \\ N =  \frac{\lambda}{\mu} \\ N_Q = 0 \\ W = 0$$
Intuitively.


M/M/m/m Loss system
again, our tool is markov chain, solve for $p_n$.

actually, there is an easier way. This is a truncated $MM\infty$ case, for those who are accepted, the system indeed has $\infty$ servers. Everything stays the same except for a normalization constant.
and note the common term $e^{-\frac{\lambda}{\mu}}$ cancels.

$$p_0 = [\sum_{n = 0}^{m} (\frac{\lambda}{\mu})^n \frac{1}{n!}]^{-1} p_n = p_0 (\frac{\lambda}{\mu})^n \frac{1}{n!}$$
The most important quantity is the blocking probability (Erlang B formua): $p_m$.
with such probability, any new arrival seen m customer already in system, and it will be rejected.


//-------------------------------------------------------------------------
3.5 MG1
Most important formula: Pollaczek - Khinchin formula. PK formula.
$$\bar{X} = \textrm{average service time} \\ \bar{X^2} = \textrm{second moment of average service time} \\ W = \frac{\lambda \bar{X^2}}{2(1-\rho)}$$
other quantities can be found using Little's law.

example1:
MM1
$$\bar{X} =  \frac{1}{\mu} \Rightarrow E[X^2] = \frac{2}{\mu ^2} W = \frac{\rho}{\mu-\lambda}$$
MD1
$$E[X^2] = E[X]^2 = \frac{1}{\mu ^2} \Rightarrow W = \frac{\rho}{2(\mu - \lambda)}$$
we note MD1 has only half the queuing delay than the MM1.
FOLK's law: the more random, the more delay.

Proof of PK formula by the author of the book. 
how long will a new arrival has to wait in queue?
$$W = R + \frac{1}{\mu} N_Q$$
R: mean residual time.
$N_Q$: number of customer in queue seen by arrival.
using little law: $N_Q = \lambda * W$
$$W = \frac{R}{1-\rho}$$
What is R?
in the interval [0,t], $M(t)$ is the number of service completed.
$$\begin{split} \frac{1}{t} \int_{0}^{t} r(\tau) d\tau &= \frac{1}{t} \sum_{i = 1}^{M(t)} \frac{x_i ^2}{2}\\ &= \frac{M(t)}{t} \sum_{i = 1}^{M(t)} \frac{x_i ^2}{2 M(t)} \\ R &= \lambda \frac{E[X^2]}{2} \end{split}$$
by letting $t\rightarrow \infty$

MG1 with vacation.
At the end of busy period(with probability $1-\rho$), a server that goes to vacation from time to time, with
$E[V]$: average vacation time.
$E[V^2]$: second moment of average vacation time.
We note that service time and vacation time are almost indistinguishable.
Treat R as "residual service time or vacation time."
The derivation is similar to the proof of PK formula:
$$\begin{split} R &= \lim_{t\rightarrow \infty} {\frac{M(t)}{t} \sum_{i = 1}^{M(t)}\frac{X_i ^2}{2M(t)}+ \frac{L(t)}{t} \sum_{i = 1}^{L(t)}\frac{V_i ^2}{2L(t)}} \\ & = \frac{\lambda E[X^2]}{2} + \frac{(1-\rho)E[V^2]}{2E[V]} \\ \frac{L(t)}{t} & \rightarrow \frac{1-\rho}{E[V]} \end{split}$$
where $L(t)$ is the number of vacation completed during [0, t].
Basically, the vacations increase $p_0$, however, the system can still be viewed as two subsystems:
1. when the system is working, this gives the first part of the R.
2. w.p. $1-\rho$, the system goes to vacation, leading to the second part of the R.
finally:

$$W = \frac{\lambda E[X^2]}{2(1-\rho)} + \frac{E[V^2]}{2E[V]}$$

MG1 with reservation.
let consider only a single user, for the i th packet:
1. R: residual till the end of the current transmission, which could either be really transmission or reservation making.
2. N*E[X]: transmission of the before-coming packets.
3. V: (denoted same as vacation) it must wait a full reservation slot, in which its reservation is made.
The system is designed s.t. before its transmission, there bound to be a reservation slot.

again
$$\begin{split} V &\leftarrow E[V] \\ R &\leftarrow \frac{\lambda E[X^2]}{2}  + \frac{E[V^2]}{2E[V]} (1-\rho) \\ W &= \frac{R+V}{1-\rho} = \frac{\lambda E[X^2]}{2(1-\rho)} + \frac{E[V^2]}{2E[V]} + \frac{E[V]}{1-\rho} \end{split}$$
This is fully gated system, meaning ony those packets that arrived prior to the user's preceding reservation interval are transmitted.
therefore every packet has to experience a full reservation slot.

Exhaustive system: all available packets of a user are transmitted during the corresponding data interval.
partially gated system: transmit those packets arrived up to the beginning of the data interval.

Note the exhaustive system is equivalent to the vacation system, only those who arrive see vacation/reservation have to wait.


Priority queuing MG1
non-preemptive: high class CANNOT interrupt low class at service.
preemptive: high class interrupt low class at service, no resumption for the low class. 臭流氓!
Assuming class 1 has the highest priority, class n has the lowest.

non-preemptive is easier:
$\mu_i$  $\lambda_i$ are different.

during the waiting of class2, those later-comer class 1 will jump the queue!
$$\begin{split} W_1 &= R + \frac{N_Q ^1}{\mu_1} \\ N_Q^1 &= \lambda_1 W_1 \\ W_1 &= \frac{R}{1-\rho_1} \\  \textrm{"class 1 jump the queue while class 2 waiting"} \\ W_2 &= R + \frac{N_Q ^1}{\mu_1} + \frac{N_Q ^2}{\mu_2}  + \frac{\lambda_1 W_2}{\mu_1} \\ W_2 &= \frac{R}{(1-\rho_1)(1- \rho_1 - \rho_2)} \\  \textrm{"finally"} \\ W_k &= \frac{R}{(1-\rho_1 - \ldots - \rho_{k-1})(1-\rho_1 - \ldots - \rho_{k})} \\  \text{"R like a weighted sum"} \\ R &= \frac{1}{2} \sum_{i=1}^{n} \lambda_i E[X_i ^2 ] \end{split}$$
The calculation involves all class 1 - n, because it is a non-preemptive system.



preemptive system:
The arrival sees the system as a MG1, ignoring the class (k+1) to n.

$$\begin{split} W_k &= \frac{R_k }{1-\rho_1 - \ldots - \rho_k } \\ R_k &= \frac{\sum_{i = 1}^{k} \lambda_i E[X_i ^2]}{2} \\ \end{split}$$

an explanation for this.
If we only consider the first k class, the capacity assigned to class k is no longer $\rho _k$, but a normalized one:
$$\frac{\rho_k}{\rho_1 + \ldots + \rho_k}$$
therefore the service time becomes:
$$\mu_k \Rightarrow \mu_k \frac{\rho_k}{\rho_1 + \ldots + \rho_k}$$
which is a improvement, because the denominator is less than 1.
finally.
$$W_k = R_k + N_Q ^k \frac{\rho_1 + \ldots + \rho_k}{\rho_k \mu_k} \\ = R_k + \lambda_k W_k  \frac{\rho_1 + \ldots + \rho_k}{\rho_k \mu_k} \\ = R_k + (\rho_1 + \ldots + \rho_k)W_k$$
This leads to the same result.


//-------------------------------------------------------------------------
3.6 networks of transmission lines.
//-------------------------------------------------------------------------
3.7 time reversibility - Burke's theorem
backward transition probability:
$$P_{ij}^* =  P{(X_m = j | X_{m+1} = i)} = \frac{p_j P_{ji}}{p_i}$$
definition:
The markov chain is time reversible if $P_{ij}^*  = P_{ij}$, forward and backward transition happens with equal probability.

Chain is time reversible if and only if: $p_i P_{ij} = p_j P_{ji}$,(local balance equation) which is true for birth death process, all M/M/*.

Burke's theorem:
consider M/M/* system, with arrival rate $\lambda$, suppose system starts from steady state, then:
1. the departure rate is Poisson with $\lambda$.
2. at each time t, N in the system is independent of the sequence of departure times prior to t.
Proof: Since the chain is TR.
1. arrival and departure are indistinguishable.
(which also proves for birth death process, $d_n = a_n$)
2. at time t, N is is independent of the arrival sequence after t.

example: two MM1 in tandem.
the first queue is MM1 by nature.
the departure process of queue 1 is independent of the service time of queue2, therefore queue2 is also MM1. (the queue2 is not a MM1, it just happens behave like a MM1)
by part b of Burke's, at time t, N1 in queue1 is independent of prior to t departure, also of the N2 of queue2.
$$P[N1 = n, N2 = m] = P[N1 = n] P[N2 = m]$$


//-------------------------------------------------------------------------
3.8 Networks of queues - Jackson's theorem.
solve linear system:
$$\lambda_j = r_j + \sum_{i = 1}^{K}\lambda_i P_{ij}$$
then $\rho_j = \frac{\lambda_j }{\mu_j}$
assuming that $\rho _j <1$, for all j, then
$$P(n)  = \prod _{j = 1}^{K} {\rho_j ^n(1-\rho_j)}$$
as if they were all independent MM1.

closed Jackson's theorem
first, for state independent system:
solve the linear system:
$$\lambda_j = \sum_{i = 1}^{K}\lambda_i P_{ij}$$
define
$$\rho_j= \frac{\lambda_j }{\mu_j}$$
j = 1, ..., K

$$G(M) = \sum_{n1+n2+\ldots+n_K = M} {\rho_1 ^{n_1} \rho_2 ^{n_2} \ldots \rho_K ^{n_K}}$$

Closed Jackson network:
under the preceding assumption
$$P(n_1, n_2, \ldots, n_K) = \frac{\rho_1 ^{n_1} \rho_2 ^{n_2} \ldots \rho_K ^{n_K}}{G(M)}$$
where $G(M)$ can be viewed as a simple normalization constant.

The key is:
1. solve for the internal arrival rates.
2. treat each queue like independent MM1.




//-------------------------------------------------------------------------end