Frame-Based Worst-Case Weighted Fair Queueing with Jitter Control

Yeali S. SUN  Yung-Cheng TU  Wei-Kuan SHIH  

IEICE TRANSACTIONS on Communications   Vol.E84-B   No.8   pp.2266-2278
Publication Date: 2001/08/01
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Internet
jitter control,  weighted fair queueing,  quality of service (QoS),  frame-based,  

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

In the past, a number of scheduling algorithms that approximate GPS, such as WFQ, have been proposed and have received much attention. This class of algorithms provides per-flow QoS guarantees in terms of the bounded delay and minimum bandwidth guarantee. However, with O(log N) computational cost for each new arrival scheduling, where N is the number of backlogged flows, these algorithms are expensive to implement (e.g., in terms of scalability). Moreover, none of them addresses the issues of delay distribution and jitter. In this paper, we propose a new traffic scheduling discipline called Jitter Control Frame-based Queueing (JCFQ) that provides an upper bound for delay jitter in the case of rate-controlled connections, such as packet video streams and IP telephony, while guaranteeing bounded delay and worst-case fair weighted fairness, such as in the WF2Q algorithm, but with O(1) complexity in selecting the next packet to serve, assuming that the number of flows is fixed. Three different algorithms for slot or service order assignment between flows are proposed: Earliest Jitter Deadline First (EJDF), Rate Monotonic (RM) and Maximum Jitter First (MJF). In these algorithms, delay jitter is formulated into the virtual finish time calculation. We compare the fairness, delay and jitter performance of the JCFQ with that of the MJF algorithm with WF2Q via simulation. The results show that with proper choice of the slot size, JCFQ can achieve better flow isolation in delay distribution than can WF2Q.