Queueing – Applied Probability Notes

Markov chains and matrices — A Quick Summary

Probabilities for a Markov chain can be expressed in terms of the probability vector $\boldsymbol{\lambda}$ and the transition matrix $P$ .

For example, for $x, x_0, \ldots, x_t \in \mathcal{X}$ and a function $r : \mathcal{X} \rightarrow \mathbb{R}$ ,

$\displaystyle \mathbb{P}(X_0 = x_0, \ldots, X_t = x_t) = \lambda_{x_0} P_{x_0 x_1} \cdots P_{x_{t-1} x_t}$

$\displaystyle \mathbb{P}(X_t = x) = [\lambda P^t]_x$

$\displaystyle \mathbb{E}_x[r(X_t)] = (P^t r)_x$

So essentially, multiplication to the left gives probabilities and multiplication to the right gives expectations.

Notation explanation. If the above is unclear, some notation may need explaining. For $P^t = P \times P \cdots \times P$ , we multiply $t$ copies of the matrix $P$ together.¹ Interpreting $\boldsymbol{\lambda}$ as a row vector, $\boldsymbol{\lambda} P^t$ is a row vector, and $[\boldsymbol{\lambda} P^t]_x$ is the $x$ -th component of that row vector.

Similarly, we can think of the function $r : \mathcal{X} \rightarrow \mathbb{R}$ as a column vector $\boldsymbol{r} = (r(x) : x \in \mathcal{X})$ . Then $P^t \boldsymbol{r}$ is a column vector under matrix multiplication, and $(P^t \boldsymbol{r})_x$ denotes its $x$ -th component.

Throughout these notes, $\mathbb{P}_x(\cdot) = \mathbb{P}(\cdot \mid X_0 = x)$ and $\mathbb{E}_x[\cdot] = \mathbb{E}[\cdot \mid X_0 = x]$ .

¹ We use $\top$ for transpose, not $t$ .

Discrete-time Markov chains — A Quick Look

Markov chains are the primary stochastic process used in queueing theory. The main elements of a Markov chain are its state and the independent randomness used to generate future states. This creates a very clean and natural form of dependence for which many properties are known. We will cover a few important properties of Markov chains, including recurrence, transience, and the existence of stationary distributions.

Congestion Control

We argue, in a slightly informal manner, that queueing networks implicitly optimize a utility function subject to constraints on network capacity. We start with the simple example of a closed queueing network and, as we shall discuss, a motivating example is the Transmission Control Protocol which controls the number of packets in transfer on an Internet connection.

Continue reading “Congestion Control”

Distributed Random Access Scheduling

We consider a network of wireless routers. The routers that are close together can interfere if they transmit simultaneously. So schedules need to avoid such collisions. We want each each wireless node to achieve a transmission rates that equals its arrival rate. One might want to implement a policy like MaxWeight or simply estimate the vector of arrival rates and accordingly choose the correct transmission rate. However, this is complicated by the fact that the routers do not know the arrival and transmission rates of their neighbors; all they can do is sense if their neighbors are transmitting or not.

Continue reading “Distributed Random Access Scheduling”