## M/M/1 Queues **M/M/1 queues** stand for a queue with 1 server and exponential interarrival and service times: ![[MM1QueueDiagram.png#invert|center|w80]] The detailed balance equations for a distribution $\xi$ are: $\mu\xi_{i+1}=\lambda \xi_{i}~ ~ ~(i=0,1,\dots),$so it has solutions of the form $\xi_{i}=\left( \frac{\lambda}{\mu} \right)^{i}\xi_{0},$which can be normalized to be a distribution if the **traffic intensity $\rho:= \lambda / \mu<1$**. Using the properties of the jump chain $(Y_{t})$ as a DTMC, - If $\rho >1$, the CTMC $(X_{t})$ is transient. - For $\rho<1$ it is positive recurrent since there is a (unique) stationary distribution. It is null recurrent if $\rho=1$ since the stationary measure cannot be normalized. The arrival process $(A_{t})$ and departure process $(D_{t})$ of a queue is defined to be: $\begin{align*} A_{t}&:= \# \{ s \le t ~|~ X_{s}-X_{s-}=1 \}\\ D_{t}&:= \# \{ s \le t ~|~ X_{s}-X_{s-}=-1 \} \end{align*}$ **Burke's theorem** states that for a M-M-1 queue in equilibrium, with arrival rates of $\lambda$ and processing rate of $\mu$, both the arrival and departure processes are $\mathrm{Po}(\lambda)$. - This is because the chain is reversible under equilibrium, so the arrival process of the time-reversal $(\hat{X}_{t})$ is also $\mathrm{Po}(\lambda)$, but this is just the reversal of $(D_{t})$, so by symmetry of the original process, $(D_{t})$ has the same distribution as its reversal. ## M/M/s Queues **M/M/s queues** are queues with $s$ servers and exponential interarrival and service times: ![[MMsQueueDiagram.png#invert|center|w80]] Note that the down rate increases linearly up to $s\mu$, when all servers are busy. The detailed balance equations read $\begin{cases} \lambda\xi_{i}=(i+1)\mu \xi_{i+1} & \text{if }i < s ,\\ \lambda\xi_{i}=s\mu \xi_{i+1} & \text{if }i \ge s . \end{cases}$Therefore the invariant measure is (with **traffic intensity $\rho:= s\lambda / \mu$**), $\xi_{i}\propto \begin{dcases} \frac{\rho^{i}s^{i}}{i!}& \text{ if }i < s ,\\[0.4em] \frac{\rho^{i}s^{s}}{s!}& \text{if }i \ge s . \end{dcases}$To normalize it into a distribution, we just need $\rho<1$, and the recurrence/transience is the same as the M/M/1 queue. ## M/G/1 Queues The M/G/1 queue is the same as the M/M/1 queue, except that the service times $G$ are not necessarily exponential, but follows some general distribution. - Instead of the rate, let $\mu:= 1 / \mathbb{E}[G]$, and the traffic rate is again $\rho:= \lambda /\mu= \lambda \mathbb{E}[G]$. We may still study the process as a DTMC, studied at the times of departure: $D_{0}=0$ and $D_{n}:= \inf \{ t > D_{n-1}~|~\underset{\substack{\text{departure just}\\ \text{happened}}}{X_{t}+1=X_{t-}} \}.$At those departure, let there be $(V_{n}):= X_{D_{n}}$ people remaining in the queue. > [!theorem|*] Departure Chain is a DTMC > Let $G$ have the distribution of the service time, then *$(V_{n})$ is a DTMC* with transition probabilities > $\begin{align*} p_{i \to j}&= \mathbb{P}[(i-j+1) \text{ people arrived before the departure}]\\[0.4em] &= \mathbb{E}_{G}[\pi_{\mathrm{Po}(G\lambda)}(i-j+1)] \\[0.4em] &= \begin{cases} \mathbb{E}_{G}\left[ e^{-G\lambda}\cdot\frac{(G\lambda)^{j-i+1}}{(j-i+1)!} \right] & \text{if }j\ge i-1, \\[0.4em] 0 &\text{otherwise}. \end{cases} \end{align*}$ where $\pi_{\mathrm{Po(\theta)}}$ is the pmf. of the Poisson distribution with rate $\theta$. > >[!proof] > > It is a DTMC because: > > - The service times $G_{1},\dots$ are independent by assumption, so the (Poisson process) arrivals $N_{1},\dots$ during each service time are also independent. The increments of $V_{n}$ are just $(N_{n})-1$. > > > > Condition on the interarrival time $G$, then by independence assumptions, the number of customers arriving have the distribution $\mathrm{Po}(G \lambda)$. > > > > Now take the expectation over $G$ and use the tower law to get the result. Given the total waiting time $T$ of a customer (time spent waiting in queue $W$ plus the service time $G$), the number of people arriving after them (which is also the value of $V$ after their departure) is $\mathrm{Po}(T\lambda)$. Therefore, if the queue is in equilibrium, it has pgf. $\phi$: $\phi(s)=\mathbb{E}_{T}[\mathbb{E}_{N ~|~ T}[s^{N}]]=\mathbb{E}_{T}[e^{\lambda(s-1)T} ],$where the second equality substitutes in the Poisson pgf of $N ~|~ T$. By independence between $W,G$: $\phi(s)=\mathbb{E}[e^{\lambda(s-1)W}] \cdot \mathbb{E}[e^{\lambda(s-1)G}],$and solving for the term involving $W$ gives (with $\theta=\lambda(s-1)$): $\mathbb{E}[e^{\theta W}]=\frac{\phi(s)}{\psi(\theta)}=\frac{(1-s)(1-\rho)}{\psi(\theta)-s}$ ## G/M/1 Queues Similarly, the **G/M/1** queue has a general interarrival time $Z$ and an exponential service time of rate $\mu$. - The **traffic intensity** is $\rho:= \mathbb{E}[Z] / \mu$. We may study $(U_{n})$, the number of (other) people in the queue when the $n$th person arrives: $U_{n}:= X_{T_{n}-},$and similar to the departure process for M/G/1 queues, $(U_{n})$ is also a DTMC: > [!theorem|*] Arrival Chain is a DTMC > Let $Z$ have the distribution of the interarrival time, then *$(U_{n})$ is a DTMC* with transition probabilities > $\begin{align*} p_{i \to j}&= \mathbb{P}[(i-j+1) \text{ people left before the arrival}]\\[0.4em] &= \begin{cases} \text{the queue is not emptied}& \text{if }j > 0, \\[0.4em] \text{the queue is emptied} & \text{if }j=0, \\[0.4em] \text{impossible} &\text{otherwise}. \end{cases}\\[0.8em] &= \begin{cases} \mathbb{E}_{Z}\left[ e^{-Z\mu}\cdot\frac{(Z\mu)^{i-j+1}}{(i-j+1)!} \right] & \text{if }j> 0, \\[0.4em] 1- \sum_{j \ne 0} p_{i \to j} & \text{if }j=0,\\[0.4em] 0 &\text{otherwise}. \end{cases} \end{align*}.$ > >[!proof] > > It is a DTMC because: > > - The interarrival times $Z_{1},\dots$ are independent by assumption, so the (Poisson process) departures $N_{1},\dots$ during each service time are also independent. The increments of $(U_{n})$ are just $1-(N_{n})$. > > > > Condition on the interarrival time $Z$, then by independence assumptions, the number of customers leaving have the distribution $\min(i+1, \mathrm{Po}(Z \mu))$. > > - If the queue is not empty, the increment is still Poisson; > > - The queue being emptied is just complement to the above. > > > > Now take the expectation over $Z$ and use the tower law to get the result. Furthermore, if the traffic intensity $\rho=\mathbb{E}[Z] / \mu<1$, then the chain $(U_{n})$ has a unique stationary distribution $\xi$ equal to the pmf. of $\mathrm{Geom}(1-q)$, where $q$ is the minimal positive solution to $s:s=\mathbb{E}[e^{\mu(s-1)Z}]=m_{Z}(\mu(s-1))$. > [!proof]- > Simply verify stationarity: $\begin{align*} p_{\ast \to j} \cdot \xi&= \sum_{i}p_{i \to j}\xi_{i}\\ &= \sum_{i=j-1}^{\infty} \mathbb{E}_{Z}\left[e^{-Z\mu} \frac{(Z\mu)^{i-j+1}}{(i-j+1)!} \right] \cdot q^i(1-q)\\ &= \sum_{k=0}^{\infty}\mathbb{E}_{Z}\left[ e^{-Z\mu} \frac{(Zq\mu)^{k}}{k!} \right]q^{j-1}(1-q)\\ &= \underbrace{\mathbb{E}_{Z}[e^{Z\mu(q-1)}]}_{=q} \cdot q^{j-1}(1-q)\\ &= \xi_{j}. \end{align*}$ - For example, the M/M/1 queue has $m_{Z}(t)=\frac{\lambda}{\lambda-t}$, so the solution $q$ to $q=m_{Z}(\mu(q-1))$ is $q=\rho$, consistent with the M/M/1 conclusion.