Search

Recent high-speed devices (network interfaces, external storage, computational accelerators) provide multiple access channels to allow concurrent I/O from mutually distrusting applications or virtual machines, enabling them to serve millions of ops/s. Unfortunately, it is difficult for the operating system to fairly partition bandwidth among resource principals (VMs, flows, etc.) without introducing synchronization overhead that would largely negate the benefits of multi-channel parallelism. Existing resource scheduling algorithms, which generally assume underlying serial operation, are also unsuitable to devices with a high degree of internal parallelism. To address these challenges, we present the first known fair, work- conserving scheduler for multi-channel I/O devices. Specifically, we (1) reformulate the classical notion of virtual time to accommodate parallel channels, and (2) describe a scalable implementation that bounds potential unfairness while minimizing synchronization overhead. Our implementation of multi-queue fair queueing (MQFQ) in the Linux 4.15 kernel demonstrates that it is possible to achieve both fairness and very high throughput. Evaluation with an NVMe over RDMA fabric (NVMf) device demonstrates MQFQ offers up to 20× more throughput and superior fairness compared to an existing Linux fairness algorithm (BFQ) -- a rate of up to 3.1 Million IOP/s on a single machine. Compared to running without a fairness algorithm, MQFQ reduces the slowdown caused by an antagonist from 3.78X to 1.33X for the FlashX workload and from 6.57X to 1.03X for the Aerospike workload.

Middleboxes are ubiquitous in today's networks and perform a variety of important functions, including IDS, VPN, firewalling, and WAN optimization. These functions differ vastly in their requirements for hardware resources (e.g., CPU cycles and memory bandwidth). Thus, depending on the functions they go through, different flows can consume different amounts of a middlebox's resources. While there is much literature on weighted fair sharing of link bandwidth to isolate flows, it is unclear how to schedule multiple resources in a middlebox to achieve similar guarantees. In this paper, we analyze several natural packet scheduling algorithms for multiple resources and show that they have undesirable properties. We propose a new algorithm, Dominant Resource Fair Queuing (DRFQ), that retains the attractive properties that fair sharing provides for one resource. In doing so, we generalize the concept of virtual time in classical fair queuing to multi-resource settings. The resulting algorithm is also applicable in other contexts where several resources need to be multiplexed in the time domain., QC 20121120