Exp-PIFO：可扩展且高效的可编程数据包调度系统

《Proceedings of the ACM on Networking》：Exp-PIFO: Scalable and Efficient Programmable Packet Scheduling

可编程分组调度器通过自适应指数优先级优化传输顺序，在内存受限环境下实现高效性能，Exp-PIFO策略仅用两个内存单元近似严格PIFO调度，在Intel Tofino交换机验证中表现出低内存占用和优异FCT表现，部分场景性能优于现有近似算法。

　　

摘要

可编程数据包调度器在数据包传输顺序的编排方面提供了极大的灵活性。它们使网络运营商能够利用适应传入流量特征变化的策略来优化关键性能指标，例如流量完成时间（Flow Completion Time, FCT）。然而，在编程这些设备时面临的一个挑战是它们的寄存器、内存和控制流操作能力受到严重限制。以“先进先出”（Push-In First-Out, PIFO）这种流行的调度策略为例，由于该策略依赖于数据包的排序，而在当前硬件上难以实现高速处理。PIFO的固定优先级近似实现方式（如SP-PIFO和AIFO）虽然有硬件支持，但在内存使用量等方面通常仍不具备良好的扩展性。本文介绍了一种新的PIFO近似策略——Exp-PIFO，它基于自适应的指数优先级规则对数据包进行优先级排序，这些规则被称为“指数区间”（exponential bins）。Exp-PIFO仅使用两个内存单元来维护其状态，并通过查找表来避免复杂的控制流程。起初我们担心这种改进会在FCT性能上相对于PIFO及其现有近似方案产生负面影响。然而，实证评估表明Exp-PIFO在某些情况下甚至优于严格的PIFO实现。我们对此现象进行了解释，并通过在Intel Tofino交换机上进行的概念验证实现来证明Exp-PIFO的实际可行性，该实现比SP-PIFO和AIFO的类似方案所需的内存要少得多。

可用格式

您可以通过以下格式查看完整内容：

PDF