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.

BANDWIDTH REQUEST MECHANISMS

During network entry and initialization processes, each SS is assigned up to three dedicated CIDs for the purpose of sending and receiving control messages. They are used for allowing a differentiated level of QoS. In WiMAX, an SS can get a bandwidth request to the BS using several methods, these include requests, grants, UGS, Unicast Polling, Multicast/Broadcast Polling, Contention-based focused bandwidth requests, Contention-based code division multiple access (CDMA) bandwidth requests, and Optional Mesh topology support. Vendors are allowed to optimize the performance of their systems by employing different combinations of these schemes. Requests refer to mechanisms used by SSs to indicate to the BS that they require Uplink allocation of bandwidth. It can be as a stand-alone bandwidth request header or as a piggyback request. The use of piggyback is optional.

Another important concept in WiMAX is bandwidth stealing. It refers to an optional strategy, adopted by an SS, in which a portion of bandwidth allocated (in response to a request by a connection) is used to send another bandwidth request rather than sending data. It has been modified in the mobile WiMAX standard, as referring to the use by a SS, of a portion of the bandwidth allocated in response to a bandwidth request for a connection to send a bandwidth request or data for any of its connections.

Polling refers to a process where the BS allocates some bandwidth to SSs specifically for making bandwidth requests. It can be for an individual (unicast) or a group (multicast/broadcast) of SSs. The contention-based bandwidth request mechanisms of WiMAX are only allowed for ertPS, nrtPS, and BE traffic classes. UGS and rtPS are not allowed to participate in the contention process. To resolve contentions, a mandatory, truncated binary exponential backoff scheme has been specified in the standard. It has an initial and a maximum backoff window controlled by the BS. Its value is specified by the uplink channel descriptor message and it follows the power-of-two rule. Readers interested in the modeling of polling and contention-based bandwidth.

To optimize the bandwidth request latency from an SS to a BS, and thus the response time, for elastic traffic generated by various sources (such as TCP or Push-to-Talk), defined the Poll-Me (PM) bit in a generic MAC header. Currently, the PM bit is part of the WiMAX standard and it may be used to request to be polled for a different non-UGS connection. The SSs with currently active UGS connections can set the PM bit in the grant management subheader to indicate to the BS that they need to be polled to request bandwidth for non-UGS connections. It is noted that except for UGS, piggyback and bandwidth stealing is allowed for all other traffic classes.

Recently, Its basic idea is to adapt polling intervals according to ON/OFF periods of traffic. During an ON period, polling intervals are short and of fixed length, whereas during an OFF period the polling intervals are lengthened exponentially, thus, reducing the signaling overhead.

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.