Aliquem: a Novel DRR Implementation to Achieve Better Latency and Fairness at O(1) Complexity

Deficit round-robin is a packet scheduling algorithm devised to provide fair queueing in the presence of variable length packets (see Shreedhar, M. and Varghese, G., IEEE Trans. on Networking, vol.4, p.375-85, 1996). DRR can be implemented at O(1) complexity provided that each flow is allowed to transmit at least one maximum size packet on each round; however, under this constraint, DRR may exhibit high latency and poor fairness. We first generalize previous results known for DRR, related to its latency and fairness. We then introduce a novel DRR implementation technique, called active lists queue method (Aliquem), which allows the above constraint to be relaxed while preserving O(1) complexity, thus achieving better latency and fairness that are comparable to those of more complex algorithms, such as self-clocked fair queueing.