拥塞算法小结

公平性

公平性是在发生拥塞时各源端（或同一源端建立的不同TCP连接或UDP数据报）能公平地共享同一网络资源（如带宽、缓存等）。处于相同级别的源端应该得到相同数量的网络资源。产生公平性的根本原因在于拥塞发生必然导致数据包丢失，而数据包丢失会导致各数据流之间为争抢有限的网络资源发生竞争，争抢能力弱的数据流将受到更多损害。因此，没有拥塞，也就没有公平性问题。 TCP层上的公平性问题表现在两方面：

(1) 面向连接的TCP和无连接的UDP在拥塞发生时对拥塞指示的不同反应和处理，导致对网络资源的不公平使用问题。在拥塞发生时，有拥塞控制反应机制的TCP数据流会按拥塞控制步骤进入拥塞避免阶段，从而主动减小发送入网络的数据量。但对无连接的数据报UDP，由于没有端到端的拥塞控制机制，即使网络发出了拥塞指示（如数据包丢失、收到重复ACK等），UDP也不会像TCP那样减少向网络发送的数据量。结果遵守拥塞控制的TCP数据流得到的网络资源越来越少，没有拥塞控制的UDP则会得到越来越多的网络资源，这就导致了网络资源在各源端分配的严重不公平。

网络资源分配的不公平反过来会加重拥塞，甚至可能导致拥塞崩溃。因此如何判断在拥塞发生时各个数据流是否严格遵守TCP拥塞控制，以及如何“惩罚”不遵守拥塞控制协议的行为，成了目前研究拥塞控制的一个热点。在传输层解决拥塞控制的公平性问题的根本方法是全面使用端到端的拥塞控制机制。

(2) 一些TCP连接之间也存在公平性问题。产生问题的原因在于一些TCP在拥塞前使用了大窗口尺寸，或者它们的RTT较小，或者数据包比其他TCP大，这样它们也会多占带宽。

RTT不公平性

AIMD拥塞窗口更新策略也存在一些缺陷，和式增加策略使发送方发送数据流的拥塞窗口在一个往返时延(RTT)内增加了一个数据包的大小，因此，当不同的数据流对网络瓶颈带宽进行竞争时，具有较小RTT的TCP数据流的拥塞窗口增加速率将会快于具有大RTT的TCP数据流，从而将会占有更多的网络带宽资源。

1. Vegas

1994年，Brakmo提出了一种新的拥塞控制机制TCP Vegas，从另外的一个角度来进行拥塞控制。从前面可以看到，TCP的拥塞控制是基于丢包的，一旦出现丢包，于是调整拥塞窗口，然而由于丢包不一定是由于网络进入了拥塞，但是由于RTT值与网络运行情况有比较密切的关系，于是TCP Vegas利用RTT值的改变来判断网络是否拥塞，从而调整拥塞控制窗口。如果发现RTT在增大，Vegas就认为网络正在发生拥塞，于是开始减小拥塞窗口，如果RTT变小，Vegas认为网络拥塞正在逐步解除，于是再次增加拥塞窗口。由于Vegas不是利用丢包来判断网络可用带宽，而是利用RTT变化来判断，因而可以更精确的探测网络的可用带宽，从而效率更好。然而Vegas的有一个缺陷，并且可以说致命的，最终影响TCP Vegas并没有在互联网上大规模使用。这个问题就是采用TCP Vegas的流的带宽竞争力不及未使用TCP Vegas的流，这是因为网络中路由器

只要缓冲了数据，就会造成RTT的变大，如果缓冲区没有溢出的话，并不会发生拥塞，但是由于缓存数据就会导致处理时延，从而RTT变大，特别是在带宽比较小的网络上，只要一开始传输数据，RTT就会急剧增大，这个在无线网络上特别明显。在这种情况下，TCP Vegas降低自己的拥塞窗口，但是只要没有丢包的话，从上面看到标准的TCP是不会降低自己的窗口的，于是两者开始不公平，再这样循环下去，TCP Vegas的效率就非常低了。其实如果所有的TCP都采用Vegas拥塞控制方式的话，流之间的公平性会更好，竞争能力并不是Vegas算法本身的问题。

适用环境：很难在互联网上大规模适用（带宽竞争力低）

2. Reno

Reno是目前应用最广泛且较为成熟的算法。该算法所包含的慢启动、拥塞避免和快速重传、快速恢复机制，是现有的众多算法的基础。从Reno运行机制中很容易看出，为了维持一个动态平衡，必须周期性地产生一定量的丢失，再加上AIMD机制--减少快，增长慢，尤其是在大窗口环境下，由于一个数据报的丢失所带来的窗口缩小要花费很长的时间来恢复，这样，带宽利用率不可能很高且随着网络的链路带宽不断提升，这种弊端将越来越明显。公平性方面，根据统计数据，Reno的公平性还是得到了相当的肯定，它能够在较大的网络范围内理想地维持公平性原则。

Reno算法以其简单、有效和鲁棒性成为主流，被广泛的采用。

但是它不能有效的处理多个分组从同一个数据窗口丢失的情况。这一问题在New Reno算法中得到解决。

基于丢包反馈的协议

近几年来，随着高带宽延时网络（High Bandwidth-Delay product network）的普及，针对提高TCP带宽利用率这一点上，又涌现出许多新的基于丢包反馈的TCP协议改进，这其中包括HSTCP、STCP、BIC-TCP、CUBIC和H-TCP。 总的来说，基于丢包反馈的协议是一种被动式的拥塞控制机制，其依据网络中的丢包事件来做网络拥塞判断。即便网络中的负载很高时，只要没有产生拥塞丢包，协议就不会主动降低自己的发送速度。这种协议可以最大程度的利用网络剩余带宽，提高吞吐量。然而，由于基于丢包反馈协议在网络近饱和状态下所表现出来的侵略性，一方面大大提高了网络的带宽利用率；但另一方面，对于基于丢包反馈的拥塞控制协议来说，大大提高网络利用率同时意味着下一次拥塞丢包事件为期不远了，所以这些协议在提高网络带宽利用率的同时也间接加大了网络的丢包率，造成整个网络的抖动性加剧。

BIC-TCP、HSTCP、STCP等基于丢包反馈的协议在大大提高了自身吞吐率的同时，也严重影响了Reno流的吞吐率。基于丢包反馈的协议产生如此低劣的TCP友好性的主要原因在于这些协议算法本身的侵略性拥塞窗口管理机制，这些协议通常认为网络只要没有产生丢包就一定存在多余的带宽，从而不断提高自己的发送速率。其发送速率从时间的宏观角度上来看呈现出一种凹形的发展趋势，越接近网络带宽的峰值发送速率增长得越快。这不仅带来了大量拥塞丢包，同时也恶意吞并了网络中其它共存流的带宽资源，造成整个网络的公平性下降。