Distributed Coordination Function (DCF)¶
The Distributed Coordination Function (DCF) application implements the standard 802.11 random-access CSMA/CA protocol. The entire DCF protocol is implemented in C code. All MAC interactions and timing parameters are specified in code and can be easily modified for custom MAC designs based on the standard DCF.
Parameters¶
Contention Window Bounds¶
The DCF code tracks the state of the node’s contention window with a contention window exponent variable named gl_cw_exp. The contention window exponent is bounded by two parameters: gl_cw_exp_min and gl_cw_exp_min. These values dictate the minimum and maximum contention window exponents, which bound the actual contention window. The contention window CW and gl_cw_exp exponent are related by the expression:
By default, gl_cw_exp_min is assigned a value of 4, giving a minimum contention window of 15 slots, and gl_cw_exp_max is assigned a value of 10, giving a maximum contention window of 1023 slots.
RTS Threshold¶
The 802.11 standard distinguishes between “short” packets, which are sent directly without reservation of the medium and “long” packets, which invoke the the Request-to-Send (RTS) / Clear-to-Send (CTS) procedure prior to data transmission. The distinction between these two types of packets is dictated by the gl_dot11RTSThreshold parameter. Packets whose length exceed this threshold are considered “long” and use RTS/CTS.
By default, gl_dot11RTSThreshold is set to 2000 bytes. This treats all outgoing MPDUs as “short” packets and effectively disables RTS/CTS.
The DCF honors RTS/CTS receptions independent of the node’s gl_dot11RTSThreshold value.
Retry Limits¶
Retry limits dictate the operation of the DCF Recovery Procedure. The short and long retry limits are controlled by the gl_dot11ShortRetryLimit and gl_dot11LongRetryLimit parameters respectively. These parameters specify the maximum number of times a given short/long packet will be re-transmitted unsuccessfully before it is dropped.
By default, gl_dot11ShortRetryLimit is assigned a value of 4 and gl_dot11LongRetryLimit is assigned a value of 10.
MAC Timing Values¶
By default the DCF implementation adheres to the 802.11 standard’s MAC timing values. All timing values are specified as variables in the DCF C code and can be changed. The gl_mac_timing_values variable is a structure with the following fields:
| Parameter | Description |
|---|---|
u16 t_slot |
Slot time (µsec) |
u16 t_sifs |
SIFS - Short Interframe Space (µsec) |
u16 t_difs |
DIFS - DCF Interframe Space (µsec) |
u16 t_eifs |
EIFS - Extended Interframe Space (µsec) |
u16 t_phy_rx_start_dly |
Time between the first sample entering the PHY Rx and the assertion of the RX_START event (µsec) |
u16 t_timeout |
ACK Timeout (µsec) |
Wireless Tx¶
- There are three types of packets which are transmitted wirelessly.
- Unicast Data and Management Frames: data-bearing packets addressed to a single wireless device
- Multicast Data and Management Frames: data-bearing packets addressed to many/all wireless devices
- Control Frames: packets created by the DCF to coordinate medium access
Unicast Data and Management Frames¶
Unicast Data and Management frames have a non-multicast receiver address and invoke the 802.11 Recovery Procedure when transmission failures occur. These packets are divided into Short Frames, which are directly transmitted, and Long Frames which use RTS/CTS for medium reservation.
Short Frames¶
Short frames require no medium reservation. The Tx Controller A is used to access the medium and invoke an ACK timeout. If an ACK is received during the timeout the transmission is deemed successful. If not, the Recovery Procedure is invoked.
Long Frames¶
Long frames are preceded by an RTS/CTS exchange. The Tx Controller A is used to access the medium, transmit an RTS, and invoke a CTS timeout. If a CTS is received the long frame is transmitted using the Tx Controller A. If a CTS is not received the Recovery Procedure is invoked.
Multicast Data and Management Frames¶
Multicast Data and Management frames are addressed to a multicast address. These packets are always transmitted once without an RTS/CTS exchange and no ACK response is expected. Multicast transmissions are never retransmitted and are always marked as successful.
Beacons¶
Beacon frames are used to communicate various parameters describing a BSS (wireless network) at regular intervals. The 802.11 standard provides strict rules on the timing of these beacon transmissions. For example, the next frame transmitted immediately following a Target Beacon Transmission Time (TBTT) must be a beacon. This means that beacon transmissions can be interleaved with retransmissions of data packets. Therefore, the DCF must be responsible for handling beacon timing.
The MAC Interface Core implements a programmable timer which tracks the Target Beacon Transmission Time (TBTT). The DCF polls this timer to decide when a beacon should be transmitted. The interval between TBTTs is programmable.
Beacon Tx by Infrastructure APs¶
In an infrastructure network (i.e. high MAC application is the Access Point), the DCF will transmit a beacon as soon as possible following a TBTT. Because Tx Controller A may be actively being used during this time for a different packet, the DCF cannot use it to transmit a beacon. Instead, the DCF uses Tx Controller C to transmit the beacon at the appropriate time.
Beacon Tx by Ad-hoc Node¶
In an ad-hoc mode (i.e. high MAC application is the Ad-hoc Client), there are further challenges because each device in the ad-hoc network is responsible for sending beacons. However, the standard is careful to ensure that on average only one member of the ad-hoc network sends a beacon on each TBTT. Furthermore, which member is responsible for transmitting the beacon is chosen at random in order to minimize issues due to hidden nodes. Each device in the ad-hoc network begins a random backoff period immediately following the TBTT. Whichever device chooses the lowest backoff will transmit its beacon first. All other devices that receive that beacon cancel their own pending beacon transmissions. Every node which receives a beacon adopts the MAC Time from the beacon’s timestamp. This MAC Time update ensures all nodes share a common time base for scheduling future beacon transmissions. This behavior is part of the 802.11 Timing Synchronization Function (TSF).
Multicast Buffering¶
The DCF implements the standard DTIM multicast buffering scheme in infrastructure networks. Stations can power down their radios (i.e. enter a “doze” state), the only safe time to send multicast frames is at a time when all stations plan to be awake. This time is immediately following a TBTT where the DTIM count is zero. At this time, an AP is allowed to dequeue all buffered multicast frames. Like beacon transmissions, these multicast data transmissions may defer ongoing Recovery Procedure operations in Tx Controller A. As such, Tx Controller D is used for the transmission of multicast data frames when DTIM multicast buffering is enabled.
Control Frames¶
Control frames are short packets created by the MAC to coordinate medium state.
RTS¶
The DCF will transmit an RTS using Tx Controller A when the high MAC application requests long unicast frame be transmitted.
CTS¶
A CTS is sent in response to a valid RTS reception if the Network Allocation Vector (NAV) is clear. The CTS is transmitted using Tx Controller B a SIFS interval after the RTS reception.
ACK¶
An ACK is sent in response to a valid unicast reception. The ACK is transmitted using Tx Controller B a SIFS interval after the data reception.
Wireless Rx¶
The DCF monitors the MAC Interface Core for new RX_START events, indicating the start of a new wireless reception. The DCF code begins processing the frame while the reception is ongoing. For example, the code prepares an ACK packet while a paylaod is still being received. This ACK is then submitted for transmission only if the received checksum is correct. All processing of wireless receptions is implemented in the frame_receive() function.
Control Frame Rx¶
RTS¶
When a valid RTS is received, the DCF checks the NAV state. If the NAV is zero the DCF transmits a CTS; otherwise the RTS is dropped and no CTS is transmitted.
CTS¶
A CTS received in response to an RTS cancels the timeout and retransmission of an RTS. It then triggers the transmission of an MPDU for which an RTS was sent. Other CTS receptions update the NAV.
ACK¶
A ACK received in response to a data transmission cancels the timeout and any further retransmissions. It marks the successful completion of the transmission of a unicast frame.
Data Frames¶
Received data frames are delivered to the high MAC application for further processing. If applicable, they may trigger an ACK control packet transmission.
Recovery Procedure¶
An important role of the 802.11 DCF is to detect the presence of transmission failures and properly recover from those errors through the use of a retransmission mechanism. The organization of this section is a series of examples that build on one another and show corner cases in the behavior. The retransmission mechanism in 802.11 is further complicated by the presence of RTS/CTS medium reservation handshakes prior to the transmission of an MPDU, so examples are broken up into sections depending on whether RTS/CTS is used (i.e. if an MPDU is “short” or “long”). Without loss of generality, the examples in this document assume the following parameters:
dot11ShortRetryLimit= 7dot11LongRetryLimit= 4aCWmin= 15aCWmax= 1023
Overview and Terminology¶
Fig. 4.4 Legend
The figures above are not drawn to scale. The presence of the events shown in the legend above is used to indicate only their existence and not their relative size to one another. Furthermore, the presence of a backoff interval is not shown as increasing in duration with an increasing contention window. In fact, it is important to keep in mind that any given random draw of a backoff can produce a 0-duration backoff. The figure will show this event with the full backoff event regardless.
| Term | Definition |
|---|---|
| SRC | Short Retry Count of MPDU |
| LRC | Long Retry Count of MPDU |
| SSRC | Station Short Retry Count |
| SLRC | Station Long Retry Count |
| CW | Contention Window |
The above table summarizes the terms used in the figures below. A station is responsible for maintaining an SRC and LRC for each MPDU it intends to transmit. The SRC and LRC are used for controlling retransmissions of the MPDU in the event of a failure. Additionally, a station maintains an SSRC and SLRC that are global to the station and not tied to any particular MPDU. The SSRC and SLRC are used for controlling the current CW of the station.
Short MPDUs (MPDU length <= dot11RTSThreshold)¶
Example S.1¶
Fig. 4.5 Example S.1
The above example shows the ideal scenario for the transmission of 2 MPDUs. The reception of an ACK after each MPDU transmission keeps all the associated retry counts in the originating station at their minimum along as well as the contention window.
Example S.2¶
Fig. 4.6 Example S.2
The above example shows a scenario where 2 MPDUs are ultimately successful. However, the first transmission attempt of the first MPDU does not result in the successful reception of an ACK. Instead, a timeout occurs and the originator infers a transmission failure. The illustrated behavior in the originator’s retry counts and contention window are described by the following paragraphs in the standard:
Every STA shall maintain a STA short retry count (SSRC) … which shall take an initial value of 0. The SSRC shall be incremented when any short retry count (SRC) … is incremented. … The CW shall take the next value in the series every time an unsuccessful attempt to transmit an MPDU causes either STA retry counter to increment, until the CW reaches the value of aCWmax.
—Excerpt A of 10.3.3 of 802.11-2016
The CW shall be reset to aCWmin after every successful attempt to transmit a frame containing all or part of an MSDU or MMPDU, … .
—Excerpt B of 10.3.3 of 802.11-2016
The SRC … and the SSRC shall be incremented every time transmission that MPDU fails. This SRC and the SSRC shall be reset when transmission of that MPDU succeeds.
—Excerpt A of 10.3.4.4 of 802.11-2016
In other words, the SRC increments because of the MPDU transmission failure. The SSRC increments because the SRC increments. The CW increases because the SSRC increments. When an ACK is received in the second attempt of MPDU 1, Section 10.3.4.4 dictates that the success of that MPDU causes the SRC and the SSRC to be reset. Section 10.3.3 dictates that the successful delivery of the MPDU also resets the CW.
Example S.3¶
Fig. 4.7 Example S.3
The above examples shows a scenario where the no MPDU transmission ever succeeds. As in Example S.2, Excerpt A of Section 10.3.3 of 802.11-2016 dictates that each failure to deliver the transmission causes an increase in the SRC, SSRC, and the CW. The termination of retransmissions is dictated by the following excerpt from the 802.11 standard:
Retries for failed transmission attempts shall continue until the SRC … is equal to dot11ShortRetryLimit … . When [this limit] is reached, retry attempts shall cease, and the MPDU … shall be discarded.
—Excerpt B of 10.3.4.4 of 802.11-2016
On the 7th failure, the SRC increments from 6 to 7. At this moment, the SRC equals the dot11ShortRetryLimit, causing the MPDU to be discarded. Simultaneously, Excerpt A of Section 10.3.3 of 802.11-2016 from Example S.2 dictates that the SSRC increase from 6 to 7 due to the increment operation of the SRC. At this point in time, the SSRC equals the dot11ShortRetryLimit as well. This event triggers the following behavior:
The CW shall be reset to aCWmin … when SSRC reaches dot11ShortRetryLimit.
—Excerpt C of 10.3.3 of 802.11-2016
As such, the 2nd MPDU begins with a fresh CW minimum. However, it is important to note that the SSRC itself is not reset, so the next MPDU begins with an SSRC of 8.
Example S.4¶
Fig. 4.8 Example S.4
The above example extends Example S.3 to a third MPDU transmission. The main behavior to notice is that, while MPDU 2 began with a minimum contention window (for reasons explained in Example S.3), MPDU 3 begins with a maximum contention window. In general, the contention window does not reset with every new MPDU. In the event of a string of failures, it will only reset when the SSRC exactly equals the dot11ShortRetryLimit.
Long MPDUs (MPDU length > dot11RTSThreshold)¶
Example L.1¶
Fig. 4.9 Example L.1
The above example shows the ideal scenario the transmission of 2 MPDUs. Each MPDU transmission is initiated with an RTS control frame. A successful CTS response to that RTS transmission instructs the originator to attempt a transmission of the MPDU. A reception of a successful ACK in response to that MPDU transmission keeps all counts and contention window at station at their minimum values.
Example L.2¶
Fig. 4.10 Example L.2
This example shows a type of failure that can occur in the attempted transmission of a long MPDU. If an ACK is not received in response to the transmission of the long MPDU, then the following excerpts of the 802.11 standard applies:
Every STA shall maintain a … STA long retry count (SLRC), … which shall take an initial value of 0. … The SLRC shall be incremented when any long retry count (LRC) … is incremented. The CW shall take the next value in the series every time an unsuccessful attempt to transmit an MPDU causes either STA retry counter to increment, until the CW reaches the value of aCWmax.
—Excerpt D of 10.3.3 of 802.11-2016
The LRC for an MPDU … and the SLRC shall be incremented every time transmission of that MPDU fails. This LRC and the SLRC shall be reset when transmission of that MPDU succeeds.
—Excerpt C of 10.3.4.4 of 802.11-2016
The failure to receive an ACK for the long MPDU causes both the LRC and and the SLRC to increment. The increment operation on the SLRC causes the CW to increase to its next value. When the ACK is received in the second attempt, the CW is reset to its minimum value according to Excerpt B of Section 10.3.3 of 802.11-2016 from Example S.1. The SLRC is also reset to zero as explained by the following excerpt:
The SSRC shall be reset to 0 when a CTS frame is received in response to an RTS frame, when a BlockAck frame is received in response to a BlockAckReq frame, when an Ack frame is received in response to the transmission of a frame containing all or part of an MSDU or MMPDU that is contained in a PSDU of length less than or equal to dot11RTSThreshold, or when a frame with a group address in the Address 1 field is transmitted. The SLRC shall be reset to 0 when an Ack frame is received in response to transmission of a frame containing all or part of an MSDU or MMPDU that is contained in a PSDU of length greater than dot11RTSThreshold, or when a frame with a group address in the Address 1 field is transmitted.
—Excerpt E of 10.3.3 of 802.11-2016
Notably, the above excerpt described incorrect behavior in the 2012 version of the standard and was corrected fo the 2016 release.
Example L.3¶
Fig. 4.11 Example L.3
This example shows a type of failure that can occur in the attempted transmission of a long MPDU. A failure is inferred if a CTS is not received after the transmission of an RTS.
After an RTS frame is transmitted, the STA shall perform the CTS procedure, as defined in 10.3.2.7. If the RTS frame transmission fails, the SRC for the MSDU or MMPDU and the SSRC are incremented.
—Excerpt D of 10.3.4.4 of 802.11-2016
Furthermore, Excerpt A from 10.3.3 of 802.11-2016 in Example S.1 applies here as well, so the contention window immediately increases to 31 after the post-RTS timeout. The second attempt of the first MPDU begins with a new RTS transmission. When a CTS is received in response to that RTS, the following excerpt instructs our behavior:
The SSRC shall be reset to 0 when a CTS frame is received in response to an RTS frame … .
—Excerpt F of 10.3.3 of 802.11-2016
Note that resetting the SSRC to 0 does not indicate that the contention window shall be reset. As such, the CW remains at 31 during the transmission of the MPDU. Upon the reception of the MPDU’s ACK, the CW is reset to its minimum value according to Excerpt B of Section 10.3.3 of 802.11-2016 from Example S.1.
Example L.4¶
Fig. 4.12 Example L.4
In this example, we see the error introduced in Example L.2 taken to its limit when the maximum retransmission limit is reached. After the 4th failure to transmit the long MPDU, the LRC increments to 4. At this point in time, the following excerpt from the standard binds:
Retries for failed transmission attempts shall continue until the … LRC for the MPDU … is equal to dot11LongRetryLimit. When either of these limits is reached, retry attempts shall cease, and the MPDU … shall be discarded.
—Excerpt E of 10.3.4.4 of 802.11-2016
As such, the MPDU is discarded since the LRC hit the dot11LongRetryLimit. At the same moment, the SLRC reaches dot11LongRetryLimit as well, thereby enacting the following passage:
The CW shall be reset to aCWmin … when SLRC reaches dot11LongRetryLimit … .
—Excerpt G of 10.3.3 of 802.11-2016
As such, MPDU 2 begins with a minimum contention window. The SLRC, however, remains at a value of 4 at the beginning of MPDU 2.
Example L.5¶
Fig. 4.13 Example L.5
In this example, we see the error introduced in Example L.3 taken to its limit when the maximum retransmission limit is reached. Since RTS transmissions count as “short” frames, this example is actually equivalent to Example S.3.
Example L.6¶
Fig. 4.14 Example L.6
This example mixes the long and short failures introduced respectively in Example L.2 and Example L.3, respectively. In this example, an RTS transmission fails 6 times. On the 7th attempt, however, a CTS is received. According to Excerpt F from 10.3.3 of 802.11-2016 from Example L.3, the SSRC is reset to 0 at this time. Neither that SRC nor the CW are reset at this time. This point in particular is often misunderstood. The reset of an SSRC to 0 due to the successful reception of a CTS does not coincide with the reset of the SRC. Excerpt A of Section 9.3.4.4 of 802.11-2016 from Example S.1 does not apply here. That excerpt very specifically applies to “a frame that requires acknowledgment.” This is not true for the RTS that was just successful.
The successful reception of the CTS then causes then MPDU to be transmitted. Failure to receive an ACK for this MPDU causes the LRC and SLRC to increment. The CW would have also increased had it not already been at its maximum value. From this point forward, the behavior of the example matches Example L.2. Notice that having a dot11ShortRetryLimit of 7 and a dot11LongRetryLimit of 4 actually allows for a total of 10 “attempts” to transmit (6 RTS-only transmissions followed by 4 RTS and MPDU transmissions).
Example L.7¶
Fig. 4.15 Example L.7
This example differs from Example L.6 in one important respect: the 10th RTS transmission fails. At this point in time, the SRC finally increments up to 7. Since this is the dot11ShortRetryLimit, the MPDU is discarded. However, the SSRC increments up to a value of 1 since it had been at 0 because of the prior RTS successes. As such, since the SSRC does not equal dot11ShortRetryLimit, the CW is not reset for the beginning of the second MPDU.