Skip to content

Deficit Round Robin (DRR)

Jump to bottom
Yash Agarwal edited this page Nov 2, 2019 · 3 revisions

Introduction

Deficit Round-robin (DRR) Packet Scheduler schedules N queues in an orderly fashion. Each queue is provided with a byte credit, where byte credit is the maximum number of bytes that can be dequeued from a queue at a time. If the size of the packet present at the head of the queue is greater than the byte credit than the scheduler linearly probes for the next queue and at the same time increments the byte credit of the current queue with the size of a quantum. When a queue is identified, having byte credits greater than the head packet size. The Scheduler keeps dequeuing the packets and decrementing the byte credits by the size of the packet dequeued until the size of the head packet becomes greater than the byte credits. In this manner, DRR provides near-perfect throughput fairness with O(1) packet processing. DRR can be classified into two major categories :

  1. Unweighted DRR: each queue is initialized with the same quantum of size.
  2. Weighted DRR: each queue can be initialized with a different quantum of size.

Keywords

  1. Byte Credits: The maximum number of bytes that a flow(queue) is allowed to transfer when it is its turn (Or) The maximum number of bytes that can be dequeued from a queue when it is its turn.
  2. Deficit Counter: It is the same as Byte Credits and can be used interchangeably.
  3. Backlogged: A queue is said to be backlogged if it still has a packet to send and don't have sufficient Byte Credits.
  4. Quantum: The amount by which Byte Credits are initialized initially or incremented in the case of backlogged.

Operation of DRR Scheduler

  • The packets from flows(queues) are transmitted in a round-robin manner.
  • The quantum is added to the byte credits of a queue before dequeuing packets from it.
byte credits(f) = byte credits(f) + quantum
  • A packet from the queue is transmitted only if:
byte credits >= length of the head packet
  • If a packet is transmitted, the byte credits of that queue is updated as follows:
deficit counter(f) = deficit counter(f) - (#bytes in the packet)
  • If a queue was not able to send a packet in the previous round because its packet size was too large, the remainder from the previous quantum is added to the quantum for the next round.
  • Thus, deficits are kept track of. The queues that were shortchanged in a round are compensated in the next round. Hence, called Deficit Round Robin Scheduling.
Clone this wiki locally