当前位置：首页 > NSDI > 正文

【NSDI 2022】BFC：背压流量控制/Backpressure Flow Control

NSDI
2022-10-18
3052
更新：2023-01-04 21:42:23

## **摘要**

数据中心网络的有效拥塞控制变得越来越具有挑战性，因为对时延敏感的流量越来越多，链路越来越宽，流量也越来越频繁。广泛部署的算法，如DCTCP和DCQCN，在许多可能的场景中仍然远远不是最优的，尤其是在尾部时延方面。许多运营商通过以较低的平均利用率运行网络来进行补偿，这大大增加了成本。

在本文中，我们认为我们已经达到了端到端拥塞控制的实际极限。相反，我们提出、实现并评估了一种新的拥塞控制体系结构，称为背压流量控制(BFC)。BFC提供逐跳逐流的流量控制，但具有有界状态、恒定时间切换操作，并谨慎使用缓冲区和队列。我们通过在最先进的基于P4的可编程硬件交换机Tofino2上实现BFC来证明它的可行性。在仿真中，我们表明，即使在高网络负载和交叉incast流量等挑战性条件下，BFC也能实现接近最优的吞吐量和尾部时延行为。与部署的端到端方案相比，对于短流，BFC实现了2.3-60倍的尾部时延，对于长流，BFC实现了1.6-5倍的平均完成时间。

## **1 导言**

单租户和多租户数据中心已成为计算机行业最大、增长最快的细分市场之一。数据中心正日益主导着所有类型的高端计算市场，包括企业服务、并行计算、大规模数据分析、容错中间件和全球分布式应用。这些工作负载给数据中心网络带来了巨大的压力，使其能够以更低的成本以更低的尾部时延提供更快的吞吐量，即使对于高度突发的流量也是如此。

尽管细节各不相同，但如今几乎所有数据中心网络都结合使用端点/endpoint拥塞控制、交换机处的FIFO队列，以及拥塞信号(如时延或显式交换机状态)的端到端反馈到端点控制环路。然而，随着链路速度继续增加，控制回路的设计变得更加困难。首先，一次往返时间可以容纳更多的流量，这使得更难有效地使用反馈。第二，流量变得越来越频繁，因此网络负载不是一个稳定的属性，除非在很短的时间范围内。第三，交换机缓冲容量跟不上链路速度的增长(图1)，这使得处理流量突发变得更加困难。大多数网络运营商以非常低的平均负载运行网络，以远低于网络容量的速度限制长流量，甚至会看到显著的拥塞损失。

相反，我们提出了一种不同的方法。在我们看来，数据中心网络面临的关键挑战是如何在拥挤的网络交换机上高效地分配缓冲空间。如果控制操作是逐流和逐跳进行的，而不是端到端的，那么这将变得更容易、更简单。尽管具有优势，但逐跳逐流流量控制似乎需要每个交换机的逐流状态，即使对于静态流(quiescent flows)，这在数据中心规模上是不实际的。

我们的主要贡献是，在现代可编程交换机上，仅使用简单的恒定时间切换操作，就可以用有限的交换机状态和适度数量的交换机队列来近似实现逐跳逐流流量控制。我们不需要所有流，只需要活跃流的状态和其特定队列，即带有排队数据包的流。我们发现，在交换机级公平排队或最短流调度的情况下，对于典型的数据中心工作负载，活跃流的数量是适度的，即使在分布的尾部也是如此。折衷(需要考虑的tradeoff)是，当活跃流的数量超过队列的数量时，性能可能会降低。在实践中，我们提倡将逐跳流量控制与端到端拥塞控制相结合，以避免病态行为。然而，为了更好地说明我们的方法的优点和局限性，我们的描述和实验侧重于比较纯逐跳控制和纯端到端控制。

我们已经在Tofino2上实现了我们的方法，即背压流量控制(BFC)。Tofino2是一种基于最先进的P4的可编程交换机ASIC，支持12.8 TB的交换容量。Tofino2在每个输出端口有32-128个独立的可暂停队列。我们的实现使用了Tofino2上不到10%的专用有状态内存。所有逐包操作都完全在数据平面上实现；BFC以全/full(满)交换机容量运行。

为了评估性能，我们使用合成跟踪(synthetic traces)来运行大规模ns-3仿真，这些跟踪与谷歌和Facebook数据中心在超额订阅的多级Clos网络拓扑上测得的工作量一致。我们将incast综合添加到这些工作负载中，以表示端到端和逐跳方法的挑战场景。我们考虑了短，中，长流的吞吐量和尾部时延性能。

对于我们的仿真工作负载，BFC提高了短流的时延和长流的吞吐量。与广泛部署的端到端系统(包括DCTCP、DCQCN和HPCC)相比，BFC在短流中的尾流完成时间(FCT)效果提高了2.3-60倍，在长流中的平均性能提高了1.6-5倍。ExpressPass实现了超过35%的短流尾部时延收益，但长流的平均情况性能差17倍。我们还证明了BFC的性能接近于一个理想的公平排队系统，该系统具有无界缓冲区和交换队列，但队列有限，缓冲区小得多。BFC可以与其他交换机调度算法相结合，如流量类别间(traffic classes)的优先级调度。与Homa等其他接收端驱动的方案不同，BFC不假设流大小的先验知识，也不依赖数据包spraying(这在实践中很难部署)。有了数据包spraying，Homa优于BFC，但没有它，我们发现BFC优于Homa，并且可以更准确地执行最短剩余流优先调度。

我们的具体贡献是：

<span style="font-family: Wingdings;color: #222222;letter-spacing: 1px;font-size: 16px;background: #FFFFFF">l <span style="color: #222222; letter-spacing: 1px; font-size: 16px; background: #FFFFFF; font-family: 微软雅黑;">一种用于逐跳逐流流量控制的实用协议，称为BFC，它使用少量、恒定的状态和数量有限的交换机队列，以实现典型数据中心工作负载的接近最佳的尾部时延性能。
</span>

<span style="font-family: Wingdings;color: #222222;letter-spacing: 1px;font-size: 16px;background: #FFFFFF">l <span style="color: #222222; letter-spacing: 1px; font-size: 16px; background: #FFFFFF; font-family: 微软雅黑;">商业交换机上对BFC的实施和概念验证评估。据我们所知，这是第一次为多Tbps交换机实现逐跳逐流流量控制方案。
</span>

## **2 动力**

在过去十年中，研究人员和数据中心运营商已经为数据中心提出了各种拥塞控制算法，包括DCTCP、Timely、Swift、DCQCN和HPCC。这些协议的主要目标是实现高吞吐量、低尾包时延，以及对突发和incast流量模式的高恢复/适应(resilience)能力。在操作上，这些协议依赖于端到端的反馈回路，发送方根据接收方反馈的拥塞反馈信号调整速率。无论信号类型如何(例如，ECN标记、多位INT信息，时延)，这些方案的反馈时延都是网络往返时间(RTT)。这种时延对端到端方案的性能有重要影响。尤其是，发送方需要至少一个RTT来获得反馈，因此在决定流的起始速率时面临着艰难的权衡。它们既可以以高速率启动，有可能导致拥塞，也可以以低速率启动，有可能出现利用网络不足。此外，即使在收到反馈后，如果网络状态(例如链路利用率和排队时延)与RTT相比变化很快，发送方也可能难以确定正确的速率。

我们认为，随着时间的推移，有三种趋势正在使这些问题变得更糟，并将使端到端协议实现良好性能变得越来越困难。

**趋势1：链接速度快速增加**。图1显示了Broadcom制造的顶级数据中心交换机的交换机容量。在过去六年中，交换机容量和链路速度增加了10倍，没有停止的迹象。

**趋势2：大多数流量都很短**。图2显示了三个行业数据中心工作负载的流量大小字节加权累信用布：(1)谷歌数据中心的所有应用程序，(2)Facebook中心的Hadoop集群，以及(3)WebSearch工作负载。每个点是属于小于该工作负载阈值的流的所有发送字节的分数。例如，对于Google工作负载，小于100KB的流代表了所有字节的近一半。随着链路速度的提高，越来越多的流量属于相对RTT而言完成得很快的流量。例如，大多数Facebook Hadoop流量可能会在未来十年内满足一次往返。虽然有人认为数据中心流的大小正在增加，但随着RDMA在细粒度远程内存访问中的使用越来越多，这种趋势可以说是相反的。

**趋势3：缓冲区大小不随交换机容量扩展**。图1显示，在过去六年中，总的交换机缓冲区大小相对于其容量几乎减少了2倍(从75us减少到40us)。相对于链路速度而言，缓冲区更小，现在缓冲区填充速度更快，使得端到端拥塞控制更难管理这些缓冲区。

### **2.1 端到端拥塞控制的限制**

这种结合——非常快的链路、短的流和不足的缓冲区——为端到端拥塞控制协议创造了完美的风暴。在一个或几个RTT内完成的流(在流量中所占比例越来越大)要么没有收到反馈，要么持续的反馈周期太少，以至于无法找到正确的速率。对于较长的流量，交叉流量的快速到达和离开会在RTT时间尺度上造成可用带宽的显著波动，因此很难找到正确的速率。其结果是吞吐量损失和大量队列累积。交换机缓冲不足进一步加剧了这些问题，导致数据包丢失或链路级暂停事件(PFC)，从而将拥塞扩散到上游。

为了理解这些问题，我们考虑了一个实验，一个长寿命的流在单个链接上对抗来自谷歌、脸谱网和WebSturk工作负载的交叉链接。我们以10、40和100 Gbps的速率重复该实验，在每种情况下，交叉业务流的平均负载设置为链路容量的60%。图3绘制了不同时间间隔内长寿命流量公平份额率的相对变化。当公平共享率随反馈时延(通常是RTT)发生显著变化时，拥塞控制协议难以跟踪公平共享率。随着链路速度增加或流量变短，公平共享率的变化更快(因为流量到达和结束更快)，因此拥塞控制变得更加困难。

表1详细考虑了一种配置，一个长流与在60%的平均负载下从Facebook流分布中提取交叉流量共享一个100 Gbps的链路。最小RTT(亦即反馈时延)为8us。我们考虑提出的方法(BFC)和两个端到端协议(DCQCN和HPCC)的单包(第九十九百分位)排队时延和吞吐量。BFC能够以低尾部时延实现长寿命流(40%)的接近最大可能吞吐量，而端到端协议在这两方面都有不足。

### **2.2 现有解决方案不足**

除了端到端拥塞控制之外，还有几种现有的解决方案。我们简要讨论这些方法中最突出的，以及为什么它们不足以应对上述挑战。

**优先级流控(PFC)**。处理增加的缓冲区占用率的一种方法是使用PFC，一种逐跳流控制机制。在PFC中，如果来自特定输入端口的数据包开始在拥挤的交换机上累积(超过可配置的阈值)，交换机将向上游发送“暂停”帧，阻止该输入发送更多流量，直到交换机有机会耗尽存储的数据包。这可以防止交换机缓冲区溢出。不幸的是，PFC有一个副作用：队头(HoL)阻塞。例如，向单个服务器incast的流量可能会导致PFC暂停帧向流量源上游发送一跳。这将停止所有通过暂停链接的流量，甚至那些流向其他未阻塞出端口的流量。这些数据流将被延迟发送，直到拥塞端口的数据包被排出。更糟糕的是，当数据包在PFC后面排队时，额外的PFC暂停帧可能会在上游跳数处触发，从而扩大了HoL阻塞的范围。

**交换机调度**。有几项工作使用交换机调度来克服大象流对短流时延的负面影响。这些建议包括公平排队的近似(例如，随机公平排队/Stochastic Fair Queuing，近似公平排队/Approximate Fair Queuing)，以及优先考虑短流的调度策略(例如，pFabric，QJump，Homa)。我们的工作与交换机调度策略的选择是正交的，我们首先给出了优先级调度和最短流的结果。调度本身并不能减少缓冲区占用；缓冲区可能会被填满，从而导致数据包丢失或HoL阻塞，而与调度无关。

**基于接收端的拥塞控制**。由于基于发送方的拥塞控制方案通常在incast工作负载上表现不佳，一些研究人员建议转向这样一种方案，即接收方通过显式地向发送方分配用于发送流量的信用来防止拥塞。三个例子是NDP、pHost和Homa。与这些方法相比，BFC做出的假设更少。例如，Homa假设知道流大小分布和流长度，因此它可以将流分配给接近最优优先级的队列；这在今天的TCP套接字接口中是不可用的，并且并非所有应用程序都提前知道流长度。Homa使用数据包spraying来实现更好的负载平衡，因此拥塞主要发生在最后一跳，在最后一跳中，接收端具有完全的可视性(complete visibility)。然而，对于广泛部署的超额订阅和不对称网络，网络核心的无拥塞运行很难设计。数据包spraying还可能导致数据包重新排序，这与高速终端主机软件和硬件数据包处理不兼容。其他方案建议在发送之前收集流接收端产生的信用(由流路径上的所有交换机控制的拥塞)；在高链路速度下，网络状态在反馈时延期间迅速变化，使得接收端难以确定正确的信用速率，这与基于发送方的协议类似。

### **2.3 再看逐跳、逐流的流量控制**

我们的方法受到了90年代早期管理千兆ATM网络的逐跳基于信用的流量控制工作的启发。同一时代的多处理器硬件设计也引入了基于信用的流量控制。在这些系统中，每个交换机都有系统地跟踪其缓冲区空间，当且仅当其缓冲区中有空间时，才允许在上游交换机上发送。在ATM中，不同流的数据包被缓冲在不同的队列中，并根据流的服务要求进行调度。其结果是网络在设计上没有拥塞丢包。

这种逐跳、逐流流量控制方案的理想实现具有以下几个理想特性：

**(1) 快速反应**：当流量开始在交换机处遇到拥塞时，上游交换机可以在1跳RTT内降低其速率，而不是标准拥塞控制方案所需的端到端RTT。同样，当交换机的容量变得可用时，上游交换机可以在1跳RTT内提高其速率(前提是上游交换机具有来自该流的数据包)。假设采用硬件实现，1跳RTT由传播时延和交换机管道时延组成——通常为1-2us。这比数据中心中典型的端到端RTT(例如10-20us)小得多，除了多个交换机跳数之外，还包括端点处的时延。

**(2) 缓冲池/Buffer pooling**：在流量突发期间，逐跳逐流流量控制机制会限制瓶颈上游的流量。这使得瓶颈交换机能够接入其上游邻居的缓冲区，从而显著提高网络吸收突发的能力。

**(3) 无HoL阻塞**：与PFC不同，逐跳逐流流量控制没有HoL阻塞或拥塞扩散，因为交换机隔离不同队列中的流，并分别对逐队列执行流量控制。

**(4) 简单的控制措施**：与端到端拥塞控制算法相比，逐跳逐流流量控制系统中的流量控制决策更易于设计和推理，因为：(i)是否在交换机上发送或暂停流量仅取决于下一跳交换机的反馈(而不是端到端方案中的多个潜在拥塞点)，(ii)通过在每个交换机上调度流，可以轻松地处理公平性等问题，因此流控制可以专门关注管理缓冲区占用和确保高利用率这一更简单的任务。

尽管有这些令人信服的特性，但逐跳逐流流量控制方案尚未得到广泛部署，部分原因是它们的实现复杂性和资源需求很高。ATM方案需要每个连接状态和大的缓冲区，这在今天的数据中心交换机中是不可行的。然而，我们观察到，实际上并不需要逐连接交换机的状态(per-connection switch state)。实际上，很多时候，逐连接状态都用于交换机上没有数据包排队的流，因此不需要对其进行流控制。

我们将活跃流(active flow)定义为这样一个流：其一个或多个数据包在交换机上排队。排队论的一个结果是，对于使用公平排队的交换机来说，活跃流的数量惊人地少。特别是，对于平均负载$$\rho<1$$的泊松流到达的M/G/1-PS(处理器共享)队列，活跃流的数量是具有均值为$$\frac{\rho}{1-\rho}$$的几何分布，与连接速度或流量大小分布无关。即使在负载$$\rho=0.9$$的情况下，活跃流的预期数量也只有9。这一事实背后的直觉是，公平排队交换机倾向于快速处理短流，完成它们并保持活跃流的数量较小。

数据中心网络的工作负载通常比泊松更具突发性，导致更长的队列和更多活跃流。然而，基本原则仍然成立。图4显示了在不同负载和链路速度下运行的单个瓶颈链路的活跃流数量的累信用布，使用谷歌流大小分布和(突发)对数正常流到达时间(log-normal flow inter-arrival times)。上图假设公平排队，并包含一个垂直线，显示Tofino2上每个端口的队列数。在100 Gbps时，仅当负载高于85%时，活跃流的数量显著超过队列的数量，然后仅略微超过；重要的是，分布对链接速度是不变的，而且趋势是更快的链接拥有更多的队列。最短剩余流优先(SRF)调度的结果更为有效。相比之下，使用FIFO排队时，即使是单个长流也会导致大量小流在其后面堆积，因此活跃流的数量要大得多。

## **3 设计**

我们的目标是为数据中心网络设计一个实用的逐跳、逐流控制系统。我们首先描述了设计的约束条件(第3.1节)。然后，我们勾勒出一个看似合理的strawman方案，结果出乎意料地完全不起作用(第3.2节)，并以此作为我们设计的动机(第3.3节)。

### **3.1 设计约束**

图5显示了逐跳、逐流控制方案(逐端口)的基本组件。(1)映射到物理队列：当数据包到达交换机时，交换机将数据包路由到出端口，并将其映射到该端口的FIFO队列。流到队列的这种分配必须是一致的，即保证数据包顺序。(2)背压模块/Backpressure module：根据队列占用情况，交换机为一些流生成背压反馈，并将其发送到上游。(3)调度器：每个出端口的调度器转发队列中的数据包，同时考虑来自下游交换机的背压反馈。

ATM逐跳逐流流量控制系统大致遵循这种架构，但它们对于现代数据中心来说是不切实际的。首先，他们假设每个流都有队列和状态，但现代交换机每个出端口的队列数量有限，表内存也不多。特别是，不可能为所有活跃连接保持交换机状态。其次，早期的方案并没有试图最小化缓冲区占用。相反，他们只在交换机缓冲区即将用完时才发送背压反馈。在受缓冲区约束的交换机上，这可能会导致缓冲区耗尽——速率慢的流(straggler flows)持有的缓冲区可能会阻止其他流在以后使用这些缓冲区。

**硬件假设**。现代数据中心交换机已经朝着更大的灵活性迈进，但它们并不是无限可塑性的，而且有真正的资源限制。基于Tofino2的性能，我们做出以下假设。

1、我们假设交换机是可编程的，并且支持有状态操作。Tofino2可以维护数以百万计的寄存器条目，并支持简单的逐包固定时间操作，以线速率更新状态。

2、交换机每个出端口的FIFO队列数量有限，这意味着流必须多路复用到队列上。Tofino2每100/400G端口有32/128个队列。将流分配到队列是可编程的。调度器可以在队列之间使用deficit round-robin(DRR)或优先级，但队列中的数据包是按FIFO顺序转发的。

3、逐队列都可以独立暂停和恢复，而不会减慢其他队列的转发速度。当我们暂停一个队列时，会暂停分配给该队列的所有流。交换机可以直接在数据平面内暂停/恢复逐队列。

### **3.2 Strawman方案**

我们最初认为，具有逐队列背压的随机公平队列可能会满足我们的目标：在流报文头上使用哈希函数，将每个流的数据包一致地分配给其出端口处随机选择的FIFO队列，并在其缓冲区超过1跳带宽时延积(BDP)时暂停队列。为简单起见，在每个交换机处使用相同的哈希函数。

这个strawman只需要少量状态来生成背压反馈，而不需要状态来分配队列。然而，即使是少量的活跃流，生日悖论(birthday paradox)也意味着，任何特定流都有很大的可能进入已被占用的FIFO队列。这些冲突影响时延有两个原因：(1)流的数据包将排队在到其他流的不相关数据包之后；例如，短流可能会在长流之后排队。(2)队列共享可能会导致HoL阻塞。如果某个特定流被暂停(因为它下游拥挤)，共享同一队列的所有流都将被时延。为了防止冲突影响尾部时延性能，strawman需要比活跃流多得多的队列。例如，在一个有n个活跃流的出端口，要实现少于1%的冲突，我们需要大约100n个队列。

### **3.3 背压流量控制(BFC)**

我们的设计实现了以下特性：

**最小化HoL阻塞**：我们动态地将流分配给队列。只要出口处的活跃流数量小于队列数量(概率很高)，就没有两个流共享一个队列，也没有阻塞。当一个新的流到达交换机时，如果一个队列可用，它将被分配到一个空队列，只有当所有队列都在使用时，它才会共享队列。

**低缓冲和高利用率**：当队列占用率超过一个小阈值时，BFC在上游暂停流。BFC的暂停阈值被激进地设置以减少缓冲(设置的小)。对于像PFC这样的粗暂停，暂停会严重影响利用率，但BFC只会暂停导致拥塞的流(发生碰撞时除外)。上游的剩余流量可以继续传输，避免利用不足。

**硬件可行性**：BFC不需要每个流状态，而是使用与交换机中物理队列数量成比例的内存量。为了有效地查找与流关联的状态，状态存储在流表中，该表是一个使用流标识符的哈希索引的数组。此数组的大小与物理队列的数量成比例设置。在我们的Tofino2实现中，它消耗的专用有状态内存不到10%。关键的是，产生背压并对其作出反应的机制很简单，相关操作可以在数据平面上完全以线速率实现。

**通用性**：BFC不假设网络拓扑结构或可能发生拥塞的位置，也不需要NDP或Homa等数据包spraying。此外，它不假设知道流量大小或截止时间。这些信息可以整合到BFC的设计中，以提高小流量性能(见附录A.2)，同时降低部署成本。

**幂等状态/Idempotent state**：由于光纤数据包在传输过程中可能会损坏，BFC确保以一种对数据包丢失具有弹性的方式，以幂等方式保持暂停和恢复状态。

#### **3.3.1 将流分配给队列**

为了最小化队列共享和HoL阻塞，我们动态地将流分配给空队列。只要流处于活跃状态(交换机上有排队的数据包)，该流的后续数据包将被放入同一FIFO队列。每个流都有一个唯一的源地址和目标地址、端口号和协议的5元组；我们称之为流标识符(FID)。BFC使用FID的哈希来跟踪流的队列分配。为了简化空队列的定位，BFC维护了空队列的位图。当队列中的最后一个数据包被调度时，BFC重置该队列的相应位。

通过动态队列分配，可以将流分配给不同交换机上的不同队列。为了暂停流，BFC暂停来自上游交换机(称为上游队列)的流的队列。暂停适用于与暂停流共享同一上游队列的所有流。我们在第3.3.2节中详细描述了暂停机制。包调度器使用DRR在未暂停的队列之间实现公平排队。

由于队列数量有限，因此当新的流到达时，所有队列都可能已分配，此时HoL阻塞是不可避免的。为了简化硬件，在这种情况下，我们将流分配给一个随机队列。分配给同一队列的数据包按FIFO顺序进行调度。活跃流的数量通常很小(第2.3节)，但在某些设置中，如incast，它可能超过队列的数量。在这种情况下，BFC的行为类似于随机公平排队，因为它会导致HoL阻塞。除最极端的情况外，BFC仍优于DCQCN和HPCC等现有协议(见附录A.1)。即使在大规模incast期间，BFC也可以利用大量向瓶颈交换机提供流量的上游队列来(1)吸收更大的突发，以及(2)限制拥塞扩散。特别是，当incast中涉及的流分布在多个上游端口之间时，BFC会将这些流分配给这些端口上的单独队列。只要流的总数不超过所有上游端口的队列总数，BFC就不会在上游交换机上产生HoL阻塞。随着网络规模的增加和每个交换机的扇入变得更大，上游交换机将有更多的队列来吸收incast，进一步减少拥塞扩散。

**机制**：为了跟踪队列分配，BFC维护一个由流的出端口和FID的哈希索引的数组。映射到同一索引的所有流都被分配到同一队列。我们维护每个条目的以下状态：物理队列分配(qAssignment)，以及来自映射到此条目的流的队列中的数据包数(size)。伪代码如下(我们将特定于交换机实施问题留给第6.1节)：

在流表中，如果两个流映射到同一个索引，它们将使用相同的队列(冲突)。由于流经不同出端口的流不能使用同一队列，因此索引还包括出端口。流表中的索引冲突可能会影响性能。这些冲突随着表的大小而减少，但流表不能任意大，因为交换机的状态内存有限。在我们的设计中，我们将流量表的大小设置为交换机中队列数的100倍。这确保了如果出端口的流数小于队列数，则索引冲突的概率小于1%。如果流的数量超过队列的数量，那么索引冲突无关紧要，因为不管怎样，物理队列中都会有冲突。Tofino2总共有4096个队列，因此流表的大小为409600个条目，不到交换机专用状态内存的10%。

虽然使用数组不节省内存，但访问状态却仅涉及简单的操作。维持流状态的现有解决方案要么涉及较慢的控制平面操作，要么更复杂。未来，如果队列数量大幅增加，我们可以将这些解决方案用于流表；然而目前，额外的复杂性是不必要的。

#### **3.3.2 背压机制**

如果分配给该流的队列占用率超过暂停阈值Th，BFC将暂停该流。要暂停/恢复流，交换机可以向上游交换机发送流ID信号，然后上游交换机可以暂停/恢复与该流相关的队列。虽然这种解决方案在原则上是可行的，但很难在当今的可编程交换机上实现。挑战在于，在接收到暂停时，上游交换机需要执行查找，以找到分配给该流的队列，以及一些额外的记录，以处理队列包含来自多个流的数据包的情况(其中一些可能已暂停，另一些未暂停)。

我们采取了不同的方法。交换机直接向上游设备发送信号，以暂停/恢复特定队列。每个上游交换机/源NIC在名为upstreamQ的特殊头字段中插入其本地队列号。下游交换机使用此信息在上游暂停队列。

**机制**：回想一下，通常情况下，在极少数情况下，多个流可以共享一个队列。这有两个含义。首先，我们跟踪队列长度(而不仅仅是flowTable.size)，并使用它来确定流的上游队列是否应该暂停。第二，通常，每个上游队列都可以有流在多个出口处向多个队列发送数据包。如果上游队列的任何一个流被分配了一个拥挤的队列，我们会暂停该队列，当上游队列的任何一个流在拥挤的队列中都没有数据包时(在数据包到达交换机时测量)，我们会恢复该队列。

我们使用一个暂停计数器(Pause Counter)、一个由入端口和数据包的upstreamQ索引的数组来监控这一点。当且仅当上游队列在下游交换机处的暂停计数器不为零时，上游队列才会暂停。在数据包排队时，如果其流被分配了一个超过暂停阈值的队列，我们将该索引处的暂停计数器增加1。当这个数据包(超过Th的那个)离开交换机时，我们将计数器减量1。无论分配给upstreamQ的流的数量如何，只有当其所有超过暂停阈值的数据包(当数据包到达时)离开交换机时，才会恢复。

为了最大限度地减少发送暂停/恢复所消耗的带宽，我们只在索引的暂停计数器从0变为1时发送暂停数据包，在索引的暂停计数器从1变为0时发送恢复数据包。为了防止暂停/恢复数据包被丢弃，我们还定期发送应该让上游暂停的队列位图(使用暂停计数器)。此外，交换机使用高优先级队列来处理暂停/恢复数据包。这将可用于动态队列分配的队列数量减少了1，但它消除了由于暂停/恢复数据包时延而导致的性能下降。

与流表(flow table)相比，暂停计数器所需的内存较小。例如，如果每个上游交换机每个出端口有128个队列，那么对于32端口的下游交换机，暂停计数器是4096个条目。

**暂停阈值**。BFC将任何队列累积视为拥塞的迹象。BFC将暂停阈值Th设置为队列排空速率下的1跳BDP大小。假设$$N_{active}$$表示出口处活动队列的数量，即具有未暂停传输数据的队列，HRTT是到上游的1跳RTT，u是端口容量。假设使用公平排队作为调度策略，则出口处队列的平均排放率为$$u/N_{active}$$。因此，暂停阈值Th由$$(HRTT)\cdot(u/N_{active})$$给出。当活动队列的数量增加时，Th减小。在非对称拓扑中，出端口可以具有不同的链路速度；因此，我们根据每个出口的速度计算不同的暂停阈值。类似地，入端口可以具有不同的1跳RTT。由于一个队列可以有来自不同入口的数据包，我们使用所有入口的最大HRTT来计算Th。我们使用一个预先配置的匹配操作表，该表用$$N_{active}$$和u的索引来计算Th。

BFC不保证流不会因为暂停而耗尽数据包。首先，如果一个流与其他暂停的流共享其上游队列，那么它可能会被不必要地暂停。其次，交换机只有在其所有数据包(到达时超过暂停阈值)离开下游交换机后，才会恢复上游队列。由于恢复需要HRTT才能生效，因此流可能会在HRTT的下游交换机处耗尽数据包，这可能会影响利用率。然而，这种情况不太可能发生——暂停只在队列建立时发生，通常是因为多个流正在竞争同一出端口。在这种情况下，出口处的其他流将具有要占用链路的分组，从而防止利用不足。

我们可以通过提前恢复上游队列来减少(小的)利用率不足的可能性，例如，当下游的流队列下降到Th以下时，或者更准确地说，当逐队列(来自同一上游队列的流)下降到Th以下时。实现这一点需要额外的记录，使设计复杂化。

增加暂停阈值将减少生成的暂停/恢复的数量，但只会以增加缓冲为代价(图7)。在附录C，我们在一个简单的模型中分析了Th对利用率不足和缓冲区峰值占用的影响，并且我们表明，当Th设置为1-hop BDP时，流最多有20%的时间会耗尽数据包。我们的评估结果表明，BFC的吞吐量比实际情况下的最坏情况要好得多(表1，第6节)。

**粘性队列分配/Sticky queue assignment**：使用upstreamQ暂停流带来了挑战。由于交换机不知道上游流的当前队列分配，因此它使用流的最后一个数据包传输的upstreamQ暂停队列。然而，如果流在上游交换机处用完了数据包(例如，因为它在下游交换机处而不是在上游处受到瓶颈限制)，则其队列分配可能会针对后续数据包发生变化，从而导致其暂时避开下游交换机发送的暂停信号。当下游接收到带有新upstreamQ的数据包时，这样的流将再次暂停。当旧队列的最后一个数据包(超过Th)离开下游交换机时，该队列也将取消暂停。

为了减少这种队列分配变化的影响，我们在流表状态中添加了一个时间戳，每当数据包排队或出队时都会进行更新。只有当流表中的大小/size值为0，且时间戳早于“粘性阈值/sticky threshold”(即，流表中的条目在交换机中没有小于此阈值的数据包)时，才会执行新的队列分配。由于使用BFC的背压机制，对于HRTT，流可能会耗尽数据包，因此我们将粘性阈值设置为HRTT的一个小倍数(2*HRTT)。

虽然粘性队列分配减少了积压的流更改队列的可能性，但它并不能完全消除这种可能性(例如，由于更前面的瓶颈，来自同一流的数据包到达的速度可能比这个时间间隔慢)。这种情况很少见，我们发现BFC的性能几乎与理想(但不切实际)变体相同，后者使用流ID直接暂停流，而不使用粘性队列分配。

## **4 TOFINO2 上 的实现**

我们在Tofino2中实现了BFC，这是一款即将发布的基于P4的可编程交换机ASIC，具有可重构匹配表(RMT, Reconfigurable Match Table)架构。Tofino2中的数据包首先通过入口管道，然后是流量管理器(TM, traffic manager)，最后是出口管道。Tofino2有四个入口和四个出口RMT管道。每个管道都有多个阶段，每个阶段都能够执行有状态的数据包操作。入口/出口静态分配给管道。

**记账/Bookkeeping**：流量表和暂停计数器都保存在入口管道中。流表包含每个条目的三个值，因此实现为三个独立的寄存器数组(每个值一个)，一个接一个地更新。

**多条管道**：流表被分成四条入口管道，每个入口管道中的流量表大小为25×队列数。在正常操作期间，活跃流的数据包到达单个入口管道(同一入端口)。因为流的状态只需要在单个管道中访问，所以我们可以拆分流表。然而，如果进入管道中的流量分布不均，则切分(splitting)可能会略微增加碰撞。类似地，暂停计数器在入口管道之间切分。入口管道包含对应于其自身入端口的暂停计数器条目。

**收集队列深度信息**：我们需要入口管道中的队列深度信息，用于暂停和动态队列分配。Tofino2有一个为这项任务量身定制的内置功能。TM可以将交换机中所有队列的队列深度信息传送到所有入口管道，而无需消耗任何额外的入口周期/cycles或带宽。空队列的位图会定期使用这些数据进行更新，每个管道有一个不同的旋转起点(rotating starting point)，以避免将新的流分配给同一个空队列。

**从出口到入口管道的通信**：当数据包到达时，前面描述的排队操作在入口管道中执行。出列操作应该发生在出口，但记账数据结构在入口。为了解决这个问题，在出口管道中，我们在数据包出队时对其进行镜像，并将镜像数据包的头循环回它来自的入口管道。在再循环的数据包报头上执行出列操作。

循环数据包涉及两个约束。首先，交换机有专门用于再循环的内部链路，但再循环带宽仅限于整个交换机容量的12%。第二，再循环的数据包消耗额外的进入周期。交换机每秒可以处理的数据包数量(pps容量)有上限。

大多数工作负载的平均数据包大小都大于500字节，Tofino2的设计在带宽和pps方面有足够的空闲容量，可以为这些工作负载的每个数据包处理报头循环(有空闲空间)。如果平均数据包大小小得多，我们可以通过采样数据包进行再循环来减少再循环(见附录A.8)。

再循环不是BFC的基础。例如，Tofino2对TM中的PFC记账具有原生支持能力。同样，如果在TM中实施BFC记账，则不需要循环。类似地，在具有分布式RMT架构（disaggregated RMT architecture）的交换机中，相同的内存可以在入口和出口处访问，因此不需要再循环。

## **5 讨论**

**无丢包保证/Guaranteed losslessness**。BFC不保证无损。特别是，BFC中的交换机仅在从其接收到数据包后才会暂停upstreamQ。这意味着upstreamQ可以在暂停之前向瓶颈交换机发送高达HRTT的数据包，即使交换机已经拥塞。在某些大规模incast的情况下，这可能足以触发丢包。使用信用/credits可以解决这个问题，但代价是增加了复杂性。我们将对BFC的这种潜在变体的研究留给未来的工作。在我们对实际交换机缓冲区大小的评估中，BFC从未发生过丢包，除非是在2000比1的情况下(第6.3节)，即使是在这种情况下，也只有0.007%的数据包被丢包。

**死锁/Deadlocks**：PFC等推回机制(Pushback mechanisms)已被证明在存在循环缓冲依赖(CBD)或行为异常的NIC时容易出现死锁。BFC NIC不会产生任何背压，因此不会导致死锁。由于NIC总是在排空（drain），在没有CBD的情况下，BFC不会出现死锁(正式证明见附录B)。如果BFC中的下游交换机耗尽upstreamQ发送的所有数据包，它将恢复upstreamQ。如果下游没有死锁，它最终将从上游排出数据包，因此，相应的上游无法死锁。

为了防止CBD，我们可以重用以前的方法来防止死锁。这些方法可分为两类。首先是重新设计路由协议，以避免安装可能导致CBD的路由。另一种方法是识别可证明无CBD的可能入口/出口对的子集，并仅沿这些对发送暂停/恢复。对于胖树拓扑，这将允许上下路径，但不允许临时环路或迂回路线/detour route。在BFC中，我们使用后一种方法。给定一个拓扑结构，我们预先计算一个由入口和出端口索引的匹配操作表，如果不允许，只需删除背压暂停/恢复信号。请参阅附录B了解详情。

**增量部署/Incremental Deployment**：在完全部署中，BFC不需要端到端的拥塞控制。在部分部署中，我们提倡某种形式的端到端拥塞控制，例如限制流中飞行数据包的数量。一种常见的升级策略是以比服务器NIC更快的速度升级交换机。如果只有交换机而不是NIC在运行BFC，那么对飞行中的数据包进行上界限制可以防止源NIC溢出第一跳交换机的缓冲区。同样的策略也可以用于在数据中心的其余部分之前升级一个集群的交换机。在我们的评估中，我们发现incast部署会对边缘的缓冲区占用产生一些影响，但对性能的影响最小(附录A.8)。

## **6 评估**

我们将对Tofino2实现进行概念验证评估。为了比较BFC与现有方案的性能，我们进行了大规模ns-3仿真。

### **6.1 Tofino2评估**

**试验台/Testbed**：为了进行评估，我们能够远程访问Tofino2交换机。通过使用单个交换机，我们创建了一个简单的多交换机拓扑(图6)，将数据包从出端口循环回交换机。所有端口均为100 Gbps，每个端口有16个队列。实验包括三组流。

为了产生流量，我们使用芯片上的数据包生成器，没有端到端的拥塞控制。

**低缓冲、高利用率**：图7a显示了当两个流在链路上竞争时(组2的流在交换机2→接收端2链路上与组3的流竞争)流的队列长度。暂停阈值显示为一条水平黑线。BFC的暂停机制能够将队列长度限制在暂停阈值(Th)附近。Th的被击穿（overshoot）有两个原因。首先，暂停需要HRTT才能生效。其次，Tofino2在出口管道之后有小的硬件队列，来自下游的暂停不能暂停已经在这些硬件队列中的数据包。

请注意，队列长度会暂时变为0。回想一下，下游交换机只有在从upstreamQ中排出超过Th的所有数据包后，才会恢复upstreamQ。因此，下游的流可能会耗尽HRTT的数据包。当两个流的队列同时变空时，这可能会导致利用率不足。我们重复上述实验，但改变暂停阈值。图7b显示出了平均队列长度和拥塞链路的利用不足。BFC的暂停阈值为2us，平均队列长度为15 KB，利用率接近100%。

**队列分配和拥塞扩散**：接下来我们评估队列分配对HoL阻塞和性能的影响。我们使用BFC的背压机制评估了三种不同的队列分配策略：(1)“BFC+单一”：所有流都分配到一个队列(类似于PFC)；(2) “BFC+随机”：使用随机哈希将流分配给队列；(3) “BFC+动态”：如第3.3.1节所述的动态队列分配。

该设置由两个组1流、八个组3流和一些组2流组成，这些流在4到20之间变化。所有流的大小都是1.5MB。实验的设计使得对于组2和组3流，瓶颈是交换机2→接收端2连接。组1流的瓶颈是交换机1→交换机2连接。交换机2将暂停交换机1处的队列，以响应来自组2流的拥塞。请注意，组1和组2流共享交换机1→交换机2连接。如果组1流与组2流共享队列(碰撞)，组2流产生的背压会减慢组1流的速度，导致HoL阻塞，并不必要地增加其流完成时间(FCT)。

图8显示了四次运行中组1流量的平均FCT。晶须/whiskers对应于FCT中的一个标准偏差。BFC+single实现了最差的FCT，因为组1和组2流始终共享一个队列。使用随机分配时，FCT显著降低，但FCT中的标准差很高。在某些运行中，组1和组2流不共享队列，也不存在HoL阻塞。在其他运行中，由于分配的随机性，它们确实共享一个队列(即使存在其他空队列)，导致性能更差。通过动态分配，BFC可以获得最低的平均FCT和最佳的尾部性能。特别是，当交换机1→交换机2链路(组1+组2流)处的流量数量少于队列数时，标准偏差接近于0。在这种情况下，组1流始终不会发生碰撞。当流的数量超过队列时，冲突是不可避免的，FCT中的标准偏差也会增加。

### **6.2 基于仿真的评估**

我们还在ns-3中实现了BFC。对于DCQCN，我们使用“NS-3 simulator for RDMA”的程序，对于ExpressPass，我们使用“Express pass simulation”中的程序，对于所有其他方案，我们使用“HPCC simulation”中的程序。

#### **6.2.1 设置**

**网络拓扑**：我们使用Clos拓扑，包含128个leaf服务器、8个机架顶部(ToR)交换机和8个spine交换机(订阅比例为2:1)。每个spine交换机连接到所有ToR交换机，每个ToR有16台服务器，每个服务器连接到一个ToR。所有链路均为100Gbps，传播时延为1us。最大端到端基本往返时间(RTT)为8us，1跳RTT为2us。交换机缓冲区大小设置为12 MB。相对于2.4 Tbps的ToR交换机容量，缓冲区大小相比与交换机容量为40us，与图1中Broadcom的Tomahawk3相同。我们使用1KB的MTU。除非另有规定，我们使用go-back-N进行重传，使用流级ECMP进行负载平衡，使用现有交换机中实现的标准共享缓冲内存模型。

**比较：HPCC**：HPCC使用来自交换机的显式链路利用率信息，以减少缓冲区占用和拥塞交换机处的丢包/PFC。我们使用论文中的参数$$\eta=0.95$$，maxStage=5。动态PFC阈值设置为当来自输入端口的流量占空闲缓冲区的11%以上时触发(如HPCC论文中所述)。我们对DCQCN和DCTCP使用相同的PFC阈值。

**HPCC-PFC**：这个版本用完美的重传取代了PFC。在丢包时，交换机直接通知发送方，然后发送方重新传输丢包。我们选择这种(可能是不切实际的)策略，以提供使用任何重传方案都可以实现的性能界限/上界。

**DCQCN**:DCQCN使用ECN标记位和端到端控制来管理拥塞交换机的缓冲区使用。ECN阈值在PFC之前触发(Kmin=100KB，Kmax=400KB)。

**DCTCP**：ECN阈值与DCQCN相同。流量以线速启动，以避免FCT因启动缓慢而退化。

**ExpressPass**：在ExpressPass中，发送方根据接收方生成的信用传输数据。这些信用在交换机上是有速率限制的，以避免拥挤。我们选择了$$\alpha=0.5$$，$$w_{init}=0.0625$$，信用缓冲区大小为16个信用。ExpressPass仿真器不遵循共享缓冲区模型；相反，它假定每个端口都有专用缓冲区。为了消除丢包，我们提供了75MB的高逐端口缓冲区值。没有PFC。

**BFC**：我们每个端口使用32个物理队列(与Tofino2一致)，我们的流表有76K个条目。流表占用400 KB的内存。我们选择逐流公平排队作为调度机制；所有的比较方案都力求每个流的公平性，因此，公平排队提供了一个公正的比较。

**Ideal-FQ**：为了了解BFC接近最佳性能的程度，我们仿真了在每个交换机上具有无限缓冲的理想公平队列。NIC将流的飞行数据包限制为1 BDP。请注意，无限缓冲在实践中是不可实现的；它的作用是限制我们可能做得多好。

**对参数的敏感性**：所有系统都配置为在无工作负载（unloaded network）的网络上实现单个流的完全吞吐量。对于端到端方案，参数的选择决定了短流(通过减少排队)和长流(更高的链路利用率)性能之间的权衡。我们在附录4中对HPCC、DCTCP和ExpressPass进行了参数敏感性分析。

**性能度量**：我们考虑三个性能指标：(1)FCT归一化到相同大小流的以链路速率运行的最佳可能FCT，(称为FCT slowdown)；(2) 交换机的总体缓冲区占用率；(3) 单个流的吞吐量。

**工作负载**：我们合成了一个跟踪，以匹配图2中讨论的行业工作负载的流量大小分布：(1) 谷歌数据中心中所有应用程序的总工作量；(2) Facebook上的Hadoop集群(FB_Hadoop)。流量到达模式是开环的，遵循$$\sigma=2$$的突发对数正态到达时间分布(bursty log-normal inter-arrival time distribution)。对于每个到达的流，源-目的地对都来自均匀分布。我们考虑有和没有incast的场景，不同的流量负载设置和incast比率。由于我们的拓扑结构被过度订阅，平均而言，核心(Spine-ToR)中的链接将比ToR-leaf服务器流链接更加拥挤。在我们的实验中，X%负载指的是核心链路上的X%负载。

#### **6.2.2 性能**

图9和图10显示了我们的主要结果。流量大小来自谷歌分布，平均负载设置为网络容量的60%。对于图9(但不是图10)，5%的流量(平均)来自incast流。incast为100比1，总大小为20MB。新的incast事件每500us启动一次。由于incast的最佳情况完成时间为1.6毫秒(20 MB/100 Gbps)，因此多个incast在网络中同时共存。我们报告了平均、第95和第99百分位的FCT slowdown、尾部缓冲区占用率(不遵循共享缓冲区模型的ExpressPass仿真除外)，以及因PFC而暂停的时间链接的比例。我们在附录12中分别报告了incast流量的FCT slowdown。

在所有方案中，DCQCN对于小流量的时延最差，无论是在平均值还是尾部值。与DCQCN相比，DCTCP使用每ACK反馈而不是通过QCN的周期性反馈，从而提高了时延。然而，频繁的反馈是不够的，而且性能远远不是最优的(Ideal-FQ)。问题是DCQCN和DCTCP对拥塞的响应都很慢。由于流以线速率开始，因此流可以在瓶颈处建立缓冲(100KB)的整个端到端带宽时延积(BDP)，然后才有可能降低其速率。在突发事件中，这个问题更加严重。瓶颈交换机可能会在每个incast流中累积一个BDP的数据包(对于100比1的incast，总计10 MB)。

这两种协议对于长流的吞吐量都很低。当容量可用时，长流量可能无法足够快地增加，从而降低吞吐量，并将其工作转移到更繁忙的时段，从而影响其他流量。此外，在突然出现拥堵时，流量可能不会以足够快的速度降低速度，从而减慢短流量。

HPCC通过使用链路利用率代替ECN和更好的控制算法，对DCQCN和DCTCP进行了改进。与DCQCN和DCTCP相比，HPCC减少了尾部时延、尾部缓冲区占用和PFC暂停(在incast的情况下)。然而，与BFC相比，HPCC在有incast的短流中的尾部时延差5-30倍，而在没有incast的情况下，尾部时延差2.3-3倍。与DCQCN和DCTCP相比，HPCC的长流性能更差，因为HPCC有意将95%的利用率和非常小的队列作为目标，以改善短流的尾部时延。

通过理想的重传，HPCC性能得到改善，尤其是对于短流和中等流。然而，没有PFC的HPCC具有更高的尾部缓冲区占用率和丢包率。与BFC相比，无论是长流还是短流，总体性能都更差。

在所有系统中，ExpressPass的长流量吞吐量最差。在ExpressPass中，接收端可以在得知流已完成之前为额外的RTT生成不必要的信用。这些信用被认为是“浪费”的，因为发送方无法发送响应数据包，因此可能导致链路利用率不足。信用浪费和相应的利用不足随着链路速度的加快和/或流量变短而增加。

Ideal-FQ实现了比所有方案更低的时延，但其缓冲区占用率可能会增长到不可行的水平。

在所有方案中，BFC实现了最好的FCT(平均和尾部)。如果没有incast，BFC的性能将接近最优。使用incast，传入流会耗尽物理队列的数量，从而触发HoL阻塞并影响尾部时延。对于尾部的最小的那些流量，这种影响最大。图10c显示了端口处活跃流数量的CDF。在没有incast的情况下，99%的时间内活跃流的数量小于总队列的数量，并且冲突很少发生。使用incast时，活跃流的数量会增加，从而导致碰撞。然而，使用BFC的短流的尾部时延仍然比现有方案高5-30倍。BFC还提高了incast流的性能，与HPCC相比，在尾部实现了2倍于HPCC的FCT(见附录A.12)。

请注意，与BFC和Ideal-FQ相比，使用现有方案，中等流(200-1000KB)的时延稍微好一些。因为相对于完美的公平性，它们会减慢长流的速度，所以中等流有更快通过的空间。相反，对于长流量，尾部slowdown比具有BFC和Ideal-FQ的中等流量更好。长期流达到接近长期平均可用带宽的效果，而中等流受瞬时拥塞的影响更大。

**另一种负载**：我们用Facebook公布的负载重复了图9和图10中的实验。图11显示了第99百分位FCT slowdown。FCT放缓的趋势与谷歌公布的相似，只是ExpressPass表现更好，因为它会减少Facebook工作负载的浪费信用(以百分比计)，后者的流量更大。出于空间的考虑，我们省略了前面介绍的其他统计数据，但其趋势与图9和图10相似。从今以后，所有的实验都使用Facebook的工作负载。

### **6.3 压力测试BFC**

在本节中，我们将在高负载和大加速程度下对BFC进行压力测试。流量到达遵循突发对数正态分布($$\sigma=2$$)。我们评估了两种不同队列配置下的BFC：(1)每个端口32个队列(BFC 32)；(2) 每个端口128个队列(BFC 128)。我们展示了长流量(>3MB)的平均slowdown和短流量(<3KB)的第99百分位slowdown。

**负载**：图12显示了平均负载在50%到95%之间变化时的性能(无incast)。HPCC仅支持高达70%的负载。在更高的负载下，它会变得不稳定(未完成流的数量会无限制地增长)，部分原因是INT报头的开销(每个数据包80 B)。所有其他方案在所有荷载值下都是稳定的。

在负载$$\leq$$ 80%，BFC 32实现了短流的较低尾部时延(图12b)和长流的较高吞吐量(图12a)。短流的尾部时延接近完美值1。在负载较高的情况下，流在瓶颈交换机处的排队时间更长，这增加了物理队列用完的可能性，从而导致线路阻塞。这尤其会影响短流的尾部性能，因为如果短流与长流被分配到同一队列，它们可能会时延更长的时间。在95%的高负载下，HoL头阻显著降低了BFC 32的尾部时延。然而，它仍然实现了良好的链路利用率，并且对于长流，冲突的影响是有限的。

增加队列数量可以减少冲突和相关的HoL阻塞。BFC 128在短流负载下实现了更好的尾部时延≥90%.

**Incast程度/degree**：如果Incast的大小足够大，可能会耗尽物理队列并影响性能。图13显示了改变incast程度对性能的影响。平均负载为60%，包括5%的incast。incast大小总计为20MB，但我们将incast的大小从10更改为2000。

就吞吐量而言，只要与队列数量相比，递增程度适中，BFC 32和BFC 128都表现良好。当递增程度超过每个端口的队列数的8倍时，两者都会开始降级。到目前为止，BFC可以利用更多上游队列(以及更大的聚合上游缓冲区空间)中的扇入来防止incast妨碍不相关的流量。随着加速程度进一步扩大，BFC 32能够保留其相对于HPCC和DCTCP的一些优势。

对于高incast规模，短流的尾部时延比HPCC更差。尾端是倾斜的，因为有百分之几的小请求恰好与incast发送到同一个目的地。(在我们设置的128个组1流服务器中，有几个服务器在任何时候都是incast的目标，这些服务器也会收到正常流量的份额。)随着incast程度的增加，更多的小流与incast流共享物理队列，从而导致更多的HoL阻塞。

在附录A.1，我们通过设计用于在瓶颈交换机处触发可变数量活跃流的微基准来进一步探讨这个问题。我们表明，通过向BFC添加一个非常简单的端到端控制机制，我们可以在充分利用链路的同时改善HoL阻塞的影响。

### **6.4 动态队列分配**

接下来，我们考虑应用BFC的动态队列分配独立于背压机制的效果。为此，我们改进了HPCC和理想重传(HPCC-PFC)，添加了随机公平队列(HPCC-PFC+SFQ)和动态队列分配(HPCCPFC+DQA)。为了匹配BFC，我们使用32个物理队列和HPCC。我们重复图11a中的实验，图14显示了HPCC变体、BFC和Ideal-FQ的尾部slowdown和缓冲区占用。

通过将SFQ与不同队列中的长流隔离，将SFQ添加到HPCC可以改善短流时延，但它仍然比DQA遭受更多冲突(因此短流的尾部时延更高)。然而，DQA本身对长流量没有好处：由于HPCC无法适应流数量(以及公平份额率)的快速变化，因此即使使用DQA，它也无法充分利用长流量的链路。此外，HPCC-PFC+SFQ和HPCCPFC+DQA都构建了深度缓冲区，遭受丢包的速度与HPCC-PFC相同。请注意，HPCC较低的长流吞吐量有利于短流，以至于HPCC-PFC+DQA在短流中实现了比BFC和IdealFQ更好的尾部时延。

### **6.5 额外的实验**

在附录A，我们使用我们的仿真框架来进一步描述BFC的限制，比较BFC和Homa，以及研究优先级调度、参数选择、流量矩阵中的局部性、慢启动、incast标记和其他因素的影响。

## **7 结论**

本文提出了一种实用的数据中心网络拥塞控制体系结构——背压流量控制(BFC)。BFC提供逐跳逐流流量控制，但具有有界状态、恒定时间切换操作和谨慎使用缓冲区的特点。交换机动态地将流分配给物理队列，允许在相互竞争的流之间进行公平调度，并使用选择性背压来减少缓冲，同时尽可能减少HoL阻塞。相对于现有的端到端拥塞控制方案，BFC改善了具有高带宽链路和突发流量的网络的短流尾部时延和长流利用率。我们通过在最先进的基于P4的可编程硬件交换机Tofino2上实现BFC来证明它的可行性。在仿真中，与几种部署的端到端方案相比，对于短流，BFC实现了2.3-60倍更低的尾部时延，对于长流，BFC实现了1.6-5倍更好的平均完成时间。

> 参考文献：Prateesh Goyal , Preey Shah , Kevin Zhao , Georgios Nikolaidis , Mohammad Alizadeh , Thomas E. Anderson, “Backpressure Flow Control”, NSDI 2022

> <span style="font-style: italic;">声明：本文素材来源于网络，仅供学习使用，如有侵权请联系网站删除(ngdcn_admin@163.com)。由于本人水平有限，如有纰漏，请以参考文献文章为准。</span>

<font color=red>**欢迎扫码关注微信公众号“网络技术风云汇”，更快速接收更多网络技术咨询。**</font>