Chakchai So-In, Raj Jain and Abdel-Karim Al Tamimi, "Deficit Round Robin with Fragmentation Scheduling to Achieve Generalized Weighted Fairness for Resource Allocation in IEEE 802.16e Mobile WiMAX Networks," Accepted for publication in Future Internet, 2010.


Deficit Round Robin (DRR) is a fair packet-based scheduling discipline commonly used in wired networks where link capacities do not change with time. However, in wireless networks, especially wireless broadband networks, i.e., IEEE 802.16e Mobile WiMAX, there are two main considerations violate the packet-based service concept for DRR. First, the resources are allocated per Mobile WiMAX frame. To achieve full frame utilization, Mobile WiMAX allows packets to be fragmented. Second, due to a high variation in wireless channel conditions, the link/channel capacity can change over time and location. Therefore, we introduce a Deficit Round Robin with Fragmentation (DRRF) to allocate resources per Mobile WiMAX frame in a fair manner by allowing for varying link capacity and for transmitting fragmented packets. Similar to DRR and Generalized Processor Sharing (GPS), DRRF achieves perfect fairness. DRRF results in a higher throughput than DRR (80% improvement) while causing less overhead than GPS (8 times less than GPS). In addition, in Mobile WiMAX, the quality of service (QoS) offered by service providers is associated with the price paid. This is similar to a cellular phone system; the users may be required to pay air-time charges. Hence, we have also formalized a Generalized Weighted Fairness (GWF) criterion which equalizes a weighted sum of service time units or slots, called temporal fairness, and transmitted bytes, called throughput fairness, for customers who are located in a poor channel condition or at a further distance versus for those who are near the base stations, or have a good channel condition. We use DRRF to demonstrate the application of GWF. These fairness criteria are used to satisfy basic requirements for resource allocation, especially for non real-time traffic. Therefore, we also extend DRRF to support other QoS requirements, such as minimum reserved traffic rate, maximum sustained traffic rate, and traffic priority. For real-time traffic, i.e., video traffic, we compare the performance of DRRF with deadline enforcement to that of Earliest Deadline First (EDF). The results show that DRRF outperforms EDF (higher achievable throughput under the promised delay latency) and maintains fairness under an overload scenario.

Complete paper in Adobe Acrobat format.

Back to the List of Papers
Back to Raj Jain's home page