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.

BANDWIDTH REQUESTS AND CINR REPORTS | QoS and Fairness in WiMAX

To make the channel-aware scheduler effectively operate, information about the quality of the wireless links toward each SS must be gathered by the BS. To this aim, the wireless channel state is continuously monitored by each SS, which gets CINR (carrier to interference and noise ratio) measurements, updates estimates of the CINR’s mean and standard deviation values, and reports them back to the BS through specific signalling messages provided by the IEEE 802.16 standard, e.g., through BR messages (normally used by SSs for requesting bandwidth), which can also include the CINR report.

The compensation block is in charge of collecting received information on the channel qualities and making the BS aware of the status of each link toward the SSs. Two assumptions hold in our reference scenario:

§  Wireless channel quality of each connection changes on a per-frame basis, but it remains constant for a frame duration; i.e, the BS assumes that the CINR report received by the SS at the frame beginning is valid for the entire subsequent frame duration. This is equivalent to modelling a block-fading channel, which is a feasible assumption for the slowly varying radio links of the fixed WiMAX PMP scenario.

§  Perfect channel state information is available at the BS. This means that the CINR reports must be correctly received by the BS over an error-free feedback channel.

The monitored channel quality at the SS is compared against the allowed values of signal-to-noise ratio and receiver sensitivity for each transport mode (burst profile) at a given bit error rate (BER). As soon as the received power level becomes lower than the receiver sensitivity threshold for a given DL transport mode and target BER, then a more robust profile must be chosen. This change in the transport mode can proceed until the most robust modulation/coding scheme (BPSK modulation with 1/2 coding rate) is chosen. A channel is considered “good” as long as a more robust transport mode can be selected, which is capable to cope with the channel adverse conditions. Otherwise, the channel is finally considered as “bad.”

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.

PERFORMANCE MEASUREMENTS FOR WiMAX NETWORKS

It has been noted that, at the time of writing, there is not much published work available regarding real-life performance evaluation of WiMAX networks. However, some of the currently available literature will be briefly described in this section.

WiMAX test-bed based results for measurements in the field have been reported. The Alvarion test bed, BreezeMax http://www.alvarion.com/, operating in the 3.5 GHz licence band and fully IEEE 802.16-2004 compliant, has been employed for measurements. Experimental data has been collected for four nodes operating in PMP mode in a rural residential environment. A sectorial antenna with a gain of 14 dbi, covering all three SS (FDD half duplex), has been deployed. All nodes run using a Linux distribution and are attached to WiMAX equipment through the Ethernet. Data flow and CBR VoIP are generated by the freely available tool known as D-ITG, http://www.grid.unina.it/software/ITG/;

It has been observed that the performance of a G.711 codec is far too low to be acceptable and SS cannot support more than two high quality calls. The G.723.1 codec outperforms G.729.2. It has been pointed out that UL measurements contradict simulation results and its earlier version, where larger delays in UL are ascribed to bandwidth request mechanisms and PHY overhead. Due to activation of piggybacking for bandwidth reservation. It has also been pointed out that the R-factor, E-model, needs to be considered for scheduler design, though, nothing has been mentioned about the type of scheduler that was being used at SSs and BS during the test-bed measurements.

Recently, a performance study of UL Scheduling algorithms for PMP WiMAX has been carried out. It has studied major scheduling algorithms using the NS-2 simulator. Also, it provides pseudocode for various schedulers in a simple and accessible manner. The existing scheduling mechanisms have been divided into three categories: homogenous, heterogenous, and opportunistic types. It has been reported that EDF and (EDF+WFQ+FIFO) result in the lowest average delay for rtPS and ertPS; WRR, WFQ, and (EDF+WFQ) provide a fair distribution of bandwidth; the (EDF+WFQ) hybrid setup is fairer than (EDF+WFQ+FIFO). In addition, it has been concluded that most of the legacy schedulers are not very suitable for WiMAX applications. However, WFQ, cross-layer, and queueing theoretic-based schedulers are seen to be promising candidates for applications in a WiMAX network.

HETEROGENOUS FRAMEWORKS

These frameworks employ more than one type of scheduler for the various traffic classes of WiMAX.

WRR has been adopted for rtPS and nrtPS traffic classes, whereas simple RR has been employed for BE. It does not consider the ertPS traffic class and nor does it specify clearly whether or not GPSS is used.

Based on priority scheduling and dynamic bandwidth allocation, a QoS architecture for WiMAX. The contention slot allocator has been proposed to be used by the BS to dynamically adjust the ratio of the bandwidth allocated to the contention and reservation slots. WRR has been used as an upstream scheduler at the BS. At the SS level, there are two levels of scheduler, viz., (1) strict priority scheduling for distribution of allocated bandwidth among various classes and (2) schedulers for each of four classes. At the first level of scheduling at SS, the Multiclass Priority Scheduler has been suggested; whereas, at the second level of scheduling at the SS IWFQ has been proposed for higher priority, WRR for middle priority, and first-in-first-out (FIFO) for lower priority traffic classes of WiMAX. No experimental or simulation results have been presented.

A scheduling framework has been proposed, which is based on a centralized mechanism similar to the GPC mode of operation. The proposed UL packet scheduler requires three modules at the BS: an information module, a scheduling database module, and a service assignment module. The information module performs the following functions: retrieving the queue size information for each connection from bandwidth request messages, determining the number of packets that have arrived from an rtPS connection in the previous time frame by using arrival service concept, determining rtPS packets’ arrival time/deadlines and updating the scheduling database, queueing information from nrtPS, and BE request messages are directly passed to the scheduling database. The proposed scheduling database module will provide scheduling information to all of the connections; whereas the service assignment module determines UL-MAP by using information in the scheduling database. A strict priority scheduler is used for allocation of bandwidth from UGS, rtPS, nrtPS, and BE. Further, it has been proposed that there is no scheduler for UGS, EDF for rtPS, WFQ for nrtPS, and FIFO for BE. 

Deficit fair priority queueing (DFPQ) has been proposed for the first layer of scheduling at SSs. It has been derived from the DRR discipline. At the second layer of scheduling, EDF has been proposed for rtPS, WFQ for nrtPS, and WRR for BE. Some simulation results have also been presented. It is not clear whether GPSS or GPC has been employed for this work. However, the idea of DFPQ can be easily adopted for other advanced scheduling frameworks involving WiMAX.

A multiclass uplink fair scheduling structure (MUFSS), to support delay and bandwidth requirements of IEEE 802.16 QoS. The BS adopts modified WRR, but these details are not provided. At the SS, a modified WFQ has been suggested for UGS and rtPS classes; whereas, modified WRR and FIFO have been suggested for nrtPS and BE classes. Although MUFSS can provide guarantees for delay sensitive real-time traffic, it has less throughput overall and higher processing time.

HOMOGENOUS FRAMEWORKS

These frameworks employ a single kind of scheduler for all types of WiMAX traffic.

Simulations have been used to evaluate the QoS performance of WiMAX. DRR has been selected as a DL scheduler and WRR has been chosen as an UL scheduler. Similarly, both WRR and DRR have been selected, independently, to be employed at SSs. This chapter does not consider the application of a wide variety of other schedulers for the various traffic classes.

Two sets of simulation experiments are performed: first EDF for all traffic classes and second WFQ for all traffic classes. It has been reported in these studies that, if the total traffic load is under 100%, both schedulers can satisfy traffic class performance requirements. However, when one traffic class starts consuming more than its fair share of bandwidth, EDF favors streams with more crucial deadlines, whereas WFQ strives for fairness and punishes the flow that is unfair. It has been concluded that using either EDF or WFQ for all traffic classes is not optimal.

Based on the fair queueing model proposes a hierarchical scheduling model for WiMAX traffic classes. It specifies three types of scheduling servers, viz., hard-QoS, soft-QoS, and best effort servers. UGS traffic is mapped into the hard-QoS server and rtPS traffic into the soft-QoS server; whereas nrtPS can be mapped into either. All servers implement the WF²Q algorithm.

A token bucket based call admission control and an UL packet scheduler employing EDF. The focus of their algorithm is to meet the bandwidth and delay requirements of rtPS flows. It employs the arrival service curve and a two-dimensional rtPS database. However, this algorithm does not consider the ertPS traffic class. A token rate estimation model, for Poisson traffic fed to both an infinite and a finite queue, has been developed by employing well-known Markov chain models. The integration of admission control and scheduling has been left as future work. Thus, this approach needs to be investigated further before it can be adopted for use in WiMAX. It is also known that a potential problem with token bucket-based schemes involves allowing large bursts of traffic, for which a leaky bucket can be arranged after the token bucket