[网络领域顶会追踪系列#4][NSDI'22] GearBox: 一个近似加权公平队列的分层数据包调度器

本系列为个人论文阅读笔记，大多数应该是对顶会摘要的个人菜鸟翻译，旨在让感兴趣的朋友能快速浏览、获取信息。如有错误或心得，欢迎在评论区交流指正！

Gearbox: A Hierarchical Packet Scheduler for Approximate Weighted Fair Queuing

背景

带宽分配和性能隔离对实现网络虚拟化和保证数据中心服务质量很重要，WFQ（Weighed Fair Queuing，加权公平队列）可以实现带宽分配和性能隔离

挑战

然而，在大规模高速网络系统中实现WFQ很困难，因为调度很复杂且需要的队列数很多。

工作

提出了GearBox，一个针对下一代可编程交换机和智能网卡的调度器原语，实际上是一个近似的WFQ。GearBox由一系列逻辑分层的队列等级组成，可以使用相对少的FIFO队列，适应很大范围的包完成时间。GearBox的入队和出队操作有着O(1)的时间复杂度，使其能够适用于高速线速。GearBox通过允许与严格WFQ轻微不同的包离开时间，提供了简单性和高性能。展示了GearBox的正态离开时间的偏移性是受限制的，并且在带宽分配和流完成时间上只有轻微的影响。

实验

做了NS2仿真和FPGA仿真。NS2结果表明很接近标准WFQ，能实现加权最大-最小公平带宽分配和流量隔离。提供了与理想WFQ相近的FCT性能。在FPGA上的实验表明能够实现线速，消耗了少于1%的逻辑资源和4%的内存。

原文摘要

Bandwidth allocation and performance isolation are crucial to achieving network virtualization and guaranteeing service quality in data centers as well as other network systems. Weighted Fair Queuing (WFQ) can achieve customized bandwidth allocation and flow isolation; however, its implementation in large-scale high-speed network systems is very challenging due to the high complexity of the scheduling and the large number of queues required.

This paper proposes Gearbox, a scheduler primitive for next-generation programmable switches and smart NICs that practically approximates WFQ. Gearbox consists of a logical hierarchy of queuing levels, which accommodate a wide range of packet departure times using a relatively small number of FIFOs. Gearbox's enqueue and dequeue operations have O(1) time complexity, which makes it suitable to cope with high-speed line rates. Gearbox provides its simplicity and performance advantages by allowing slight discrepancies in packet departure time from strict WFQ. We show that Gearbox's normalized departure time discrepancy is bounded and has a negligible impact on bandwidth allocation and flow completion time (FCT).

We implement Gearbox in NS2 and in VHDL, targeted to a Xilinx Alveo U250 card with an XCVU13P FPGA. The NS2 evaluation results show that Gearbox closely approximates WFQ and achieves weighted max-min fairness in bandwidth allocation as well as flow isolation. Gearbox provides FCT performance comparable to ideal WFQ. The Gearbox FPGA prototype runs at 350MHz and achieves full line rate for 100GbE with packets larger than 123 bytes. Gearbox consumes less than 1% of the FPGA's logic resources and less than 4% of its internal block memory.