摘要：本文首先阐述了计算机网络中拥塞的定义、拥塞产生的原因以及经常提起的拥塞控制的定义。中间阐述了目前使用最多的拥塞控制算法FIFO算法和RED算法，最后提出了这两个算法的改进思想。
关键字：IP拥塞算法改进

一、概述

1.拥塞定义

当网络中存在过多的数据包时，网络的性能就会下降，这种现象称为拥塞。在网络发生拥塞时，会导致吞吐量下降，严重时会发生“拥塞崩溃”（congestioncollapse）现象。一般来说，在网络负载的增加导致网络效率的降低的时候，就会发生拥塞崩溃。Floyd总结出拥塞崩溃主要包括以下几种[[1l:传统的崩溃、未传送数据包导致的崩溃、由于数据包分段造成的崩溃、日益增长的控制信息流造成的崩溃等。

2.拥塞产生的原因

网络产生的拥塞的根本原因在于用户（或叫端系统）提供给网络负载大于网络资源容量和处理能力，表现为数据包延时增加、丢弃概率增大、上层应用系统性能下降。拥塞产生的直接原因有以下三点:

（1）存储空间不足。几个输入数据流共同需要同一个输入端口，在这个端口就会建立排队，如果没有足够的存储空间，数据包就会丢弃，对突发数据流更是如此。增加存储空间在一定程度上可以缓解这一矛盾，但如果路由器有无限存储量，拥塞只可能变得更坏，而不是更好。因为网络里的数据包经过长时间排队后才通过路由器完成转发，会浪费网络资源，加重网络拥塞。

（2）带宽容量不足，低速链路对高速数据流的输入也会产生拥塞。根据香农信息理论，任何信道带宽最大值（即信道容量）为C=Blog2（1+S/N）（其中N为信道白噪声的平均功率，S为信源的最大功率，B为信道带宽）。所有信源发生的速率R必须小于或等于信道容量C，如果R>C，则在理论上无差错传输就是不可能的。所以在网络低速链路处就会形成带宽瓶颈，当其满足不了所有信源带宽要求时，网络就会发生拥塞。

（3）处理器能力弱、速度慢，也能引起拥塞。如果路由器的CPU在执行排队缓存，更新路由表等功能时，处理速度跟不上高速链路，也会产生拥塞。同样，低速链路对高速CPU也会产生拥塞。

3.拥塞控制的定义

拥塞控制就是采用某种策略或机制，保持网络工作在正常的状态下，也就是使网络经常工作在崖点左侧的区域内。若一种控制机制使得网络工作在膝点附近，该方法称之为拥塞避免若一种控制机制是的网络工作在崖点或崖点以后的网络回复至膝点前后，该方法称之为拥塞恢复。

因此拥塞控制策略包括拥塞避免（congestionavoidance）和拥塞控制（congestioncontrol）这两种不同的控制机制。拥塞避免是“预防”机制，它的目标是避免网络进入拥塞状态，使网络运行在高吞吐量、低延迟的状态下。拥塞控制是“恢复”机制，它用于把网络从拥塞状态中恢复出来。

二、计算机网络中IP拥塞控制算法

1.FIFO算法

FIFO又叫“先到先服务”（FCFS），即第一个到达路由器的数据包首先被传输。由于每个路由器的缓存总是有限的，如果包到达时缓存己满，那么路由器就不得不丢弃该包。这种做法没有考虑被丢弃包的重要程度。由于FIFO总是丢弃到达队尾的包，所以有时又称为“去尾”（droptail）算法。但“去尾”和FIFO是两个不同的概念。FIFO是一种包调度策略，决定包传送的顺序:“去尾”是一种丢弃策略，决定哪些包被丢弃。因为FIFO和“去尾”分别是最简单的包调度和丢弃策略，所以两者有时被视为一体，甚至有时就简单称为FIFO排队。

2.RED算法

RED算法包含两部分:如何监控队列长度和何时丢弃数据包。

首先，RED使用类似TCP计算超时时使用的权值Weight来计算平均排队长度Qe，即：

Qe=（1-Weight）Qe+WeightSampleQe
其中，Weight是滤波系数，0<Weight<1，SampleQe是即时采样的队列长度。

RED有两个阀值:Qmin和Qmax。当一个数据包到达路由器时，RED将当前Qe和这两个阀值按以下原则比较:如果Qe<Qmax时，将此包排队如果

Qmin<Qe<Qmax，计算丢弃概率P，并以P丢弃此包；如果Qmax<Qe，则丢弃此包。这种规则意味着如果平均队长小于较低的阂值，路由器不会采取任何措施，如果平均队长大于高阀值，数据包都要被丢弃，如果平均队长介于两者之间，新到数据包就要以某个概率P丢弃。显然，丢弃概率P在Qe处于两个阀值之间时缓慢增加，在Qmax到达最大值MaxP。当然，也有一些研究建议从随机丢弃到完全丢弃的过渡应该更“平滑”。

三、算法改进

1.对FIFO的改进

FIFO排队的主要问题是无法区分不同的数据流。由于整个TCP的拥塞控制是在源端执行，而FIFO排队不提供约束所有数据源遵守拥塞控制的机制，这就有可能让行为不良的数据流强占大量带宽。在Internet环境中，某个应用不使用TCP协议是完全可能的。结果，它可以绕开端到端的拥塞控制机制，向路由器任意发送自己的数据包，从而引起其它应用的包被丢弃。

公平排队算法（FairQueuingFQ）则解决了这个问题。FQ算法是一种“轮询”（roundrobin，RR）的调度算法。在FQ算法中，路由器对每个输出线路有一个排队队列。路由器按“轮询”（roundrobin）方式处理包。当一条线路闲时，路由器就来回扫描所有队列，依次将每队第一个包发出。当某个流的数据包到达过快时，其队列就会很快占满，属于这个流的新到的包就会被丢弃。采用这种方式，每个数据流就不可能牺牲其它数据流而多占资源。 www.lunwenwang.com 论文网在线

另外，FQ算法并没有告知源端路由器状态的机制，也就是说，FQ仍然要依赖于端到端的拥塞控制机制。它只是将数据流分隔，使不遵守拥塞控制机制的数据流不至于影响其它流。所以它在.没有牺牲统计复用的情况下提供了公平性，与端到端的拥塞控制机制也可以较好地协同。加权公平排队算法（WeightedFairQueuing，WFQ）是FQ的改进算法。WFQ对每个流（排队）分配一个权值。这个权值决定了路由器每次发往该队列的比特数量，从而控制数据流得到的带宽。将所有权值看成1，那么FQ也是一种特殊的WFQ。权值的分配往往对应不同优先级的数据流，例如用IP包头中TOS域指定流的优先级，排队时再按优先级分配权值。这也是区分服务的思想。WFQ中权值可以由路由器自己决定，也可以由源端通过某种信令通知路由器来决定。

总之，WFQ根据不同数据流应用的不同带宽要求，对每个排队队列采用加权方法分配缓存资源，从而增加了FQ对不同应用的适应性。

2.对RED的改进

LRED算法把LossRatio引入到RED的丢弃概率的计算中，对RED的鲁棒性有一定改进，但链路利用率考虑不够VRC算法对队列长度进行规范，获得了高的链路利用率，也具有快速的响应速度，但其鲁棒性欠缺。在综合考虑RED，PI，REM，LRED及其他RED改进算法存在问题的基础上，本文结合LRED（基于丢失率的随机及早检测）与VRC（虚拟速率控制）算法的优缺点，介绍一种新的AQM算法:LRC——RED算法。鉴于文章篇幅问题，LRED算法和VRC算法就不再次累赘了，读者可以参考文献4和5。

算法实现如下：

周期性地计算丢失比率，令l（k）为最近M个测量周期内的丢失包的比率，即可表示为在最近M个周期被丢弃的数据包的数目与总的到达的数据包的数目的比率，表示为

 接着需要利用瞬时队列长度和总的输入速率来设计计算数据包的丢包率的函数.此函数必须满足:当队列长度和总的输入速率在各自的目标值附近抖动时，丢包率应该尽可能地接近被测丢失率.结合LRED和VRC算法的思想，设计了如下简单的丢包率方程:
 

优点：同时稳定到目标队列值和瓶颈队列的链路带宽值,并把单个丢包率同整体数据丢失率联系在一起。

参考文献：

[1]罗万明，林闯，阎宝平.TCP/IP拥塞控制研究[J]，计算机学报，2001

[2]刘秋让，倪洪波.TCP拥塞控制解决方法分析及评价[J]，计算机工程，2001

[3]邓亚平，叶凌伟，陈雁.TCP/IP拥塞控制算法的改进[J]，计算机科学，2001

[4]WangChonggang,LiBin,HouYT,etal.LRED:aroustactivequeuemanagementschemebasedon

packetlossratio[J].IEEE/ACMTransactionNet-working,2004

[5]ParkEun-Chan,LimHyuk,ParkKyung-Joo,etal.AnalysisofthevirtualratecontrolalgorithminTCPnetworks[J].IEEE/ACMTransactionNetworking,2004<Weight<1，SampleQe是即时采样的队列长度。RED有两个阀值:Qmin和Qmax。当一个数据包到达路由器时，RED将当前Qe和这两个阀值按以下原则比较:如果Qe<Qmax时，将此包排队如果Qmin<Qe<Qmax，计算丢弃概率P，并以P丢弃此包；如果Qmax<Qe，则丢弃此包。这种规则意味着如果平均队长小于较低的阂值，路由器不会采取任何措施，如果平均队长大于高阀值，数据包都要被丢弃，如果平均队长介于两者之间，新到数据包就要以某个概率P丢弃。显然，丢弃概率P在Qe处于两个阀值之间时缓慢增加，在Qmax到达最大值MaxP。当然，也有一些研究建议从随机丢弃到完全丢弃的过渡应该更“平滑”。三、算法改进1.对FIFO的改进FIFO排队的主要问题是无法区分不同的数据流。由于整个TCP的拥塞控制是在源端执行，而FIFO排队不提供约束所有数据源遵守拥塞控制的机制，这就有可能让行为不良的数据流强占大量带宽。在Internet环境中，某个应用不使用TCP协议是完全可能的。结果，它可以绕开端到端的拥塞控制机制，向路由器任意发送自己的数据包，从而引起其它应用的包被丢弃。公平排队算法（FairQueuingFQ）则解决了这个问题。FQ算法是一种“轮询”（roundrobin，RR）的调度算法。在FQ算法中，路由器对每个输出线路有一个排队队列。路由器按“轮询”（roundrobin）方式处理包。当一条线路闲时，路由器就来回扫描所有队列，依次将每队第一个包发出。当某个流的数据包到达过快时，其队列就会很快占满，属于这个流的新到的包就会被丢弃。采用这种方式，每个数据流就不可能牺牲其它数据流而多占资源。另外，FQ算法并没有告知源端路由器状态的机制，也就是说，FQ仍然要依赖于端到端的拥塞控制机制。它只是将数据流分隔，使不遵守拥塞控制机制的数据流不至于影响其它流。所以它在.没有牺牲统计复用的情况下提供了公平性，与端到端的拥塞控制机制也可以较好地协同。加权公平排队算法（WeightedFairQueuing，WFQ）是FQ的改进算法。WFQ对每个流（排队）分配一个权值。这个权值决定了路由器每次发往该队列的比特数量，从而控制数据流得到的带宽。将所有权值看成1，那么FQ也是一种特殊的WFQ。权值的分配往往对应不同优先级的数据流，例如用IP包头中TOS域指定流的优先级，排队时再按优先级分配权值。这也是区分服务的思想。WFQ中权值可以由路由器自己决定，也可以由源端通过某种信令通知路由器来决定。总之，WFQ根据不同数据流应用的不同带宽要求，对每个排队队列采用加权方法分配缓存资源，从而增加了FQ对不同应用的适应性。2.对RED的改进LRED算法把LossRatio引入到RED的丢弃概率的计算中，对RED的鲁棒性有一定改进，但链路利用率考虑不够VRC算法对队列长度进行规范，获得了高的链路利用率，也具有快速的响应速度，但其鲁棒性欠缺。在综合考虑RED，PI，REM，LRED及其他RED改进算法存在问题的基础上，本文结合LRED（基于丢失率的随机及早检测）与VRC（虚拟速率控制）算法的优缺点，介绍一种新的AQM算法:LRC——RED算法。鉴于文章篇幅问题，LRED算法和VRC算法就不再次累赘了，读者可以参考文献4和5。算法实现如下：周期性地计算丢失比率，令l（k）为最近M个测量周期内的丢失包的比率，即可表示为在最近M个周期被丢弃的数据包的数目与总的到达的数据包的数目的比率，表示为接着需要利用瞬时队列长度和总的输入速率来设计计算数据包的丢包率的函数.此函数必须满足:当队列长度和总的输入速率在各自的目标值附近抖动时，丢包率应该尽可能地接近被测丢失率.结合LRED和VRC算法的思想，设计了如下简单的丢包率方程:优点：同时稳定到目标队列值和瓶颈队列的链路带宽值,并把单个丢包率同整体数据丢失率联系在一起。参考文献：[1]罗万明，林闯，阎宝平.TCP/IP拥塞控制研究[J]，计算机学报，2001[2]刘秋让，倪洪波.TCP拥塞控制解决方法分析及评价[J]，计算机工程，2001[3]邓亚平，叶凌伟，陈雁.TCP/IP拥塞控制算法的改进[J]，计算机科学，2001[4]WangChonggang,LiBin,HouYT,etal.LRED:aroustactivequeuemanagementscheme
basedonpacketlossratio[J].IEEE/ACMTransactionNet-working,2004[5]ParkEun-Chan,LimHyuk,ParkKyung-Joo,etal.AnalysisofthevirtualratecontrolalgorithminTCPnetworks[J].IEEE/ACMTransactionNetworking,2004