摘   要： 拥塞控制和避免机制是实现Internet服务质量的重要保证。本文在详细分析了随机早期检测算法的基础上，提出一种基于拥塞等级的改进方案CLRED算法。通过仿真实验对RED和CLRED算法在标准化吞吐量、分组丢失及排队延迟方面的性能进行了对比。
关键词： 拥塞控制和避免  随机早期检测  拥塞等级  分组丢弃

　　网络用户数量及其应用的爆炸式增长，造成网络结构日趋复杂、网络信息量急骤增加以及突发性信息量频繁产生，这些情况都会使网络瞬间产生拥塞。因此需要一定的拥塞控制机制来加以约束和限制。为在网络中提供真正意义的服务质量（Quality of Services，QoS）[1]保证，主动队列管理（Active Queue Management，AQM）[2]以及拥塞控制策略的研究及改进一直是业内研究的重点。
1  随机早期检测算法
　　传统的队列管理采用尾丢弃算法，容易造成全局同步和缓冲区易被填满等问题。随机早期检测（Random Early Detection，RED）是由Sally Floyd和Van Jacobson[3]提出的一种拥塞避免机制，是一种积极的队列管理技术，旨在提供比传统的尾丢弃方式更佳的性能。因此IETF推荐RED算法作为下一代网络默认的算法。RED算法的基本思想是路由器通过计算平均队列长度avg和设置2个缓冲阈值max和min提前检测到拥塞。
　　avg是时间t的函数，是实现积极丢弃分组的控制变量，定义为：
　　avg(t)=(1-w)avg(t-1)+wq(t)
　　avg(t)是在t时刻的平均队列长度，q(t)是在t时刻的队列长度，w是计算平均队列长度的加权参数。分组丢弃概率p的计算公式为：
　　p=P_max(avg-min)/(max-min)
　　RED算法分组丢失概率曲线图如图1所示。当avg≥min时，以概率p来丢弃分组，而不是等到队列完全填满之后才开始丢弃。p随着avg的增加而线性增大，因此通过丢弃更多的分组来控制平均队列长度。当avg≥max时，将以最大丢弃概率P_max丢弃分组，所以avg被严格控制在最大阈值之下。由于被丢弃的分组来源于不同的主机且是随机丢弃，从而避免了全局同步。分组丢失同时意味着向TCP源发出减缓信号，使TCP流进入缓慢启动模式，以降低注入网络的流量。

　　虽然RED算法能有效避免拥塞，但是该算法仍存在不足，如对参数设置敏感，需要有足够的缓冲空间，多个流不能公平地共享带宽等。因此，自RED算法提出之后，围绕着提高其性能的各个方面(如吞吐量、延迟/抖动、时间响应、流量稳定性和公平性等)做了大量工作。
2  基于拥塞等级的RED改进算法
2.1 CLRED算法的提出
　　在RED算法中，实际上当avg≥min时，网络就进入了轻度拥塞状态。本文提出的CLRED（Congestion Level-Based Random Early Detection）算法的基本思想就是把拥塞程度详细地划分为若干个等级，根据不同的拥塞等级p增加的程度也不同，即当拥塞等级较大时，p增加的也较大，就能及时地通过调整p来丢弃更多的分组，从而就能更快地调整队列长度，也就能更及时、准确地控制拥塞。理论上划分的等级越多，就能越准确地描述拥塞程度，但这同时也增加了计算p的时间。划分的等级数由ISP根据用户要求的QoS来决定，即用户的QoS要求越高，其拥塞程度划分得越细，反之亦然。
2.2 CLRED算法描述
　　设有n+1个拥塞等级：L₀，L₁，……L_n。其中，L₀表示无拥塞，L₁表示轻度拥塞，以此类推，L_n拥塞程度最大，表示进入完全拥塞，此时所有到达的数据分组都将被丢弃。设avg的增加量为：
　　

2.3 性能分析
　

　　分组丢弃概率曲线如图2所示。从图2中可以看出，丢弃概率函数的斜率随着拥塞等级变化而变化。随着拥塞程度的加深，CLRED丢弃概率增加更快，向源发出拥塞警告的速度也同时变大，因而拥塞比RED更有效地减小了，队列就会有效地下降，从而降低排队延迟。

3  仿真实验
3.1 仿真拓扑结构
　　Linux操作系统下用ns-2网络仿真软件对算法进行了仿真比较，采用仿真软件中关于区分服务[4]的配置，同时对底层的相关进程进行修改。实验采用的仿真拓扑结构如图3所示，2个边界路由器E1和E2以及2个核心路由器C1和C2构成一个简单的网络。路由器之间的链路带宽除C1-C2链路带宽为10Mbps外，E1-C1和C2-E2链路带宽均为100Mbps，源节点S1和S2发出的聚集流经区分服务网络到达目的节点D1和D2。由于在C1-C2处形成瓶颈，在C1处的聚集流产生拥塞，分别以RED和CLRED算法丢弃分组。在仿真实验中，RED和CLRED算法的平均队列长度的最大和最小值分别为20和6个分组的长度，P_max分别为0.1和1，加权参数w=0.05。

3.2 仿真结果
　　仿真运行500秒(时间足够用于完成所有数据流的分类及转发)，在瓶颈处形成拥塞，从而导致丢弃分组。C1处聚集流的标准化吞吐量、排队延迟、分组丢失率，其仿真结果比较如表1所示。TCP发送端开始发送分组的时候没有拥塞发生，因此转发的分组没有被丢弃。然而，当越来越多的分组注入网络时，即有拥塞发生，路由器队列迅速建立，并根据AQM算法来丢弃分组。由于CLRED算法比RED算法丢失的分组少，所以标准化吞吐量比RED算法高，同时分组丢失少意味着长时间内队列长度的值要小一些，或者说长时间内网关的排队延迟的值更小。结果表明，CLRED算法在标准化吞吐量、分组丢失以及排队延迟方面都优于RED算法。

4  结论及展望
　　本文提出了一种基于拥塞等级的RED改进算法——CLRED算法。该算法把拥塞程度详细划分为若干个等级。产生拥塞时，不同的拥塞等级分组丢失的程度不同。仿真结果表明，CLRED算法在标准化吞吐量、分组丢失以及排队延迟方面都优于RED算法。但是在拥塞等级划分比较多的情况下，CLRED算法的p值计算较复杂。后期将考虑简化计算，即在拥塞程度划分为尽可能多的等级和简化p的计算之间找到一个平衡点，使区分服务网络能根据用户的需要调整拥塞等级，以保证QoS。关于RED的改进方法有很多，CLRED算法仅从拥塞等级这个角度对其进行了改进，AQM算法的研究及改进将一直是业内研究的重点。
参考文献
1   Eder M，Chaskar H，Nag N S.Considerations from the Service Management Research Group(SMRG) on Quality of Service(QoS) in the IP Network.RFC3387，2002
2   Braden B，Clark D，Crowcroft J et al.Recommendations on Queue Management and Congestion Avoidance in the Internet.RFC 2309，1998
3   Floyd S，Jacobson V.Random Early Detection Gateways for  Congestion Avoidance.IEEE/ACM Transaction on Networks，1993；(4)
4   Blacke S，Black D，Carison M et al.An Architecture for Differentiated Services.IETF RFC 2475，1998