IEEE 802.11 Latency Modeling with Non-IEEE 802.11 Interfering Source

Abstract

IEEE 802.11 network deployments are ubiquitous and provide connectivity to millions of users. Interference that originates from other technologies, like simple Radio Frequency (RF) equipment, severely degrades the performance of those networks. To effectively manage wireless networks, the interference needs to be modeled and predicted. The current state of the art models are insufficient to model performance correctly. In this letter, we describe the interference as an interrupted Poisson process and use a decomposition approach to predict the latency of an interfered client from the latency of a non-interfered client. This novel approach allows for fast and easy prediction of latency in an interfered network. The results show that our method gets as close as 6% of the real value.

1 Introduction

Since the beginning of IEEE 802.11 networks, interference from overlapping networks degrades the performance, especially in large and dense deployments [3, 10]. The main reason for this degradation is the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) Listen-Before-Talk (LBT) protocol of IEEE 802.11. It uses Carrier Sense (CS) and Energy Detection (ED) to detect whether the channel is busy and defers from sending when it is. A failed attempt results in an increased random back-off and in the end to a dropped packet. With recent technologies, the spectrum of IEEE 802.11 becomes severely crowded, which has an impact on the performance, especially when they do not adhere to an LBT protocol. Many daily appliances with RF capabilities like baby phones, television screens, or microphones, can have an impact [5, 11, 14]. The more such appliances are employed, for example at a concert, the more impact they have. However, also Long-Term Evolution (LTE) in the unlicensed band can lead to up to 98% throughput loss if no LBT protocol is employed [1, 6]. This severe performance degradation makes network management increasingly difficult and a solution to predict latency depending on the interference is needed.

Several studies analyzed the latency of IEEE 802.11 networks. Initially, the focus was throughput, but soon it became broader and included latency, jitter, packet loss, and error-prone channels as well [2, 7, 8, 13]. The main component of all of these works is the Markov chain to model the IEEE 802.11 back-off mechanism. While this allows for an accurate representation thereof, it also makes computation slow as it is needed to solve it numerically. These works all lack to assess the impact of non-IEEE 802.11 interference though, which can have a significant impact [4]. The base performance, however, or the one obtained from a real setup without interference, can be used to calculate the performance when interference is present.

In this article, we propose a fast and accurate analytical model that can predict the latency with an interfering source present from latency when no interfering source is present. We use an interrupted Poisson process as a model for the interfering source. Taking into account three characteristics of the IEEE Medium Access Control (MAC), we can accurately describe the latency in such a system. Our measurement results show that the latency we observe correlates with the latency of our prediction. This is especially useful when deploying wireless networks in challenging environments like large concerts or conferences.

2 Characterizing an Interfering Source

To correctly model the interfering source, we take an on/off process with exponentially distributed on and off periods as a basis. The interruptions of the medium access by the interfering source, which generates energy above the ED threshold, occurs according to a Poisson process with rate $\nu$. Different sources can be modeled in this form, for example, a microwave oven or baby phone [12]. We assume that during an ongoing interruption no new interruptions occur. The variable u denotes the random variable representing the length of the interruptions. We assume that u is exponentially distributed with mean E[u]. With the Poisson assumption in mind, the average time that the interfering source is inactive is given by $\frac{1}{\nu }$. In contrast, the fraction of the time the interfering source is active is given by:

$$\begin{aligned} p_a = \frac{E[u]}{E[u]+\frac{1}{\nu }} \end{aligned}$$

(1)

3 Modeling Latency

3.1 Description of the Latency Components

An interfering source has three major effects on the operation of the IEEE 802.11 MAC protocol.

The first is based on the ED function of an IEEE 802.11 station which senses for energy on the channel before it tries to send a packet. When the interfering source becomes active, the station detects energy on the channel and defers from transmitting a packet for E[u] seconds on average.

Next, when the interfering source becomes active at the time a packet is being transmitted, the packet collides with the signal of the interfering source and is lost. Not only a re-transmission of the packet is the result, but it also adds additional latency in the form of a doubled contention window for the next back-off phase.

Third, stations with a packet at the head of the queue during the time the interfering source is active will sense the medium busy. As soon as the interfering source stops transmitting, the stations will enter in a back-off phase. If a station is in the back-off phase during the activity of the interfering source, it has to stop the process and needs to wait until the medium is considered free again.

3.2 Computing Average Latency in a System with Interference

We will first take the unavailability of the medium and the increased CW into account. Consider an IEEE 802.11 network with N stations, which are equally loaded. We model a station as a finite capacity single server queue with Poisson input with rate $\lambda$ where the service time equals the sum of the IEEE 802.11 access latency and the transmission time itself. We will model the activity of the interfering source as service interrupts. Computing the latency in this M/M/1/K queue with service interruptions will result in the average packet latency of a station.

For a random variable d, we denote D(t) its cumulative distribution, respectively $D^{*}(s)$ its Laplace-Stieltjes Transform (LST). E[d] denotes its mean value. The service time of a packet consists of two major parts, access latency and the transmission time of the packet itself. The service time is denoted by $b_{ni}$, respectively $b_{wi}$, in the system without interference, respectively the system with interference. Let b denote the transmission time of a packet. We make the additional assumption that both $b_{ni}$ and $b_{wi}$ are exponentially distributed. This turns the model of a station in a system with and without interference into an M/M/1/K queue. Let $d_{ni}$ and $d_{wi}$ be the packet latency respectively in the system without interference and in the system with interference.

First, we derive a formula for the LST of the service time in a system with interference $B^{*}_{wi}(s)$, as a function of the LST of the packet latency in a system without interference $B^{*}_{ni}(s)$. We follow reasoning similar to the one by Fiems et al., where the service interruptions are the active periods of the interfering source [9]. We consider three cases, depending on the start of the first time the interfering source becomes active after a packet starts its service in relation to the different components of this service time.

First case: the interfering source does not become active during the service time. In this case, the service time in the system with interference is the same as the service time in a system without interference.

Second case: the interfering source becomes active during the access latency of a packet. In this case, the time the interfering source is active needs to be added to the service time in a system without interference.

Third case: the interfering source becomes active during the transmission time of a packet. In this case, not only the time the interfering source is active needs to be added to the service time, but also an additional time since the MAC protocol reacts on this interrupt of the transmission by doubling the contention window. Let a be the random variable representing the additional access latency of a packet whose transmission was interrupted by the interfering source. Note that this case includes the added latency of the paused back-off mechanism when a packet is at the head of the queue.

Assume that the service time in the system without interference is given by x.

• 1. No interrupt by the interfering source occurs during the service time, which happens with probability $e^{-\nu x}$. In this case

  $$\begin{aligned} B^{*}_{wi}(s|x) = e^{-(\nu +s)x} \end{aligned}$$

  (2)

  where $B^{*}_{wi}(s|x)$ denotes the LST of $b_{wi}$, given that the service time in the system without interference is x.

• 2. An interrupt by the interfering source occurs during the access latency (i.e., during $[0,x-b[$). This happens with probability $1 - e^{-\nu (x-b)}$. In this case

  $$\begin{aligned} B^{*}_{wi}(s|x) = \frac{\nu }{\nu + s} \cdot V^{*}(s) \cdot B^{*}_{wi}(s) \cdot (1 - e^{-(\nu + s)(x - b)}) \end{aligned}$$

  (3)

• 3. An interrupt by the interfering source occurs during the transmission time (i.e., during $[x - b,x[$). This happens with probability $e^{-\nu (x - b)} - e^{-\nu b}$. In this case

  $$\begin{aligned} B^{*}_{wi}(s|x) = \frac{\nu }{\nu + s} \cdot V^{*}(s) \cdot A^{*}(s) \cdot B^{*}_{wi}(s) \cdot (e^{-(\nu +s)(x-b)} - e^{-(\nu +s)x}) \end{aligned}$$

  (4)

Combining the three cases, we obtain

$$\begin{aligned} \begin{aligned} B^{*}_{wi}(s|x) = e^{-(\nu +s)x} + \frac{\nu }{\nu + s} \cdot V^{*}(s) \cdot B^{*}_{wi}(s) \cdot (1 - e^{-(\nu + s)(x - b)}) \\ + \frac{\nu }{\nu + s} \cdot V^{*}(s) \cdot A^{*}(s) \cdot B^{*}_{wi}(s) \cdot (e^{-(\nu +s)(x-b)} - e^{-(\nu +s)x}) \end{aligned} \end{aligned}$$

(5)

Integrating over all possible service times x leads to

$$\begin{aligned} B^{*}_{wi}(s)= & {} B^{*}_{ni}(\nu +s)\! +\! \frac{\nu }{\nu +s} \cdot V^{*}(s) \cdot B^{*}_{wi}(s) \cdot (1\! -\! e^{(\nu +s)b} \cdot B^{*}_{ni}(\nu +s))\nonumber \\&+ \frac{\nu }{\nu +s} \cdot V^{*}(s) \cdot A^{*}(s) \cdot B^{*}_{wi}(s) \cdot (e^{(\nu +s)b} \cdot B^{*}_{ni}(\nu +s)-B^{*}_{ni}(\nu +s)) \end{aligned}$$

(6)

Since

$$\begin{aligned} E[b_{wi}] = -\frac{d\cdot B^{*}_{wi}(s)}{ds} |_{s= 0} \end{aligned}$$

(7)

we obtain that

$$\begin{aligned} E[b_{wi}] = \frac{1}{\nu \cdot B^{*}_{ni}(\nu )} \cdot (1 - B^{*}_{ni}(\nu )) \cdot (1 + \nu \cdot E[v]) + E[a] \cdot (e^{\nu b} - 1) \end{aligned}$$

(8)

Given the assumption that $b_{ni}$ is exponentially distributed, we obtain

$$\begin{aligned} E[b_{wi}] = E[b_{ni}] \cdot (1 + \nu \cdot E[v]) + E[a] \cdot (e^{\nu b } - 1) \end{aligned}$$

(9)

Let us compute E[a]. The probability that the interfering source becomes active while a packet is being transmitted is given by

$$\begin{aligned} \int _{0}^{b} \nu e^{-\nu b} dt = 1 - e^{-\nu b} \end{aligned}$$

(10)

with b being the time needed to transmit a packet.

Hence, the probability that the interfering source becomes active during each of the consecutive i re-transmissions of a packet and not during the $(i+1)$^th is given by

$$\begin{aligned} (1-e^{-\nu b})^{i} \cdot e^{-\nu b} \end{aligned}$$

(11)

Assuming $CW_{min} = 63$, $CW_{max} = 1023$ and for the 5^th and 6^th re-transmission $CW = 1023$, the value of E[a] is given by

$$\begin{aligned} E[a] = \sum _{i=1}^{5} 2^{4+i} \cdot (1-e^{-\nu b})^{i} \cdot e^{-\nu b} + 2^{9} \cdot [1 - \sum _{i=0}^{5}(1-e^{-\nu b})^{i} \cdot e^{-\nu b}] \end{aligned}$$

(12)

To take the increased latency of the paused back-off mechanism into account when the packet is at the head of the queue we consider the behavior of stations when the interfering source becomes active similar to their behavior when other stations transmit packets. Therefore, we express the activity of the interference source in terms of packet transmissions. The fraction of the time the interference source is active is given by $p_{a}$. Let $n_{if}$ be the number of packets per second that could be sent during an active period of the interference source. Then

$$\begin{aligned} n_{if} = \frac{p_{a}}{b+c} \end{aligned}$$

(13)

with c being the transmission time of an acknowledgment. For the latency computation with interference, the packet arrival rate is given by

$$\begin{aligned} \lambda _{a} = \lambda +\frac{n_{if}}{N} \end{aligned}$$

(14)

and will be used to derive the performance measures for the system with interference.

To compute the average packet latency in a system with interference $E[d_{wi}]$, given the average packet latency in the system without interference $E[d_{ni}]$, using the relationship between $E[b_{wi}]$ and $E[b_{ni}]$ as established above, assume that the number of stations N and the packet arrival rate $\lambda$ are given. Let K be the length of the MAC queue in a station. The random variables $l_{ni}$ and $l_{wi}$ denote the number of packets in a station without and with interference. Let

$$\begin{aligned} \rho _{ni} = \lambda \cdot E[b_{ni}] \end{aligned}$$

(15)

respectively,

$$\begin{aligned} \rho _{wi} = \lambda _{a} \cdot E[b_{wi}] \end{aligned}$$

(16)

be the load of a station without, respectively, with interference. Assume that we know the average latency $E[d_{ni}]$ of a packet in a system without interference and that a station in the system without interference is modeled as an M/M/1/K queue. Given Little’s law, the average number of packets in the station is given by

$$\begin{aligned} E[l_{ni}] = \lambda _{eff_{ni}} \cdot E[d_{ni}] \end{aligned}$$

(17)

where

$$\begin{aligned} \lambda _{eff_{ni}} = \lambda _{a} \cdot (1 - \frac{1 - \rho _{ni}}{1 - \rho _{ni}^{K+1}} \cdot \rho _{ni}^{K}) \end{aligned}$$

(18)

is the effective packet arrival rate in the system without interference.

Then, the average number of packets, $E[l_{ni}]$, is also given by the formula

$$\begin{aligned} E[l_{ni}] = \rho _{ni} \cdot \frac{1 - (K + 1) \cdot \rho _{ni}^{K} + K \cdot \rho _{ni}^{K+1}}{(1 - \rho _{ni}) \cdot (1 - \rho _{ni}^{K+1})} \end{aligned}$$

(19)

From Eqs. 17 and 19 we derive the value of $\rho _{ni}$. This leads to

$$\begin{aligned} E[b_{ni}] = \frac{\rho _{ni}}{\lambda _{a}} \end{aligned}$$

(20)

Now it is possible to compute $E[b_{wi}]$ using Eq. 9. Once $E[b_{wi}]$ is known, it is possible to compute

$$\begin{aligned} \rho _{wi} = \lambda \cdot E[b_{wi}]. \end{aligned}$$

(21)

Using Eq. 19 for the system with interference, we derive $E[l_{wi}]$ and applying Little’s formula leads to the average latency in a system with interference

$$\begin{aligned} E[d_{wi}] = \frac{E[l_{wi}]}{\lambda _{eff_{wi}}} \end{aligned}$$

(22)

with

$$\begin{aligned} \lambda _{eff_{wi}} = \lambda \cdot (1 - \frac{1 - \rho _{wi}}{1 - \rho _{wi}^{K+1}} \cdot \rho _{wi}^{K}) \end{aligned}$$

(23)

4 Results

4.1 Experimental Setup

For our experimental study, the w-ilab.t¹ lab facility, a large-scale emulation platform with wireless nodes allowing extensive experiments, has been used. Configurations of 15, 20, and 25 stations on the 5 GHz band with IEEE 802.11a were used. All stations are connected to a single access point (AP), and a test includes transmitting packets for 60 s with a repetition of 5 times for each configuration. To generate interference according to the previously defined model in Sect. 2, we installed a Software Defined Radio (SDR).

Two modes of interference occurrence were used in the experiment: low occurrence with $\frac{1}{\nu }$ equal to $9 \cdot 10^{-4}$ s and high occurrence with $\frac{1}{\nu }$ equal to $1.8 \cdot 10^{-4}$ s. The duration of interference E[u] was set to three different modes: low ($9\cdot 10^{-5}$ s), medium ($4.5 \cdot 10^{-4}$ s), and high ($9 \cdot 10^{-4}$ s). The packets have a size of 1500 bytes and are sent at a fixed bit rate of 54 Mbps. The sending rate of packets per second had a minimum of 25 and a maximum of 200 packets per second with an interval of 25 packets per second. A continuous packet source was used to generate packets on the MAC layer according to a Poisson process. The queue length is given by $K=64$.

4.2 Validation

Fig. 1.

Latency with interference $1/\nu = 9 \cdot 10^{-4}$ with 15 stations.

Fig. 2.

Latency with interference $1/\nu = 9 \cdot 10^{-4}$ with 20 stations.

Fig. 3.

Latency with interference $1/\nu = 9 \cdot 10^{-4}$ with 25 stations.

Fig. 4.

Latency with interference $1/\nu = 1.8 \cdot 10^{-4}\,\mathrm{s}$ with 15 stations.

Fig. 5.

Latency with interference $1/\nu = 1.8 \cdot 10^{-4}\,\mathrm{s}$ with 20 stations.

Fig. 6.

Latency with interference $1/\nu = 1.8 \cdot 10^{-4}\,\mathrm{s}$ with 25 stations.

There are two significant elements to assess the accuracy of the model, the saturation point and the maximum average latency when the system is saturated. Saturation is the state when the maximum capacity of the wireless network is reached and depends on the number of stations, the number of packets per station, and the characteristics of the interfering source. Note that, as we only have measurement results with steps of 25 packets per second, interpolation was used when applying Eq. 17.

Low Occurrence. Figures 1, 2, and 3 present the graphs for 15, 20, and 25 stations and $1/\nu = 9 \cdot 10^{-4}$ s. In 8 out of 9 cases the saturation point is accurately matched. Only in the case of 15 stations and with the shortest duration was the saturation point predicted too early. The latency prediction at saturation is within 6–7% of the average latency, while a higher number of stations leads to higher accuracy.

High Occurrence. Figures 4, 5, and 6 show similar results for $1/\nu = 4.5 \cdot 10^{-4}$ s. The saturation point is accurately matched in 8 out of 9 cases, again except for 15 stations and the shortest duration, and the accuracy of the latency at saturation is within 13–50%. The high duration is an outlier with any number of station. The airtime usage of the interfering source amounts to 83% of the available airtime. The difficulty of prediction stems from the low amount of successful packets, as can be seen by the confidence interval.

The results show that the accuracy is high and that our proposed method can be used in further network management.

5 Conclusion

In this article, we developed an analytical model that allows predicting the average latency a station of an IEEE 802.11 network experiences in the presence of an interfering source assuming that the latency without interference is known. Three characteristics drive this model: the time the medium is busy during the activity of the interfering source, the interruption and increased CW of a station, and the additional latency of a station that has a packet ready to transmit when the source becomes active. We demonstrated the accuracy of our model using real-life measurements. The accuracy of the model increases with the number of stations, which is especially crucial for dense deployments.