Research Challenges | Quality-Of-Service Scheduling for WiMAX Networks

Though WiMAX is the most promising technology for enabling BWA systems to be widely deployed, many issues need to be addressed to make it effectively support the requirements and constraints of end-users' multimedia flows. To do so, according to the discussion mentioned previously, an efficient QoS-enabled scheduling algorithm has to be designed and implemented. In this section, we point out and briefly describe the most promising, as well as challenging, directions in such a field, by outlining a research roadmap for QoS provisioning in WiMAX networks. As we considered the scheduling algorithm in isolation in the last section, we shall now present cross-layer approaches, in which performance improvements are obtained by making an appropriate use of information which comes from the lower or upper layers.

Though WiMAX is the most promising technology for enabling BWA systems to be widely deployed, many issues need to be addressed to make it effectively support the requirements and constraints of end-users' multimedia flows. To do so, according to the discussion mentioned previously, an efficient QoS-enabled scheduling algorithm has to be designed and implemented. In this section, we point out and briefly describe the most promising, as well as challenging, directions in such a field, by outlining a research roadmap for QoS provisioning in WiMAX networks. As we considered the scheduling algorithm in isolation in the last section, we shall now present cross-layer approaches, in which performance improvements are obtained by making an appropriate use of information which comes from the lower or upper layers.

§  Multiantenna architectures for WiMAX networks. In recent years, intensive research efforts have led to the development of spectrally efficient multi-user transmission schemes for wireless communications based on the use of multiple antenna systems. The use of multiple antennas in combination with appropriate signal processing and coding is indeed a promising direction which aims to provide a high-data rate and a high-quality wireless communications in the access link. In this sense, multiantenna systems can be seen as a way to enhance the cell capacity while offering a better and more stable link quality at the same time. On the other hand, antenna arrays can be used also to achieve beam-forming capabilities, with a remarkable improvement in terms of network performance. Adaptive Antenna Systems (AAS) are encompassed by the IEEE 802.16 standard to improve the PHY-layer characteristics. However, AAS can also act as enablers of spatial division multiple access (SDMA) schemes. In this way, multiple SSs, separated in space, can simultaneously trasmit or receive on the same subchannel. This, obviously, demands the realization of a scheduling algorithm able to effectively exploit the presence of such beam-forming capabilities. In this way, through a cross-layer approach, striking results can be obtained in terms of QoS support. An AAS-aware scheduling could indeed profit from the additional degree of freedom (i.e., the spatial dimension) provided by the underlying PHY techniques. Although this may lead to better performance, it also leads to an increase in the complexity of the scheduler itself. Nonetheless, we believe that the use of this and other related multiantenna techniques (e.g., space-time codes) represent a research direction with big potential in terms of throughput optimization. To fully take advantage of the power provided by multiple antenna systems, innovative QoS-enabled scheduling algorithms, able to work in both space and time dimensions, need to be designed and engineered.

§  Opportunistic scheduling. In wireless networks, channel conditions may vary over time because of user mobility or propagation phenomena. These effects are usually referred to as shadowing and fading, depending on their typical time-scales. They have been traditionally considered as harmful features of the radio interface due to their potentially negative impact on the quality of communication. However, recent research has shown that the time-varying nature of the radio channel can be used for enhancing the performance of data communications in a multi-user environment. Indeed, time-varying channels in multi-user environments provide a form of diversity, usually referred to as multi-user diversity, that can be exploited by an "opportunistic" scheduler, that is, a scheduler that selects the next user to be served according to the actual channel status . This approach may also be applied, at the cost of some additional complexity and signaling between PHY and MAC, to WiMAX networks. Opportunistic scheduling schemes do not usually apply to flows that require QoS guarantees, due to the unpredictable delays that may come from the channel dynamics. However, their use may actually lead to an enhanced QoS support. For example, improving the effect of non-realtime traffic (i.e., nrtPS and BE traffic) would free some additional resources to higher priority traffic. In this way, opportunistic scheduling schemes may actually help to increase the QoS capabilities of WiMAX networks. Moreover in this case, novel scheduling schemes are required to exploit multi-user diversity while providing QoS guarantees to the active traffic flows at the same time. It may be interesting to note that multiple antenna systems can actually be used to build up multi-user diversity by means of random beamforming mechanisms (usually referred to in the literature as "dumb" antennas ). Although this direction is somehow orthogonal in nature to the one (based on "smart antennas") outlined before, it could be worth investigating whether these two techniques may be implemented to coexist (e.g., in a timesharing fashion) to obtain the advantages of both approaches.

QoS support in mesh-based architectures. The techniques we have presented earlier as research challenges are aimed at providing a better QoS support in PMP architecture. However, they are still subject to the limits imposed by such an architectural choice in terms of service coverage, network capacity, and system scalability. One possible solution to overcome such problems could be the adoption of a mesh-based architecture [28]. In mesh topologies, direct communication among neighboring SSs is allowed, so enhancing the network coverage and possibly enabling the deployment of a fully wireless backbone connecting to an Internet gateway. While mesh-based architectures offer interesting possibilities thanks to its inherent flexibility, they also present many research challenges to be addressed in terms of MAC and packet routing. This is even more challenging in the case of QoS support for multimedia flows, where reliable levels of services have to be ensured by means of distributed algorithms. In this framework, a "double cross-layer" approach (where information is shared among PHY, MAC, and NET layers) may lead to potentially dramatic performance improvements compared with conventional layered solutions. This clearly entails the definition of radically innovative scheduling protocols, which are able to work in a distributed and collaborative way, so cooperating with the routing algorithms to provide QoS guarantees to SFs based on some PHY information. For example, the integration of scheduling and routing protocols can be based on the actual channel conditions, as well as on the level of interference in the network. ^[3] The application of these concepts to WiMAX networks is not straightforward, as it would imply some major modifications to the actual standard, in terms of both signaling (necessary for pursuing cross-layer optimization) as well as definition of basic functionalities and interfaces of the routing protocol to be employed.

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.

QoS Support in the 802.16 MESH Mode

In stark contrast to the PMP mode, the QoS in MESH mode is provisioned on a packet-by-packet basis. Thus, the per-connection QoS provisioning using the DSx messages as introduced previously is not applicable. This design decision helps to reduce the complexity of implementing the MESH mode considerably. However, the MESH mode even with this simplification is quite complex.

The CID in the MESH mode is shown in Figure 1. The mesh CID is used to differentiate the forwarding service a PDU should get at each individual node. As can be seen from Figure 1 it is possible to assign a priority to each MAC PDU. Based on the priority the transmission scheduler at a node can decide if a particular PDU should be transmitted before another. The field reliability specifies the number of retransmissions for the particular MAC PDU (if needed). The drop precedence specifies the dropping likelihood for a PDU during congestion. Messages with a higher drop precedence are more likely to be dropped. In effect, QoS specification for the MESH mode is limited to specifying the priority of a MAC PDU, the reliability, and its drop precedence. Given the same reliability and drop precedence and MAC PDU type (see Figure 1), the MAC will attempt to provide a lower delay to PDUs with higher priority. This QoS mechanism, however, does not allow the node to estimate the optimal bandwidth requirement for transmissions on a particular link. This is because (just based on the previous interpretation as presented in the 802.16 standard), the node is not able to identify the expected arrival characteristics of the traffic and classify it into the different categories as traffic requiring UGS, rtPS, nrtPS, or BE service.

Figure 1: MESH connection identifier (CID).

To summarize, QoS mechanisms in the MESH mode are not consistent with those provided for the PMP mode. In addition, the per-packet QoS specification for the MESH mode does not allow a node to optimally estimate the amount of bandwidth required for transmission on a link, as no information about the data scheduling service required for the traffic is included explicitly in the QoS specification in the mesh CID.

We next give an overview of the existing bandwidth request and grant mechanisms specified for the MESH mode of 802.16. This is followed by a description of our proposed QoS architecture, which enables efficient bandwidth management in the MESH mode and allows support of the data scheduling services consistent with those outlined for the PMP mode.

QoS Support in the 802.16 PMP Mode

The 802.16 MAC is connection-oriented. QoS is provisioned in the PMP mode on a per-connection basis. All data, either from the SS to the BS or vice versa is transmitted within the context of a connection, identified by the connection identifier (CID) specified in the MAC protocol data unit (PDU). The CID is a 16-bit value that identifies a connection to equivalent peers in the MAC at both the BSs as well as the SSs. It also provides a mapping to a service flow identifier (SFID). The SFID defines the QoS parameters which are associated with a given connection (CID). The SFID is a 32-bit value and is one of the core concepts of the MAC protocol. It provides a mapping to the QoS parameters for a particular data entity.

Figure 1 shows the core objects involved in the QoS architecture as specified in the standard for the PMP mode. As is seen from Figure 1 , each MAC PDU is transmitted using a particular CID, which is in turn associated with a single service flow identified by a SFID. Thus, many PDUs may be transmitted within the context of the same service flow but a single MAC PDU is associated with exactly one service flow. Figure 1 also shows that there are different sets of QoS parameters associated with a given service flow. These are the "ProvisionedQoSParamSet," "AdmittedQoSParamSet," and "ActiveQoSParamSet." The provisioned parameter set is a set of parameters provisioned using means outside the scope of the 802.16 standard, such as with the help of a network management system. The admitted parameter set is a set of QoS parameters for which resources (bandwidth, memory, and so on) are being reserved by the BS (SS). The active parameter set is the set of QoS parameters defining the service actually being provided to the active flow. For example, the BS transmits uplink and downlink maps specifying bandwidth allocation for the service flow's active parameter set. Only an active service flow is allowed to transmit packets. To enable the dynamic setup and configuration of service flows, the standard specifies a set of MAC management messages, the so-called dynamic service messages (DSx messages). These are the dynamic service addition (DSA), dynamic service change (DSC), and the dynamic service deletion (DSD) messages. The various QoS parameters associated with a service flow are negotiated using these messages.

Figure 9.2: Quality-of-service (QoS) object model for IEEE 802.16-2004 point-to-multipoint mode.

Typical service parameters associated with a service flow are traffic priority, minimum reserved rate, tolerated jitter, maximum sustained rate, maximum traffic burst, maximum latency, and scheduling service. The BS may optionally create a service class as shown in Figure 1 . A service class is a name given to a particular set of QoS parameters, and can be considered as a macro for specifying a set of QoS parameters typically used. The value for the scheduling service parameter in the QoS parameter set specifies the data scheduling service associated with a service flow. The 802.16 standard currently defines the following data scheduling services: Unsolicited Grant Service (UGS), Real-Time Polling Service (rtPS), Non-Real-Time Polling Service (nrtPS), and Best Effort (BE). The UGS is meant to support real-time data streams consisting of fixed-size data packets issued periodically. The rtPS is meant to support data streams having variable-sized data packets issued at periodic intervals. The nrtPS is designed to support delay-tolerant streams of variable-sized data packets for which a minimum data rate is expected. The BE traffic is serviced on a space-available basis. For service flow associated with the scheduling service UGS, the BS allocates a static amount of bandwidth to the SS in every frame. The amount of bandwidth granted by the BS for this type of scheduling service depends on the maximum sustained traffic rate of the service flow. For rtPS service flows, the BS offers real-time, periodic, unicast request opportunities meeting the flow's requirements and allowing the SS to request a grant of the desired size. For nrtPS the BS, similar to the case of a rtPS service flow, offers periodic request opportunities. However, these request opportunities are not real-time, and the SS can also use contention-based request opportunities in addition to the unicast request opportunities for a nrtPS service flow as well as the unsolicited data grant types. For a BE service flow no periodic polling opportunities are granted. The SS uses contention request opportunities, unicast request opportunities, and unsolicited data grant burst types. 

To summarize, the PMP mode provides the BS with efficient means to manage the bandwidth optimally and at the same time satisfy the requirements of the individual admitted service flows.

QoS Architecture for Efficient Bandwidth Management in the IEEE 802.16 Mesh Mode

The IEEE 802.16 standard series represents the state-of-the-art in technology for metropolitan area broadband wireless access networks. The point-to-multipoint (PMP) mode of IEEE 802.16 has been designed to enable quality of service (QoS) in operator-controlled networks and, thus, is foreseen to complement existing third-generation cellular networks. In contrast, the optional mesh (MESH) mode of operation in IEEE 802.16 enables the setup of self-organizing wireless multi-hop mesh networks. A distinguishing characteristic of the IEEE 802.16 standard series is its support for QoS at the Medium Access Control (MAC) layer. However, the QoS specifications and mechanisms for the PMP and the MESH mode are not consistent. This article presents a novel QoS architecture as a key enhancement to the IEEE 802.16 MESH mode of operation. The architecture is based on the QoS mechanisms outlined for the PMP mode and, thus, enables a seamless coexistence of the PMP and the MESH mode. In particular, we look at the various options the standard provides and the trade offs involved when implementing QoS support in the 802.16 MESH mode, with a focus on the efficient management of the available bandwidth resources. This article is meant to provide researchers and implementers crucial anchor points for further research.

1 Introduction and Motivation

The demand for ubiquitous connectivity is the driving force for innovation in the field of wireless networks. To satisfy the differing demands of users a huge variety of wireless network platforms has developed over the years. Figure 1 shows some of the contemporary wireless access technologies.

From the figure, one can see that the IEEE 802.16 standard as published in  intends to support metropolitan area networks, rural networks, or enterprisewide networks. Initially these networks are expected to support only static nodes (subscriber stations). The standard IEEE 802.16-2004 specifies two modes of operation as shown in Figure 2. In the point-to-multipoint mode (PMP) all the Subscriber Stations (SSs) are required to be in direct range of the Base Station (BS). The SSs can directly communicate only with the BS. Direct communication between two SSs is not supported in the PMP mode. On the other hand, when operating in the MESH mode, the SSs are allowed to establish communication links with neighboring nodes and are able to communicate with each other directly. In addition, they are also able to send traffic to and receive traffic from the BS (a MESH BS is a SS, which provides backhaul services to the mesh network). The MESH mode of 802.16 allows for flexible growth in the coverage of the mesh network and also increases the robustness of the network due to the provision of multiple alternate paths for communication between nodes. An overview of the 802.16 standard is provided in. In addition, current efforts in the 802.16e task group have led to the publication of the IEEE 802.16e specification. The latter mainly offers enhancements to the IEEE 802.16-2004 to support mobility.

Figure 1: (a) Overview of contemporary wireless access network technologies showing the geographical scale of the wireless technologies. (b) Point-to-multipoint (PMP) mode of operation in 802.16. (c) Mesh mode (MESH) of operation in 802.16.

Figure 1: (a) Overview of contemporary wireless access network technologies showing the geographical scale of the wireless technologies. (b) Point-to-multipoint (PMP) mode of operation in 802.16. (c) Mesh mode (MESH) of operation in 802.16.

A distinguishing feature of the IEEE 802.16 standard is the extensive support for QoS at the MAC layer. In addition, the IEEE 802.16 standard outlines a set of physical layer (PHY) specifications which can be used with a common MAC layer. This flexibility allows the network to operate in different frequency bands based on the users' needs and the corresponding regulations. The QoS support and flexibility at the PHY layer in the 802.16 standard make it an optimal base to support multi-service networks. Thus, 802.16 networks are expected to play a significant role in next-generation broadband wireless access (BWA) networks. Such networks cater to the demand for the so-called "Triple Play" networks, that is, a single network supporting broadband Internet access, telephony, and television services. They are thus expected to replace conventional Digital Subscriber Line (DSL)-based access networks. The needs of each of these application categories are however varying. For example, applications such as interactive video conferencing, telephony, etc. require predictable response time and a static amount of bandwidth continuously available for the life-time of the connection. On the other hand, traffic like variable rate compressed video streams (e.g., to support television services) relies on accurate timing between the traffic source and destination but does not require a static amount of bandwidth over the duration of the connection. Some other applications such as data transfer using File Transfer Protocol (FTP) have no inherent reliance on time synchronization between the traffic source and destination. However, these applications benefit when the network attempts to provide a guaranteed bandwidth or latency. Some other services may not be very important from the providers' point of view, and traffic belonging to this class may be serviced on space-available basis. This type of traffic has usually no reliance on time synchronization between the traffic source and destination. An example of application generating the latter type of traffic is web surfing. The 802.16 standard defines different data scheduling services to support these types of traffic; thus, providing tools for network operators to support multi-service networks.

The optional MESH mode of operation specified by the standard allows for organic growth in coverage of the network, with low initial investment in infrastructure. In addition, a mesh inherently provides a robust network due to the possibility of multiple paths for communication between nodes. Thereby, a mesh can help to route data around obstacles or provide coverage to areas which may not be covered using the PMP setup with a similar position for the BS as in the MESH mode. A mesh also enables the support of local community networks as well as enterprisewide wireless backbone networks. This application scenario makes the MESH mode very attractive to network providers, companies, and user communities. This article focuses on efficient management of bandwidth for realization of QoS in the MESH mode. In particular we look shortly at the nuts and bolts involved and the options provided by the standard. Although the IEEE 802.16-2004 standard specifies an extensive set of messages and mechanisms to realize QoS, the algorithms to realize QoS and manage bandwidth are left open to foster innovation and provide scope for vendor optimization. This article provides the readers with an overview of the scope for innovation and some critical challenges that need to be addressed to obtain a robust and efficient implementation of the IEEE 802.16 MESH mode.

WeWewwe provide an overview of the QoS specification for the MESH mode as specified by the 802.16 standard. In particular, we introduce the mechanisms available in the PMP mode and the MESH mode. In future, IEEE 802.16-based networks are expected to support seamless interworking of nodes operating in the PMP and the MESH modes. The QoS specifications for the two modes however are not consistent. We provide an overview of our proposed QoS architecture for management of the bandwidth in the MESH mode to enable support of the data scheduling services similar to those available in the PMP mode.

Finally, we provide an insight into the benefits and effects of deploying our proposed QoS architecture which we have been able to observe via an intensive simulation study. The simulation study was carried out using a MESH mode simulator we built into the JiST/SWANS environment. We will here also highlight some promising areas for further investigation and outline areas for research which can build up on and extend the QoS architecture described by us.