Programmable packet scheduling with a single queue
Programmable packet scheduling with a single queue
复制标题
DOI：
10.1145/3452296.3472887
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Zhuolong Yu;Chuheng Hu;Jingfeng Wu;Xiao Sun;V. Braverman;Mosharaf Chowdhury;Zhenhua Liu;Xin Jin
中科院分区：
文献类型：
--
作者：
Zhuolong Yu;Chuheng Hu;Jingfeng Wu;Xiao Sun;V. Braverman;Mosharaf Chowdhury;Zhenhua Liu;Xin Jin
可编程数据包调度使调度算法能够被编程到数据平面中，而无需更改硬件。现有的提案要么没有交换机 ASIC 的硬件实现，要么需要多个严格优先级队列。我们提出了准入先出（AIFO）队列，这是一种仅使用单个先进先出队列的可编程数据包调度的新解决方案。 AIFO 是由两个最新趋势的融合推动的：交换机中的浅缓冲区和终端主机中的快速收敛拥塞控制，这共同导致了一个简单的观察：现代数据中心网络中流完成时间（FCT）的决定性因素通常是数据包入队或丢弃的决定因素，而不是它们离开交换机的顺序。 AIFO 的核心思想是维护一个滑动窗口来跟踪最近数据包的排名，并计算到达数据包在窗口中的相对排名以进行准入控制。从理论上讲，我们证明 AIFO 为推入先出 (PIFO) 提供了有限的性能。根据经验，我们完全实现了 AIFO 并通过一系列实际工作负载评估 AIFO，证明 AIFO 非常接近 PIFO。重要的是，与 PIFO 不同，AIFO 可以在现有硬件上以线速运行，并使用最少的交换机资源——少至单个队列。
Programmable packet scheduling enables scheduling algorithms to be programmed into the data plane without changing the hardware. Existing proposals either have no hardware implementations for switch ASICs or require multiple strict-priority queues. We present Admission-In First-Out (AIFO) queues, a new solution for programmable packet scheduling that uses only a \emph{single} first-in first-out queue. AIFO is motivated by the confluence of two recent trends: \emph{shallow} buffers in switches and \emph{fast-converging} congestion control in end hosts, that together leads to a simple observation: the decisive factor in a flow's completion time (FCT) in modern datacenter networks is often \emph{which} packets are enqueued or dropped, not the \emph{ordering} they leave the switch. The core idea of AIFO is to maintain a sliding window to track the ranks of recent packets and compute the relative rank of an arriving packet in the window for admission control. Theoretically, we prove that AIFO provides bounded performance to Push-In First-Out (PIFO). Empirically, we fully implement AIFO and evaluate AIFO with a range of real workloads, demonstrating AIFO closely approximates PIFO. Importantly, unlike PIFO, AIFO can run at line rate on existing hardware and use minimal switch resources---as few as a single queue.