SCHEDULING SETUP IN WiMAX

IEEE 802.16e has been developed to serve mobile SSs through a centralized BS by employing point-to-multi point (PMP) as well as through the optional mesh mode architecture of a wireless network topology. In the former operating mode, the downlink from a BS to an SS operates on the basis of PMP. However, in the mesh mode, there are no separate DL and UL subframes and there can be SSs that are not directly connected to the BS but only through intermediary SSs, which is in contrast to the PMP mode. Hence, a larger number of SS can be supported in the mesh mode than in the PMP mode or equivalently, mesh mode can offer the least number of BSs for economy. Furthermore, in the mesh mode of WiMAX the SSs can consume less power, thereby efficiently using battery life, as it is not mandatory to be always connected to the BS. The intermediate SSs will greatly reduce the power consumption of far off users.

Three types of scheduling are supported in the mesh mode of WiMAX; they are coordinated distributed, uncoordinated distributed, and centralized scheduling. In coordinated scheduling, all nodes coordinate in their two-hop neighborhood and broadcast their schedules (available resources, requests and grants) to all of their neighbors; whereas, in uncoordinated scheduling there are direct uncoordinated requests and grants between two nodes. The main difference between the two types of distributed scheduling methods is in the use of the control subframe: transmitting collision-free scheduling messages in the coordinated type and with possible collision in the uncoordinated type. In the centralized method, the resources are distributed centrally and this is similar to the PMP case.

The performance of coordinated distributed scheduling has been investigated. It has been reported that this mechanism has a scalability problem that leads to poor performance in dense networks and aggravates QoS provisioning. To overcome these problems, the XmtHoldoffTime has been made adaptive at every node, which has been shown to improve contention, and thus enhance the throughput in dense meshes. A combined distributed and centralized scheduling scheme has been proposed for mesh networks in WiMAX; wherein, through simulation studies, it has been shown that the minislot^[*] utilization can be significantly improved with the proposed scheme.

For synchronization of distributed and centralized control mesh networks, the WiMAX standard provides network configuration (MSH-NCFG) and network entry (MSH-NENT) packets as a basic level of communication between various nodes. The scheduling of transmission for the next MSH-NCFG is done by a mesh-election procedure. It is carried out among all eligible competing and local nodes. The NetEntry scheduling protocol provides slots for transmission of MSH-NENT packets by new nodes that are not yet fully functional members of the mesh .

In contrast to mesh mode, a detailed QoS architecture has been defined for the PMP mode. Scheduling services refer to data-handling mechanisms supported by the MAC scheduler for data transport on each connection. A single scheduling service will be associated with each data connection. Each of the data services will be characterized by a set of parameters that will quantify the QoS aspects of its behavior. These QoS parameters are managed by dynamic service addition (DSA), dynamic service change (DSC), and dynamic service deletion (DSD) message dialogues, where each of these signaling schemes can be initiated by either a BS or an SS.

It can be seen that scheduling mechanisms for a PMP mode are also applicable to a mesh mode; however, since all transmission between two nodes is managed by a link, PMP scheduling is not directly applicable to the mesh mode. By default, at the time of connection establishment, each mesh SS is assigned a unique node identifier; a Service Adaptive QoS has been proposed for mesh mode, which assigns five node IDs to each SS instead of a single ID. These five virtual nodes correspond to five traffic classes, and each node requests bandwidth individually and the mesh mode BS handles these requests on the basis of their scheduling services. Hence, mesh mode WiMAX can be treated by scheduling the services of the PMP mode. Therefore, subsequently in this chapter, we shall only consider scheduling in the PMP mode for WiMAX networks.

GENERALIZED WIRELESS PACKET SCHEDULING

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.

ADMISSION CONTROL AND BANDWIDTH ALLOCATION

In general, admission control is a network’s QoS mechanism that determines whether a new session (or connection), with given bandwidth and delay requirements, can be established or not. For providing QoS, this procedure has been applied to both wireline and wireless networks. In the case of WiMAX, whenever a new session wants to make use of the wireless network, an admission control request is sent by the SS to the BS. This admission control request will be accepted by the BS if there is enough available bandwidth, QoS guarantees for bandwidth and delay can be met and the QoS of existing connections is not disturbed. An admission control scheme for WiMAX has been proposed together with the derivation of rules for each of the four classes of WiMAX. In addition, a token bucket based admission control for rtPS flows has been proposed. Omitting any further discussion involving admission control, we now present a brief overview of bandwidth allocation mechanisms in WiMAX.

The BS allocates bandwidth on a per SS basis, known as the grant per subscriber station (GPSS); further, each SS distributes this bandwidth among all of its active connections. The SS can efficiently distribute the allocated bandwidth as it has up-to-date information about the queue status of each connection. Thus, GPSS requires a packet scheduler at each SS, which may increase the complexity and the cost of an SS. However, GPSS is scalable to a large number of SSs and is, therefore, the only bandwidth allocation mechanism being employed in the current WiMAX.^[*]

With GPSS, each SS treats various connections separately at its own level and these are then pooled together as one entity for bandwidth allocation at the BS. Thus, the scheduler at the BS will only need a small amount of information about the overall bandwidth required by a particular SS. This approach has the additional advantage of avoiding the time lag in receiving updated information about individual connections at the SS. Once a lump of bandwidth has been granted to a particular SS, then it is responsible for the appropriate scheduling, according to priorities and the QoS for each active connection. This process greatly reduces the workload on the BS. For instance, suppose that an urgent packet arrives at the SS, then the BS does not need to have information about it and it is the duty of the scheduler at the SS to provide the required throughput and delay.

BS and SS communicate with each other by using a bidirectional path, viz., Uplink (UL: SS to BS) and Downlink (DL: BS to SS); whereas the bandwidth requirements are made by the UL and grants are made by the DL. WiMAX supports both Frequency Division Duplex (FDD) and Time Division Duplex (TDD) modes as shown in Figures 1 and 2, respectively.

Figure 1: An example of Burst FDD bandwidth allocation. (From IEEE-802.16-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.)

Figure 2: Frame structure of TDD. (From IEEE-802.16-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.)

In FDD mode, both the UL and DL are operating at separate frequencies and DL data can be sent in bursts. To facilitate various types of modulation, a fixed duration frame is used for both the DL and UL transmissions. Also, it allows the simultaneous use of both full and half duplex SSs; a full duplex SS can transmit and receive data at the same time whereas a half duplex SS can either transmit or receive data at any given time. If half duplex SSs are used, then bandwidth controller will not allocate UL bandwidth at the same time that it is expecting to receive data on DL channel. It should also take into account the allowance for propagation delay, SS transmit/receive transition gap, and SS receive/transmit transition gap. In FDD mode, the use of a fixed duration frame, for both the DL and UL channels, also helps in simplifying the design of algorithms for bandwidth allocation. It can be noted that a full duplex SS can listen to a DL channel continuously, whereas the half duplex SS can only listen to a DL when it is not transmitting on the UL channel.

In the case of TDD, the UL and DL transmissions occur at different time intervals, while usually employing the same frequency. A TDD frame is also of fixed duration and is composed of one DL and one UL subframe. For easy partitioning of bandwidth, a TDD frame is divided into an integer number of physical slots. Also, TDD framing is adaptive and the bandwidth allocated to the UL and DL parts can vary and is controlled by the higher layers. The DL-MAP and UL-MAP messages define the usage of the corresponding transmission intervals. The BS also regularly transmits DL and UL channel descriptors, DCD and UCD, for the physical description of the corresponding channel. The complete list of MAC management messages. It should be noted that a WiMAX network can be planned with either FDD or TDD, but the former mode has been discussed more frequently in the literature.