Unsolicited Grant Service with Activity Detection

The UGS-AD algorithm is designed to support real-time service flows that generate fixed-size data packets on a semi-periodic basis (e.g., VoIP using on–off voice codec). It incorporates activity detection, which makes it suitable for use with on/off voice codecs. The algorithm uses combined features of UGS and rtPS. UGS-AD has two scheduling modes: UGS and rtPS, and can switch between these modes depending on the status of the voice users (on or off). On initialization of VoIP services, this algorithm starts with the rtPS mode. While in rtPS mode, if the voice user requests bandwidth size of zero bytes, the BS maintains this (rtPS) mode. However if the user requests bandwidth size greater than zero, the BS switches its mode to UGS. While in UGS mode, if the voice user requests bandwidth size = 0, the BS switches to rtPS, and if the user requestsbandwidth greater than zero, the BS stays in UGS. By switching between rtPS and UGS modes, the UGS-AD algorithm significantly addresses the problem of UL resources wastage in the UGS algorithm, and the MAC over head and access delay in the rtPS. This is however only for the case where the voice user uses voice codecs with only two data rates (on–off). Where voice codecs with variable data rates like EVRC is used, resources wastage still occur in the UGS-AD algorithm. In this case, the wastage occurs during the on duration, when full resources is assigned eventhough the variable data rate of voice codecs means that it will not operate at full rate for all of the time the resources is allocated. The operation of the UGS-AD algorithm is illustrated in Figure 1.

 
Figure 1: UL resource allocation using UGS-AD algorithm.

Real-Time Polling Service | QoS Scheduling

The rtPS algorithm is designed to support real-time service flows, such as MPEG video or tele-conference, that generate variable size data packets periodically. In this algorithm, the BS assigns UL resources that are sufficient for unicast bandwidth request to the voice users. This is called the polling process. The duration for which the BS continues to poll an SS with rtPS connection is negotiated in the initialization process of the connection. The SSs utilize the assigned polling resources to send their bandwidth requests, reporting the exact bandwidth need for their rtPS connection. The BS in response then allocates the exact bandwidth requested to the SS for transmission of the data. Figure 1 illustrates this dynamic polling process.

 
Figure 1: Polling process in rtPS.

Because rtPS always carry out polling process, it is able to adaptively determine suitable resource allocation from frame to frame. This adaptive request-grant process goes on until the connection is terminated. Because of the dynamic request-grant process, the algorithm has more optimum data transport efficiency than the UGS algorithm. The algorithm is able to dynamically follow all data rate of the voice codec without any resource wastage as illustrated in Figure 2 (allocated and utilized resources are equal). This is a major advantage over the UGS algorithm. The drawback of the rtPS algorithm however is that the dynamic polling process causes MAC overhead and access delay. Hence rtPS has more MAC overhead and larger access delay than the UGS.

 
Figure 2: UL resource allocation using rtPS algorithm.

Unsolicited Grant Service

The UGS algorithm is designed to support real-time service flows, such as Voice over Internet Protocol (VoIP), that generate fixed size data packets periodically. BS periodically assigns fixed-size grants to voice users. These grants are sufficient to send voice data packets generated by the maximum data rate of enhanced variable rate “voice” codec (EVRC). The grant period are negotiated during the initialization process of the connection. Thus, MAC overhead and UL access delay caused by bandwidth request process are minimized. The drawback of the UGS algorithm is the following. Generally, voice users do not always have voice data packets to send throughout the duration of a connection, because voice users have frequent silence periods. A typical voice codec switches intermittently between “on” and “off” states as illustrated in Figure 1. While in “on” state, popular voice codecs like the EVRC also have variable data rates. For example, the EVRC operates at 1/8 of the full data rate during the off state, while the device has three different rates during the on state (rates 1, 1/2, and 1/4). Therefore for a UGS algorithm that reserves a flat amount of resources capable of sending data at the maximum rate of EVRC periodically, a significant amount of UL resources is wasted when the codec is in silence (or off) mode as well as when the codec is on but not operating at the full rate. This is illustrated in Figure 2. A number of other algorithms have thus been designed to adaptively determine the actual UL needs of each connection during frame periods, so as to minimize these resources wastage.

 
Figure 1: Voice codec status.

 
Figure 2: UL resource allocation using UGS algorithm.

Scheduling Algorithms

In the WiMAX standard (802.16), four scheduling classes have been defined: Unsolicited grant service (UGS), real-time polling service (rtPS), nonreal-time polling service (nrtPS), and best effort (BE). As illustrated in Figure 1, each traffic connection is associated with one of the four scheduling services, and the SS scheduler selects packets to be transmitted from each queue based on the scheduling policy employed. Usually, the scheduler selects packets to be transmitted from the highest priority queue that is not empty. Transmission of packets from lower priority queues are postponed until there is no packet available to send from a higher priority queue. Since UL traffic is generated at SS, the SS scheduler is able to arrange the transmission based on the up-to-date information on the current numbers/status of UL connections, which help to improve QoS performance. In the following, we review the various scheduling algorithms provided in the standard for handling the transmissions of packets belonging to these various services.

 
Figure 1: UL scheduling at the SS.

QOS SCHEDULING AND ADAPTIVE RESOURCE ALLOCATIONS

IEEE 802.16 supports fixed-length frame, with flexible (adaptive) DL/UL resource usage ratios. The BS adaptively adjusts DL and UL subframe lengths on a frame-by-frame basis depending on the DL/UL traffics and channel conditions. Typically, the DL:UL resources can be varied from 3:1 to 1:1 in a PMP WiMAX network. Figure 1 illustrates the fixed-length frame in the PMP WiMAX network, and the flexible DL/UL subframes. The figure also depicts the network entry process for subscriber stations (SS) and the scheduling periods for assigning transmission opportunities to SS already initiated into the network. For access (PMP) mode, new SS detects preamble and frame control header (FCH), and identifies the number of DL burst transmissions from the DL MAP in the FCH. At the end of the last DL burst (Figure 1), new SS uses a contention period to exchange network entry request signal with the BS. If successful, the BS process the request and sends entry instruction (assigned DL/UL transmission opportunities, power, etc.) in the DL/UL MAPS of the next frame, and the SS gets initiated into the network. For the mesh mode, new SS waits for network entry signal broadcast at the beginning of a frame, to which they can respond within a specified period. Scheduling process is used for initiating new SS into the network. SS transmits on the scheduled slots.

 
Figure 1: Adaptive DL/UL subframes in WiMAX standard.

In the WiMAX standard (802.16e), UL and DL assignments are based on time division multiple access (TDMA). In each frame, the BS scheduler assigns UL and DL transmission opportunities to SS until their negotiated data periods expire. The resources given to an SS for its data transmission are both in the frequency and time domain. WiMAX MAC thus supports frequency-time resource allocation in both DL and UL on a per-frame basis. The resource allocation is delivered in media access protocol (MAP) messages at the beginning of each frame. Therefore, the resource allocation can be dynamically changed frame-by-frame in response to traffic and channel conditions. Additionally, the amount of resource in each allocation can range from one slot to the entire frame in the time domain, and from one subchannel to the entire subchannels in an OFDM symbol, in frequency domain. Also WiMAX employs fast scheduling both in the DL and UL to respond to fast variations in channel conditions. This fast and fine granular resource allocation allows superior QoS for data traffic in a bursty traffic and rapidly changing channel condition. The fundamental premise of the IEEE 802.16 MAC architecture is QoS. It defines services flows which can map to Diffserve code points or MPLS flow labels that enable end-to-end IP-based QoS. Additionally, subchannelization and MAP-based signaling schemes provide a flexible mechanism for optimal scheduling of space, frequency, and time resources over the air interface on a frame-by-frame basis. This flexible scheduling allows QoS to be better enforced and enable support for guaranteed service levels including committed and peak information rates, latency, and jitter for various types of traffic on a customer-by-customer basis.

DRR-Based Algorithm | QoS and Fairness in WiMAX

DRR is a scheduling algorithm that approximates less strictly the fairness performance of GPS, but with a low computational complexity, which is O(1) processing work per packet. It uses round-robin service with a quantum of service assigned to each queue. Differently from traditional round-robin scheme, if a queue was not able to send a packet in a given round because of its large packet size, the remainder of the quantum (deficit) is added to the quantum for the next round. The use of the deficit variable makes DRR suitable to the management of queues with different packet sizes.

DRR maintains for each queue q_i (i = 1, …, 3) a deficit counter DC_i and a quantum Q_i measured in bytes. At the beginning, all DC_i variables are set to zero. The algorithm works serving queues in turn; each time a queue is selected, its DC_i is incremented by the Q_i value; then packets are sent out if their size (in bytes) is less than DC_i. Each time a packet is extracted from queue, DC_i is decremented by the packet size. To avoid examining empty queues, the scheduler keeps an auxiliary list, active list, which includes the indices of queues that contain at least one packet. The round-robin selector points to the head of the active list. Whenever a packet arrives to a previously empty queue, the index of that queue is inserted into the active list.

CHANNEL ERROR COMPENSATOR

At the beginning of each frame, the compensation block classifies a flow (i.e., a CID) as sensing a good or a bad channel on the basis of the CINR reports received by the relevant target SS. Accordingly, CIDs destined to an SS sensing a lossy channel are marked as “banned” from being transmitted. When the error-free service scheduler selects a head-of-line (HOL) packet to be extracted from queue i, it interacts with the compensator to check whether the CID of the selected packet is banned or not. If it is banned (the packet would risk to be corrupted if transmitted over the radio link), then the scheduler looks for a packet belonging to an unmarked flow of the same class (i.e., in the same queue) to transmit instead of the HOL packet. To help the scheduler in selecting the substitute flow, the compensator manages a debit/credit counter for each active (leading or lagging) flow. Each time a flow substitutes another one for transmission, it is considered as a leading flow, and its credit counter increases by one; at the same time, the replaced flow is considered as a lagging flow, and its debit counter increases by one. Each time a HOL packet cannot be transmitted due to poor channel conditions, the substitute flow is the one with the highest debit counter among unmarked flows of the same class. If no unmarked packets can be found in the queue, then the entire queue is banned and the turn passes to the successive queue.

The pseudocode listed below briefly shows how the compensator works and interacts with the scheduler, regardless of the specific algorithm (WF²Q+ or DRR) this latter uses.

1 ban flow if CINR > CINRthr;

2 until available resources {

3       until a pkt is dequed || all queues examined {

4               scheduler selects queue x : x !banned i.e. scheduler selects flow i = head(x);

5               if i is marked {

6                      select less serviced flow j : j !banned;

7                      if !found {

8                                    mark x;

9                                    goto 3; }

10                    else {

11                                   deque pkt;

12                                   modify scheduler variables;

13                                   modify credit/debit counter of i and j;

14                                   exit; } }

15              else {

16                     modify scheduler variables;

17                     deque pkt; } } }

At the beginning of each frame, the compensator bans the flows directed to SSs, which currently sense a lossy channel (line 1), according to the received channel state information reports. For the duration of the DL subframe, packets within the queues are examined by the scheduler until at least one queue contains a packet belonging to an unbanned CID (lines 2–3). The scheduler selects the queue to be served among all backlogged (and unbanned) queues; this corresponds to select the first packet in the queue (line 4). If this packet belongs to an unbanned flow, then it gains service and the variables for the specific scheduling algorithm (WF²Q+ or DRR) are updated accordingly (lines 15–17). These variables can be the quantum and deficit counter values for DRR, and (S, F, V) values for WF²Q+. Otherwise, if the HOL packet is banned, the scheduler starts searching for the unbanned flow (in the same queue) that has received the worst service in the past (lines 5–6). If no unbanned flow exists, the Scheduler considers the entire queue as no longer servable and selects another queue among the backlogged ones, if any (lines 7–9). If at least an unbanned flow exists, the first enqueued packet belonging to this flow is selected and the scheduling variables are updated accordingly (lines 10–14). Also credit/debit counters for the originally selected flow and the substitute flow are consequently updated.

PACKET CLASSIFIER | QoS and Fairness in WiMAX

Packets received by the BS and destined to the DL are sorted by the packet classifier and buffered into one of the per-class queues in the BS, according to the class of service they belong to. In the queues, packets wait for transmission over the air toward a given SS. Queues are managed by the scheduler on a frame basis.

The main task of the classifier is to match the CID of the incoming packets with the traffic class they belong to, and to queue such packets in their relevant buffers. Only the service received by rtPS, nrtPS, and BE queues will be analyzed, because flows belonging to the UGS and ertPS service classes are assumed to receive a constant reserved amount of bandwidth frame-by-frame and not need to be scheduled. This choice allows high demanding (UGS and ertPS) flows to save up the time required for the BR process.

Another important task of the classifier is to timestamp each incoming packet according to its arrival time. This information is exploited by the buffer manager to recognize when a queued packet’s timeout expires, i.e., when its elapsed waiting time exceeds the maximum tolerated latency.

CHANNEL- AND QoS-AWARE SCHEDULER DESIGN FOR WiMAX NETWORKS

In this section some design guidelines are given for a “channel-aware” and “QoS-aware” scheduler to be implemented at the BS of a WiMAX PMP network for the delivery of DL traffic to a set of distributed SSs with active connections of different traffic nature. The scheduling algorithm, which is running at the WiMAX base station, needs to fulfill the following requirements:

§  Efficient link utilization: The scheduler shall take opportunistic decision and not assign a transmission opportunity to a flow with a currently low-quality link, because the transmission will be wasted.

§  Delay bound: The algorithm shall be able to provide delay bound guarantees for individual flows, to support delay-sensitive applications; besides, it shall prevent too late packet transmissions from wasting bandwidth.

§  Fairness: The algorithm shall redistribute available resources fairly among flows; thus providing short-term fairness to error-free flows and long-term fairness to error-prone flows.

§  Throughput: The algorithm shall provide guaranteed short-term throughput to error-free flows and guaranteed long-term throughput to all flows.

§  Implementation complexity: A low-complexity algorithm is necessary to take quick scheduling decisions.

§  Scalability: The algorithm shall operate efficiently when the number of flows sharing the channel increases.

To match all the above-mentioned needs, (1) a class-based wireless scheduling is recommended to fulfill the WiMAX service class differentiation needs, and also to simplify interworking with the Internet (supporting class-based differentiated services); (2) “per class” service differentiation must be achieved, and simple “per flow” mechanisms (e.g., lead/lag counters per each flow) must be provided to guarantee fair service to traffics within a class; (3) channel awareness must be exploited to make efficient use of wireless resources, and a compensation technique for missed transmission opportunities must be provided to guarantee proportional fairness in sharing the bandwidth; (4) useless compensation must be avoided through simple measures, e.g., periodic buffer cleaning of over-delayed packets could be used; and (5) simple expedients must be provided to avoid monopolization of the scheduler by a lagging flow after the recovery of its channel, and to guarantee graceful throughput degradation of leading flows; this could come at a very low cost by using combination of lead/lag counters and queue parameters.

In Figure 1, the reference channel- and QoS-aware scheduling architecture is illustrated. It is considered to be implemented at the MAC layer of a WiMAX BS, which manages local traffic queues for packet delivery over the DL channel. The illustrated framework must be able to provide per-class differentiated QoS and fair service to flows in the same class through the operation of the following QoS-support modules:

§  An error-free service scheduler that decides how to provide service to traffic flows based on an error-free channel assumption.

§  A lead/lag counter for each traffic flow that indicates whether the flow is leading, in sync with, or lagging its error-free service model and in which extent.

§  A compensation technique that is used to improve fairness among flows. A lagging flow is compensated at the expense of a leading flow when its link becomes error free again. The system maintains credit/debit counters for each lagging/leading flow.

§  Separate per-class packet queues used to support rtPS, nrtPS, and BE traffic flows.

§  A means for monitoring and predicting the channel state of each backlogged flow.

Figure 1: Channel-aware QoS scheduling architecture in the BS.

SOME OPEN RESEARCH ISSUES | Scheduling in WiMAX

In the foregoing discussion we have alluded to various incomplete studies and opportunities for further research. In this section, we shall list some open research issues related to QoS scheduling in WiMAX, viz.,

§  An open issue is to how to provide tight delay and throughput guarantees in rtPS and ertPS traffic classes while using round robin schedulers, i.e., WRR and DRR. Also, the applications of other variations of round robin, such as smoothed round robin and stratified round robin, need to be further investigated.

§  Integration of time-stamped schedulers, such as WF²Q, SCFQ, and SFQ, with IWFQ type of algorithms for wireless networks, thus designing schedulers that are specific for high priority traffic classes of WiMAX.

§  The use of IWFQ within rtPS and ertPS traffic classes needs to be investigated further, as it requires significant support from the MAC layer.

§  The CIF-Q algorithm has higher complexity, and authors have argued that the wireless part has a lower bandwidth, which is obviously not true in the case of WiMAX. Thus, an interesting area for further work is to investigate the behavior of CIF-Q with rtPS and ertPS traffic classes.

§  Design of dynamic and efficient priority-based mechanisms for distribution of the allocated grants among the various classes at SS. The issues of inter- and intraclass fairness need to be investigated further.

§  Development of intelligent bandwidth requests, admission control, and bandwidth allocation schemes at the BS. Also, an investigation of efficient and adaptive techniques for traffic policing and shaping at BS/SSs is required.

§  Transforming the schedulers designed for PMP mode into the mesh mode of operation for WiMAX.

§  It is important to investigate the use of RED-based buffer management for BE at SSs. Also, the use of modern scheduling techniques, such as multiuser diversity, that exploit variations in wireless channels must be investigated. Similarly, cross-layer approach, adaptive bandwidth requests, and queue length based scheduling are needed to be investigated further. One of the basic issues with the cross-layer approach is how to cater for multiple SSs in the same time frame.

§  Performance measurements of WiMAX based services is also very important. For this purpose a test bed has been developed, which employs the well-known Packet-E-Model for estimation of voice quality. It is also important to develop models that can estimate performance of various services (voice/video/data) offered in WiMAX. Hence, this area also needs to be investigated further.

§  One of the important issues is cooperation between various current technologies, for the benefit of customers. In this regard, the interoperation WiMAX with 3GPP’s High Speed Packet Access based technologies would be very worthwhile to investigate.

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.