Approximate and Deployable Shortest Remaining Processing Time Scheduler

The scheduling policy installed on switches of datacenters plays a significant role on congestion control. Shortest-Remaining-Processing-Time (SRPT) achieves the near-optimal average message completion time (MCT) in various scenarios, but is difficult to deploy as viewed by the industry. The reasons are two-fold: 1) many commodity switches only provide FIFO queues, and 2) the information of remaining message size is not available. Recently, the idea of emulating SRPT using only a few FIFO queues and the original message size has been coined as the approximate and deployable SRPT (ADS) design. In this paper, we provide the first theoretical study on the optimal ADS design. Specifically, we first characterize a wide range of feasible ADS scheduling policies via a unified framework, and then derive the steady-state MCT, slowdown, and impoliteness in the M/G/1 setting. Hence we formulate the optimal ADS design as a non-linear combinatorial optimization problem, which aims to minimize the average MCT given the available FIFO queues. We also take into account the proportional fairness and temporal fairness constraints based on the maximal slowdown and impoliteness, respectively. The optimal ADS design problem is NP-hard in general, and does not exhibit monotonicity or sub-modularity. We leverage its decomposable structure and devise an efficient algorithm to solve the optimal ADS policy. We carry out extensive flow-level simulations and packet-level experiments to evaluate the proposed optimal ADS design. Results show that the optimal ADS policy installed on eight FIFO queues is capable of emulating the true SRPT.