Copa：端到端的互联网拥塞控制算法

来源
：Networked Systems Design and Implementation

作者
：Venkat Arun & Hari Balakrishnan

内容整理
：尹文沛

摘要
简介
Copa 算法

目标速率和更新规则
与缓冲区填充方案竞争

动态 Copa

中位 RTTstanding
达到平衡的替代方法

Copa 目标利率的合理性

目标函数和纳什均衡
引理 1：

Copa 更新规则遵循均衡率

等式的性质

评估

模拟链路上的动态行为
真实世界评估
RTT 公平性
对丢包的鲁棒性
模拟数据中心网络
模拟卫星链路
与缓冲填充方案共存

相关工作
总结

摘要

本文介绍了 Copa，一种采用三种思想的端到端拥塞控制算法。首先，它表明目标速率等于，其中是（测量的）排队延迟，优化了马尔可夫数据包到达模型下吞吐量和延迟的自然函数。其次，它在这个目标速率的方向上调整它的拥塞窗口，即使面对明显的流量流失，也能迅速收敛到正确的公平速率。这两个想法使一组 Copa 流能够以低排队延迟保持高利用率。然而，当瓶颈与填充缓冲区的基于丢失的拥塞控制流共享时，Copa 与其他延迟敏感方案一样，吞吐量都会很低。为了解决这个问题，Copa 使用了第三种想法：通过观察延迟演变来检测缓冲填充物的存在，并以参数的加法增加/乘法减少来响应。实验结果表明，Copa 优于 Cubic（相似的吞吐量、更低的延迟、更公平的不同 RTT）、BBR 和 PCC（显着更公平、更低的延迟），并且与 BBR 和 PCC 不同的是，copa 能够与 Cubic 共存。Copa 对非拥塞损失和大瓶颈缓冲区也很稳健，并且在长 RTT 路径上优于其他方案。

简介

一个好的互联网端到端拥塞控制协议必须实现高吞吐量、低排队延迟，并以公平的方式为流分配速率。尽管经过了三年的努力，这些目标仍然难以实现。原因之一是网络技术和应用程序一直在不断变化。自从十年前部署 Cubic [13] 和 Compound [32, 31] 以提高 Reno 在高带宽延迟积 (BDP) 路径上的性能 [16] 以来，链路速率显着提高，无线（随时间变化）链路速率已变得普遍，互联网变得更加全球化，地面路径的往返时间 (RTT) 比以前更高。更快的链接速率意味着许多流更快地启动和停止，从而增加流量流失的水平，但是视频流和大批量传输（例如文件共享和备份）的流行意味着这些长流必须与短流共存目标不同（高吞吐量与低流完成时间或低交互延迟）。较大的 BDP 会加剧“缓冲膨胀”问题。更加全球化的互联网导致具有非常不同的传播延迟的流共享一个瓶颈（加剧了许多当前协议所表现出的 RTT 不公平性）。

与此同时，应用程序提供商和用户对性能变得更加敏感，实时和流媒体的“体验质量”概念以及用于衡量 Web 性能的各种指标正在开发中。许多公司已投入大量资金来改善网络和应用程序性能。因此，作为用于在 Internet 上传递数据的传输协议的核心，拥塞控制算法的性能对于理解和改进非常重要。

拥塞控制研究已经在多个线程中发展。一个线程，从 Reno 开始，扩展到 Cubic 和 Compound，依赖于丢包（或 ECN）作为基本的拥塞信号。由于这些方案填满了网络缓冲区，它们以排队延迟为代价实现了高吞吐量，这使得交互式或类似 Web 的应用程序在长时间运行的流也共享瓶颈时难以获得良好的性能。为了解决这个问题，Vegas [4] 和 FAST [34] 等方案使用延迟而不是损失作为拥塞信号。不幸的是，由于 ACK 压缩和网络抖动，这些方案容易高估延迟，从而导致链路利用率不足。此外，当使用并发的基于丢失的算法运行时，这些方法的吞吐量很差，因为基于丢失的方法必须填充缓冲区以引发拥塞信号。

大约十年前开始的第三个研究方向专注于网络环境或工作负载的重要特殊情况，而不是争取普遍性。在过去的几年里，数据中心 [1、2、3、29]、蜂窝网络 [36、38]、Web 应用程序 [9]、视频流 [10、20]、车载 Wi-Fi [8] 出现了新的拥塞控制方法, 21] 等等。专用拥塞控制方法的性能通常明显优于先前的通用方案。可以产生比人类更好的行动。该线程中的工作包括 Remy [30, 35]、PCC [6] 和 Vivace [7]。这些方法定义了一个目标函数来指导提出一组在线操作的过程（例如，在每个 ACK上，或周期性地），这将优化指定的功能。Remy 离线执行此优化，生成将观察到的拥塞信号映射到发送者操作的规则。PCC 和 Vivace 执行在线优化。

在许多情况下，这些目标优化方法优于更传统的窗口更新方案 [6, 35]。然而，它们的缺点是在运行时执行的在线规则要复杂得多，而且人类难以推理（例如，典型的 Remy 控制器有超过 200 条规则）。使用在线优化的方案需要能够测量进入目标函数的因素，这可能需要一些时间才能获得；例如，PCC 的默认目标函数包含丢包率，但是以低丢包率（理想情况）运行的网络将需要相当长的时间来估计。

我们询问是否有可能开发一种拥塞控制算法，以实现高吞吐量、低排队延迟和公平速率分配的目标，但它也易于理解并且普遍适用于广泛的环境和工作负载，并且其性能至少与为特定情况设计的最佳先验方案一样好。

方法：我们开发了 Copa，一种实现这些目标的端到端拥塞控制方法。受网络效用最大化 (NUM) [18] 工作和机器生成算法的启发，我们从一个目标函数开始进行优化。我们使用的目标函数结合了流的平均吞吐量，，和数据包延迟（减去传播延迟）, 。目标是最大化每一个发送者的。在这里，决定了与吞吐量相比延迟的权重；较大的表示要求较低的数据包延迟。

我们表明，在数据包到达的某些简化（但合理）建模假设下，最大化的稳态发送速率（以每秒数据包为单位）为:

其中是每个数据包的平均排队延迟（以秒为单位），以 MTU 大小的数据包为单位。当每个发送者都以这个速率传输时，就会达到一个独特的、社会可接受的 NASH 均衡。

我们将此费率用作 Copa 发件人的目标费率。发送方使用其 RTT 观测值估计排队延迟，然后快速移动到接近该目标速率附近。这种机制还引入了队列定期刷新的属性，这有助于所有端点获得对排队延迟的正确估计。最后，为了更好地与缓冲区填充竞争流竞争，当 Copa 观察到瓶颈队列很少为空时，它会模仿 AIMD 窗口更新规则。

结果：我们在模拟、现实世界的互联网路径以及将 Copa 与其他几种方法进行比较的模拟中进行了几次实验。

随着流量进入和离开模拟网络，Copa 保持几乎完全的链路利用率，Jain 公平指数中值为 0.86。Cubic、BBR 和 PCC 的中位数指数分别为 0.81、0.61 和 0.35（越高越好）。
在现实世界的实验中，Copa 实现了几乎与 Cubic 和 BBR 相同的吞吐量和低 2-10 倍的排队延迟。
在数据中心网络模拟中，在从数据中心网络 [11] 绘制的网络搜索工作负载跟踪中，Copa 在 DCTCP 上的短流完成时间减少了 5 倍以上。它在长流中实现了类似的性能。
在模拟卫星路径的实验中，Copa 实现了几乎完全的链路利用率，平均排队延迟仅为 1 毫秒。Remy 的性能相似，而 PCC 实现了相似的吞吐量，但排队延迟约为 700 毫秒。BBR 以≈100ms 的排队延迟获得了 50% 的链路利用率。Cubic 和 Vegas 的利用率均小于 4%。
在测试 RTT 公平性的实验中，Copa、Cubic、Cubic over CoDel 和 Newreno 分别获得了 0.76、0.12、0.57 和 0.37 的 Jain 公平指数（越高越好）。Copa 旨在与 TCP 共存（参见第 2.2 节），但当被告知不存在竞争 TCP 时，Copa 为所有流分配了相等的带宽（公平指数≈1）。
Copa 与 TCP Cubic 很好地共存。在一组随机选择的模拟网络中，Copa 和 Cubic 流共享一个瓶颈，Copa 流受益并且 Cubic 流在平均吞吐量上没有受到损害（直到统计上不显着的差异）。BBR 和 PCC 以竞争 Cubic 流为代价获得更高的吞吐量。

Copa 算法

Copa 包含三个想法：首先，目标速率与测量的排队延迟成反比；其次，一个窗口更新规则依赖于将发送者向目标速率移动；第三，与缓冲区填充流竞争的 TCP 竞争策略。

目标速率和更新规则

Copa 使用拥塞窗口 cwnd，它设置了传输中数据包数量的上限。在每个 ACK 上，发送方估计当前速率，其中是在最近的时间窗口内观察到的最小 RTT。我们使用，其中 srtt 是标准平滑 RTT 估计的当前值。RTTstanding 是对应于“站立”队列的 RTT，因为它是最近时间窗口中观察到的最小值。

发送方使用等式（1）计算目标比特率，估计排队延迟为：

其中是长时间观察到的最小 RTT。我们使用 10 秒和流开始以来的时间中的较小值（10 秒用于处理可能改变路径最小 RTT 的路由更改）。

如果当前速率超过目标，发送方减少 cwnd；否则，它会增加 cwnd。为避免数据包突发，发送方以每秒数据包的速率对数据包进行调整。随着流数量的增加，发送的过程还会使到达瓶颈队列的数据包出现泊松，这是一个有用的属性，可以提高我们模型推导目标速率的准确性（§4）。发送速率是双倍的，以适应发送中可能有的缺陷；如果它恰好是，那么发送者的发送速度可能比期望的慢。

在最近的持续时间中使用最小 RTT 的原因，而不是最新的 RTT 样本，是为了在 ACK 压缩 [39] 和网络抖动方面具有鲁棒性，因为这会增加 RTT 并可能使发送者混淆相信较长的 RTT 是由于在前向数据路径上排队造成的。ACK 压缩可能由反向路径上的排队和无线链路引起。

Copa 发送者在每次 ACK 到达时运行以下步骤：

使用等式(2)更新排队延迟，使用标准的TCP指数加权移动平均估计器估计。
根据等式(1)，设置
如果，那么，其中是一个“速度参数”（在下一步中定义）。否则，，在 1 个 RTT 上，cwnd 的变化因此是个数据包。
速度参数，，加速收敛。被初始化为 1。每个窗口一次，发送方将当前 cwnd 与发送最新确认数据包时的 cwnd 值（即当前窗口开始处的 cwnd）进行比较。如果当前 cwnd 较大，则将方向设置为“向上”；如果较小，则将方向设置为“向下”。现在，如果方向与之前相同，就将值翻倍。如果方向不一致，则将值重新设置为 1。但是，只有在三个 RTT 的方向保持不变后，才能开始将加倍。由于在稳定状态下 2.5 个 RTT 的方向可能保持不变，如图 1 所示，否则即使在稳定状态下也可能导致。在稳定状态下，我们希望。

图1 一个 Copa 周期：队列长度随时间的演变。当 RTTstanding 估计的站立队列长度超过的阈值时，Copa 在变化点 A 和 B 处切换方向。RTTstanding 是 ACKs 数据包的最后一个窗口（阴影区域）中的最小 RTT。当前动作的反馈在网络中延迟了 1 个 RTT。线的斜率是每个 RTT 的个数据包

当流程开始时，Copa 执行慢启动，其中 cwnd 每个 RTT 加倍一次，直到超过。虽然速度参数也允许指数增加，但常数更小。有一个明确的慢启动阶段允许 Copa 有一个更大的初始 cwnd，就像许多部署的 TCP 实现一样。

与缓冲区填充方案竞争

我们现在修改 Copa 以与 Cubic 和 NewReno 等缓冲填充算法很好地竞争，同时保持其良好的属性。问题是 Copa 试图保持较低的排队延迟。如果不进行修改，它将输给缓冲区填充方案。我们为 Copa 提出了两种不同的运营模式：

默认模式，其中。
动态调整以匹配典型缓冲区填充方案的积极性的竞争模式。

Copa 在这些模式之间切换取决于它是否检测到竞争的长时间运行的缓冲区填充方案。检测器利用了一个关键的 Copa 属性，即当只有具有相似 RTT 的 Copa 流共享瓶颈时，队列至少每一次为空（第 3 节）。即使有一个并发的长时间运行的缓冲区填充流，队列也不会在此周期为空。因此，如果发送者在最后 5 个 RTT 中看到“几乎为空”的队列，它会保持默认模式；否则，它会切换到竞争模式。我们估计“几乎是空的”，因为任何排队延迟低于最后四个 RTT 中速率振荡的；即，，其中是在过去四个 RTT 中测量的，而是我们之前定义的长期最小值。使用允许 Copa 将其“近乎空”的概念校准为当前网络中的短期 RTT 方差量。

在竞争模式下，发送者根据希望模拟的任何缓冲区填充算法（例如，NewReno、Cubic 等）改变。在我们的实现中，我们根据数据包成功或丢失在上执行 AIMD，但该方案可以响应其他拥塞信号。竞技模式下，。当 Copa 从竞技模式切换到默认模式时，它会将重置为 0.5

即使存在竞争的缓冲区填充流（例如，由于最近的数据包丢失），队列也可能几乎是空的。如果发生这种情况，Copa 将切换到默认模式。最终，缓冲区将再次填满，使 Copa 切换到竞争模式。

请注意，如果某些 Copa 流在竞争模式下运行，但不存在缓冲区填充流，可能是因为决策错误或竞争流离开了网络，则 Copa 流再次开始定期清空队列。模式选择方法将检测到这种情况并切换到默认模式。

动态 Copa

图 1（示意图）和 2（仿真链接）显示了 Copa 的 cwnd 随时间的演变。

图2 在 12 Mbit/s Mahimahi 模拟链路上运行的 Copa 流的拥塞窗口和 RTT 作为时间的函数。正如预测的那样，振荡周期约为 5RTT，幅度约为 5 个数据包。模拟器的调度策略会导致 RTT 测量的不规则性，但 Copa 不受此类不规则性的影响，因为 cwnd 的演变仅取决于将 RTTstanding 与阈值进行比较。

在稳定状态下，每个 Copa 流都会围绕目标速率产生小幅振荡，这也是平衡速率（第 4 节）。“均衡”是指每个发送者都以目标速率发送的情况。当共享瓶颈的流的传播延迟与排队延迟相似且可比（或大于）时，小的振荡同步导致瓶颈处的队列长度在每五个 RTT 具有和数据包之间振荡。在这里，。平衡队列长度为包。当每个（默认值）时，，其中为总的流数量。

我们使用简化确定性 (D/D/1) 瓶颈队列模型的窗口分析来证明上述关于稳态的断言。在第 4 节中，我们讨论马尔可夫（M/M/1 和 M/D/1）队列。我们假设链路速率是恒定的（或与 RTT 相比变化缓慢），并且（为简单起见）反馈延迟是恒定的。这意味着在时间从 ACK 推断出的队列长度为，其中是时间的拥塞窗口，BDP 是带宽延迟乘积(BandWidth-Delay Product)。在恒定延迟假设下，发送速率为。

首先考虑一个 Copa 发送端。实验表明，一旦 Copa 开始振荡，它就会保持稳定状态振荡，如图 1 所示。在稳定状态下，（只有在 cwnd 以相同方向改变至少 3 个 RTT 后，才开始加倍。在稳定状态下，方向每 2.5 个 RTT 改变一次。（因此一直保持在稳态下，）当流到达“变化点 A”时，它的估计对应于最近 ACK 的窗口中的最小值。最新的 ACK 对应于前发送的数据包。在平衡时，当目标速率，等于实际速率，，队列中有个数据包。当队列长度超过这个数据包的阈值时，目标速率变得小于当前速率。因此发送方开始减少 cwnd。当流量到达“变化点B”时，队列长度已降至 0 个数据包，由于 cwnd 每个 RTT 减少个数据包，发送方需要 1 个 RTT 才能知道队列长度已降至目标以下。在“变化点 B”，速率再次开始增加，继续循环。由此产生的循环平均队列长度，为，略高于，因为需要额外的才能达到“变化点 A”的阈值。

当每个具有不同的 N 个发送者共享瓶颈链路时，它们相对于公共延迟信号同步。当它们都具有相同的传播延迟时，它们的目标速率会同时超过它们的实际速率，而与它们的无关。因此，他们一起增加/减少他们的 cwnd，表现得像一个发送者。

为了引导上述稳态振荡，目标速率应高于或低于每个发送者的当前速率至少 1.5 RTT，而每个。请注意，其他振荡模式也是可能的，例如，当两个发送者以异相平衡速率振荡时，保持队列长度不变。然而，小的扰动将导致目标速率高于/低于每个发送者的当前速率，从而导致上述稳态振荡开始。到目前为止，我们假设。在实践中，我们发现速度参数允许系统快速达到目标速率。然后它保持等于 1，因为发送者悬停在目标周围。

为了从经验上验证我们的主张，我们模拟了一个哑铃拓扑结构，它具有 100 Mbit/s 的瓶颈链路、20 ms 的传播延迟和 ns-2 中的 5 BDP 缓冲区。我们一一引入流，直到 100 个流共享网络。我们发现上述属性在整个模拟过程中保持不变。速度参数在大多数情况下保持等于 1，仅在流量远离平衡速率时才发生变化。事实上，这些说法在我们的大多数实验中都成立，即使是在有意添加抖动的情况下。

我们发现这种行为在实践中只有在两种情况下才会中断：（1）当传播延迟远小于排队延迟时；（2）当不同的发送者具有非常不同的传播延迟时，延迟同步减弱。这些违规可能会导致端点错误地认为存在竞争的缓冲区填充流（参见第 2.2 节）。即使在竞争模式下，Copa 也提供了优于 TCP 的几个优势，包括更好的 RTT 公平性、更好的收敛到公平速率以及损失恢复能力。

中位 RTTstanding

如果流达到的稳态速率，则中值站立排队延迟，。如果的中位数较低，Copa 会更频繁地增加其速率而不是降低，从而增加。如果更高，类似的推理也成立。这意味着 Copa 实现了可量化的低延迟。例如，如果每个流在默认模式下达到速率（），则平均平衡排队延迟为 20 ms（一个包大小为1500bytes,）。如果达到 12 Mbit/s，平均平衡排队延迟将是 2 ms。在此分析中，我们忽略了稳态振荡期间的变化，因为它很小。

达到平衡的替代方法

另一种方法是直接将当前发送速率设置为目标速率。我们对这种方法进行了试验和分析，但发现系统仅在某些条件下才会收敛。我们证明了当时系统收敛到一个恒定速率，其中是一个无量纲常数。通过 ns-2 模拟，我们发现这个条件对于收敛是必要和充分的。否则它会振荡。这些振荡可能导致网络严重利用不足，确保我们始终在保证收敛的条件下运行并非易事。

此外，收敛到恒定速率和非零排队延迟对于基于延迟的拥塞控制器来说并不理想。如果队列永远不会清空，那么稍后到达的流将高估它们的最小 RTT，从而低估它们的排队延迟。这会导致严重的不公平。因此，我们需要一个逐渐接近平衡并围绕平衡进行小幅振荡以定期排空队列的方案。

当比率低于或高于目标时，Copa 方法的自然替代候选者是加法增加/乘法减少 (AIMD)。然而，Copa 的目标函数力求使队列长度保持较小。如果此时执行乘法减少，则会出现严重的利用率不足。类似地，平衡点附近的乘法增加将导致较大的队列长度。

AIAD 满足我们的许多要求。它收敛到平衡并围绕它进行小幅振荡，以便队列定期清空，同时保持高链路利用率（§5.1）。但是，如果带宽延迟积 (BDP) 很大，AIAD 可能需要很长时间才能达到平衡。因此，我们引入了一个速度参数 §2.1，它将速率以指数方式快速移向平衡点，之后使用 AIAD。

Copa 目标利率的合理性

本节解释了 Copa 中使用的目标汇率的基本原理。我们对瓶颈处的数据包到达建模不是像上一节中那样确定性到达，而是泊松到达。这是一个简化的假设，但是当有多个流时，它比确定性到达更现实。随机数据包到达的关键特性（例如泊松分布）是即使瓶颈链路没有完全利用，队列也会建立。

一般来说，流量可能比泊松到达[28]预测的更突发，因为流和数据包传输可以相互关联。在这种情况下，Copa 高估了网络负载，并通过隐含地更多地评估延迟来做出响应。这种行为是合理的，因为要更加谨慎地应对更高延迟的风险。最终，我们通过实验验证了 Copa 算法，但建模假设为设置良好的目标速率提供了良好的基础。

目标函数和纳什均衡

考虑结合吞吐量和延迟的发送者（流）的目标函数：

其中，是“转换时延”(total minus propagation delay)，使用 switch-delay 是为了技术上的方便；它几乎等于排队延迟。

假设每个发送者都试图最大化自己的目标函数。在这个模型中，当没有发送者可以通过单方面改变其速率来增加其目标函数时，系统将处于纳什均衡。纳什均衡是发送速率的 n 元组满足：

对于所有发送者和任何非负。

我们假设马尔可夫数据包到达的一阶近似。瓶颈的服务过程可能是随机的（由于交叉流量，或时变链路速率），也可能是确定性的（固定速率链路，无交叉流量）。作为瓶颈环节随机服务过程的合理一阶模型，我们假设一个马尔可夫服务分布，并使用该模型开发 Copa 更新规则。假设确定性服务过程给出了类似的结果，设置偏置因子为 2。原则上，发送者可以不以某个平均速率而是以马尔可夫方式发送他们的数据，这将使我们的建模假设与实践相匹配。在实践中，我们不这样做，因为：(1) 无论如何，来自端点的传输存在自然抖动，(2) 当发送者数量较少时，故意的抖动会不必要地增加延迟，以及 (3) Copa 的行为对假设不敏感。

我们证明了以下关于马尔可夫数据包传输存在纳什均衡的命题。然后，我们使用该平衡的特性来推导方程式的 Copa 目标速率。(1)。我们对均衡属性感兴趣的原因是速率更新规则旨在独立优化每个发送者的效用；我们直接从纳什均衡的理论速率推导出来。需要注意的是，使用这个模型并不是因为它精确，而是因为它是对现实的简单易懂的近似。我们的目标是推导出一个作为模型稳定点出现的原则性目标速率，并用它来指导速率更新规则。

引理 1：

考虑一个有 n 个流的网络，流以速率发送数据包，使得到达瓶颈队列是马尔可夫。然后，如果流具有由等式定义的目标函数(3)。并且瓶颈是 M/M/1 队列，存在唯一的纳什均衡。

此外，在这种均衡下，对于每个发送者，

其中，。

证明：表示队列中的总到达率，对于 M/M/1 队列，队列和链路的平均等待时间之和为。将此表达式代入方程式 (3) 并分离出项，我们得到：

令每个流的偏导数等于 0 会产生:

的二阶导数，是负数。

因此方程 (4) 满足当且仅当。我们得到以下 n 个方程组，每个发送者 i 一个方程组：

这个线性方程组的唯一解是：

这是发送者的期望均衡发送速率。当假定服务过程是确定性的时，我们可以将网络建模为 M/D/1 队列。队列中的预期等待时间为。与上述类似的分析给出发送者的均衡速率为，这与每个减半时的 M/M/1 情况相同。由于不确定性较小，因此发送者可以在相同的延迟下获得更高的速率。

Copa 更新规则遵循均衡率

在平衡状态下，数据包之间的发送时间为：

然而，由于马尔可夫到达的聚合行为，每个发送者不需要知道还有多少其他发送者，也不需要知道他们的偏好是什么。上述等式中括号内的术语代表其他发送者的“有效”数量，或等效的网络负载，并且可以以不同的方式计算。

如前所述，M/M/1 队列的平均切换延迟为。将方程 (8) 代入该方程中的，我们发现，在平衡时，

其中是切换延迟(switch delay)（如前所述），是网络中的平均排队延迟。

这个计算是目标速率的基础和灵感。没有模拟 Copa 的动态，其中发件端速率随时间变化。此分析的目的是为发送端确定一个好的目标速率。然而，使用稳态公式计算预期队列延迟是可以接受的，因为速率在稳态下变化缓慢。

等式的性质

我们现在对这种均衡做一些评论。首先，在所有 i 上添加等式(5)，我们发现所有发送者的总速率为：

这也意味着平均排队延迟为。如果，具有 n 个流的入队数据包的数量是。这个平均排队延迟是根据 (7) 式，和算出来的。

其次，解释方程式很有趣。(5) 和 (8) 在重要的特殊情况下，当都是相同的。然后，，这相当于将容量除以个发送者和（可能是非整数）“伪发送者”。是从完全加载瓶颈链路到允许平均数据包延迟不爆炸到的“差距”。分配给“伪发送者”的容量部分未使用，它决定了发送者可以通过选择任何来调整平均队列长度。

在这种情况下，总比率为。当不相等时，带宽分配与成反比。Copa 速率更新规则使得具有恒定参数的发送者在稳态下等效于具有恒定参数的个发送者。

第三，我们推荐默认值。虽然我们想要低延迟，但我们也想要高吞吐量；即，我们想要最大的也能实现高吞吐量。值 1 导致队列中平均有一个数据包处于平衡状态（即，当发送方以目标平衡速率传输时）。虽然理论上是可以接受的，但抖动会导致数据包在实践中的节奏不完美，当只有单个流占据瓶颈时，会导致经常出现空队列和浪费传输时隙，这在我们的实验经历中很常见。因此，我们选择，为数据包调步提供空间。请注意，根据上述基于 M/M/1 队列建模的等式，当发送者数量较少（≤5）时，链路将未得到充分利用。但是由于发送者很少，到达队列的不是泊松，随机变化不会导致队列长度增加。因此，在队列增长之前，链路利用率接近，如 §5.1 所示。

第四，平衡点的定义与我们的更新规则一致，即当（且仅当）系统处于纳什均衡时，每个发送者的传输速率等于他们的目标速率。该分析提出了一种确定合作发送者行为的机制：每个发送者观察一个共同的延迟并计算一个共同的（如果所有发送者具有相同的）或其。那些传输速度比这个值的倒数更快的必须降低它们的速率，而那些传输速度慢的必须增加它。如果每个发端都这样做，他们都会受益。

评估

为了评估 Copa 并将其与其他拥塞控制协议进行比较，我们使用了用户空间实现和 ns-2 模拟。我们在模拟链路和真实链路上运行用户空间实现。

实现：我们比较了 Copa 的用户空间实现与 TCP Cubic、Vegas、Reno 和 BBR [5] 的 Linux 内核实现以及 Remy、PCC [6]、Vivace [7] 的用户空间实现的性能，Sprout [36] 和 Verus [38]。我们使用了开发人员对 PCC 和 Sprout 的实现。对于 Remy，我们开发了一个用户空间实现并验证其结果与 Remy 模拟器匹配。有许多可用的 RemyCC，每当我们找到适合该网络的 RemyCC 时，我们都会报告其结果。我们使用 Linux qdisc 创建模拟链接。我们的 PCC 结果是针对默认的基于损失的目标函数。Pantheon [37] 是一个独立的拥塞控制测试平台，使用基于延迟的目标函数进行 PCC。

ns-2 模拟：我们将 Copa 与作为端到端协议的 Cubic [13]、NewReno [15] 和 Vegas [4] 以及 Cubic-over-CoDel [26] 和 DCTCP [1] 进行比较，它使用网络内机制。

模拟链路上的动态行为

为了了解 Copa 在流量到达和离开时的行为方式，我们使用 Linux qdiscs 建立了一个 100 Mbit/s 的链路，具有 20 ms RTT 和 1 BDP 缓冲区。一个流在前 10 秒内每秒到达，在接下来的 10 秒内每秒有一个流离开。流在每个时隙获得的带宽的平均值±标准偏差如图 3 所示。不同时隙的 Jain 公平指数的 CDF 如图 4 所示。

图3：平均值±标准差。10 个流每秒一次进入和离开网络时的吞吐量偏差。黑线表示理想的分配。BBR、Cubic 和 PCC 的图表在每个图中与 Copa 一起显示以进行比较。Copa 和 Cubic 流紧密地遵循理想分配。

Copa 和 Cubic 都基本遵循理想的速率分配。图 4 显示 Copa 的公平指数中值最高，Cubic 紧随其后。BBR 和 PCC 对不断变化的网络条件的响应要慢得多，并且无法正确分配带宽。在网络变化较慢的实验中，BBR 和 PCC 最终成功收敛到公平分配，但这需要几十秒。

这个实验展示了 Copa 快速适应不断变化的环境的能力。Copa 的模式切换器大部分时间都正常运行，检测到在此期间没有任何缓冲区填充算法处于活动状态。在这个实验中，在 Copa 中观察到的大部分噪音和不公平是由于少数 RTT 错误地切换到了竞争模式。发生这种情况是因为当流量到达或离开时，它们会干扰 Copa 的稳态运行。因此，对于少数 RTT，队列可能永远不会为空，并且 Copa 流程可以从默认模式切换到竞争模式。在这个实验中，有几个 RTT，在此期间有几个流切换到竞争模式，并且它们的减小。但是，如果不存在竞争的缓冲区填充流，那么在此模式下，队列也会每五个 RTT 清空一次。此属性使 Copa 能够在几次 RTT 后正确恢复到默认模式。

真实世界评估

为了了解 Copa 如何通过真正的交叉流量和数据包调度程序在广域 Internet 路径上执行，我们将 Copa 的用户空间实现提交给 Pantheon。(http://pantheon.stanford.edu)（一个用来评估拥塞控制算法的系统）在我们的实验中，Pantheon 在六个国家拥有节点。它使用节点和离它最近的 AWS 服务器之间的每个拥塞控制方案创建流，并测量吞吐量和延迟。我们将这组实验分为两类，具体取决于节点如何连接到 Internet（以太网或蜂窝网络）。

为了获得数十个实验的综合性能视图，我们绘制了平均归一化吞吐量和平均排队延迟。吞吐量相对于在实验中的所有运行中获得最高吞吐量的流量进行归一化，以获得介于 0 和 1 之间的数字。Pantheon 在使用 NTP 同步时钟计算的可公开访问日志中报告每个数据包的单向延迟两个终端主机。为了避免被 NTP 固有的系统附加延迟所混淆，我们报告了排队延迟，计算为延迟与该流看到的最小延迟之间的差。每个实验持续 30 秒。其中一半有一个流。另一半在实验开始后的 0、10 和 20 秒开始有三个流。

Copa 在不同类型的网络中的表现是一致的。与大多数其他方案相比，它实现了显着降低的排队延迟，并且仅减少了少量吞吐量。Copa 的低延迟、对丢失不敏感、RTT 公平性、抗缓冲膨胀和快速收敛性可在各种网络设置中实现弹性。Vivace LTE 和 Vivace 延迟在 AWS 圣保罗和哥伦比亚的一个节点之间的链路中实现了过度延迟，有时超过 10 秒。当针对 Vivace 延迟和 LTE 移除所有大于 2000 毫秒的运行时，它们分别获得 156 毫秒和 240 毫秒的平均排队延迟，仍显着高于 Copa。使用的 Remy 方法针对 100 倍的链路速率范围进行了训练。PCC 使用其基于延迟的目标函数。

图5 Pantheon 路径的真实世界实验：在两种不同类型的 Internet 连接下，通过各种拥塞控制算法实现的平均归一化吞吐量与排队延迟。每种类型在 6 条 Internet 路径上的多次运行中进行平均。请注意两个图表中非常不同的轴范围。x 轴翻转并采用对数刻度。Copa 在这两种类型的网络中都实现了始终如一的低排队延迟和高吞吐量。请注意，专为蜂窝网络设计的 Sprout、Verus 和 Vivace LTE 等方案。在一种类型的网络中表现良好的其他方案在另一种类型的网络中表现不佳。在有线以太网路径上，Copa 的延迟比 BBR 和 Cubic 低 10 倍，平均吞吐量仅略有降低。

RTT 公平性

共享同一瓶颈链路的流通常具有不同的传播延迟。理想情况下，它们应该获得相同的吞吐量，但许多算法表现出明显的 RTT 不公平性，不利于具有较大 RTT 的流。

为了评估各种算法的 RTT 公平性，我们在 ns-2 中设置了 20 个长时间运行的流，传播延迟均匀分布在 15 毫秒到 300 毫秒之间。该链路具有 100 Mbit/s 的带宽和 1 BDP 的缓冲区（以 300 ms 延迟计算）。实验运行 100 秒。我们在图 6 中绘制了每个流获得的吞吐量。

图6 各种方案的 RTT 公平性。共享 100 Mbit/s 瓶颈链路的 20 个长期运行流的吞吐量与其各自的传播延迟。“Copa D”是默认模式下的Copa，没有模式切换。“Copa”是完整的算法。“理想”显示公平分配，与“Copa D”匹配。注意 y 轴上的对数刻度。名称以外的方案为具有大 RTT 的流分配很少的带宽。

当传播延迟如此多样化时，就会违反 Copa 的特性，即每 5 个 RTT 中队列几乎为空一次。因此 Copa 的模式切换算法错误地转移到了竞技模式，导致 Copa 模式切换（图中标记为“Copa”）继承了 AIMD 的 RTT 不友好性。然而，由于 AIMD 为，而底层延迟敏感算法稳健地抢占或放弃带宽以使分配与成比例，因此 Copa 的 RTT 不友好性比其他方案要温和得多。

我们在关闭模式切换并以默认模式（）运行后也运行 Copa，在图中表示为“Copa D”。因为发送者共享一个共同的排队延迟和一个共同的目标速率，在相同的条件下，他们将做出相同的决定来增加/降低他们的速率，但有一个时间偏移。这种方法消除了任何 RTT 偏差，如“Copa D”所示。

原则上，Cubic 具有与 RTT 无关的窗口演化，但在实践中，它表现出明显的 RTT 不公平性，因为低 RTT 的 Cubic 发送方放弃带宽的速度很慢。CoDel AQM 的存在改善了这种情况，但仍然存在严重的不公平现象。Vegas 是不公平的，因为由于队列很少排空，因此几个流的基本 RTT 估计值不正确。Copa 以外的方案几乎不为长 RTT 流分配带宽（注意对数比例），这是 Copa 解决的问题。

对丢包的鲁棒性

为了满足基于丢失的拥塞控制方案的期望，现代网络的较低层试图通过实施广泛的可靠性机制来隐藏数据包丢失。这些通常会导致链路层延迟过高且可变，就像在许多蜂窝网络中一样。损失有时也被归咎于跨大陆链路的拥塞控制方案性能不佳（我们已经通过测量证实了这一点，例如，在欧洲的 AWS 和美国的非 AWS 节点之间）。理想情况下，5% 的非拥塞丢包率应该会使吞吐量降低 5%，而不是 5 倍。由于 TCP 为了实现较大窗口就需要较小的丢失率，因此随着网络带宽的增加，丢失恢复变得更加重要。

默认模式下的 Copa 不使用丢失作为拥塞信号，丢失的数据包只会影响 Copa，因为它们占用了拥塞窗口中浪费的传输时隙。在存在高丢包率的情况下，Copa 的模式切换器将切换到默认模式，因为任何竞争的传统 TCP 都会退出。因此，Copa 应该在很大程度上对随机损失不敏感，同时仍然执行良好的拥塞控制。

为了验证这一假设，我们建立了一个带宽为 12 Mbit/s 且 RTT 为 50 ms 的仿真链路。我们改变随机丢包率并绘制各种算法获得的吞吐量。每个流程运行 60 秒。

图 7 显示了结果。Copa 和 BBR 在整个范围内对损失不敏感，验证了我们的假设。正如预测的 [22]，NewReno、Cubic 和 Vegas 的吞吐量随着丢失率的增加而下降。PCC 忽略高达 ≈5% 的损失率，因此在此之前保持吞吐量，然后由其 sigmoid 损失函数确定急剧下降。

图7 在具有 50 ms RTT 的 12 Mbit/s 链路上存在随机数据包丢失的情况下各种方案的性能。

模拟数据中心网络

为了测试 Copa 中的想法的广泛应用，我们考虑了数据中心网络，它与广域网具有完全不同的属性。许多数据中心的拥塞控制算法利用了一个实体拥有和控制整个网络这一事实，这使得整合网络内支持变得更加容易[1、3、24、29、12]。例如，DCTCP [1] 和 Timely [23] 旨在在拥塞建立之前检测和响应拥塞。当队列长度超过预设阈值时，DCTCP 使用路由器在数据包头中标记 ECN。使用延迟作为监控拥塞的细粒度信号。Copa 的相似之处在于它倾向于向目标速率移动以响应拥塞。

利用数据中心的受控环境，我们对算法进行了三个小改动：（1）传播延迟由外部提供，（2）由于不需要与 TCP 竞争，我们禁用模式切换并始终以默认模式运行并且 (3) 由于不存在网络抖动，我们使用最新的 RTT 而不是 RTTstanding，这也可以实现更快的收敛。对于计算 v，拥塞窗口仅在大于 2/3 的 ACK 导致该方向上的运动时才被认为在给定方向上发生变化。

我们模拟通过 10 Gbit/s 链路连接到 40 Gbit/s 瓶颈链路的 32 个发送方。路由器有 600 KB 的缓冲区，每个流的传播延迟为 12 µs。我们使用从数据中心 [1] 中的网络搜索工作负载中提取的流长度的开关工作负载。关闭时间呈指数分布，平均为 200 ms。我们将 Copa 与 DCTCP、Vegas 和 NewReno 进行比较。

平均流完成时间 (FCT) 相对于图 8 中的流长度绘制，y 轴显示在对数刻度上。由于其倾向于保持短队列并稳健地收敛到平衡，Copa 显着减少了短流程的流程完成时间 (FCT)。与 DCTCP 相比，对于 64 KB 以下的小流量，Copa 的 FCT 好 3 到 16 倍。对于更长的流程，好处是适度的，而且在许多情况下，其他方案在数据中心环境中的表现要好一些。这一结果表明，对于涉及短流程的数据中心网络工作负载，Copa 是一个很好的解决方案。

我们还实现了 TIMELY [23]，但它在此设置中表现不佳（平均比 Copa 差 7 倍以上），可能是因为 TIMELY 旨在为长流获得高吞吐量和低延迟。TIMELY需要设置几个参数；我们与开发人员进行了沟通并使用了他们推荐的参数，但是我们的工作量和他们的 RDMA 实验之间的差异可以解释这些差异；因为我们不确定，所以我们不会在图表中报告这些结果。

模拟卫星链路

我们使用来自 WINDS 卫星系统 [27] 的测量结果在模拟卫星链路上评估 Copa，复制 PCC 论文 [6] 中的实验。该链路具有 42 Mbit/s 容量、800 ms RTT、1 BDP 缓冲区和 0.74% 随机丢失率，我们在其上运行 2 个并发发送者 100 秒。该链路具有挑战性，因为它具有高带宽延迟积和一些随机损失。

图 9 显示了吞吐量 v。BBR、PCC、Remy、Cubic、Vegas 和 Copa 的延迟图。在这里，我们使用 RemyCC 训练了 2 个发送者的 RTT 范围为 30-280 毫秒，指数开关流量为 1 秒，每个发送者的链接速度为 33 Mbit/s，令人惊讶的是，在这种情况下效果很好，并且是在 Remy 存储库中可用的那些中表现最好的。

图9 卫星链路的吞吐量与延迟图。请注意，对丢失不太敏感的算法（包括忽略小的丢失率的 PCC）在吞吐量方面都做得很好，但对延迟敏感的算法的延迟也大大降低。注意对数刻度。

PCC 获得了高吞吐量，但代价是高延迟，因为它往往会填满缓冲区。BBR 忽略了丢失，但仍然没有充分利用链路，因为它的速率由于 BDP 高而在 0 到超过 42 Mbit/s 之间剧烈波动。这些振荡也会导致高延迟。Copa 对损失不敏感，并且由于其指数速率更新，可以扩展到大型 BDP。Cubic 和 Vegas 都对损失很敏感，因此会损失吞吐量。

与缓冲填充方案共存

一个主要的问题是当前的 TCP 算法是否会简单地压倒 Copa 中嵌入的延迟敏感性。问：（1）Copa 如何影响现有的 TCP 流？（2）Copa 流在与 TCP 竞争时是否获得了公平的带宽份额（即模式切换的工作情况如何）？

我们在几个模拟网络上进行实验。我们随机采样吞吐量在 1 到 50 Mbit/s 之间，RTT 在 2 到 100 ms 之间，缓冲区大小在 0.5 到 5 BDP 之间，并运行 1-4 个 Cubic 发送器和 1-4 个正在评估的拥塞控制算法的发送器。流同时运行 10 秒。我们报告了每个流实现的吞吐量与其理想公平份额的比率的平均值，用于测试的算法和立方。为了为 Cubic 内的变化设置基线，我们还报告了 Cubic 的数字，将一组 Cubic 流视为与另一组“不同”。

图 10 显示了结果。即使与其他 Cubic 流竞争，Cubic 也无法充分利用网络。Copa 利用这种未使用的容量来实现更大的吞吐量，而不会影响立方流。事实上，与 Copa 竞争的 Cubic 流比与其他 Cubic 流竞争时获得更高的吞吐量（在统计上微不足道）。

目前 Copa 在竞技模式中的 AIMD 为。修改它以更紧密地匹配 Cubic 的行为将有助于减少标准偏差。

PCC 获得了更高的吞吐量份额，因为其基于损失的目标函数在 5% 左右之前忽略了损失并优化了吞吐量。BBR 获得更高的吞吐量，同时显着损害了竞争的 Cubic

图10 通过绘制每个流的吞吐量与理想公平率之比的平均值和标准差来显示不同方案的吞吐量与三次方的关系。平均值是随机抽样网络的几次运行。左右条分别显示正在测试的方案和立方的值。Copa 比 BBR 和 PCC 对 Cubic 公平得多。它还使用 Cubic 不使用的带宽来获得更高的吞吐量而不损害 Cubic。

总结

我们描述了 Copa 的设计和评估，这是一种实用的基于延迟的 Internet 拥塞控制算法。这个想法是根据当前速率是低于还是高于明确定义的目标速率 1/(δdq) 来增加或减少拥塞窗口，其中是（测量的）排队延迟。我们展示了这个目标速率如何优化吞吐量和延迟的自然函数。Copa 使用一个简单的更新规则来调整目标速率方向的拥塞窗口，即使面对明显的流量流失，也能快速收敛到正确的公平速率。

这两个想法使 Copa 流能够以低排队延迟（平均每个队列中的流个数据包）保持高利用率。但是，当瓶颈与 Cubic 或 NewReno 等缓冲区填充流共享时，Copa 与其他延迟敏感方案一样，吞吐量较低。为了解决这个问题，Copa 发送器通过观察延迟演变来检测缓冲区填充器的存在，然后在参数上使用 AIMD 进行响应以与这些方案很好地竞争。

附上论文链接：http://people.csail.mit.edu/venkatar/copa.pdf

继续阅读

阅读原文