Categories
WLAN general

What does 802.11 Contention Look Like (Part 3) – Probabilities & Our First Model

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:

  1. The possibility that person 2 or person 3 will choose the SAME number as person 1. (A = B or A = C)
  2. 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:

Eq_img_1

Therefore P the chance of choosing the same number:
Screenshot 2016-06-14 13.02.35

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:

Screen Shot 2016-06-13 at 9.44.50 PM

Therefore if we had 4 People, the chances of persons B, C, or D choosing the same number as A would be:

Screen Shot 2016-06-13 at 9.44.59 PM

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:

Screen Shot 2016-06-13 at 9.45.13 PM

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:

Screen Shot 2016-06-13 at 9.45.20 PM

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:

Screen Shot 2016-06-13 at 9.45.28 PM

The probability of a collision occurring is therefore equal to:

Screen Shot 2016-06-13 at 9.45.36 PM

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:

Screen Shot 2016-06-13 at 9.45.44 PM

Simplifying the equation and multiplying everything out, we can see that the equation becomes:

Screen Shot 2016-06-13 at 9.45.55 PM

Screen Shot 2016-06-13 at 9.46.03 PM

Screen Shot 2016-06-13 at 9.52.12 PM

The probability of a collision occurring is complementary to the probability of no collision, so the probability of a collision is given by:

Screen Shot 2016-06-13 at 9.52.26 PM

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:

  1. Number of total STAs cannot exceed 101 – this is a limitation with Excel mathematical capabilities – I’ll work around that later!
  2. Assume DSSS and HR-DSSS PHY Types do not support QoS.
  3. All STAs are using the same PHY Type.
  4. All STAs are transmitting traffic in the same QoS Access Category
  5. All STAs are contending for medium access 100% of the time (100% Duty Cycle)
  6. All STAs are using the same Contention Window size.
  7. 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.
  8. 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.

Rob

Categories
WLAN general

What Does 802.11 Contention Look Like (Part 2) – How contention works:

802.11 Medium Access Control implemented with the Distributed Co-ordination Function (DCF) and Enhanced DCF Channel Access (EDCA) methods, uses a random back-off counter to help ensure that clients do not transmit their data at the same time, but rather take turns to send their data one after the other.  This is the “Collision Avoidance” part of CSMA/CA.

When two (or more) 802.11 stations both have data to send on the same channel and both have established that the channel is clear, both stations will select a random number, wait a pre-defined period called a DCF Interframe Space (DIFS) and then start counting from the random number to zero. The first station to reach zero transmits its frame. The other station hears the PHY & MAC header of the frame transmission and returns to idle state until the transmission is completed. Once the transmission is over and it is time for the second station to contend for the medium again, it will go through the process again and simply start counting down from where it left off. The first station, if it has more data to transmit, will select another random number and contend for the medium again.

The first important observation

It is important to realize early on, there is a possibility here that the first station could choose a random number lower than the one that the second station is on. Think of the scenario where the first station chooses a random back-off value of 4 for its first transmission, and a back-off value of 7 for its second transmission (12,4% probability). If the second station chose a random back off of anything greater than 11 for its first transmission (26% probability) then the first station will send two frames before the second station has even sent one! Statistically however, this should happen an equal number of times to both stations ensuring roughly fair access to the medium! This is why we say WLAN is a BEST EFFORT protocol. There is no guaranteed access to the medium as there is with “Telco” wireless access technologies! (WiMAX, iBurst, 2G, 3G, LTE etc)

An Analogy

You can think of 802.11 channel contention like randomly choosing a number to find your position in a queue in a bank. You pick a number and join the queue in that position and wait until it is your turn to be served by the teller.  If there is a person in front of you, and that person goes to the teller, you take a few steps forward then stop and hold your place in the queue until it is your turn to be served.  If the person ahead of you has any further business requests they join the queue in a new random position and wait their turn again.


EDIT: A point of clarity from Devin Akin here:

“When the CCA is returned as BUSY, then the remaining number of slot times are held during frame transmissions from other STAs/APs, which could each take a long time if they are large aggregate data frames.”

Let’s say there are two people in the queue, and you pick position 7 and another picks position 3.  Both of you will walk forward 3 steps toward the teller.  The other person will get to the counter first, you will see that the teller is busy and you will hold position 4 until that person is done.  This could take some time!  Imagine if the person talks very slowly?  Once the person is done, then they will rejoin the queue in a random place and you will start walking forwards again from the position you were in.


Collisions

Now the trick is, if the range of numbers you can choose is finite, let’s say between 0 to 15, then there is a chance of you choosing the same position in the queue as someone else. This chance obviously increases with the number of the people joining the queue.

If you choose the same random number as someone else, you would both arrive at the front of the queue at the same time. The bank clerk serving the queue would be unable to answer both of your requests simultaneously and would refuse to acknowledge either of you.

You have just had a “collision”.

According to the rules of 802.11 WLAN channel access, both of you would have to pick a NEW random number and rejoin the queue, but with a slight twist. In order to try and reduce the chance of people choosing the same random number and resultant position in the queue, those that suffer a collision would choose a number between 0-31. That is, you would double the range of random numbers you could choose from.

With each consecutive collision you experience, you will double the range of the random numbers you select from. So if you experience a collision and select a random number between 0 – 31 and you reach the counter at the same time as someone else again, you go back (again), select a random number between 0-63 and rejoin the queue and try again, and so on and so forth.

If you succeed in getting to the front of the queue alone, then your request will be served. For your next request you will return to using the original number range (0 – 15).

A second important observation

Just because a specific station has experienced a collision (or several) does not mean that another station has had the same experience. This means that while one station is choosing numbers from 0-31 or 0-63 or even higher after several collisions, there are other stations choosing from 0-15 at the same time!

The Contention Window

In 802.11 WLANs, we call the random number range that stations can choose from the “Contention Window” (CW). The contention window can be calculated by the equation CW = 2N-1. In OFDM Based WLANs with traffic in the Best Effort or Background Access Categories the starting value of N is 4.

802.11 client devices and APs (both referred to as Stations or STAs for short) will typically attempt to re-transmit their data up to 7 times before giving up and dropping the frame. With each successive collision the value of N is incremented until a successful transmission occurs. This means that the Contention Window will typically follow the pattern below:

Attempt # N Value Contention Window (2N-1)
1 4 0-15
2 5 0-31
3 6 0-63
4 7 0-127
5 8 0-255
6 9 0-511
7 10 0-1023
8 NA Give Up. (Dropped Frame)

If the Transmitting STA succeeds in sending the frame and receives an ACK from the receiving station, or to follow our analogy above, gets to the front of the queue alone then N resets to 4 and it returns to using the smallest contention window size (0-15) on the next attempt.

CWmin and CWmax

According to the IEEE 802.11 standard and its amendments, the Contention Window has a minimum and a maximum value.   The example above shows a CWmin of 15 (N = 4) and a CWmax of 1023 (N = 10).   This is true for any 802.11a/g/n/ac WLANs using the Best Effort or Background QoS Access Categories.

802.11 and 802.11b

Any WLAN that uses DSSS (802.11) or HR-DSSS (802.11b) technologies uses a slightly larger CWmin with the N-Value set to 5. This means that the CWmin value for 802.11 and 802.11b WLANs is 31. The CWmax value is still 1023 (N=10)

802.11e QoS:

The 802.11e amendment introduced the ability to prioritize traffic based on 4 different Access Categories. The goal in this case was to ensure that higher priority traffic gained access to the medium faster and ahead of traffic from lower priority Access Categories. The CWmin and CWmax values for the different access categories are shown below.

Access Category CWmin CWmax
VOICE 3 7
VIDEO 7 15
BEST EFFORT – Default for most WLAN traffic 15 1023
BACKGROUND 15 1023

Slot Times

Before we get too far ahead of ourselves it is sensible to just cover how long it takes each STA to count down the randomly selected back off. Each unit in the random back-off countdown lasts for a specific Slot Time as shown in the below table:

PHY Type Slot Time
DSSS / HR-DSSS 20μs
ERP-OFDM 9μs
OFDM 9μs
HT-OFDM 9μs
VHT-OFDM 9μs

It is also important to note that 2.4GHz 802.11g/n networks may only use the 9us slot times when there are no DSSS / HR-DSSS STAs associated to the Basic Service Set. This information enables us to see the actual time delay introduced by the random back-off countdown.

Summary

In this blog post, I really wanted to put a spotlight on the random back off timer and its specifications. I know I haven’t looked at the Interframe Spaces very carefully and I also have not looked at other aspects of traffic flow like TXOP etc. For now I am focused purely on looking at how the random back off affects WLAN contention. We have made some interesting observations and drawn some interesting conclusions:

  1. There is a chance that one STA can successfully transmit two frames or gain access to the medium twice before another STA using the same Contention Window value can gain access to the medium once.
  2. There is a chance that two STAs can pick the same random back off number and collide.
  3. When STAs suffer a collision and don’t receive an ACK they double the size of the contention window and re-contend for the medium.
  4. STAs in the same BSS can all be using different contention Window values at the same time depending on the result of their most recent attempted frame transmission.
  5. STAs will re-transmit up to 7 times, using a contention window of up to 1023 slots (up to 9,2 milliseconds!) before giving up and dropping the packet.
  6. Once a STA has successfully tranmistted a frame and received an ACK, it goes back to the original Contention Window (CWmin) and commences the process again for the next packet.
  7. In QoS enabled networks, Voice and Video traffic use smaller contention windows than Best Effort and Background traffic to guarantee faster access to the medium and also do not increase the N value by more than 1 increment in their re-transmissions.

 

Now that we know the above things, we can start to build some simple models that show the likelihood of a collision under different circumstances. That will come in the next blog post though!

Rob

Categories
WLAN general

What Does 802.11 Contention Look Like? (Part 1)

The IEEE 802.11 Wireless LAN protocol uses Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) with a fairly robust arbitration mechanism to allow WLAN Stations (STAs) to gain access to the wireless medium based on their traffic priority.

The central problem with CSMA/CA and the 802.11 arbitration mechanisms is that the chances of a collision occurring between two stations increases seemingly exponentially with the number of active stations contending for the wireless medium.  This means that as more and more stations use a given channel, the efficiency of the channel decreases quite dramatically.

Many engineers I have met have questioned this and have wondered why the IEEE Standards Body and 802.11 Working Group did not consider more “efficient” methods of medium access.  Why not TDMA, CDMA or OFDMA?  Now, I am not here to get into a discussion about which medium access method the IEEE or vendors should have chosen to develop way back when in 1990-whatever.  Maybe we can discuss channel access methods and their properties on another day after I have read more on the topic!   The truth is though, the IEEE 802.11 Working Group defined several methods of medium access. As it turns out, vendors only ever really developed their products to use the Distributed Co-ordination Function (DCF) and its 802.11e-defined successor, the Enhanced DCF Channel Access (EDCA) method also referred to as the Hybrid Co-ordination Function or HCF for short.

I have often wondered as a WLAN engineer what CSMA/CA actually LOOKS LIKE in the real world.  As designers of Wireless LANs we are often asked to perform capacity calculations and predict what performance level a given design will achieve for a specified application type.  We have the tools to perform a coverage analysis very well, but sadly the tools for capacity prediction fall short of expectation in my opinion.

I agree that there are some good tools out there that get us into the right ballpark and remove a fair amount of guesswork.  But I have yet to come across any tools that can accurately model the effects of WLAN contention and its effect on capacity from first principles.  Most capacity calculators and models I have ever used will cover for the effects of contention using a simple  “RF environment” setting that reduces the amount of airtime efficiency by a certain factor to account for higher collisions in noisier and busier environments.  While this gets us closer to an estimated value of capacity, it still does not give us a definitive answer.  It also IGNORES the underlying mechanics of what is truly going on, making our calculations susceptible to unforeseen errors.  Don’t get me wrong – errors are present in all calculations and can be worked around, but we need to know what they are or at least see where they may come from!  Oftentimes, if we get pushed to reveal the source of some values used in our current capacity calculators, we often have to admit that it is based largely on empirical evidence, or past experience.  Sometimes that will work, other times it might not.

There are also newer technologies like 802.11ax with OFDMA channel access methods that promise to introduce a new “High Efficiency” mode of operation to the 802.11 Standard.  It would be useful then to understand exactly why and under what circumstances the current standard and its amendments are inefficient!  We also need to build a model that can show the potential improvements brought forth by new amendments.

This is the source of  my motivations for starting this blog series.  And before you say it…

Yes, I know The Birthday Problem

When you mention the term 802.11 Contention or CSMA/CA most WLAN engineers will talk about THE BIRTHDAY PROBLEM, and we all understand that this calculates the overall chance of a collision given a certain number of clients.  But it still doesn’t really give us a clear picture of how it works.  It’s kind of like saying “There is a 15% chance of rain today”, which is useful to tell whether to walk outside with an umbrella, but it doesn’t give us any insight into how the clouds form, or when it will rain, or for how long, or if there will be a monkey’s wedding, or if it will involve a romantic couple kissing in a park.  Ok, maybe I took it too far, but you get my gist.  We want details! Details are important.  Details bring insight and understanding.

So what am I going to attempt?

In this blog series I intend to try and model the 802.11 arbitration process to show how certain factors can affect contention overhead in a Wireless LAN.

I will spend some time outlining the mechanics of what I am trying to model and some of the various approaches I have taken to visualize it.  I will also show how those methods are limited and why they are only an approximation of reality.

Let’s start (and end Part 1) by defining exactly what I am trying to visualize.

I want to explore what 802.11 contention LOOKS LIKE in the real world.  Given N active stations using a given WLAN channel:

  1. What is the likelihood overall of one (or more) collisions occurring given N active clients? (This is the answer given by The Birthday Problem).
  2. What is the likelihood of a specific station experiencing a collision at any given time?
  3. How many collisions should we expect a client to have before successfully transmitting a packet?
  4. Do the number of collisions fluctuate or settle into a relatively stable dynamic equilibrium?
  5. Can the number of collisions “snowball” into a state where the medium becomes unusable?
  6. What (really) is the maximum number of active clients that can be supported on a single WLAN channel before the system becomes unstable and the protocol breaks down?
  7. How do different 802.11 technologies (E.g. DSSS, HR-DSSS) affect the number of collisions?
  8. How does traffic volume affect the likelihood of a collision?
  9. What is the effect of an unequal split of upstream Vs. downstream traffic on the number of collisions?
  10. How does setting QoS values alter the number of collisions?
  11. How can we characterize and model application traffic streams?
  12. How does airtime efficiency and the negotiated PHY Data Rate affect the number of collisions?
  13. How does the effect of contention affect our WLAN capacity calculations?
  14. Most importantly, given this insight how can we minimize the number of collisions to get the best possible network capacity?

Right, well that’s a pretty solid list of items to try and answer. I am not sure we will be able to get to all of them at once, but now that we’ve written down what we want to see, we can move on to Part 2!

Rob