TY - JOUR
T1 - Vertical dimensioning
T2 - A novel DRR implementation for efficient fair queueing
AU - Bakiras, Spiridon
AU - Wang, Feng
AU - Papadias, Dimitris
AU - Hamdi, Mounir
PY - 2008/9/5
Y1 - 2008/9/5
N2 - Fair bandwidth allocation is an important mechanism for traffic management in the Internet. Round robin schedulers, such as Deficit Round Robin (DRR), are well-suited for implementing fair queueing in multi-Gbps routers, as they schedule packets in constant time regardless of the total number of active flows. The main drawback of these schemes, however, lies in the maintenance of per flow queues, which complicates the buffer management module and limits the sharing of the buffer space among the competing flows. In this paper, we introduce a novel packet scheduling mechanism, called Vertical Dimensioning (VD) that modifies the original DRR algorithm to operate without per flow queueing. In particular, VD is based on an array of FIFO buffers, whose size is constant and independent of the total number of active flows. Our results, both analytical and experimental, demonstrate that VD exhibits very good fairness and delay properties that are comparable to the ideal Weighted Fair Queueing (WFQ) scheduler. Furthermore, our scheduling algorithm is shown to outperform significantly existing round robin schedulers when the amount of buffering at the router is small.
AB - Fair bandwidth allocation is an important mechanism for traffic management in the Internet. Round robin schedulers, such as Deficit Round Robin (DRR), are well-suited for implementing fair queueing in multi-Gbps routers, as they schedule packets in constant time regardless of the total number of active flows. The main drawback of these schemes, however, lies in the maintenance of per flow queues, which complicates the buffer management module and limits the sharing of the buffer space among the competing flows. In this paper, we introduce a novel packet scheduling mechanism, called Vertical Dimensioning (VD) that modifies the original DRR algorithm to operate without per flow queueing. In particular, VD is based on an array of FIFO buffers, whose size is constant and independent of the total number of active flows. Our results, both analytical and experimental, demonstrate that VD exhibits very good fairness and delay properties that are comparable to the ideal Weighted Fair Queueing (WFQ) scheduler. Furthermore, our scheduling algorithm is shown to outperform significantly existing round robin schedulers when the amount of buffering at the router is small.
KW - Deficit round robin
KW - Fair queueing
KW - Packet scheduling
UR - http://www.scopus.com/inward/record.url?scp=49649128328&partnerID=8YFLogxK
U2 - 10.1016/j.comcom.2008.06.008
DO - 10.1016/j.comcom.2008.06.008
M3 - Article
AN - SCOPUS:49649128328
SN - 0140-3664
VL - 31
SP - 3476
EP - 3484
JO - Computer Communications
JF - Computer Communications
IS - 14
ER -