《网络拥塞控制》由会员分享，可在线阅读，更多相关《网络拥塞控制（14页珍藏版）》请在金锄头文库上搜索。
1、一、互联网概述TCP，即传输控制协议，是目前网络上使用的最多的传输协议，我们知道，整个互联网 的体系结构是以IP协议提供的无连接的端到端的报文传输服务为基础，在这种体系结构下， 那么端到端的数据传输需要自己来保证数据的可靠性，TCP所作的就是这样的工作，它提供 了端到端的数据可靠性的传输，当然，在互联网上没有100%的可靠性保证。正是因为TCP 的贡献，所以自从提出后就成为了网络的标准传输协议。先来看下TCP的是如何保证数据可靠传输的，TCP对所传输的数据都做了序号标记，序 号是按照字节数来增长的，TCP的接收方在接到数据后发出一个确认（ACK）给对端，ACK 里面包含一个序列号，这个序列号n
2、表示序号在n之前的数据已经全部收到了，现在期待序 号为n的数据到来。我们必须要知道的一个事实就是，主机发去网络上的任何一个数据包都 有可能在网络上被丢弃，由于网络中路由器处理能力限制、链路错误等原因都会导致数据包 的丢弃。如果ACK被丢弃了的话，那么就要靠重传机制了 TCP对发出去的数据包都保留 有计时器，如果定时器到而确认还没有收到的情况下，TCP会对刚才发送的数据包进行重传。 TCP使用确认和超时重传机制保障了数据的可靠性传输。再看流量控制方面，由于数据的发送方和接收方并不一定有相同的数据处理能力，为了 避免数据发送过快而超过对方的接收能力，TCP采用了流量控制机制，接收方在TCP的包头
3、里面通告了发送方自己的接收窗口，也就是还能够接收的最多的数据包，这样TCP就不会过 度发包而超过对方的接收能力。似乎看上去TCP已经很完美了，它提供了端到端的数据可靠性保证，并且还考虑对端的 接收能力，事实上TCP的最初设计也就是这么一些机制，具体可以看RFC793的文档。注意 到这篇文档的日期为1981年，TCP从此开始出现在互联网上传输数据。1986年10月，一件 事情的发生使得TCP开启了一个新领域，从美国LBL到UC Berkeley的数据吞吐量从32Kbps 下降到 40bps，具体可以参见 V. Jacobson 的论文“Congestion Avoidance and Contr
4、ol”， 请记住这篇文章，我们后面还会多次提到它。是什么原因导致了数据吞吐量如此严重的下降 呢？原来在TCP的控制机制里面只考虑到了接收端的接受能力，而忽略了一个很重要的方 面，那就是没有考虑到网络自己的传输能力，从而造成了整个网络崩溃的发生。从这以后， TCP的研究课题就开始多了一个方向，那就是拥塞控制，因为拥塞控制算法对保证互联网的 稳定性具有十分重要的作用，其中以V. Jacobson的那篇论文开创了互联网网拥塞控制领域 的工作。Q什么是拥塞？当网络中存在过多的报文时，网络的性能就会相应下降，这种现象就被成为拥塞。Copy一篇论文中的话来解释下：如上图，当负载较小时，吞吐量的增长与负载相
5、比基本呈线性关系，延时（即第二个图 的纵坐标：响应时间）增长缓慢，但是当负载超过Knee点后，吞吐量增长十分缓慢，但是 延迟却增长较快，当负载超过Cliff之后，吞吐量就急剧下降，延迟相应急剧上升。Cliff 点也就是网络的最大负载，一旦超过网络的整体性能就大打折扣。而负载在Knee附近时网 络的使用效率是最高的，此时吞吐量高，响应时间也比较快。拥塞控制的思想就是网络中的 节点采取一定的措施来保证尽量使得网络的负载保持在Knee位置，需要避免拥塞的发生或 者对拥塞的发生作出反应，使其能够再次恢复到Knee位置，从而保持网络的整体性能最大 化。与上面介绍的TCP的流控比较下就可以发现，流控主要是
6、考虑接收端，不要发送过快， 超过对方的接收能力，而拥塞控制则是要考虑到整个网络环境，使其负载不能超过网络的最 大承受能力。显然拥塞发生的原因是因为“需求”大于了 “供给”，网络中的有限资源被多 用户共享使用，网络本身无法根据资源的利用情况来限制某些用户，并且随着目前互联网的 发展，上网的用户和应用的数量也随之增长，这样，如果不采取某种措施来协调资源的使用， 那么拥塞的发生就是必然的。一般来说，拥塞控制算法包括拥塞避免和拥塞控制两个方面，拥塞避免是一种预防机制， 也就是说避免网络进入拥塞状态，尽量使得网络保持在高吞吐量和低延迟的情况下。对应的 拥塞控制就是恢复机制了，它使得网络一旦发生了拥塞，需
7、要从拥塞状态中恢复出来，重新 进入高吞吐量和低延迟的状态。看起来比较容易，然后事情不是想象中的那么简单。看看为什么拥塞控制是一件比较困难的事情尤其是要做到很到的拥塞控制时让网络的 利用率达到最大化。首先是互联网的模型，目前互联网采用的是报文交换(packet-switched)网络，比起之 前的电路交换相比，报文交换大大提高了网络的资源利用率(关于这一点，看看IP电话就 知道为什么IP电话便宜了)。但是报文交换网络使得整个网络变为分布式的，在网络中间 没有连接的概念，造成了每个节点所获得的信息不是很完整，而不完整的信息要完成比较好 的拥塞控制，那是非常困难的。其次就是网络环境是非常复杂的，互联
8、网上各处的网络性能有很大的差异，比如说网通 到电信的跨运营商网络丢包率就非常大，网络中间还有瓶颈链路，因此算法必须要有很好的 适应性才行，处理报文丢失、乱序等情况。第三就是算法的性能要求，整个主要包括公平性、效率、稳定性和收敛性等各个方面。 公平性主要指在带宽占用方面，不能一条连接占据了大部分带宽，而让其他的连接无法跑应 用。效率指的是在带宽充足的时候要能够充分利用带宽，避免带宽的浪费。稳定性则是要能 够长久的运行，而不能一段时间后就出现无法上面所说的一些性能要求。收敛性性则是要对 网络的动态变化快速做出响应，从而调整整个网络重新达到平衡状态。第四点需要考虑到就是算法的开销，拥塞算法必须尽量地
9、减少附加的网络流量，尤其是 在拥塞恢复的时候。这就要求各个节点间的通信要尽可能少，这个要求使得算法设计变得十 分困难。同时算法还必须网络节点的计算复杂性，否则就会降低网络节点对其它数据包的处 理能力。为了防止网络的拥塞现象，TCP提出了一系列的拥塞控制机制。最初由V. Jacobson在 1988年的论文中提出的TCP的拥塞控制由“慢启动(Slow start)”和“拥塞避免 (Congestion avoidance) ”组成，后来TCP Reno版本中又针对性的加入了 “快速重传(Fast retransmit) ”、“快速恢复(Fast Recovery) ”算法，再后来在TCP New
10、Reno 中又对 “快速恢复”算法进行了改进，近些年又出现了选择性应答 (selective acknowledgement,SACK)算法，还有其他方面的大大小小的改进，成为网络研 究的一个热点。TCP的拥塞控制主要原理依赖于一个拥塞窗口 (cwnd)来控制，在之前我们还讨论过TCP 还有一个对端通告的接收窗口 (rwnd)用于流量控制。窗口值的大小就代表能够发送出去的但 还没有收到ACK的最大数据报文段，显然窗口越大那么数据发送的速度也就越快，但是也有 越可能使得网络出现拥塞，如果窗口值为1，那么就简化为一个停等协议，每发送一个数据， 都要等到对方的确认才能发送第二个数据包，显然数据传输效
11、率低下。TCP的拥塞控制算法 就是要在这两者之间权衡，选取最好的cwnd值，从而使得网络吞吐量最大化且不产生拥塞。由于需要考虑拥塞控制和流量控制两个方面的内容，因此TCP的真正的发送窗口=min(rwnd, cwnd)。但是rwnd是由对端确定的，网络环境对其没有影响，所以在考虑拥塞 的时候我们一般不考虑rwnd的值，我们暂时只讨论如何确定cwnd值的大小。关于cwnd的 单位，在TCP中是以字节来做单位的，我们假设TCP每次传输都是按照MSS大小来发送数据 的，因此你可以认为cwnd按照数据包个数来做单位也可以理解，所以有时我们说cwnd增加 1也就是相当于字节数增加1个MSS大小。慢启动：
12、最初的TCP在连接建立成功后会向网络中发送大量的数据包，这样很容易导致 网络中路由器缓存空间耗尽，从而发生拥塞。因此新建立的连接不能够一开始就大量发送数 据包，而只能根据网络情况逐步增加每次发送的数据量，以避免上述现象的发生。具体来说， 当新建连接时，cwnd初始化为1个最大报文段(MSS)大小，发送端开始按照拥塞窗口大小发 送数据，每当有一个报文段被确认，cwnd就增加1个MSS大小。这样cwnd的值就随着网络 往返时间(Round Trip Time,RTT)呈指数级增长，事实上，慢启动的速度一点也不慢，只是 它的起点比较低一点而已。我们可以简单计算下：开始-cwnd = 1经过1个RTT
13、后-cwnd = 2*1 = 2经过2个RTT后-cwnd = 2*2= 4经过3个RTT后-cwnd = 4*2 = 8如果带宽为W，那么经过RTT*log2W时间就可以占满带宽。拥塞避免：从慢启动可以看到，cwnd可以很快的增长上来，从而最大程度利用网络带 宽资源，但是cwnd不能一直这样无限增长下去，一定需要某个限制。TCP使用了一个叫慢 启动门限(ssthresh)的变量，当cwnd超过该值后，慢启动过程结束，进入拥塞避免阶段。 对于大多数TCP实现来说，ssthresh的值是65536(同样以字节计算)。拥塞避免的主要思想 是加法增大，也就是cwnd的值不再指数级往上升，开始加法增加
14、。此时当窗口中所有的报 文段都被确认时，cwnd的大小加1，cwnd的值就随着RTT开始线性增加，这样就可以避免 增长过快导致网络拥塞，慢慢的增加调整到网络的最佳值。上面讨论的两个机制都是没有检测到拥塞的情况下的行为，那么当发现拥塞了 cwnd又 该怎样去调整呢？首先来看TCP是如何确定网络进入了拥塞状态的，TCP认为网络拥塞的主要依据是它重 传了一个报文段。上面提到过，TCP对每一个报文段都有一个定时器，称为重传定时器(RTO)， 当RTO超时且还没有得到数据确认，那么TCP就会对该报文段进行重传，当发生超时时，那 么出现拥塞的可能性就很大，某个报文段可能在网络中某处丢失，并且后续的报文段也
15、没有 了消息，在这种情况下，TCP反应比较“强烈”：1. 把ssthresh降低为cwnd值的一半2. 把cwnd重新设置为13. 重新进入慢启动过程。从整体上来讲，TCP拥塞控制窗口变化的原则是AIMD原则，即加法增大、乘法减小。 可以看出TCP的该原则可以较好地保证流之间的公平性，因为一旦出现丢包，那么立即减半 退避，可以给其他新建的流留有足够的空间，从而保证整个的公平性。其实TCP还有一种情况会进行重传：那就是收到3个相同的ACK。TCP在收到乱序到达 包时就会立即发送ACK，TCP利用3个相同的ACK来判定数据包的丢失，此时进行快速重传， 快速重传做的事情有：1. 把ssthresh设
16、置为cwnd的一半2. 把cwnd再设置为ssthresh的值(具体实现有些为ssthresh+3)3. 重新进入拥塞避免阶段。后来的“快速恢复”算法是在上述的“快速重传”算法后添加的，当收到3个重复ACK时，TCP最后进入的不是拥塞避免阶段，而是快速恢复阶段。快速重传和快速恢复算法一般 同时使用。快速恢复的思想是“数据包守恒”原则，即同一个时刻在网络中的数据包数量是 恒定的，只有当“老”数据包离开了网络后，才能向网络中发送一个“新”的数据包，如果 发送方收到一个重复的ACK，那么根据TCP的ACK机制就表明有一个数据包离开了网络，于 是cwnd加1。如果能够严格按照该原则那么网络中很少会发生拥塞，事实上拥塞控制的目 的也就在修正违反该原则的地方。具体来说快速恢复的主要步骤是：1. 当收到3个重复ACK时，把ssthresh设置为cwnd的一半，把cw
