Tim Godfrey, GlobespanVirata
Dec 19, 2003 (10:00 AM)
Wireless networks based on IEEE 802.11 have been widely adopted by home users and businesses. New applications such as video and multimedia streaming bring unique and challenging quality of service (QoS) requirements.
The ever-expanding demand for bandwidth has caused network congestion and slowdowns, but home users want multimedia distribution to work perfectly without dropouts or glitches. Network administrators need mechanisms to ensure that applications with stringent QoS requirements will function properly over a congested network. These developments have triggered the development of a QoS enhancement for the 802.11 Wireless LAN.
The carrier sense multiple access (CSMA) technique used in 802.11 is intended to provide fair and equal access to all devices. It is essentially a "listen-before-talk" mechanism. When networks become overloaded, the performance becomes uniformly poor for all users and all types of data.
QoS modifies the access rules to provide a useful form of "controlled unfairness." Data that is identified as having a higher priority is given preferential access to the medium. It will therefore gain access at the expense of the lower priority traffic.
To enable QoS techniques to come to life in WiFi networks, the IEEE 802.11 committee is working on the 802.11e standard. Currently in draft form, this standard defines changes to the operation of the 802.11 media access control (MAC) layer to enable prioritization and classes of service over a wireless LAN. Let's take a closer look at 802.11e and the changes it will provide.
The Legacy MAC
The 802.11-1999 standard defines two channel access mechanisms, called coordination functions. These coordination functions determine when a station is permitted to transmit, and when it must be prepared to receive data. The fundamental mechanism is the distributed coordination function (DCF), which uses the CSMA mechanism. While wired networks implement collision detection on the medium (CSMA/CD), the nature of the wireless medium precludes a reliable collision detection mechanism. WLANs, on the contrary, use collision avoidance (CSMA/CA).
The basic rule of CSMA is listen-before-talk. The PHY provides a clear channel assessment (CCA) signal to the MAC to indicate if any other stations are transmitting. 802.11 includes a virtual carrier sense mechanism to reduce problems with hidden stations. This mechanism is supplemented in 802.11e, but will not be detailed further. The second coordination function is point coordination function (PCF), which will be discussed below.
To keep multiple stations from attempting to transmit simultaneously when another station stops transmitting, a random backoff is used. A station wanting to transmit will generate a random number within a range called the contention window. Once the station senses that the medium is unoccupied for a short time, it starts counting down from the random backoff. If the count reaches zero, it starts transmitting. If another station has selected a lower number and starts transmitting first, the station will hold its current backoff count and resume counting when the medium becomes clear again after the intervening transmission.
802.11 defines a number of frame exchange sequences which can continue without medium contention. The CSMA rules cause a frame exchange sequence to look like continuous activity on the medium. At the end of frame exchange sequences, stations must sense the medium and perform backoff before transmitting again.
The 802.11 standard also defines the optional PCF. This function allows different access rules based on polling by a point coordinator (PC) operating at an access point (AP). The PC uses special control frames to divide the time between beacons into a contention free period (CFP) and a contention period (CP) [Figure 1].
Figure 1: Summary of 802.11 coordination functions during the optional contention free period and the contention period.
During the CFP, the AP maintains control of the medium, polling each station that has requested to be on the polling list, and accepting a frame in response to the poll. There is a continuing exchange of frames going to and from the AP, with no time spent for backoff or contention. Since stations only transmit when polled, there are no collisions. After the AP has completed the polling of all the stations, the CP begins and access using the DCF rules resumes.
Implementation of the PCF is an option, and it has not been widely implemented. Although the PCF appears to have the potential to deliver QoS, there are a number of limitations. The hybrid coordination function defined in 802.11e provides all the advantages and capabilities of the PCF with none of the disadvantages and limitations.
A Hybrid Approach
The Hybrid Coordination Function (HCF) replaces the legacy DCF and PCF in a station implementing 802.11e (A QoS Station, or QSTA). The HCF is mandatory in all QoS stations (QSTAs). Within the HCF, there are two access mechanisms, the enhanced distributed channel access (EDCA) and HCF controlled channel access (HCCA). Unlike the legacy PCF, which used different frame exchange sequences in the contention period and the contention free period, the HCF defines a uniform set of frame exchange sequences that are usable at any time. In summary: HCF = EDCA + HCCA (Figure 1).
Diagram of the draft 802.11e architecture.
The HCF allocates the right to transmit through transmit opportunities (TXOPs) granted to QSTAs. A station may obtain a TXOP through one or both of the channel access mechanisms. A TXOP grants a particular QSTA the right to use the medium at a defined point in time, for a defined maximum duration. The allowed duration of TXOPs are communicated globally in the beacon for stations using EDCA.
The HCF also introduces new acknowledgement (ACK) rules. In the legacy standard, every unicast data frame required an immediate response using an ACK control frame. The HCF adds two new options: no acknowledgement and block acknowledgement. These are specified in the QoS Control field of data frames.
No acknowledgement is useful for applications with very low jitter tolerance, such as streaming multimedia, where the data would not be useful after the delay of a retry. Block acknowledgements increase efficiency by aggregating the ACKs for multiple received frames into a single response. The implementation of block acknowledgement is optional, and will be discussed in more detail below.
EDCA contention access is an extension of the legacy CSMA/CA DCF mechanism to include priorities. The contention window and backoff times are adjusted to change the probability of gaining medium access to favor higher priority classes. A total of eight user priority levels are available. Each priority is mapped to an access category, which corresponds to one of four transmit queues (Figure 3).
Figure 3: Diagram of the EDCA queue architecture.
Each queue provides frames to an independent channel access function, each of which implements the EDCA contention algorithm. When frames are available in multiple transmit queues, contention for the medium occurs both internally and externally, based on the same coordination function, so that the internal scheduling resembles the external scheduling. Internal collisions are resolved by allowing the frame with higher priority to transmit, while the lower priority invokes a queue-specific backoff as if a collision had occurred.
The parameters defining EDCA operation, such as the minimum idle delay before contention, and the minimum and maximum contention windows, are stored locally at the QSTA. These parameters will be different for each access category (queue) and can be dynamically updated by the QoS access point (QAP) for each access category through the EDCA parameter sets. These are sent from the QAP as part of the beacon, and in probe and re-association response frames. This adjustment allows the stations in the network to adjust to changing conditions, and gives the QAP the ability to manage overall QoS performance.
Under EDCA, stations and access points use the same access mechanism and contend on an equal basis at a given priority. A station that wins an EDCA contention is granted a TXOP—the right to use the medium for a period of time. The duration of this TXOP is specified per access category, and is contained in the TXOP limit field of the access category (AC) parameter record in the EDCA parameter set. A QSTA can use a TXOP to transmit multiple frames within an access category.
If the frame exchange sequence has been completed, and there is still time remaining in the TXOP, the QSTA can may extend the frame exchange sequence by transmitting another frame in the same access category. The QSTA must ensure that the transmitted frame and any necessary acknowledgement can fit into the time remaining in the TXOP.
EDCA Admission Control
Contention-based medium access is susceptible to severe performance degradation when overloaded. In overload conditions, the contention windows become large, and more and more time is spent in backoff delays rather than sending data. Admission control regulates the amount of data contending for the medium.
EDCA admission control is mandatory at the AP, and optional at the station. The AP may indicate that it requires stations to support admission control and explicitly request access rights if they wish to use an access category.
Admission control is negotiated by the use of a TSPEC. A station specifies its traffic flow requirements (data rate, delay bounds, packet size, and others) and requests the QAP to create a TSPEC by sending the ADDTS (add TSPEC) management action frame. The QAP calculates the existing load based on the current set of issued TSPECs. Based on the current conditions, the QAP may accept or deny the new TSPEC request. If the TSPEC is denied, the high priority access category inside the QSTA is not permitted to use the high priority access parameters, but it must use lower priority parameters instead. Admission control is not intended to be used for the "best effort" and "background" traffic classes.
Controlled Channel Access
The HCF controlled channel access (HCCA) mechanism uses a hybrid coordinator (HC) to centrally manage medium access. The intent of HCCA is to increase efficiency by reducing the contention on the medium.
The HC has privileged access to the medium because it can initiate a transmission after waiting a shorter time than the shortest backoff delay of any station using EDCA. Under control of the HC, a nearly continuous sequence of frame exchanges can be maintained, with short, fixed delays between frames. The inter-frame delay does not increase with increasing traffic, unlike the contention window used in EDCA access. There is no possibility of collisions, except from stations on the same frequency that are not under control of the HC. HCCA supports parameterized QoS, where specific QoS flows from applications can have individually tailored QoS parameters, and tighter control of latency and scheduling.
802.11e defines new QoS frame types that allow the HC to send any combination of data, poll, and acknowledgement to a station in a single frame. When the HC sends a poll to a QSTA, the QoS control field contains a TXOP limit value that specifies the duration of the granted TXOP.
The HC is responsible for controlling the allocation of time on the medium through the use of polled TXOPs. The HC is guided in its decisions on TXOP allocation through the use of TSPECs. TSPECs are requested by the QSTA, and the QAP may grant or deny a TSPEC request. The handling of TSPECs is described below under the topic of scheduling.
Optional .11e Features
There are a host of optional features defined under the 802.11e specification. These include contention-free bursts, block acknowledgements, a direct link protocol, and active power mode save delivery. Let's look at each in detail starting with contention free bursts.
Contention free bursts (CFBs) are not explicitly listed as an optional feature of 802.11e, but a QSTA or QAP may choose to use CFBs to improve efficiency by eliminating some contention. A CFB may be used when a QSTA or QAP has time remaining in a granted TXOP, and additional data to send. Rather than contending for the medium again as would be required in the legacy standard, 802.11e allows a station to resume transmitting after the short inter-frame space (SIFS) delay. A CFB is a special form of frame exchange sequence that fits within a TXOP. CFBs may be used during TXOPs that were gained under both EDCA and HCCA channel access functions.
The .11e standard specifies methods for the QAP or QSTA to recover in the case of a transmission failure during a granted TXOP. Recovering means that the owner of the TXOP can re-establish operation before any other station is able to access the medium through the normal contention mechanisms.
CFBs are also useful to improve throughput of 802.11g stations in the presence of 802.11b legacy devices, even if the network is not otherwise using 802.11e QoS mechanisms. The 802.11g station is programmed to use a TXOP length comparable to the single frame duration of a station using the legacy 802.11b rates. The 802.11g station can send multiple frames during the CFB, occupying the medium for the same amount of time as a single legacy frame. The use of CFBs allows 802.11g devices to achieve the expected higher throughput by keeping 802.11b devices from taking a disproportionate amount of time on the medium.
The legacy 802.11 MAC always sends an acknowledgement (ACK) frame after each frame that is successfully received. Block ACK allows several data frames to be transmitted before an ACK is returned, which increases the efficiency since every frame has a significant overhead for radio synchronization. Block ACK is initiated through a setup and negotiation process between the QSTA and QAP. Once the block ACK has been established, multiple QoS Data frames can be transmitted in a contention free burst, with SIFS separation between the frames.
There are two block ACK mechanisms defined under 802.11e: immediate and delayed. When using immediate block ACK, the sending station transmits multiple data frames in a contention free burst, separated by SIFS. The sender must obey the constraints of the TXOP duration it is currently operating within. At the end of the burst, the sender transmits a block ACK Request frame. The receiver must immediately respond with a block ACK frame containing the acknowledgement status for the previous burst of data frames (Figure 4).
Figure 4: Overview of the immediate block ACK mechanism.
The delayed policy allows the group acknowledgement to be sent in a subsequent TXOP following the burst. The same sequence of a contention free burst and block ACK request is used as in the immediate mode. The receiver simply sends a standard ACK in response to the block ACK request, indicating that the block ACK will be delayed. Delayed acknowledgement increases the latency, and is provided to support lower performance implementations that are unable to immediately calculate the ACK.
Figure 5: Overview of the delayed block ACK mechanism.
Direct Link Protocol
Direct link refers to the ability to exchange data directly between two stations in the network, without traversing the AP. The legacy 802.11 MAC specifies that stations may only communicate with APs. When a station sends a frame to another station in the same logical network it must be relayed through an access point. This is to ensure that communication is possible between all stations, even if they are out of range to each other. But this reduces the available bandwidth for station-to-station communication by possibly more than one half.
The direct link protocol (DLP) in 802.11e provides a mechanism to allow direct station-to-station communication in the case where the stations are in range of each other (Figure 6).
Figure 6: Overview of DLP for setting up a direct link.
The normal setup process for a direct link is shown in Figure 6. The station wishing to initiate a direct link with another station sends a DLP request action frame to the QAP. The QAP relays the request to the other station, which responds with a DLP response action frame with a status of success. The QAP relays the response back to the station that initiated the request. At that point direct communication may commence between the two stations.
There are several cases where the negotiation can fail. If the QAP does not allow DLP in the BSS, or if the requested station is not present in the BSS, the QAP may respond with a "not allowed" or "not present" status to the first request. A station may also respond with a "refused" status to a DLP request.
A DLP teardown message can be used to explicitly end the DLP session. Stations also maintain a DLP inactivity timer that will time out unused DLP connections.
Automatic Power Save Delivery
Automatic power save delivery (APSD) is an enhancement of the existing 802.11 power save mechanisms. APSD allows a station to set up a "schedule" for delivery of frames, based on a repeating pattern of a specified number of beacon intervals.
When APSD has been enabled, the AP will buffer the APSD station's frames for the number of beacon intervals specified in the APSD setup. The time offset within the beacon interval can be specified, allowing a number of stations to wake up at different times during one beacon interval to receive their traffic.
APSD is especially useful for battery-operated devices that must turn off their radio entirely for the majority of the time, but still maintain reasonably low latency response to data sent from the QAP. The time-offset parameter allows a larger number of devices to be supported by shifting the scheduled awakening time of different devices.
APSD support is indicated in the QAP's capability information. APSD operation is invoked by a station by establishing a TSPEC with the APSD flag set. The QAP acknowledges APSD with a schedule element with the APSD flag set.
Bridging the Gap Between .11e and a Full QoS Implementation
The access point is the focal point of a wireless network, typically operating at the interface between a wired network and the wireless medium with relatively limited bandwidth. The QAP is responsible for implementing scheduling and admission control to provide the QoS agreements negotiated with the wireless stations. Scheduling and admission control are also required at stations when the station supports multiple applications or traffic streams requiring different QoS parameters.
The 802.11e standard does not specify how an HCCA scheduler must work, and there are many possible implementation techniques. The standard does specify the required signaling that is used over the air to convey the information needed by the scheduler to do its job.
The TSPEC is the primary mechanism for communication of QoS parameters. QSTAs send TSPEC requests to the QAP in the form of an ADDTS management action frames. The QSTA must request TSPEC for both upstream (from QSTA to QAP) and downstream (QAP to QSTA) flows. The QAP evaluates if there are available resources to meet the requested TSPEC. The QAP can respond by offering the QSTA an alternate TSPEC (perhaps with lower performance QoS parameters), or it may deny the TSPEC request entirely.
Once a TSPEC has been established, it may be used for data transfer, and the QAP will meet the TSPECs QoS parameters to the extent possible. A TSPEC may be deleted by the QSTA or the QAP. The QAP may unilaterally delete a QSTA's TSPEC if there are changes in the channel condition reducing available bandwidth, or if higher-priority TSPECs are requesting admittance.
TSPECs are generally created and destroyed based on requests from higher-layer management entities. TSPECs would be deleted when it the application using the QoS service has completed. Finally, a TSPEC will time out if corresponding traffic does not take place within the timeout defined during the setup.
Adapting to Varying Channel Conditions
The WLAN channel environment is challenging. Operation takes place in unlicensed spectrum where interference from other devices is commonplace, and the channel propagation properties can vary widely with movement of the wireless devices or objects in their vicinity. This variability makes the job of maintaining QoS exceptionally difficult.
The QAP is expected to grant TSPECs with specific QoS parameters appropriate to current channel conditions, and meet the request of a particular traffic stream or class to the best extent possible. At the same time, the PHY bit rates may have to be adjusted to account for changing channel conditions with any QSTA that associated. The QAP will have to adjust the scheduling and bandwidth allocations to compensate, possibly impacting the QoS delivered to one station when the conditions of the connection to another station with a higher priority stream become degraded.
The QoS mechanisms specified in 802.11e are intended to provide a general framework that is able to support present and future application requirements. Higher layers interface to the 802.11e MAC through the SAP, an abstract interface where data frames conceptually enter or leave the MAC sub-layer.
When bridging from other 802 MACs, 802.11e uses IEEE 802.1D priority tags associated with data frames at the MAC SAP. The user priorities (UP) represented by 802.1D can range from 0 to 7.
These user priorities are mapped to the traffic identifiers (TID) in the QoS control field of QoS data frames transmitted and received on the wireless medium. The TID field is 4 bits, and can represent values from 0 to 15. TID values from 8 to 15 represent traffic streams, and are associated with corresponding TSPECs within the MAC.
The recommended priority ordering of 802.1D UP fields are not sequential from 0 to 7. Table 1 shows the mapping and designations of the priorities.
Table 1: Mapping between 802.1D priorities and EDCA access categories.
The completion of the 802.11e standard will enable many new uses for WLAN. To date, the lack of QoS capabilities has held back many consumer and enterprise applications. Once completed, 802.11e will make video and multimedia transport as well as Voice over IP telephony more practical over WLANs, thus opening the technology to new service and revenue schemes.
About the Author
Tim Godfrey is a strategic manager in GlobespanVirata's PRISM Wireless Product Group as well as the secretary of the IEEE 802.11 standards committee. Tim holds a BSEE from the University of Kansas and can be reached at email@example.com.