Skip to content

Deficit Round Robin (DRR)

Jump to bottom
Yash Agarwal edited this page Oct 8, 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 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 and every queue is initialized with the same quantum of size.
  2. Weighted DRR: each queue can be initialized with 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)
Clone this wiki locally