TR-IIS-02-003    PDF format

On Maximum Rate Control of Worst-case Weighted Fair Queueing

Jeng Farn Lee, Yeali Sun, Meng-Chang Chen


While exisiting weighted fair scheduling schemes guarantee minimum bandwidths for classes/sessions in a shared channel, maximum rate control, which is critical  to service providers and carriers for resource management and business strategies, was generally enforced by employing policing mechanisms. The previous approaches  use either a concatenation of rate controller and scheduler, or a policer in front of scheduler. The concatenation method uses two sets of queues and management  aparartus, and thus incurs overhead. The other method allows bursty traffic to pass through that can violate maximum rate constraint or cause a high packet loss rate.  In this paper, we present a new weighted fair scheduling scheme,  WF2Q-M, to  simultaneously support maximum rate control and minimum service rate guarantee. WF2Q-M proposes the virtual clock adjustment method to enforce maximum rate control by distributing the excess bandwidths of maximum rate constrained sessions to other sessions without recalculating the virtual starting and finishing times of regular sessionss. In terms of performance metrics, we prove that WF2Q-M is  theoretically bounded by a fluid reference model.  A procedural scheduling implementation of WF2Q-M is proposed and  proof of correctness is given. Finally, we conduct extensive experiments to show the performance of WF2Q-M is just as we claimed.

Link Sharing, Rate Control, Scheduling, PGPS