WF2Q-M: Worst-case fair weighted fair queueing with maximum rate control

While existing weighted fair scheduling schemes guarantee minimum bandwidths/resources for the classes/processes of a shared channel, the maximum rate control, which is critical to service providers, carriers, and network managers for resource management and business strategies in many applications, is generally enforced by employing traffic policing mechanisms. These approaches use either a concatenation of the rate controller and scheduler, or a policer in front of the scheduler. The concatenation method uses two sets of queues and a management apparatus that incurs overhead. The latter method may allow bursty traffic to pass through the controller, which violates the maximum rate constraint, or results in packet loss. In this paper, we present a new weighted fair scheduling scheme, WF2Q-M, which can simultaneously support maximum rate control and minimum service rate guarantees. WF2Q-M uses the virtual clock adjustment method to enforce maximum rate control and distribute the excess bandwidths of saturated sessions to other sessions without recalculating the virtual starting and finishing times of sessions. In terms of performance, we prove that WF2Q-M is theoretically bounded by a corresponding fluid reference model. A procedural scheduling implementation of WF2Q-M is proposed, and a proof of correctness is given. Finally, we present the results of extensive experiments to show that the performance of WF2Q-M is just as claimed.