Weighted Fair Queuing (WFQ)

Description

Weighted Fair Queuing (WFQ) is a scheduling algorithm used in packet-switched networks to achieve fair bandwidth allocation among different flows (or sessions). Each flow is assigned a weight, and packets are scheduled in a round-robin manner based on their weights. WFQ ensures fairness by prioritizing flows with smaller weights over those with larger weights.

C++ Code

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

struct Packet {
    int flowId;
    int weight;
    int remaining;
};

void weightedFairQueuing(vector<Packet>& packets) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int n = packets.size();
    vector<int> processed(n, 0);

    for (int i = 0; i < n; ++i) {
        pq.push({0, i});
    }

    int currentTime = 0;
    while (!pq.empty()) {
        pair<int, int> current = pq.top();
        pq.pop();

        int index = current.second;
        int currentWeight = packets[index].weight;
        int currentFlowId = packets[index].flowId;

        if (packets[index].remaining > 0) {
            cout << "Processing packet from flow " << currentFlowId << " at time " << currentTime << "\n";
            packets[index].remaining--;

            pq.push({currentTime + currentWeight, index});
        }
        currentTime++;
    }
}

int main() {
    vector<Packet> packets = {
        {1, 3, 5},
        {2, 2, 3},
        {3, 1, 7}
    };

    weightedFairQueuing(packets);

    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Weighted Fair Queuing	O(n * log n)	O(n)

Where:

• n: Number of packets (flows) in the queue.

← Back to Homepage