1st International Workshop on Advanced Architectures and Algorithms for Internet DElivery and Applications

Research Article

Proportional Nested Deficit Round Robin: Improving the Latency of Packet Scheduler with an O(1) Complexity

  • @INPROCEEDINGS{10.1109/AAA-IDEA.2005.14,
        author={Afshin Shiravi and Yoon Kim and Paul Min},
        title={Proportional Nested Deficit Round Robin: Improving the Latency of Packet Scheduler with an O(1) Complexity},
        proceedings={1st International Workshop on Advanced Architectures and Algorithms for Internet DElivery and Applications},
        publisher={IEEE},
        proceedings_a={AAA-IDEA},
        year={2006},
        month={7},
        keywords={Packet Switch Fair queuing PNDRR Nested-DRR Deficit Round Robin Quantum Size O(1) Complexity},
        doi={10.1109/AAA-IDEA.2005.14}
    }
    
  • Afshin Shiravi
    Yoon Kim
    Paul Min
    Year: 2006
    Proportional Nested Deficit Round Robin: Improving the Latency of Packet Scheduler with an O(1) Complexity
    AAA-IDEA
    IEEE
    DOI: 10.1109/AAA-IDEA.2005.14
Afshin Shiravi1,*, Yoon Kim2,*, Paul Min1,*
  • 1: Dept. of Electrical and Systems Engineering Washington University in St. Louis One Brookings Drive St. Louis, MO 63130
  • 2: Dept. of Eng. and Tech., Computer Eng. Virginia State University 1 Hayden Drive Petersburg, VA 23806
*Contact email: afshin.shiravi@wustl.edu, ykim@vsu.edu, psm@wustl.edu

Abstract

In recent years, many fair Packet scheduling algorithms have been proposed for switches and routers to provide the Quality of Service (QoS) guarantees required by many applications. In addition to the fairness and low end-to-end delay that these algorithms have to have, simplicity and scalability are two significant factors that play an important role. In this paper, we present a new scheduling discipline called Proportional Nested Deficit Round Robin (PNDRR), which has a low latency and reduces burstiness. PNDRR is a class of Nested-DRR in which each DRR round is split into some smaller inner rounds. However, unlike Nested-DRR, flows receive credits proportional to their deficit counters in each inner round. PNDRR takes advantage of the input traffic pattern and decreases the serving size of flows when the input traffic contains many small packets. This helps to interleave packets in many practical scenarios, such as the Internet, where the majority of packets are relatively small. The latency and fairness of PNDRR are studied and compared to other algorithms using simulation. PNDRR has a per-packet computational complexity of O(1).