基于RED算法的拥塞控制的研究

1、基于RED算法的拥塞控制的研究摘要随机早期检测RED(RandEarlyDetetin)算法是目前路由器中采用的重要的队列管理算法。本文介绍了目前广泛研究的拥塞控制算法RED算法，指出了其运用于网络时存在的缺陷，对几种改良的RED算法做了介绍和分析。关键字拥塞控制随机早期检测SREDDREDFRED1引言在过去的十几年里，计算机网络经历了爆炸式的增长，给我们的生活带来了极大的方便，同时也带来了严重的拥塞问题。据统计，由于缓存的缺乏，其中发送端发送的数据包大约%10的包都将会被丢弃。我们使用图1来描绘拥塞的发生，其中有两个关键点，分别是Knee和liff。当网络负载较轻时，吞吐量的增长和网络负载

2、相比根本成线性关系，网络延迟增长缓慢；在网络负载超过Knee之后，网络的吞吐量增长缓慢，而网络延迟增长较快。当网络负载超过liff之后，网络吞吐量急剧下降，而网络延迟急剧上升。从图1中我们可以看出拥塞控制的目的就是使网络在Knee附近工作，.流控制和拥塞控制不同，流控制主要考虑了发送过程中的发送端和接收端,目的是使发送端的发送速率不超过接收端的接收才能.而拥塞控制那么主要考虑了发送端和接收端之间的网络环境,他们的目的是保证网络环境中的数据不超过网络的传送才能,从而防止图一出现的网络性能严重下降的情况。1993年，Flyds和Jabsn提出了如何利用随机早期检测RED机制提供的路由器来检测网络的

3、拥塞状况。当今的网络使用的TP传输控制协议中，检测到有数据包丧失时，才能检测到网络拥塞。而Flyds和Jabsn指出这很可能会造成长队列一直占用整个时间，这将可能会极大的增加队列的延迟时间。因此，随着网络速度的进步，急迫需要一种机制保证较高的吞吐量和较低的延迟。2RED算法TP基于窗口的端到端拥塞控制对于Internet的鲁棒性起到了关键作用。然而，随着网络的不断开展，网络规模越来越大，仅仅依靠TP拥塞控制机制来进步网络的效劳质量是远远不够的，事实上，在Internet这样复杂的系统中，不能指望所有的用户都能兼容这种端到端的拥塞控制机制。而必须是网络中的中间节点也参入到网络拥塞的控制当中来。如

4、采用路由器端的拥塞控制方法IP拥塞控制问题，通常也称之为队列管理机制。其主要的思想就是通过排队算法决定那些包可以传输，以此分配带宽，通过丢弃策略决定承受到的包哪些包被丢弃，哪些包被转发，以此来分配缓存。RED算法鉴于以上原因，一种主动队列管理AtiveQueueanageent技术REDRandEarlyDetetin,随机早期检测应运而生，RED通过随机丢弃数据分组，控制平均队列长度，从而防止网络拥塞和全网同步重发，保证相对的公平性，并确保没有传输层的协同工作时也能使平均队列长度不超过某个上界。其根本思想是：随着队列尺寸的增大，数据分组被丢弃的可能性也会增大。RED利用指数加权平滑低通滤波器

5、计算平均队列长度AVQ，将AVQ与两个门限值INth和AXth，INthAXth比拟。当平均队列长度小于INth时，不标记任何数据分组。当平均队列长度大于AXth时，那么标记所有后续到达的数据分图一组。通过丢弃标记分组或通知源节点降低发送速率的方式，保证平均队列长度不超过AXth所限定的队列长度。假设平均队列长度介于两个门限值之间，那么以概率Pa丢弃或标记后续到达分组，其中Pa是平均队列长度的函数。事实上，连接中分组丢弃的概率大致和该连接占用的带宽成正比。这是因为对一个发送量较大的数据流来说，可供随机丢弃的分组的数量也相对较多，不能保证公平性，这也是RED算法的缺陷。其分组丢弃如图二所示。事实

6、上，RED路由器有两个独立的算法，计算平均队列长度算法与计算丢弃概率算法。计算平均队列长度的算法决定了路由器队列包容突发性数据流的长度，计算丢弃概率决定了在给定的当前拥塞级别时分组的丢弃频度。整个算法大体描绘如下：Avq=0，unt=-1;当有分组到达时：If(队列空)=f(tie-q_tie);Avq=(1-)Avq;elseAvq(1)Avq+q；If(INth=Avq=AXth)unt=unt+1;Pbaxp(Avq-INth)/(AXth-INth);Pa=Pb/(1-unt*P);elseif(Avq=AXth)丢弃分组elseunt=-1;其中：Avq:路由器队列平均长度;q:当前

7、队列长度。Pa:当前分组被丢弃的概率;Pb:计算中临时使用的概率。:路由器空闲期间可能发送的最小分组数;tie:当前时间。q_tie:队列空闲时间的开场;f(t):时间t的一个线性函数;unt:上次丢弃分组后收到的分组个数;axp:Pb的最大值。RED算法的缺陷参数设置问题：RED性能的优劣很大程度上是由其预先设置的参数,AXth和INth决定的。如何权衡吞吐量延迟之间的关系，从而找到一组最优的参数有待进一步研究.图2尚不能有效估计拥塞的严重性：RED通过检测早期的拥塞减轻了“尾部丢弃机制造成的大量分组无畏丢弃，但必须配置足够的缓冲区包容从检测到拥塞到瓶颈链路负荷开场下降这段时间内到达的数据分

8、组。当有大量突发性TP数据时，队列长度的增减异常迅速，RED来不及做出反映。RED公平性问题：对RED而言，不同TP流RTT的差异是损害公平性的原因之一。理论上，在丢弃概率一定的情况下，TP的发送速率大致和RTT呈反比，而RED在特定时刻对所有流都使用同一丢弃概率，这就必然导致不公平。鉴于以上原因，RED出现了它的多种变体及改良，下面对其中的几种算法的原理和性能进展一下简单的介绍。3RED的改良及性能介绍ARED在拥塞严重的网络中，RED必须将拥塞信息通知到足够的源端充分降低负荷，防止队列溢出而丧失分组。Ranjan指出在TP连接中采用上述的RED模型将会出现许多非线性现象，比方随参数的变化会

9、出现振荡和混乱现象。其中RED的一个弱点就是平均队列长度很大一局部依赖于网络中的负载，假设负载较轻，那么平均队列长度接近于最小队列，并且系统处于不稳定状态。为理解决上述问题，Flyd提出了RED的改良机制，即ARED。ARED的根本思想是通过检查平均队列长度的变化来决定RED是更激进还是更保守，即是丢弃更多的包还是选择减少丢包的数量，从而尽量保持平均队列的长度的变化在INth和AXth。详细的说，假如平均长度在INth之间摆动就是说明拥塞控制算法太激进了，那么就减小axp，axp=axp/a;相反的假如平均长度在AXth之间摆动，就是说明拥塞控制算法太保守了，那么就增大axp，axp=axp*

10、b.其中ba1.FREDFRED对每个业务流(或连接)都施行单独的一个RED算法,它通过对每个活泼的数据流进展记帐，对使用不同带宽的流做出不同的标记包的决策，从而进步了不同的流享用带宽的公平性。使用RED时，主要会产生公平性问题：对一些强壮的流，这些数据流可以对网络中发生的拥塞做出反映，并可以充分利用现有的网络条件继续发送数据，但对一些脆弱流，他们也可以做出反映，但这些数据流要么对丢包过于敏感，要么对更多可用的带宽适应很慢，比方TELNET.。当一个包进入路由器时，不在是单单的采用RED算法来进展数据包的丢弃，假如平均队长Avq小于AXth，并且该包所属流在缓冲区中排队包的数量小于最小队列长度

11、，该包总被接收。这样，FRED就保护了脆弱的流。当该流的队列长度大于最大队列长度时，那么标记该流的概率就会大大增加。SREDSRED的根本思想就是比拟。当有一个包到达buffer时，就和buffer中随机选出的一个包进展比拟，假设两个包属同一个流，那么称为击中hit。为了使系统有更长的记忆，SRED设计了一种数据构造，称为僵尸列表ZbieList。这个列表可以被认为是一种流ahe，其中记录了最近流经该buffer的个流及其一些额外信息：unt和时间戳。起初列表为空，当有一个包到达时，只要列表非空，那么该包的流标识源、目的地址等参加列表，其僵尸的unt设为0，时间戳为该包的到达时间。一旦僵尸列表

12、满了，那么作如下工作：当一个包到达后，它和僵尸列表中随机选出的僵尸进展比拟：击中：一旦到达包的流与僵尸匹配，称为一个hit，在此情况下，僵尸的unt值加1，tiestap值更新为新到达包的时间。没击中：假如两者不是同一个流，称为“N-hit，在此情况下，以概率p重写僵尸中的流描绘符，unt值设为0，tiestap设为新到包的时间，以1-p的概率维持原有僵尸表。SRED用一个函数Hit(t)来记录第t个包是否击中，假如击中，那么Hit(t)取值为1，否那么为0。从恶意流相比拟良好流更易引发击中，这个意义上说，假如一个包引发击中，那么可认为该包属于恶意流。假如一个包击中并且该僵尸的unt值很大，就

13、更明显了。4算法比拟与评价以上RED算法均有改良之处，RED允许网关同时获得较高吞吐量和较低的平均延迟，但是它对参数的设置非常敏感，同样的参数设置在不同的网络环境下获得的网络性能会有很大的差异，因此需要根据网络环境的变化来动态地调节RED参数，ARED较好地解决了这个问题。FRED改良了带宽分配的不公平性，假如拥塞比拟持久，意味着RED的Avq高于INth。这时丢包率是一个非零的值，即使占用带宽较小的值也有包丢弃，且对于一样类型的传输也会有短暂的不成比例的包丢弃。针对上述几个问题，FRED进展了有效的改良。与RED的随机选择某一个连接进展拥塞通告的方式不同，FRED有选择地向那些队列中有较多数

14、据包地连接发送反应信息，它能有效地隔离不规矩的连接，对突发数据较多和低速的连接提供了更好的保障，进步了不同数据流带宽分配的公平性。SRED的主要目的是保持FIF队列的稳定(与活泼流(Ativefls)的数量无关);另外一个目的是鉴别恶的流(isbehavingfls)其主要思想是通过估计网络中流的个数调整分组标记/丢弃概率。而流的个数是通过概率统计的方法来获得的，所以SRED中不需要使用Per-fl信息。SRED在相当大的负荷范围内，都能保持队列的稳定而与活泼流的数量相独立，从而有效的减小了延迟抖动。而且也给出了鉴别恶意流的方法并且对其进展惩罚。5小结从以上讨论可以看出,FRED,ARED和SRED几乎在所有方面都要优于RED算法,而这几种算法之间那么很难说哪种算法性能更好.它本身各有其优势之处，但改良算法在完善了RED的根底上大都很难解决自身的参数设置问题，如何解决这个问题有待我们进一步研究。参考文献：1潘爱民,徐明伟.计算机网络.清华大学出版社,北京:2022年2徐恪，徐明伟.高等计算机网络体系构造，协议机制，算法设计与路由技术3S.Athuraliya,VH.Li,S.H.L,Netrk,vl.15,n.3,pp.48-53a