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.