Scheduling in WiMAX

Packet scheduling is the process of resolving contention for shared resources in a network. The process involves allocating resources among the users and determining their transmission order. Scheduling algorithms for a particular network need to be selected based on the type of users in the network and their QoS requirements. For real-time applications such as video conferencing, voice chat, and audio/video streaming, delay and delay jitter are the most important QoS requirements. Delay jitter is the inter-packet arrival time at the receiver and is required to be reasonably stable by real-time applications. On the other hand, for non-real time application such as FTP, throughput is the most important QoS requirement. Some applications, such as web-browsing and email do not have any QoS requirements. In a network, different types of applications with diverse QoS requirements can co-exist. The task of a scheduling algorithm in such a network is to categorize the users into one of the pre-defined classes. Each user is assigned a priority, taking into account his QoS requirements. Subsequently, resources are allocated according to the priority of the users while fairness is observed.

Besides having a very close coupling with the QoS requirements of the users, the design of a scheduling algorithm also depends on the type of the network it is intended for. A wireless network can be categorized into a single-hop or a multi-hop network. A single-hop network contains a central entity such as a BS that makes and delivers decisions to all SSs in its cell. On the other hand, in a cellular multi-hop network, some SSs are not in direct contact with the BS, that is, an object such as a building could be blocking the path from the BS to the SS. In such a network, a RS is used to relay the information to and from these SSs.

Packet scheduling algorithms can usually be distinguished based on their characteristics. In the sequel, we shall review some of the desirable qualities a scheduling algorithm should possess. We also highlight the issues that need to be addressed by these algorithms.

• Flexibility: A scheduling algorithm should be able to accommodate users with diverse QoS requirements and also meet the minimum requirements of the users. Ideally, the design of a scheduling algorithm should be flexible enough so that it requires minimal changes to be deployed in a different network or even a different technology.
• Simplicity: A scheduling algorithm should be simple, both conceptually and mechanically. Conceptual simplicity allows manageable analysis of the algorithm such that distribution or worst case analysis bound for parameters such as delay and throughput can be derived. Mechanical simplicity allows efficient implementation of the algorithm at a large scale.
• Protection: A scheduling algorithm needs to be able to protect well behaving users from sources of variability such as BE traffic, misbehaving users and fluctuations in the network load. Upon admission into the network, users specify a contract they will adhere to, for example, a user will specify the peak rate at which it will send traffic into the network. Sometimes a user will not abide by the contract causing unpredicted fluctuations in the network. A scheduling algorithm needs to ensure that such fluctuations do not affect well behaving users in the network.
• Fairness: Besides satisfying the QoS requirements of the users, a scheduling algorithm needs to ensure a reasonable level of fairness is maintained between the users. Fairness measures the difference between the users with respect to the resources allocated to them. In a wireless network, due to the presence of variations in channel quality, users experiencing poor channel quality might be denied service by the scheduling algorithm. This is because resources allocated to users with inferior channel quality will essentially be wasted as the data will be lost or corrupted prior to reaching the destination. A scheduling algorithm needs to have a mechanism to compensate users that have lost service and maintain fairness between all the users.
• Link Utilization: A scheduling algorithm is required to assign bandwidth to the users such that maximum link utilization is realized. Link utilization is a critical property for the service providers as it is directly linked to the revenue generated. A scheduling algorithm needs to ensure that resources are not allocated to users that do not have enough data to transmit, thus resulting in wastage of the resources.
• Power conservation on the mobile device: Due to limited power available on the MS, a scheduling algorithm needs to ensure that limited processing is done on this device.
• Device mobility: Different cells can have different notions of time, that is, the BSs of different cells are not required to be synchronized. When a MS moves from one cell to another, packets need be time-stamped based on the notion of time in the new cell. Scheduling algorithms that allocate bandwidth to the users according to the time-stamp of the packets (e.g., schedule users based on their packet deadlines) will not function as expected if the packets are not stamped with the correct notion of time.

To evaluate the performance of current WiMAX schedulers, several scheduling algorithms are assessed with respect to the characteristics of the IEEE 802.16 MAC layer and OFDM PHY. The authors of [1] classify the proposals into three categories; homogenous algorithms, hybrid algorithms and opportunistic algorithms. The homogenous and the hybrid categories consist of traditional scheduling algorithms with the hybrid category employing multiple legacy schemes in an attempt to satisfy the QoS requirements of the multi-class traffic in WiMAX networks. The opportunistic category refers to algorithms that exploit variations in channel conditions in WiMAX networks whilst incorporating the QoS requirements in their scheduling design. Representative schemes in each of these categories will be discussed next.

Homogeneous Algorithms

Weighted Round Robin (WRR) and Deficit Round Robin (DRR) algorithms are evaluated in a WiMAX network in [2]. WRR is evaluated for the uplink traffic while DRR is evaluated for the downlink traffic. In WRR, each SS is assigned a weight factor that reflects its relative priority. Priority of the SSs can also be incorporated in the DRR algorithm. DRR allows provision of different quanta for each SS. A higher quantum can be assigned to higher priority SSs. Ruangchaijatupon et al. [3] evaluated the performance of Earliest Deadline First (EDF) algorithm. This is a work conserving algorithm originally proposed for real-time applications in wide area networks [3]. The algorithm assigns deadline to each packet and allocates bandwidth to the SS that has a queued packet with the earliest deadline. Weighted Fair Queuing (WFQ) is also evaluated and compared with EDF in [4].

Tsai et al. [5] proposed an uplink scheduling algorithm and a token bucket based Call Admission Control (CAC) algorithm. The CAC algorithm assigns thresholds to each class to avoid starvation of lower priority classes. The scheduling algorithm first grants bandwidth to SSs of the UGS class, then allocates bandwidth to SSs of the rtPS class using EDF algorithm and restricting the allocation to the maximum grant size. Finally, the algorithm allocates minimum required bandwidth to SSs of the nrtPS and BE classes.

Hybrid Algorithms

Wongthavarawat and Ganz [6] proposed a hybrid scheduling algorithm that combines EDF, WFQ and FIFO algorithms. The overall allocation of resources is done in a strict priority manner. EDF scheduling algorithm is used for SSs of the rtPS class, WFQ is used for SSs of the nrtPS class and FIFO for SSs of the BE class. Besides the scheduling algorithm, an admission control procedure and a traffic policing mechanism are also proposed.

Vinay et al. [7] proposed a hybrid scheme that uses EDF for SSs of the rtPS class and WFQ for SSs of nrtPS and BE classes. This algorithm differs from [6] in that WFQ is used for SSs of both nrtPS and BE classes and the overall bandwidth is allocated fairly, however, the authors did not describe the mechanism for fair allocations. Settembre et al. [8] propose a hybrid scheduling algorithm that uses WRR and RR algorithms with a strict priority mechanism for overall resource allocation. In the initial stages, resources are allocated on a strict priority basis to SSs of the rtPS and nrtPS classes only. The WRR algorithm is used to allocate bandwidth amongst SSs of rtPS and nrtPS classes until they are satisfied. Any residual bandwidth is distributed between the SSs of the BE class using the RR algorithm.

A vital component of hybrid algorithms is the distribution of bandwidth among the diverse traffic classes. We have selected to evaluate hybrid (EDF + WFQ + FIFO) and hybrid (EDF + WFQ) schemes, which employ different mechanisms of distributing bandwidth among the traffic classes. The hybrid (EDF + WFQ + FIFO) algorithm applies the strict priority mechanism, whereas the hybrid (EDF + WFQ) keeps track of the bandwidth allocated to all service classes and perform dynamic distribution of bandwidth by providing fair service to all traffic classes. In our evaluation, we use the MRTR of a SS as the core of this approach (details were not available in [7]). Specifically, bandwidth is distributed with respect to the relative MRTR of all SSs in a class, that is, the available bandwidth is multiplied by the ratio of sum of MRTR of SSs in a class to the sum of MRTR of all the SSs in the network.

Opportunistic Algorithms

A Cross-Layer scheduling algorithm is proposed in [9] whereby each SS is assigned a priority based on its channel quality and service class. The SS with the highest priority is scheduled for transmission in each frame. The algorithm considers all the required QoS parameters of the scheduling services specified in the IEEE 802.16-2004 standard. Class coefficients are utilized to assign relative priority to the different traffic classes. Rath et al. [10] proposed to use an opportunistic extension of the DRR algorithm with the purpose of satisfying delay requirements of multi-class traffic in WiMAX. The cornerstone of the algorithm is selecting an appropriate polling mechanism. At the beginning of a polling interval, a set of schedulable SSs are selected that constitute a schedulable set. Until the next polling interval, SSs are selected only from this schedulable set.

Niyato and Hossain [11] proposed a joint resource allocation and connection admission control algorithm based on queuing theory. In order to limit the amount of bandwidth allocated per class, a bandwidth threshold is assigned to each class. A utility function is calculated for each SS based on the QoS requirements of the traffic class. Subsequently, bandwidth is allocated based on the utility, giving priority to the SS with the lowest utility.

Singh and Sharma [12] proposed a scheduling algorithm for OFDMA systems with a TDD frame structure for both uplink and downlink traffic in WiMAX. The algorithm allocates bandwidth among the SSs on a priority basis taking into consideration the channel quality, the number of slots allotted to the SS and the total bandwidth demanded by the SS. Kim and Yeom proposed an uplink scheduling algorithm for TCP traffic for the BE class [12]. The proposed algorithm does not require explicit bandwidth request from a SS. It estimates the amount of bandwidth required by the SS based on its current transmission rate. The purpose of the algorithm is to provide reasonable fairness among the SSs based on the min-max fairness criteria while providing high frame utilization.

The Cross-Layer and Queuing Theoretic algorithms provide a good representation of all the schemes in this category. Both algorithms differ with respect to the number of SSs selected for transmission and the QoS parameters incorporated. The queuing theoretic algorithm schedules multiple SSs in each frame whereas the cross-layer algorithm schedules only one SS. The cross-layer algorithm includes both throughput and delay in the priority function of rtPS class but the queuing theoretic algorithm includes only the delay in the utility function of the rtPS class.

The performance of the scheduling algorithms is evaluated under different conditions. These conditions include studying performance of the algorithms under various concentrations of traffic and under characteristics of the IEEE 802.16 MAC layer such as uplink burst preamble, frame length and bandwidth request mechanisms. Table 17.1–17.3 show a summary of the comparison among WiMAX schedulers. A detailed results and discussion can be found in [Pratik].

Table 17.1 Comparison of Homogeneous schemes

Table 17.2 Comparison of Hybrid schemes

Table 17.3 Comparison of Opportunistic schemes