INTRODUCTION TO QoS SCHEDULING IN WiMAX

One of the main objectives of WiMAX is to manage bandwidth resources at the radio interface in an efficient manner, while ensuring that QoS levels, negotiated at the time of connection setup, are met in an appropriate way. In the sequel, the provision of guaranteed levels of QoS in WiMAX is fundamentally dependent upon traffic policing, traffic shaping, connection admission control, and packet scheduling. To utilize the bandwidth most efficiently, the IEEE 802.16 standards employ operations of concatenation, fragmentation, and packing of MAC protocol data units (PDUs) and MAC SDUs.

Due to the highly variable nature of multimedia traffic, subscriber stations (SSs) of WiMAX can perform traffic shaping and policing for efficient utilization of resources and conformance to service level agreements. The nonconforming traffic can be penalized or rejected by an SS. A centralized connection admission control guarantees that newly admitted traffic will not cause congestion or degradation of services in the existing traffic. In WiMAX, admission control is implemented at the base station (BS). Despite the importance of the aforementioned mechanisms, the most important component for QoS provisioning is the Packet Scheduler. Thus, providing efficient scheduling mechanisms in WiMAX is the main focus of this chapter. However, several other related concepts are also described briefly.

In its broadest sense, scheduling refers to the mechanism for serving the enqueued resource requests of various users. A scheduling discipline has two orthogonal components: deciding the order of servicing the users’ requests and management of the service queues. A sketch of basic operations in a typical wireless scheduler is presented in Figure 1. Scheduling is important in both best effort and QoS networks. In the former case, the fair allocation of network bandwidth among a wide variety of network users is a prime objective. Whereas, in networks providing QoS guarantees (such as WiMAX), scheduling disciplines play a key role in ensuring that negotiated service level agreements are fully complied with. It should be noted that the requirements for scheduling algorithms in wired and wireless networks, such as WiMAX, are different from each other, and this will be explained in more detail in forthcoming sections.

Figure 1: Basic operation of scheduler in a wireless network. (Adapted from Bhagwat, P., Bhattacharya, P., Krishna, A., and Tripathi, S.K., IEEE INFOCOM, 3, 1133, March 1996.)

To provide QoS provisioning, the following three methods have been devised for WiMAX: Service flow QoS scheduling, dynamic service establishment, and two-phase activation model. A service flow in WiMAX has been defined as a MAC transport service that provides unidirectional transport of data packets either to uplink packets transmitted by the SS or to downlink packets transmitted by the BS. It is characterized by latency, jitter, and throughput assurances. It has the following major attributes:

§  Service flow ID (SFID): It is assigned to each existing service flow and serves as its principal identifier in the network

§  Connection ID (CID): It is a mapping to the SFID that exists only when a connection has been admitted or it is an active service flow

§  ProvisionedQoSParameterSet: It is a set of QoS parameters that is provisioned from outside the standard, such as a network management system belonging to the provider

§  AdmittedQoSParameterSet: It defines a set of QoS parameters for which both the BS and the SS reserve resources (bandwidth, memory, and other time-based resources)

§  ActiveQoSParameterSet: It is a set that defines the service actually being provided to active service flows

§  Authorization module: It is a logical module within the BS that approves or denies every change to the QoS parameters and classifiers associated with a service flow

The relationship between the various sets of QoS parameters has been depicted in Figure 2. It can be noticed that the ActiveQoSParameterSet is always a subset of the AdmittedQoSParameterSet, which in turn is always a subset of the authorized envelope. The scheduling algorithms to be used at the SSs of WiMAX will need to comply with values of the QoS parameters as indicated by the envelope.

Figure 2: Envelopes for provisioned and dynamic authorization models. (From IEEE 802.16e-2004, IEEE standard for local and metropolitan area networks—Part 16: An interface for fixed and mobile broadband wireless access systems, October 2004. With permission.)

Note that the automatic repeat request (ARQ) mechanism is optional in WiMAX. If implemented, it is done on a per connection basis and is specified and negotiated at the time of creation of the connection. Also, a connection cannot have a mixture of ARQ and non-ARQ traffic.

TECHNOLOGICAL STRENGTHS OF WiMAX TO ADDRESS QoS

WiMAX is designed with QoS in mind and it has some underlying technological strengths that help it offer improved QoS. Some of these strengths are outlined in this section.

1 WIMAX PHY LAYER

In WiMAX, the upstream PHY layer consists of time division multiple access (TDMA) and demand assigned multiple access (DAMA). For TDMA, the channel for upstream communication is divided into multiple time slots and the access of time slots for various clients is governed by the MAC layer at the receiver end. The time slots allocated for various clients can be varied depending on demands. The downstream traffic can be continuous time division multiplexing (TDM) or burst mode transfer. In continuous TDM, data for various clients is multiplexed onto the same stream and is received by all clients at the same coverage sector. For bursty data, bursts are sent to the receiver in a similar fashion to the TDMA upstream burst. With time slots-based communication, overheads due to contentions and collisions can be reduced significantly, which can improve the QoS.

The modulation used in WiMAX is the orthogonal frequency division multiplexing (OFDM). WiMAX OFDM features multiple subcarriers ranging from a minimum of 256 up to 2048, each modulated with either BPSK, QPSK, 16 QAM, or 64 QAM modulation. The advantage of orthogonality is that it minimizes self-interference, a major source of error in received signals in wireless communications. WiMAX supports different signal bandwidths ranging from 1.25 to 20 MHz to facilitate transmission over longer ranges in different multipath environments. Multipath signals, another limiting factor for higher sustained throughput in wireless communications, specially when the terminal nodes have the mobility, are caused by reflections between a transmitter and receiver whereby the reflections arrive at the receiver at different times. 

Interference caused by multipath tends to be highly problematic when the delay spread, the time span separating the reflection, is on the order of the transmitted symbol time. For WiMAX, due to its OFDMA, symbol times tend to be in the order of 100 µs, which makes multipath less of a problem. Moreover, in WiMAX, a guardband of about 10 µs, called the cyclic prefix, is inserted after each symbol to mitigate the effect of multipath. Another feature of WiMAX PHY is the use of advanced multiantenna signal processing techniques, mainly in the form of multiple input multiple output (MIMO) processing and beamforming. For MIMO, the received signal from one transmitting antenna can be quite different to the received signal from a second antenna, a common scenario in indoor or dense metropolitan areas where there are many reflections and multipaths between the transmitter and the receiver. In such cases, a different signal can be transmitted from each antenna at the same frequency and still be recovered at the receiver by signal processing.

Beamforming, on the other hand, attempts to form a coherent construction of the multiple transmitters at the receiver, which can ultimately offer a higher SNR at the receiver resulting in higher bandwidth or longer range communication. In WiMAX, it is also possible to combine both MIMO and beamforming in cases like 4-antenna systems.

All these features in the WiMAX PHY layer contribute to higher throughput and stability at the receiver end, which makes WiMAX an excellent platform to deliver a predefined level of QoS. With improved throughput and stability, management of QoS is considerably easier in WiMAX compared to other similar wireless standards. Increased throughput, however, does not ensure guaranteed QoS, and bandwidth management is another crucial part that plays a big role for maintaining QoS. This is where WiMAX MAC comes into action.

2 WIMAX MAC

WiMAX MAC is designed for the point-to-multipoint wireless communication with the capability to support higher-layer protocols including ATM, IP, and other future protocols. One of the design considerations of WiMAX MAC is to accommodate very high bit rates of the broadband PHY layer, while delivering ATM-compatible QoS at the same time. A connection oriented MAC architecture in WiMAX provides a platform for strong QoS control. MAC uses a scheduling algorithm that enables the subscriber station (SS) to only compete once for initial entry into the network and upon successful entry, the SS is allocated a time slot by the BS. The time slot can increase or decrease according to the needs and it remains assigned to the SS for the whole communication period. The time slot assigned to an SS cannot be used by other subscribers, which makes WiMAX MAC increasingly stable under overload and over-subscriptions. It also works as a key tool for the BS to control QoS by adjusting the time-slot assignments according to the applications’ needs of the SSs.

LEGACY QoS SOLUTIONS FOR WIRELESS COMMUNICATIONS

Over the past decade, researchers have introduced various wireless QoS mechanisms and almost all of them are incorporated at the MAC or physical (PHY) layer. Considering the wireless channel reliability issue, various error control mechanisms have also been introduced as part of the transmission protocols to improve jitter, loss rate, and overall throughput. The legacy QoS mechanisms include the following.

1 MAC QOS MECHANISMS

The MAC, also known as the medium access control, is a part of the data link layer that acts as an interface between the logical link control sublayer and the network’s physical layer. The MAC layer is responsible for controlling which node of the wireless network is allowed to access the shared channel and how nodes communicate with each other, hence it has significant impacts on the MSR, MRR, latency, jitter, and priority characteristics observed at each node. Many different wireless MAC schemes have been developed to support a wide variety of services while trying to ensure QoS. Figure 1 depicts the QoS schemes in the legacy 802.11. Each scheme has been optimized to support a particular application or set of applications. The optimization of a particular scheme leads to its inherent strengths and weaknesses. These strengths and weaknesses determine how effectively the scheme functions in real life for a particular mix of applications.

Figure 1: QoS framework in IEEE 802.11.

The MAC, designed for the IEEE 802.11b , was originally intended to allow quick, easy, and robust access to a wireless channel without complicated addressing or queuing techniques. Differentiation of services is usually all that it achieves, and latency and jitter are still unpredictable due to the random nature of the waiting time at each client for the channel access. The average throughput in a saturated network running 802.11 distributed coordination function (DCF) MAC is equal for all nodes if they all have the same traffic pattern. The IEEE 802.11e standard implements an enhanced version of DCF. This is still a contention-based MAC using carrier sense multiple access with collision avoidance (CSMA/CA). Traffic at each node is differentiated into up to eight queues, each having a different arbitrary interframe space (AIFS) and a different minimum contention window time. Traffic classes with a shorter AIFS and window size will have a higher probability of getting access to the medium. This scheme guarantees bandwidth for high priority traffic very well while still maintaining connectivity for low priority traffic. The enhanced distributed channel access (EDCA) also achieves reasonably good latency performance. However, each queue essentially works like its own DCF, meaning that as the number of users rises, the collision rate increases quite rapidly limiting the throughput. SpectaLink is one of the world’s largest provider of voice over IP (VoIP) telephony products and as such have developed their own scheme SpectraLink voice priority (SVP) for providing QoS in 802.11 networks, in the absence of a suitable standard. SVP is a modification of 802.11 which specifies that the back-off time for higher priority packets should be set to zero. In the original specification of SVP, setting the contention window to zero for high priority traffic is only done at the access point. SVP also specifies that higher priority packets should either be put at the head of the queue or put in a separate queue completely. Both these methods are designed to give priority access to packets that contain higher priority data and allow them to access the network in a timely manner at the expense of more collisions. Collisions, however, often reduce the total throughput of data in the system. Because SVP is based on the concept of DCF, many of DCF’s shortcomings are also evident in SVP. The wireless token network (WTN) is another MAC design that incorporates the overheads that are absolutely necessary to provide good throughput and QoS. All decisions during the design phase leaned toward lower transmission overhead and hence WTN is more efficient with the bit rate compared to the 802.11. The WTN, however, cannot offer guaranteed QoS when the network is overloaded and also suffers from the problem of higher jitter because of its design issues.

2 PHY LAYER QOS MECHANISMS

The 802.11 standard specifies multiple transmission rates that can be achieved by different modulation techniques at the PHY layer. The philosophy behind it is to adapt the modulation techniques according to the channel conditions so that the received error remains within a limit and QoS does not degrade substantially. The standard, however, leaves the rate adaptation and signaling mechanisms open. Because transmission rates depend on the channel conditions, an optimized link adaptation mechanism is desirable to maximize the throughput under different channel conditions. Most of the existing link adaptation mechanisms focus on algorithms to switch among transmission rates specified in the physical layer convergence procedure (PLCP), without the need to modify existing standards. The 802.11b, however, incorporates a novel method to adjust the length of direct sequence spread spectrum systems (DSSS) pseudo-noise (PN) code with slight modifications of its DCF. Metrics that are also commonly used in existing link adaptation algorithms include channel signal-to-noise ratio/carrier-to-interference ratio (SNR/CIR), average payload length, received power level, or transmission acknowledgments. Received signal strength (RSS) is a metric used in the adaptation algorithm with the assumption that transmission power is fixed. The RSS metric also assumes that there is a linear relationship between the average RSS and SNR. Based on the measured RSS, the station dynamically switches to an appropriate transmission rate.

Packet error rate (PER) prediction is another link adaptation scheme in which decisions are made based on PER prediction that not only depends on SNR/CIR but also on the momentary channel transfer function. MAC protocol data unit (MPDU)-based link adaptation is another link adaptation scheme that uses a combination of SNR, average payload length, and frame retry count as the metric for the link adaptation algorithm. The proposed algorithm pre-established a table of best transmission rate for decision making. Link adaptation with success/fail (S/F) thresholds uses the ACKs of transmitted frames as a measurement of channel condition and adjusts the transmission rate depending on the subsequent successful transfer of frames. Code Adapts To Enhance Reliability (CATER) is an adaptive PN code algorithm for DSSS used in 802.11b and it is designed to improve the throughput under high bit error rate (BER) channel conditions.

3 ERROR CONTROL MECHANISMS

A wireless network is not as reliable as a wired network and error in transmitted packets is common in wireless communication. The error is more evident when the nodes have the mobility that causes error in the received packets due to slow and fast fading. An error control mechanism attempts to address the problems caused by error in received signals and thereby maintains QoS by improving loss rate and jitter performances and overall throughput. The Transmission Control Protocol (TCP) is a popular protocol designed to provide reliable and orderly delivery of a stream of bytes and is a key part of the TCP/IP protocol suit. The TCP provides a simpler interface to applications by hiding most of the underlying packet structures, rearranging out-of-order packets, minimizing network congestion, and retransmitting corrupted packets. Forward error correction (FEC) is another error control mechanism for data transmission. In FEC, the sender incorporates additional redundant data to its messages, which allows the receiver to detect and correct errors within a certain limit without the need for retransmission. FEC block codes are applied to a sequence of packets, and in case of a loss/error in packets, a receiver reconstructs the missing packets from the redundant information carried in error-correcting codes. Naturally, error-correcting capability in FEC comes at some costs because the FEC codes represent redundant information that increases the overall transmission rate. FEC is highly effective where the communication media is unreliable and retransmissions of too many packets prove costly in context of available bandwidth.

Although considerable effort has gone into improving the QoS in the 802.11 standard, the most it can achieve is to differentiate traffic and treat them with their corresponding priority and also to adapt the transmission rates at various environments to offer graceful degradation of throughput. Due to its design limitations at different layers, the 802.11 standard cannot offer guaranteed QoS, which is one of the key motivations behind introducing another standard, the IEEE 802.16, also known as WiMAX.