UK Essays Services:

Free Help:

Multimedia Broadband WiMAX

QoS Support for Multimedia in IEEE 802.16 Networks

A Survey of Scheduling Techniques

Abstract

In the last few years, the demand for broadband access has grown rapidly. This has lead to an increase in internet based multimedia applications. The problem however is that this broadband access is expensive and cant be provided to remote locations. WiMAX is the last mile broadband wireless access solution which is intended to address these problems. One of the features of WiMAX is its differentiated treatment of different multimedia Quality of Service (QoS) requirements at the MAC layer. The objective of this paper is to do a survey of existing scheduling techniques for dividing bandwidth between traffics with different QoS requirements. The last section examines the effect of weighted round robin used with priority queuing on throughput in different WiMAX scenarios.

WiMAX the last mile Broadband Wireless Access Solution

Broadband Wireless Access (BWA) is one of the most promising solutions for broadband access. However BWA is still in its early stages of growth with IEEE Project 802 working group 16 working towards building its standards. In this regard, a commercial forum, Worldwide Interoperability for Microwave Access (WiMAX), was founded which includes more than 300 member companies.

It is envisioned, that WiMAX will provide the last mile internet access to residential users. This will be particularly useful in regions where wire lined infrastructure does not exist or can not be setup, such as rural areas and remote mountainous areas for instance. It is interesting to note, that WiMAX proved its importance during the devastating December 2004 Tsunami in Aceh, Indonesia which completely destroyed the existing infrastructure, and thus crucial communication took through WiMAX stations deployed rapidly on urgent basis. For small and medium enterprises, WiMAX will create an economical alternative to expensive leased line solutions. [1] [2]

Evolution of the WiMAX

IEEE 802.16 physical layer has evolved much since its first version was completed in October 2001. The first version operated between 10-66 GHz and specified a single carrier for a fixed Point-to-Multipoint (PMP) communication. The second version, 802.16a, extended the frequency band to below 11 GHz. This enabled non line of sight communication by employing the benefits of diffraction which are available only at lower frequencies. In this version, two OFDM based air interfaces; 256-carrier Orthogonal Frequency Division Multiplex (OFDM) and 2048-carrier Orthogonal Frequency Division Multiple Access (OFDMA) were also provided. This version also allowed mesh based topology in addition to the existing PMP communication. This version was followed by 802.16d published in June 2004. It incorporates all the previous versions to provide fixed BWA. Then came 802.16e, concluded in 2005, which supports full mobility at speed up to 70-80 m/s. [2] [6]

WiMAX MAC Layer and the Provisioning of Quality of Service

There are two types of WiMAX architectures; point-to-multipoint (PMP) and mesh. PMP consists of a base station (BS) which serves all the subscriber stations (SS) in its range. There is no communication between SSs. They all communicate through the BS. The BS is concerned with the setting up and management of the connections when an SS sends a request. The BS acts as a network gateway. In case there is communication between SSs as well, then it forms mesh architecture. The mesh architecture allows a connection over several hops and a tree network topology can be formed. The mesh and PMP are incompatible because PMP is only capable of single hop transmission. PMP has a lower signaling overhead than the mesh mode [14], [15]

For data transfer in WiMAX, downlink and uplink subframes are duplexed using either frequency-division duplex (FDD) or time-division duplex (TDD). [1] It should be noted that WiMAX is a connection oriented network

BS schedules the uplink and downlink grants at the start of each frame in order to meet the negotiated QoS requirements. Each SS finds the boundaries of its allocated uplink sub frame by decoding the UL-Map message. The DL-Map message contains information about the downlink grants in the forthcoming sub frame. Both maps are transmitted by the BS at the beginning of each downlink sub frame. This is done for both FDD and TDD modes. [1]

Providing quality of service (QoS) simultaneously to services with different requirements is a much more difficult task in wireless mediums as compared to wired networks because of its highly variable and unpredictable nature in terms of time-dependence as well as location dependence. To cope with such issues, QoS in wireless networks is handled at the medium access control (MAC) layer. [1]

An exciting feature of WiMAX is its support for QOS. It classifies all traffic according to four types:

Unsolicited Grant Services (UGS): because of a constant bit rate requirement, this category needs constant bandwidth allocation.

real-time Polling Services (rtPS): because of real time variable bit rate requirements, these applications need minimum bandwidth granted and have to request transmission resources by polling. Contention and piggybacking are not allowed.

non-real-time Polling Services (nrtPS): because of non real time flows, this category requires traffic polling. Bandwidth requests are allowed when minimum bandwidth requirements are needed, otherwise contention and piggybacking are used.

Best Effort Services (BES): best effort flows can make bandwidth request only with contention and no minimum resources allocation is granted. [16]

To design a good scheduling algorithm, the following issues must be catered to:

Bandwidth utilization must be efficient. For example, resources shouldn't be allocated to a bad link.

The scheduler should be able to cater to different QoS requirements with a guarantee on the long term throughput for all connections.

The scheduler should be fair in both the long run as well as the short run.

The scheduler should have a low complexity so that the decision making is rapid.

The system should be scalable. [17]

It is interesting to note that WiMAX standard does not specify the type of scheduling algorithm to be used and instead leaves it to the discretion of the vendor. Also the scheduling at the BS determines how much total bandwidth is to be allocated to each SS. It does not differentiate between the different traffics destined for the same SS. Thus the scheduling for these different traffics is done at the respective SS. [16]

Survey of Scheduling Techniques and Architectures

Many scheduling techniques and architectures have been explored for their viability in PMP WiMAX networks. Some of the more important ones have been discussed in the following paragraphs.

In [3], the proposed packet scheduler assigns priorities to the packets to be transmitted, based on the channel status reported by the user equipments as well as the QoS statistics maintained by the BS. Since the scheduler works in a global timeline, a time utility function (TUF) is used for the scheduling.

There are three steps in the scheduling algorithm. In the first step, the incoming packets are stored in the buffer corresponding to the SS and the traffic type. The QoS profiles of each arrived packet, such as the arrival time, deadline, packet type, head of line (HOL) delay, and packet size are also maintained.

In the next step, at each scheduling instance, the urgency factor of each HOL packet of each buffer is calculated from the TUF. The TUF of a real-time traffic is a straight line up till a threshold with a dead drop. Because it is a hard and discontinuous function in delay, the unit change of utility can not be obtained directly at its delay time. Thus a continuous TUF having straight line up till a threshold with a gradual z-shaped drop is used instead. The gradual decay occurs in the marginal scheduling time interval (MSTI) which is a small time window of delay jitters around the deadline. This relaxed z-shaped function is given by U_RT (t) = e^-a(t-c)/(1 + e^-a(t-c)) where a and c are the parameters which determine the slope and location of the point of inflection. The unit change of utility of a real time traffic at the inflection point (t = c) is given by |U'_RT (t = c)| = a/4, and this value forms the urgency factor. For non real time traffics, the TUFs are monotonic decreasing functions in time (delay). TUF of a non real time traffic is f_NRT(t) = 1 - exp(at)/exp(D) where D is the maximum time used for normalization purpose. The resulting urgency function is |U'_NRT(t)| = aexp(at)/exp(D).

Once the urgency has been calculated, the highest urgency factor for an SS out of the four buffers for that SS is taken as the representative for that user. The efficiency factor of each SS is then calculated. It is a moving average of the channel state of the SS, given by R(t) = (1 - 1/W)R'(t-1) + (1/W)R(t), where R(t) is the channel state at time t, R'(t) is the average channel state and W is the number of time slots up till time t. Finally, the scheduling priority value of each SS is calculated by p(t) = U'(t) * (R(t)/R'(t))

As a last step, based on the priorities calculated for each SS, the top n number of packets having the highest priorities are transmitted, where n is the number of different streams the OFDMA can send simultaneously.

The authors in [4] identified the method proposed by [3] as unsophisticated because non real time traffic carries a higher priority as long as the real time packet still have some time before their deadline. Thus they propose their own scheduling method, multiclass modified largest weighted delay first (MLWDF), to tackle this problem.

In their approach, the BS has a separate buffer for each traffic class and each buffer has queues for each SS. The traffic classes are prioritized and each traffic class indicates the urgency of each packet. At each scheduling instance, the scheduler checks the class priority and within the class having the highest priority, it considers the packet having the highest urgency. This urgency is determined by the HOL packet's waiting time in QoS traffic and the queue length information in BE traffic. As long as there are packets in a higher class buffer, the lower class buffer will never be taken into consideration. This approach has a serious problem of unfairness and starvation. For a fairer allocation, the authors suggest that QoS and BE packets be considered as one as long as the QoS packets don't approach their maximum allowable delay. When a QoS packet experiences a delay longer than some pre determined percentage of the maximum allowable delay, then the original method will take over.

In [5], the authors propose a hybrid of Earliest Due Date (EDD) and Weighted Fair Queue (WFQ). In EDD, all the arriving packets get a deadline stamp and are scheduled according to the increasing order of deadlines. In WFQ, a specific amount of resource is allocated to each connection, and according to the resulting assigned weight, each connection is served in turn. The authors suggest using EDD for real time and WFQ for non real time streams. They however don't mention the approach to take if both the traffic classes have non empty buffers. I suppose they intend to serve the real time traffic first and only if the real time buffer is empty will they consider BE traffic. This I believe will lead to starvation.

In [6], the authors consider two types of queues. The first type is used to schedule data grants for UGS and allocate request opportunities for rtPS and nrtPS. These grants are scheduled in a first in first out (FIFO) manner. Once the first queue type has been served, the scheduler will consider the second type. The second type of queues are used for scheduling data grants for rtPS, nrtPS and BE based on the information contained in the bandwidth request sent by the respective SS. Here, the BS scheduler first of all distributes the reserved bandwidth as determined by the bandwidth request messages. The residual bandwidth is distributed in a weighted queue manner. If the weight assigns more bandwidth than required to an SS, then any unused reserved bandwidth is distributed in the next round of excess bandwidth allocation.

In [7], the authors propose a Token Bank Fair Queuing (TBFQ) scheduling algorithm for WiMAX. Priority is calculated by E/r for each SS, where E is the number of tokens exchanged between the bank and that connection, and r is the reserved rate. A negative E means that the connection has used more than its assigned number of tokens. The SSs are served based on their token generation rate to guarantee throughput and latency and the remaining bandwidth is distributed according to the priority ranking. The parameters (debt limit, credit burst, and creditable threshold) determine the dynamic behavior of the algorithm.

A Frame Registry Tree Scheduler (FRTS) is proposed in [8]. This approach focuses on properly preparing future transmitted frames. As evident from the name, this approach uses a tree based approach. First level is taken to be the root. The second level represents time frames immediately after the current time frame. The third level represents the available modulation types. The fourth level organizes all the connections according to the SS each SS has one uplink node and one downlink node at this level. The fifth level organizes the connections according to their QoS. The last level consists of leaves for each active connection queue. The data structure presented achieves time frame creation and reduces the processing needs at the beginning of each frame. The algorithm schedules each packet at the last time frame before its deadline. This allows more packets to be transmitted and hence an increased throughput. This method also avoids fragmentation of transmissions to/from the same SS or same modulation. Another good feature is its ability to handle changes in the connection characteristics like modulation type or service type of the channel.

In the method proposed in [9], the BS polls each SS at specific intervals by either sending polling messages or allocating extra bandwidth for this purpose. Each SS generates bandwidth requests, which are either aggregate, or incremental. When a BS receives such a request message it updates its perception of the SS requirements. The specific scheduling algorithm used to complement this architecture is WFQ.

In [10], the scheduling architecture is divided into two layers. The first layer is for bandwidth requests. The authors propose a Deficit Fair Priority Queue (DFPQ) for scheduling at this layer. The BS maintains an active list which includes all the non empty queues. The scheduler visits all the queues in the active list and determines the number of requests in each. The variable DeficitCounter of a queue is incremented by the value of Quantum each time that queue is visited. If the requested data size of the bandwidth request packet at the head of the queue is less than or equal to the variable DeficitCounter, the variable DeficitCounter is reduced by the number of bits in the packet and the packet is transmitted. The process continues until the DeficitCounter is zero or the queue is empty. When this happens, the scheduler moves on to the next non empty priority queue. The Quantum is set to the aggregate of maximum sustained traffic rate in that service flow.

The second layer scheduling is for the data traffic. UGS are not scheduled because they already have a reserved bandwidth. For the other three traffic classes, a hybrid of scheduling algorithm is proposed. The authors suggest Earliest Deadline First (EDF) for rtPS traffic, where the packets with earliest deadline are scheduled first. For nrtPS, WFQ is proposed. Scheduling is based on the weight assigned to each HOL packet where weight is the ratio between that connection's minimum reserved traffic rate and the total sum of minimum reserved traffic rates of all the nrtPS connections. The bandwidth left is allocated to each BE traffic in a round robin (RR) manner.

The authors in [11] propose an architecture consisting of three schedulers. The first scheduler is concerned with UGS and rtPS flow, as well as rtPS and nrtPS polling flow. An EDF scheduling is applied in this scheduler. The second scheduler is concerned with flows requiring a minimum bandwidth mainly nrtPS. WFQ scheduling is used here where the weight is the size of the requested bandwidth. The third scheduler is used for BE traffic and here too a WFQ scheduling is employed where the weight is the traffic priority. Among the schedulers, the first level has the highest priority, and only after all the packets have been served, is the second scheduler considered. The third scheduler comes when the first two have become free.

Opportunistic Fair Scheduling scheme is proposed in [12]. The scheduler firstly computes the fair share weights for each connection based on the knowledge it has of the average gains of the channels. The associated data rate of each SS is calculated by the adaptive modulation process in BS. The scheduler then sorts in descending order each SS based on its achievable rate. Once the order and rate of transmission is determined, the down link sub frame is filled by the bursts in the order defined. The BS then updates the estimated average rate of transmission to each SS up till that time.

In [13], the authors propose the use of Maximum Delay Utility (MDU) scheduling for a mixture of delay sensitive and best effort traffic. To apply MDU scheduling, the authors use marginal utility functions with respect to the average waiting time for the corresponding QoS requirements. The marginal utility function for delay sensitive applications should be such that it meets all the conditions of the maximum stability region. And for the BE traffic, the function should be such that they control the greediness of their connections. The strength of MDU scheduling is that it can sense network congestion and react accordingly.

Simulations and Performance Analysis of the 802.16 MAC Layer

Scenario

[18], [19] and [20] have implemented publicly available WiMAX modules for NS2. For my analysis work, I selected the one implemented by Jenhui Chen et al [18], [19]. They have implemented unsolicited grant service (UGS) for the constant bit rate service, real-time polling service (rtPS) for the variable bit rate service, non-real-time polling service (nrtPS) for non-real-time variable bit rate service, and best effort service (BE) for service with no rate or delay requirements. Additionally, the extended real-time polling service (ertPS) for voice over IP (VoIP) service with silence suppression has also been implemented as is required in the 802.16e standard. The traffic is queued according to priority; in descending order UGS, rtPS, ertPS, nrtPS and BE. The scheduling between these queues is done in a weighted round robin fashion.

I have studied the effect of this model on the throughput and packet loss for all the five traffic types when the transport protocol used is UDP as well as when the underlying protocol is TCP. I have kept the number of service stations in the scenario at five and they communicate with each other through a single base station in a point to multipoint manner. I have not taken into consideration the mobility of the nodes. The following section summarizes the simulation results. All the figures have been provided in the appendix.

Observations

Effect of traffic and transport protocol

a) Individual Throughput

From fig. 1 and fig. 10, we see that if only BE traffic is used in all the five SS, the throughput graph is fairly similar for each traffic. However, if TCP is used then the variation in the graphs is lesser as compared to if UDP is used. This could be due to the fact that TCP is network friendly and hence in face of packet loss it would decrease its transmission rates. Thus TCP has lower and uniform drop rates as compared to UDP. If UDP is used, the five traffics face much variation in throughput in the early seconds. If TCP is used, then there is almost no variation, however, after some time has elapsed, the throughput jumps to a much higher level. Also, if TCP is used, then the SS which had a higher throughput at the start continues to have a higher throughput throughout the duration of the simulation. This could be because of the fact that all the other SS would decrease there sending rates because of TCP's congestion policy.

Fig.4 and fig.13 show the case when each SS has a different traffic type. We see that if UDP is used, then rtPS has the highest throughput which is relatively stable. This is followed by nrtps, UGS, ertPS and finally BE. UGS and ertPS are relatively equal. nrtPS, ertPS and BE have the same least starting throughput which increases according to the traffic type. BE however remains the same throughout. This behavior is understandable by looking at the properties of these traffic types. However, if TCP is used, then all the traffic types have the same (very small) starting throughput. This is because of TCP's congestion window policy. Throughput is relatively stable for BE and nrtPS and is the minimum. It is also stable for UGS but there is a jump after an initial time period has elapsed. The ertPS fluctuates and shows an increasing trend. rtPS has the largest and also the greatest amount of fluctuations. This pattern is due to traffic characteristics.

Fig. 7 and fig. 16 show the case where each SS has all the five traffic types. In this case, if UDP is the underlying protocol, then the first SS has a much higher throughput as compared to all the other SS which show a similar traffic pattern. However if TCP is used, then all the SS show the same pattern around the same average throughput.

b) Aggregate Throughput

Comparing fig.2 and fig.11 (only BE traffic over UDP), we see that the aggregate throughput of the scenario is relatively stable if TCP is used and there is a jump in the throughput after some time has elapsed. However if UDP is used then the throughput graph is bumpy with high fluctuations at the start. This is because of the high drop rate inherent in UDP's nature.

If different traffics are used at each SS (fig. 5 and fig. 14), then we see that there are large fluctuations in the throughput at the start if TCP is used and then the throughput becomes stable. However if UDP is used then there is a large jump in the beginning and then the graph has small fluctuations around an average point.

According to fig. 8 and fig. 17, we see that if each SS has each traffic type, then the aggregate throughput takes a large jump in the beginning and then remains constant if UDP is used. However if TCP is used then there is a relatively smooth curve.

c) Packet Stats

From fig.3 and fig. 12, we see that if only BE traffic exists in all the SS, then the number of packets dropped and received is similar whether TCP is used or UDP, and the number of packets received is much higher compared to number sent or dropped. In the BS, the number of packets sent is much higher compared to the number dropped or received. Also, the number of packets dropped at the BS is much higher in the case of UDP and the number received is slightly higher in the case of TCP.

From fig. 6 and fig. 15, we see the stats for scenarios where each SS has a different traffic type using either TCP or UDP. We see that the number of packets dropped at the SS is much higher if TCP is used. This can be further divided into highest loss if BE and nrtPS are used, followed by ertPS and UGS and the least drop for rtPS. The BS pattern is similar no matter which transport protocol is used. The packets received and sent pattern is also similar for the SS no matter which transport protocol is used.

From fig. 9 and fig. 18, we see that if all the traffic types are used at each SS, then the number of packets dropped and sent at the base station is much higher if UDP is used. The number of packets received by the BS is higher if TCP is used. If TCP is used then the number of packets sent and received at the SS is similar for all nodes. However if UDP is used then the number of packets received is much higher at the first SS compared to the other four SS. also at the SS the number of packets received is similar whether TCP is used or UDP , but the number of packets sent is much higher if TCP is used. This is due to the protocol characteristics of UDP and TCP.

Effect of frame size

a) Individual Throughput

Fig. 19 and fig. 22 show this scenario. If UGS over UDP is used, traffics having different sizes show similar behavior, but for a larger size the starting throughput is lower. If TCP is used, a smaller size will cause stability in throughput while a larger size may face a large data burst. Excluding this burst, the throughput is higher for a smaller frame size. This is because a packet loss has a more drastic effect on throughput if the packet size is large.

b) Aggregate Throughput

Fig. 20 and fig. 23 show this scenario. The throughput is stable if UDP is used, however it may see a large jump in throughput initially. The graph is bumpy if TCP is used.

c) Packet Stats

Fig. 21 and fig. 24 show this scenario. The packet stats are similar no matter which transport protocol is used. However the packet loss is greater at the SS if TCP is used and greater at the BS if UDP is used.

Conclusions and Future Direction

In this paper, we did a survey of the existing scheduling techniques and frameworks for the 802.16 networks. We also used the publicly available WiMAX module for NS2 and compared the throughput of the network in different scenarios where the scheduling algorithm employed is weighted round robin scheduling.

There is much research opportunity in this area. Scheduling architectures are required which provide QoS guarantees without being unfair to lower priority traffics. One major issue that has not yet been catered to is the problem that as distance from the BS increases, the bandwidth decreases. Thus scheduling should be such that the SS further away from the BS are not treated unfairly. This problem becomes especially prominent when the nodes are mobile.

References

[1] C. Cicconetti, L. Lenzini, and E. Mingozzi, “Quality of Service Support in IEEE 802.16 Networks”

[2] http://en.wikipedia.org/wiki/WiMAX

[3] S. Ryu, B. Ryu, H. Seo, and M. Shin, “Urgency and Efficiency based Wireless Downlink Packet Scheduling Algorithm in OFDMA System”

[4] W. Park, S.Cho, and S. Bahk, “Scheduler Design for Multiple Traffic Classes in OFDMA Networks”

[5] K. Vinay, N. Sreenivasulul, D. Jayaraml, and D. Das, “Performance Evaluation of End-to-end Delay by Hybrid Scheduling Algorithm for QoS in IEEE 802.16 Network”

[6] J. Sun, Y. Yao, and H. Zhu, “Quality of Service Scheduling for 802.16 Broadband Wireless Access Systems”

[7] W. K. Wong, H. Tang, S. Guo, and V. C. M. Leung, “Scheduling Algorithm in a Point-to-Multipoint Broadband Wireless Access Network”

[8] S. A. Xergias, N. Passas, and L. Merakos, “Flexible Resource Allocation in IEEE 802.16 Wireless Metropolitan Area Networks”

[9] H. S. Alavi, M. Mojdeh, and N. Yazdani, “A Quality of Service Architecture for IEEE 802.16 Standards”

[10] J. Chen, W. Jiao, and H. Wang “A Service Flow Management Strategy for IEEE 802.16 Broadband Wireless Access Systems in TDD Mode”

[11] N. Liu, X. Li, C. Pei, B. Yang, “Delay Character of a Novel Architecture for IEEE 802.16 Systems”

[12] M. Mehrjoo, M. Dianati, X. Shen, K. Naik “Opportunistic Fair Scheduling for the Downlink of IEEE 802.16Wireless Metropolitan Area Networks”

[13] G. Song, Y. Li, “Utility-Based Resource Allocation and Scheduling in OFDM-Based Wireless Broadband Networks”

[14] F. De Pellegrini, D. Miorandi, E. Salvadori and N. Scalabrino. “QoS Support in WiMAX Networks: Issues and Experimental Measurements”

[15] Christian Müller, Anja Klein, Frank Wegner, “Coverage Extension of WiMax Using Multihop in a Low User Density Environment”

[16] D. Tarchi, R. Fantacci, and M. Bardazzi, “Quality of Service Management in IEEE 802.16 Wireless Metropolitan Area Networks”

[17] X. Meng, “An Efficient Scheduling For Diverse QoS Requirements in WiMAX”

[18] http://ndsl.csie.cgu.edu.tw/wimax_ns2.php

[19] Jenhui Chen et al, "The design and implementation of WiMAX module for ns-2 simulator", Proceeding from the 2006 workshop on ns-2: the IP network simulator

[20] http://www.antd.nist.gov/seamlessandsecure/doc.html

We provide a professional essay writing service that thousands of our customers use as an effective way of improving their grades, improving their research and saving them lots of time.