Des Autom Embedded Syst

Tandem queue weighted fair smooth scheduling

View publication


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 light-weight, fair schedulers that accommodate an arbitrarily large number of requestors and are suitable for ultra high-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 find that this can damage the performance of buffer-credit allocation schemes. 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 and evaluate a scheme that dynamically adjusts the service rates of request/grant buffer reservation to achieve byte-level fairness based on received packet sizes.