Size-based scheduling for TCP flows: Implementation and performance evaluation

In many theoretical works, the benefits of size-based scheduling disciplines have been proved. The Foreground-Background discipline (or Least Attained Service (LAS)) and the multi-level processor sharing discipline are two examples of scheduling algorithms that provide an improvement of the expected flow completion time for heavily-tailed TCP flows with respect to the widely adopted Processor Sharing (PS) discipline. In this work, we provide an implementation of the 2-level processor sharing queue (2LPS) for a Linux kernel and we measure its performance with TCP flow sizes taken from real-world datasets. 2LPS is the simplest implementation of a size-based scheduling and is parametrised with a threshold a: at each epoch, flows which received less than a service have hard priority on those that have crossed the threshold. We give a numerical procedure to solve the 2LPS queue which allows for the computation of the optimal threshold for arbitrary job size distributions (approximated arbitrary well by generalised hyper-exponential distributions) and compare the results with those obtained by other disciplines (LAS and Shortest Remaining Processing Time (SRPT)). Finally, we measure the performance of its implementation. Our findings show that the benefits of 2LPS, although slightly lower than those predicted by the theoretical model, are still significant and that using just two levels with optimal threshold seems the best trade-off between the complexity and resource demand of the implementation of a size-based scheduler and the improvements in the expected response time.