In this section, we consider the general problem of packet scheduling in wireless networks. For later sections it will set the stage for defining the classification/framework for scheduling algorithms in WiMAX. The fundamental characteristics of packet-networks operating over wireless channels include
(1) time-varying wireless channel capacity,
(2) location-dependent channel errors and traffic that is bursty in nature,
(3) contention among mobile hosts,
(4) mobile hosts do not have a global channel state
(5) proper type of scheduler required for both UL and DL flows, and
(6) mobile hosts often have limited battery and processing power.
The above-mentioned factors need to be considered very carefully, while designing schedulers for wireless networks. Otherwise, the performance will not be optimal.
Two basic performance measures used in the literature for packet schedulers are throughput and fairness. Throughput usually refers to the amount of data transferred from the BS to the SS, in its own traffic class; whereas fairness refers to, ideally, equal allocation of allotted bandwidth to all SSs for a particular traffic class. If an SS lies in a bad channel state, then there should not be bandwidth allocation to that particular SS. The concept of fairness is discussed in more detail in the latter part of this section.
In wired networks, the retransmitted packets can be excluded from throughput computation to give another performance measure, known as goodput. Similarly, in WiMAX networks, either throughput or goodput can be used as measures of data transferred from BS to SS and vice versa. It should be noted that customers in various traffic classes will try to maximize their throughputs, which may lead to classical selfish game-theoretic behavior, which needs to be policed by mechanisms at the SSs or at the BSs. In such a competitive environment, each user will be trying to maximize its own utility function.
While taking into account the temporal characteristics of channels, a wireless packet scheduler should have the following essential features:
§ Efficient utilization of wireless channel bandwidth: The wireless scheduling algorithm should utilize the channel efficiently and should avoid wasting resources on links operating in bad state. An efficient service discipline will be able to meet the end-to-end performance guarantees for various service classes under all load conditions.
§ Throughput bound: For each service class, the scheduler should be able to provide a short-term throughput bound for flow with a clean channel and a long-term throughput bound for all flows including those in an error state in the channel.
§ Short-term and long-term fairness: The scheduler should be able to provide fair allocation of bandwidth to all flows, from various traffic classes, within a good channel state as well as to those lying within a bad state.
§ Delay bound: The scheduling algorithm should be able to provide a guaranteed delay bound on various traffic classes.
§ Implementational complexity: The scheduling algorithm should be simple and have a low time complexity to select and forward a packet from the queues of various classes. Generally, fairness and delay bound requirements collide with the complexity of the scheduling algorithm. Schedulers having good fairness and strict delay bounds are harder to implement, whereas algorithms are simplest but provide poor fairness and delay bounds.
§ Graceful degradation of service: The scheduler should be able to compensate for backlogged flows, which have not received service due to bad channel conditions, at the expense of those flows which have received extra service due to good channel conditions. This corrective reduction in the service allocation of certain flows belonging to wireless channel in a good state should be smooth and gradual.
§ Protection against misbehaving flows: The scheduling algorithm should be able to protect service guarantees for various classes and eliminate the effects of misbehaving flows, network load fluctuations, and best effort uncontrolled traffic flows (such as in the case of denial-of-service (DOS) attacks).
§ Decoupling between delay and bandwidth: The scheduler should be able to decouple bandwidth and delay and thus should support both delay sensitive and error sensitive flows. Usually, the classes having higher reserved data rate also have low delay requirements; however, some high bandwidth applications can work well even with larger delays, such as web browsing.
§ Flexibility and scalability: The scheduling algorithm should be flexible enough to cope with the vast number of different current types of IP traffic, as well for future traffic characteristics. Also, it should perform well when there is an increase in the number of connections for each traffic class.
§ Power efficiency: The scheduling algorithm should be power efficient. It is especially important for the mobile subscriber’s equipment, wherein currently available batteries have a limited (charged) life.
