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).

STA-AP: WPA2-PSK Connection Establishment

WPA2 vs WPA Comparison

	WPA2	WPA
Encryption Type	AES	RC4
PTK length	384(KCK,KEK,TK)	512(KCK,KEK,TK,MIC)
Message integrity	Uses TK	Uses MIC
Group Key	TKIP or CCMP	TKIP
Group Key message	M3	Group-M1
Information Element	RSN IE	WPA IE

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 

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.

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.

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).