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.

Quality-Of-Service Scheduling for WiMAX Networks

Nicola Scalabrino, D. Miorandi, Francesco De Pellegrini, R. Riggio, Imrich Chlamtac, and E. Gregori

The broadband wireless world is moving toward the adoption of WiMAX (the commercial name of the IEEE 802.16 standard) as the standard for broadband wireless Internet access. This will open up a very large market for industry and operators, with a major impact on the way Internet access is conceived today. On the other hand, the emergence of innovative multimedia broadband services is going to impose severe quality of service (QoS) constraints on underlying network technologies. In this work, after a brief review of the IEEE 802.16 standard, we intend to present an in-depth discussion of its QoS support features. We point out the scheduling algorithm as the critical point in QoS provisioning over such networks, and discuss architectural and algorithmic solutions for an efficient support of multimedia flows. Performance measurements obtained from an experimental test-bed are also presented. The chapter concludes with a description of the key research challenges in the area, and provides a roadmap for the research in the field.

Introduction

The IEEE 802.16 standard, promoted by the WiMAX (Worldwide Interoperability for Microwave Access) forum, will be the leading technology for the wireless provisioning of broadband services in wide area networks. Such technology is going to have a deep impact on the way Internet access is conceived, by providing an effective wireless solution for the last mile problem.

The market for conventional last mile solutions (e.g., cable, fiber, and so on) presents indeed high entrance barriers, and it is thus difficult for new operators to make their way into the field. This is due to the extremely high impact of laborintensive tasks (i.e., digging up the streets, stringing cables, and so on) that are required to put the necessary infrastructure into place. On the other hand, the market is experiencing an increasing demand for broadband multimedia services , pushing toward the adoption of broadband access technologies. In such a situation, broadband wireless access (BWA) represents an economically viable solution to provide Internet access to a large number of clients, thanks to its infrastructure-light architecture, which makes it easy to deploy services where and when it is needed. Furthermore, the adoption of ad hoc features, such as self-configuration capabilities in the Subscriber Stations (SSs) would make it possible to install customer premises equipment without the intervention of a specialized technician, so boosting the economical attractiveness of WiMAX-based solutions. In this context, WiMAX is expected to be the key technology for enabling the delivery of highspeed services to the end users.

Typical BWA deployments will rely on a point-to-multipoint (PMP) architecture, as depicted in Figure 1a, consisting of a single Base Station (BS) wirelessly interconnecting several SSs to an Internet gateway. The standard also supports, at least in principle, mesh-based architectures, like the one plotted in Figure 1b. While WiMAX-based mesh deployments could play a relevant role in the success of such technology, the current standard is far from off ering a real support to such architecture. Therefore, we intend to restrict the scope of our work to the PMP architecture only.

Figure 10.1: Typical WiMAX system configuration—(a) point-to-multipoint; (b) mesh.

Figure 10.1: Typical WiMAX system configuration—(a) point-to-multipoint; (b) mesh.

In terms of raw performance, WiMAX technology is able to achieve data rates up to 75 Mb/s with a 20 MHz channel in ideal propagation conditions. But regulators will often allow only smaller channels (10 MHz or less) reducing the maximum bandwidth. Although 50 km distance is achievable under optimal conditions and with a reduced data rate (a few Mb/sec), the typical coverage will be around 5 km in non-line-of-sight conditions and around 15 km with an external antenna in a line-of-sight situation. Moreover, such a wide coverage makes it possible, and economically viable to provide broadband connectivity in rural and remote areas, a market which is usually not covered by traditional service providers.

The fundamental requirements for WiMAX to define itself as a possible winning technology are data reliability and the ability to deliver multimedia contents. Indeed, the provision of QoS guarantees will be a pressing need in the next generation of Internet, to enable the introduction of novel broadband multimedia applications. Users are actually getting more and more interested in broadband applications (e.g., video streaming, video conferencing, online gaming, and so on) that require assurances in terms of throughput, packet delay and jitter, to perform well. This applies also to WiMAX networks, which have also to face all the problems related to the hostile wireless environment, where time-varying channels and power emission mask constraints make it difficult to provide hard QoS guarantees. This entails the definition of a Medium Access Control (MAC) protocol which is able to effectively support such multimedia applications, while on the other hand, it efficiently exploits the available radio resources. The IEEE 802.16 standard encompasses four classes of services, with different QoS requirements and provides the basic signaling between the BS and the SS to support service requests/grants. However, the scheduling algorithms to be employed in the BS and the SS are not specified and are left open for the manufacturers to compete.

In this paper, after a brief review of the standard fundamentals, we will provide an in-depth overview and discussion on the QoS support provided by WiMAX technology. Particular attention will be devoted to scheduling algorithms for WiMAX networks. We will survey the existing literature, and point out some common issues involved in well-known technologies (e.g., wireless ATM), from which a system designer can draw to design an efficient scheduler without starting from scratch. Performance measurements obtained from an experimental test-bed are also presented. This chapter concludes with an overview of the actual research challenges, pointing out and detailing the most promising directions to pursue for research in this field.

Frame Structure and Bandwidth Management in the MESH Mode

The 802.16 network supports only time division duplex (TDD) in the MESH mode. Figure 1 shows the corresponding frame structure. The time axis is divided into frames of a specified length decided by the mesh BS. Each frame is in turn composed of a control subframe and a data subframe. There are two types of control subframes, namely the network control subframe and the schedule control subframe. Network control subframes are used to transmit network configuration information as well as to allow new nodes to register and join the network. The schedule control subframe is used by nodes to transmit scheduling information, and to request and grant bandwidth for transmission. All data transmissions take place in the data subframe using slots previously reserved by the node for transmission. The control subframe is divided into a number of transmission opportunities and the data subframe is divided into a number of minislots. The length of the control subframe depends on the mesh configuration in use. This decides the number of transmission opportunities in the control subframe and the number of minislots in the data subframe. The MESH mode supports coordinated centralized scheduling, and coordinated as well as uncoordinated distributed scheduling for allocating bandwidth for transmission on individual links in the MESH mode of operation. The mesh configuration specifies a maximum percentage of minislots in the data subframe allocated to centralized scheduling. The remainder of the data subframe as well as any minislots not occupied by the current centralized schedule can be used for distributed scheduling.

Figure 1: MESH frame structure. Abbreviations—MAC, Medium Access Control; PDU, protocol data units.

In centralized scheduling, the bandwidth is managed in a more centralized manner than when using distributed scheduling. Thus, although the computation of the actual transmission schedule is done by the individual nodes independently (in a distributed manner), the grants for each individual node are controlled centrally by the BS in coordinated centralized scheduling (also called centralized scheduling). The BS uses centralized scheduling to manage and allocate bandwidth for transmissions up and down the routing tree (scheduling tree, see Figure 2 for an example) from the BS to the SSs up to a specified maximum hop limit. The routing tree is advertised by the BS periodically using MSH-CSCF messages. The BS in the mesh network gathers resource requests from individual SSs within the maximum hop range. Each SS in the scheduling tree accumulates the requests from its children and adds to it its own requirement for uplink bandwidth before forwarding the request upwards along the scheduling tree (uplink here implies transmission along a link in the scheduling tree from a SS to another SS that is closer to the BS; downlink will be considered to be a transmission down the tree in the opposite direction). The BS collects all the requests and transmits the grants to its children. The grants for each individual SS are then propagated down the scheduling tree hop-by-hop. Nodes use MSH-CSCH messages to propagate requests and grants for centralized scheduling.

Figure 2: Overview of scheduling in the MESH mode.

The grants propagated to the SSs in the scheduling tree do not contain the actual schedule. Each SS computes the schedule using a predetermined algorithm and the parameters obtained from the grant. Using centralized scheduling, transmissions can be scheduled only along the links in the scheduling tree. To reserve bandwidth for transmission on links not in the scheduling tree, distributed scheduling has to be used.

Distributed scheduling is used by a node to reserve bandwidth for transmission on a link to any other neighboring node (also for links included in the centralized scheduling tree). Nodes use distributed scheduling to coordinate their transmissions in their two-hop neighborhood. The nodes use a distributed election algorithm to compete for transmission opportunities in the schedule control subframe. A pseudo-random function (the mesh election algorithm specified in the 802.16 standard), with the node IDs of the competitors and the transmission opportunity number as input determines the winning node. The losing nodes compete for the next DSCH transmission opportunity until they win. The parameter XmtHoldoffExponent of each node determines the magnitude of transmission opportunities a node has to wait after sending a distributed scheduling message (MSH-DSCH) in a won transmission opportunity. 

The mean time a node has to wait between two won transmission opportunities for distributed scheduling messages depends on the number of nodes in the two-hop neighborhood, the node's own XmtHoldoffExponent, and the network topology. It show that the time a node has to wait between two distributed scheduling transmission opportunities it wins increases with an increase in the number of two-hop neighbors and moreover with an increase in the value of the XmtHoldoffExponent.

When using coordinated distributed scheduling, the nodes broadcast their individual schedules (available bandwidth resources, bandwidth requests, and bandwidth grants) using transmission opportunities won by the node in the schedule control subframe. The mesh election algorithm ensures that when a node wins a transmission opportunity in the schedule control subframe for transmission, no other node in its two-hop neighborhood will simultaneously transmit. Thus, it is ensured that the scheduling information transmitted by a node in the schedule control subframe can be received by all of the nodes' neighbors. To enable a conflict-free schedule to be negotiated each node maintains the status of all individual minislots in the frame. A minislot at any point in time may be either in status available (node can receive or transmit data in minislot), receive available (node can only receive data in minislot), transmit available (node can only transmit data in the minislot), or unavailable (node may not transmit or receive data in the minislot).

The schedule negotiated using coordinated distributed scheduling is such that it does not lead to conflict with any of the existing data transmission schedules in the two-hop neighborhood of the transmitter. On the other hand, nodes can also establish their transmission schedule by directed uncoordinated requests and grants between two nodes. In contrast to coordinated distributed scheduling requests and grants which are sent in the schedule control subframe, the uncoordinated requests and grants are sent in the data subframe. The latter scheduling mechanism is called uncoordinated scheduling. When a node SS3 wants to reserve slots for transmission to a neighbor node SS4, they exchange scheduling information using slots in the data subframe reserved for transmissions between the two nodes (see Figure 2). Nodes individually need to ensure that their scheduled transmissions do not cause collisions with the data as well as with control traffic scheduled by any other node in their two-hop neighborhood. Transmissions in the data subframe using slots reserved for transmission to a particular neighbor may not be received by all the other neighbors due to other simultaneous transmissions. Thus, the schedule negotiated using the data subframe (uncoordinated scheduling) may not be known to all the neighbors of the nodes involved in the uncoordinated schedule. The neighbors of these nodes may then schedule conflicting transmissions due to lack of the previous uncoordinated schedule information. Hence, uncoordinated scheduling may lead to collisions and is not suitable for long-term bandwidth reservations. Nodes use MSH-DSCH messages to transmit the bandwidth requests grants and negotiate schedules when using distributed scheduling (both coordinated as well as uncoordinated distributed scheduling).

In contrast, centralized scheduling allows the setup of a transmission schedule for transmissions only along links in the scheduling tree, and hence, is not very suitable for enabling a wireless mesh network in the traditional sense. We next outline our novel proposed QoS architecture for bandwidth management in the MESH mode. Without loss of generality and to avoid confusion in the following discussion we assume that the nodes in the mesh network use only distributed scheduling.

The proposed QoS architecture using distributed scheduling is easily extensible and can be adapted for use in centralized scheduling, too. The proposed architecture uses a combination of coordinated distributed scheduling and uncoordinated distributed scheduling to efficiently manage the bandwidth in the network.