Tandem Queue Weighted Fair Smooth Scheduling

Network devices supporting 100G links are in demand to meet the communication requirements of computing nodes in datacenters and warehouse computers. In this paper, we propose TQ and TQ-Smooth, two lightweight, fair schedulers that accommodate an arbitrarily large number of requestors and are suitable for ultrahigh-speed links. We show that our first algorithm, TQ, as well its predecessor, DRR, may result in bursty service even in the common case where flow weights are approximately equal, and we identify applications where this can damage performance. Our second algorithm, TQ-Smooth, improves short-term fairness to deliver very smooth service when flow weights are approximately equal, while allocating bandwidth in a weighted fair manner. In many practical situations, a scheduler is asked to allocate resources in fixed-size chunks (e.g. buffer units), whose size may exceed that of (small) network packets. In such cases, byte-level fairness will typically be compromised when small-packet flows compete with large-packet ones. We describe a novel scheme that dynamically adjusts the service rates of request/grant buffer reservation to achieve byte-level fairness based on received packet sizes.