可编程交换机上的近似公平排队阅读笔记

可编程交换机上的近似公平排队

Approximating Fair Queueing on Reconfigurable Switches

意义

公平的带宽分配方案可能非常适合当今的数据中心环境，在这种环境中，具有不同网络需求的多个应用程序经常共存。一些应用程序需要低延迟，而其他应用程序需要持续的吞吐量。数据中心网络还必须应对具有挑战性的流量模式，如大型插入或扇入、微突发和同步流，这些都可以使用公平的排队机制进行有效管理。公平排队机制还可以为共享云基础设施的多个租户提供带宽保证。

今天的拥塞控制主要是通过端到端机制来实现的，而很少有来自网络的支持。虽然这种方法简化了交换机，并允许它们以非常高的速度运行，但它要求终端主机合作以实现公平的网络共享，从而导致效率低下和性能隔离差。如果交换机能够维护每流状态，从网络中提取丰富的遥测数据，并执行可配置的每包处理，则可以实现智能拥塞控制机制，直接利用网络内部的动态网络状态，并提高网络性能。

挑战

虽然像公平排队这样的路由器机制保证了对所有参与者的公平带宽分配，并且在某些方面被证明是最优的，但它们需要复杂的流分类、缓冲区分配和基于每个包的调度。这些因素使得它们在高速交换机中实现的成本很高。

多年来，人们提出了几种实现带宽公平分配的算法，但由于其固有的复杂性，很少在实践中部署。这些算法在每个流的基础上维护状态并执行操作，这使得它们在3-6 Tbps的数据速率下在硬件上实现具有挑战性。

方案

在本文中，我们使用新兴的可编程交换机来发展一种近似线性运行的公平排队（AFQ）。我们利用可配置的每包处理和在交换机内部维护可变状态的能力，在所有遍历流中实现公平的带宽分配。进一步设计了一个新的离队调度程序，称为旋转严格优先级调度程序，它允许我们从多个队列以近似排序的顺序传输数据包。

公平排队路由器执行每个流的管理任务，以保证公平的带宽分配。这些任务包括报文分类，报文属于哪个流，缓冲区分配，该流的报文是加入队列还是丢弃队列，以及报文调度决定下一个传输哪个流的报文。AFQ背后的关键思想是利用可编程交换机中可用的特性来近似公平排队方案的各个组成部分。

我们的设计模拟了前面描述的理想按位轮循（Bit-by-Bit Round Robin）BR算法。与该算法类似，AFQ以轮询方式进行，其中每个流在每轮中传输固定数量的字节。在到达时，每个包被分配一个基于流过去发送的字节数的起始轮数，包计划以递增的轮数进行传输。实现该方案需要AFQ存储交换机上每个活动流的完成轮数，并按顺序调度缓冲数据包。它还必须在交换机上定期存储和更新当前的轮数。

我们用三个关键思想来近似公平排队。

• 在次线性空间中存储近似的流投标数，
• AFQ使用粗粒度轮，只有在所有活动流通过输出端口传输了可配置的字节数后才会增加。
• AFQ利用这些可重构交换机的每个端口上可用的多个FIFO队列，以近似排序的方式调度数据包离开。

开放问题

近似的影响

首先，使用计数最小估计意味着AFQ在发生冲突时可能会高估包的投标数。当活动流的数量增长到超出估计的大小时，冲突的可能性就会增加，导致包的调度时间比预期的要晚。

其次，与BR公平排队算法不同，AFQ允许活动流每轮发送多个字节。由于这个起始轮数比投标数要粗，并且AFQ按照FIFO的顺序缓冲了相同轮数的包，因此，如果交换机较早收到投标数较高的包，则可能会在投标数较低的包之前传输。这种重新排序可能导致轮内的不公平。

每轮字节的权衡

由于AFQ只缓冲下N轮的数据包，因此必须仔细选择每轮传输的字节（BpR），以平衡公平和交换缓冲区的有效使用。如果BpR太大，单个流可能会占用很大一部分缓冲区，从而导致不公平的包延迟和丢弃。如果它太小，AFQ将从单个流突发中丢弃数据包，尽管有足够的空间来缓冲它们。

总结

提出了一种被称为近似公平排队(AFQ)的公平带宽分配机制，该机制适用于新兴的可编程交换机。使用可编程交换机上可用的特性来近似公平排队调度程序的各种机制。具体地说，我们使用可编程交换机状态来近似每个流的状态关于它前向传输的包的数量和时间;我们对每个数据包执行有限的计算，以计算其在输出调度中的位置;我们动态地决定对给定的包使用哪个出口队列;我们设计了一种新的离队方法，称为旋转严格优先级调度程序，以近似排序的顺序传输数据包。在一个真实的硬件测试平台上模拟，表明AFQ精确地逼近了理想的排队行为，比现有的方案显著提高了性能，并且开销是相当小的。