Monday, March 7, 2011

Understanding Wi-Fi Carrier Sense

The Importance of Carrier Sense
Carrier Sense (CS) is one of the most integral parts of modern Wi-Fi networks. Fundamentally, Wi-Fi is a multiple access link, which means that it is shared and requires vastly different protocol design and architecture than a point to point circuit (as any Masters graduate student studying computer science could tell you). In addition, random access to the medium is distributed across all stations on the network. Wi-Fi does not pass tokens, reserve the medium with bit-mappings, or use any other control mechanisms dictating which stations have access to transmit.

This distributed nature makes carrier sense (and subsequent medium contention) core components of network operation and efficiency. The practical implications are seen in Wi-Fi engineer's daily work. We perform site surveys, develop non-overlapping 1, 6, 11 channel plans, optimize channel re-use, and perform capacity planning all in the name of performance optimization for a network that runs over an unguided medium with random access distributed between stations. Understanding these principles of design and the protocol operation behind them are important for engineers to adequately and successfully build wireless networks.

The precursors to the IEEE 802.11 and Wi-Fi protocol design were developed in the pure ALOHAnet protocol, slotted ALOHA, and finally Carrier Sense Multiple Access (CSMA) developed for the 802.3 Ethernet specification.

As I've previously written, 802.11 Wi-Fi is based on CSMA/CA, whereas 802.3 Ethernet is based on CSMA/CD. What's the deal, one little letter difference? Well that one little letter represents a significant underlying difference between the two network protocols. What they both have in common is the need to perform Carrier Sense (CS) for medium idle/busy detection on a Multiple Access (MA) network segment (hence the CSMA portion). What differs are how stations determine if the medium is idle (Collision Detection versus Collision Avoidance), and how they are granted access to the medium once it is found to be idle (1-persistent for Ethernet versus p-persistent for Wi-Fi, where "p" indicates the probability of transmission when the medium is found to be idle). This is largely due to the inherent differences of electromagnetic signalling over guided versus unguided media (copper or fiber cabling versus the air). For an overview of collision avoidance and medium contention, see my previous series on Wireless QoS.

Let's review how carrier sense is performed.

Wi-Fi Carrier Sense Overview
Wi-Fi carrier sense is composed of two separate and distinct functions, Clear Channel Assessment (CCA) and the Network Allocation Vector (NAV). From a high level perspective, CCA is physical carrier sense which listens to received energy on the radio interface. NAV is virtual carrier sense which is used by stations to reserve the medium for mandatory frames which must follow the current frame.

It is important to note that CCA is not the same as the NAV. CCA indicates a busy medium for the current frame, whereas NAV reserves the medium as busy for future frames that are required to be transmitted immediately following the current frame.

Clear Channel Assessment
CCA is defined in the IEEE 802.11-2007 standards as part of the Physical Medium Dependant (PMD) and Physical Layer Convergence Protocol (PLCP) layer. For reference, the IEEE layer specifications include PMD, PLCP, MAC/LLC as shown below:

Clear Channel Assessment is composed of two related functions, carrier sense (CS) and energy detection (ED).

Carrier sense refers the ability of the receiver to detect and decode an incoming Wi-Fi signal preamble. In addition, CCA must be reported as BUSY when another Wi-Fi signal preamble is detected, and must be held as BUSY for the length of the received frame as indicated in the frame's PLCP Length field. Typically, any incoming Wi-Fi frame whose PLCP header can be decoded will cause CCA to report the medium as busy for the time required for the frame transmission to complete.

The PLCP header Length field indicates either the number of microseconds required for transmission of the full frame MPDU payload (DSSS), or the number of octects carried in the frame MPDU payload (OFDM) which is then used in combination with the Rate field (which identifies the modulation used for the payload) to determine the time required for MPDU transmission. Either way, the Length or Rate + Length fields give the receiver the information required to de-modulate the frame and determine how long the medium will be busy.

For reference, here is the PLCP frame header format for the DSSS PHY:

Note - for those curious, the PLCP header is always encoded at a fixed data rate so that the receiving stations can decode the information. DSSS PLCP is transmitted at 1 Mbps, DSSS Short Preamble at 2 Mbps, and OFDM at 6 Mbps. Only the frame MPDU payload is encoded at a variable data rate which is specified in the SIGNAL/RATE field.

Energy detection (ED) refers to the ability of the receiver to detect the non-Wi-Fi energy level present on the current channel (frequency range) based on the noise floor, ambient energy, interference sources, and unidentifiable Wi-Fi transmissions that may have been corrupted but can no longer be decoded. Unlike carrier sense which can determine the exact length of time the medium will be busy with the current frame, energy detection must sample the medium every slot time to determine if the energy still exists. In addition, energy detection requires a pre-defined threshold which determines if the reported energy level is adequate to report the medium as busy or idle. This is typically referred to as the ED threshold level or CCA sensitivity level. The ED threshold is usually much lower for valid Wi-Fi signals that can be decoded using carrier sense than it is for non-Wi-Fi signals. For example, the noise ED threshold must be 20 dB greater than the corresponding Wi-Fi signal ED threshold for most PHYs.

For more information on the CCA sensitivity level of each PHY, see the "Further Reading" notes at the end of this post.

As an interesting side note, when evaluating the RF environment with a spectrum analyzer, the ED threshold level value may be implemented differently than Wi-Fi stations. This may cause the spectrum analyzer's duty cycle metric to be out of alignment with how a Wi-Fi station would interpret the same environment. For example the Cisco Spectrum Expert SaGE v2 chipset reports duty cycle as any energy above the noise floor which is typically -92 to -95 dBm, whereas a client adhering to DSSS specifications transmitting at 50mW would only mark the medium as busy based on ED of -76 dBm or greater (per IEEE 802.11-2007 section 15.4.8.4). This difference is worth noting, but in my experience is not cause for significant concern when evaluating an environment for noise or interference.

Network Allocation Vector
In addition to CCA determining the medium idle/busy state for the current frame and noise, the NAV allows stations to indicate the amount of time required for transmission of required frames immediately following the current frame. This is important to reserve the medium as busy for these mandatory frames.

The importance of NAV virtual carrier sense is to ensure medium reservation for frames critical to operation of the 802.11 protocol. Typically these are control frames, but not always. They include 802.11 acknowledgements, subsequent data and acknowledgement frames as part of a fragment burst, and data and acknowledgement frames following an RTS/CTS exchange.

The NAV is carried in the 802.11 MAC header Duration field which is part of the MPDU payload, and is encoded at a variable data rate as discussed previously. Therefore, not all stations within the area may be able to decode the MPDU due to insufficient SNR. However, all stations within the area should still be able to decode the PLCP header used for CCA. Since the critical frames that the NAV protects use shorter inter-frame spacing values (SIFS for example), those frames should still gain access to the medium before any other station attempts to transmit and stations will detect a busy medium through CCA carrier sense. However, the added protection through NAV reservation is lost.

Stations that are able to decode the 802.11 header extract the Duration field value and use it mark the medium as busy for the amount of time specified (in microseconds). Therefore, the transmitter should follow the strict rules defined in the 802.11 specification for calculation of the NAV value to be sent within frames. Stations (including APs) not adhering to the specification could reserve too much time in order to hog the medium, as has been accused of at least one infrastructure vendor in the past. (I won't name names, but they know who they are :)

Note - The NAV timer also accounts for time required for appropriate inter-frame spacing, such as SIFS intervals between data and acknowledgement for example.

Summary and Recap
Every Wi-Fi station must first determine the state of the medium as idle or busy through the process of carrier sense, prior to being allowed to perform pro-active collision avoidance and ultimately transmit a frame. Carrier sense is composed of clear channel assessment and the network allocation vector, which together allow for adequate sensing of the physical environment as well as reserve the medium for frames critical to the operation of the protocol.

If you're like me, you find the physical layer properties of Wi-Fi networks fascinating. These fundamental concepts of carrier sense, CCA, NAV, modulation, encoding and the underlying physical properties of radio frequency propagation form the building blocks for most of the advanced mobile technologies that form our modern civilization. It's exciting to understand these concepts and see real-world examples in front of us everyday that are shaping our culture and our lives.

My intent is to convey my joy of these concepts to you, my readers, and inspire the same passion for Wi-Fi as I have. We are a new generation of RF engineers, not all that different from generations past who invented the telegraph, radio communications, and amateur ham radio operators.

Cheers,
Andrew


A Note on Nomenclature
PHY stands for Physical Layer Specifications.
DSSS stands for Direct Sequence Spread Spectrum, and is used in the original 802.11 PHY at 1 and 2 Mbps.
HR-DSSS stands for High Rate DSSS, and is used in the 802.11b PHY at 5.5 and 11 Mbps.
ERP stands for Extended Rate Physical, and is used with OFDM encoding with 802.11g PHY at 6 - 54 Mbps.
OFDM stands for Orthogonal Frequency Division Multiplexing, and is used in the 802.11a PHY at 6 - 54 Mbps.
HT stands for High Throughput, and is used with OFDM encoding with 802.11n PHY at 6.5 - 600 Mbps.

Further Reading
The following references are worthwhile reading for those looking for more information:

CSMA Persistence - "Computer Networks: Fifth Edition" by Andrew S. Tanenbaum and David J. Wetherall

The following sections in the IEEE 802.11-2007 standard:

PLCP Header Format in DSSS 15.2.2
PLCP Header Format in HR-DSSS 18.2.2
PLCP Header Format in ERP 19.3.2 (Can actually use any of the other 3 formats, depending on the situation)
PLCP Header Format in OFDM 17.3.2
PLCP Header Format in HT 20.3.2 (Found in the 802.11n amendment, not 802.11-2007)

CCA Sensitivity in DSSS 15.4.8.4
CCA Sensitivity in HR-DSSS 18.4.8.4
CCA Sensitivity in ERP 19.3.5
CCA Sensitivity in OFDM 17.3.10.5
CCA Sensitivity in HT 20.3.22.5 (Found in the 802.11n amendment, not 802.11-2007)

NAV 9.2.5.4 through 9.2.5.6, and 9.2.11

21 comments:

  1. Nice post andrew, you cleared up a couple of issue that had been bugging me, one being the ED threshold.

    ReplyDelete
  2. Hello Andrew,

    Thank you for your post, it is very clear and well structured. I have some questions though about the OFDM PHY.

    1. The 802.11-2007 standard specifies that if the preamble is correctly received, the received power level also needs to be checked against the sensitivity threshold before calling PHY_CCA.ind(BUSY). What happens if the power level is under the threshold, but we are still able to receive the message?

    2. There is no ED level literally specified for OFDM PHY, it is only mentioned that if the preamble is not decoded, a threshold 20dB higher than the CCA sensitivity level should be used. Is this the ED level for OFDM?

    3. When IEEE 802.11 is modeled in different simulation tools, the supposition that two different thresholds exist is made. These power levels are usually called "reception threshold" and "carrier sense threshold", with Rt higher than CSt. Do you think they can be mapped on some parameters from the standard, or is this just an artifact of the modeler?

    Once again, thank you for your explanations, your blog definitely goes in my bookmarks.

    Grtz from France,

    Razvan

    ReplyDelete
  3. Hi Razvanica,
    To answer your questions:

    1. If a station can properly decode a Wi-Fi preamble it will indicate the medium is busy. See section 15.4.8.4, CCA Mode 2 and 3, and sub-bullet c) on the same page.

    2. The OFDM PHY energy detection threshold references the receiver minimum input sensitivity in section 17.3.10.1.

    3. I have never used simulation tools or modelers, but it would be reasonable to use the 802.11 standards baseline receiver minimum input sensitivity values for each PHY. The section referenced in the last answer (17.3.10.1) is an example for the OFDM PHY. You'll have to find the values for the other PHYs in the standard.

    If you wanted to model data for a specific client adapter, you can check the manufacturer specifications for receive sensitivity at each data rate to get a more precise value. But these values will vary for each client based on manufacturing. For an example, look at the receiver sensitivity of the Cisco CB21AG card here:
    http://www.cisco.com/en/US/prod/collateral/wireless/ps6442/ps4555/ps5818/product_data_sheet09186a00801ebc29.html

    Cheers,
    Andrew

    ReplyDelete
  4. Thank you Andrew for your answer.

    However, there is still something I do not understand. The values in 17.3.10.1. are modulation dependent. But if the station can not decode the header, it has no way to detect which type of modulation has been used. Therefore I don't really see how this threshold can be considered the same as the ED limit, because the ED limit does not depend on modulation.

    Moreover, section 17.3.10.5. clearly mentions that "a valid OFDM transmission" only triggers PHY_CCA.ind(BUSY) if the reception power level is higher than the minimum input sensitivity. So you can understand my problem with a valid OFDM transmission received under the sensitivity threshold.

    Thank you again and I hope you can find a couple of minutes to make this clear for me.

    Regards,

    Razvan

    ReplyDelete
  5. Hi Razvanica,
    If a station cannot decode the 802.11 preamble, which is transmitted at a constant low data rate (e.g. 6 Mbps for 802.11a OFDM), then it is interpreted as noise and applies to the energy detection threshold. However, the ED threshold is much higher than the minimum receiver input sensitivity for the 6 Mbps rate. So in these instances the noise will not be sufficient enough to trigger CCA Busy.

    Essentially, if the station can decode the preamble, then the station senses medium busy. If the station cannot decode the preamble, then the signal is usually way too low and interpreted as noise which is too low to trigger the ED threshold and the medium could be marked idle if no other transmission or noise is present.

    The other scenario is when the Wi-Fi transmission has been corrupted, perhaps by a collision, and is at a much higher signal level above the ED threshold. In this case, the receiver will not be able to decode the preamble correctly, but the noise will be above the ED threshold and trigger CCA Busy.

    Hope this helps,
    Andrew

    ReplyDelete
  6. Hi Andrew,

    Every WiFi station does noise calibration periodically to update the noise level. In light of this, does noise level can shoot up when the receiver is not able to decode the WiFi signal ?

    Thanks,
    Ajay

    ReplyDelete
  7. Hi Andrew,

    Regarding your statement:
    "Stations (including APs) not adhering to the specification could reserve too much time in order to hog the medium, as has been accused of at least one infrastructure vendor in the past. (I won't name names, but they know who they are :)"

    I won't ask for vendor name 8-) , do you remember why they want to hog the air time by cheating on the packet duration?

    Thanks.

    Thanh

    ReplyDelete
  8. Hi Thanh,
    See these articles about manipulation of the 802.11 Duration field and why that may be advantageous for a vendor:

    http://www.networkcomputing.com/wireless/229610421

    http://www.networkcomputing.com/wireless/229610532

    http://www.networkcomputing.com/wireless/229610060

    Andrew

    ReplyDelete
  9. Hi Andrew,

    Thank you for the links provided!
    I read the articles with great interest regarding the fuzzing on packet duration.
    Keep up the good "non-bias" posting on wifi.

    Thanh

    ReplyDelete
    Replies
    1. Hello Andrew,

      While doing some IDS tests to see how fast the IDS detects a NAV attack, I found several mobiles devices (Apple,Nokia,Rim) sent CTS-self with duration set to 10ms to 14.5ms.
      I'm puzzled for the reason why those devices set duration such high except maybe when they go to sleep mode and the mobile devices attempt to "shut-off" the AP to send them any traffic while they are in sleep mode?!!
      I don't like what I see because all the others devices receiving the CTS-self will also stop transmitting for the duration.
      I wonder if you have seen this kind of behavior from your own wifi experience? and if you have any comments on that.

      Thanks.

      Thanh

      Delete
  10. Hi Thanh,
    I have never seen a mobile device calculate that large of a Duration value. That is extremely excessive! If you don't mind me asking, how did you conclude that? Was it from an actual packet capture and analysis, or the log out of your IDS system?

    I can't believe that those values are accurate. Please verify. If you have an actual packet capture, would you mind sending it to me to look at. My contact info is listed in the right column of this website.

    Also, by chance are you mis-interpreting the value as milliseconds when it is actually microseconds? That can be easy to do sometimes, depending on the tool or log output that you are looking at and how it is formatted.

    For reference, the 802.11-2007 standard section 7.1.3.2, table 7-3 (page 64) clearly states that the Duration value is listed in microseconds.

    Thanks!
    Andrew

    ReplyDelete
    Replies
    1. Hi Andrew,

      I'm pretty much sure I read 10ms (10000) for Apple, 14.5ms (14500) for Nokia+Rim, also I found an evalboard AP from Broadcom doing cts 10ms every 360sec or 240sec (probably for background scan), I believe the AP is trying to silent its clients while doing off-channel scanning and avoid losing packets from the clients associated during the dwell-time spend away from the home channel.

      I'm currently at home, so on Monday I will post you my wireshark capture that sit on my laptop at work so you can inspect those packets yourself.

      I was surprise to found these packets as I'm doing NAV attack at 32ms to test the IDS, and just by curiosity I lower my duration to 10000 and found those packets not from my injection tool. My sniffing setup is Ubuntu 11.04 with Atheros 3 streams card XB114 chipset AR9390.

      Anyway, I will send you those captures.

      Thanh

      Delete
  11. Hi Andrew,

    I have two questions regarding the wireless LAN. I hope you can answer in your free time. It would be a big help for me. Thanks in advance.

    1) In the case, when a wireless LAN node is receiving simultaneous transmission from other wireless LAN nodes, How is the successful reception decision taken? Normally two models are considered in literature. In the first one, the packet is successfully received if the received power from the desired transmitter is greater than the strongest interferer by a certain threshold (SINR threshold). In the second model, the packet is considered successful if the received power from the desired transmitter is SINR threshold greater than the sum of all the interferer powers plus the noise. Which model do you think is more realistic?

    2) What is the least power that the wireless LAN can detect and consider it as an interference for other simultaneously received transmissions. I mean if a wireless node is receiving a packet stronger than its sensitivity threshold and another packet arrives at the wireless node which is lower than the sensitivity threshold, the second packet will be the interference for the first packet. Is there any limit in terms of threshold for the interference packet, for example all packets below noise floor may not be considered.

    Regards,
    Javed.

    ReplyDelete
    Replies
    1. Hi Javed,
      1) I'm not entirely sure how simultaneous transmissions could be handled by a receiver. Typically this is referred to as a collision and the receiver can't recover the frame. But with MIMO systems I'm not sure how they handle reception of a frame based on SINR differences. Since 11n MIMO systems have advanced DSP chips to decode multiple signals at once and recover each independently, I'm sure it could be possible given a large enough SINR difference. However, I don't know that level of detail. Sorry I can't be of more help! I would have to ask a hardware design engineer who has more experience in this area.

      2) As to the second question, if the interfering signal is below the sensitivity threshold for the data rate at which the frame was transmitted, then it's considered noise and the noise floor is effectively raised.

      Cheers,
      Andrew

      Delete
  12. This is really outstanding. Thank you for this article.

    ReplyDelete
  13. Hi Andrew,

    Awesome article.

    I had one query, in case of the services which are real time (like voice service) does the voice packets get prority? if there are multiple users on the same WiFi using real time services how will it work and how the QoS can be maintained in such cases.

    ReplyDelete
  14. Can any one tell me the channel busy duration indicated by the Channel Clear Assessment (CCA) module for each message sensed?

    ReplyDelete
    Replies
    1. Hi Deepak,
      The station indicates the channel is busy for the duration of the Wi-Fi frame if the preamble and the PLCP header "Length" field is decoded properly. This gives the station the exact amount of time the frame will occupy.

      If energy detection is what causes CCA to indicate busy, then the station samples the air every "slot time" to determine if the energy is still above the threshold.

      Both of these points are clearly stated in the article above.

      Cheers,
      Andrew

      Delete
  15. Hi Andrew, am working on mobile VoIP as my project work at school.
    I want to know if the WiFi is enough suitable for several voip session, i mean mobile device with soft phone connected on wifi hotspot.
    I understand very poorly wifi concept, as i see, each device on the network wait for clear channel assessment CCA, but voip call need a continuous flow of data, even if the nav perform a reservation, if the number of user increase, i mean busy hour, lets see 30 voip call at the same time, so some delay may occur independently to the voip server, because of the medium, since the waiting time for each user to transmit will increase, i know that it is matter of micro or mili second, but still, even if the throughput of the wifi wont be saturated since a voip call required 84kbps on asterisk server, so i would like to get so understand, since voip is different of normal packet transmission where the jitter is not important.
    Thank you in advance for ansswer, and your post have been very instructive for me

    ReplyDelete
  16. Hi Andrew, I was studying for the CWAP exam and needed some more info on ED threshold and found your post with my internet search. Great article! And thanks for sharing and I was able to learn something plus I will add this to my CWAP study resources. Thanks, Dale

    ReplyDelete