# A Markovian Analysis of an IEEE-802.11 Station with Buffering

Guy Fayolle, Paul Muhlethaler

► To cite this version:

Guy Fayolle, Paul Muhlethaler. A Markovian Analysis of an IEEE-802.11 Station with Buffering. Markov Processes And Related Fields, 2023, 29 (5), pp.709-726. 10.61102/1024-2953-mprf.2023.29.5.006. hal-04362437v2

HAL Id: hal-04362437

https://inria.hal.science/hal-04362437v2

Submitted on 7 Mar 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# A Markovian analysis of an IEEE-802.11 station with buffering

Guy Fayolle* Paul Muhlethaler †

## Abstract

The purpose of this paper is to analyze the so-called *backoff technique* of the IEEE 802.11 protocol with buffers. This protocol rules the transmissions on a radio channel between nodes (or stations) of a network exchanging packets of information. In contrast to existing models, packets arriving at a station which in the backoff state are not discarded, but are stored in a buffer of infinite capacity. *The backoff state* corresponds to the number of time-intervals (mini-slot) that a node must wait before its packet is actually transmitted. As in previous studies, the key point of our analysis hinges on the assumption that the time on the radio channel is viewed as a random succession of transmission slots (whose duration corresponds to a packet transmission time) and mini-slots, which stand for the time intervals during which the backoff of the station is decremented. During these mini-slots the channel is idle, which implies that there is no packet transmission. These events occur independently with given probabilities, and the external arrivals of messages follow a Poisson process. The state of a node is represented by a three-dimensional Markov chain in discrete-time, formed by the triple (backoff counter, number of packets at the station, number of transmission attempts). Stability (ergodicity) conditions are obtained for an arbitrary station and interpreted in terms of maximum throughput. Several approximations related to these models are also discussed.

**Keywords:** Wireless LAN, IEEE 802.11 protocol, Analytical Model, Markov chain, Generating Function, Ergodicity

## 1 Introduction and model outline

This section presents the main assumptions of the study and briefly summarizes how the access pattern is organized in the network.

The protocol IEEE 802.11 which we study rules the transmissions on a radio channel between nodes (or stations) of a network exchanging packets of information.

A packet consists of a series of bits (or 0 or 1), and represents the smallest piece of information exchanged on the channel (radio medium). These series of bits are modulated and sent as an electromagnetic signal. When this signal arrives at the receiving node, it is demodulated and the packet is rebuilt. In contrast to existing models, packets arriving at a station which is in a state commonly known as the *backoff state* are not discarded, but stored in a buffer of infinite capacity. This backoff state actually corresponds to a counter, which is the number of time-intervals (*mini-slots*) that a node must wait before its packet is actually transmitted. Where the context allows, we simply write backoff instead of backoff counter. The channel is supposed to be sampled at discrete time instants $Z_i$, so that it is sensed during consecutive time intervals $Z_i - Z_{i-1}, i \ge 1$, which are equal either to $T$ (*normal transmission slot*) or to $\sigma$ (*mini-slot*). In some sense, we have thus introduced two embedded time-scales: normal slots are used to transmit packets on the

<footnote>*INRIA Paris-Rocquencourt, Domaine de Voluceau, BP 105, 78153 Le Chesnay Cedex, France. Email: Guy.Fayolle@inria.fr</footnote>

<footnote>†INRIA Paris, 2 rue Simone Iff 75012 Paris, France. E.mail: Paul.Muhlethaler@inria.fr</footnote>
channel, whereas mini-slots correspond to time-intervals during which the backoff counters of all stations of the network are decremented.

In general, the selection between these two types of slots is random: a slot is a normal with probability $r$, and a mini-slot with probability $1-r$. Nonetheless an arbitrary node will be said to be greedy, as, when the backoff of a station reaches 0, a transmission takes place in a slot which is necessarily a normal one of length $T$. This implies in particular that a sequence of slots is not exactly obtained as a pure outcome of repeated Bernoulli trials. We also assume that a collision can occur if at least two packets from two different stations are sent simultaneously, in which case this collision (usually indicated by a lack of acknowledgment) has the duration of the normal slot of length $T$. The duration of the acknowledgment (or lack of acknowledgment) is supposed to be part of a normal slot of length $T$.

The backoff and the retransmission policy are really the two main ingredients of the access algorithm of the IEEE 802.11 protocol. When a packet arrives at a station, it receives a backoff which counts the idle time before the transmission of the packet. Whenever a collision occurs, the packet receives another backoff (usually greater than the previous one) for retransmission. This process stops when the packet is successfully transmitted. The detailed automaton of the access scheme is presented in the next section.

Our purpose is to analyze the stability of an arbitrary IEEE 802.11 node. In contrast to the seminal model proposed by G. Bianchi [1], we allow infinite buffer at the node. In [4], the broadcast transmission was analyzed, but collision events were not considered by the access protocol.

The present paper is organized as follows. Section 2 describes the dynamics and the main parameters of an arbitrary station, sometimes referred to as the ego station. Section 3 is devoted to the forward Kolmogorov's equations. Sections 4, 5, 6 study the steady-state behavior of the process. In particular, ergodicity conditions are explicitly obtained in Section 6. The final Section 7 proposes some reflections aiming at the immersion of the station into a network.

## 2 Dynamics

The isolated ego station which we analyze in the sequel could be viewed as an element of a network made of such identical stations. The three following parameters are of prime importance.

* The probability $p$ of collision, when at least two packets (originating in fact from different stations) are simultaneously transmitted on the channel.

* The probability $r$ that the channel is busy.

* The Poisson process rate $\lambda$ of packets arriving at the station.

In our model, $p$ and $r$ are essentially viewed as constant exogenous parameters, but in the final Section 7 some suggestions are made pertaining to a network context, in which case, from a realistic point of view, it would be necessary to assume $r > p$.

### 2.1 Detailed operation of the protocol

The WiFi IEEE 802.11 algorithm is based on a backoff scheme and a retransmission in case of a collision on the channel. When a new packet arrives at the ego station, according to a Poisson process of rate $\lambda$, it receives a random backoff of $k \in [0, 1, 2, ..., W_0 - 1]$, so that the idle time until its effective transmission will be $k\sigma$. The ego station monitors the channel and the backoff is decremented by one unit when an empty slot is sensed on the transmission channel, i.e. the event on the channel is a mini-slot $\sigma$. When the backoff counter $k$ reaches 0, the packet in the ego station is transmitted and generates a slot of size $T$ on the channel. If the transmission is successful, then the ego station removes the pending packet from its waiting queue. If the transmission is a collision, then the transmission level, also called *backoff stage*, is incremented by 1, going say from $m$ to $m + 1$, and the value of the backoff counter of the packet is uniformly chosen over a new interval (or window) of size $W_{m+1}$. For $W_m = \alpha^m W_0$, the backoff window size is thus increased by the factor $\alpha > 1$ (in IEEE 802.11, $\alpha$ is usually 2). Whenever $m = M$, the packet remains at the $M$-th
transmission level, with a backoff drawn uniformly over $W_M$, and $M$ thus denotes the maximum backoff stage, which is a finite positive integer. When the transmission is a success (this occurs with probability $1-p$), the pending packet is removed from the waiting queue of the ego station. If at least one pending packet remains in the queue, then this packet directly receives a backoff $k$, uniformly distributed over $[0, 1, 2, \dots, W_0 - 1]$; otherwise the automaton of the ego station enters an idle state, waiting for a new arrival which will receive a backoff $k \in [0, 1, 2, \dots, W_0 - 1]$. The automaton is shown in Figure 2.1.

## 2.2 Main notations

According to the preceding section, we introduce the following basic variables.

* $n$, the number of pending packets at the ego station.

* $m$, the backoff stage, where $m \in [0, 1, \dots, M]$.

* The windows $W_i$, $0 \le i \le M$, form a sequence of fixed positive numbers.

* $k$, an integer representing the backoff time counter in an arbitrary window $W_m$, so that $k \in [0, 1, 2, \dots, W_m - 1]$. In typical applications, the size of the backoff window at the $m$-th stage will have the form $W_m = \alpha^m W_0$, with $\alpha > 1$.

* $\mathcal{A} \stackrel{\text{def}}{=} \{(k, n, m) \in [0, W] \times [0, \infty] \times [0, M]\}$, with $W = \max\{W_i, 1 \le i \le M\}$. This countable set $\mathcal{A}$ is endowed with the $\sigma$-algebra $\mathfrak{A}$.

The behavior of the ego station will be represented by a stochastic process, which is a three-dimensional random walk $\{X_i \stackrel{\text{def}}{=} (K_{Z_i}, N_{Z_i}, M_{Z_i}), i \ge 1\}$, where $Z_i$ is the embedded increasing sequence of discrete random times at which the chain is observed. At time $Z_i$, $K_{Z_i}$ stands for the value of the backoff counter, $N_{Z_i}$ is the number of packets in the waiting queue at the station, and $M_{Z_i}$ is the transmission level.

Under the initial conditions $Z_1 = 0$ and $(K_0 = k, N_0 = n, M_0 = m)$, the sequence of random instants $Z_i, i \ge 1$, introduced above satisfies the recursive stochastic relationship

$$Z_{i+1} = Z_i + \Delta_i [\mathbb{1}_{\{K_{Z_i}>0\}} + \mathbb{1}_{\{K_{Z_i}=N_{Z_i}=0\}}] + T \mathbb{1}_{\{K_{Z_i}=0, N_{Z_i}>0\}}, \quad (2.1)$$

with

$$\Delta_i = T \mathbb{1}_{\{B_i\}} + \sigma(1 - \mathbb{1}_{\{B_i\}}),$$

where $\mathbb{1}_{\{\cdot\}}$ is an indicator function and $B_i$ idenotes the event $\{\text{channel busy}\}$ at time $Z_i$. From the assumptions made above, $\{\mathbb{1}_{\{B_i\}}, i \ge 1\}$ forms a sequence of independent identically distributed random variables with $\mathbb{P}(B_i) = r$. The probability of sensing an idle slot is thus $1 - \mathbb{P}(B_i) = 1 - r$.

The rest of the paper is devoted to the probabilistic analysis of $\{X_i\}$, the main result being an explicit bound on $\lambda$ (see Theorem 6.4) for the station to be stable, or, in other words, for the process to be ergodic.

## 3 Forward Kolmogorov's equations in a random environment

In accordance with the definitions given in 2.2, the stochastic process $\{X_i, i \ge 1\}$, with state space $(\mathcal{A}, \mathfrak{A})$, can be seen as evolving in the stationary random environment generated by the sequence of independent Bernoulli trials $\{B_i, i \ge 1\}$ (see e.g. [2, 3, 6] and references therein).

The sequence $\{\mathbb{1}_{\{B_i\}}, i \ge 1\}$ of i.i.d. random variables is stationary ergodic, and it is immediate to check that the joint process $Y_i \stackrel{\text{def}}{=} \{X_i, \mathbb{1}_{\{B_i\}}\}$ forms an irreducible Markov chain taking its values in $(\mathcal{A} \times \mathcal{B}, \mathfrak{A} \times \mathfrak{B})$.

Let

$$p_i(k, n, m) \stackrel{\text{def}}{=} \mathbb{P}(K_{Z_i} = k, N_{Z_i} = n, M_{Z_i} = m)$$

denote the random variable which is the probability distribution of $X_i$ at time $Z_i$.
<figure><img src="image_2.png" /><figcaption>Fig. 2.1: The WiFi Markov chain</figcaption></figure>
Then

$$Q(a, b; u) \stackrel{\text{def}}{=} \mathbb{P}(X_{i+1} = b | X_i = a, \mathbb{1}_{\{B_i\}} = u) \quad (3.1)$$

is the conditional probability for $\{X_i\}$ to go from $a$ to $b$ in one step in the $u$ environment, remembering that $(a, b) \in \mathcal{A}$ are 3-dimensional vectors with integer coordinates, and $u \in \{0, 1\}$.

Hence, the one step transition probabilities of the Markov chain $\{Y_i = (X_i, \mathbb{1}_{\{B_i\}})\}$ can be written as the product of two kernels given by

$$\mathbb{P}[(b, v)|(a, u)] \stackrel{\text{def}}{=} K(v)Q(a, b; u), \quad (3.2)$$

where $K(v)$ is the one-step transition probability for the sequence of independent random variables $\{\mathbb{1}_{\{B_i\}}\}$. To avoid unnecessarily overloading the presentation, we shall not write explicitly the generator defined in (3.2), preferring instead to detail the following Kolmogorov's forward equations (see e.g [5]) depicting the evolution of the $p_i$'s.

(1) For $0 \le k \le W_m - 1$ and $1 \le m \le M - 1$, the following general equilibrium equation holds.

$$\begin{aligned} p_{i+1}(k, n, m) = \mathbb{1}_{\{k>0\}} \mathbb{1}_{\{B_i\}} & \sum_{j=0}^{n-1} \frac{e^{-\lambda T} (\lambda T)^j}{j!} p_i(k, n-j, m) \\ & + \frac{p}{W_m} \sum_{j=0}^{n-1} \frac{e^{-\lambda T} (\lambda T)^j}{j!} p_i(0, n-j, m-1) \\ & + \mathbb{1}_{\{k< W_m-1\}} (1-\mathbb{1}_{\{B_i\}}) \sum_{j=0}^{n-1} \frac{e^{-\lambda \sigma} (\lambda \sigma)^j}{j!} p_i(k+1, n-j, m). \end{aligned} \quad (3.3)$$

(2) For $m = M$ and $0 \le k \le W_M - 1$, according to the dynamics of the model, we have the special equation

$$\begin{aligned} p_{i+1}(k, n, M) = \mathbb{1}_{\{k>0\}} \mathbb{1}_{\{B_i\}} & \sum_{j=0}^{n-1} \frac{e^{-\lambda T} (\lambda T)^j}{j!} p_i(k, n-j, M) \\ & + \frac{p}{W_M} \left( \sum_{j=0}^{n-1} \frac{e^{-\lambda T} (\lambda T)^j}{j!} p_i(0, n-j, M-1) + \sum_{j=0}^{n-1} \frac{e^{-\lambda T} (\lambda T)^j}{j!} p_i(0, n-j, M) \right) \\ & + \mathbb{1}_{\{k< W_M-1\}} (1-\mathbb{1}_{\{B_i\}}) \sum_{j=0}^{n-1} \frac{e^{-\lambda \sigma} (\lambda \sigma)^j}{j!} p_i(k+1, n-j, M). \end{aligned} \quad (3.4)$$

(3) For the last boundary case $m = 0$, $0 \le k < W_0$ and $n \ge 1$, we have

$$\begin{aligned} p_{i+1}(k, n, 0) = \mathbb{1}_{\{k>0\}} \mathbb{1}_{\{B_i\}} & \sum_{j=0}^{n-1} \frac{e^{-\lambda T} (\lambda T)^j}{j!} p_i(k, n-j, 0) \\ & + \sum_{m=0}^{M} \frac{1-p}{W_0} \sum_{j=0}^{n} \frac{e^{-\lambda T} (\lambda T)^j}{j!} p_i(0, n+1-j, m) \\ & + \frac{1}{W_0} \left( \mathbb{1}_{\{B_i\}} \frac{e^{-\lambda T} (\lambda T)^n}{n!} + (1-\mathbb{1}_{\{B_i\}}) \frac{e^{-\lambda \sigma} (\lambda \sigma)^n}{n!} \right) p_i(0, 0, 0) \\ & + \mathbb{1}_{\{k< W_0-1\}} (1-\mathbb{1}_{\{B_i\}}) \sum_{j=0}^{n-1} \frac{e^{-\lambda \sigma} (\lambda \sigma)^j}{j!} p_i(k+1, n-j, 0). \end{aligned} \quad (3.5)$$

On the other hand, it is important to note that the dynamic of the algorithm implies that the states $(k, 0, m)$ do not exist, unless when $k = m = 0$ which corresponds to the state $(0, 0, 0)$. Then one
can easily check that the Markov chain is irreducible, in agreement with the following additional equation

$$p_{i+1}(0,0,0) = \mathbb{1}_{\{B_i\}}e^{-\lambda T}p_i(0,0,0) + (1-\mathbb{1}_{\{B_i\}})e^{-\lambda\sigma}p_i(0,0,0) \\ + e^{-\lambda T}(1-p)\sum_{m=0}^{M}p_i(0,1,m). \qquad (3.6)$$

Equation 3.3 means that the state $(k, n, m)$ can be reached from the state $(k, n-j, m)$ after a normal slot encompassing $j$ external arrivals. Likewise, $(k, n, m)$ can be reached from $(k+1, n-j, m)$ after sensing a mini-slot with $j$ arrivals. Finally, $(k, n, m)$ can be reached from $(0, n-j, m-1)$ after a collision and $j$ arrivals with probability $p/W_m$.

Equation 3.4 means that the state $(k, n, M)$ can be reached from the state $(k, n-j, M)$ after a normal slot with $j$ external arrivals. Similarly, $(k, n, M)$ can be reached either from $(0, n-j, M)$ or from $(0, n-j, M-1)$ after $j$ arrivals with probability $p/W_M$. Finally, $(k, n, M)$ can be reached from $(k+1, n-j, M)$ after a mini-slot with $j$ arrivals.

Equation 3.5 means that $(k, n, 0)$ can be reached from $(k, n-j, 0)$ after a normal slot and $j$ arrivals. Likewise, $(k, n, 0)$ can be reached from $(0, n+1-j, m)$ after $j$ arrivals with probability $(1-p)/W_0$, and $(k, n, 0)$ can be reached from $(0, 0, 0)$ after $n$ arrivals during a full slot or a mini-slot with probability $1/W_0$. Finally, state $(k, n, 0)$ can be reached from $(k+1, n-j, 0)$ after $j$ arrivals during a mini-slot. Finally state $(k, n, 0)$ can be reached from state $(k+1, n-j, 0)$ after sensing a mini-slot with $j$ arrivals.

Equation 3.6 means that $(0, 0, 0)$ can be reached either from $(0, 0, 0)$ (no arrival during a slot or a mini-slot), or from the states $(0, 1, m)$, with $0 \le m \le M$, when no arrival occurs during a normal slot.

# 4 Stationary regime

As mentioned before, the Markov chain $\{Y_i\}$ is irreducible with a countable state space, and therefore has at most one stationary invariant measure.

Let us construct an auxiliary Markov chain $\{\tilde{X}_i\}$ with distribution $q_i(k, n, m)$, which evolves according to equations (3.3), (3.4), (3.5), (3.6), just replacing in the right-hand sides the $\mathbb{1}_{\{B_i\}}$'s by $r$. In a way, for large $i$, the construction of $\{\tilde{X}_i\}$ amounts to taking the expectation with respect to the environment. Noting that $\lim_{i \to \infty} Z_i = +\infty$ almost surely (and even surely from (2.1), we can easily adapt some results of [6] and claim that $\{Y_i\}$ is positive recurrent if and only if the Markov chain $\{\tilde{X}_i\}$ is positive recurrent. Hence, we shall analyze in detail the stationary distribution of $\{\tilde{X}_i\}$, which will simply denoted by $p(k, n, m)$.

In the rest of the study, for the sake of brevity, we simply write

$$p(0) \stackrel{\text{def}}{=} p(0, 0, 0).$$

Then, for $1 \le m < M$ and $0 \le k < W_m$, equations (3.3) and (3.4) yield

$$p(k, n, m) = \mathbb{1}_{\{k>0\}}r \sum_{j=0}^{n-1} \frac{e^{-\lambda T}(\lambda T)^j}{j!}p(k, n-j, m) + \frac{p}{W_m} \sum_{j=0}^{n-1} \frac{e^{-\lambda T}(\lambda T)^j}{j!}p(0, n-j, m-1) \\ + \mathbb{1}_{\{k< W_m-1\}}(1-r) \sum_{j=0}^{n-1} \frac{e^{-\lambda \sigma}(\lambda \sigma)^j}{j!}p(k+1, n-j, m), \qquad (4.1)$$
together with (the case $m = M$)

$$ 
\begin{aligned}
p(k, n, M) = {}& \mathbb{1}_{\{k>0\}} r \sum_{j=0}^{n-1} \frac{e^{-\lambda T}(\lambda T)^j}{j!} p(k, n-j, M) \\
& + \frac{p}{W_M} \left( \sum_{j=0}^{n-1} \frac{e^{-\lambda T}(\lambda T)^j}{j!} p(0, n-j, M-1) + \sum_{j=0}^{n-1} \frac{e^{-\lambda T}(\lambda T)^j}{j!} p(0, n-j, M) \right) \\
& + \mathbb{1}_{\{k<W_M-1\}} (1-r) \sum_{j=0}^{n-1} \frac{e^{-\lambda \sigma}(\lambda \sigma)^j}{j!} p(k+1, n-j, M).
\end{aligned} 
\quad (4.2) $$

Similarly, for $m = 0, 0 \le k < W_0$ and $n \ge 1$, we get from (3.5) and (3.6)

$$ 
\begin{aligned}
p(k, n, 0) = {}& \mathbb{1}_{\{k>0\}} r \sum_{j=0}^{n-1} \frac{e^{-\lambda T}(\lambda T)^j}{j!} p(k, n-j, 0) + \sum_{m=0}^{M} \frac{1-p}{W_0} \sum_{j=0}^{n} \frac{e^{-\lambda T}(\lambda T)^j}{j!} p(0, n+1-j, m) \\
& + \mathbb{1}_{\{k<W_0-1\}} (1-r) \sum_{j=0}^{n-1} \frac{e^{-\lambda \sigma}(\lambda \sigma)^j}{j!} p(k+1, n-j, 0) \\
& + \frac{p(0)}{W_0} \left( \frac{r e^{-\lambda T}(\lambda T)^n + (1-r)e^{-\lambda \sigma}(\lambda \sigma)^n}{n!} \right),
\end{aligned} 
\quad (4.3) $$

together with

$$ [1 - r e^{-\lambda T} - (1-r)e^{-\lambda \sigma}] p(0) = (1-p)e^{-\lambda T} \sum_{m=0}^{M} p(0, 1, m). \quad (4.4) $$

# 5 Functional equations

Let us introduce the generating functions

$$ G_{k,m}(x) \stackrel{\text{def}}{=} \sum_{n=0}^{\infty} p(k, n+1, m)x^n, \quad H_m(x, y) \stackrel{\text{def}}{=} \sum_{k=0}^{W_m-1} G_{k,m}(x)y^k, \quad 0 \le m \le M, \quad (5.1) $$

which are a priori defined in the complex plane for $|x| \le 1$ and $|y|$ finite (since the $H_m$'s are polynomials in $y$), keeping in mind here that $G_{0,m}(x) = H_m(x, 0) = 0, \forall m \ge 0$.

## 5.1 Functional recurrence relationships

Let

$$ R(x, y) \stackrel{\text{def}}{=} 1 - \frac{(1-r)e^{-\lambda\sigma(1-x)}}{y} - r e^{-\lambda T(1-x)}. \quad (5.2) $$

As before, we have to consider three different cases, depending on the values of $m$.

(a) For $1 \le m < M$, by multiplying equation (4.1) by $x^{n-1}$ and summing over $n \ge 1$, we obtain the following recurrence.

$$ G_{k,m}(x) = r \mathbb{1}_{\{k>0\}} e^{-\lambda T(x-1)} G_{k,m}(x) + \frac{p e^{-\lambda T(1-x)}}{W_m} G_{0,m-1}(x) \\
+ \mathbb{1}_{\{k<W_m-1\}} (1-r) G_{k+1,m}(x) e^{-\lambda \sigma(1-x)}, $$

whence, after summing over $k, 0 \le k < W_m$,

$$ R(x, y)H_m(x, y) = (R(x, y) - 1)H_m(x, 0) + \frac{p(1 - y^{W_m})e^{-\lambda T(1-x)}}{W_m(1 - y)} H_{m-1}(x, 0). \quad (5.3) $$
(b) Similarly, for $m = M$, we get from (4.2)

$$G_{k,M}(x) = r \mathbb{1}_{\{k>0\}} e^{-\lambda T(1-x)} G_{k,M}(x) + \frac{p e^{-\lambda T(1-x)}}{W_M} [G_{0,M-1}(x) + G_{0,M}(x)] \\ + \mathbb{1}_{\{k<W_M-1\}} (1-r) G_{k+1,M}(x) e^{-\lambda \sigma(1-x)},$$

which yields in turn

$$R(x, y)H_M(x, y) = (R(x, y) - 1)H_M(x, 0) + \frac{p(1 - y^{W_M})e^{-\lambda T(1-x)}}{W_M(1 - y)} [H_{M-1}(x, 0) + H_M(x, 0)]. \quad (5.4)$$

(c) For $m = 0$, the derivation of a functional relation from equation (4.3) is slightly more awkward, due to the presence of boundary terms appearing when $n = 1$. After a preliminary tedious algebra, we obtain

$$G_{k,0}(x) = r \mathbb{1}_{\{k>0\}} re^{-\lambda T(1-x)} G_{k,0}(x) + \mathbb{1}_{\{k<W_0-1\}} (1-r) G_{k+1,0}(x) e^{-\lambda \sigma(1-x)} \\ + \frac{p(0)[R(0,1) - R(x,1)] + (1-p)[e^{-\lambda T(1-x)}S(x) - K]}{xW_0}, \quad (5.5)$$

with

$$S(x) \stackrel{\text{def}}{=} \sum_{m=0}^{M} G_{0,m}(x) = \sum_{m=0}^{M} H_m(x, 0), \quad \text{and} \quad K \stackrel{\text{def}}{=} e^{-\lambda T} \sum_{m=0}^{M} p(0, 1, m) = e^{-\lambda T} S(0).$$

By equation (4.4), we have the simple relation $(1-p)K = R(0,1)p(0,0,0)$, which allows to rewrite (5.5) in the slightly more compact form

$$G_{k,0}(x) = r \mathbb{1}_{\{k>0\}} re^{-\lambda T(1-x)} G_{k,0}(x) + \mathbb{1}_{\{k<W_0-1\}} (1-r) G_{k+1,0}(x) e^{-\lambda \sigma(1-x)} \\ + \frac{(1-p)e^{-\lambda T(1-x)}S(x) - p(0)R(x,1)}{xW_0}, \quad (5.6)$$

which, after multiplying by $y^k$ and summing over $k$, leads to

$$R(x, y)H_0(x, y) = (R(x, y) - 1)H_0(x, 0) \\ + \frac{1 - y^{W_0}}{W_0 x(1 - y)} \left[ (1 - p)e^{-\lambda T(1-x)}S(x) - p(0)R(x, 1) \right] \quad (5.7)$$

## 5.2 The basic triangular scheme

The equations obtained in Section 5.1 lead to the following lemma.

**Lemma 5.1.**

$$\left\{ \begin{array}{l} H_m(x, 0) = p U_m(x) H_{m-1}(x, 0), \quad 1 \le m < M, \\ H_M(x, 0) = \frac{p U_M(x)}{1 - p U_M(x)} H_{M-1}(x, 0), \\ H_0(x, 0) = \frac{U_0(x) [(1 - p)S(x) - p(0)e^{\lambda T(1-x)} R(x, 1)]}{x} \end{array} \right. \quad (5.8)$$

where

$$\left\{ \begin{array}{l} \varphi(x) \stackrel{\text{def}}{=} \frac{(1-r)e^{-\lambda \sigma(1-x)}}{1 - re^{-\lambda T(1-x)}}, \\ U_m(x) \stackrel{\text{def}}{=} \frac{(1 - \varphi(x)^{W_m})e^{-\lambda T(1-x)}}{W_m(1 - \varphi(x))}, \quad 0 \le m \le M. \end{array} \right. \quad (5.9)$$
**Proof.** Straightforward, noting that, $\forall 0 \le m \le M$, the function $H_m(x, y)$ is analytic in $y$, as being a polynomial in $y$. So, for $y = \varphi(x)$, the kernel $R(x, y)$ in equations (5.3),(5.4),(5.7) does vanish, and system (5.8) follows immediately.

<figure><img src="image_3.png" /></figure>

Furthermore, by using the definition of $S(x)$ given in (5.5), we see that system (5.8) allows to get an explicit form for $H_m(x, 0), \forall m \ge 0$. But, before going into more detailed calculations, we will state the following important quantitative result.

**Proposition 5.2.** *When the Markov chain $\{\tilde{X}_i\}$ constructed in Section 4 is ergodic, the probability $p(0)$ is given by the formula*

$$p(0) = \frac{1}{1 + C e^{\lambda T} (1 - r e^{-\lambda T} - (1 - r) e^{-\lambda \sigma})}, \quad (5.10)$$

where

$$C \stackrel{\text{def}}{=} \sum_{m=0}^{M} C_m p^m, \quad C_m = 1 + \frac{W_m - 1}{2(1-r)}, \quad 0 \le m < M, \quad C_M = \frac{1}{1-p} \left[ 1 + \frac{W_M - 1}{2(1-r)} \right].$$

**Proof.** Under the assumption of positive recurrence, the only remaining unknown $p(0)$ in system (5.8) can be obtained from the normalization condition

$$\sum_{k \ge 0} \sum_{n \ge 1} \sum_{m=0}^{M} p(k, n, m) = \sum_{m=0}^{M} H_m(1, 1) = 1 - p(0). \quad (5.11)$$

Then, by using (5.3),(5.4),(5.7) and (5.8), we get after a straightforward algebra

$$\left\{
\begin{aligned}
R(x, 1)H_m(x, 1) &= p[(R(x, 1) - 1)U_m(x) + e^{-\lambda T(1-x)}]H_{m-1}(x, 0), \quad 1 \le m < M, \\
R(x, 1)H_M(x, 1) &= \left[R(x, 1) - 1 + \frac{e^{-\lambda T(1-x)}}{U_M(x)}\right]H_M(x, 0), \\
R(x, 1)H_0(x, 1) &= \frac{[(1-p)S(x) - p(0)e^{\lambda T(1-x)}R(x, 1)][(R(x, 1) - 1)U_0(x) + e^{-\lambda T(1-x)}]}{x}.
\end{aligned}
\right.
\quad (5.12)$$

In addition, letting $x = 1$ in system (5.8), we obtain, since $U_m(1) = 1 \forall m \ge 0$, the following useful relations

$$\left\{
\begin{aligned}
H_m(1, 0) &= p H_{m-1}(1, 0), \quad 1 \le m < M, \\
H_M(1, 0) &= \frac{p}{1-p} H_{M-1}(1, 0), \\
H_0(1, 0) &= (1-p)S(1).
\end{aligned}
\right.
\quad (5.13)$$

**Remark 5.3.** It is worth noting that the 3 equations of system (5.13) are not independent. Indeed, the third equation is a direct consequence of the two first ones.

The idea will be now to divide all equations in (5.12) by $R(x, 1)$, to let $x \to 1$, in order to apply the well-known L'Hôpital's rule and the normalizing condition (5.11).

Hence, by using the following intermediate identities easily inferred from definition (5.9),

$$U'_m(1) = \frac{W_m - 1}{2(1-r)} \varphi'(1) + \lambda T, \quad 0 \le m \le M,$$

we get

$$\left\{
\begin{aligned}
H_m(1, 1) &= p C_m H_{m-1}(1, 0), \quad 1 \le m < M, \\
H_M(1, 1) &= (1-p) C_M H_M(1, 0), \\
H_0(1, 1) &= C_0 H_0(1, 0),
\end{aligned}
\right.
\quad (5.14)$$
where $C_m, 0 \le m \le M$ was defined in Proposition 5.2, and in the last equation of (5.14) we have replaced $(1-p)S(1)$ by $H_0(1, 0)$.

Then, by summing all the equations of system (5.14), using (4.4) and (5.13), we obtain (5.10), and the proof is concluded.

■

## 6 Stability (ergodicity) condition

To ensure the ergodicity of the Markov chain $\{\tilde{X}_i\}$, it suffices to find a solution of system (5.8) analytic in the unit disk $\mathcal{D}$. With this in mind, we state the following lemma.

**Lemma 6.1.** We have

$$H_0(x, 0) = \frac{p(0)e^{\lambda T(1-x)}U_0(x)R(x, 1)}{T(x)}, \qquad (6.1)$$

with the $U_i, i \ge 0$, defined in (5.9) and

$$\left\{ \begin{array}{ll} F_m(x) & \stackrel{\text{def}}{=} \prod_{i=1}^{m} U_i(x), \quad \forall m \ge 1, \quad \text{and} \quad F_0(x) \stackrel{\text{def}}{=} 1, \\ T(x) & \stackrel{\text{def}}{=} (1-p)U_0(x) \left[ \sum_{m=0}^{M-1} p^m F_m(x) + \frac{p^M F_M(x)}{1-pU_M(x)} \right] - x. \end{array} \right.$$

*Proof.* The result is obtained by a simple algebra from system (5.8), using in particular the intermediate relationship

$$H_m(x, 0) = p^m F_m(x) H_0(x, 0), \quad 1 \le m < M. \qquad (6.2)$$

■

**Theorem 6.2.** The Markov chain $\{\tilde{X}_i\}$ is

* recurrent positive if $T'(1) < 0$,

* transient if $T'(1) \ge 0$,

where the function $T(\cdot)$ has been computed in Lemma 6.1.

*Proof.* From equation (6.2), we note straight away that the analyticity of $H_0(x, 0)$ in $\mathcal{D}$ yields immediately the analyticity of $H_m(x, 0)$, $m \ge 1$ in $\mathcal{D}$. Hence, the ergodicity of the system is equivalent to the analyticity of $H_0(x, 0)$ in $\mathcal{D}$.

To proceed further, we will employ the so-called Rouché's theorem, which we recall below for the sake of completeness.

**Theorem 6.3 (Rouché, see e.g. [7]).** For any two complex-valued functions $f$ and $g$ holomorphic inside some region $\mathcal{H}$ with simple closed contour $\partial\mathcal{H}$, if $|g(z)| < |f(z)|$ on $\partial\mathcal{H}$, then $f$ and $f + g$ have the same number of zeros inside $\mathcal{H}$, where each zero is counted with its multiplicity.

On the unit circle $\mathcal{C}$, when $|x| = 1, x \ne 1$, we have $|x| > |T(x) + x|$, since $|U_m(x)| < 1, \forall m$, and $T(1) = 0$.

(i) Assume $T'(1) < 0$. We construct a contour $\mathcal{C}_\varepsilon$ consisting essentially of the unit circle $\mathcal{C}$ continuously distorted around $x = 1$ by a small notch (say an arc of circle of radius $\varepsilon$ centered at 1), keeping the point 1 inside the domain $\mathcal{D}_\varepsilon$ bounded by $\mathcal{C}_\varepsilon$. Then, choosing $\varepsilon$ sufficiently small, we have

$$|x| > |T(x) + x|, \quad \forall x \in \mathcal{C}_\varepsilon.$$
Rouché's theorem says that the functions $x$ and $T(x)$ have the same number of zeros inside $D_\epsilon$, in this case exactly one. Hence, since $T(1) = 0$, $T(x)$ has no zero inside $D$. Consequently, when $T'(1) < 0$, the function $H_0(x, 0)$ is analytic in $D$ and the system is ergodic.

(ii) When $T'(1) > 0$, a quite similar argument shows that $T(x)$ has a zero inside the open disk $|x| < 1$.

(iii) In the special case $T'(1) = 0$, equation (6.1) implies that we must also have

$$ \frac{dR(x, 1)}{dx}\bigg|_{x=1} = \lambda[(1 - r)\sigma + rT] = 0, $$

which is impossible.

The proof of Theorem 6.4 is concluded.

<figure><img src="image_4.png" /></figure>

## 6.1 Explicit maximum arrival rate $\lambda$ for stability

We will show below that the ergodicity condition (6.2) can be expressed as a linear inequality in $\lambda$. Introduce the quantities

$$ a_i \stackrel{\text{def}}{=} \frac{W_i - 1}{2}, \quad i \ge 0, \quad \text{and} \quad A_m \stackrel{\text{def}}{=} \sum_{i=1}^{m} a_i. $$

Then after direct (albeit slightly painful!) calculations, we can write the following equality.

$$ T'(1) = \left[ (1-p) \sum_{m=1}^{M-1} p^m A_m + \frac{p^M(A_M - pA_{M-1})}{1-p} + a_0 \right] \varphi'(1) + \lambda T \left[ (1-p) \sum_{m=1}^{M-1} m p^m + M p^M + \frac{p^{M+1}}{1-p} + 1 \right] - 1. $$

From the definition (5.9), we have

$$ \varphi'(1) = \frac{\lambda[(1 - r)\sigma + rT]}{1 - r}, $$

and all these elements combined together lead directly to the following theorem, which is the twin of Theorem 6.2.

**Theorem 6.4.** For all finite $W_i$'s, the ego station is stable if $\lambda < \lambda_{Max}$, and unstable if $\lambda \ge \lambda_{Max}$, where

$$ \lambda_{Max} = \frac{1}{\frac{(1-r)\sigma + rT}{1-r} \left[ (1-p) \sum_{m=1}^{M-1} p^m A_m + \frac{p^M(A_M - pA_{M-1})}{1-p} + a_0 \right] + \frac{T}{1-p}}. \quad (6.3) $$

**Remark 6.5.** From a theoretical point of view, it is quite possible to let the number $M$ of backoff stages tend to $\infty$, by merely assuming the convergence of the power series in $p$ which appears in the denominator of (6.3).

## 7 About possible extensions to a network context

Theorem 6.3 gives a necessary and sufficient condition for one arbitrary ego station to be stable, when $p$ and $r$ are considered as exogenous parameters. However, in a network with $N$ identical stations, one can think of linking $p$ and $r$ to the behavior of an arbitrary station at steady state, as mentioned at the beginning of Section 2.
<figure><img src="image_5.png" /><figcaption>Fig. 7.1: Station throughput versus $\sigma$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 7.2: Station throughput versus $r$ for different backoff strategies.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 7.3: Station throughput versus $p$, for $\sigma = 0.1$ and $r = 0.5$.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 7.4: Network throughput versus $\sigma$, for $M = 2$ and $M = 5$, with $N = 20$ nodes.</figcaption></figure>
Let

$$ \tau \stackrel{\text{def}}{=} \sum_{m=0}^{M} \sum_{n=1}^{\infty} p(0, n, m), $$

so that $\tau$ is just the probability that, at the ego station, all backoff stages $m$ have a counter $k = 0$, and this probability can clearly be viewed as a transmission rate.

Then, a reasonable heuristic choice for $(p, r)$ could be as follows.

* $p = 1 - (1 - \tau)^{N-1}$, the probability of collision when at least two packets (sent by different stations) are simultaneously transmitted on the channel.

* $1 - (1 - \tau)^N$ is the probability that the channel is busy, whence $\mathbb{P}(B_i) = 1 - (1 - \tau)^N = r$.

* Hence, $1 - r = (1 - p)(1 - \tau)$.

In this context, preliminary numerical experiments show in fact that the stability condition seems also to depend on the existence of a solution to the fixed-point equation (either in $\tau$ or in $p$)

$$ H_0(1, 0) = (1 - p)S(1) = (1 - p)\tau = \frac{p(0)R_x'(1, 1)}{T'(1)} \quad (7.1) $$

derived in (5.13). This problem will be the subject of a future study.

The Figures 7.1, 7.2, 7.3 present the station throughput by using Theorem 6.3. Unless otherwise specified, we take $M = 5$, $W_i = 2^i W_0$ and $W_0 = 32$.

Figure 7.1 shows the variation of the maximum station throughput versus $\sigma$. Here $\sigma$ can be seen as the measurement of the protocol overhead, i.e. the backoff. Thus we plainly understand that the increase of $\sigma$ leads a decrease in the station throughput. Since $r$ and $p$ are exogenous parameters, the decrease of $W_0$ leads to an increase in the throughput.

Figure 7.2 shows the variation of the maximum station throughput versus $r$. Since $r$ measures the channel occupancy, it is quite normal that when $r$ increases the station throughput decreases. Moreover, since $r$ and $p$ are exogenous parameters, the throughput is a decreasing function both of $W_0$ and of the number $M$ of backoff stages.

Figure 7.3 shows the variation of the maximum station throughput as a function of $\sigma$, for different fixed values of $p$. We can understand that the station throughput is a decreasing function of $p$.

The final Figure 7.4 depicts the network throughput, by making use of the formulas for $r$, $p$ and $H_0(1, 0)$ given at the beginning of this Section. The maximum station throughput is now the value $\lambda_s$ for which the equation (7.1) has a solution, from which it follows that the total throughput is $\lambda_s N$ (here $N = 20$). Unlike the station throughput result with $p$ and $r$ exogenous, in the network context $p$ and $r$ are functions of the network parameters. For instance, we observe that increasing $M$ can be beneficial for network throughput, in contrast to the results obtained for the isolated ego station.

## Acknowledgments

The authors would like to thank Christine Fricker (Inria-Paris Research Center) for several interesting discussions, and the anonymous referees for their comments and suggestions.

## References

[1] G. BIANCHI, Performance Analysis of the IEEE 802.11 Distributed Coordination Function. IEEE Journal of Selected Areas in Communications., 18 (2000), pp. 535–547.

[2] R. COGBURN, Markov chains in random environments: the case of markovian environments. The Annals of Probability, 8(5):908–916, 1980.

[3] R. COGBURN. The ergodic theory of markov chains in random environments. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 66(1):109–128, 1984.
[4] G. FAYOLLE AND P. MÜHLETHALER. *A Markovian Analysis of IEEE 802.11 Broadcast Transmission Networks with Buffering*. Probability in the Engineering and Informational Sciences, 30(3):19, June 2016.

[5] W. FELLER. *An introduction to probability theory and its applications, Vol. II.*, Second edition. John Wiley & Sons Inc., New York, 1971.

[6] S. FOSS, S. SHNEER, AND A. TYURLIKOV. *Stability of a Markov-modulated markov chain, with application to a wireless network governed by two protocols*. Stochastic Systems, 2(1):208–231, 2012.

[7] E. C. TITCHMARSH, *The Theory of Functions*, Oxford University Press, 2nd ed., 1939.