Fair scheduling with tunable latency: a round robin approach

Abstract

Much of the previous research in packet scheduling for high speed routers is focused around the weighted fair queuing (WFQ) paradigm. In WFQ schemes, the transmission schedule is determined by sorting the tags of the packets contending for the link. This requires processing at line speeds for tag computation and tag sorting. We propose an alternative and lower complexity approach to packet scheduling, based on modifications of the classical round robin scheduler. Contrary to conventional belief, we show that appropriate modifications of the weighted round robin (WRR) service discipline can, in fact, provide tight fairness properties and efficient delay guarantees to multiple sessions. Two such modifications are described: (i) list-based round robin, in which the server visits different sessions according to a precomputed list which is designed to obtain the desirable scheduling properties and, (ii) multiclass round robin, a version of hierarchical round robin with controls designed for good scheduling properties. The schemes considered are compared with well known WFQ schemes and with the deficit round robin (a credit-based weighted round robin), on the basis of desirable properties such as bandwidth guarantees, fairness in excess bandwidth sharing, worst-case fairness and efficiency of latency (delay guarantee) tuning.