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.