Host-based scheduling: Achieving near-optimal transport for datacenter networks

Datacenters use limited network resources to host complex and diverse applications, which requires transport schemes to treat diverse applications as a black box and provide low latency for latency-sensitive applications. Many schemes need to beforehand obtain flow information (e.g., flow size, deadline or traffic distribution) or require new hardware design or modification of applications, which leads to difficult use and inefficiency in practice. To solve the dilemma, we present Strict Priority Queuing (SPQ), an information-agnostic and readily deployable flow scheduling scheme, which provides near-optimal flow completion times (FCT) for latency-sensitive applications and effectively harnesses the long-tail behaviors of flows. Unlike the existing in-network priority schemes, SPQ enables host-based, fine-grained flow scheduling, leaving the in-network queuing mechanism simple. SPQ does not make any assumptions about the availability of any flow information and hence, can be applied to any types of datacenter applications. Moreover, SPQ approximates the Least Attained Service (LAS) scheduling discipline and hence is a near-optimal solution. Meanwhile, SPQ utilizes two novel feedback adjustment mechanisms to alleviate the possible negative impact of long flows on short flows. Our simulation results demonstrate that SPQ effectively addresses some major limitations of the in-network priority schemes, resulting in the near-optimal performance in reducing the average and tail latency. For example, the average FCT of short flows for SPQ only has a 0-3.5% gap with respect to the ideal information-aware scheme under a Hybrid workload.