来源
：SIGCOMM 2022

论文链接
：https://dl.acm.org/doi/abs/10.1145/3544216.3544223

论文标题
：Starvation in end-to-end congestion control

内容整理
：尹文沛
目录
  • 1. 介绍
  • 2. 延迟和延迟-收敛
    • 2.1 延迟来源
    • 2.2 延迟聚合
  • 3. 网络模型
  • 4. 时延收敛算法中的饥饿问题是不可避免的
    • 4.1 示例
    • 4.2 定义
    • 4.3 饥饿理论
  • 附录 A 延迟约束算法饥饿定理的证明细节
为了克服传统的基于丢包的拥塞控制算法(CCAs)的弱点，研究人员已经开发和部署了几种基于延迟的 CCA，它们可以在延迟不增长的情况下实现带宽的高利用率(例如，Vegas、 fAST、 BBR、 PCC、 Copa 等)。当在一个固定瓶颈速率的路径上运行时，这些 CCA 算法评估收敛到一个平衡的小延迟范围。本文证明了一个令人惊讶的结果: 虽然这些 CCA 算法的设计可以实现合理的流间公平性，但是现有的基于延迟的 CCA 方法并不总是能够避免饥饿，这是一种极端形式的不公平。在由于实际因素(如 ACK 聚合和终端主机调度)导致的非拥塞网络延迟变化，超过 CCA 均衡收敛到的延迟范围两倍的路径上时，可能会发生饥饿。我们提供了 BBR、 PCC Vivace 和 Copa 链路仿真的实验证据。我们讨论了这个结果的含义，并假定为了保证没有饥饿，一个有效的延迟定界 CCA 应该设计一定数量的非拥塞抖动，并确保其平衡延迟振荡至少是这个抖动的一半。

1. 介绍

随着交互式和实时应用程序的兴起，缓冲区膨胀被广泛认为是一个重要问题，以及用户对高质量体验的期望越来越高，网络社区开发了各种基于延迟的拥塞控制算法(CCAs) ，供应用程序在互联网上使用。与 Reno/NewReno [22,24] ，Cubic [20]和 Composite [41]等 CCA 不同，延迟限制 CCA 不会不断增加其拥塞窗口(cwnd) ，直到它们经历数据包丢失或接收带有明确拥塞通知(ECN)位的确认(ACK)[14]。相反，他们使用测量的往返时间(RTT)和其他因素(例如，带宽估计值)来设置 cwnd。它们的目标是实现高利用率而不会造成延迟膨胀，并且在面对一些包丢失时也更有效率。
延迟约束 CCA 的发展始于1994年的 Vegas[6] ，其次是 FAST [44] ，但是由于这些算法在与 Reno/NewReno 等基于缓冲区的 CCA 竞争时无法获得良好的吞吐量，特别是 Cubic。然而，在过去的十年中，延迟约束的 CCA 经历了一次复苏，提出了几个克服这些问题的一些方法，包括 Sprout [46] ，Remy [45] ，BBR [8,10] ，PCC [12,13] ，Copa [3]和 Verus [48]。其中一些方案被广泛使用，最著名的是 BBR，它现在是许多流行的互联网站使用的 CCA。
在本文中，我们研究多个流如何运行一个给定的延迟限制 CCA 共享带宽。我们首先指出，许多 CCA 都有一个共同属性。在具有恒定瓶颈速率和传播延迟的理想网络路径上，它们收敛到一个较小的延迟范围，并在该范围内振荡。在均衡状态下经历的平均排队延迟范围要么是常数(无论瓶颈速率如何) ，要么是瓶颈速率的递减函数(例如，CCA 维护一定数量的排队包)。
我们证明了这个收敛性有一个重要的结果。由于大多数 CCA 试图跨越多个速率数量级，因此它们必须将大的速率范围映射到小的延迟范围。因此，即使估计的排队延迟发生很小的变化，也会导致推断的速率发生巨大的变化。这一观察结果向我们表明，除非延迟是完全可以测量的，否则带宽可能无法公平分享。
然而，我们意识到，即使是完美的延迟测量也不够，除非有一种方法可以精确测量 (congestive) 拥塞排队延迟。原因是非拥塞(即非瓶颈排队)对网络延迟的贡献在现实中很少是恒定的，而且很难与拥塞分离。由于 ACK 聚合、延迟 ACK、端主机操作系统或线程调度、token bucket filter(令牌桶过滤器)、硬件卸载时间变化等影响，数据包在与瓶颈排队无关的网络路径上经历抖动。
延迟限制 CCA 的设计者早已认识到这些问题，并使用各种技术试图区分排队和非排队(非拥塞) RTT 变化。这些包括 RTT 的平均值(Vegas，FAST，BBR)[6,8,44] ，最小值(LEDBAT，Copa)[3,38]和最大值(Verus)[48] ; 速率最大值(BBR)[8]和重复实验(PCC)[12]。然而，由于在现实世界路径上观察到的延迟模式多种多样，这个问题本质上是困难的。最近一篇关于 CCA 验证(CCAC)的论文报告说，即使在简单的情况下，许多 CCA 也会以令人惊讶的方式失败。
基于这个动机，我们致力于理解非拥塞抖动对基于延迟的 CCA 的影响，期待一定程度的不公平性，并希望将其量化为延迟抖动的函数。但是，我们的发现让我们感到惊讶: 在稳态收敛到有界延迟范围的有效延迟约束 CCA 不仅不公平，而且不能避免饥饿。我们证明了当使用相同 CCA 的两个流共享一个瓶颈链路时，如果非拥塞延迟的变化超过平衡时最大和最小排队延迟差的两倍，则存在非拥塞延迟的模式，其中一个流得到的吞吐量将减小到几乎为0。我们的定理表明，CCA 最多只能选择三个属性中的两个: 高吞吐量，收敛到一个小的和有界的延迟范围，没有饥饿。我们使用一个简单而实际的网络模型证明了这个结果，其中网络路径可以在一个小范围内以任意方式延迟任何数据包。
需要注意的是，饥饿是一种强烈的不公平形式，远远超出了 RTT 不公平的传统概念，甚至一个流的吞吐量比另一个流的吞吐量高。我们证明了不存在有限的 ，其中较快的流总是小于较慢的流的吞吐量的 s 倍。为了证明这些结果不是人为的或假设的，我们使用从证据中得到的见解来展示在 BBR、 Copa 和 PCC 中发生饥饿的经验情景。具有相同传播 RTT 的简单拓扑，其中两个流之间的吞吐量比为10:1。如果不考虑我们的链路模拟器的局限性，这个比例会更高。
这个结果对于延迟限制的 CCA 来说听起来很悲观，因此问题是我们是否注定要在延迟限制和避免饥饿之间做出选择。我们讨论如何能够通过明确 CCA 设计中的非拥塞延迟来实现两个理想的目标，确保 CCA 平衡中的延迟变化至少是沿着路径预期的非拥塞抖动的一半。如果事实并非如此，那么我们的研究结果证明饥饿是不可避免的。

2. 延迟和延迟-收敛

本节讨论延迟的来源，重点是拥塞和非拥塞延迟变化的来源之间的区别。它正式地定义了前面讨论过的延迟收敛的概念。表 1 提供了论文中使用的符号的词汇表。
表1 符号表

2.1 延迟来源

数据包所经历的 RTT 有三个组成部分:
  1. 拥塞(瓶颈)延迟。它是等待在瓶颈链路上发送的数据包所引起的排队延迟和瓶颈链路上的传输时间的总和;
  2. 最小包传播 RTT，以 表示，定义为单个数据包穿过路径的非瓶颈部分和发送方接收 ACK 所需的时间(这包括路径的光速延迟和每个非瓶颈链路上的数据包传输延迟);
  3. 非拥塞延迟。我们将其定义为抖动，这是由于网络因素(可能也是在瓶颈处)可能会暂时保存数据包或 ACK，但它们本身并不是长期的速率瓶颈。
非拥塞延迟的来源包括 ACK 聚合、延迟的 ACK、端主机或网络内调度开销、令牌桶过滤器、硬件卸载时间变化以及 MAC 和物理层的延迟。在实践中，由于链路层(例如 Wi-Fi) ACK 聚合，非拥塞延迟的范围可以从操作系统线程调度引起的几毫秒[29]到几十毫秒[18]。这些因素中的每一个都以不可预测的方式干扰 RTT。
延迟限制 CCA 寻求在瓶颈环节控制排队延迟。我们解决的问题是因为端到端的 CCA 不能(也许不能)消除两个可变源之间的歧义: 排队延迟和非拥塞延迟抖动。

2.2 延迟聚合

我们观察到，尽管它们在操作上存在许多差异，但迄今为止发展的大多数延迟约束 CCA 算法具有一个共同的特性，我们称之为延迟收敛。他们寻求收敛到一个固定的发送速率和排队延迟，再这个平衡点只有很小的振荡(如果有的话)。这种设计模式提供了两个好处。首先，稳定的发送速率为应用程序提供稳定的性能。 其次，许多方案(无论是隐式的还是显式的)将发送速率映射到相应的(推断的)队列延迟，这使得推断它们的行为变得更加容易。因此，许多端到端延迟控制 CCA 采用这种策略，包括 Vegas、 FAST、 Sprout、 BBR、 PCC Vivace、 Copa、 PCC Proteus 和 Verus。
我们定义了一个延迟收敛的 CCA，是根据一个流在一个理想的路径上运行时它的行为定义的。一个理想的路径有一个恒定的瓶颈链路速率 、最小的包传播 RTT 和一个足够大的瓶颈队列以至于永远不会溢出。当然，这样一个足够大的队列大小只存在于绑定其最大队列的 CCA 中。
定义1: 当 CCA 在给定 的理想路径上运行时，如果两个条件保持不变，则 CCA 是延迟收敛的。
(1) 在一个时间 之后，RTT 总是在一个有界区间内 ，其中 是瓶颈链路速率。定义 。 (2) 在 不接近零的情况下，和 都是有界的，即存在链路速率 ， 和 的有限界使得 和 对所有 成立。
图 1 描述了这个定义，显示了假设的 CCA 的 RTT 的时间演变。正如我们看到的，CCAs 维持一个更小的 就意味着 "更加收敛"，更容易挨饿。特别地，我们证明了当由非拥塞时延引起的时延模糊度大于 时，就会发生饥饿。对于许多 CCA 而言， 很小，因为它们努力使延迟变化小于 。因此，即使是一点点的延迟模糊也会导致饥饿。
图1 一类假设的延迟收敛 CCA 的理想路径行为。
比如说，在 Vegas, FAST 和 BBR 的 cwnd 限制模式下, 为 0。在 Copa 中， 为 ，其中 为包大小，(这个数值在 和 的情况下 < )。当 BBR 处于 pacing 模式下时为 。在 PCC Vivace 下是 。(见图3) 我们表明，所有这些协议遭受饥饿，即使在简单的双流场景和小的非拥塞抖动情况下。
图3 各种延迟限制 CCA 如何将延迟映射到发送速率。阴影区域显示每个 CCA 的 和 。该区域的宽度为 。BBR 有两种模式(如图所示)。对于 Vegas、 FAST 和 BBR (cwnd-limited) ，，因此它是一条线，而不是一个区域。对于这些 CCA，。第 5 节描述了这些映射是如何从这些算法的动态变化中产生的。由于 的传输延迟是不可避免的，所有 CCA 的延迟随着 而增加。
对于一个固定的 ，延迟收敛 CCA 将每个链路速率 映射到一个稳定的延迟范围。图 2 显示了这个范围如何随着 的变化而变化。典型的 和 是 的递减函数，因为 CCA 通常随着它们对拥塞延迟的估计的减少而增加它们的速率。
图2 一个假设的延迟收敛算法的速率延迟图。理想路径的 C 随其 的固定而变化。
图 3 显示了一些实际延迟收敛 CCA 的速率延迟图。对于所有这些 CCA， 都很小(或者与 一起变小)。

3. 网络模型

我们的分析和证明使用了下面所示的网络模型:
流共享一个单独的大型 FIFO 队列，从这个队列中以恒定的 速率出队的数据包经历一个恒定的最小数据包传播 RTT (我们假设瓶颈链路速率 是恒定的; 当它随着无线链路的变化而变化时，设计一个 CCA 只会变得更加困难。)。然后，数据包通过一个组件，该组件添加一个不确定的、有界的延迟，该延迟表示网络路径上的非拥塞延迟。该组件可以将数据包延迟 0 到 D 秒之间的任何值，而不需要重新排序数据包。由于网络路径的非瓶颈部分对于不同的流可能不同，所以这种非拥塞延迟是特定于流的。
非拥塞延迟在瓶颈处造成了排队延迟数量的模糊性。例如，当 CCA 测量 RTT 增加了 时 (通常情况下，CCA 只关心延迟的变化，因为不变的传播延迟 没有传达关于拥塞的信息)， 它只知道因为拥塞增加的延迟处于 (可能为负数) 和 之间，这种模棱两可造成发送端的困惑。如果观察到的延迟确实是由拥塞引起的，CCA 应该降低它的速率，但是如果它这样做了，并且延迟被证明是非拥塞的，它可能会低估网络的利用率。当共享链路的流估计排队延迟不同时，它们可能以不同的速率发送，这可能导致饥饿。较大的 意味着较高的模糊度，当 时，模型接近不产生模糊的理想路径。
模型中的非拥塞延迟具有非确定性但又不是随机的，这一点很重要。这种模型确保了标准的过滤技术不能总是区分排队和非拥塞延迟。这种模型选择的动机是观察到，虽然许多 CCA 尝试各种各样的过滤，他们仍然会在某些路径上失败。 例如，平均 RTT 的方法[6,13,38]只有当非拥塞延迟是随机的，平均值为 0 时才起作用。这通常不是这种情况; 因为网络成分添加正延迟，平均值通常是正的。使用延迟的最小值[3,38]和速率的最大值[8]也被尝试过，但已被证明是无效的[2]。尽管我们不能排除存在一个精确识别非拥塞延迟的复杂统计(也许使用机器学习) ，但是由于在现实世界路径上观察到的延迟模式多种多样，这个问题本质上是困难的。因此，我们认为 CCA 应该针对我们的模型进行压力测试，以获得稳健性。
我们的模型将 CCAC 模型[2]扩展到多个流(在单流的情况下，CCAC 论文表明它包含了我们模型的所有网络行为。)，但是比较弱; 例如，我们不对令牌桶过滤器建模，而 CCAC 的模型对令牌通过滤器1进行了建模。由于我们的模型更弱，我们的定理更强; 任何适用于我们的模型的不可能结果也适用于 CCAC 模型。

4. 时延收敛算法中的饥饿问题是不可避免的

我们的主要结果是，如果由 CCA 引起的平衡延迟幅度 小于网络路径测量模糊度的一半, D, 那么就存在一些条件，在这些条件下，一个有效的 CCA 不能同时约束延迟和避免饥饿。本节描述证明这一结果所涉及的关键思想和步骤。在提供正式的声明和证明之前，我们首先介绍一个振奋人心的示例和定义。

4.1 示例

在正式公式化我们的结果之前，我们描述了一个例子，这个例子展示了非拥塞延迟时如何导致饥饿的。考虑一个 CCA 算法(比如说 Vegas 或者 FAST) 尝试在收敛时维持每个流的排队队列长度为 个包。 是算法设定的参数。(比如说)。在一个理想路径上，一旦 CCA 实现了这一目标，它的速率就稳定下来且队列长度不会再改变。因此 , 如图 3 所示。
问题是，为了达到这种均衡，CCA 必须对排队延迟进行高精度的测量。比如说，当 且包大小为 时， 时 ，而 时 。 因此，估计的排队延迟只有0.45 ms 的差异就可以导致 CCA 的发送速率改变10倍！因此，当时延测量模糊度超过这个值时，很容易造成严重的不公平性。而在 Wi-Fi [18]和蜂窝[47]链路上会发生数十毫秒的延迟抖动。
这个问题不限于 Vegas 或 FAST，甚至不限于如图 2 所示的速率-延迟递减函数的 CCA。任何延迟收敛的 CCA 如果试图将延迟变化限制在网络抖动(延迟模糊)的水平之下，都会遇到同样的问题。最根本的问题是，非常不同的链路速率但却具有相似的延迟测量。当不同的数据流经历不同的非拥塞延迟时，它们可以推断出非常不同的链接速率，从而导致不公平，正如我们所展示的，饥饿。

4.2 定义

我们假设网络中的所有流在时间 时开始。我们将流在时间 t 的吞吐量定义为在时间 到 之间被确认的字节数除以 。我们感兴趣的是饥饿，一种极端形式的不公平。我们提出以下定义。
定义2：考虑从任意初始条件开始的两个流 和 (其中一个流动可能已经运行了很长时间，而另一个才刚刚开始)。如果总是存在一个有限的时间 ，使得在所有超过 的时间内，较快的流量与较慢的流所达到的吞吐量比小于 ，就称网络是 的。
定义3：饥饿就是说，没有一个有限的 使得网络满足 。
这个定义允许在不造成饥饿的情况下存在大规模的不公平。例如，如果在稳定状态下，两个流的吞吐量比为100万比1，我们仍然可以说没有饥饿。我们的分析询问是否有任何有限的比率是可以实现的，并证明了这对延迟约束 CCA 是不可能的。
为了证明饥饿的发生，我们需要证明存在开始状态和网络行为，在这些状态和行为之后，无论流运行多长时间，它们都不会改善带宽分配。这是令人惊讶的，因为我们预计我们的 CCA 最终会收敛到一个良好的分配，无论最初的分配如何。流以不平等的分配开始，例如，当一个流接着另一个流开始时。我们还通过实验表明，对于 Copa，BBR 和 PCC，即使在同一时间流动也很容易造成饥饿。
有人可能会认为，这种饥饿主张要求 CCA 以高效率运行; 例如，可能对100% 利用率的关注会导致攻击性行为导致饥饿。我们发现我们的结果适用于那些总是利用至少一些常数比例链路容量的 CCA，这些部分可能非常小(比如1%) ，而且远远不是极端的效率。我们只需要消除“愚蠢的”CCA，比如 “set cwnd = 10 always”，它可以避免饥饿，但是效率低下且不切实际，以及应用程序限制的流。
定义4：一个 CCA 算法是 。当运行在具有瓶颈链路速率 和最小 RTT 的理想路径上时，最终获得至少 的吞吐量; 对于任何 ，都存在 ，使得从 到 的周期内传递的字节数至少为 。
我们这样定义 是因为我们需要对所有的延迟收敛 CCA，甚至是荒谬的 CCA 进行描述。例如，我们可以设计一个当 时不存在吞吐量限制的 CCA。实际的 CCA 通常表现得更好。我们相信这个定义充分地捕获了稳态吞吐量，因为吞吐量必须至少是 无限多次。

4.3 饥饿理论

下面的定理证明了我们关于延迟约束 CCA 的饥饿必然性的结果。
定理1：对于任何确定性的，，延迟约束的 CCA ，任何传播延迟 ，任何吞吐量比率 ，以及任何 ，存在一个具有两个流的网络场景(通过两个流的初始状态和非拥塞延迟的轨迹指定), 使得一个流得到吞吐量 ，另一个流得到吞吐量 。
证明的大纲如下。附录 A 填写了我们在这里省略的数学细节。
步骤1：回想一下，有界 有一个对应的 ; 即对任意 都有 和 。我们确定了两个瓶颈链接速率 ，使得 远大于 (至少大于因子 ) ，但是当 CCA 分别在这两个速率的链接上独立运行时，在两个相互接近的范围内延迟收敛。
在这里，“close” 意味着在速率 和 收敛到的延迟范围落在一个大小为 的区间内。我们将证明对于任意 ，对于一个延迟收敛的 CCA，我们总能找到这样一个 和 (我们将在后面选择 )。
我们的主张来自于图4所示的一个鸽巢原理论点。回想一下，任何链路速率 的延迟必须落在区间 中。现在只有有限个大小为 的非重叠区间可以适用于(最多为 )。但是考虑一下，例如，链路速率的无限序列，定义为。对任意 而言，对任意 ，有 . 由于这是一个无限的链路速率序列，我们可以找到一对 。使得 和 在差异为 的同一区间内，即 。令 且 。
图4 证明中使用的鸽巢原理论证
结论之所以如此，是因为任何链路速率的延迟范围最多只有 。
步骤2：考虑发送速率和延迟的轨迹时，将使用 CCA 的流分别独立运行在链路速率为 和 的理想路径上。回想一下，一个理想的路径有零非拥塞延迟。图 5 显示了一个假设的延迟约束算法的示例，该算法在两种情况下在 time 和 之后收敛。CCA 在两个链路上收敛到相似但不同的延迟范围。然而，在这两种情况下，它会收敛到非常不同的发送速率。设 和 分别表示在容量 和 的链路上实现的长期吞吐量。显然 ，由于 CCA 是 的，所以有 。因此，实际上我们使用了 ，即 。
图5 一类假设的延迟收敛 CCA 的收敛轨迹
步骤3：简而言之，到目前为止，我们已经确定了两个链路速率 ，，使得 CCA 收敛到相似范围内的延迟，但其发送速率在这些链路上相距甚远。在最后一步，我们在速率为 和传播延迟为 的共享链路上构建了一个双流场景，这样两个流遵循的轨迹与我们在步骤 2 中设计的完全相同。因此，在这个场景中，两个流收敛到满足饥饿标准的吞吐量 和 : 。我们的初始观察结果是，对于一个确定的 CCA，在任何时候的发送速率是时间 观察到的延迟和算法的初始状态的函数。因此，如果我们能够在双流场景中设置非拥塞延迟，使得每个流观察到与步骤 2 中的一个延迟轨迹相同的总延迟，那么两个流的发送速率也将遵循步骤 2 中的速率轨迹。我们将控制流程中的非拥塞延迟来实现特定的延迟轨迹称为模拟延迟轨迹。问题是，我们是否可以模拟第2步的延迟轨迹，在双流场景中，将每个流的路径加上多达 D 秒的非拥塞延迟？
为了完成双流场景的构造，我们必须指定两个流的 CCA 初始状态，共享链路的队列的初始状态，以及两个流在任何时候的非拥塞延迟的轨迹。设 和 为延迟轨迹， 和 分别为步骤 2 中链路 和 获得的速率轨迹。假设流在时间 和 收敛到它们的最终延迟范围，如图 5 所示。定义 作为延迟和速率轨迹的时移版本，使时间起点设置为收敛时间。这些轨迹对应于图 5 中显示的粗体部分。
我们将两个流的内部状态初始化为步骤 2 中相应流的状态，时间为 和 。我们现在的目标是通过适当地选择两个流的非拥塞延迟来模拟所有 的延迟 和 。设 和 分别为流量 1 和流量 2 的非拥塞延迟，为双流场景中的传播延迟 和排队延迟之和。(在 2-flow 场景中，我们对所有信号都使用上标*。)请注意， 对于这两个流是共同的。为了实现仿真，我们需要确保: 对于所有 ，和 。
我们控制了 和 ，那 是什么呢？为了掌握 ，让我们暂时假设我们的延迟仿真是成功的，并且这两个流精确地以 和 的速率发送。然后，我们可以精确地计算双流场景中的排队延迟: 它只是一个队列的延迟，其净到达速率为 ，净流失速率为 。在证明中(详见附录 A) ，我们使用这一观察结果来表明 是由以下方面给出的:
前面这一项时时变的，后面一项是个常数。 (i) 一个时变部分，是步骤 2 中延迟轨迹 和 的加权平均数; (ii) 一个时变部分，是第二步中延迟轨迹 和 的加权平均数; 一个常量部分，取决于在双流场景中选择的初始排队延迟。这个初始延迟是 ，我们可以将它设置为任何 的值。 在证明中，我们选择这个值来得到上面关于 的表达式。
为了使延迟仿真成功，我们必须要满足 对于某些 ，对于所有 且 成立。只有当 满足两个性质时，才能做到这一点：
  1. 。 必须是 和 的下界，这保证了非拥塞延迟是非负的。
  2. 。 必须是 和 \bar{d_2(t)} 的一个上界。这保证了非拥塞延迟 。
证明的最后一步表明，上面定义的 满足这两个性质。我们将细节推迟到附录 A，但是这个方法有效的原因是 和 的延迟值从来不会离对方太远，因此从来不会离 太远。图 6 显示了在我们的运行示例中， 相对于 和 的位置。
图6 在例子中， 相对于 和 的位置。

附录 A 延迟约束算法饥饿定理的证明细节

我们现在将填写第4节中讨论的证明细节。
定理1：对于任何确定性的，，延迟约束的 CCA ，任何传播延迟 ，任何吞吐量比率 ，以及任何 ，存在一个具有两个流的网络场景(通过两个流的初始状态和非拥塞延迟的轨迹指定), 使得一个流得到吞吐量 ，另一个流得到吞吐量 。
证明的第一步和第二步在第 4 节中都是完整的。现在来补充步骤3证明的细节。回想一下在步骤 2 中，我们创建了两个不同的理想链接，在这两个链接中，单独运行的流获得的吞吐量满足 。关键在于，流经历的延迟都在一定的大小范围内。现在，我们将在我们模型中提到的 FIFO 队列上运行这两个流。我们将选择两个流的起始状态，使它们在收敛后与这两个流分别单独运行在理想路径上收敛状态相同，即它们分别在 和 时的状态。接下来，我们选择初始队列长度，并改变每个流的非确定性延迟，以便它们所经历的延迟与它们在单个流情况下所经历的延迟相同。由于 CCA 是确定性的，他们的发送率将是相同的。我们仍需证明，我们确实能够再现同样的延迟。
令。根据 与 的比较结果，有两种情况。
情况1：。在这种情况下，我们将在具有传播延迟 和瓶颈链接速率 的公共链接上运行这两个流。当流 本身在理想路径上运行时，它所经历的延迟的导数是 。这是因为 且队列永远不为空。让我们计算当来自两个流的数据包以 和 的速率到达时，在容量为 的链路上的队列延迟。设 是组合双流网络中经历的延迟，如果 ，我们有:
因此 是 和 的加权平均数，分别具有 和 的权重。因为我们可以设置初始条件，所以我们设置初始队列长度:
因为在这种情况下，我们假设 ，所以减去 ， 仍然大于 。上述等式继续适用于所有 ，因为 仍然满足对 t 求导的(3)。因此:
推导出上面的表达式后，我们已经完成了第4节中未完成的任务之一。我们在第4节中推迟的另一项任务是证明我们总是能够模拟出目标延迟状态。为此，我们证明
上述两项等价于：
对 。注意 和 都在给定 的 的公共区间内。因此它们的加权平均数也落在这个区间内，。它们都位于这个区间意味着 三个量(,, )中的任意两个之间的差距是 。即：
这样第一项就证明好了。此外， (注意，)。原因如下图所示:
这也很好理解 和 处在 的区间内，再加一个 自然大于等于
因此，我们可以模拟一个双流网络，达到每个流分别在带宽不同的理想链路上的状态。因此，饥饿将随之而来。
情况2：。这是一种简单的情况。既然两个延迟都在大小为 的区间内，所以有 。这意味着如果两个流瓶颈中的队列延迟总是 0，那么单独的非确定性延迟元素就可以模拟这两个延迟。因此，我们简单地选择一个链路速率，其大小足以使得对 ，。
注意，在这种情况下，我们可以证明比饥饿定理更强的结论; 在我们的网络模型中，CCA 甚至不具有 (尽管对于非拥塞延迟为零的理想路径它是 )。我们可以有一个非常大的链路率，完全仿真 使用非拥塞延迟和诱导 CCA 传输速率 。由于链路速率可以任意大，这会导致任意糟糕的利用率不足。这就是定理 2 的内容。
继续阅读
阅读原文