基于TCP和路由器技术的网络拥塞控制-基础电子

精品文档-下载后可编辑基于TCP和路由器技术的网络拥塞控制-基础电子1引言

Internet中拥塞控制的大部分工作是由TCP完成的，目前标准TCP协议的实现都包含了一些避免和控制网络拥塞的算法。当今Internet的可靠性和稳定性与TCP拥塞控制机制密不可分，而TCP的成功也要归功于其稳固的拥塞控制机制。随着应用要求的日益丰富和技术的不断发展，要想完全依赖实现在终端系统上的策略和算法很难满足服务质量（QoS）这样复杂的要求，为了解决相应的问题，相关网络技术逐渐转向网络的中间节点即路由器上，通过增强它们的功能来实现端到端无法达到的技术，从而达到有效的拥塞控制，保持网络的良好性能。

2产生拥塞的原因

当一个网络中出现太多报文分组的时候，网络的性能开始下降，这种情况称为拥塞。拥塞是一种持续过载的网络状态，此时用户对网络资源的需求超过了其固有的容量，这是产生拥塞的根本原因，而端到端之间却存在着直接的原因，主要有：1.存储空间相对不足。主要表现在理由器上，虽然增加存储空间有时可以缓解拥塞的产生，但有时候不但不能缓解拥塞，反而会加剧拥塞。2.带宽容量不足。低速链路对高速数据流的输入也会产生拥塞。3.链路与CPU的处理速度不匹配，造成处理能力弱，速度慢从而引起拥塞。

3TCP的拥塞控制机制

3.1加法增加乘法减少（AIMD）算法

TCP作为Internet上使用广泛的端到端传输协议，它的拥塞控制机制主要基于加法增加乘法减少(AIMD)算法，该算法定义了3个窗口变量：

(1)拥塞窗口(cwnd)：它限定了在拥塞控制中源端在一时间段里的数据传输量，是来自源端的流量控制。

(2)通告窗口(awnd)：接受端与源端建立连接后，接收端通告源端它的可接受速率，它是来自接受端的流量控制。

(3)有效窗口(win):即源端发送数据的实际窗口大小，定义为win=min(cwnd,awnd)

AIMD的工作过程可分为两步：

(1)源端每收到一个来自接受端的ACK确认,拥塞窗口按cwnd=cwnd+MSS*(MSS/cwnd)(MSS为分组大小)增大，它所表示的实际意义是如果源端发送的分组都在近的往返时间(RTT)内获得确认,源端就将cwnd加1，即加法增加思想。

(2)当数据传送发生超时，TCP认为路线上出现拥塞，并开始减小源端的数据发送速率。每发生超时，源端就会重新计算拥塞窗口的值，公式如下：

cwnd=cwnd/2

它表示发生超时，拥塞窗口将在原来基础上减小一半，即乘法减少思想。

3.2TCP拥塞控制的四个阶段

这是TCP拥塞控制的，也体现了TCP拥塞控制的基本思想，它分为启动阶段，拥塞避免，快速重传和快速恢复阶段。

(1)启动阶段

当连接刚建立或在发生超时的情况下，进入慢启动阶段。

一个新的TCP连接建立后，cwnd被初始化为1，源端只被允许发送一个报文段。当发出的报文收到接受端的ACK确认后，cwnd加1，即增加一个报文段发送。在这个阶段中，cwnd随RTT呈指数增长。

采用慢启动方法，可以防止TCP在启动一个新的连接时发送过多的数据而造成数据丢失和网络拥塞，同时，由于cwnd实际上以指数规律增长也就避免了单纯的AIMD算法造成的吞吐量增加过慢的问题。

cwnd的无限增长必将引起网络拥塞，于是引入一个状态变量：慢启动阈值ssthresh。

当cwndssthresh时，TCP执行慢启动算法，cwnd随RTT呈指数增长；

当cwndssthresh是，则采用拥塞避免算法，减缓cwnd的增长速度。

(2)拥塞避免阶段

在拥塞避免阶段，当TCP探测到网络将要发生拥塞，并没有直接采用复位cwnd＝1，重新开始慢启动的方法。因为一旦发生拥塞，需要很长的时间来恢复，而慢启动算法中cwnd的指数增长就显得有些激进，它很可能会加重网络拥塞。因此，在这个阶段，采用相对更保守的调节机制改变awnd的增长方式，使它由指数增长变成线性增长，具体过程如下：

1.将慢启动阈值ssthresh设置为当前cwnd的一半，即ssthresh=cwnd/2；

2.发生超时时，置cwnd=1,在cwndssthresh条件下，TCP执行慢启动；

3.awnd=ssthresh时，执行拥塞避免算法，cwnd每收到一个ACK确认时，只增加1/cwnd个数据包这就使得cwnd随RTT呈线性增长。

(3)快速重传和快速恢复阶段

由于在拥塞避免阶段，当发生超时时，cwnd重新置1，进入慢启动，这将导致过大减小发送窗口尺寸，很大程度上降低了TCP连接的吞吐量。为了完善TCP的性能，又引入了快速重传和快速恢复机制。

快速重传阶段，当源端收到3个或者3个以上的重复ACK确认，即认为发生了数据包丢失，此时将ssthresh设置为当前cwnd的一半，ssthresh=awnd/2，并重新传送丢失的数据包，进入快速恢复阶段。

在快速恢复阶段，源端每收到一个重复的ACK，则cwnd加1；若收到非重复的ACK，置cwnd＝ssthresh，转入拥塞避免；当发生超时重传时，置ssthresh=cwnd/2，cwnd=1，进入慢启动阶段。

快速重传和快速恢复机制避免了数据包一发生超时就直接进入慢启动，在很大程度上提高了TCP的性能和吞吐量。

3.3典型TCP拥塞控制算法分析比较

TCP发展到现在已经形成了TCPTahoe、TCPReno、TCPNewReno、SACK、Vegas等不同版本，算法各有利弊。

Tahoe算法是TCP的早期版本。它的思想是：让cwnd以指数增长方式迅速逼近可用信道容量，然后慢慢接近均衡。它包括了3个基本的拥塞控制算法：慢启动、拥塞避免、快速重传。Tahoe的缺点体现在快速重传后转向慢启动算法，这样不能有效的利用网络带宽并且还引入较大的延时。

针对Tahoe算法的不足，提出了改进算法Reno。改进主要有两方面：一是对于收到连续3个重复的ACK确认，算法不经过慢启动，而直接进入拥塞避免阶段；二是增加了快速重传和快速恢复机制。Reno算法以其简单、有效和鲁棒性成为TCP源算法的主流，被广泛的采用。但它不能有效的处理多个分组从同一数据窗口丢失的情况。

NewReno对Reno中快速恢复算法进行了补充，它考虑了一个发送窗口内多个分组同时丢失的情况。Reno算法中，发送方收到一个不重复的应答后就退出快速恢复，而NewReno中，只有当所有的分组都被应答后才退出快速恢复状态。NewReno的实现只要修改TCP发送端的实现代码，实现简单。

SACK算法也针对一个窗口内多个分组丢失的情况而对Reno算法进行改进：SACK定义了一个变量pipe来表示出现在路由器上分组的估计数量，接收方TCP发送SACK分组来通知发送方接收数据的情况，这样源端就能准确的知道那些数据被正确的传到接收端，从而避免不必要的重传，减少延时，提高网络吞吐量。但SACK算法的实现需要修改TCP发送端和接收端的实现代码，增加了TCP的复杂性，因此不易大规模的应用。

Vegas与上述的算法不同，它是以RTT的变化来作为拥塞信号，调节源端的发送速率。通过监测RTT的变化来改变cwnd的大小。由于Vegas采用RTT的改变来判断网络的可用带宽，能较好的预测网络带宽的使用情况，其公平性、效率都较好。但是，由于Vegas与其它算法在竞争带宽方面存在不公平现象，因此未能在Internet上普遍采用，还需要不断改进。

4基于路由器技术的拥塞控制机制

路由器作为Internet的部件，需要同时维护一个或多个队列，这是基于它分组交换的特性。而队列管理算法又将直接影响到路由器的各种性能以及拥塞控制能力。通过在路由器中引入队列管理的拥塞控制算法，使网络本身也参与资源控制从而能有效的实现对拥塞的监测和预防。

4.1随机早期丢弃算法（RED）

RED是主动队列管理算法中早也是的一个，以RED算法为例来描述基于路由器技术拥塞控制的基本原理。RED算法通过平均队列长度预测可能到来的网络拥塞，并采用随机选择的策略对分组进行标记，在拥塞尚未出现时提示源端降低其发送速率以达到拥塞避免的目的。由于RED算法采用随机标记策略，使不同TCP流的拥塞异步化，因而解决了TCP流的全局同步问题。

RED算法采用指数加权平均算法来计算系统的平均队列长度，作为拥塞预测的依据，计算公式如下：

RED算法有效的避免了TCP流全局同步现象，提高了网络资源的利用率，并能有效地控制平均队列长度，使得系统吞吐率和分组时延达到很好的平衡，并采取一定的附加机制来保障系数的公平性。RED算法基于简单的控制机制，易于实现，因此也得到了广泛的认可和支持。但RED算法也存在一些缺点：对控制参数过于敏感，难以优化参数设定；不支持服务分区，没有考虑不同等级服务之间不同用户之间的差别，无法提供有效的公平性保障。

基于路由器技术的队列管理算法现今已经有很多中，例如：加权随机早期检测算法（WRED）,加权循环调度算法（WRR），公平排队算法（FQ），加权公平排队算法（WFQ）等，采用不同或者改进的算法来实现路由器的各种功能以及拥塞控制能力和QoS能力。

4.2缓冲管理和分组调度相结合

广义的队列管理，是指以队列为依托，对数据分组，数据流进行传输控制的多种机制，主要包括了缓冲管理和分组调度两方面的内容。图1给出了采用输入输出队列结构路由器中的分组处理流程。

图1输入输出排队路由器的分组处理流程

而目前，在绝大多数队列管理方案中，缓冲管理和分组调度都是分开进行的，缺乏一定的联系，使缓冲资源和带宽资源的分配相互独立，协作性差。而只有当缓冲资源与带宽资源的分配相一致时，才能的利用缓冲队列的特性，使得系统吞吐量和分组丢失率综合性能。因此，把缓冲管理和分组调度结合起来考虑，在缓冲管理算法中引入带宽分配是一个很有价值的研究方向。