Abstract
Probably no protocol has been analysed as much as the various versions of the IEEE 802.11 Distributed Coordination Function (DCF). In this paper, we show how to describe a typical DCF analytic model as a semi-Markov process (SMP) by taking a new approach to performance modelling, called Traffic-Centric Modelling (TCM). TCM is therefore explained at the hand of an example IEEE 802.11 network in Basic Access mode under both saturated and unsaturated traffic conditions. We show how to solve the corresponding SMP by executing DCF activity over the SMP structure, making the proposed solution a hybrid analytical-simulation method. The accuracy of the technique is illustrated by comparing the results with that from the analytic model that is most frequently cited in the research literature.
Keywords: Traffic-Centric Modelling; Analytical and Numerical Simulation; Semi-Markov process; Performance Modelling; WLAN.
Introduction
System hardware and operating software typically constitute the core of the performance model. It is not surprising then that performance models are far too often developed with the workload as an afterthought. A new perspective, called Traffic-Centric Modelling (TCM), where the perspective is from the quality of service (QoS) experienced in the system by the individual traffic units (t-units) constituting the workload, is advocated herein.
Since the IEEE 802.11 Distributed Coordination Function (DCF) has been analysed in countless papers, an IEEE 802.11 DCF example system is modelled using the TCM approach. Evidently the most-cited paper1 in the literature of DCF modelling is that by Bianchi [1]. A reading of the 6 most-cited papers by Ziouva and Antonakopoulos [2], Zheng et al. [3], Dong and Varaiya [4], Ni et al. [5] and Daneshgaran et al. [6] reveals that the models in all of these papers are based upon a Markov chain (MC) that is some derivation of the original model by Bianchi.
In this paper, we show that the models mentioned above, and others, can be viewed as an instance of a much more general semi-Markov process (SMP) due to the modelling approach taken. More significantly even, the solutions of the earlier MC models invariably involve a complicated stochastic analysis with non-trivial mathematical formulation. We present an SMP model on the analysis of an example IEEE 802.11 DCF network and an efficient algorithmic solution of the model.
It is not the objective of this paper to present another DCF model but rather to show how previous MC-based analytic models can be re-interpreted as SMPs, thus allowing a much broader and more general perspective on the modelling of versions of the IEEE 802.11 standard, workloads and channel conditions. Also, due to its generality, this perspective may prove useful in wireless network configurability, flexibility and programmability studies.
In the next section, we briefly outline the basic principles that TCM stems from and then, in Sect. 3, we describe the behaviour of the example network we have chosen to illustrate the TCM methodology. The SMP description of the example network is developed in Sect. 4, where after, in Sect. 5, we derive the basic normalised network throughput for our example network. An algorithmic solution of the SMP of the network is given in Sect. 6. Such an algorithm can be written for the solution of any SMP of a system in a stable state, which is what all MC models assume. In Sect. 7, we compare the SMP results with those of the original Markov model presented by Bianchi. Moreover, we show that it is straightforward to account for unsaturated traffic conditions by presenting results for 2 unsaturated traffic intensities.
Traffic-Centric Modelling
Any system performance model needs to consider the traffic in the system as well as a model of the machine, i.e., the associated hardware, software structures and protocols. Workload modelling is hard though because events change indeterminately and frequently but at a rate orders of magnitude different from that of events in the machine model (MM). Because it is somewhat intangible, the workload model (WLM) is frequently specific to the particular MM. This does not make the performance model very useful should the workload composition or its nature change. The authors are advocating an approach whereby we define, as a modelling artefact, an entity called a traffic unit (t-unit) that carries with it not only attributes of the physical data (HTML, MPEG4, etc.) but attributes describing its quality-of-service (QoS) and the quality-of-experience (QoE) of the connection as experienced by itself and earlier t-units. We call this approach Traffic-Centric Modelling (TCM).
TCM is an approach to system modelling where the system model requires a WLM and an MM, as before. As shown in Fig. 1, what distinguishes TCM from other modelling techniques is that it shifts the focus of the performance modelling exercise from that which serves to that which requires service. Traditionally, the WLM and MM are joined by a traffic generation interface (MM-WLM interface in Fig. 1) with no opportunity for QoE feedback; the optional feedback mechanism would be implemented separately, directly feeding from the MM into the WLM, noting that the event-time resolutions of the workload and machine operations would have to be managed on the same time-line. Differently, TCM connects the WLM and MM by making the t-unit the core model component that is affected independently and directly by both, as shown in Fig. 1. The QoE feedback is applied directly to the t-unit.
Fig. 1. Comparison between Traffic-Centric and other more traditional systems modelling approaches
To prove the feasibility of what we propose, we consider an IEEE 802.11 MPDU, i.e., a data frame, as the t-unit. The frame is described by its attributes, such as its packet length in bits, and by its behaviour, such as being received successfully at the destination, colliding with one or more transmissions from other nodes in the system, and so on. The t-unit experience some actions in the system and various performance metrics can be determined from these experiences.
System Behaviour
We describe an IEEE 802.11 system operating under unsaturated traffic conditions to illustrate the proposed methodology. As is usually the case, we make the assumption that the system is a fully-connected point-to-multipoint IEEE 802.11 network of homogeneous nodes. Each node n, of a total of N nodes, transmits data frames to a central access point (AP) according to the Basic Access (BA) mode of the DCF access mechanism.
As is often done [7,8,9,10], we describe the system behaviour from the perspective of an observer node, denoted n, which may be any one of the N nodes in the network. The behaviour of a particular node includes the behaviour actions that the frame can experience.
We define the state of a node (and thus of the SMP, see Sect. 4.2), as the number of successive transmissions of the same frame. An observation point is set at the instant when a change of state, possibly a return to the same state, occurs.
At each observation point 1, 2,…, the observer records whether the channel was idle or busy during the previous observation period. As shown in Fig. 2, the wireless channel is thus considered to be alternating between consecutive, interleaved idle and busy periods, corresponding to the collective behaviour of the N nodes. A frame is transmitted, either successfully or not, during a busy period. Failure would result if 2 or more nodes transmit simultaneously, referred to as a collision. In order not to complicate the SMP, we do not take failure as a result of an error on the wireless channel into consideration, although such an extension is straightforward.
Fig. 2. An instance of the channel alternating between idle and busy periods as one or more nodes transmit data
The DCF dictates that an individual node, ready to transmit a frame, first monitors the channel for a Distributed Interframe Space (DIFS) period, TDIFS. If the node has a frame to transmit, the node decrements the back-off counter for a random number of slots. If the node has no frames to transmit, it remains idle for an empty time period.
The duration of the back-off period, BoVn, is picked uniformly from an integer-valued interval called the contention window. The length of the contention window begins at CWmin and doubles in length after every failed transmission, up to a maximum length CWmax. This specific action attempts to avoid collisions, since other nodes may have been monitoring the channel for the same purpose.
If the channel is sensed busy during back-off, the back-off counter suspends and is reactivated after a successful transmission and after the channel has been sensed idle for a further DIFS period. When the back-off counter reaches zero, the node transmits the frame. If two or more nodes transmit simultaneously, a collision occurs. To resolve a collision, all nodes involved in the collision reset their back-off counters and restart back-off immediately. Counters of the other non-colliding nodes in the neighbourhood suspend transmission for a period TEIFS called the Extended Interframe Space (EIFS). Thus, colliding nodes have a greater probability of medium access for this post-collision period.
All frames are acknowledged within a Short Interframe Space (SIFS) period TSIFS. If the sender does not receive an acknowledgment within the required time, it either reschedules transmission or drops the frame, depending on its retransmission (retry) count. The microsecond values for the slot duration a and the Interframe Spaces are determined by the modulation scheme employed in the Physical Layer (PHY).
DCF Behaviour as a Semi-Markov Process
Although the following material about SMPs can be found in several textbooks (e.g., Bause [11]), we believe that a short introduction is useful for those readers not already familiar with the theory.
General Semi-Markov Theory
An SMP can be thought of as a process whose successive state occupancies are governed by the transition probabilities of a Markov process that spends time (the holding or sojourn time) in any state described by an integer-valued random variable that depends on the state currently occupied and on the state to which the next transition will be made. The state variable in our case is the number of consecutive transmissions of the same frame at any one node.
At the transition instants (the observation points described in Sect. 3), the SMP behaves just like a Markov process. We call this process the embedded Markov process and denote the single-step state transition probabilities by Pij, i,j = 0,1,…,R. For simplicity, we assume that the process has a finite state space of size R that is in fact the maximum number of collisions allowed for any one frame. We also define Tij as the sojourn time in state i before the transition to the next state j.
The sojourn times with expected value t[j are positive, integer-valued random variables (with unit time a, the IEEE 802.11 slot time), each governed by a probability mass function si (m), m = 0,1,..., called the sojourn time mass function for a transition from state i to state j. That is,
In other words, to fully describe a discrete-time SMP, we must specify R2 holding time mass functions, in addition to the single-step transition probabilities.
We next define the waiting time Ti with expected value Ti as the time spent in state i, i = 0,1,...,R, irrespective of the successor state and we define the probability mass function of this waiting time as
and
That is, the probability that the system will spend m time units in state i if we do not know its successor state, is the sum for all possible successor states j of the probability that it will spend m time units in state i, provided its successor state is j, multiplied by the probability that its successor state will indeed be j.
Finally, let vector p = (^0, ,..., 4*r) denote the steady-state probabilities of the SMP in state r and let n = {n0,n1,...,nR} be the steady-state probability vector of the equivalent embedded MC.
One can show (e.g., Howard [12]) that
or
where we have written
and M is the diagonal matrix [rr] of mean waiting times.
Intuitively, the probability of finding the SMP in state r is the product of the average waiting time ~r in that state, multiplied by the probability 7rr of being in that state in the embedded MC and normalised by the steady-state mean time spent in a visit to a state r.
In Sect. 5, we show that the values of ~r,(f>r and the transition probabilities are sufficient to derive common performance metrics for IEEE 802.11 networks.
SMP Model for the Example Network
Assuming homogeneous node behaviour and a perfect channel, the number of possible events in the network and the resultant states and state changes are the same for each node. Figure 3 illustrates the SMP corresponding to the system behaviour, described in Sect. 3. In the figure, the state variable r, r = 0,1,…,R, represents the number of transmissions of the same frame at a particular node, where R G N+ is the installation specific retry-limit, i.e., the maximum number of consecutive frame retransmissions allowed, after which the frame is discarded, i.e., dropped. When in state R, the system will revert to state 0 in the case of either a failure or success of the last transmission.
While in state r, node n can experience the events and resultant transitions listed in Table 1. These transition definitions are similar to the definition of slot states by Malone et al. [13]. Different from those authors, we do not define an explicit idle state, rather the idle time is included in the sojourn time of a state.
Fig. 3. Semi-Markov chain for a typical node
Table 1. State transition descriptions
|
Transition |
Description |
 |
The probability that the current frame at node n is transmitted successfully, in which case the number of collisions returns to 0. |
 |
The probability that the transmitted frame at n is involved in a collision, in which case node n must back-off by an adjusted random time and the number of transmissions increases by 1. |
 |
The probability that the back-off process at node n is suspended due to a successful transmission by another node. |
 |
The probability that the back-off process at node n is suspended due to a collision at nodes other than itself. |
 |
The probability that there was no frame to send by the node during an observation interval while another node transmitted successfully. |
 |
The probability that there was no frame to send by the node during an observation interval while two or more nodes suffered a collision. |
 |
The probability that a frame at node n suffers a collision in state R, i.e., the drop probability. |
Calculating Common Performance Metrics
It is important to be reminded that IEEE 802.11 performance can be viewed from the perspective of a single node (sometimes referred to as a "de-coupled" node), or from the perspective of the transmission medium experiencing the collective behaviour of all nodes on the network. To be specific, we refer to a user performance metric and a channel performance metric, respectively, in the sequel.
The most popular performance metric of a node in IEEE 802.11 DCF is the normalised throughput defined as the amount of useful data transmitted divided by the capacity of the medium. Referring to Fig. 3, this normalised mean throughput, denoted ijjn of a single user n, is given by the probability of the SMP being in a state r, r = 0,…,R, returning to state 0 after a successful transmission of the mean time to transmit the payload information £r, all as a ratio of the mean sojourn time 7> in that state:
The normalised mean throughput ip of the whole network of N nodes, each with the same behaviour, is then given by
Another metric is the mean network (or channel) efficiency v. That is, the percentage of time the channel is being used productively. From the SMP model in Fig. 3 and Table 1, we have
As is the intention of the paper, the metrics mentioned are not intended to be an exhaustive list but rather as typical examples of those that can be computed using the estimates obtained through the SMP and parameters of the model that can be computed, as we shall show in the following section.
Steady-State Analysis of the SMP
In order to compute the metrics mentioned in the previous section, we need to determine the values of the basic variables pij and t[J \/i,j = 0,…, R. The probability mass functions sij (m) of Eq. 2 are not known but we can determine the values of empirically. Algorithm 1 is used to do this, assuring that the system reaches steady-state. In other words, the algorithm is executed until it converges and then the appropriate pij and Tj~j estimates are computed as shown in Table 2. The execution of Algorithm 1 constitutes the simulation-component of the hybrid model proposed.
The algorithm requires that one nominates a node to act as the wireless channel observer, called the reference node. Lines 16, 21, 36, 40, 56 and 58 show where the convergence estimates are recorded for the reference node. pi,j values, as defined in Table 1, are recorded with their corresponding Ti,j values.
Lines 7 through 9 determine after how many slots the next transmission will occur and which nodes get to transmit next. Referring to Fig. 2 and Table 1, depending on the transition, the idle time is made up of one or more of the empty time (ET), DIFS, EIFS and the back-off time (annotated as BoV).
The number of slots required to transmit during the next busy period tbusy is shown to be computed at line 10. Depending on whether the transmission was a success or not, tbusy takes on one of two values. These values are different for either BA and RTS/CTS modes.
Algorithm 1. Algorithm to derive values for the SMP parameters
At line 29, a new BoV is generated for a node that transmitted, whether successful or not. However, at line 33, the BoV is only updated to the difference between the amount of time it would have waited to transmit and the amount of time passed before another node transmitted during the observation period.
Corresponding to the system description, given in Sect. 3, the ET variable is introduced as an extension to account for non-saturated workload scenarios. It represents the period that a node is expected to have no data in its buffer since its last transmission. A new ET is generated for a node at lines 18 and 24, which is the case when the node enters state 0, i.e., a frame was transmitted successfully or dropped. The node is thus also reverted at these lines to state 0. In lines 43 through 47 and lines 49 through 53, ET is updated by the time elapsed since the last observation point, which includes tbusy.
When the node is in state R and it is involved in a collision, the probability of a node dropping a frame is recorded in the same way as for any other collision.
In order to verify that the values of the respective computed metrics converge, we computed the auxiliary variables defined below. The results shown in Table 2 are for a network operating in BA mode with an arbitrary number
N = 10 contending nodes and where infinite retries are allowed, i.e.
First, we write
as the normalised mean throughput observed after each of i consecutive iterations of 106 steps of the algorithm, with i = 1,…,20. Furthermore,
Next we form the cumulative sum
The values for these variables for i, i = 1,…, 20, derived from executing the algorithm for 20 x 106 cycles, are shown in Table 2.
Note that, in particular the cumulative sum of the relative difference in successive values of ^(i), remains almost constant after i = 9. Since it is a numerical computation, one expects the final value to fluctuate around some steady state value as is indicated in the table. The computations were done on a 2.5GHz Intel I5 processor and takes less than 10 seconds to converge to the values shown. The Java code of the algorithm, comprising just over 450 lines of code, is available from the authors.
Table 2. Results showing consecutive iterations through Algorithm 1
|
Iteration i |
|
m |
CM |
CM |
|
1 |
0.83573307 |
- |
- |
- |
|
2 |
0.835337667 |
4.73E-04 |
4.73E-04 |
- |
|
3 |
0.835479861 |
-1.70E-04 |
3.03E-04 |
1.70E-04 |
|
4 |
0.835579425 |
-1.19E-04 |
1.84E-04 |
1.19E-04 |
|
5 |
0.835498504 |
9.68E-05 |
2.81E-04 |
-9.68E-05 |
|
6 |
0.835476546 |
2.63E-05 |
3.07E-04 |
-2.63E-05 |
|
7 |
0.835479476 |
-3.51E-06 |
3.03E-04 |
3.51E-06 |
|
8 |
0.835469503 |
1.19E-05 |
3.15E-04 |
-1.19E-05 |
|
9 |
0.835390717 |
9.43E-05 |
4.10E-04 |
-9.43E-05 |
|
10 |
0.835337454 |
6.38E-05 |
4.73E-04 |
-6.38E-05 |
|
11 |
0.835351775 |
-1.71E-05 |
4.56E-04 |
1.71E-05 |
|
12 |
0.835379917 |
-3.37E-05 |
4.23E-04 |
3.37E-05 |
|
13 |
0.835348441 |
3.77E-05 |
4.60E-04 |
-3.77E-05 |
|
14 |
0.835324045 |
2.92E-05 |
4.89E-04 |
-2.92E-05 |
|
15 |
0.835328289 |
-5.08E-06 |
4.84E-04 |
5.08E-06 |
|
16 |
0.835327233 |
1.26E-06 |
4.86E-04 |
-1.26E-06 |
|
17 |
0.835312823 |
1.73E-05 |
5.03E-04 |
-1.73E-05 |
|
18 |
0.835322277 |
-1.13E-05 |
4.92E-04 |
1.13E-05 |
|
19 |
0.835323287 |
-1.21E-06 |
4.90E-04 |
1.21E-06 |
|
20 |
0.835327283 |
-4.78E-06 |
4.86E-04 |
4.78E-06 |
