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.

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.