A Weighted Fair Queuing with Optimal Rate and Delay Allocation

The characteristic latency of each flow in the Weighted Fair Queuing (WFQ) scheduler may be over or under its delay budget allocated to the scheduler. The scheduler raises the scheduling rate to make the flow's practical latency be equal to the budget if over-budget, but otherwise it does not do anything even though there exists the excess delay resource of the difference between the budget and the characteristic latency, and, in a consequence, the resource will be wasted. In a word, legacy WFQ is non-optimal in the context of rate and delay allocation. In order to overcome this problem, this paper proposes a WFQ with optimal rate and delay allocation, called General-time Fair Queuing (GFQ) I. INTRODUCTION Fair queuing algorithm has been extensively studied in the last decade due to its importance in the provision of Quality- of-Service (QoS) guarantees in packet networks. Numerous sorted-priority fair queuing algorithms (2-8) have been devel- oped to emulate the ideal algorithm called General Processor Sharing (GPS) (1). They can be categorized into two design approaches in the terms of the reference time used in cal- culating the timestamp of each packet: the Start-Time (ST) one using the transmission starting time of the packet in the corresponding GPS server and the Finish-Time (FT) one using its transmission finishing time. The FT approach, applied to Weighted Fair Queuing (WFQ) (2), satisfies the requirement of isolating flows and providing differentiated QoS guarantees so that was considered as a typi- cal scheduling scheme for the RSVP-capable router introduced in the IntServ model (9) of Internet Engineering Task Force, where RSVP stands for reservation protocol. It was known that WFQ, however, has the inherent drawback of poor bandwidth utilization, particularly under the traffic requiring low rate but tight delay bound such as internet phone (3). There have been several works to overcome the drawback. A WFQ with policer, called Decoupled Fair Queuing (4), was proposed for the support of voice traffic, in which scheduling rates for voice flows are judiciously over-allocated and instead the policer enforces an over-provisioned voice flow actually to receive only the desired bandwidth. Optimal Network Service Curves (5) and Credit-based Processor Sharing (6) introduced a variable scheduling rate scheme instead of the policer dropping some packets, in which each flow temporarily requiring higher scheduling rate than reserved one borrows its deficient rate from other flows with surplus bandwidth. The terms rate and bandwidth are used synonymously in this paper. This scheme, however, may do not work well in the case that there are only few flows with surplus bandwidth to lend. It has been understood that the poor utilization in WFQ is due to its coupled rate and delay allocation (3-6). We consider that it is due to rather the resource waste being occurred when the characteristic latency of a flow is under its delay budget and then proposes an algorithm, called General-time Fair Queuing (GFQ), to prevent the waste in which a general-time instead of the finish-time applied to WFQ is used.