Sunday, August 24, 2014

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




Friday, April 18, 2014

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.

Monday, March 24, 2014

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.

Sunday, February 2, 2014

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.


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