Ergodic process:

As nothing is neither generated or lost in the queuing system, the arrival rate of packages equals to the departure rate.

Little's Law

Stochastic processes and Markov chains

Given appropriate state space and time variable, a stochastic process can be properly described. If the time variable is discrete, the process is called discrete-time process; otherwise, it's called continuous-time process.

$\mu$ is the number of customers that can be served at one time (serving rate)
$\lambda$ is the mean arrival rate, indicating number of customers arriving per time

Arrival process is a stochastic (random) process. The number of arrivals in a given interval of time duration is characterized by Poisson distribution (Poisson arrival process). While the inter-arrival times of occurrences and the service time in queuing systems are both modeled using an exponential distribution.

Markov (memoryless) property of Poisson arrival process

Markov property describes a kind of dependent relationship between the past state of the process and the future evolution. If a stochastic process is Markov, it indicates that the future evolution of the process is statistically independent to its past.

Arrival process of customers/service requests in many queuing systems exhibit Markov property. A Poisson arrival process is Markovian.

Markov chains

Explanation for memoryless: assume a scenario of walking. You may have several ways/paths to get to the current position. But where you will go next moment (where is your next subsequent position) only depends on your current position (as a new start point) rather than the past/previous position you have passed by.

Birth-death Markov chains: a kind of Markov chain that the state transitions only happen among adjacent states. It can be used to model Markovian queuing systems.

$N(t)$ is the number of packages in a router as a function of time $t$.

Our ultimate goal is to figure out the transmitting probability $P_i$. In the transition region, the probability of having many packages is high and the probability of having less packages is low.

Markov queuing system

$\rho$ tells you the proportion of time a server is busy on average (server utilization factor)

For single server system, $\rho = \frac \lambda \mu$. For an arbitrary long time $\tau$, mean number of arrivals is $\tau \lambda$ ($\lambda$ is the average arriving rate). It takes $\frac{\tau\lambda}{\mu}$ time for the server to process these arrivals, where $\mu$ is the average processing rate of the server. Thus, the proportion of time is calculated as $\frac{\frac{\tau\lambda}{\mu}}{\tau}=\frac \lambda \mu$.

For multi-server system, $\rho$ is defined as the mean of individual servers’ utilizations as each server has its own processing rate or time. $\rho = average(\rho_1+\rho_2+\cdots+\rho_m)$. Assume that there are $m$ identical servers in total and their average processing rate equal to each other, $\mu_1=\mu_2=\cdots=\mu_m$. Thus the utilization factor can be calculated as $\frac{\frac{\lambda\tau}{m}\frac 1 \mu}{\tau}=\frac{\lambda} {m\mu}$.

Traffic intensity/Offered load is the product of customers arrival rate $\lambda$ into the system and the mean time $1/\mu$ that a single server will serve a customer. $A=\frac \lambda \mu$.

M/M/1 queuing system

As there is only one server in the system for processing, this case can be regarded as the simplest birth-death Markov chains. Given different states (number of requests in the queuing line), the birth rate and death rate stay the same respectively ($\lambda, \mu$).

M/M/m queuing system

Due to multiple servers in the system, the death rate of the Markov chain in this case depends on the system state: (maximum serving rate is $m\mu$ in this case)
$$\mu_i=\left\{\begin{aligned} i\mu, \mathrm{for}\ i<m\\ m\mu, \mathrm{for}\ i\geq m \end{aligned}\right. $$

M/M/m/m queuing system

No buffer/queue in this case. Any customer comes to the queue will directly be served. In this case, the system has all together $m+1$ states and it is always stable since there is finite number of states. The birth rate is $\lambda_i = \lambda \ \forall i$ and the death rate depends on the system state: $\mu_i=i\mu \ \forall i$.

Similarly, the state probabilities $P_i$ can be expressed as:
$$P_i = \frac{(m\rho)^i}{i!}P_0 \ \forall i,\ P_0=\frac{1}{\sum_{i=0}^m \frac{(m\rho)^i}{i!}} $$

The blocking probability is equal to the probability that the system is in state $m$: (Erlang B formula)
$$P_b = P_m = \frac{(m\rho)^m}{m!\sum_{i=0}^m\frac{(m\rho)^i}{i!}}=\frac{A^m}{m!\sum_{i=0}^m\frac{A^i}{i!}} $$

Thus, mean number of requests in the system can be expressed as:
$$\begin{align*} N&=\sum_{i=0}^miP_i\\ &=\sum_{i=1}^m i \frac{(m\rho)^i}{i!}P_0\\ &=m\rho\sum_{i=1}^m\frac{(m\rho)^{i-1}}{(i-1)!}P_0\\ &=m\rho (1-P_m)\\ &=m\rho(1-P_b) \end{align*} $$

The rate $\lambda_{accepted}$ that should be used in Little's Law can be obtained as:

M/M/$\infty$ queuing system

In this case, there is no queue/buffer since a service request can always find a free server.

PASTA property

In case of a Poisson arrival process, $a_i = P_i\ \forall i$, where $a_i$ is the probability that an incoming service request finds the system in state i and $P_i$ is the probability that the system is in state i as seen by an external random observer.

Proof of PASTA property:

Assume that:

• $N(t)$ = actual number of service requests in the system at time $t$
• $P_i(t)$ = the probability that the system is in state $i$ at time $t$, which equals to $P\{N(t)=i\}$
• $a_i(t)$ = the probability that the incoming service request finds the system in state $i$
• $A(t,t+\delta t)$ = the event that a service request arrives at time $t$ (between time $t$ and $t+\delta t$, where $\delta t$ is a very small time gap)

Thus, we can write that:
$$a_i(t)=\lim_{\delta t \to 0}P\{N(t)=i|A(t,t+\delta t)\} $$

According to Bayes' theory:
$$P(A|B)=\frac{P(B|A)P(A)}{P(B)} $$

We can derive:
$$a_i(t)=\lim_{\delta t \to 0}\frac{\mathrm{Prob}\left\{A(t,t+\delta t)|N(t)=i\right\}\mathrm{Prob}\left\{N(t)=i\right\}}{\mathrm{Prob}\left\{A(t,t+\delta t)\right\}}$$

Since inter-arrival times possess the memoryless property, $\mathrm{Prob}\left\{A(t,t + \delta t)\right\}$ is independent of the past history of the arrival process and hence independent of the current state of the queuing system, i.e.,
$$\mathrm{Prob}\left\{A(t,t+\delta t)|N(t)=i\right\}=\mathrm{Prob}\left\{A(t,t+\delta t)\right\}$$

Therefore,
$$a_i(t)=\lim_{\delta t \to 0}\frac{\mathrm{Prob}\left\{A(t,t+\delta t)\right\}\mathrm{Prob}\left\{N(t)=i\right\}}{\mathrm{Prob}\left\{A(t,t+\delta t)\right\}}=\mathrm{Prob}\left\{N(t)=i\right\}=P_i(t)$$

Take the limit $t\rightarrow \infty$, we have the PASTA property:
$$a_i=P_i\ \forall i$$