An adaptive scheduling scheme for fair bandwidth allocation

Wei Liu, Wenqing Cheng, Jianhua He, Chunhui Le, Zongkai YangProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 2005 · DOI

Abstract

Class-based service differentiation is provided in DiffServ networks. However, this differentiation will be disordered under dynamic traffic loads due to the fixed weighted scheduling. An adaptive weighted scheduling scheme is proposed in this paper to achieve fair bandwidth allocation among different service classes. In this scheme, the number of active flows and the subscribed bandwidth are estimated based on the measurement of local queue metrics, then the scheduling weights of each service class are adjusted for the per-flow fairness of excess bandwidth allocation. This adaptive scheme can be combined with any weighted scheduling algorithm. Simulation results show that, comparing with fixed weighted scheduling, it effectively improve the fairness of excess bandwidth allocation.

Introduction: The Challenge of Excess Bandwidth

In modern networking, the Differentiated Services (DiffServ) architecture provides varying levels of Quality of Service (QoS). For instance, "Expedited Forwarding" (EF) is prioritized for real-time traffic, while "Assured Forwarding" (AF) and "Best Effort" (BE) handle standard data.

A significant challenge arises with excess bandwidth—the surplus capacity available when the network is not fully congested. Ideally, this surplus should be shared equitably among active flows. However, most routers employ fixed weights for scheduling. If the number of users in a specific category, such as "Best Effort," spikes unexpectedly, they may monopolize the excess bandwidth. This leaves "Assured Forwarding" users with less than their fair share, undermining the core promise of service differentiation. Existing solutions often involve complex per-flow tracking that is difficult to scale for high-speed core routers.

Proposed Adaptive Scheduling Scheme

The authors propose a measurement-based, adaptive approach that can be integrated into any standard weighted scheduling algorithm, such as Weighted Round Robin (WRR) or Weighted Fair Queueing (WFQ).

Architecture of the adaptive weighted scheduling scheme showing service classes and RIO/RED queues.

The core of this method involves two key estimations performed locally at the router:

  1. Estimating Active Flows ($N_i$): Instead of resource-intensive per-flow tracking, the scheme uses a mathematical formula derived from average queue length, packet drop probability, and round-trip time.
  2. Estimating Subscribed Bandwidth ($S_i$): The router estimates "in-profile" (subscribed) versus "out-of-profile" traffic by comparing the average size of the "IN" packet queue to the total queue.

Every 5 to 10 seconds (the "adaptation period"), the router recalculates ideal weights and updates the scheduler. This allows the network to react to bursty traffic without maintaining a massive database of connections.

Experimental Evaluation

The scheme was evaluated using ns-2 (Network Simulator 2). The simulation topology featured a DiffServ domain with two edge routers and one core router, connected by a 50Mbps bottleneck link. TCP connections were simulated between source and destination nodes under varying "subscription ratios" (30% to 90% of total capacity) and dynamic traffic loads.

Key Results and Insights

The primary insight of this research is that per-flow fairness can be achieved across a network using only local metrics (queue lengths and drop rates) already available in buffer management systems like RIO/RED.

Fairness index over time for different subscription ratios, showing convergence to 1.0.
  • Fairness Index: Using a "Fairness Index" where 1.0 represents perfect equity, the proposed Adaptive WRR (AWRR) consistently maintained values between 0.9 and 1.0. In contrast, standard fixed WRR dropped as low as 0.6 under shifting traffic loads.
  • Rapid Adaptation: When the number of Best Effort flows jumped from 15 to 35, the AWRR scheme recalibrated bandwidth allocation within approximately 20-30 seconds to restore fairness.
  • Scalability: By avoiding per-flow state tracking, the method remains highly scalable for high-speed core routers where memory and processing cycles are limited.

Limitations and Future Work

While effective, the current model is primarily TCP-centric, relying on the relationship between drop rates and throughput characteristic of TCP traffic. Future work could extend this to more diverse traffic types, including UDP. Additionally, the estimation accuracy is sensitive to buffer size; buffers should ideally be an integer multiple of the bandwidth-delay product. Finally, there is an inherent trade-off in the adaptation period: shorter periods increase CPU load, while longer periods may react slowly to very brief traffic bursts.

Summary updated

Abstract

Class-based service differentiation is provided in DiffServ networks. However, this differentiation will be disordered under dynamic traffic loads due to the fixed weighted scheduling. An adaptive weighted scheduling scheme is proposed in this paper to achieve fair bandwidth allocation among different service classes. In this scheme, the number of active flows and the subscribed bandwidth are estimated based on the measurement of local queue metrics, then the scheduling weights of each service class are adjusted for the per-flow fairness of excess bandwidth allocation. This adaptive scheme can be combined with any weighted scheduling algorithm. Simulation results show that, comparing with fixed weighted scheduling, it effectively improve the fairness of excess bandwidth allocation.
BibTeX
@inproceedings{liu2005adaptive,
  author = {Wei Liu and Wenqing Cheng and Jianhua He and Chunhui Le and Zongkai Yang},
  title = {{An adaptive scheduling scheme for fair bandwidth allocation}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {2005},
  doi = {10.1117/12.574964},
}
Figure