Tuesday, September 21, 2010

QoS Scheduling in WiMAX Networks

To offer an efficient QoS support to the end user, a WiMAX equipment vendor needs to design and implement a set of protocol components that are left open by the standard. These include traffic policing, traffic shaping, connection admission control (CAC), and packet scheduling.

Due to the highly variable nature of multimedia flows, traffic shaping and traffic policing are required by the SS, to ensure an efficient and fair utilization of network resources. At connection setup, the application requests network resources according to its characteristics and to the required level of service guarantees. A traffic shaper is necessary to ensure that the traffic generated actually conforms to the prenegotiated traffic specification. However, traffic shaping may not guarantee such conformance between the influx traffic and service requirements. This is dealt with by a traffic policer, which compares the conformance of the user data traffic with the QoS attributes of the corresponding service and takes corresponding actions, for example, it rejects or penalizes nonconformance flows.

QoS profiles for SS are usually detailed in terms of Committed Information Rate (CIR) and Maximum Information Rate (MIR) for the various QoS classes. The CIR (defined for nrtPS and rtPS traffic) is equal to the information transfer rate that the WiMAX system is committed to carry out under normal conditions. The MIR (defined for nrtPS and BE QoS types) is the maximum information rate that the system will allow for the connection. Both these QoS parameters are averaged over a given interval time.

To guarantee that the newly admitted traffic does not result in network overload or service degradation for existing traffic, a (centralized) CAC scheme also has to be provided.

Although all the aforementioned components are necessary to provide an efficient level of QoS support, the core of such a task resides in the scheduling algorithm. An efficient scheduling algorithm is the essential conditio sine qua non for the provision of QoS guarantees, and it plays an essential role in determining the network performance. Besides, a traffic shaper, policer, and CAC mechanisms are tightly coupled with the scheduler employed. Therefore, the rest of this section is devoted to such an issue.

Although the scheduling is not specified in the standard, system designers can exploit the existing rich literature about scheduling in wireless ATM, from which WiMAX has inherited many features. If this allows one not to start from scratch, existing schemes need to be adapted to match the peculiar features (e.g., traffic classes, frame structure) of the IEEE 802.16 standard.

As an example, the IEEE 802.16 scheduling mode can be seen as an outcome of the research carried out on hierarchical scheduling. This is rooted in the necessity of limiting the MAC exchange overhead by letting the BS handle all connections of each SS as an aggregated flow. As explained in the previous section, according to the standard, the SSs request bandwidth on per-connection basis; however, the BS grants bandwidth to each individual SS, so that the resources are allocated to the aggregation of active flows at each SS. Each SS is then in charge of allocating the granted bandwidth to the active flows, which can be done in an efficient way because the SS has complete knowledge of its queues status. This, however, requires the introduction of a scheduler at each SS, enhancing the complexity (and consequently the cost) of the SS equipment. A detailed operational scheme is depicted in Figure 10.3, outlining the role played by each component and the requests/grants mechanism at the basis of WiMAX QoS support.

Figure 1: Graphic representation of hierarchical scheduling.

Schedulers work on multiple connections to ensure the negotiated throughputs, delay bounds, and loss rates. The target of a scheduling algorithm is to select which connection has to be served next. This selection process is based on the QoS requirements of each connection. An efficient scheduling algorithm at the BS must be provided guarantee proper performance. To better explain the scheduler's role, let us first assume that the BS performs the scheduling functions on a per-connection basis. To schedule packets correctly, information such as the number of pending connections, their reserved throughputs, and the statues of session queues is needed. While this information is easily accessible as concerns downlink connections, the SSs need to send their bandwidth requests and queue status to the BS for the uplink. This has a twofold effect. On the one hand, it increases the signalling overhead, while, on the other hand, it provides the BS with information that may be not up-to-date (e.g., due to contention delays, and so on). In downlink, the scheduler has complete knowledge of the queue status, and, thus, may use some classical scheduling schemes, such as weighted round robin (WRR), weighted fair queueing (WFQ), etc. Priority-oriented fairness features are also important in providing differentiated services in WiMAX networks. Through priority, different traffic flows can be treated almost as isolated when sharing the same radio resource. However, due to the nature of WiMAX TDD systems, the BS scheduler is non-work-conserving, as the output link can be idle even if there are packets waiting in some queues. Indeed, after downlink flows are served in their devoted subframe, no additional downlink flows can be served till the end of the subsequent uplink subframe.

Scheduling uplink flows is more complex because the input queues are located in the SSs and are hence separated from the BS. The UL connections work on a request/grant basis. Using bandwidth requests, the uplink packet scheduling may retrieve the status of the queues and the bandwidth parameters. The literature is not rich in terms of QoS scheduling schemes specifically designed for WiMAX networks. In the following, we will briefly describe the most relevant works that address such a topic, to the best of the authors' knowledge.

In particular, they propose a scheduling process divided into two parts. The first one, executed by the uplink scheduler inside the BS, is performed to grant resources to the SSs in response to bandwidth requests. This is done by means of a classical WRR. At each SS, bandwidth assignments are computed by starting from the highest priority class (i.e., UGS flows) and then going down to rtPS, nrtPS, and BE. In this way, a strict priority among service classes is guaranteed. The scheduling schemes employed for the various classes are different. A classical WFQ  is used for UGS and rtPS, whereas a simpler WRR is used for nrtPS service class. BE traffic is served through a simple FIFO policy. By means of this prioritized approach (which resembles somehow multiclass priority fair queueing), the proposed architecture is able to guarantee a good performance level to UGS and rtPS classes, to the detriment of lower priority traffic (i.e., nrtPS and BE flows).

Via simulation, the performance of an IEEE 802.16 system using the class of latency-rate scheduling algorithms where a minimum reserved rate is the basic QoS parameter negotiated by a connection within a scheduling service. Specifically, within this class, they selected defict round robin (DRR) as the downlink scheduler to be implemented in the BS, as it combines the ability to provide fair queueing in the presence of variable length packets with the simplicity of implementation. In particular, DRR requires a minimum rate to be reserved for each packet flow being scheduled. Therefore, although not required by the IEEE 802.16 standard, BE connections should be guaranteed a minimum rate. This fact can be exploited to both avoid BE traffic starvation in overloaded scenarios, and let BE traffic take advantage of the excess bandwidth which is not reserved for the other scheduling services. On the other hand, DRR assumes that the size of the head-of-line packet is known at each packet queue; thus, it cannot be used by the BS to schedule transmissions in the uplink direction. In fact, with regard to the uplink direction, the BS is only able to estimate the overall amount of backlog of each connection, but not the size of each backlogged packet. Therefore, the authors selected WRR as the uplink scheduler. Like DRR, WRR belongs to the class of ratelatency scheduling algorithms. At last, DRR is implemented in the SS scheduler, because the SS knows the sizes of the head-of-line packets of its queues.
Related Posts with Thumbnails