Sunday, December 15, 2013

802.11e (Quality of Service) : EDCA

Have you ever visited a famous temple in India? In many temples, there are different "queues" based on the ticket price. If you buy a more expensive ticket, it is most "likely" that your queue will move faster compared to the less expensive one.

802.11e provides a similar facility for different types of user data in a WLAN. The different types of user data are: Voice, Video, Best Effort and Background. 802.11e defines Hybrid Coordination Function (HCF), that includes two new channel access methods:
  • HCF Controlled Channel Access (HCCA). This is based on PCF and like PCF, is not used in real-world implementations.
  • Enhanced Distributed Channel Access (EDCA). This is based on DCF and is a mandatory feature for WMM certification.

Channel Access in DCF

As EDCA is based on DCF, lets first understand how DCF works.
802.11 works on the principles of "carrier sensing" and "collision avoidance". Carrier sensing is achieved through Clear Channel Assessment(CCA) and/or Network Allocation Vector (NAV).

Collision avoidance is achieved using a back-off procedure. The channel access procedure in DCF is depicted in the below diagram.

Channel Access in DCF
The above diagram considers an example in which two stations have data to transmit.

  1. "BUSY":  The stations initially find the medium to be busy (some other station already transmitting). The stations find this either through CCA or NAV.
  2. "DIFS Wait": After the channel is found to be free, both stations need to wait for a fixed duration of DIFS (DCF Interframe Space).   
    • DIFS = SIFS + 2*slot_time
      • slot_time = 9 (OFDM), 16 (DSSS) micro seconds
  3. "Contention": The stations now contend for the medium using random wait.
    • 0 <= Random Wait <= Contention Window (CW)
    • CWMin <= CW <= CWMax
      • CW = 2^x - 1  where x = (4,31)(for OFDM)
      • CWMin = 2^4 - 1 = 15
      • CWMax = 2^31 - 1 = 1023  
  4. "Data": STA1 uses a lower random wait and wins the medium
  5. "SIFS", "ACK": After the data frame is transmitted, the AP waits for SIFS (< DIFS) before sending an ACK.
    • SIFS = 10 (2.4 GHz) or 16 (5 GHz)  micro seconds
  6. Both stations need to contend for the medium after the "ACK" (i.e., start from "Step 2: DIFS wait").

Channel Access in EDCA

EDCA improves on DCF by changing the IFS, Contention Window and the Contention free period based on the "Access Class" of the data. 

EDCA IFS

EDCA uses two Interframe Spaces: SIFS (Same as the one used in DCF) and AIFS. AIFS is similar to DIFS but it varies based on the type of data.
  • AIFS = SIFS + AIFSN * slot_time
  • AIFS Voice, AIFS Video = DIFS 
    • SIFS + 2 * slot_time
  • AIFS Best Effort
    • SIFS + 3 * slot_time
  • AIFS Background
    • SIFS + 7 * slot_time
EDCA Contention Window
The maximum and minimum values of contention window values are dependent on the type of data. The values of CWMin and CWMax are shown below (in slots). Please note that Contention Window is equal to  2^x - 1. The minimum and maximum values are derived from minimum and maximum values of x. x is incremented whenever a transmission failure is detected (e.g., No ACK is received).

CWMin CWMax
DCF
15 
(OFDM) 
(x = 4)
1023
(x = 10)
EDCA VO
3
(x = 2)
7
(x = 3)
EDCA VI
7
(x = 3)
15
(x = 4)
EDCA BE
15
(x = 4)
1023
(x = 31)
EDCA BK
15
(x = 4)
1023
(x = 10)

The effect of AIFS and modified CWMin values can be seen in the below figure.


As a result of the modified wait period, Voice traffic has the highest "probability" of accessing the medium. Video comes next followed by Non-QoS (DCF), Best Effort and Background.

EDCA Contention Free Period (TXOP)
Contention free period can be defined as the duration during which a station can send or receive data without contending for the medium. For e.g., in case of DCF, the contention free period starts with "DATA" and ends after receiving an "ACK". So the contention free period is effectively for one frame. EDCA allows this to be more than one frame and is called a TXOP (Transmission Opportunity).

The TXOP limits are set by the QoS AP. TXOP limit is described in terms on number of 32 micro second intervals.

Typical values for TXOP limits for OFDM (a/g/n) are

  • Voice: 47 (47 *32 =  1504 micro seconds)
  • Video: 94 (94 * 32 = 3008 micro seconds)
  • Best Effort, Background: 0 (Only one frame at a time and then contend again for the medium)

EDCA parameters advertised by the QoS AP

The below snippet from an air-trace shows the EDCA parameters from WMM information element in the beacon of a QoS AP. Note: ECWmin/ECWmax is "x" describe earlier (CW = 2^x -1).


Saturday, November 16, 2013

STA-AP: WPA2-PSK Connection Establishment



WPA2 vs WPA Comparison

WPA2WPA
Encryption TypeAESRC4
PTK length384(KCK,KEK,TK)512(KCK,KEK,TK,MIC)
Message integrityUses TKUses MIC
Group KeyTKIP or CCMPTKIP
Group Key messageM3 Group-M1
Information ElementRSN IEWPA IE


Saturday, October 5, 2013

STA-AP: WPA-PSK Connection Establishment (Sequence Diagram)



Summary

  • Probe response and beacon frames include the WPA IE (AP WPA capabilities)
  • Association request from STA includes the WPA IE (STA WPA capablities)
  • IEs in EAPOL messages and corresponding probe/beacon/assoc messages should match
  • WPA Pairwise Key (TKIP) is dervied from the following
    • STA MAC address
    • AP MAC address
    • PMK (Pairwise Master Key) (PMK = PSK (256 bits))
    • Authenticator (AP) Nonce (A random value genearted by AP)
    • Supplicant (STA) Nonce (A random value generated by STA)
  • Pairwise key consists of 
    • EAPOL KEK (128 bits)
    • EAPOL KCK (128 bits)
    • TKIP TK (128 bits)
    • TKIP MIC Key (128 bits)
  • WPA does not use KEK to encrypt the keys (Q:What is the purpose of KEK in TKIP?)
  • KCK is used for integrity protection of EAPOL messages
  • Group key messages are encrypted using TKIP TK
  • Group key consists of
    • Group Temporal Key (128 bits)
    • Group MIC (128 bits)
  • Group key may be periodically updated by the AP
  • Air-traces used to generate this diagram can be downloaded from here 

Saturday, September 21, 2013

Understanding the Address Fields in 802.11 frames

Address fields are present in the MAC header of 802.11 frames. A frame may contain 4 address fields.


Address fields are 6 octets in length. Address fields are used to indicate Source, Transmitter, Destination, Receiver and BSSID. The address could be a unicast, multicast or broadcast address.

Isn't "Source" same as "Transmitter"? Isn't "Destination" same as "Receiver"?. 
It depends on the type of frames. They could be same (e.g. in Management frames) or different (in Data frames).


The above diagram illustrates the difference between various addresses.
  • SA(Source Address): Source of the data (MSDU)  --> STA1 
  • TA(Transmitter Address) : STA that transmitted the frame --> STA1, AP1, AP2
  • RA(Receiver Address) : Immediate recipient of the frame --> AP1, AP2, STA2
  • DA(Destination Address) : Final recipient of the data (MSDU) --> STA2
  • BSSID (Basic Service Set IDentifier) : Unique identifier of the BSS, e.g,  the MAC address of the AP in an infrastructure network --> AP1, AP2
Are all the 4 address fields always used?
No, they are not. Only Address1 is mandatory. For e.g, CTS frame only has Address1. The remaining fields are filled based on the the frame.

How is each field used?
Address fields are used based on the type of frames: Control, Management and Data.

Control Frames
Management Frames
Data Frames
Address1
RA
RA
RA
Address2
TA(not all)
TA
TA
Address3
Not used
BSSID
BSSID or SA or DA
Address4
Not used
Not used
BSSID or SA

The Address fields in Data frames are based on the direction of the frame:  "To DS" or "From DS".

  • "To DS": Set to 1 in all data frames sent from STA to AP
  • "From DS": Set to 1 in call data frames sent from AP to STA
  • Both "To DS" and "From DS" may be set to 1 if the frame is being relayed between APs.

To DS
From DS
Address 3
Address 4
0
0
BSSID
Not used
0
1
SA
Not used
1
0
DA
Not used
1
1
DA
SA

Note: In case of A-MSDU, SA and DA are part of A-MSDU sub-headers. BSSID is filled in Address3 and Address4 instead of SA and DA.

Address Fields in Sniffer logs
Lets looks at some sniffer traces and examine the address fields.









Sunday, August 25, 2013

STA-AP: Connection Establishment(No Security)

Sequence diagrams are very useful in understanding the interaction between various nodes in an 802.11 network. I will post sequence diagrams of 802.11 scenarios in this blog.
  • The sequence diagrams will be created from "actual" air traces in the network (Notice the frame numbers in the diagram)
  • The air trace used to create the sequence diagram will also be attached
I will start with a very basic scenario: "Connection establishment"
  • Mode: Infrastructure
  • No security (Open Network)


Connection establishment involves the following basic steps:

  • Scan
    • In case of an active scan, the STA would send out a probe request and receive a probe response from the AP.
    • In case of a passive scan, the STA would find the AP by listening to the beacon.
  • Authentication
  • Association

The air-trace for this scenario can be downloaded here.

Sunday, August 4, 2013

Wi-Fi (802.11) PHY Data Rates

Devices supporting the latest 802.11ac (draft) standard are now being certified by the Wi-Fi Alliance. 802.11ac promises various improvements over 802.11n. Starting from the first IEEE 802.11 standard in 1997 to the latest 11ac standard, there have been improvements in various aspects of 802.11 networks - speed of the network being one of the major improvements. This article attempts to explain the PHY data rates of 11b, 11a/g, 11n and 11ac.


Modulation



The above diagram shows the modulation techniques used in different 802.11 PHYsical layers. 802.11 systems support two (Ignoring the optional and obsolete types) types of modulation - DSSS/CCK and OFDM. This article is not going to cover the details of DSSS/CCK (a good intro can be found here) and OFDM. The below figure gives an overview of both the techniques.




Data Rate

DSSS/CCK (11b Date Rates)
DSSS/CCK data symbol is formed by spreading and modulating the data bits. The data rate depends on : 
  • Chips per second (CSec) = 11,000,000
  • Chips per symbol (CSym) = 11 (DSSS) or 8 (DSSS with CCK)
  • Bits per symbol (NBits) = 1 or 2 (DSSS), 4 or 8 (DSSS with CCK)
Data Rate = (CSec/CSym)*NBits

    Chips per second Chips per symbol Bits per symbol Data Rate (Mbps)
    11,000,000 11 1 1
    11,000,000 11 2 2
    11,000,000 8 4 5.5
    11,000,000 8 8 11
    11b Data Rates 

    OFDM

    DSSS/CCK uses the entire available bandwidth as one single channel. OFDM divides the channel into multiple(overlapping) sub-channels. The data rate depends on:
    •  Symbol duration (in other words symbols per second) (SDur)
      • Symbol duration depends on "Guard Interval" between symbols.
    •  Bits per symbol (NBits)
    •  Coding rate (CRate)
      • Some bits are used for error correction and do not carry data 
    • Number of sub-channels (NChan)
      • Depends on channel width(20/40/80/160)
      • 11n/11ac have more sub-channels in the same bandwidth compared to 11a/11g
    Data Rate = (1/SDur)*(NBits*CRate)*NChan

    11a/11g Rates

    Modulation NBits CRate NChan SDur (micro sec) Data Rate (Mbps)
    BPSK 1 1/2 48 4 6
    BPSK 1 3/4 48 4 9
    QPSK 2 1/2 48 4 12
    QPSK 2 3/4 48 4 18
    16-QAM 4 1/2 48 4 24
    16-QAM 4 3/4 48 4 36
    64-QAM 6 2/3 48 4 48
    64-QAM 6 3/4 48 4 54
    11a/11g Data Rates
    Note: The above table shows date rates for 20MHz channel width. 5,10 MHz channel widths are not shown.

    11n/11ac Data Rates

    11n and 11ac data rate improvements are due to:
    • The number of sub-channels in 11n and 11ac is more than 11a and 11g. 
    • Higher coding rate (5/6)
    • 11ac also uses 256-QAM which further increases the data rate.
    • Wider Channels (40,80,160)
    • Multiple Spatial Streams (MIMO) (Nss
    Modulation NBits CRate NChan Data Rate (Mbps)
    SDur=4us
    Data Rate (Mbps)
    SDur=3.6us
    BPSK 1 1/2 52 6.5 7.2
    QPSK 2 1/2 52 13 14.4
    QPSK 2 3/4 52 19.5 21.7
    16-QAM 4 1/2 52 26 28.9
    16-QAM 4 3/4 52 39 43.3
    64-QAM 6 2/3 52 52 57.8
    64-QAM 6 3/4 52 58.5 65
    64-QAM 6 5/6 52 65 72.2
    256-QAM (11ac) 8 3/4 52 78 86.7
    256-QAM (11ac) 8 5/6 52 86.7 96.3
    11n and 11ac Data Rates (20 MHz, 1 SS)
    The entries highlighted are 11ac only rates and the rest are common to 11n and 11ac.
    Updated on 20/08/2014: Note: The last entry,i.e, MCS9 (256 QAM, 5/6 rate) is not allowed in 11ac 20 MHz channel.

    The maximum data rate is achieved with MIMO and maximum channel width.


    Channel Width NBits CRate NChan Data Rate (Mbps)
    SDur=3.6us (Nss=1)
    11n Max Rate
    (Nss=4)
    20 Mhz 6 5/6 52 72.2 288.8
    40 Mhz 6 5/6 108 150 600
    11n Max Data Rates

    Channel Width NBits CRate NChan Data Rate (Mbps)
    SDur=3.6us (Nss=1)
    11ac Max Rate
    (Nss=8)
    20 Mhz 8 5/6 52 96.3 577.8
    (Nss=6)
    40 Mhz 8 5/6 108 200 1600
    80 Mhz 8 5/6 234 433.3 3466.4
    160 Mhz 8 5/6 468 866.7 6933.6
    11ac Max Data Rates 
    Updated on 20/08/2014: Max valid spatial streams for 11ac 20 MHz channels corrected to 6.

    Summary

    The improvement in data rate from 11b to 11ac is due to various factors: OFDM, Wider Channels, QAM, Higher coding rate and MIMO.  The figures below depicts the improvement in data rate due to each factor(excluding MIMO).