Protocol Stack in Wi-Fi Chipsets

Wi-Fi is found in various devices like Mobile phones, Laptops, Access points, TVs etc. The number of types of devices (or things) with Wi-Fi is set to grow with the advent of "Internet of Things". The various layers of the protocol stack in Wi-Fi devices are shown in the below figure. How are these layers implemented in different types of devices? What parts of the the protocol stack are implemented in Wi-Fi chipsets?

The protocol stack consists of the MAC, PHY, MLME, Supplicant (which handles security), Data Stack and Applications.

FullMAC and SoftMAC

Wi-Fi chipsets can be classified into two types based on whether they include the MLME or not.
The two types are "SoftMAC" and "FullMAC" (as defined by the Linux wireless community).

What is the advantage of having (or not having) the MLME in the Wi-Fi chipset?
MLME is MAC Sublayer Management Entity and takes care of various management procedures like Assocation, Authentication etc. MLME in the chip allows the host processor to save power by offloading certain functionality (most significant being roaming) to the chip. On the other hand, this can increase the cost (more memory, more processing etc) of the Wi-Fi chip.
"FullMAC" (why not FullMLME?) is suitable for battery powered mobile devices and "SoftMAC" is suitable for devices that are mains powered.

Another possible split is to have part of MLME in the chip and the rest outside. For e.g., the chip may handle beacons and probe request/response but not authentication and association.

FullStack

The classification of "Soft" and "Full" MAC can be applied to the Wi-Fi chipsets in almost all the usual (say laptops, Phones, Access Points) Wi-Fi devices. However, as Wi-Fi gets into more "things", the chipsets are also required to support more layers of the stack.
Consider the case of a wireless speaker that doesn't have its own processor. The Wi-Fi chipset itself could provide all the layers of the protocol stack. Two possible "FullStack" (Note: This is how I call it and is not a standard term) options are shown below.

Examples

The usual (do note that some implementations may vary) stack architecture in different types of devices is shown below with some examples.

Device Type	Wi-Fi Chpset Stack Architecture	Upper Layers of the Stack	Chipset Example(s)
Mobile Phone	FullMAC	Application Processor	BCM4335 and other broadcom chipsets found in Smart phones
Laptop	SoftMAC	Application Processor	Intel Wi-Fi chipsets for laptops
Home/Small Access Point	SoftMAC	Application Processor	QCA9880
Enterprise (Light Weight) Access Point	SoftMAC	Wireless LAN Controller	Chipsets in Cisco 3700 Aironet APs Not clear who makes the Wi-Fi chipset/radio
Dumb things connected to network/internet	FullStack	No upper layers at all (All layer in the chip) or A small processor/micro controller in the "thing"	QCA4002 and QCA4004

11n Block Acknowledgement

Every unicast frame in the initial 802.11 standard required a positive acknowledgement. 802.11e introduced the concept of "Block Acknowledgement": Single acknowledgement for multiple frames. Block Ack along with A-MPDU Aggregation is used in 11n to achieve significant improvement in application throughput.

Lets understand the 11n Block Ack by answering some basic questions.
"BA" in the below text means "Block Acknowledgement".

Q: Is it necessary to setup a BA before it can be used?
A: Yes. A BA session must be setup in each direction (Tx and Rx). The session needs to be setup by the device that intends to receive the BA. The session is setup using ADDBA request/response. A DELBA can be used to tear down the session. ADDBA and DELBA are BA action frames.

title "BA Setup"

note over dev1,dev2: "Connected"
opt Dev1 decides to enable BA (for it Tx Data)
dev1->dev2: ADDBA Request (BA Params)
note over dev2: Dev2 can accept or reject the request.\n It can also change the BA parameters.
dev2->dev1: ADDBA Response (Status, BA Params)
note over dev1:"Can now send A-MPDU"
end

opt Dev2 decides to enable BA (for it Tx Data)
note over dev2:"I want to enable BA (for my Tx Data)"
dev2->dev1: ADDBA Request(BA Params)

note over dev1: Dev1 can accept or reject the request.\n It can also change the BA parameters.
dev1->dev2: ADDBA Response(Status, BA Params)
note over dev2:"Can now send A-MPDU"
end

The following parameters are exchanged in ADDBA messages:

• A-MSDU supported in MPDU or not
• BA policy (Immediate or Delayed)
• Traffic Identifier
• Number of MPDUS  that can be acknowledged in one BA
• The response may indicate a value lower than the request
• Starting Sequence Number (only in ADDBA request). This is the sequence number of the first packet that would be acknowledged using the BA.

Q: What are the different types of BA?
A: There are two different types of BA: Immediate BA and Delayed BA, which are explained in the below diagrams.

title "Delayed vs Immediate Block Ack"
dev1->dev2: Data Frame (A-MPDU with multiple MPDUs)
alt Delayed Block Ack
dev1->dev2: BA Request
dev2->dev1: Ack
dev2->dev1: Block Ack
dev1->dev2: Ack
else Immediate Block Ack
dev1->dev2: BA Request
dev2->dev1: Block Ack
end

Q: I've captured a 11n air-trace and can see a BA even without BA Request. Why is it different from Immediate and Delayed BA?
A: That is true. You would usually find that a BA is sent event without a BA Request. That is because the BA request is implicit. What you have seen is an "Immediate BA with implicit BA request". 

title Immediate BA with Implicit BA Request
dev1->dev2: Data Frame (A-MPDU with multiple MPDUs)\nAck Policy=Implicit BA
dev2->dev1: Block Ack

Q: What is a BA bitmap?
A: A BA bitmap along with the starting sequence number indicates the packets that are being acknowledged.  Each bit acknowledges one packet and sequence number of the packet is equal to starting sequence number + bit number. For e.g., the BA shown in the below diagram acknowledges packets 3 and 4.

Q: What is a compressed BA?
A: BA as defined originally in 802.11e allowed individual MSDUs to be acknowledged and the bitmap was 128 bytes long. 11n only allows MPDUs to be acknowledged and the bitmap is 8 bytes in long. The BA with 8 byte bitmap is known as compressed BA.

Q: Why does my device send some BA request frames even when there is no frame to be acknowledged?
A: A BA request is also used to change the starting sequence number. One example when this would be happen is if the transmitter has sent some frames without using aggregation (and hence acknowledged using normal Ack) and later wants to send some aggregated data. The transmitter can update the receiver with the new starting sequence number by sending a BA request. The receiver would respond with a zero bitmap BA in response to such a request.

PHY rate and UDP throughput

802.11ac supports a maximum speed of ~433 Mbps on a 80 Mhz channel. Does this mean the application level throughput between two 11ac devices is 433 Mbps? Not really. "433 Mbps" is the Maximum PHY rate and this is what the device manufacturers would advertise. Application throughput depends on various factors that vary from time to time and device to device. Some factors are the type of data (TCP/UDP etc), Speed of the device, Channel conditions etc. Apart from the variable factors there are also some overheads in the 802.11 protocol itself. This article tries to describe the 802.11 overheads and calculate the maximum UDP throughput (under _ideal_ conditions) for a given PHY rate.

Overheads in 802.11 data transmission

The overheads in 802.11 data transmission are illustrated in the above figure.

They are:

• Fixed wait : DIFS or AIFS
• Random Wait 
• PHY Header
• MAC Header
• MAC FCS
• SIFS
• ACK/Block ACK (PHY Header + ACK Data + FCS)

Along with the above, the data frame has the following overheads

• SNAP Header
• IP Header
• UDP Header

UDP Throughput

Maximum UDP throughput (for a UDP payload of 1500 bytes) in various 802.11 modes is shown below.

Mode	Maximum PHY Rate(Mbps)	PHY Data time (us)	PHY HDR time (us)	ACK time (us)	Maximum UDP throughput (Mbps) (Payload size = 1500 bytes)
11g	54	232	120	34	31.1
11a	54	232	126	40	30.2
11n (20 MHz)	72.2	176	142	56	32.1
11n (40 MHz)	150	84	142	56	42.6
11ac (20 MHz)	86.7	148	146	60	33.9
11ac (40 MHz)	200	64	146	60	44.4
11ac (80 MHz)	433	32	146	60	50.4

Updated on 20/08/2014: Corrected 11ac 20 MHz max rate (MCS9 is not allowed in 20 MHZ 1SS).

Isn't it surprising that a PHY rate of 433 Mbps results in a throughput of just 50.4 Mbps? Well, that is why aggregation is essential for achieving good throughput. Lets look at the throughput when MPDU aggregation is used (in 11n and 11ac).

Throughput with A-MPDU

Mode	Maximum  PHY Rate(Mbps)	A-MPDU  size	Maximum Throughput (UDP Payload=1500,  A-MPDU spacing=0)
11n (20 MHz)	72.2	8192	56.3
	72.2	16384	62
	72.2	32768	65.5
	72.2	65536	67.3
11n (40 MHz)	150	8192	97.1
	150	16384	116.1
	150	32768	128.3
	150	65536	136
11ac (80 MHz)	433	8192	169.5
	433	16384	241
	433	32768	305.3
	433	65536	352.9

The impact of aggregation on throughput is better understood with the below graph.

Approximations/Assumptions

The Maximum possible UDP throughput in the above calculations should be fairly accurate. However, please note that:

• An average random wait of 8 slots is considered (CWMax=15)
• PHY "SERVICE" bits (16) are not considered
• MPDU PAD bits are not considered
• Tail bits (6) are not considered
• Transmission time is rounded to nearest symbol time (4 micro seconds)
• A different UDP payload size would result in a different throughput number (larger the payload size better is the throughput)
• "Ideal" conditions are assumed, e.g., an RF shield room 

The spreadsheets used for the above calculations can be downloaded from here.

STA-AP: WPS STA PIN Procedure

WPS (Wi-Fi Protected Setup) is a WFA Certification program that is intended to allow the users to easily connect to a secure home or small office Wi-Fi network. It is also used for establishing the connection between two Wi-Fi Direct devices.

Connection establishment between a STA and AP using WPS can be done in of the the following ways:

• Push Button Configuration (PBC): By pressing a physical/virtual button on the STA and AP
• PIN
• Enter STA PIN in the AP
• Enter AP PIN in the STA
• A good description of this method and its vulnerabilities can be found here
• NFC (Near Field Communication)
• This is "out of band" method (PBC and PIN are "in band"). 
• An example of this is the "S-Beam"

This article is about what happens between an STA and AP in the "STA PIN in the AP" method.

Basic steps in WPS

Connection establishment to a WPA2 network using "In Band" WPS procedure consists of the following steps:

• Authentication and Association (Round 1)
• WPS EAP Procedure
• EAP Start, Identity request/response
• WPS registration procedure(M1 to M8)
• EAP Done (Ends with an EAP Failure as this is not real Network authentication) 
• Deauthentication
• Authenticaton and Association (Round 2)
• EAPOL 4-way handshake (WPA2 Keys)

WPS PIN procedure may fail in the following cases:

• STA(Enrollee) initiates the procedure before AP (registrar) has the PIN
• This is not a "total" failure. STA understands that it has to wait and retry.
• User enters an incorrect PIN in the AP

WPS STA PIN : Sequence Diagram

The below sequence diagram is based on tests run between a mobile phone (STA) and an AP. The sniffer logs for the tests can be found here.

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