网络传输问题本质上是对网络资源的共享和复用问题，因此拥塞控制是网络工程领域的核心问题之一，并且随着互联网和数据中心流量的爆炸式增长，相关算法和机制出现了很多创新，本系列是免费电子书《TCP Congestion Control: A Systems Approach》的中文版，完整介绍了拥塞控制的概念、原理、算法和实现方式。原文: TCP Congestion Control: A Systems Approach
第 3 章 设计空间
有了 TCP/IP 的架构基础，就可以准备探索解决拥塞的设计空间了。但要做到这一点，首先需要退一步考虑一些更宏观的问题。互联网是计算、存储和通信资源的复杂组合，数百万用户共享这些资源，主要问题在于如何将这些资源(特别是交换容量、缓冲区空间和链路带宽)分配给端到端数据流。
由于互联网最初采用了尽力而为服务模式，用户(或者更准确的说，为用户服务的 TCP)可以自由向网络发送尽可能多的数据包，因此互联网最终也必然会面临公地悲剧(tragedy of the commons) 。随着用户开始体验到拥塞崩溃，自然反应是试图加上更多控制。因此，术语拥塞控制(congestion control) 可以被视为一种分配资源的隐式机制。当控制机制发现资源变得稀缺时，就会做出反应，努力缓解拥堵。
在网络服务模型中，一种明显的替代方案是将资源显式的分配给数据流。例如，应用程序可以在发送流量之前显式请求资源。IP 的尽力而为假设意味着，当拥塞成为严重问题时，这种方法并不能够立即奏效。随后的工作是将更明确的资源分配机制用来改造互联网的尽力而为模型，包括提供 QoS 保证的能力。通过这种角度思考应对互联网拥堵的方式很有好处。本书的第一部分探讨了构成控制机制基础的一系列设计决策，然后我们定义了定量评估和比较不同拥塞控制机制的标准。
3.1 实现选择
我们首先介绍拥塞控制机制面临的四种实现选择，以及 TCP/IP 决策背后的设计原理。考虑到所处环境，有些决定是"显而易见的"，但因为互联网的持续发展造成的环境变化，我们需要谨慎考虑所有这些决定。
3.1.1 集中式和分布式
原则上，第一个设计决策是网络的资源分配是集中式还是分布式的。在实践中，互联网的规模以及所连接的组织的自主权，决定了应该采取分布式方法。事实上正如 Dave Clark 所阐述的那样，分布式资源管理是互联网设计的明确目标，但承认这一默认决定之所以重要，有两个原因。
延伸阅读:
D. Clark, The Design Philosophy of the DARPA Internet Protocols. ACM SIGCOMM, 1988.
首先，虽然互联网控制拥塞的方法是分布在数百万主机和路由器上的，但可以认为它们将合作尝试实现全局最优解决方案的。从这个角度来看，存在一个共享的目标函数，所有组件都实现某个分布式算法来优化该函数。本书所描述的各种机制只是简单定义了不同的目标函数，其中一个长久的挑战是，当部署了多种机制时，如何协调目标函数之间的竞争。
其次，虽然集中式方法对整个互联网来说并不实用，但可以适用于有限的领域。例如，逻辑上集中的控制器可以收集有关网络链路和交换机状态信息，计算全局最优资源分配，然后建议(甚至监督)终端主机所提供的可用容量。这种方法当然会受到集中式控制器响应网络变化的时间尺度的限制，但当前已经成功应用于 B4 和 SWAN 等流量工程机制做出的粗粒度分配决策。现在还没有办法明确的在粗粒度的流量工程决策和细粒度的拥塞控制决策之间划一条线，但最好对所有可能的选择保持开放的心态。
延伸阅读:
S. Jain, et al. B4: Experience with a Globally-Deployed Software Defined WAN. ACM SIGCOMM, August 2013.
集中式控制在数据中心也得到了有效应用，这对于拥塞控制来说是一个有趣的环境。首先，数据中心的 RTT 非常低(不考虑进出数据中心的流，只考虑数据中心服务器之间的通信)。其次，很多情况下数据中心可以被视为一个新领域，这提高了尝试新方法的可能性，这些新方法不必与现有算法平等共存。由麻省理工学院和 Facebook 研究人员合作开发的 Fastpass 就是这种集中式方式的很好的例子。
延伸阅读:
J. Perry, et al. Fastpass: A Centralized “Zero-Queue” Datacenter Network. ACM SIGCOMM, August 2014.
3.1.2 以路由器为中心还是以主机为中心(Router-Centric versus Host-Centric)
给定某个分布式资源分配方法，下一个问题是，应该在网络内部(即在路由器或交换机上)实现该机制，还是在网络边缘(即在主机中作为传输协议的一部分)实现该机制。这不是严格意义上的非此即彼的情况，实践中这两个地方都需要涉及，真正的问题是哪个组件需要承担主要责任。路由器总是负责决定哪些包要转发，哪些包要丢弃。但是，在路由器介入终端主机的决策并学习如何做出决定时，其介入的程度有很多不同的选项。
在这些选项的一端，路由器允许为主机预留容量，确保每个流的数据包得到相应的传递。路由器可以利用类似公平队列这样的机制实现某个信令协议，仅在有足够容量时接受新的流，并监督主机确保创建的流不超过资源预留范围。这就是基于预留的 QoS 保证机制，具体细节超出了本书范围。
另一端是以主机为中心的方法。路由器对可用容量不做任何保证，也不提供任何明确的反馈(当缓冲区满时，会默默的将包丢弃)，而观察网络状况(例如，有多少包成功通过了网络)并相应调整其行为是主机的责任。
在两个极端的中间，路由器可以采取更主动的行动来协助终端主机完成工作，但不是通过预留缓冲区空间的方式，而是需要路由器在缓冲区满时向终端主机发送反馈。我们将在第 6 章介绍某些形式的主动队列管理(AQM, Active Queue Management) ，但在接下来的两章中介绍的以主机为中心的机制假设路由器在缓冲区满时只是静默丢包。
过去，在传输层实现了以主机为中心的方法，通常是 TCP 或其他一些模仿 TCP 算法的传输协议，比如 DCCP(数据报拥塞控制协议, datagram congestion control protocol)或 QUIC(一种相对较新的为基于 HTTP 的应用程序设计的传输协议)。然而，也可以在应用程序本身实现拥塞控制。DASH(基于 HTTP 的动态自适应流, Dynamic Adaptive Streaming over HTTP) 就是一个例子，尽管严格来说应该被视为传输层(因为运行在 TCP 上)和应用层拥塞控制的组合。根据测量到的网络性能，向客户端传输视频的服务器在一系列不同的视频编码之间切换，从而改变向 HTTP 流发送数据的速率。实际上，TCP 试图为流找到一个可持续的带宽，然后应用程序调整其发送速率，以充分利用该带宽，避免发送超过当前网络条件下所能支持的数据。拥塞控制的主要责任落在 TCP 上，但应用程序的目标是保持流水线满，同时保证良好的用户体验。
3.1.3 基于窗口 vs 基于速率(Window-Based versus Rate-Based)
确定了以主机为中心的方法之后，下一个实现选择是基于窗口的机制还是基于速率的机制。TCP 使用基于窗口的机制来实现流量控制，因此 TCP 拥塞控制的设计决策似乎显而易见。事实上，在第四章中介绍的拥塞控制机制是围绕计算拥塞窗口(congestion window) 的算法展开的，其中发送方被较小的流量控制窗口或计算拥塞控制窗口所限制。
但也可以计算出网络能够支持的数据包传输速率，并相应调整传输速度。观察到的速率只是在一段时间内(例如测量的 RTT)交付的字节数。我们指出速率和窗口之间的这种二元性，是因为基于速率的方法更适合以某种平均速率生成数据的多媒体应用，而且至少需要某种最小吞吐量才能发挥作用。例如，某个视频编解码器可以生成平均速率为 1 Mbps 的视频，峰值速率为 2 Mbps。
在支持不同 QoS 级别的基于预留的系统中，基于速率的方法是合理选择，但即使在像互联网这样的尽力而为网络中，也可以实现某种自适应的基于速率的拥塞控制机制，可以在应用程序需要调整传输速率时(例如通过调整其编解码器)通知应用程序。这是 TCP 友好速率控制(TFRC, TCP-friendly rate control)的核心思想，它将 TCP 避免拥塞的概念扩展到更自然的以特定速率(例如，视频编解码器在给定质量水平上产生的比特率)发送数据包的应用程序。TFRC 通常与 RTP 一起使用，RTP 是一种为实时应用设计的传输协议，我们将在第 7 章中看到这种机制的例子。
最后，TCP 拥塞控制的最新进展之一是 BBR(瓶颈带宽和 RTT, Bottleneck Bandwidth and RTT)，它结合使用了基于窗口和基于速率的控制，从而尽量限制网络队列的堆积。我们将在第 5 章详细介绍这种方法。
3.1.4 基于控制 vs 基于回避(Control-based versus Avoidance-based)
我们要注意，最后的实现选择可能有些微妙。终端主机面临的挑战是，根据反馈和观察，计算网络中有多少可用容量，并相应调整其发送速率。有两种实现此目的的通用策略: 一种是积极的方法，故意以某个会产生丢包的速率发包，然后对其进行响应；另一种是保守的方法，尝试检测队列开始出现堆积的时间点，并在溢出之前降低速率。我们将第一种类型的机制称为基于控制(control-based) 的机制，第二种类型的机制称为基于回避(avoidance-based) 的机制。
延伸阅读:
R. Jain and K. K. Ramakrishnan. Congestion Avoidance in Computer Networks with a Connectionless Network Layer: Concepts, Goals and Methodology. Computer Networking Symposium, April 1988.
Raj Jain 和 K.K. Ramakrishnan Jain 在 1988 年首次提出了这种区分，但经常被忽略，而人们通常只有"拥塞控制"这个术语来指代这两种方式。但我们认为这两者的区别非常重要，因此在适当的时候我们就会指出这一不同之处。不过，如果两者的区别对讨论不是很重要的话，我们还是只用"拥塞控制"这一个术语。
还需要注意，我们称为"基于控制"和"基于回避"的方法有时分别被称为基于丢包(loss-based) 和基于延迟(delay-based) 的方法，这是因为两者对拥塞窗口进行调整的信号不一样，前者在检测到丢包时调整窗口，后者在检测到延迟梯度变化时调整窗口。从这个角度来看，在接下来的四章中介绍的每一种算法都以某种方式有效改进了这些信号的保真度。
3.2 评估标准
在确定构建拥塞控制机制所需的设计决策集之后，下一个问题是，如何判断给定解决方案是好是坏。回想一下，第一章中我们提出了网络如何有效(effectively) 、公平(fairly) 分配其资源的问题，这表明至少有两种广泛的指标可以用来评估资源分配方案，接下来我们依次考虑。
3.2.1 有效性(Effectiveness)
考虑吞吐量和延迟这两个网络的主要指标是评估拥塞控制机制有效性的很好的起点。显然，我们想要尽可能高的吞吐量和尽可能低的延迟，但不幸的是，这两个目标可能彼此冲突。增加吞吐量的方法是允许尽可能多的数据包进入网络，从而将所有链路的利用率提高到 100%。这样做是为了避免链路空闲从而影响吞吐量。这一策略的问题在于，增加网络中包的数量也会增加每个路由器上队列的长度，从而意味着数据包在网络中的延迟会增加，更糟的是，多余的包有可能会被丢弃。在网络中丢弃数据包不仅会影响延迟，而且会损害吞吐量，因为上游链路带宽被浪费在了一个无法成功发送到目的地的数据包上<sup>[1]</sup>。
[1] 我们有时使用术语 goodput 而不是吞吐量来强调我们关心的是通过网络成功发送到接收方的数据，而不仅仅是发送方发送的数据。
吞吐量与延迟的比率是评估资源分配方案有效性的通用指标。这个比率有时被称为系统指数(power):
Power=Throughput/Delay
我们的目标是最大化这个比率，这个函数表示我们的系统可以支持多少负载，而负载由资源分配机制设置。图 11 给出了典型的指数曲线，理想情况下，资源分配机制将在曲线的峰值处运行。峰值左边，机制过于保守，也就是说，不允许发送足够多的数据包来保持链路繁忙。峰值右边，过多的包进入网络，要么(a)由于排队导致延迟增加(分母)，要么(b)由于丢包造成吞吐量(分子)实际上开始下降。
图 11. 作为负载的函数的吞吐量与延迟比。
此外，我们需要关注的是，即使系统在沉重的负载下运行(图 11 中曲线的右端)，会发生什么情况。我们希望避免系统吞吐量接近于零的情况，目标是使机制保持稳定，即使在网络负载过重时，数据包也能继续通过网络。如果某个机制在过载情况下不稳定，网络就会发生拥塞崩溃(congestion collapse) 。
注意，虽然"持久队列"和"拥塞崩溃"都需要避免，但对于网络遭受这两种情况的阈值没有精确的定义。它们都是关于算法行为的主观判断，总之，延迟和吞吐量是两个重要的性能指标。
3.2.2 公平性(Fairness)
网络资源的有效利用并不是判断资源分配方案的唯一标准，我们还必须考虑公平性问题。然而，当我们试图定义什么是公平的资源分配时，很快就会陷入了混乱。例如，基于预留的资源分配方案提供了一种显式的方法来创建受控的不公平，在这种方案中，我们可以通过预留使视频流通过某些链接接收 1 Mbps 的数据，而同一链接上的文件传输流只能接收 10 Kbps 的数据。
另一方面，在没有明确信息的情况下，如果几个流共享某个特定链路，我们希望每个流都能使用相同份额的带宽。这个定义假定公平的带宽份额意味着平等使用带宽。但是，即使没有预留，平等也不一定等于公平。我们是否也应该考虑路径的长度？例如图 12 所示，当一个四跳流与三个单跳流竞争时，什么才是公平？
图 12. 一个四跳流与三个一跳流竞争。
假设最公平的情况是所有流都使用相同的带宽，网络研究员 Raj Jain 提出了一个可以用来量化拥塞控制机制公平性的度量指标。Jain 公平指数的定义如下:
给定一组流吞吐量
(x1,x2,…,xn)
(以 bps 为单位衡量)，下面的函数为流分配一个公平索引:
f(x1,x2,…,xn)=n∑i=1nxi2(∑i=1nxi)2
公平指数的结果总是在 0 到 1 之间，其中 1 表示最大的公平。下面我们尝试理解一下这个指标背后的含义。考虑所有 n 个流每秒接收 1 个数据单位的吞吐量的情况，可以看到，本例中的公平指数为
n×nn2=1
假设一个流接收的吞吐量为1+Δ，现在公平指数为
n(n−1+(1+Δ)2)((n−1)+1+Δ)2=n2+2nΔ+nΔ2n2+2nΔ+Δ2
注意，分母比分子大(n−1)Δ2，因此，无论奇数流的流量比其他所有流的流量多还是少(多或少Δ单位)，公平指数现在都降到了 1 以下。另一种需要考虑的简单情况是，n 个流中只有 k 个流量的吞吐量相等，其余 n-k 个用户的吞吐量为零，在这种情况下公平指数下降到 k/n。
延伸阅读:
R. Jain, D. Chiu, and W. Hawe. A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer Systems. DEC Research Report TR-301, 1984.
下一节我们将重新讨论适用于新拥塞控制算法的公平概念，正如上面所提到的，它并不像最初看起来那样明确。
TCP 友好速率控制(TFRC)也使用了公平的概念。TFRC 使用 TCP 吞吐量方程(在第 1.3 节中讨论)来估计由实现 TCP 拥塞控制方案的流所获得的拥塞链路带宽份额，并将其设置为应用程序发送数据的目标速率。然后应用程序可以做出决定，帮助它达到目标速率。例如，视频流应用程序可能会在一组不同的编码质量级别中进行选择，以尝试在由 TFRC 确定的"公平"级别上保持平均速率。
