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)
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.
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)|
|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)
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.
|BEST EFFORT – Default for most WLAN traffic||15||1023|
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|
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.
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:
- 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.
- There is a chance that two STAs can pick the same random back off number and collide.
- 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.
- 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.
- 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.
- 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.
- 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!