The paper "Efficient Fair Queueing using Deficit Round Robin" by George Varghese and M. Shreedhar introduces a new approximation of fair queuing called Deficit Round Robin (DRR). Fair queuing is a technique that ensures each network flow receives a fair share of network resources. Previous schemes for achieving nearly perfect fairness were expensive to implement, with packet processing complexity of \(O(\log(n))\), where \(n\) is the number of active flows. Cheaper approximations often exhibited unfair behavior. The authors propose DRR, which achieves nearly perfect fairness in terms of throughput, requires only \(O(1)\) work to process a packet, and is simple enough to implement in hardware. DRR is applicable to other scheduling problems where servicing cannot be broken into smaller units. The scheme uses source hashing to reduce lookup costs and deficit round-robin to avoid the unfairness of traditional round-robin scheduling by keeping track of past deficits. The paper also discusses the limitations of previous fair queuing schemes, such as Nagle's scheme and McKenney's stochastic fair queuing, and provides a detailed analysis of DRR's performance and complexity. The authors prove that DRR achieves a fairness index of 1 and has a worst-case packet processing work complexity of \(O(1)\). They compare DRR with other fair queuing algorithms and show that DRR outperforms them in terms of fairness and efficiency.The paper "Efficient Fair Queueing using Deficit Round Robin" by George Varghese and M. Shreedhar introduces a new approximation of fair queuing called Deficit Round Robin (DRR). Fair queuing is a technique that ensures each network flow receives a fair share of network resources. Previous schemes for achieving nearly perfect fairness were expensive to implement, with packet processing complexity of \(O(\log(n))\), where \(n\) is the number of active flows. Cheaper approximations often exhibited unfair behavior. The authors propose DRR, which achieves nearly perfect fairness in terms of throughput, requires only \(O(1)\) work to process a packet, and is simple enough to implement in hardware. DRR is applicable to other scheduling problems where servicing cannot be broken into smaller units. The scheme uses source hashing to reduce lookup costs and deficit round-robin to avoid the unfairness of traditional round-robin scheduling by keeping track of past deficits. The paper also discusses the limitations of previous fair queuing schemes, such as Nagle's scheme and McKenney's stochastic fair queuing, and provides a detailed analysis of DRR's performance and complexity. The authors prove that DRR achieves a fairness index of 1 and has a worst-case packet processing work complexity of \(O(1)\). They compare DRR with other fair queuing algorithms and show that DRR outperforms them in terms of fairness and efficiency.