Title :
Fair, efficient and low-latency packet scheduling using nested deficit round robin
Author :
Kanhere, Salil S. ; Sethu, Harish
Author_Institution :
Dept. of ECE, Drexel Univ., Philadelphia, PA, USA
Abstract :
In the emerging high-speed integrated-services packet-switched networks, packet scheduling algorithms in switches and routers play a critical role in providing the quality of-service (QoS) guarantees required by many applications. We present a new scheduling discipline called nested deficit round robin (Nested-DRR), which is fair, efficient and in addition has a low latency bound. Nested-DRR splits each DRR round into one or more smaller rounds, within each of which we run a modified version of the DRR scheduling discipline. In this paper, we analytically prove that Nested-DRR results in a significant improvement in the latency bound in comparison to DRR, and in addition preserves the good properties of DRR such as the per-packet work complexity of O(1). Nested DRR also has the same relative fairness bound as DRR
Keywords :
delays; packet switching; quality of service; telecommunication network routing; DRR scheduling discipline; Nested-DRR results; QoS; efficient packet scheduling; fair packet scheduling; frame-based DRR scheduler; high-speed networks; integrated-services packet-switched networks; latency bound; low-latency packet scheduling; nested deficit round robin; packet scheduling algorithms; quality of-service; routers; switches; Computer aided instruction; Delay; Electronic mail; Packet switching; Quality of service; Round robin; Scheduling algorithm; Sorting; Switches; Video on demand;
Conference_Titel :
High Performance Switching and Routing, 2001 IEEE Workshop on
Conference_Location :
Dallas, TX
Print_ISBN :
0-7803-6711-1
DOI :
10.1109/HPSR.2001.923594