Deficit Round Robin (DRR)

Description

Deficit Round Robin (DRR) is a variation of the Round Robin scheduling algorithm used in packet-switched networks to allocate bandwidth fairly among multiple flows (or sessions). It assigns each flow a quantum (or deficit counter) that determines how many packets it can send in a round. If a flow cannot use its entire quantum in a round, the unused quantum is carried over to the next round, ensuring fair distribution of bandwidth.

C++ Code

#include <iostream>
#include <vector>
using namespace std;

struct Flow {
    int flowId;
    int quantum;
    int packetsLeft;
};

void deficitRoundRobin(vector<Flow>& flows) {
    int n = flows.size();
    int timeSlice = 3;

    while (true) {
        bool allEmpty = true;
        for (int i = 0; i < n; ++i) {
            if (flows[i].packetsLeft > 0) {
                allEmpty = false;
                cout << "Processing packet from flow " << flows[i].flowId << "\n";

                int packetsProcessed = min(timeSlice, flows[i].packetsLeft);
                flows[i].packetsLeft -= packetsProcessed;

                flows[i].quantum -= packetsProcessed;
                if (flows[i].quantum <= 0) {
                    flows[i].quantum += timeSlice;
                }
            }
        }
        if (allEmpty) {
            break;
        }
    }
}

int main() {
    vector<Flow> flows = {
        {1, 5, 10},
        {2, 3, 7},
        {3, 2, 5}
    };

    deficitRoundRobin(flows);

    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Deficit Round Robin	O(n * max(packetsLeft))	O(n)

Where:

• n: Number of flows in the queue.
• packetsLeft: Maximum packets left to process among all flows.

← Back to Homepage