基于特征分析方法消解RED冗余参数*

吴 斌，马继涛，邬 平，谭 鹏

(云南省科学技术情报研究院，云南 昆明 650051)

基于特征分析方法消解RED冗余参数*

吴 斌，马继涛，邬 平，谭 鹏

(云南省科学技术情报研究院，云南 昆明 650051)

RED算法是网络拥塞控制的基础算法，加载算法需要设置队列平均长度、队列丢包上下限阈值、数据包平均尺寸等多项参数，且参数设置没有明确的规则限制和理论依据，不合理的参数值会削弱算法的拥塞控制效果。在网络拥塞特征分析的基础上，挖掘数据包达到速率和数据包处理速度两个拥塞控制指标之间的关系，建立指标与RED算法参数的映射，消解多余参数并确定参数值域范围，改善算法在网络环境中的拥塞控制效果，提高算法的实用性。

随机早期侦测；特征方程；拥塞控制；线性映射

1 引言

随机早期侦测RED(Random Early Detection)是网络拥塞控制经典算法，其主要设计思路是在平均队列长度和网络拥塞程度之间建立分段函数，通过概率方法控制队列数据包的丢弃行为，将平均队列长期稳定于拥塞控制范围，最终达到拥塞控制的目的[1]。RED算法在实际应用中面临的难点是参数的动态控制与调整以适应网络状态，其原因在于几个具有耦合关系的参数对不同网络状态很敏感，若参数设置不当将削弱算法网络拥塞控制能力，降低网络整体性能[2～5]。

近年来，众多学者针对这一难点提出了许多新的理论方法。文献[2]利用非线性滑模控制方法解决线性方法不能准确跟踪网络动态变化问题，避开系统输入受限问题，存在缓冲区溢出的可能性。文献[3]基于TCP自同步特性改进RED算法，获得比原有算法更宽松的参数设置范围，但没有对参数取值合理性进行分析，参数对网络状态敏感问题仍旧存在。文献[4]利用数学期望分析TCP/RED拥塞控制机制离散模型稳定状态行为，推导网络稳定状态期望值与参数解析关系式、算法配置及应用难度较大。文献[5]利用二次圆函数计算丢包概率，减少算法中最大丢弃概率maxp与队列qmax两项参数，没有综合考虑其参数的耦合性。为此，本文将利用特征分析方法建立网络状态特征方程，基于工程经验消解冗余参数。

2 网络拥塞特征分析

2.1 拥塞分析

网络拥塞通常发生于宽带链路与窄带链路的连接点，由于节点处数据包处理能力有限，当链路数据包到达速率大于节点处数据包处理速率，队列缓存出现累积效应；若单位时间内数据到达速率远远大于节点处数据包处理速率，可能发生Floyd S等人[6]于1999年所论述的拥塞崩溃现象。

若要在时间t内避免拥塞崩溃，网络节点处数据包到达率(dμ(t)/dt)减数据包离开率(dυ(t)/dt)与数据队列缓存长度(dl(t)/dt)之和应小于或等于物理缓存长度L：

(1)

2.2 网络数据包到达及处理分析

(1)网络数据包到达分布。

由于网络数据包具有突发特性，且在单位时间内到达的数据包与起始时间无关，只与时间长度有关，数据包到达数量呈非线性单调增加，满足泊松流分布特性[7]。根据泊松流定义网络数据包到达分布：

(2)

网络节点处数据包到达率为λe-λt，在t时间内平均到达数据包个数mi的期望值：

(3)

(2)网络节点数据包处理时间分布。

网络节点数据包处理时长与数据包到达时间分布无关，即到达过程与处理过程相互独立。为方便量化处理过程，我们将网络节点视同为黑盒[8]，单位时间内离开数据包速率作为衡量数据包处理性能指标。由于节点数据包处理速度为常量，数据包处理时间满足均匀分布[9]：

(4)

在t时间内平均离开的数据包个数ni的期望：

(5)

(3)队列缓存长度时间分布。

队列缓存长度时间分布与网络数据包到达分布、网络节点数据包的处理时间分布具有相关联系。设节点处缓存容限无限大(L→∞)，以网络节点数据包处理时间为单位时间(t)，则n个单位时间长度(T=nt)范围内三者关系如式(6)所示：

(6)

3 RED冗余参数消解

3.1 参数说明

网络节点加载RED拥塞算法需要设置队列平均长度、队列丢包上下限阈值、数据包平均尺寸等多项参数[10]，参数说明见表1。

Table 1 Arguments of the algorithm表1 算法参数说明表

队列中设置数据包下限阈值(min)和上限阈值(max)，旨在界定一个合理范围，使网络在不同拥塞程度有不同的丢弃概率，丢弃概率与拥塞程度成线性关系。

3.2 参数说明

RED算法将拥塞程度(D)与队列平均长度相关联[11]，我们认为拥塞程度与网络发生拥塞的可能成正比，因此采用分段表示拥塞程度：

(7)

首先，根据式(7)的定义，当队列占满时到达数据包将被全部丢弃，此刻丢弃概率为1，而队列为空时丢弃概率为0。若将min与max直接与平均队列长度映射会使算法在无拥塞情况下也产生丢包行为。为保证算法可用性，借鉴前人实验结果[12]，当平均队列大于75%时网络节点有拥塞发生的可能，将可用队列缓存长度与拥塞发生区间进行线性映射，消解min、max和probability三个参数。

其次，网络节点数据包处理能力有限，数据包平均处理时长等于节点数据包处理速度与网络平均封包之商。根据工程经验[13]，节点数据包处理速度在队列缓冲区饱和情况下趋近于节点上行网络速率，这意味着在网络拥塞可能发生的情况下，可将节点数据包平均处理速度与节点数据包离开速度等同处理。

第三，网络队列长度取值太大则增加网络延迟，太小又容易增加数据包的丢弃数量[14]。Internet数据包传输容忍延迟为300 ms[15]，缓存队列长度取值根据节点网络接口数据包发送速率、数据包传输容忍延迟以及数据包平均尺寸计算，消解参数limit。

最后，为减少数据丢弃概率计算的频率，算法采用burst参数对每轮计算的队列平均长度进行调整。我们假定网络处理数据单位时间内丢弃概率不变时，平均队列长度进入max与min区域，基于二分法消解burst。

消解步骤具体如下：

步骤1消解缓存队列长度参数，计算式：limit=bandwidth×0.3/(avpkt×8)；

步骤2消解队列上下限阈值参数，计算式：max=limit以及min=limit×75%；

步骤3消解突发数据包参数，计算式：burst=limit/2(max-min) ×bandwidth/avpkt；

冗余参数消解后，加载RED拥塞控制算法只需要取值实际物理网络接口的连接速率以及网络数据包平均尺寸，降低了RED应用的难度。

4 参数验证

4.1 验证方法

为了验证算法消解后的参数能否对不同网络出现的拥塞现象进行有效控制，我们在Opnet仿真环境中模拟网络路由节点两端不同宽/窄带宽链路，包括小型企业接入(100M局域网-2MADSL租用线路)、组织机构接入(100M局域网-10M光纤租用线路)和大中型企业接入(100M局域网-100M光纤租用线路)三种常见环境，人为制造网络拥塞现象(设置ecn为0值，即发生拥塞时节点不通知远程主机发包速率过快)。从网络延迟、丢包率两个方面来验证bandwidth和avpkt两个参数的RED算法在发生拥塞时网络响应能保持一个可容忍的范围，具体配置见表2。

Table 2 Simulation configuration forarguments test of the algorithm表2 算法参数验证仿真配置

利用参数消解计算的数值与前人经验设置范围趋同[17, 18]，参数消解方法对于不同网络具有较好的适应性。

4.2 实验结果分析

为能实际反映算法对于三种不同网络连接时拥塞参数的控制效果，选择节点窄带链路的网络延迟、RED平均队列、链路利用率、数据包接收速率和数据包丢弃速率进行测量。

(1)100 M Ethernet-2 M ADSL(见图1)。

仿真测试环境数据发送时间长度为150 s，2分钟网络延迟增加到300 ms左右；RED平均队列长度达到76，与max参数设置趋同；链路利用率为100%，网络发生拥塞，数据包丢弃率为40包/s，接收率为250包/s，丢弃率为40/(250+40)≅13%，300 ms延迟为数据包传输容忍延迟，说明网络发生拥塞时，网络仍能保持通信，算法参数的取值较好地适应了网络环境，没有引起取值不当导致网络拥塞现象发生[19]。

Figure 1 100 M-2 M congestion control test图1 100 M-2 M 拥塞控制测试

(2)100 M Ethernet-10 M Ethernet(见图2)。

在数据源发送速率不变的情况下，链路利用率只有25%，此时网络处于不饱和状态，因此算法没有以概率方式丢弃数据包，避免了网络链路不饱和时算法强制丢包的现象，此时网络延迟为6 ms。算法运行于节点中，增加了节点数据包处理的负荷，传输延迟较网络空闲时略有增加。

Figure 2 100 M-10 M congestion control test图2 100 M-10 M 拥塞控制测试

(3)100 M Ethernet-100 M Ethernet(见图3)。

当数据源发送速率不变且节点两端均为100 M连接时，链路利用率几乎为零，链路带宽处于空闲状态，RED平均队列为0，说明到达数据包被立即处理，无丢包现象发生，此时网络传输延迟为4 ms，RED算法不干预传输过程。

Figure 3 100 M-100 M congestion control test图3 100 M-100 M 拥塞控制测试

5 结束语

通过特征分析拥塞控制指标与参数之间关系，通过映射方法消解RED算法中队列缓存长度、队列丢弃上/下限阈值、数据包丢弃概率及突发传输的数据包五个需专家经验才能配置的复杂参数项。算法仅需配置网络数据包平均尺寸和节点处的网络接口连接速率两个参数，降低了RED算法在传统应用中的人工干预，提高了算法的适用性。实验表明，进行参数消解后的算法能够适应不同网络环境需要，在保障RED算法拥塞控制效果的同时降低了算法应用难度。

[1] Wu Ping, Wu Bin. Research on the adaptability model of RED queue’s control measurements[J]. Computer Systems & Applications, 2008,17 (11):25-28.(in Chinese)

[2] Wang Hong-wei,Yu Chi,Jing Yuan-wei.Global sliding mode control for nonlinear network systems with input restriction[J]. Journal of Northeastern University(Natural Science), 2010, 31(3):326-329.(in Chinese)

[3] Chen Xiao-long, Tian Yi-qiang, Zhang Yun. Stability analysis of improved TCP/RED model[J]. Computer Engineering, 2010, 36(10):19-21.(in Chinese)

[4] Hu Xiao-qing. Analysis and parameter setting for TCP/RED discrete model [J]. Computer Engineering, 2011, 37(17):75-77.(in Chinese)

[5] Jiang Wen-gang, Sun Jin-sheng, Wang Zhi-quan. New revised queue management algorithm of RED: RED-r[J]. Application Research of Computers, 2012, 29(7):2632-2634.(in Chinese)

[6] Floyd S, Fall K. Promoting the use of end-to-end congestion control in the Internet[J]. IEEE/ACM Transactions on Networking, 1999, 7(4): 458-472.

[7] Ge Yu-bo. Probability and mathematical statistics [M]. Beijing: Tsinghua University Press, 2005.(in Chinese)

[8] Yang Jin-tao, Guo He-qing. Study of the test case base of black box testing[J]. Computer Engineering & Science, 2006，28(5):130-132.(in Chinese)

[9] Casella G,Berger R.Statistical inference [M].2nd Edition. Florence: Thomson- Brooks/Cole, 2008.

[10] Kuznetsov A, Makarenko A, Salim J H. Tc-red(8)-Linux man page[EB/OL].[2002-12-01]. http://linux.die.net/man/8/tc-red.

[11] Chen Zuo, Li Ren-Fa, Xu Cheng, et al. Steady state error analysis of RED queue[J]. Journal of Computer Research and Development, 2004,41(11):1874-1878.(in Chinese)

[12] Huang Yan-qin. An improved active RED queue scheduling algorithm[J]. Digital Technology and Application, 2010(3):105-106.(in Chinese)

[13] Wu Ping, Wu Bin. Optimizing process performance of network traffic management model using regression analysis[J]. Computer Engineering and Applications, 2012, 48(4):104-106.(in Chinese)

[14] Zhao Yi, Wang Xiang-ting. Use of variable length of queue AQM improvement and research[J]. Shanxi Electronic Technology, 2009(1):85-86.(in Chinese)

[15] Bi Jing-ping, Wu Qi, Li Zhong-cheng. Measurement and analysis of Internet delay bottlenecks[J]. Chinese Journal of Computers, 2003,26(4):406-416.(in Chinese)

[16] Werner W A, Salim J H, Kuznetsov A. Differentiated services on Linux[C]∥Proc of Global Telecommunications Conference, 1999:831-836.

[17] Kalinowski S. Traffic shaping fur open WRT[EB/OL].[2006-12-01]. http://svenkalinowski.de/linux-wiki/TSHAPER.

[18] Leonardo B. RED queuing discipline[EB/OL].[2012-12-01]. http://www.softwareopal.com/qos/default.php.

[19] Ziegler T, Fdida S, Brandauer C. Stability criteria for RED with bulk-data TCP traffic[C]∥Proc of IFIP ATM&IP Working Conference, 2000:1-13.

附中文参考文献：

[1] 邬平，吴斌. 随机早期侦测队列控制测度自适应性模型研究[J]. 计算机系统应用, 2008, 17(11):25-28.

[2] 王宏伟，于驰，井元伟. 输入受限的非线性网络系统全局滑模控制[J]. 东北大学学报 (自然科学版), 2010, 31(3):326-329.

[3] 陈晓龙，田义强，章云. 改进的TCP/RED模型的稳定性分析[J]. 计算机工程, 2010, 36(10):19-21.

[4] 胡小青. TCP/RED离散模型分析及参数设置[J]. 计算机工程, 2011, 37(17):75-77.

[5] 姜文刚，孙金生，王执铨. 改进的RED队列管理算法: RED-r[J]. 计算机应用研究, 2012, 29(7):2632-2634.

[7] 葛余博. 概率论与数理统计[M]. 北京：清华大学出版社, 2005.

[8] 杨劲涛，郭荷清. 黑盒测试用例基的研究[J]. 计算机工程与科学, 2006,28(5):130-132.

[11] 陈佐，李仁发，徐成, 等. RED队列稳态误差分析[J]. 计算机研究与发展, 2004,41(11):1874-1878.

[12] 黄燕琴. 一种改进的主动队列调度RED算法[J]. 数字技术与应用, 2010(3):105-106.

[13] 邬平，吴斌. 采用回归方法优化网络流量管理模型处理性能[J]. 计算机工程与应用, 2012,48(4):104-106.

[14] 赵忆，王香婷. 利用可变队列长度的AMQ改进与研究[J]. 山西电子技术, 2009(1):85-86.

[15] 毕经平，吴起，李忠诚. Internet延迟瓶颈的测量与分析[J]. 计算机学报, 2003,26(4):406-416.

WUBin,born in 1977,MS,senior engineer,his research interest includes network management and scheduling.

马继涛(1974-),男,云南昆明人，硕士，高级工程师，研究方向为网络管理。E-mail:mjt@ynst.net.cn

MAJi-tao,born in 1974,MS,senior engineer,his research interest includes network management.

邬平(1967-),男,云南昆明人，高级工程师，研究方向为软件工程。E-mail:wuping@ynst.net.cn

WUPing,born in 1967,senior engineer,his research interest includes software engineering.

EliminatingredundantargumentsofREDbyfeatureanalysis

WU Bin，MA Ji-tao，WU Ping，TAN Peng

(Yunnan Academy of Scientific & Technical Information,Kunming 650051,China)

The RED algorithm is the basis of network congestion control.By using this algorithm, more than one parameter,such as queue average length,limit value of dropping packets,average size of packets,need to be loaded. What’s more,arguments’values are set without clear rules and the theoretical basis and unreasonable values weak the effect of the congestion control algorithm. The relationship of two system performance indicators of arrival rate of packets and the capability of data processing are analyzed by the way of feature analysis and build up a map relation between indicators and arguments of RED.Furthermore,excess parameters are combined and the ranges of values are confirmed by using the linear relation among parameters.The congestion control effect of the algorithm is improved in the network environment and increase the practicality of RED.

random early detection;characteristic equation;congestion control;liner mapping

1007-130X(2014)08-1519-05

2013-01-03;

：2013-03-26

TP393.072

：A

10.3969/j.issn.1007-130X.2014.08.016

吴斌(1977-),男，云南昆明人，硕士，高级工程师，研究方向为网络管理与调度。E-mail:star_amethyst@qq.com

通信地址：650051 云南省昆明市云南省科学技术情报研究院

Address:Yunnan Academy of Scientific & Technical Information,Kunming 650051,Yunan,P.R.China