网络拥塞算法总结.doc

网络拥塞算法总结 网络拥塞控制算法总结网络拥塞控制的目的不是要完全避免拥塞的发生，而是通过拥塞控制，提高网络的性能及数据处理能力，保障网络的稳定和持续运行，并且保证数据传输的公平性。 我们知道，网络拥塞的根本原因在于端系统发出的数据超出了网络的处理能力，而拥塞控制算法的基本思想则是解决这一问题，通常的方法就是TCP拥塞控制算法和IP拥塞控制算法。 1.TCP拥塞控制算法通常，TCP的拥塞控制分为4个阶段，即慢启动（slow start）阶段、拥塞避免（congestion avoidance）阶段、快速重传（fast retransmit）阶段、快速恢复（fast recovery）阶段；可参考TCP/IP详解卷I的相关内容。 在实际的实现过程中，TCP对拥塞的控制都是通过改变一些参数来实现的，如拥塞窗口（cwnd）、通告窗口（awin）、发送窗口（win）、慢启动阈值（ssthresh）、往返时延（RTT）、超时重传计数器（RTO）、快速重传阈值等。 a)TCP拥塞控制算法的演进我们知道，TCP是端到端的协议，所以，基于TCP的拥塞控制也是端到端的算法，具体包括TCP Tahoe算法、TCP Reno算法、TCP NewReon算法、TCP SACK算法等，下面对这几种算法进行简单的介绍。 ?TCP Tahoe算法该算法包括慢启动、拥塞避免、快速重传以及RTT估计量的修改，这是TCP拥塞控制的基础，其它的算法依赖于此。 ?TCP Reno算法该算法在Tahoe的基础之上增加了“快速恢复”阶段，Reno算法在快速重传后并不将cwnd减少至1MSS，而是将cwnd减半，进入拥塞避免阶段。 但该算法也存在不足，当发送端检测拥塞后，需要重传全部数据包（包括已经正确传输的数据包）。 ?TCP NewReno算法该算法是对Reno算法的补充，它通过尽量避免Reno在快速恢复阶段的重传超时，在快速恢复阶段，发送方收到一个部份的ACK后，立即重传余下的数据包，从而提高传输性能，目前在互联网上使用最多的就是TCP NewReno算法。 ?TCP SACK算法该算法是对Reno算法的补充，使用该算法，当检测到数据丢失后，不用重传全部数据包，而是对数据包进行选择性确认和重传，从而减少重传，时延，提高传输性能。 SACK算法并不是每一个TC端都支持。 b)TCP拥塞控制算法的优缺点TCP拥塞控制是端到端的控制，它可以降低网络交换设备的工作负担，保持设备的稳定性，而且其算法所涉及的设备少，非常容易实现，所以目前的互联网大部份都是基于TCP拥塞控制来实现的。 但它也存在一些缺点，如在高速网络中不能有效利用带宽（确认机制、重传机制等）；与UDP相比，存在对网络资源的不公平使用问题，因为当出现网络拥塞时，遵循拥塞控制TCP应用得到的资源会越来越少，而没有拥塞机制的UDP应用会得到越来越多的资源等。 2.IP拥塞控制算法TCP拥塞控制是端到端的拥塞管理，但在实际的数据传输中，网络本身也会造成拥塞，所以需要让网络本身参与到拥塞控制中，也就是IP拥塞控制算法，通过对路由器的缓冲队列进行管理控制，从而提高路由器性能、拥塞管理和QoS能力。 a)IP拥塞控制算法的分类IP拥塞控制的典型算法一般有先进先出（FIFO）、随机早期检测（RED）、显示拥塞指示算法（E）、公平排队算法（FQ）、加权公平排队算法（WFQ）等。 ?先进先出（FIFO）算法先进先出的最大优点在于实施起来简单，其原理是第一个到达的数据包将被首先传输，由于路由器的缓存总是有限的，当缓冲区满后，随后到达的包将被丢弃。 由于FIFO总是丢弃到达队尾的包，所以经常和去尾(DropTail)算法在概念上被淆。 FIFO是一种包的调度策略，DropTail是一种包的丢弃策略。 由于FIFO和DropTail实施起来比较简单，因而目前去尾的先入先出是Intemet上最广泛使用的队列调度管理方式。 ?随机早期检测（RED）算法RED算法通过监控路由器中的数据包排队长度，在缓存占满之前，一旦发现拥塞迫近就按一定的概率丢弃进入路由器的数据包，这样就可以及早地通知源端减小拥塞窗口，从而减少进入网络的数据量。 这意味着路由器以后不必丢弃更多的数据包，从而提高网络的吞吐量。 RED算法主要包含两部分如何监控平均队列长度和如何丢弃数据包。 ?显示拥塞指示算法（E）E由RFC2481推荐，在IPv4报头结构中的TOS字段中的设置E域，E在源端数据包中嵌入E使能发送比特位，由路由器根据网络的具体情况设置CE位。 发送端接收到这种置位的数据包后就认为网络发生拥塞，从而减小发送速率。 详见.csna./workanalyst2439611.html?公平排队（FQ）算法公平算法通过对数据流进行分隔，让不同的数据流互不影响，为数据流公平的分配资源。 每个输出线路都分配一个队列，路由器按“轮询”方式来回扫描所有队列，并依次将每队的第一个包发出去，当某个流的数据到达过快且队列占满后，属于该流的新到数据会被丢弃。 公平排队算法遵循以下规则当只有一个流时，将所有带宽分配给该流；当有X个流要共享带宽时，每个流得到的带宽为1/X。 ?加权公平排队（WFQ）算法加权公平排队算法是对公平排队算法的改进，它对每个流分配一个权值，该值决定路由器每次发送数据的数量，从而控制数据流的带宽分配。 权值的分配跟据不同优先级的数据流而定，如在IP报头中的TOS字段指定的优先级，在排队时再按优先级分配权值，这也是区分服务的思想。 注FQ是一种特殊的WFQ，即将所有权值看成1。 b)IP拥塞控制算法的优缺点IP拥塞控制在网络层实现，可以区分不同的发送端产生的数据流，在路由器中通过队列调度，接受或丢弃数据，可以达到对带宽的公平处理，对于短期的拥塞，IP拥塞控制可以处理得比较好，但对于长期的拥塞却无能为力。 而且相应的算法也存在不足，如RED算法会导致不稳定，不适合对时延敏感的应用，E算法存在兼容性问题，FIFO没有考虑数据包的重要程度等。 3.TCP与IP拥塞比较TCP拥塞控制实际上是一种基于源的拥塞控制方法，实现在端系统中，这种拥塞控制方法在网络拥塞发生到感知到拥塞后采取控制行动之间存在着比较大的延迟；IP拥塞控制在网络中实现，可以及时感知到网络拥塞的发生，采