网络拥塞控制的分析与研究

1、网络拥塞控制的分析与研究2015级 软件工程高家祺摘要随着互联网本身规模的迅速扩大、互联网用户数的剧增以及网络应用类型的快速增加，网络正经历越来越多的包丢失和其他的性能恶化问题，其中一个比较严重的现象就是网络拥塞。网络拥塞导致的直接后果是整个网络的性能下降：包括分组丢失率增加、端到端延迟增大、网络吞吐量下降、甚至有可能使整个系统发生拥塞崩溃。当网络处于拥塞崩溃状态时，微小的负载增量都将使网络的有效吞吐量急剧下降。造成网络拥塞的原因很多，主要有：存储空间不足、带宽容量不足、处理器处理能力弱、TCP/PI协议拥塞控制机制中的缺陷、用户的恶意攻击造成的网络拥塞以及网络系统的混沌、分叉等现象都会导致网

2、络通讯的崩溃。在目前的Internet中，既然网络拥塞是无法避免的，就必须采取积极主动的策略控制和避免拥塞，把拥塞发生的可能性降到最低，即使在发生拥塞后也能及时地恢复到正常运行状态；同时拥塞控制也必须保证网络效率。因此,网络拥塞控制是网络系统改善性能和提高服务质量的主要手段，网络拥塞控制问题的研究具有重要的理论意义和应用价值。本文主要从网络拥塞的概念解释、造成拥塞的原因、防止拥塞的方法、拥塞控制的常用算法、拥塞控制方面的研究热点以及网络拥塞控制未来的发展等多个方面对网络拥塞控制进行阐述。第一章：拥塞现象介绍一、拥塞现象拥塞现象是指到达通信子网中某一部分的分组数量过多，使得该部分网络来不及处理，

3、以致引起这部分乃至整个网络性能下降的现象，严重时甚至会导致网络通信业务陷入停顿，即出现死锁现象。这种现象跟公路网中经常所见的交通拥挤一样，当节假日公路网中车辆大量增加时，各种走向的车流相互干扰，使每辆车到达目的地的时间都相对增加（即延迟增加）,甚至有时在某段公路上车辆因堵塞而无法开动(即发生局部死锁)。1. 与拥塞相关的名词解释网络的吞吐量与通信子网负荷(即通信子网中正在传输的分组数)有着密切的关系。当通信子网负荷比较小时,网络的吞吐量(分组数/秒)随网络负荷(每个节点中分组的平均数)的增加而线性增加。当网络负荷增加到某一值后网络吞吐量反而下降,则表征网络中出现了拥塞现象。在一个出现拥塞现象的

4、网络中,到达某个节点的分组将会遇到无缓冲区可用的情况,从而使这些分组不得不由前一节点重传,或者需要由源节点或源端系统重传。当拥塞比较严重时,通信子网中相当多的传输能力和节点缓冲器都用于这种无谓的重传,从而使通信子网的有效吞吐量下降。由此引起恶性循环,使通信子网的局部甚至全部处于死锁状态,最终导致网络有效吞吐量接近为零。2. 造成拥塞的原因分析造成网络拥塞的原因一般来说分为以下2种：a. 多条流入线路有分组到达，并需要同一输出线路，此时，如果路由器没有足够的内存来存放所有这些分组，那么有的分组就会丢失。b. 路由器的慢带处理器的缘故，以至于难以完成必要的处理工作，如缓冲区排队、更新路由表等。3.

5、 防止拥塞的常用方法由于拥塞可以发生在TCP/IP模型中的传输层、网络层和数据链路层三个层次，所以防止拥塞的方法在不同层次也具有不同的表现形式。a. 在传输层可采用：重传策略、乱序缓存策略、确认策略、流控制策略和确定超时策略。b. 在网络层可采用：子网内部的虚电路与数据报策略、分组排队和服务策略、分组丢弃策略、路由算法和分组生存管理。c. 在数据链路层可采用：重传策略、乱序缓存策略、确认策略和流控制策略。二、拥塞控制的方法常见的拥塞控制方法一般分为以下三种，主要是针对不同的网络环境而有所不同。1. 缓冲区预分配法该法用于虚电路分组交换网中。在建立虚电路时,让呼叫请求分组途经的节点为虚电路预先分

6、配一个或多个数据缓冲区。若某个节点缓冲器已被占满,则呼叫请求分组另择路由,或者返回一个"忙"信号给呼叫者。这样,通过途经的各节点为每条虚电路开设的永久性缓冲区(直到虚电路拆除),就总能有空间来接纳并转送经过的分组。此时的分组交换跟电路交换很相似。当节点收到一个分组并将它转发出去之后,该节点向发送节点返回一个确认信息。该确认一方面表示接收节点已正确收到分组,另一方面告诉发送节点,该节点已空出缓冲区以备接收下一个分组。上面是"停一等"协议下的情况,若节点之间的协议允许多个未处理的分组存在,则为了完全消除拥塞的可能性,每个节点要为每条虚电路保留等价于窗口大小数

7、量的缓冲区。这种方法不管有没有通信量,都有可观的资源(线路容量或存储空间)被某个连接占有,因此网络资源的有效利用率不高。这种控制方法主要用于要求高带宽和低延迟的场合,例如传送数字化语音信息的虚电路。2. 分组丢弃法该法不必预先保留缓冲区,当缓冲区占满时,将到来的分组丢弃。若通信子网提供的是数据报服务,则用分组丢弃法来防止拥塞发生不会引起大的影响。但若通信子网提供的是虚电路服务,则必须在某处保存被丢弃分组的备份,以便拥塞解决后能重新传送。有两种解决被丢弃分组重发的方法,一种是让发送被丢弃分组的节点超时,并重新发送分组直至分组被收到;另一种是让发送被丢弃分组的节点在尝试一定次数后放弃发送,并迫使数

8、据源节点超时而重新开始发送。但是不加分辨地随意丢弃分组也不妥,因为一个包含确认信息的分组可以释放节点的缓冲区,若因节点原空余缓冲区来接收含确认信息的分组,这便使节点缓冲区失去了一次释放的机会。解决这个问题的方法可以为每条输入链路永久地保留一块缓冲区,以用于接纳并检测所有进入的分组,对于捎带确认信息的分组,在利用了所捎带的确认释放缓冲区后,再将该分组丢弃或将该捎带好消息的分组保存在刚空出的缓冲区中。3. 定额控制法这种方法在通信子网中设置适当数量的称做"许可证"的特殊信息,一部分许可证在通信子网开始工作前预先以某种策略分配给各个源节点,另一部分则在子网开始工作后在网中四处环游

9、。当源节点要发送来自源端系统的分组时,它必须首先拥有许可证,并且每发送一个分组注销一张许可证。目的节点方则每收到一个分组并将其递交给目的端系统后,便生成一张许可证。这样便可确保子网中分组数不会超过许可证的数量,从而防止了拥塞的发生。第二章：拥塞控制的常用算法分析一、TCP拥塞控制典型算法分析目前在Internet上实际使用的拥塞控制基本上是建立在TCP窗口控制基础之上的，据统计，Internet上的95%的数据流使用的是TCP协议，因此TCP拥塞控制一直是网络拥塞控制研究的重点。最初由V. Jacobson在1988年的论文中提出的TCP的拥塞控制由“慢启动(Slow st

10、art)”和“拥塞避免(Congestion avoidance)”组成，后来TCP Reno版本中又针对性的加入了“快速重传(Fast retransmit)”、“快速恢复(Fast Recovery)”算法，再后来在TCP NewReno中又对“快速恢复”算法进行了改进，近些年又出现了选择性应答(selective acknowledgement,SACK)算法，还有其他方面的大大小小的改进，成为网络研究的一个热点。1. 慢启动最初的TCP在连接建立成功后会向网络中发送大量的数据包，这样很容易导致网络中路由器缓存空间耗尽，从而发生拥塞。因此新建立的连

11、接不能够一开始就大量发送数据包，而只能根据网络情况逐步增加每次发送的数据量，以避免上述现象的发生。具体来说，当新建连接时，cwnd(计算机网络拥塞窗口)初始化为1个最大报文段(MSS)大小，发送端开始按照拥塞窗口大小发送数据，每当有一个报文段被确认，cwnd就增加1个MSS大小。这样cwnd的值就随着网络往返时间(Round Trip Time,RTT)呈指数级增长，事实上，慢启动的速度一点也不慢，只是它的起点比较低一点而已。我们可以简单计算下：开始        ->   &#

12、160; cwnd = 1    经过1个RTT后   ->     cwnd = 2*1 = 2    经过2个RTT后   ->     cwnd = 2*2= 4    经过3个RTT后 &#

13、160; ->     cwnd = 4*2 = 8 如果带宽为W，那么经过RTT*log2W时间就可以占满带宽。 2. 拥塞避免从慢启动可以看到，cwnd可以很快的增长上来，从而最大程度利用网络带宽资源，但是cwnd不能一直这样无限增长下去，一定需要某个限制。TCP使用了一个叫慢启动门限(ssthresh)的变量，当cwnd超过该值后，慢启动过程结束，进入拥塞避免阶段。对于大多数TCP实现来说，ssthresh的值是65536(同样以字节计算)。拥塞避免的主要思想是加

14、法增大，也就是cwnd的值不再指数级往上升，开始加法增加。此时当窗口中所有的报文段都被确认时，cwnd的大小加1，cwnd的值就随着RTT开始线性增加，这样就可以避免增长过快导致网络拥塞，慢慢的增加调整到网络的最佳值。3. 快速重传TCP认为网络拥塞的主要依据是它重传了一个报文段。TCP对每一个报文段都有一个定时器，称为重传定时器(RTO)，当RTO超时且还没有得到数据确认，那么TCP就会对该报文段进行重传，当发生超时时，那么出现拥塞的可能性就很大，某个报文段可能在网络中某处丢失，并且后续的报文段也没有了消息，在这种情况下，TCP反应比较“强烈”：a. 把ssthresh降低为cwnd值的一半

15、 。b. 把cwnd重新设置为1 。c. 重新进入慢启动过程。 从整体上来讲，TCP拥塞控制窗口变化的原则是AIMD原则，即加法增大、乘法减小。可以看出TCP的该原则可以较好地保证流之间的公平性，因为一旦出现丢包，那么立即减半退避，可以给其他新建的流留有足够的空间，从而保证整个的公平性。4. 快速恢复“快速恢复”算法是在上述的“快速重传”算法后添加的，当收到3个重复ACK时，TCP最后进入的不是拥塞避免阶段，而是快速恢复阶段。快速重传和快速恢复算法一般同时使用。快速恢复的思想是“数据包守恒”原则，即同一个时刻在网络中的数据包数量是恒定的，只有当“老”数据包离开了网

16、络后，才能向网络中发送一个“新”的数据包，如果发送方收到一个重复的ACK，那么根据TCP的ACK机制就表明有一个数据包离开了网络，于是cwnd加1。如果能够严格按照该原则那么网络中很少会发生拥塞，事实上拥塞控制的目的也就在修正违反该原则的地方。具体来说快速恢复的主要步骤是：a. 当收到3个重复ACK时，把ssthresh设置为cwnd的一半，把cwnd设置为ssthresh的值加3，然后重传丢失的报文段，加3的原因是因为收到3个重复的ACK，表明有3个“老”的数据包离开了网络。  b. 再收到重复的ACK时，拥塞窗口增加1。 c. 当收到新的数据包的ACK时，把c

17、wnd设置为第一步中的ssthresh的值。原因是因为该ACK确认了新的数据，说明从重复ACK时的数据都已收到，该恢复过程已经结束，可以回到恢复之前的状态了，也即再次进入拥塞避免状态。5. 其他改进的算法随着互联网技术的不断发展，人们又研发了一些更加有效的拥塞控制算法，这些算法究其本质而言都是在“慢启动”、“拥塞避免”、“快速重传”和“快速恢复”等算法的基础上进行的一些扩充。常见的有TCP Tahoe、TCP Reno、TCP NewReno、TCP Sack以及TCP Vegas等等，这里不做详细介绍。二、IP拥塞控制典型算法分析TCP基于窗口的拥塞控制机制对于Internet的健壮性起到了

18、关键性的作用。然而随着Internet本身的迅猛发展,其规模越来越庞大，结构也日趋复杂，研究者们也认识到仅仅依靠TCP端到端的拥塞控制是不够的，网络也应该参加资源的控制工作。网络本身要参与到拥塞控制中已经成为了一个不可回避的问题。现在IP层拥塞控制的研究也越来越多，已经形成了一个新的热点研究方向。IP层拥塞控制就其本质来说是通过对路由器缓冲区队列中的分组实施调度和管理来影响TCP拥塞控制的动态性能以达到目的的。已经出现了一系列的队列调度和管理的算法来实现拥塞控制。下面将对其中较为出名的两种算法进行深入探究。1. 先进先出(FIFO)FIFO又叫先到先服务(FCFS)，即第一个到达的包将被首先服

19、务。由于路由器的缓存总是有限的，当缓冲区满后，随后到达的包将被丢弃。由于FIFO总是丢弃到达队尾的包，所以经常和去尾(Drop-Tail)算法在概念上被混淆。FIFO是一种包的调度策略，Drop-Tail是一种包的丢弃策略。由于FIFO和Drop-Tail实施起来比较简单，因而目前去尾的先入先出是Internet上最广泛使用的队列调度管理方式。然而，去尾的FIFO自身存在一些问题，例如：它不能区分不同的数据流，也不提供强制数据流遵守拥塞控制的机制，这就有可能让某些数据流强占大量带宽，引发公平性问题。例如UDP数据流可以向网络任意发送数据包，从而引起其它数据流的包的丢弃；去尾的FIFO也会导致不

20、合理的丢包模式，在小规模的统计多路复用的情况下，它还存在全局同步问题，引发多个数据发送方同时减小发送速率。2. 随机检测算法(RED)RED(Random Early Detection)算法在1993年由Floyd和Jacobson提出，该算法通过监控路由器中的数据包排队长度，在缓存占满之前，一旦发现拥塞迫近就按一定的概率丢弃进入路由器的数据包，这样就可以及早地通知源端减小拥塞窗口，从而减少进入网络的数据量。这意味着路由器以后不必丢弃更多的数据包，从而提高网络的吞吐量。RED算法主要包含两部分：如何监控平均队列长度和如何丢弃数据包。平均队列长度是由指数加权滑动平均(EWMA)来计算的：。其中

21、，wq为权值。q为采样测量时的队列长度。丢包概率由下式计算：上式表明当一个数据包到达队列时，如果平均队列长度小于最小阈值，则此包进入队列排队；如果平均队列长度介于最大阈值和最小阈值之间，则根据计算得到的丢弃概率P丢弃此包；如果平均队列长度大于最大阈值，则直接丢弃此包。RED算法通过早期随即丢弃数据包，使得平均队列长度始终处于较低的水平，有利于对短期突发数据流的吸收。而且由于随即丢弃的使用，避免了去尾算法的全局同步问题。然而，RED算法也存在着缺点：算法是参数敏感的，而且其参数配置问题一直没有得到很好的解决，而且其稳定性也存在着问题。第三章：拥塞控制目前的研究热点与未来发展一、目前研究热点拥塞控

22、制不仅是网络稳定、高效运行的关键，同时又是实现各种服务质量的基础和前提。实际的网络是一个不断发展的系统，网络拥塞控制研究也是一个非常困难、有挑战性的研究领域。对网络拥塞控制的研究仍有许多工作要做，就目前来看主要的研究热点有以下几点：1. 拥塞控制基于端主机的控制策略和路由器的队列管理策略存在相互影响、相互作用的关系，如何在网络模型描述的基础上，从控制系统的角度将两者结合起来，设计出最优的拥塞控制策略，是网络拥塞控制研究的一个热点。2. 主动队列管理技术通过丢包积极响应拥塞，来达到拥塞避免和缓解的目的，是网络拥塞控制最重要的手段。如何实现主动队列管理高级策略，引入新的人工智能算法和遗传算法与模糊

23、逻辑的综合应用是目前研究的一个热点问题。3. 以往的工作主要采用局部线性化方法，缺乏对系统全局动力学的理论分析。此外，在多种源端拥塞控制策略和路由器避免策略并存时，如何分析整个网络的稳定性，如何分析各种不确定因素对稳定性的影响等，也是需要认真考虑的问题。4. TCP/IP 拥塞控制的设计和实现面临着众多的折中，不可能有一种设计和实现在所有环境中都是完美的。现有的拥塞控制思路、方法和技术在多目标的不同环境中面临着挑战，它们还有许多要改进的地方。5. 目前已经有越来越多的移动用户通过无线系统接入互联网，由于无线通信固有的特点，使得拥塞控制机制的研究更加困难，极具挑战。二、下一代网络的特点计算机网络

24、以及通信技术的迅猛发展，对人类的生产和生活方式带来了革命性的变化。人们获取信息的方式更加多样，获取信息的途径更加便捷。来源于互联网服务提供商(ISP)和网络开发设计的下一代网络技术越来越得到研究界的关注，下一代网络是一种新的基于包交换的网络技术，可以提供更多的网络服务如支持视频会议的多媒体通信，点对点网络IPTV,移动通信技术和家庭网络等等。下一代网络的特点主要有：1. 层出不穷的新应用传统智能网是一个在现有通信网络技术基础上提供电信业务的网络体系结构，主要目的在于为用户提供各类电信业务，服务业务种类较为单一。如对电话服务而言，包括着从电路交换到包交换的转换，由于受到智能网本身能力的限制，传统

25、的智能网络在业务开发、业务种类很多重要方面幵始显现出不足。当前的下一代网络旨在保证包括电话业务的、以及多媒体应用，以视频、图像传输为主的多媒体业务越来越成为下一代网络的主要业务，同时对QOS（服务质量）的要求越来越高。2. 满足不同QOS需求的分级服务传统互联网的尽力而为服务，在业务流量很高、带宽资源紧缺时，其QOS难以得到保证。传统的主要业务如文本传输只对吞吐量敏感，对其它QOS指标无法保证。而下一代网络在于网络融合，不仅需要对电信网提供服务，同时提供新业务，在网络拥塞控制时，就需保证其服务质量，实现QOS的分级服务。3. 网络的带宽时延积越来越大随着下一代网络的技术进一步发展，网络的带宽和延迟也随着增加，即网络的带宽时延积BDP (Bandwidth-Delay Product)越来越大，这是未来网络发展的重要趋势，比如光纤网络和卫星链路等大时延网络的广泛应用。仅靠传统的网络拥塞技术面临着越来越多的挑战。三、下一代网络拥塞控制研究的技术路线下一代网络的用户对服务的质量和可靠性有了更高的要求，而网络的拥塞控制仍然是阻碍服务性能的最主要的瓶颈之一，这也是网络拥塞控制仍是研究热点的原因。目前下一代网络中拥塞控制研究的主要技术路线分为两个部分：一是如何使用现有的协议配置更