In my previous blog posts in this series I covered the inherent problem with CSMA/CA and how it loses efficiency as more stations make use of a channel. I also covered some of the basic rules of how CSMA/CA works as implemented by 802.11 Wireless LANs.
As I mentioned at the beginning of this blog series, my intention here is to build an argument and the logic for describing what WLAN contention actually looks like in the real world. We’ve gone over some of the rules of how WLAN contention works. But now it is time to start building some simple mathematical models of its effects on the medium and then to carefully evaluate how those models stack up against the real world operation of 802.11 WLANs.
First, some background on probabilities
When you are working with system that uses a random or stochastic component and forms a stochastic process, it becomes very hard to build a deterministic model of how that system works. There is an inherent uncertainty built into the system and we cannot predict the outcome with 100% accuracy. It becomes necessary to start attaching a probability to any one of the possible outcomes. Let’s start with an example.
If you have two people in a room, and you ask both people to choose a random number between 0 and 15. What is the chance that they will choose the same number?
The first person chooses a random number and the second person has a 1 in 16 chance of choosing the same number. Therefore the chance of both people choosing the same number is 1/16 or 6.25%. If we want to put it another way, the chances of the two people NOT choosing the same number are 15/16 or 93.75%. We can also write 15/16 as (1-1/16).
What if we have three people? Well, then the problem becomes slightly trickier and we have to ask ourselves what we want to know!
There are two things we can calculate:
- The possibility that person 2 or person 3 will choose the SAME number as person 1. (A = B or A = C)
- The chance that any two clients have chosen the same number. (A = B, A = C, or B = C)
A = B or A =C:
The chance of choosing the same number in this case becomes a little harder to calculate. We know that as the number of people selecting numbers increases the chance of selecting the same number as the first person must increase, but how?
By looking only at the chances of choosing the same number, we struggle to find a single intuitive equation that can tell us how the chance increases. Well, at least I do.
As it turns out, we can solve the problem by evaluating the chance of NOT choosing the same number. The chance of A and B NOT choosing the same number = 93.75%. If we allow C to choose a number, the chances of also avoiding a collision with A are 93.75% of 93.75%. What are the chances that both B and C avoided a choosing the same number as A? We can say P* is the possibility of NOT choosing the same number:
Therefore P the chance of choosing the same number:
We now have an intuitive equation that gives us the possibility of person B or C choosing the same number as person A.
Generalizing to N people
But what if we had more than 3 people? We can also generalize this equation for N People as follows:
Therefore if we had 4 People, the chances of persons B, C, or D choosing the same number as A would be:
Generalizing the number of possible choices
Up until this point, we have examined only the scenario where the random number chosen by N people exists within the range of 0 to 15, i.e. there are 16 different possible outcomes with each choice. What if the number of options is larger?
We can generalise our equation to reflect the number of possible outcomes with each selection by labeling the number of possible outcomes as . The Possibility P(N) of a collision with Person 1 therefore becomes:
In summary, this generalised equation gives us the probability that the random number chosen from different options by a specific person in a group of N people will also be selected by at least one other member of the group of N people.
A = B, A = C, or B = C
In this case we are trying to find the scenario where any choice is the same as any other choice in the group of people. Put another way, in a group of people of a certain size, what is the chance that any person chose the same number as any other person?
First we can start with the trivial example of two people in a group choosing a random number out of x different options. The probability of them NOT choosing the same number is easily seen to be:
What about the case of three people choosing a number? Let’s go through it slowly.
In this case, the first person to choose a number has a 100% probability of not selecting the same number as anyone else, since nobody has selected a number. The second person has a (1-1/x) chance of no collision with the first. The third person has a (1-2/x) chance of not colliding with either of the other two. So we can say that for three people the probability of NO collision is equal to:
The probability of a collision occurring is therefore equal to:
Generalizing to N people
What if we had more than three people? The equations from above can be generalised for N people. The probability of NO collision is equal to:
Simplifying the equation and multiplying everything out, we can see that the equation becomes:
The probability of a collision occurring is complementary to the probability of no collision, so the probability of a collision is given by:
where N is the number of people, and x is the number of possible choices.
In summary, this second generalized equation gives us the probability that the random number chosen from x different options by ANY person in a group of N people will also be selected by at least one other member of the group of N people.
Our first model:
For our first model of 802.11 channel contention I have built a simple spreadsheet using the formulae above and the rules laid out in my Second Post in this series. It shows the possibility of a client experiencing a collision given a variable number of active 802.11 STAs. I have included the different Contention Window values for different QoS Access Categories and I have also included some of the effects of 802.11 PHY Type on the Contention Window Size. Feel free to download it here.
For the purposes of keeping things simple the model has the following restrictions / limitations:
- Number of total STAs cannot exceed 101 – this is a limitation with Excel mathematical capabilities – I’ll work around that later!
- Assume DSSS and HR-DSSS PHY Types do not support QoS.
- All STAs are using the same PHY Type.
- All STAs are transmitting traffic in the same QoS Access Category
- All STAs are contending for medium access 100% of the time (100% Duty Cycle)
- All STAs are using the same Contention Window size.
- This model is turn based. It assumes that once an STA has chosen a random back-off and transmits a frame, the same STA cannot interfere with the remaining STAs until everyone has sent a frame. So it is only applicable for low traffic / duty cycle environments.
- The BSS does not suffer from Near/Far problems (i.e. if two stations Tx at the same time, both will experience a collision, one cannot overpower the other and get through).
So as we can see from this model, it is pretty limited but it does give your customers an idea about why you cannot support more than a specific amount of VoIP clients on a WLAN. It will also lend significant credence to the argument by Ben Miller about why many Wi-Fi Calling Apps are better off using Video priority in HD environments with multiple active clients. You can fidget with the numbers here too and play around.
As for our modeling journey, well it is version 0.1 so we have a long, long way to go before we have something that even closely resembles the real world. But we’ve cast the first stone.
In my next blog post I will discuss a method that I used to try and improve upon this model, and I’ll discuss its differences with this model and also its limitations.