Wimax standards and Security The Wimax

FIGURE 8.6
802.16 centralized scheduling. Mesh nodes send requests to the base station with MSH-CSCH
messages moving up the tree. The base station uses the information from the received
MSH-CSCH messages together with its knowledge of network topology to calculate a global TDMA schedule for the data subframe. The base station then updates the tree topology with the MSH-CSCF messages and transmits new bandwidth assignments with the MSH-CSCH messages. The nodes use the link bandwidths to find the transmission schedule. (a) Up-tree scheduling messages. (b) Down-tree scheduling messages.

contain connection bandwidths for every connection in the network, so each node can run an independent scheduling algorithm to arrive at a global trans- mission schedule. The new schedule takes place in the first frame after the last node in the tree receives its MSH-CSCH message.

= , ,
The 802.16 standard does not specify how connections should be assigned their bandwidth; however, it does propose an algorithm that the nodes can use to determine a transmission schedule for the entire network given an assignment of connection bandwidths. The scheduling algorithm proposed in Ref. 6 uses a breadth-first traversal of the routing tree to assign transmission opportunities for all connections in the network. The first-visited connection, in the traversal of the tree, is assigned transmission opportunities at the begin- ning of the data subframe. The number of transmission opportunities needed to satisfy the bandwidth allocation B for the connection are found with
Duration ^{BTf /b + Ng} (8.5)
DataTxOppSize

「·
where denotes the ceiling of a real number, b the highest number of bits that can be transmitted in each OFDM symbol on the connection, DataTxOppSize the number of OFDM symbols in each transmission opportunity, N_g the number of guard OFDM symbols (two or three), and T_f the frame duration in seconds. The connection traversed next is assigned next available transmission opportunities and so on, until all connections are assigned the number of transmission opportunities corresponding to their bandwidth. If the total length of the schedule exceeds MSH-CSCH-DATA-FRACTION transmission opportunities, all con- nection bandwidths are scaled equally until the schedule is at most MSH-CSCH-DATA-FRACTION transmission opportunities long.

The scheduling algorithm in Ref. 6 does not take advantage of spatial reuse in the network, so it does not efficiently use the wireless bandwidth. A dif- ferent algorithm is proposed in Ref. 13. In that algorithm, the connections are assigned transmission opportunities in rounds. In each round, one trans- mission opportunity is allocated to all connections whose bandwidth is not satisfied and which are not conflicting with already-selected connections in the round. The connections are chosen in the order of decreasing unallocated bandwidth. The problem with this scheduling algorithm is that it assumes connections can transmit more than once in a frame. However, in 802.16, every transmission needs a guard time of two or three TDMA slots, meaning that at the highest modulation each transmission has an overhead of 216 or 324 bytes. The overhead decreases the value of the algorithm in Ref. 13. We propose an algorithm that can be used to find a global schedule in Ref. 14. Our algorithm limits the number of connection transmissions to one per frame. The algorithm uses the Bellman–Ford algorithm on the conflict graph for the network to find starting transmission opportunities for each connection. In Ref. 14, we also give a set of simple linear inequality constraints that guaran- tee that an allocation of connection bandwidths results in a feasible schedule. The base station can use the linear constraints to ensure that bandwidth assignments result in TDMA schedules without the need to scale down link bandwidths.
The transmission opportunities after the first MSH-CSCH-DATA-FRACTION
opportunities in the data channels are reserved with distributed scheduling. In distributed scheduling, nodes negotiate the distribution of transmission opportunities in a pairwise fashion. First, a node wishing to change the trans- mission opportunity allocation for one of its connections sends a request for transmission opportunities to its neighbors in an MSH-DSCH packet. One or more of the neighbors correspond with a range of available transmission opportunities. The node chooses a subrange of the available transmission opportunities and confirms that it will use them with a third MSH-DSCH packet. The 802.16 standard does not specify the algorithms that can be used to calculate which slots should be requested or released during the distributed scheduling. We provide a distributed scheduling algorithm in Ref. 15 that can be adapted for this purpose. In our algorithm, we use a dis- tributed Bellman–Ford algorithm to iteratively find the TDMA schedule from connection demands. The advantage of our algorithm is that the algorithm requires only a partial knowledge of the network topology, available from
802.16 neighbor tables, to determine a conflict-free TDMA schedule.
The centralized and distributed scheduling give rise to two different QoS levels in the mesh network. Connections established with the central- ized scheduling protocol have a guaranteed bandwidth, granted by the base station and known throughout the network. The hop-by-hop band- width guarantee in the centralized scheduling routing tree allows end-to-end QoS guarantees for the traffic flows traversing the tree. However connec- tions established with the decentralized scheduling protocol have a tran- sient behavior and a bandwidth dependent on the grants from the node’s

neighbors. The uncertainty in connection bandwidth translates to the best effort QoS to end-to-end flows using the connection scheduled with the distributed scheduling protocol.

An important question in the design of 802.16 mesh networks is the num- ber of transmission opportunities in the data channel that should be allocated for guaranteed traffic. Clearly, MSH-CSCH-DATA-FRACTION should be mini- mized so that as much bandwidth as possible be available for best effort traffic and enough bandwidth can be allocated for the services requiring guaranteed bandwidth. We minimize the number of slots needed to schedule links in the centralized scheduling part of the data frame in Ref. 14. The optimization finds the smallest value of MSH-CSCH-DATA-FRACTION required to support the requested link bandwidths, subject to the limit on TDMA propagation delay in the network. TDMA propagation delay occurs when an outgoing link on a mesh node is scheduled to transmit before an incoming link in the path of a packet [14].

4.