Thursday, August 5, 2010

Wireless QoS Part 5 - Contention Window and Final Thoughts

Read the Entire Wi-Fi Quality of Service 5-Part Series:
  1. Part 1 - Background Information
  2. Part 2 - IEEE 802.11e Principles
  3. Part 3 - User Priorities, Access Categories and Queues
  4. Part 4 - Arbitration Interframe Spacing
  5. Part 5 - Contention Window and Final Thoughts
Part 5 - Contention Window and Final Thoughts
The third major QoS design change implemented as part of the 802.11e amendment and WMM certification is replacement of the PHY-specific contention window scaling with PHY / QoS Access Category specific values. Just as with AC dependent AIFS values, contention window values are now AC dependent and will provide a statistical advantage for higher priority frames.

The Contention Window

Once the station has waited the appropriate arbitration inter-frame space time, it randomly selects a value for its random backoff timer. The timer value must be within the Contention Window values defined for the priority queue. Each of the 4 priority queues has a defined Contention Window range, initially defined as ranging from 0 to CWmin, where CWmin varies between each of the queues.

Once the appropriate AIFS time has been waited, each station begins decrementing the random backoff timer by one for every slot time that passes. If another station begins transmitting before its timer has reached zero, the station defers access until the medium is available again, at which time it continues decrementing the timer from where it previously left off. Once the timer reaches zero, the station is allowed to transmit the frame over the air.

If a collision occurs where two stations transmit at the same time, no acknowledgment of the frame will be received and the station will increment its retry counter and increase its contention window according to the binary exponential backoff algorithm, up to a maximum contention window size of CWmax. The stations must then wait the appropriate AIFS time, select a new random backoff timer using the new contention window range, and proceed as before.

Similar to AIFS, the differences in the contention window values serve to prioritize traffic in higher priority queues by allowing them to wait shorter time intervals before being allowed to transmit over the air. The CWmin and CWmax values vary based on the PHY and the AC queue in use.

For review, the DCF (non-QoS) contention window values are:

  • 802.11b    aCWmin 31    aCWmax 1023
  • 802.11g    aCWmin 31    aCWmax 1023 (when 802.11b stations are present)
  • 802.11g    aCWmin 15    aCWmax 1023
  • 802.11a    aCWmin 15    aCWmax 1023
  • 802.11n    aCWmin 15    aCWmax 1023

Notice how the contention window range is the same across all OFDM PHYs, with legacy CCK PHY being the only dissimilar value. Traffic prioritization is therefore very coarse, and is based not on application traffic but on the PHY used for transmission. Effectively, all frames in a legacy DCF Basic Service Set (BSS) have the same priority and access to the medium. This can lead to problems, especially for latency sensitive applications such as voice and videoconferencing.

The new EDCA contention window values vary based on the Access Category (AC) and are derived from the DCF base values shown above. These values are administrator configurable, with default values defined as:

  • AC_VO (Voice)       CWmin = (aCWmin+1)/4 – 1   CWmax = (aCWmin+1)/2 – 1
  • AC_VI (Video)       CWmin = (aCWmin+1)/2 – 1   CWmax = aCWmin
  • AC_BE (Best Effort) CWmin = aCWmin             CWmax = aCWmax
  • AC_BK (Background)  CWmin = aCWmin             CWmax = aCWmax
Note – Default values for non-AP QoS stations are defined in IEEE 802.11e amendment section 7.3.2.27 and the current IEEE 802.11-2007 standard section 7.3.2.29.

The default EDCA contention window values for the 802.11b PHY in a QoS BSS are defined as:
  • Voice Queue        CWmin = 7      CWmax = 15
  • Video Queue        CWmin = 15     CWmax = 31
  • Best Effort Queue  CWmin = 31     CWmax = 1023
  • Background Queue   CWmin = 31     CWmax = 1023
The default EDCA contention window values for the 802.11g/a/n PHY in a QoS BSS are defined as:
  • Voice Queue        CWmin = 3      CWmax = 7
  • Video Queue        CWmin = 7      CWmax = 15
  • Best Effort Queue  CWmin = 15     CWmax = 1023
  • Background Queue   CWmin = 15     CWmax = 1023
Notice the differences from legacy DCF contention window ranges. In a QoS BSS, each queue clearly has differentiated access to the medium. For instance frames in the voice queue will initially select a random backoff timer between 0 - 3, versus frames in the video queue which will initially select values between 0 - 7. In this manner, frames in the voice queue have a statistically greater chance of selecting a random timer value that is lower than frames in the video, best effort, and background queues. It is still possible that a frame from a lower priority queue will select a lower random backoff timer, but most of the time they will not. 

Also, notice how the maximum contention window range for voice and video are still relatively small compared to the other queues. On a heavily utilized network, as retransmission attempts increase, the statistical advantage for voice and video frames gets even better. 

The CWmin and CWmax values are encoded in exponent form, base 2, then decremented by 1 in the EDCA Parameter Set information element, and each field is 4 bits long. Therefore, the minimum contention window values is 0 and the maximum value is 32,767. However, in practice the typical maximum value is never set above 1,023.

Contention Window Scaling
Contention window scaling between CWmin and CWmax is easier to understand when illustrated. For the first transmission attempt, the random backoff timer is set to a value between 0 – CWmin. Only when a retransmission is required due to the lack of a returned frame acknowledgement will the possible range grow. For the first and each subsequent retransmission attempt, the contention window will double by a power of 2. This is called binary exponential backoff. Once the window grows to CWmax, it will grow no further. Subsequent retransmission attempts will use the largest contention window range when selecting a random backoff timer value until the frame is either successfully transmitted (and acknowledged) or the maximum number of retransmission attempts is reached (typically somewhere between 7 and 64 attempts; Cisco APs default to 64 attempts for example).

As an interesting side note, when optimizing networks for VoWLAN, many vendors have a feature to quickly age out latency-sensitive voice frames after fewer retransmission attempts. This is done because a voice packet that is delayed too long will be useless to the receiver since it cannot insert it back into the voice stream if it processed and sent the analog stream to the human recipient past the point where the frame was delayed. On Cisco equipment, this feature is called Low Latency MAC, it applies only to voice frames in the Voice Access Category, and it only attempts 3 retransmissions for voice frames before dropping them.


(Figure 2-5 courtesy of “Voice over Wireless LAN 4.1 Design Guide” page 2-7, by Cisco Systems)

Putting it all Together
Therefore, the design of priority schemes for IEEE 802.11 wireless networks are dictated by the definition 8 user priorities mapped to 4 access categories, 4 priority queues, Arbitrated Inter-Frame Spacing (AIFS) values for each queue, and Contention Window values for each queue. Higher priority traffic waits less time statistically before being allowed to transmit a frame over the network. 

Since wireless is shared medium, and medium contention is distributed among all clients under DCF and EDCA, higher priority traffic cannot be guaranteed to be able to transmit before lower priority traffic from other stations, or even internally within a station between its internal queues. 802.11e and WMM only provide for a statistical advantage for higher priority traffic. On average, higher priority frames will wait less time prior to transmission and have greater access to the medium than will lower priority frames. In a shared medium, there is no such thing as a guarantee!

The IEEE 802.11e AIFS and CWmin values are illustrated in the following figure, based on the 802.11b PHY.


(Figure 2-8 courtesy of “Voice over Wireless LAN 4.1 Design Guide” page 2-10, by Cisco Systems)

External Resources
Be sure to check out these additional references for more information on 802.11 arbitration (medium contention), 802.11e, and WMM:


There are many other features in the 802.11e and WMM certification relating to QoS, such as Transmit Opportunities (TXOP), (Un)Scheduled Automatic Power Save Delivery (APSD), WMM Power Save, etc.

As a wireless network administrator / engineer / architect / consultant, understanding the fundamentals of 802.11 wireless network medium arbitration and frame prioritization is essential to planning, designing, implementing, and supporting a production network. Wi-Fi networks are mission-critical for many organizations these days, and skilled wireless IT staff is typically hard to find. Arm yourself with the knowledge and skills and you'll be sure to find success following you!

-Andrew

5 comments:

  1. AIFS is the only proper way to prioritize traffic. Contention window differentiation should be used only in order to adapt backoff to traffic intensity by access category. Otherwise, if a short contention window were used for a top priority access category regardless of traffic load, when the traffic load in that access category is heavy, longer latency would be observed than what would have been experienced by starting with a longer contention window. The reason is that the probablity of collision among stations increases with a short contention window. Collisions lead to repeated contention window scaling through exponetial backoff, resulting in longer backoffs and greater latency. Top priority traffic could experience longer latencies than the lower priority traffic as a consequence.

    ReplyDelete
  2. AIFS is the only proper way to prioritize traffic. Contention window differentiation should be used only in order to adapt backoff to traffic intensity by access category. Otherwise, if a short contention window were used for a top priority access category regardless of traffic load, when the traffic load in that access category is heavy, longer latency would be observed than what would have been experienced by starting with a longer contention window. The reason is that the probability of collision among stations increases with a short contention window. Collisions lead to repeated contention window scaling through exponential backoff, resulting in longer backoff and greater latency. Top priority traffic could experience longer latencies than the lower priority traffic as a consequence.

    ReplyDelete
    Replies
    1. You make an excellent point! But I wouldn't go as far as saying AIFS is the "only" proper way to prioritize traffic. It depends on the traffic volume. Most enterprise-class WLAN equipment allows the administrator to tailor the contention window sizes (CWmin and CWmax) based on their unique environment. If your WLAN has more than a few voice calls occurring at any one time on APs, then you can adjust the CWmin value accordingly to prevent collisions and subsequent backoff and contention window scaling.

      The contention window values are of greatest concern in the Voice and Video queues where larger default CWmin settings could negatively impact timely network access (in aggregate) and subsequently result in higher latency and increased jitter.

      Also, I have actually seen vendor testing around contention window values that optimize performance at various client densities. I believe you'll start to see "smarter" vendor algorithms that can dynamically adjust contention window values based on network load and client density per-queue.

      Cheers,
      Andrew

      Delete
    2. Regarding your last point on dynamically contention window values adjustment. Do you think changing these values for the queues will keep the WiFi Equipment compliant for WMM Certification?

      Delete
    3. Hi Vipin,
      The default contention window values can be changed and the system will remain WMM compliant.

      Andrew

      Delete