1、一、互联网概述TCP，即传输控制协议，是目前网络上使用的最多的传输协议，我们知道，整个互联网的体系结构是以 IP 协议提供的无连接的端到端的报文传输服务为基础，在这种体系结构下，那么端到端的数据传输需要自己来保证数据的可靠性，TCP 所作的就是这样的工作，它提供了端到端的数据可靠性的传输，当然，在互联网上没有 100%的可靠性保证。正是因为TCP 的贡献，所以自从提出后就成为了网络的标准传输协议。先来看下 TCP 的是如何保证数据可靠传输的，TCP 对所传输的数据都做了序号标记，序号是按照字节数来增长的，TCP 的接收方在接到数据后发出一个确认（ACK）给对端，ACK 里面包含一个序列号，这个
2、序列号 n 表示序号在 n 之前的数据已经全部收到了，现在期待序号为 n 的数据到来。我们必须要知道的一个事实就是，主机发去网络上的任何一个数据包都有可能在网络上被丢弃，由于网络中路由器处理能力限制、链路错误等原因都会导致数据包的丢弃。如果 ACK 被丢弃了的话，那么就要靠重传机制了。TCP 对发出去的数据包都保留有计时器，如果定时器到而确认还没有收到的情况下，TCP 会对刚才发送的数据包进行重传。TCP 使用确认和超时重传机制保障了数据的可靠性传输。再看流量控制方面，由于数据的发送方和接收方并不一定有相同的数据处理能力，为了避免数据发送过快而超过对方的接收能力，TCP 采用了流量控制机制，接
3、收方在 TCP 的包头里面通告了发送方自己的接收窗口，也就是还能够接收的最多的数据包，这样 TCP 就不会过度发包而超过对方的接收能力。似乎看上去 TCP 已经很完美了，它提供了端到端的数据可靠性保证，并且还考虑对端的接收能力，事实上 TCP 的最初设计也就是这么一些机制，具体可以看 RFC793 的文档。注意到这篇文档的日期为 1981 年，TCP 从此开始出现在互联网上传输数据。1986 年 10 月，一件事情的发生使得 TCP 开启了一个新领域，从美国 LBL 到 UC Berkeley 的数据吞吐量从32Kbps 下降到 40bps，具体可以参见 V. Jacobson 的论文“Con
4、gestion Avoidance and Control”，请记住这篇文章，我们后面还会多次提到它。是什么原因导致了数据吞吐量如此严重的下降呢？原来在 TCP 的控制机制里面只考虑到了接收端的接受能力，而忽略了一个很重要的方面，那就是没有考虑到网络自己的传输能力，从而造成了整个网络崩溃的发生。从这以后，TCP 的研究课题就开始多了一个方向，那就是拥塞控制，因为拥塞控制算法对保证互联网的稳定性具有十分重要的作用，其中以V. Jacobson 的那篇论文开创了互联网网拥塞控制领域的工作。二、拥塞的概述什么是拥塞？当网络中存在过多的报文时，网络的性能就会相应下降，这种现象就被成为拥塞。Copy 一
5、篇论文中的话来解释下：如上图，当负载较小时，吞吐量的增长与负载相比基本呈线性关系，延时(即第二个图的纵坐标：响应时间）增长缓慢，但是当负载超过 Knee 点后，吞吐量增长十分缓慢，但是延迟却增长较快，当负载超过 Cliff 之后，吞吐量就急剧下降，延迟相应急剧上升。Cliff 点也就是网络的最大负载，一旦超过网络的整体性能就大打折扣。而负载在 Knee 附近时网络的使用效率是最高的，此时吞吐量高，响应时间也比较快。拥塞控制的思想就是网络中的节点采取一定的措施来保证尽量使得网络的负载保持在 Knee 位置，需要避免拥塞的发生或者对拥塞的发生作出反应，使其能够再次恢复到 Knee 位置，从而保持网
6、络的整体性能最大化。与上面介绍的 TCP 的流控比较下就可以发现，流控主要是考虑接收端，不要发送过快，超过对方的接收能力，而拥塞控制则是要考虑到整个网络环境，使其负载不能超过网络的最大承受能力。显然拥塞发生的原因是因为“需求”大于了“供给”，网络中的有限资源被多用户共享使用，网络本身无法根据资源的利用情况来限制某些用户，并且随着目前互联网的发展，上网的用户和应用的数量也随之增长，这样，如果不采取某种措施来协调资源的使用，那么拥塞的发生就是必然的。一般来说，拥塞控制算法包括拥塞避免和拥塞控制两个方面，拥塞避免是一种预防机制，也就是说避免网络进入拥塞状态，尽量使得网络保持在高吞吐量和低延迟的情况下
7、。对应的拥塞控制就是恢复机制了，它使得网络一旦发生了拥塞，需要从拥塞状态中恢复出来，重新进入高吞吐量和低延迟的状态。看起来比较容易，然后事情不是想象中的那么简单。看看为什么拥塞控制是一件比较困难的事情尤其是要做到很到的拥塞控制时让网络的利用率达到最大化。首先是互联网的模型，目前互联网采用的是报文交换(packet-switched)网络，比起之前的电路交换相比，报文交换大大提高了网络的资源利用率（关于这一点，看看 IP 电话就知道为什么 IP 电话便宜了）。但是报文交换网络使得整个网络变为分布式的，在网络中间没有连接的概念，造成了每个节点所获得的信息不是很完整，而不完整的信息要完成比较好的拥塞
8、控制，那是非常困难的。其次就是网络环境是非常复杂的，互联网上各处的网络性能有很大的差异，比如说网通到电信的跨运营商网络丢包率就非常大，网络中间还有瓶颈链路，因此算法必须要有很好的适应性才行，处理报文丢失、乱序等情况。第三就是算法的性能要求，整个主要包括公平性、效率、稳定性和收敛性等各个方面。公平性主要指在带宽占用方面，不能一条连接占据了大部分带宽，而让其他的连接无法跑应用。效率指的是在带宽充足的时候要能够充分利用带宽，避免带宽的浪费。稳定性则是要能够长久的运行，而不能一段时间后就出现无法上面所说的一些性能要求。收敛性性则是要对网络的动态变化快速做出响应，从而调整整个网络重新达到平衡状态。第四点
9、需要考虑到就是算法的开销，拥塞算法必须尽量地减少附加的网络流量，尤其是在拥塞恢复的时候。这就要求各个节点间的通信要尽可能少，这个要求使得算法设计变得十分困难。同时算法还必须网络节点的计算复杂性，否则就会降低网络节点对其它数据包的处理能力。三、TCP 拥塞控制算法为了防止网络的拥塞现象，TCP 提出了一系列的拥塞控制机制。最初由 V. Jacobson 在1988 年的论文中提出的 TCP 的拥塞控制由“慢启动(Slow start)”和“拥塞避免(Congestion avoidance)”组成，后来 TCP Reno 版本中又针对性的加入了“快速重传(Fast retransmit)”、“快
10、速恢复(Fast Recovery)”算法，再后来在 TCP NewReno 中又对“快速恢复”算法进行了改进，近些年又出现了选择性应答( selective acknowledgement,SACK)算法，还有其他方面的大大小小的改进，成为网络研究的一个热点。TCP 的拥塞控制主要原理依赖于一个拥塞窗口(cwnd)来控制，在之前我们还讨论过 TCP 还有一个对端通告的接收窗口(rwnd)用于流量控制。窗口值的大小就代表能够发送出去的但还没有收到 ACK 的最大数据报文段，显然窗口越大那么数据发送的速度也就越快，但是也有越可能使得网络出现拥塞，如果窗口值为 1，那么就简化为一个停等协议，每发送
11、一个数据，都要等到对方的确认才能发送第二个数据包，显然数据传输效率低下。TCP 的拥塞控制算法就是要在这两者之间权衡，选取最好的 cwnd 值，从而使得网络吞吐量最大化且不产生拥塞。由于需要考虑拥塞控制和流量控制两个方面的内容，因此 TCP 的真正的发送窗口=min(rwnd, cwnd)。但是 rwnd 是由对端确定的，网络环境对其没有影响，所以在考虑拥塞的时候我们一般不考虑 rwnd 的值，我们暂时只讨论如何确定 cwnd 值的大小。关于 cwnd 的单位，在 TCP 中是以字节来做单位的，我们假设 TCP 每次传输都是按照 MSS 大小来发送数据的，因此你可以认为 cwnd 按照数据包个
12、数来做单位也可以理解，所以有时我们说 cwnd增加 1 也就是相当于字节数增加 1 个 MSS 大小。慢启动：最初的 TCP 在连接建立成功后会向网络中发送大量的数据包，这样很容易导致网络中路由器缓存空间耗尽，从而发生拥塞。因此新建立的连接不能够一开始就大量发送数据包，而只能根据网络情况逐步增加每次发送的数据量，以避免上述现象的发生。具体来说，当新建连接时，cwnd 初始化为 1 个最大报文段(MSS)大小，发送端开始按照拥塞窗口大小发送数据，每当有一个报文段被确认，cwnd 就增加 1 个 MSS 大小。这样 cwnd 的值就随着网络往返时间(Round Trip Time,RTT)呈指数级
13、增长，事实上，慢启动的速度一点也不慢，只是它的起点比较低一点而已。我们可以简单计算下：开始 - cwnd = 1经过 1 个 RTT 后 - cwnd = 2*1 = 2经过 2 个 RTT 后 - cwnd = 2*2= 4经过 3 个 RTT 后 - cwnd = 4*2 = 8如果带宽为 W，那么经过 RTT*log2W 时间就可以占满带宽。拥塞避免：从慢启动可以看到，cwnd 可以很快的增长上来，从而最大程度利用网络带宽资源，但是 cwnd 不能一直这样无限增长下去，一定需要某个限制。TCP 使用了一个叫慢启动门限(ssthresh)的变量，当 cwnd 超过该值后，慢启动过程结束，进
14、入拥塞避免阶段。对于大多数 TCP 实现来说，ssthresh 的值是 65536(同样以字节计算)。拥塞避免的主要思想是加法增大，也就是 cwnd 的值不再指数级往上升，开始加法增加。此时当窗口中所有的报文段都被确认时，cwnd 的大小加 1，cwnd 的值就随着 RTT 开始线性增加，这样就可以避免增长过快导致网络拥塞，慢慢的增加调整到网络的最佳值。上面讨论的两个机制都是没有检测到拥塞的情况下的行为，那么当发现拥塞了 cwnd 又该怎样去调整呢？首先来看 TCP 是如何确定网络进入了拥塞状态的，TCP 认为网络拥塞的主要依据是它重传了一个报文段。上面提到过，TCP 对每一个报文段都有一个定
15、时器，称为重传定时器(RTO)，当 RTO 超时且还没有得到数据确认，那么 TCP 就会对该报文段进行重传，当发生超时时，那么出现拥塞的可能性就很大，某个报文段可能在网络中某处丢失，并且后续的报文段也没有了消息，在这种情况下，TCP 反应比较“强烈”：1.把 ssthresh 降低为 cwnd 值的一半2.把 cwnd 重新设置为 13.重新进入慢启动过程。从整体上来讲，TCP 拥塞控制窗口变化的原则是 AIMD 原则，即加法增大、乘法减小。可以看出 TCP 的该原则可以较好地保证流之间的公平性，因为一旦出现丢包，那么立即减半退避，可以给其他新建的流留有足够的空间，从而保证整个的公平性。其实
16、TCP 还有一种情况会进行重传：那就是收到 3 个相同的 ACK。TCP 在收到乱序到达包时就会立即发送 ACK，TCP 利用 3 个相同的 ACK 来判定数据包的丢失，此时进行快速重传，快速重传做的事情有：1.把 ssthresh 设置为 cwnd 的一半2.把 cwnd 再设置为 ssthresh 的值(具体实现有些为 ssthresh+3)3.重新进入拥塞避免阶段。后来的“快速恢复”算法是在上述的“快速重传”算法后添加的，当收到 3 个重复 ACK 时，TCP 最后进入的不是拥塞避免阶段，而是快速恢复阶段。快速重传和快速恢复算法一般同时使用。快速恢复的思想是“数据包守恒”原则，即同一个时
17、刻在网络中的数据包数量是恒定的，只有当“老”数据包离开了网络后，才能向网络中发送一个“新”的数据包，如果发送方收到一个重复的 ACK，那么根据 TCP 的 ACK 机制就表明有一个数据包离开了网络，于是 cwnd 加 1。如果能够严格按照该原则那么网络中很少会发生拥塞，事实上拥塞控制的目的也就在修正违反该原则的地方。具体来说快速恢复的主要步骤是：1.当收到 3 个重复 ACK 时，把 ssthresh 设置为 cwnd 的一半，把 cwnd 设置为 ssthresh 的值加 3，然后重传丢失的报文段，加 3 的原因是因为收到 3 个重复的 ACK，表明有 3 个“老”的数据包离开了网络。 2.
18、再收到重复的 ACK 时，拥塞窗口增加 1。3.当收到新的数据包的 ACK 时，把 cwnd 设置为第一步中的 ssthresh 的值。原因是因为该ACK 确认了新的数据，说明从重复 ACK 时的数据都已收到，该恢复过程已经结束，可以回到恢复之前的状态了，也即再次进入拥塞避免状态。快速重传算法首次出现在 4.3BSD 的 Tahoe 版本，快速恢复首次出现在 4.3BSD 的 Reno 版本，也称之为 Reno 版的 TCP 拥塞控制算法。可以看出 Reno 的快速重传算法是针对一个包的重传情况的，然而在实际中，一个重传超时可能导致许多的数据包的重传，因此当多个数据包从一个数据窗口中丢失时并且
19、触发快速重传和快速恢复算法时，问题就产生了。因此 NewReno 出现了，它在 Reno 快速恢复的基础上稍加了修改，可以恢复一个窗口内多个包丢失的情况。具体来讲就是：Reno 在收到一个新的数据的 ACK 时就退出了快速恢复状态了，而 NewReno 需要收到该窗口内所有数据包的确认后才会退出快速恢复状态，从而更一步提高吞吐量。SACK 就是改变 TCP 的确认机制，最初的 TCP 只确认当前已连续收到的数据， SACK 则把乱序等信息会全部告诉对方，从而减少数据发送方重传的盲目性。比如说序号1，2，3，5，7 的数据收到了，那么普通的 ACK 只会确认序列号 4，而 SACK 会把当前的5
20、，7 已经收到的信息在 SACK 选项里面告知对端，从而提高性能，当使用 SACK 的时候，NewReno 算法可以不使用，因为 SACK 本身携带的信息就可以使得发送方有足够的信息来知道需要重传哪些包，而不需要重传哪些包。以上方面资料可以参考 V. Jacobson 的论文，RFC2001、RFC2018、RFC2581、RFC2582、RFC2883 等文献。四、TCP 拥塞控制的其他算法1994 年，Brakmo 提出了一种新的拥塞控制机制 TCP Vegas，从另外的一个角度来进行拥塞控制。从前面可以看到，TCP 的拥塞控制是基于丢包的，一旦出现丢包，于是调整拥塞窗口，然而由于丢包不一
21、定是由于网络进入了拥塞，但是由于 RTT 值与网络运行情况有比较密切的关系，于是 TCP Vegas 利用 RTT 值的改变来判断网络是否拥塞，从而调整拥塞控制窗口。如果发现 RTT 在增大，Vegas 就认为网络正在发生拥塞，于是开始减小拥塞窗口，如果 RTT 变小，Vegas 认为网络拥塞正在逐步解除，于是再次增加拥塞窗口。由于 Vegas不是利用丢包来判断网络可用带宽，而是利用 RTT 变化来判断，因而可以更精确的探测网络的可用带宽，从而效率更好。然而 Vegas 的有一个缺陷，并且可以说致命的，最终影响TCP Vegas 并没有在互联网上大规模使用。这个问题就是采用 TCP Vegas
22、 的流的带宽竞争力不及未使用 TCP Vegas 的流，这是因为网络中路由器只要缓冲了数据，就会造成 RTT 的变大，如果缓冲区没有溢出的话，并不会发生拥塞，但是由于缓存数据就会导致处理时延，从而 RTT 变大，特别是在带宽比较小的网络上，只要一开始传输数据，RTT 就会急剧增大，这个在无线网络上特别明显。在这种情况下，TCP Vegas 降低自己的拥塞窗口，但是只要没有丢包的话，从上面看到标准的 TCP 是不会降低自己的窗口的，于是两者开始不公平，再这样循环下去，TCP Vegas 的效率就非常低了。其实如果所有的 TCP 都采用 Vegas 拥塞控制方式的话，流之间的公平性会更好，竞争能力
23、并不是 Vegas 算法本身的问题。另外介绍下 Limited transmit。这个算法是在拥塞窗口比较小的时候如果在一个传输窗口内有多个包丢失时比较有效率的恢复算法。之前已经讲过，TCP 有一个快速恢复的机制，而快速恢复的前提是收到 3 个重复 ACK。然而，接收方发送重复 ACK 却又需要乱序包的到达才可以触发，TCP 在每收到一个乱序包就会立即发送一个重复的 ACK 给发送端。如果拥塞窗口比较小的时候会发生情况呢？发送方和接收方进入一段互相等待的状况，接收方等待再收到一个包于是发生重复 ACK，而发送方却等待第 3 个重复 ACK，如果窗口较小，例如为3，如果此时第一个包丢失了，接收方
24、对第二个和第三个包分别发送了重复 ACK，总共两个重复 ACK，此时发送端由于窗口的关系不能再发送数据，此时双方进入互等，直到发送方的重传超时计时器到，才能打破该僵局，显然如果是这样的话效率就明显降低，因为重传超时的时间设置为 RTT+4RTTVar，一般该值都比较大。Limited Transmit 就是为了解决这种情况的，它的方法很简单，那就是当收到两个重复 ACK时，检测两个条件：1）接收方的通告窗口 rwnd 是否允许传输新的数据包，即是否满足 rwndcwnd？2）停留在网络中的数据包个数是否小于或等于 cwnd+2？如果这两个条件都满足的话，那么 TCP 再发送新的数据包，其实第二
25、个条件换个意思理解就是说在这种情况下可以超出拥塞窗口最多再发送两个数据包。假设新的数据包和相应的ACK 不被丢失的话，那么有了这两个新的数据包，从而双方可以立即从僵局中恢复出来，发送方接着进入标准的快速恢复。注意的是尽管可以发送两个新的数据包，但是 cwnd 的值要保持不变，而不能把它增加 2。显然 Limited Transmit 算法比利用超时重传在包乱序时具有更好的鲁棒性。此外，由于一开始的 TCP 协议设计中，通常假设网络中乱序现象很少发生，但是随着Internet 乱序现象的增多(有两篇文章详细论述过：Packet Reordering is Not Pathological net
26、work Behavior、Measurement and Classification of Out-of-Sequence Packets in a Tier-1 IP Backbone)，TCP 会把乱序误认为是丢包的发生，从而降低自己的发生速率，影响了自己的性能。针对这种情况，又有了新的改进算法见此(On Making TCP More Robust to Packet Reordering)，不再详细说明。另外还有 Eifel 算法，具体参看 RFC3522、RFC4015。Eiffel 算法主要是用于 TCP 发送方更好的区分伪重传，Eifel 算法利用了 TCP 的时间戳选项。由
27、于网络拥塞控制的重要性，因而 TCP 的拥塞控制方面的研究及改进非常多，对于标准的TCP 拥塞控制，暂时先到此。首先来看高带宽和高时延网络情况，这种网络通常称之为长肥网络(Long Fat Network, LFN)，也称之为高带宽时延乘积网络(High-Bandwidth-Delay-Product Network，BDP)。带宽时延乘积(BDP)通常表示网络通道的容量，也就是能够在网络中缓冲的数据量，显然带宽增大一倍或者时延增大一倍都会使得通道的容量加倍。当这个乘积变得越来越大时，TCP 的局限性及开始暴露出来。一个 100Mbps 的网络，如果时延是 100ms，那么 BDP 为 100
28、,000,000*0.1/8=1,250,000 字节=1220.7K，如果是 1Gbps 的网络时延为 100ms，那么 BDP 为 12207K 左右，如果 TCP 跑在这种网络上，那么效率是非常低的。从 TCP 的首部中我们可以看到 TCP 利用 16 位来表示接收窗口 rwnd 大小，16 位能表示的最大值是 65535，由于 TCP 的发送窗口是取拥塞窗口 cwnd 和对端的接收窗口 rwnd 两者之间的最小值，那么显然发送窗口最大只能到 65535(以字节为单位)，显然该值与我们上述的网络 BDP 相差得太远，那么 TCP 就只能发送一阵数据然后就等待 ACK，极端下去就有点像“停
29、等协议”了。这样 TCP 就无法充分利用网络带宽，浪费带宽现象严重。窗口扩大选项：为了解决窗口过小的问题，TCP 利用起了它的选项功能，从 TCP 的头部可以看到 TCP 预留了一定的选项功能，用于扩展等用途。窗口扩大选项增加了额外的 16位来表示窗口大小，窗口的值由首部的 16 位大小和选项的 16 位值共同组成，不过不是用加法组成的，而是利用移位窗口值的幂来表示的，也就是说如果移位窗口值为 10，那么窗口的最大值就是 65535*210，这个值就比较大了，足够表示窗口的大小了。好，窗口太小的问题解决了，我们再来看窗口增长的机制存在的问题。通过前面的TCP 的拥塞控制的机制我们可以看到 TC
30、P 的增长方式是 AIMD 原则的，即加法增大，在拥塞避免阶段，每次增加 1，按照我们上面计算的网络环境 1Gbps，100ms 时延，其窗口大小到12,500,000，如果按照最理想的情况每个包大小为 1500 个字节的话，那么必须需要 8333个包大小的拥塞窗口，也就是要 8333 个 RTT 才能增长到这个值，这个时间还随着 RTT 和带宽的增大而增大，而且在增长过程中只要一出现丢包的话，那么窗口就立即减半，此时又得重新开始增长，显然该增长函数不能满足现在网络的需要。其次，传统的 TCP 总是把包的丢失解释为网络发生了拥塞，而假定链路错误造成的分组丢失是忽略不计的，这种情况是基于当时 V
31、. Jacobson 的观察，认为链路错误的几率太低从而可以忽略，然而在高速网络中，这种假设是不成立的，当数据传输速率比较高时，链路错误是不能忽略的。在无线网络中，链路的误码率更高，因此，如果笼统地认为分组丢失就是拥塞所引起的，从而降低一半的速率，这是对网络资源的极大浪费。拥塞的判断需要两个连续的分组丢失。最后就是网络的应用的多样化，音视频应用越来越多，而音视频基本上都是用 UDP 来传输数据，UDP 不提供数据可靠性的保障，同时也没有拥塞控制和流控，因此当 UDP 和 TCP在一起竞争的时候，如果造成丢包的话，此时 TCP 退避三舍，而 UDP 照样传输，显然会造成 TCP 的应用会变得奇慢，当然这个本质不是 TCP 的问题，但是给 TCP 带来了问题。针对上述问题，TCP 的拥塞控制进入了新的阶段，百花齐放，出现了很多研究热点，其中比较集中的方面有：“慢启动”过程的改进，基于速率的拥塞控制，ECN，和针对特殊网络(无线网络和卫星网络)的拥塞控制。最初提出了 HSTCP，后来又出现了 BI-TCP，CUBIC TCP、FastTCP、TCP-Westwood 等一系列的改进，UDP 的应用开始了 TCP-Friendly 的拥塞控制，出现了 TFRC，最近又有了 DCCP。
