论文部分内容阅读
摘要：RED算法采用随机丢弃策略，避免传统尾部丢弃方式而引起的TCP全局同步，同时通过控制队列的长度来抑制拥塞的发生
关键词：尾部丢弃；早期随机检测；拥塞避免
中图分类号：TP393.01 文献标识码：A文章编号：1009-3044(2007)05-11342-01
1 IP网络中的拥塞问题
拥塞避免技术通过监控网络流量负载情况，尽力在网络拥塞发生之前预计并且避免在普通的网路上拥塞的发生。这些技术用来为不同优先级别的流量种类提供处理，在发生拥塞的情况下使得网络的吞吐量和利用效率最大化，并且使报文丢弃和延迟最小化。
传统的路由器允许在拥塞发生时期将输出流量存放在缓冲区中。决定到达路由器输出端口的数据包是否接收到缓冲器的算法是单纯的FIFO队列法。FIFO队列根据数据包到达顺序将其接收到队列中，再根据到达的顺序从队列中送出。如果队列达到一定的长度，它后面到达的数据包就被丢弃。由于内存资源的有限，当队列的长度达到规定的最大长度时，所有到来的报文都被丢弃。在拥塞发生期间，队列尾部的数据包将被丢弃，直到拥塞解决。对于TCP报文，由于大量的报文被丢弃，将造成TCP超时，从而引发TCP的慢启动和拥塞避免机制，使TCP减少报文的发送。当队列同时丢弃多个TCP连接的报文时，将造成多个TCP连接同时进入慢启动和拥塞避免，称之为：TCP全局同步。这样多个TCP连接发向队列的报文将同时减少，使得发向队列的报文流量超过线路发送的速度，减少了线路带宽的利用。并且，发向队列的报文的流量总是忽大忽小，使线路上的流量总在极少和饱满之间波动。
为了避免拥塞，在网络没有发生拥塞以前根据队列状态进行有选择的丢包，当某个TCP连接的报文被丢弃，开始减速发送的时候，其他的TCP连接仍然有较高的发送速度。这样，无论什么时候，总有TCP连接在进行较快的发送，提高了线路带宽的利用率。随机早期检测（Random Early Detection， RED）就是这种用于早期避免拥塞的方法。本文探讨RED的原理极其在拥塞避免中的应用。
2 RED算法原理
早期随机检测算法是是目前最有名、应用最为广泛的拥塞避免算法。它的思想如下：
(1)如图1所示，为每个输入流设置一个队列。但每个出口链路都设有输出队列。
图1 RED输入输出队列
(2)在输入队列处定义两个阀值Lmin、Lmax。其中Lmin是最小队列阀值, Lmax是最大队列阀值。
(3)平均队列长度：
其中L为当前队列长度，WL为当前队列长度加权系数，满足0＜WL＜1，Rold为平均队列长度的先前估算值，Rnew为当前的平均队列长度。
(4)数据包丢弃率P（L）, P（L）是该队列的平均队列长度的线性函数。分组丢弃概率的计算公式如下：
P（L）=maxp×（Rnew－Lmin）/（Lmax－Lmin）
其中maxp是预先设置的标记(丢弃)概率，P（L）为当前分组标记概率的计算值。
图2 队列长度与数据包丢弃率
(5)每到达一个数据包就计算该队列的加权平均值。
如果 ≤Lmin，P（Lmin）=0，将到达的数据包接纳到队列中。
如果Lmin≤ ≤Lmax，则从队列中的随机地选出一个数据包，丢弃该数据包的被概率为P（L）。
如果Lmax≤ ，P（Lmax）=1，丢弃到达的数据包。
3 RED算法应用
RED算法基于平均队列长度预测可能到来的网络拥塞，并采用随机选择的策略对分组进行标记（或丢弃该分组，这是为了与早期TCP协议中拥塞控制机制相兼容），在拥塞尚未出现时提示端系统降低其发送速率，以达到避免拥塞的目的。同时，由于RED算法随机标记到达的数据分组，使不同TCP流的拥塞相应异步化，因而解决了TCP流的全局同步问题。
RED算法采用完全共享策略和单队列结构对到达的分组进行排队。分组到达时，RED算法采用指数加权平均算法计算系统当前的平均队列长度，作为拥塞预测的依据，并依此计算该分组的标记（或丢弃）概率。根据平均队列长度的计算公式：Rnew=（1－Wq）×Rold+ Wq×q
RED算法采用平均队列长度作为判断是否拥塞的依据，平滑了突发流量到来时对算法的影响。在网络流量突然增大的情况下，由于平均队列长度的计算采用指数平均算法，同时Wq参数的数值一般设置得较小，使得平均队列的长度变化得很缓慢，不会突然增大而导致大量分组丢弃，提高了系统对于突发流量的适应性。
RED算法设定两个控制阀值Lmin和Lmax, 当平均队列长度avg小于最小阀值Lmin时，所有到达分组都将被允许进入队列，当Rnew超过最大阀值Lmax时，所有到达分组将直接标记（或丢弃）；而当Rnew介于两个控制阀值之间时，将依据一定的概率标记（或丢弃）到达的分组。
从公式P （L） =maxp×（Rnew－Lmin）/（Lmax－Lmin）和图2可以看出，RED算法的丢弃概率随平均队列长度的变化满足分段线性关系。在算法的实际实现中，为了使被标记的分组散布得更均匀，对标记概率可以作一些修正，修正后的分组标记概率使得两次分组丢弃之间到达的分组个数满足平均分布，有效地平滑了分组的标记过程。
直接采用队列的长度和低限、高限比较并进行丢弃（这是队列的实际长度），将会对突发性的数据流造成不公正的待遇，不利于数据流的传输。所以，在和低限、高限比较并进行丢弃时，采用队列的平均长度。平均队列长度既反映了队列的变化趋势，又对队列长度的突发变化不敏感。避免了对突发性的数据流造成不公正的待遇。这里需要指出，平均队列长度与实际队列长度单位不同，不可简单比较。所配置的最大、最小阀值是用来和平均队列长度比较的。
同时需要注意的是，RED算法对控制参数敏感，难以优化参数设定。算法的性能对控制参数和网络流量负载的变化非常敏感。在用户流增大的情况下，RED算法的性能会急剧下降。
因此要想有效的运用这种算法，避免网络拥塞的发生。必须恰当的选择WL, Lmin, Lmax, maxp等参数。比如，
Wq≥0.001
Lmax≥2×Lmin
Lmin≥maxp
在此推荐以上设定方法。有关参数调节的详细内容请参考文献。[4]
图3是RED 算法效果的一个例子，表明尾部丢失与RED的平均队列长度的比较结果。有关尾部丢失与RED的平均队列长度的比较结果的详细内容请参考文献。[8]
从图3可以看出RED控制了队列的长度，其结果表明可以抑制拥塞的发生。
4 结论
RED算法采用随机丢弃策略，避免了尾部丢弃的方式而引起的TCP全局同步。通过设定队列的低限和高限。当队列的长度小于低限时，不丢弃队列。当队列的长度在低限和高限之间时，RED开始随机丢弃报文。队列的长度越长，丢弃的概率越高。当队列的长度大于高限时，丢弃所有到来的报文，最终通过控制队列的长度，来抑制拥塞的发生。
图3 尾部丢失与RED的平均队列长度的比较结果
参考文献：
[1]RFC 2474，Definition of the Differentiated Services Field (DSField) in the IPv4 and IPv6 Headers.
[2]B Nandy,J Ethridge,A Lakas,et al.Aggregate Flow Control: Improving Assurances for Differentiated Services［C］.Proc.of IEEE INFOCOM,2001.
[3]RFC 1633，Integrated Services in the Internet Architecture: An Overview.
[4]S.Floyd, V.Jacobson. Random early detection gateways for congestion avoidance, IEEE/ACM transaction on Networking vol.1,no. 4,pp. 399-408,Aug-95.
[5]S.Golestani.Network delay analysis of a class of fair queuing algorithms, IEEE J. SAC vol.13, no.6 Aug-95.
[6]Cisco System. Distributed weighted random early detection. http://cco.cisco.com.
[7]Floyd S, Jacobson A report on some recent developments in TCP congestion avoidance.
[8]RFC2309[105].
[9]任丰原.RED算法的稳定性:基于非线性控制理论的分析[J]. 计算机学报,2002,(12)：1302-1307.
[10]李琳.Internet上IP QoS的研究[J].计算机工程与设计, 2002,(5)：15-17.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：尾部丢弃；早期随机检测；拥塞避免
中图分类号：TP393.01 文献标识码：A文章编号：1009-3044(2007)05-11342-01
1 IP网络中的拥塞问题
拥塞避免技术通过监控网络流量负载情况，尽力在网络拥塞发生之前预计并且避免在普通的网路上拥塞的发生。这些技术用来为不同优先级别的流量种类提供处理，在发生拥塞的情况下使得网络的吞吐量和利用效率最大化，并且使报文丢弃和延迟最小化。
传统的路由器允许在拥塞发生时期将输出流量存放在缓冲区中。决定到达路由器输出端口的数据包是否接收到缓冲器的算法是单纯的FIFO队列法。FIFO队列根据数据包到达顺序将其接收到队列中，再根据到达的顺序从队列中送出。如果队列达到一定的长度，它后面到达的数据包就被丢弃。由于内存资源的有限，当队列的长度达到规定的最大长度时，所有到来的报文都被丢弃。在拥塞发生期间，队列尾部的数据包将被丢弃，直到拥塞解决。对于TCP报文，由于大量的报文被丢弃，将造成TCP超时，从而引发TCP的慢启动和拥塞避免机制，使TCP减少报文的发送。当队列同时丢弃多个TCP连接的报文时，将造成多个TCP连接同时进入慢启动和拥塞避免，称之为：TCP全局同步。这样多个TCP连接发向队列的报文将同时减少，使得发向队列的报文流量超过线路发送的速度，减少了线路带宽的利用。并且，发向队列的报文的流量总是忽大忽小，使线路上的流量总在极少和饱满之间波动。
为了避免拥塞，在网络没有发生拥塞以前根据队列状态进行有选择的丢包，当某个TCP连接的报文被丢弃，开始减速发送的时候，其他的TCP连接仍然有较高的发送速度。这样，无论什么时候，总有TCP连接在进行较快的发送，提高了线路带宽的利用率。随机早期检测（Random Early Detection， RED）就是这种用于早期避免拥塞的方法。本文探讨RED的原理极其在拥塞避免中的应用。
2 RED算法原理
早期随机检测算法是是目前最有名、应用最为广泛的拥塞避免算法。它的思想如下：
(1)如图1所示，为每个输入流设置一个队列。但每个出口链路都设有输出队列。
图1 RED输入输出队列
(2)在输入队列处定义两个阀值Lmin、Lmax。其中Lmin是最小队列阀值, Lmax是最大队列阀值。
(3)平均队列长度：
其中L为当前队列长度，WL为当前队列长度加权系数，满足0＜WL＜1，Rold为平均队列长度的先前估算值，Rnew为当前的平均队列长度。
(4)数据包丢弃率P（L）, P（L）是该队列的平均队列长度的线性函数。分组丢弃概率的计算公式如下：
P（L）=maxp×（Rnew－Lmin）/（Lmax－Lmin）
其中maxp是预先设置的标记(丢弃)概率，P（L）为当前分组标记概率的计算值。
图2 队列长度与数据包丢弃率
(5)每到达一个数据包就计算该队列的加权平均值。
如果 ≤Lmin，P（Lmin）=0，将到达的数据包接纳到队列中。
如果Lmin≤ ≤Lmax，则从队列中的随机地选出一个数据包，丢弃该数据包的被概率为P（L）。
如果Lmax≤ ，P（Lmax）=1，丢弃到达的数据包。
3 RED算法应用
RED算法基于平均队列长度预测可能到来的网络拥塞，并采用随机选择的策略对分组进行标记（或丢弃该分组，这是为了与早期TCP协议中拥塞控制机制相兼容），在拥塞尚未出现时提示端系统降低其发送速率，以达到避免拥塞的目的。同时，由于RED算法随机标记到达的数据分组，使不同TCP流的拥塞相应异步化，因而解决了TCP流的全局同步问题。
RED算法采用完全共享策略和单队列结构对到达的分组进行排队。分组到达时，RED算法采用指数加权平均算法计算系统当前的平均队列长度，作为拥塞预测的依据，并依此计算该分组的标记（或丢弃）概率。根据平均队列长度的计算公式：Rnew=（1－Wq）×Rold+ Wq×q
RED算法采用平均队列长度作为判断是否拥塞的依据，平滑了突发流量到来时对算法的影响。在网络流量突然增大的情况下，由于平均队列长度的计算采用指数平均算法，同时Wq参数的数值一般设置得较小，使得平均队列的长度变化得很缓慢，不会突然增大而导致大量分组丢弃，提高了系统对于突发流量的适应性。
RED算法设定两个控制阀值Lmin和Lmax, 当平均队列长度avg小于最小阀值Lmin时，所有到达分组都将被允许进入队列，当Rnew超过最大阀值Lmax时，所有到达分组将直接标记（或丢弃）；而当Rnew介于两个控制阀值之间时，将依据一定的概率标记（或丢弃）到达的分组。
从公式P （L） =maxp×（Rnew－Lmin）/（Lmax－Lmin）和图2可以看出，RED算法的丢弃概率随平均队列长度的变化满足分段线性关系。在算法的实际实现中，为了使被标记的分组散布得更均匀，对标记概率可以作一些修正，修正后的分组标记概率使得两次分组丢弃之间到达的分组个数满足平均分布，有效地平滑了分组的标记过程。
直接采用队列的长度和低限、高限比较并进行丢弃（这是队列的实际长度），将会对突发性的数据流造成不公正的待遇，不利于数据流的传输。所以，在和低限、高限比较并进行丢弃时，采用队列的平均长度。平均队列长度既反映了队列的变化趋势，又对队列长度的突发变化不敏感。避免了对突发性的数据流造成不公正的待遇。这里需要指出，平均队列长度与实际队列长度单位不同，不可简单比较。所配置的最大、最小阀值是用来和平均队列长度比较的。
同时需要注意的是，RED算法对控制参数敏感，难以优化参数设定。算法的性能对控制参数和网络流量负载的变化非常敏感。在用户流增大的情况下，RED算法的性能会急剧下降。
因此要想有效的运用这种算法，避免网络拥塞的发生。必须恰当的选择WL, Lmin, Lmax, maxp等参数。比如，
Wq≥0.001
Lmax≥2×Lmin
Lmin≥maxp
在此推荐以上设定方法。有关参数调节的详细内容请参考文献。[4]
图3是RED 算法效果的一个例子，表明尾部丢失与RED的平均队列长度的比较结果。有关尾部丢失与RED的平均队列长度的比较结果的详细内容请参考文献。[8]
从图3可以看出RED控制了队列的长度，其结果表明可以抑制拥塞的发生。
4 结论
RED算法采用随机丢弃策略，避免了尾部丢弃的方式而引起的TCP全局同步。通过设定队列的低限和高限。当队列的长度小于低限时，不丢弃队列。当队列的长度在低限和高限之间时，RED开始随机丢弃报文。队列的长度越长，丢弃的概率越高。当队列的长度大于高限时，丢弃所有到来的报文，最终通过控制队列的长度，来抑制拥塞的发生。
图3 尾部丢失与RED的平均队列长度的比较结果
参考文献：
[1]RFC 2474，Definition of the Differentiated Services Field (DSField) in the IPv4 and IPv6 Headers.
[2]B Nandy,J Ethridge,A Lakas,et al.Aggregate Flow Control: Improving Assurances for Differentiated Services［C］.Proc.of IEEE INFOCOM,2001.
[3]RFC 1633，Integrated Services in the Internet Architecture: An Overview.
[4]S.Floyd, V.Jacobson. Random early detection gateways for congestion avoidance, IEEE/ACM transaction on Networking vol.1,no. 4,pp. 399-408,Aug-95.
[5]S.Golestani.Network delay analysis of a class of fair queuing algorithms, IEEE J. SAC vol.13, no.6 Aug-95.
[6]Cisco System. Distributed weighted random early detection. http://cco.cisco.com.
[7]Floyd S, Jacobson A report on some recent developments in TCP congestion avoidance.
[8]RFC2309[105].
[9]任丰原.RED算法的稳定性:基于非线性控制理论的分析[J]. 计算机学报,2002,(12)：1302-1307.
[10]李琳.Internet上IP QoS的研究[J].计算机工程与设计, 2002,(5)：15-17.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。