一种自适应主动控制队列算法

主动队列管理AQM主动队列管理（Active Queue Management，简称AQM）是一种网络流量管理机制，旨在减少网络拥塞并提高吞吐量和延迟性能。

AQM通过在网络交换机中实现一系列的算法和策略来控制数据包的传输和排队，以解决传统的传输控制协议（Transmission Control Protocol，TCP）拥塞控制方法的一些缺陷。

一、AQM的背景与意义网络中的拥塞是指当网络中的流量量超过网络链路的吞吐能力时，网络出现堵塞的现象。

传统的TCP拥塞控制方法主要依靠丢包作为拥塞信号的指示，一旦丢包发生，TCP会减少发送速率。

然而，丢包并不能及时地反映网络的拥塞情况，且丢包发生后需要一定时间的恢复，导致了网络性能的下降。

AQM的提出旨在通过主动控制交换机中的队列长度，实时地反馈网络拥塞情况给数据源，从而减少队列中的排队延迟，提高网络的吞吐量和时延性能。

AQM的引入可以使得网络在拥塞发生前就采取一些措施，如主动丢弃数据包、降低发送速率等，以避免网络的拥塞现象。

二、AQM的工作原理AQM的工作原理可以总结为以下几个步骤：1. 检测队列长度：AQM通过周期性地检测队列的长度来获得拥塞信息。

当队列长度超过一定的阈值时，表示网络出现了拥塞。

2. 拥塞信号生成：一旦检测到网络拥塞的信号，AQM会根据一定的算法生成相应的拥塞信号。

常见的算法包括随机早期检测（Random Early Detection，RED）和随机早期丢弃（Random Early Drop，RED），它们分别通过计算数据包排队概率和随机丢包的方式来产生拥塞信号。

3. 拥塞信号传输：AQM将生成的拥塞信号传输到数据源或发送方。

这可以通过向数据源发送拥塞通知消息或降低数据包的传输速率来实现。

4. 数据源的拥塞响应：接收到拥塞信号的数据源或发送方会根据拥塞信号采取相应的措施以降低发送速率，从而减少拥塞现象。

三、AQM的优势与挑战AQM相对于传统的TCP拥塞控制方法具备以下优势：1. 实时性：AQM能够实时地反馈拥塞信息给数据源，数据源可以及时采取措施，从而降低了网络拥塞的发生概率。

基于粒子群优化的主动队列管理方法王军祥;林柏钢【摘要】针对网络拥塞现象,基于粒子群优化(PSO)提出了一种新的主动队列管理算法RQQM.该算法首先通过粒子群优化和变异算子来计算当前队列长度,并且基于到达速率和当前队列长度给出了丢包策略和丢包概率.最后,以实际数据将RQQM 算法与基于速率的早期检测公平队列管理(RFED)算法和自适应主动队列管理(ABLUE)算法进行仿真实验,发现丢包率受利用率和缓冲区影响较大；同时实验结果表明RQQM算法的公平性远远优于其他两种算法,其平均丢包率降低至12.21％.%In order to mitigate the network congestion, a new active queue management algorithm named RQQM (Rate and Queue-based Queue Management) was proposed by Particle Swarm Optimization ( PSO). In this algorithm, the actual queue length was deducted with PSO and variation factor, and the dropping strategy and dropping rate were given based on arrival rate and actual queue length. Then, a simulation with actual data was conducted to compare the algorithm performance between RQQM algorithm and RFED ( Rate-based Fair Early Detection) algorithm, as well as ABLUE ( Adaptive BLUE) algorithm. The results show that the dropping rate is greatly influenced by the utilization rate and buffer size, and the fairness of RQQM is much better than that of the other two algorithms, its average packet loss rate is decreased to 12. 21%.【期刊名称】《计算机应用》【年(卷),期】2013(033)002【总页数】4页(P390-392,396)【关键词】主动队列管理;丢包概率;粒子群优化;队列长度;到达速率【作者】王军祥;林柏钢【作者单位】福建船政交通职业学院信息工程系,福州350007;网络系统信息安全福建省高校重点实验室(福州大学),福州350108;网络系统信息安全福建省高校重点实验室(福州大学),福州350108【正文语种】中文【中图分类】TP393.06;TP180 引言随着网络拥塞程度的日益加剧，许多主动队列管理(Active Queue Management，AQM)方法被提出。

一种加强的主动队列管理算法--EBLUE
张顺亮;叶澄清;李方敏
【期刊名称】《通信学报》
【年(卷),期】2003(024)011
【摘要】作为一种典型的主动队列管理算法,BLUE明显不同于其它方法,它使用丢包和连接空闲事件来控制拥塞.试验表明BLUE的丢包率明显小于RED,但是其参数设置仍然存在一些不足之处.本文在BLUE算法的基础之上,通过引进自适应的思想对其进行了改进,提出了一种加强的BLUE队列算法--EBLUE.大量的仿真实验表明本文的改进算法能够进一步提高BLUE的性能.
【总页数】7页(P109-115)
【作者】张顺亮;叶澄清;李方敏
【作者单位】浙江大学,计算机学院,浙江,杭州,310027;浙江大学,计算机学院,浙江,杭州,310027;湘潭工学院,信息系,湖南,湘潭,411201
【正文语种】中文
【中图分类】TP393
【相关文献】
1.一种精确度加强的主动队列管理算法BLUE+ [J], 徐佳;殷新春;杨云
2.一种改进的ARED主动队列管理算法 [J], 张卓;周井泉;张萌
3.一种基于EDF-FQ的多优先级主动队列管理算法 [J], 王甲;姜希
4.一种精确度加强的主动队列管理算法PEBLUE [J], 杨云;徐佳;王秋平;刘凤玉
5.一种基于EDF-FQ的多优先级主动队列管理算法 [J], 王甲;姜希
因版权原因，仅展示原文概要，查看原文内容请购买。

一种自适应的主动网络拥塞控制机制研究
聂飞;李增智
【期刊名称】《小型微型计算机系统》
【年(卷),期】2007(28)5
【摘要】传统的端到端的拥塞控制机制不适应主动网络,针对主动网络面临的拥塞问题,提出了一种自适应的主动网络拥塞控制解决方案.在中间节点为转发到相邻节点的主动信包建立缓冲队列,以缓冲区中队列长度来表明节点的拥塞程度,通过对前向节点计算单元进行控制来改变当前节点拥塞状况,网络中相关节点通过协作对网络进行拥塞控制.理论分析和模拟试验结果表明,不管网络初始状态如何,该方案均能使各节点迅速达到动态平衡,快速消除主动网络拥塞.
【总页数】4页(P779-782)
【作者】聂飞;李增智
【作者单位】西安交通大学,计算机系统结构与网络研究所,陕西,西安,710049;空军工程大学,工程学院,陕西,西安,710038;西安交通大学,计算机系统结构与网络研究所,陕西,西安,710049
【正文语种】中文
【中图分类】TP393
【相关文献】
1.一种改进的自适应无线网络拥塞控制方案 [J], 焦翠珍
2.一种新的自适应网络拥塞控制算法 [J], 杨新宇;曾明;江晓;赵瑞;吴航
3.基于改进量子粒子群和主动PI模型的自适应无线传感器网络拥塞控制算法设计[J], 李晓玲;楚志刚
4.基于自适应性的主动队列无线网络拥塞控制算法 [J], 张禹;王怀彬
5.一种模糊自适应PI算法在网络拥塞控制中的应用 [J], 朱华;向少华
因版权原因，仅展示原文概要，查看原文内容请购买。

一种面向自相似业务的新型主动队列管理算法
杨晗;杨天明
【期刊名称】《计算机应用研究》
【年(卷),期】2015(32)4
【摘要】网络业务的自相似性对网络性能具有重要影响,可能导致严重的队列时延和分组丢失率.为解决这一问题,提出了一种考虑业务自相似性的主动队列管理算法.该算法基于小波方法对网络业务的赫斯特参数进行估计,并使用该参数的估计结果分析网络自相似过程和确定自相似性的程度.然后实时估计赫斯特参数,并基于此对网络业务进行实时分类.仿真用MATLAB生成网络架构,并使用帕累托分布模拟网络业务,将该算法和其他缓存管理算法的性能进行了比较,仿真结果验证了该算法具有更好的公平性,并且在网络拥塞的情况下,可以避免丢弃分组对其他队列造成影响.【总页数】4页(P1217-1219,1230)
【作者】杨晗;杨天明
【作者单位】西南石油大学应用技术学院,四川南充637000;华中科技大学计算机科学与技术学院,武汉430074
【正文语种】中文
【中图分类】TP393.07
【相关文献】
1.一种基于预测PI控制器的自相似网络主动队列管理算法 [J], 吴清亮;陶军;姚婕
2.自相似流量的主动队列管理算法 [J], 温昱晖;朱祥华;张勇
3.一种基于自相似流量速率估计的主动队列管理算法 [J], 汪岩;安建平;金鸿玲
4.一种基于自相似流量速率估计的主动队列管理算法 [J], 汪岩;安建平;金鸿玲
5.具有自相似性质的业务流的主动队列管理算法 [J], 付钰;张艳琴;胡俊超;潘彩平因版权原因，仅展示原文概要，查看原文内容请购买。

TCP网络的自适应神经滑模控制叶成荫;井元伟【摘要】针对TCP网络的拥塞控制问题,考虑了TCP负载和往返时延具有较大的突发性和时变性的情况,结合滑模控制与RBF神经网络提出了一种主动队列管理算法.考虑到网络系统参数是未知时变的,采用RBF神经网络逼近网络系统参数,从而使得主动队列管理算法易于实现.依据李雅普诺夫稳定性理论设计了RBF神经网络权值的自适应律,使得网络系统参数得到了较好的估计.采用RBF神经网络的输出作为滑模控制器的参数设计了一种主动队列管理算法,使得网络系统是渐近稳定的.仿真结果表明所提出的算法与比例积分控制器和传统的滑模控制器相比具有较快的响应和稳定的队列长度,在网络参数变化时仍能获得较好的鲁棒性.%To save the problem of congestion control in transmission control protocol (TCP) networks, by incorporating sliding mode control with radial basis function ( RBF) neural networks, an active queue management algorithm is presented in presence of TCP load and round trip time which are more abrupt and time-varying. Since network system parameters are unknown and time-varying, the RBF neural networks were used to approximate the network system parameters so that the active queue management algorithm was easily implemented. The network system parameters are well estimated by updating the RBF neural network weights according to Lyapunov theory. By using the output of the RBF neural network as the sliding mode controller parameters, an active queue management algorithm was designed to guarantee the network system was asymptotically stable. Compared with proportional-integral controller andconventional sliding mode controller, simulation results show that the proposed algorithm has fast system response and steady queue length as well as better robustness under various network conditions.【期刊名称】《电机与控制学报》【年(卷),期】2012(016)011【总页数】5页(P99-103)【关键词】传输控制协议;拥塞控制;主动队列管理;滑模控制;神经网络【作者】叶成荫;井元伟【作者单位】东北大学信息科学与工程学院,辽宁沈阳110819;辽宁石油化工大学计算机与通信工程学院,辽宁抚顺113001;东北大学信息科学与工程学院,辽宁沈阳110819【正文语种】中文【中图分类】TP130 引言随着传输控制协议(transmission control protocol，TCP)应用的快速增长，网络拥塞越来越频繁。

一种支持区分服务的主动队列管理算法曹振臻;肖扬【期刊名称】《铁道学报》【年(卷),期】2008(030)004【摘要】为区分服务网络的核心路由器,提出一种主动队列管理算法,它基于一种名为预估计随机早期检测PERED(Pre-estimation RED)的自适应随机早期检测算法(RED),因此称这种支持区分服务的主动队列管理算法为区分服务预估计随机早期检DSPERED(DiffServ PERED).首先DSPERED利用PERED算法中的一个离散时间队列长度的Markov模型来估计短时期后路由器缓冲区的队列状态,然后根据估计结果和服务的优先级调节不同服务的数据包最大丢包概率以实现对服务的区分.本文提出一种拥塞控制的思路,即预估计以及一种区分服务的方法,其使用不同的函数调节不同优先级服务的数据包最大丢包概率.通过使用DSPERED算法的模拟路由器对两种不同优先级服务的数据包处理的比较,验证该算法的性能.【总页数】7页(P32-38)【作者】曹振臻;肖扬【作者单位】北京交通大学,信息科学研究所,北京,100044;北京交通大学,信息科学研究所,北京,100044【正文语种】中文【中图分类】TP393.02【相关文献】1.一种基于CICQ支持区分服务质量的分布式动态双轮询调度算法 [J], 闫雒恒;王磊;李秀芹2.一种支持区分服务的模糊公平分组丢弃算法 [J], 陈远;李乐民3.一种支持比例区分服务的OBS数据信道调度算法 [J], 袁巍4.PIO:区分服务中的一种基于预测的主动队列管理算法 [J], 王建新;陈冬雷;陈建二5.一种基于CICQ支持区分服务质量的分布式动态双轮询调度算法 [J], 闫雒恒;王磊;李秀芹因版权原因，仅展示原文概要，查看原文内容请购买。

一种改进的主动队列管理算法王新生;袁小波【摘要】From the angle whether maintaining flow state information, this paper presents an improved Active Queue Management(AQM)Single Flow-AQM(SF-AQM).SF-AQM only maintenances data flow state information which has high transmission rate in order to reduce the router overhead identifies the non-adaptive flow by comparing packet the arrival intervals of different flow, improves the fairness of the algorithm, and controls the queue length under the target value to ensure the stability of the algorithm.Simulation results show SF-AQM algorithm has good performance in fairness and stability, and it is an effective algorithm in high performance communication networks congestion control.%从是否维护数据流状态信息的角度出发,提出一种改进的主动队列管理算法--SF-AQM.SF-AQM算法只维护发送速率大的数据流状态信息以降低路由器的开销,通过比较不同数据流的包到达时间间隔衡量流到达速率,识别出非适应性数据流,提高算法公平性,并使队列长度控制在目标值附近,保证算法稳定性.仿真结果表明,SF-AQM算法具有较好的公平性和稳定性,且对抑制网络拥塞有明显效果.【期刊名称】《计算机工程》【年(卷),期】2011(037)010【总页数】3页(P79-80,83)【关键词】拥塞控制;主动队列管理算法;公平性;队列长度;带宽利用率【作者】王新生;袁小波【作者单位】燕山大学信息科学与工程学院,河北,秦皇岛,066004;燕山大学信息科学与工程学院,河北,秦皇岛,066004【正文语种】中文【中图分类】TP393.021 概述在网络中间节点实施的主动队列管理算法由于能及时地反映拥塞，成为网络拥塞控制研究领域的热点，自主动队列管理思想被提出以来，产生了许多主动队列管理算法，其中，RED(Random Early Detection)算法影响最广泛。

《AOS中基于反馈机制的主动队列管理算法研究》摘要随着网络通信技术的飞速发展，网络流量和复杂性的增加对网络系统的性能提出了更高的要求。

主动队列管理（AQM）算法作为网络系统中重要的组成部分，对于保障网络稳定性和性能至关重要。

本文针对AOS（Active Operating System）系统中的主动队列管理算法进行研究，特别是基于反馈机制的主动队列管理算法，旨在提高网络系统的吞吐量和减少数据包的丢失率。

一、引言在网络通信中，主动队列管理算法是确保网络流量稳定传输的关键技术之一。

在AOS系统中，传统的被动队列管理方式已无法满足日益增长的网络需求。

因此，基于反馈机制的主动队列管理算法被广泛研究并应用于现代网络系统中。

这种算法通过实时反馈网络状态信息，动态调整队列长度，以实现更好的网络性能。

二、AOS系统中的主动队列管理概述AOS系统中的主动队列管理算法是一种基于拥塞控制的机制，它通过监测网络中的流量状态，实时调整队列长度，以避免拥塞和丢包现象。

该算法的核心思想是利用反馈机制，根据网络状态动态调整队列大小和发送速率。

通过这种方式，可以有效地控制网络的拥塞状况，提高网络的吞吐量并降低丢包率。

三、基于反馈机制的主动队列管理算法研究3.1 算法原理基于反馈机制的主动队列管理算法主要包括两个部分：一是反馈机制，二是队列管理策略。

反馈机制负责实时收集网络状态信息，包括队列长度、数据包丢失率等；而队列管理策略则根据这些信息动态调整队列大小和发送速率。

具体而言，算法通过监测网络中的流量和拥塞情况，当检测到拥塞时，会减小发送速率并增加队列长度，以避免更多的数据包丢失；当网络状态良好时，则会增加发送速率并适当减小队列长度，以提高网络的吞吐量。

这种动态调整机制可以有效地平衡网络的拥塞和传输效率。

3.2 算法实现基于反馈机制的主动队列管理算法的实现主要依赖于网络设备中的软件或硬件支持。

在AOS系统中，该算法可以通过网络设备的操作系统实现。

《自相似业务流下AOS主动队列管理技术研究》一、引言随着互联网的迅猛发展，网络流量呈现出自相似的特性，这给网络管理带来了新的挑战。

在网络流量控制中，AOS（Active Queue Management，主动队列管理）技术被广泛运用于各种网络环境，特别是在自相似业务流下，其作用尤为突出。

本文将深入探讨自相似业务流下AOS主动队列管理技术的原理、实现方法和研究进展。

二、自相似业务流的特点自相似业务流是指在网络传输过程中，数据包的到达速率和大小都呈现出自相似的特性。

这种特性使得网络流量的变化复杂且难以预测，对网络管理的实时性和稳定性提出了更高的要求。

自相似业务流的特点主要表现在以下几个方面：1. 长相关性和短相关性并存：数据包的到达时间间隔具有长程相关性和短程相关性，这给网络的实时控制和拥塞避免带来了挑战。

2. 流量峰值突出：在自相似业务流中，流量峰值较为突出，容易导致网络拥塞和丢包。

3. 难以预测：由于自相似业务流的复杂性，难以准确预测未来的流量变化。

三、AOS主动队列管理技术AOS主动队列管理技术是一种基于网络流量控制的技术，通过对网络队列的主动管理，实现对网络流量的有效控制。

其主要原理包括以下几个方面：1. 实时监测：AOS技术能够实时监测网络队列的状态，包括队列长度、数据包到达速率等。

2. 动态调整：根据监测到的网络状态信息，AOS技术能够动态调整队列管理策略，如增加或减少队列长度等。

3. 拥塞控制：通过主动队列管理，AOS技术能够在网络拥塞发生前进行预测和控制，有效避免网络拥塞和丢包。

四、自相似业务流下AOS主动队列管理的实现方法在自相似业务流下，AOS主动队列管理技术的实现需要综合考虑以下几个方面：1. 算法设计：针对自相似业务流的特性，设计合适的算法来控制网络队列的长度和流量速率。

例如，可以采用基于预测的算法或基于反馈的算法来动态调整队列长度。

2. 参数优化：根据网络环境和业务需求，对AOS技术的参数进行优化，以实现最佳的网络性能和流量控制效果。

几种典型主动队列管理(AQM)算法黄燕琴【摘要】网络拥塞控制按照不同的标准可以分为不同的控制机制和相应的拥塞控制策略.主动队列管理(AQM)算法是一种运行于网络中心节点的积极的闭环控制的链路算法.RED(随机早期丢弃)算法是IEIF推荐的主动队列管理算法的唯一侯选算法,然而算法在响应速度、稳定性等方面仍有缺陷.阐述了当前拥塞控制算法和几种典型的主动队列管理AQM算法,分析总结原始的RED算法的不足.【期刊名称】《曲阜师范大学学报（自然科学版）》【年(卷),期】2019(045)002【总页数】5页(P104-108)【关键词】拥塞控制;队列算法;主动队列管理【作者】黄燕琴【作者单位】漳州职业技术学院电子工程学院,363000,福建省漳州市【正文语种】中文【中图分类】TM3931 RED算法(Original RED算法)RED拥塞控制机制的基本思想是通过监控路由器缓冲区队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择连接来通知拥塞，使他们在队列溢出导致丢包之前减小拥塞窗口，降低发送数据速度，从而缓解网络拥塞.由于RED算法是基于FIFO队列调度策略的，并且只是丢弃正进入路由器的分组，因此其实施起来也较为简单.RED算法主要试图达到以下目标[1]:(1)最小包丢失率和排队延迟.(2)避免全局同步现象.(3)避免对突发业务的偏见:网络中含有大量的突发数据，而“丢尾”算法对突发业务有很大的偏见.在采用“丢尾”算法的路由器中，如果某个流的突发性越高，则当该流的包进入队列时越容易造成队列溢出，从而导致连续地丢弃大量的该流的包.(4)即使在缺乏传输层协议有效配合的情况下也能控制平均队列长度，从而避免拥塞.为了达成以上目标，RED算法按照指数权值移动均值 EWMA(Exponential Weighted Moving Average)的方法来计算平均队列长度，并且随机地选择正进入路由器的包进行丢弃.这种方法能被有效地实施而无需在路由器中维持每个流(Per-Ffow)的状态信息.RED算法主要分为2个部分.首先是计算平均队列长度，以此作为对拥塞程度的估计.另一个就是计算丢弃包的概率.a 计算平均队列长度由于Internet数据的突发性，如果一个队列在很多时候是空的，然后迅速被充满，又很快被取空，这时就不能判定路由器发生拥塞而向源端发送拥塞指示.因此，RED算法在计算平均队长Qavg时采用了类似低通滤波器(Low Pass Filter)带权值的方法Qavg(new)=(1-Wq)*Qavg(old)+Wq*Queue,(1)其中，Wq为权值，Queue为队列采样数据.由于Internet数据的突发本质或者短期拥塞导致的实际队列长度暂时的增长将不会使平均队长有明显变化，从而“过滤”掉短期瞬间的队长变化，尽量反映长期的拥塞变化.在计算平均队长的公式中，权值Wq相当于低通滤波器的时间常数，它决定了路由器对输入流量变化的反应程度.因此对Wq的选择非常重要，如果Wq过大，那么RED算法就不能有效地过虑短暂的拥塞;如果Wq太小，那么Qavg就会对实际队列长度的变化反应过慢，不能合理地反映拥塞状况，在这种情况下，路由器就不能有效检测到早期的拥塞.Wq的值应根据不同情况预先设置，一般来说，它是由路由器允许发生的突发业务的大小和持续的时间所决定的.b 计算丢包概率计算平均队长的目的就是为了反映拥塞状况，根据拥塞的程度来计算丢弃包的概率，从而有效地控制平均队列长度.RED算法有2个和队列长度相关的闭值:Qmin和Qmax.当有包到达路由器时，RED算法计算出平均队长Qavg.(2)计算丢包概率Pa的方法如式(2)、公式(3),(3)算法的第1部分决定了所允许的突发长度，而第二部分决定了在给定的当前拥塞级别时分组的丢弃频度.如果Qavg<Qmin，则进入分组就要排队，但如果Qavg>Qmax则进入分组自动地被丢弃.临界区就是当Qavg的值处于2个门限之间时.在此区域内，RED给进入分组指派了一个丢弃概率，取决于2个因素：若Qavg越接近于Qmax，则丢弃的概率就越高.图1 RED算法只要Qavg处在临界的范围，则保留一个count说明有多少个连接的分组避免了被丢弃；count的值越大，分组丢弃的概率也就越高.图1中的计算步骤较难看出所发生的细节，因此还是要简单地讨论一下.首先，要计算一个临时的概率值Pb.这个值在Qavg<Qmin时从0线性地增长到某个最大值Pmax(在Qavg<Qmax时的取值).如果我们定义一个量F就可以更容易地看出(4)它是小于Qavg的临界区的一部分.这样有Pb=F×Pmax, 0≤F≤1.(5)概率的现象有时会产生聚焦.例如，我们多次抛掷一个硬币，那么我们不会期望能够看到均匀出现的正面和反面交替出现的序列.相反，我们会看到全部是正面或全部是反面的聚焦，或较多的正面的聚焦，等等，而且其长期的平均值是50-50.对于RED算法，丢弃可能会相对地均匀分布着，因此对一个突发的信源不会受到惩罚.所以，丢弃中不直接使用概率Pb，而是用它来计算第2个概率Pa,它是用来确定丢弃的.将F带入图2中的算法，就可以得出以下的定义(6)下页图2给出了对这个函数的一些理解.对于一个给定的count值，当Qavg的值趋向于Qmax时，Pa均匀地增长.Pa从Qavg=Qmin时的Pa=0逐渐增加到在Qacg=Qmax时的最大值.如果保持F为恒定，并且画出Pa作为count的函数，那么这个函数真正的性质就更加清楚了.Pa 的值开始缓慢增加，然后急剧增长，直到它在count=(1/F×Pmax-1时达到Pa=1.这样，对count的大部分的数值，丢弃的概率极低，而当count接近其最大值时变得非常接近于1.这种效果是迫使丢弃间隔或多或少地更加均匀些.可以证明，如果我们令Pa为丢弃概率，而X为从一个分组被丢弃到下一个分组被丢弃之间的分组到达数，则X就是一个均匀分布的随机变量，从{1,2,…,1/Pb}中取值[2]：图2 RED概率的参数图3 RED和尾丢弃规一化吞吐量比较(4)(5)作为一个例子，文献[1]中推荐Pmax的值为0.02.当平均队列长度在minth和maxth之间时(F=0.5)，粗略地讲，大约有即的到达的分组被丢弃.图3给出了一个模拟的结果[1]，并将RED和尾丢弃策略相比.可以明显看出后者在队列已满时就简单地丢弃一个刚到达的分组.在高度拥塞时，RED可提供较高的吞吐量，因而比尾丢弃要好.RED不仅可以位于区域CDHG，也可以位于ABFE和BCGF，这取决于它是采用TD,FD还是RD.但Floyd认为，既然RED可以将平均排队时延控制在较短的范围内，FD并不能给RED带来明显的好处，RED采用TD已足够[3].RED为了限制了平均时延的大小，在平均队长超过了最大阈值后就丢包，而不是采用诸如设置CE 位之类的标记包的方法，从而有效地控制了平均队长.因为发送速度更快的流，其供随机标记的包也更多,在发生拥塞时，RED标记某个流的数据包的概率基本上和该流在路由器中的带宽成比例.从而消除了对突发流的偏见.由于RED算法存在着诸多问题，导致了改进算法的产生.这些算法主要有:Gentle RED,ARED,New ARED 等.2 Gentle RED算法1999年，Floyd又提出改进的RED算法Gentle RED，Gentle RED算法继承了RED算法的主要思想，当平均队列小于最大门阀值时，其丢弃概率的计算与RED 算法完全一致，而当平均队列Qavg大于2Qmax时，则不象RED算法一样丢弃概率由Pmax到1的跳跃，而是以另一种线性关系计算Pb的概率，然后以Pa概率来丢弃新到达路由器的分组，原理图所示.其算法函数表示为公式(7)、公式(8).(7)(8)注意到Pa不仅与Qavg有关，还与从上一次丢包开始到现在进入队列的包的数量Count有关.随着Count的增加，下一个包被丢弃的可能性也在缓慢增加.这主要是为了在到来的包之间均匀间隔地丢包，避免连续丢包，从而避免对突发流的偏见和产生全局同步现象.3 ARED算法在拥塞严重的网络中，路由器必须将足够多的拥塞信息通知到源端，以充分降低负载，避免由于队列溢出而丢包.另一方面，路由器也要防止拥塞信息过多地传给源端，从而造成瓶颈链路利用率的下降.因此，进行拥塞通知时应充分考虑到瓶颈链路上流的数量.而RED算法并没有考虑到这一点.为此ARED(A self-configuring RED)提出了一种自动配置机制，根据流量的变化来配置适当的参数.RED算法中，拥塞指示的发送速度是由参数Pmax来体现的.如果Pmax太大，那么丢包主要就是由于早期拥塞检测中产生的丢包造成的;如果Pmax太小，丢包主要就是由于队列溢出造成的.RED算法的一个弱点是平均队长对拥塞程度和参数设置很敏感.如果拥塞不太严重或者Pmax很大，则平均队长接近Qmin;如果拥塞很严重或者Pmax很小，则平均队长接近或大于Qmax.结果造成平均排队时延对流量负荷和参数设置很敏感.ARED算法的基本思想就是通过检查平均队长的变化来感知RED算法是应更激进(Aggressive)还是更保守(Conservative).如果平均队长是在Qmin附近振荡，那么拥塞控制就太激进了;如果在Qmax附近振荡，那么拥塞控制就太保守了.根据所观察到的平均队长，ARED算法动态地Pmax调整的值.其算法如下:Every Qavg Update:If (Qmin<Qavg && Qavg<Qmax)Status=between;Else if(Qavg<Qmin && Status!=below)Status=below：Pmax=Pmax/αElse if(Qavg>Qmax && Status!=above)Status=above：Pmax=Pmax*β.各参数变量含义,Status:平均队长状态, Between:Qmin和Qmax之间, Below:小于Qmin, Above:大于Qmax, α: Pmax减少量, β: Pmax增加量.ARED算法的思想很简单，就是根据平均队长是否在Qmin和Qmax之间，对Pmax采用乘法增加和乘法减少(Multiplicative Increase Multiplicative Decrease，MIMD)从而尽量保持平均队长在Qmin和Qmax之间.ARED算法是对RED算法改动很小的一种算法，它保留了RED算法的基本结构，只需调节参数Pmax从而保持平均队长在Qmin和Qmax之间，消除了RED算法的队列延时问题和参数敏感性问题.4 改进的New ARED算法为了提高ARED算法的鲁棒性， Sally Floyd等人提出了一种新的ARED算法New ARED(又称为Adaptive RED).其基本思想和ARED算法一样，都是采用自适应的Pmax以保持平均队长在Qmin,Qmax之间.不同之处在于New ARED算法保持平均队长在Qmin和Qmax的一半左右;Pmax不是每来一个包都改变，而是有一定时间间隔; Pmax不采用乘法增加和乘法减少，而是加法增加和乘法减少(Additive Increase MultiPlieative Decrease，AIMD); Pmax限制在[0.01，0.5].具体算法如下:Every interval seconds:If(Qavg>target && Pmax≤0.5)Increase Pmax:Pmax=Pmax+aElse if(Qavg<target && Pmax≥0.01)Decrease Pmax:Pmax=Pmax*β.各参变量含义,Interval:时间间隔，通常为0.05，target: Qavg的目标范围[Qmin+0.4*(Qmax-Qmin),Qmin+0.6*(Qmax-Qmin].New ARED算法的鲁棒性主要来自于Pmax不是很频繁的变化.但如果拥塞程度急剧变化，则Pmax需要过一段时间才能适应.为了保证ARED算法在这段时间里性能不会过度下降，因此将Pmax限制在[0.01,0.5]之间.这样，即使这段时间内平均对长不在目标范围内，平均延时和吞吐量也不会下降太多.RED标记包的概率依赖于拥塞水平，并且均匀地间隔丢包，避免了由于连续丢包导致地全局同步现象.但它依旧存在一些缺陷，譬如：参数敏感问题，RED算法的性能在一定程度上依赖于设计参数和网络状况[4,5].另外RED算法的公平性和稳定性也存在问题[6,7].因此，出现了一些RED改进和派生算法.丢包概率的计算很大程度上是依赖于平均队列长度的计算.参考文献：【相关文献】[1] Floyd S, Jacobson V. Random early detection gateways for congestion avoidance[J]. IEEE/ACM Trans on Network, 1993,1:397-413.[2] 夏高，刘斌. 用于高速网络入侵检测系统的并行TCP/IP协议栈[J]. 清华大学学报(自然科学版)，2011，7(8)：942-948.[3] 朱海婷，丁伟. 基于RED的差异型丢包队列管理算法[J]. 计算机学报，2014，567-577.[4] 任丰原，王福豹. RED算法的稳定性：基于非线性控制理论的分析[J]. 计算机学报，2002，25(12)：1302-1307．[5] 汤德佑，骆嘉伟，张大方. 参数自适应的随机早期检测算法[J]. 系统仿真学报，2003，15(12)：1741-1744．[6] Christiansen M, Jeffay K, Ott D, et al. Tuning RED for Web traffic[C]. Proceedings of ACM SIGCOMM 2000[A], Stockholm, Sweden, 2000. 139-150.[7] Firoiu V, Borden M. A study of active queue management for congestion control[C]. Proceedings of INFOCOM 2000[A], Tel Aviv, Israel, 2000. 1435-1444.。