Emulated Weighted Fair Queueing Algorithm for High-Speed Packet-Switched Networks

Nam-Seok KO  Hong-Shik PARK  

IEICE TRANSACTIONS on Communications   Vol.E84-B    No.10    pp.2863-2870
Publication Date: 2001/10/01
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Internet
fair queueing,  scheduling,  WFQ,  fairness,  QoS,  

Full Text: PDF(395KB)>>
Buy this Article

WFQ (Weighted Fair Queueing) is an ideal scheduling algorithm in terms of delay and fairness. However, timestamp computation complexity makes the implementation difficult. In this paper we propose an efficient and simple fair queueing algorithm, called Emulated Weighted Fair Queueing (EWFQ), which has O(1) complexity for the virtual time computation while it almost perfectly emulates the delay and fairness properties of WFQ. The key idea of EWFQ is that it calibrates the system virtual time only at the end of each packet transmission, while it calculates the system virtual time for a newly arrived packet by employing a linear approximation. By doing so, EWFQ has a rate-proportional property. EWFQ can be implemented in a router for supporting the differential and integrated services.