翻译Congestion Avoidance and Control
在过去几年中，计算机网络经历了爆炸性的增长，出现了很多网络拥塞问题。例如，网关经常由于本地缓存的耗尽，出现大约10%的丢包。我们调查后发现，大部分原因是传输层协议实现的问题，而不是协议本身设计的问题。目前主流的传输层协议实现是基于窗口的，在网络出现拥塞时会出现错误的行为。本文举了一些例子，并且给出了一些算法来修正这些错误。这个算法遵循的基本原则是：Conservation of packets。我们展示了这些算法是如何从这个原理推导出来，以及如何在网络拥塞场景下起作用的。
在1986年十月，互联网出现了第一次由于网络拥塞导致的奔溃。在这期间，从LBL到UC Berkeley的带宽从 32Kbps降低到40bps。我们很困惑为什么带宽下降了1000倍，并且开始寻找其中的原因。具体来说，我们怀疑是不是4.3BSD的TCP实现存在某种错误的行为，或者说其TCP协议栈能够通过一些优化来适应各种更复杂的网络场景。上面两个问题的答案都是“是的”。
从那时起，我们在TCP协议栈添加了七个新的算法：
1. rtt方差估计
2. 重传定时器指数回退
3. 慢启动
4. 更强的收包确认策略
5. 拥塞时的动态窗口大小
6. karn的重传回退算法
7. 快速重传
经过我们的测试环境验证，发现最终能够处理互联网上的拥塞问题。
本文主要讲解了从1到5的含义。他们遵循一个基本的观点：一条TCP流必须遵循Conservation of packets原则。如果遵循了这个原则，那网络由于拥塞而奔溃将不再会发生。
那Conservation of packets到底是什么意思呢，它指，一个处于平衡状态的连接，例如正在稳定以满窗口发送数据的流，这条流被物理学家称之为Conservative：新的数据包不会被放进网络，直到有一个包离开了网络。从物理角度，可以预测具有这样特征的流能够在网络拥塞的情况下保持稳定。但是从网络的角度看来，这样依旧不能保持平衡，为什么？
下面是几个原因：
1. 一条连接无法直接进入这样的平衡状态
2. 发送方在旧的数据包还没有离开网络时就发送了新的数据包
3. 由于路径上资源的限制导致平衡无法达到
接下来的内容，主要是如何解决这几个问题
1 让连接趋于平衡：慢启动
第一个原因，出现的场景包括连接刚启动，或者网络中出现丢包，连接需要重启。从另一个角度来看Conservation属性，就是发送端通过接受端发送的ack报文作为信号，将新的数据包发送到网络。由于接受端发送的ack报文不会比它接收到的报文多，所以这个协议是可以自我调频的(进入收到越快->发的越快->收到越快的快乐循环)。
这张图代表了发送端，接受端，以及一个通过长-窄网络连接的高带宽网络。发送端刚刚生成了整个窗口大小的负载，正通过网络发送，而接收端产生的ack确认报文，正要通过网络到达发送端。垂直方向是带宽，水平方向是时间，每个阴影代表一个数据包。Pb代表路径上最窄的地方的耗时。所以当数据包到达接收端时，接收间隔应该为Pr=Pb。如果接收端发送ack的耗时一致的话，那Ar=Pr=Pb。如果Pb够大，那Pb=Ab。由此可以推导出，发送方的发送间隔为Pb，如果ack不携带数据的话，即一个数据包通过链路中最窄地方的耗时。
自调频系统自动调整带宽来适应网络延迟变化，以及具有相当广的条件范围。从800Mbps到1200bps的网络都能适应。但是它最大的问题是启动问题。数据包要能够发送出去，得收到ack报文，但是要能够收到ack报文，必须要先发送数据包，陷入了死循环啊。
为了让这个机制运转起来，我们发明了慢启动算法，来优雅的增加发送的数据包个数。尽管听上去很高端，实现起来却很简单，测试性质的代码三行就足够了。
慢启动
上图中，水平方向代表时间线，连续的时间被截断成按照单个发送-接收回合的几片。灰色的方块是数据包，白色的数字是对应的ack。当每个ack报文到达时，会产生两个发送报文：一个是由ack驱动的（收到ack代表一个发送的数据包已经离开网络，需要添加一个数据包到网络中），另外一个代表由ack导致拥塞控制窗口扩大了一个数据包。从图上很容易看出来为什么这个每次收到ack就扩大窗口的策略能够在短时间内成倍的扩大窗口。
如果有一个本地快速网络，比长窄网络快很多，由ack触发的两个数据包能够同时到达网络中的瓶颈位置。这两个数据包就会积压起来，有一个就会被放入发送等待队列中(为什么是一个因为收到ack代表有个包从网络中出去了，腾出了位置)。所以，网络中最小的队列长度要求随着拥塞窗口的大小成本增加，打开一个W的窗口需要W/2大小的队列长度。
1. 为每个连接添加一个拥塞窗口cwnd
2. 当连接开始启动发包，或者由于丢包重启了，将cwnd设置为1
3. 每收到一个新数据对应的ack，增加拥塞窗口1（后面还有其他算法来填坑）
4. 当发送时，按照接收端建议的窗口大小与cwnd中的最小值作为发送窗口
实际上，慢启动的窗口增加的并不是那么慢，需要用Rlog2W的时间， R代表RTT，W代表窗口大小。这代表即使在带宽很大，延迟很长的网络上，其性能也能够满足需求。这也代表着，一个连接，最大会以链路能够承载的两倍速度发送数据包。如果没有慢启动，像10Mbps的以太网主机通过56Kbps的网关设备时，第一跳路由器将会发现突增的8个数据包以200倍链路带宽发送。这些突增数据包通常会导致连接长时间处于失败状态，导致持续的重传。
上图追踪了一个tcp连接的启动过程(4.3BSD tcp)，两端是不同的以太网设备，通过一个230.4Kbps的IP网关，点到点连接。连接的窗口大小为16KB，网关有30个数据包的缓存空间。上图的每个点是一个512字节的数据包，x坐标是数据包的发送时间，y坐标是数据包的seq，点构成的那条直线代表链路带宽20KBps，只有35%的带宽被使用了。其余的都被重传浪费了。
与上图相同的情况下，启用了慢启动的数据。没有带宽的浪费，不过多花了2s在慢启动上。
网友评论