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

摘要 随机早期检测RED ( Random Early Detection)算法是目前路由器中采用的重要的队列管理算法。本文介绍了目前广泛研究的拥塞控制算法RED算法，指出了其运用于网络时存在的缺陷，对几种改进的RED算法做了介绍和分析。

关键字 拥塞控制 随机早期检测 SRED DRED FRED

1 引言

在过去的十几年里，计算机网络经历了爆炸式的增长，给我们的生活带来了极大的方便，同时也带来了严重的拥塞问题。据统计，由于缓存的不足，其中发送端发送的数据包大约%10的包都将会被丢弃。我们使用图1来描述拥塞的发生，其中有两个关键点，分别是Knee和Cliff。当网络负载较轻时，吞吐量的增长和网络负载相比基本成线性关系，网络延迟增长缓慢；在网络负载超过Knee之后，网络的吞吐量增长缓慢，而网络延迟增长较快。当网络负载超过Cliff之后，网络吞吐量急剧下降，而网络延迟急剧上升。从图1中我们可以看出拥塞控制的目标就是使网络在Knee附近工作，.流控制和拥塞控制不同，流控制主要考虑了发送过程中的发送端和接收端,目的是使发送端的发送速率不超过接收端的接收能力.而拥塞控制则主要考虑了发送端和接收端之间的网络环境,他们的目的是保证网络环境中的数据不超过网络的传送能力,从而避免图一出现的网络性能严重下降的情况。1993年，Floyds和Jacobson提出了如何利用随机早期检测（RED）机制提供的路由器来检测网络的拥塞状况。当今的网络使用的TCP（传输控制协议）中，检测到有数据包丢失时，才能检测到网络拥塞。而Floyds和Jacobson指出这很可能会造成长队列一直占用整个时间，这将可能会极大的增加队列的延迟时间。因此，随着网络速度的提高，急切需要一种机制保证较高的吞吐量和较低的延迟。

2 RED算法

TCP基于窗口的端到端拥塞控制对于Internet的鲁棒性起到了关键作用。然而，随着网络的不断发展，网络规模越来越大，仅仅依靠TCP拥塞控制机制来提高网络的服务质量是远远不够的，事实上，在Internet这样复杂的系统中，不能指望所有的用户都能兼容这种端到端的拥塞控制机制。而必须是网络中的中间节点也参入到网络拥塞的控制当中来。如采用路由器端的拥塞控制方法－IP拥塞控制问题，通常也称之为队列管理机制。其主要的思想就是通过排队算法决定那些包可以传输，以此分配带宽，通过丢弃策略决定接受到的包哪些包被丢弃，哪些包被转发，以此来分配缓存。

⑴　RED算法

鉴于以上原因，一种主动队列管理（Active Queue Management）技术－RED（Random Early Detection,随机早期检测）应运而生， RED通过随机丢弃数据分组，控制平均队列长度，从而避免网络拥塞和全网同步重发，保证相对的公平性，并确保没有传输层的协同工作时也能使平均队列长度不超过某个上界。其基本思想是：随着队列尺寸的增大，数据分组被丢弃的可能性也会增大。RED利用指数加权平滑低通滤波器计算平均队列长度（AVQ），将AVQ与两个门限值（MINth和MAXth，MINth<MAXth）比较。当平均队列长度小于MINth时，不标记任何数据分组。当平均队列长度大于MAXth时，则标记所有后续到达的数据分

图一

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

事实上，RED路由器有两个独立的算法，计算平均队列长度算法与计算丢弃概率算法。计算平均队列长度的算法决定了路由器队列容纳突发性数据流的长度，计算丢弃概率决定了在给定的当前拥塞级别时分组的丢弃频度。

整个算法大体描述如下：

Avq=0，count=-1;

当有分组到达时：

If( 队列空) { =f(time-q_time); Avq= (1-w)^m Avq; }

else Avq<—(1－w) Avq+wq；

If (MINth<= Avq <=MAXth){Count=Count+1;

P_b＝max_p((Avq- MINth)/( MAXth- MINth) );

P_a=P_b/ (1-count*P);}

else if(Avq>= MAXth)丢弃分组

else count=-1;

其中： Avq:路由器队列平均长度;

q:当前队列长度。 Pa:当前分组被丢弃的概率;

P_b:计算中临时使用的概率。 m:路由器空闲期间可能发送的最小分组数;

time:当前时间。q _ time:队列空闲时间的开始;

f (t):时间t的一个线性函数;

count:上次丢弃分组后收到的分组个数; max_p: P_b的最大值。

⑵　RED算法的缺陷

①　参数设置问题：RED性能的优劣很大程度上是由其预先设置的参数w, MAXth和MINth决定的。如何权衡吞吐量延迟之间的关系，从而找到一组最优的参数有待进一步研究.

图2

②　尚不能有效估计拥塞的严重性：RED通过检测早期的拥塞减轻了“尾部丢弃”机制造成的大量分组无畏丢弃，但必须配置足够的缓冲区容纳从检测到拥塞到瓶颈链路负荷开始下降这段时间内到达的数据分组。当有大量突发性TCP数据时，队列长度的增减异常迅速，RED来不及做出反映。

③　RED公平性问题：对RED而言，不同TCP流RTT的差异是损害公平性的原因之一。理论上，在丢弃概率一定的情况下，TCP的发送速率大致和RTT呈反比，而RED在特定时刻对所有流都使用同一丢弃概率，这就必然导致不公平。

鉴于以上原因，RED出现了它的多种变体及改进，下面对其中的几种算法的原理和性能进行一下简单的介绍。

3 RED的改进及性能介绍

⑴　ARED

在拥塞严重的网络中，RED必须将拥塞信息通知到足够的源端充分降低负荷，避免队列溢出而丢失分组。Ranjan指出在TCP连接中采用上述的RED模型将会出现许多非线性现象，比如随参数的变化会出现振荡和混乱现象。其中RED的一个弱点就是平均队列长度很大一部分依赖于网络中的负载，若负载较轻，则平均队列长度接近于最小队列，并且系统处于不稳定状态。为了解决上述问题，Floyd提出了RED的改进机制，即ARED。

ARED的基本思想是通过检查平均队列长度的变化来决定RED是更激进还是更保守，即是丢弃更多的包还是选择减少丢包的数量，从而尽量保持平均队列的长度的变化在MINth和MAXth。具体的说，如果平均长度在MINth之间摆动就是说明拥塞控制算法太激进了，那么就减小max_p，max_p= max_p/a;相反的如果平均长度在MAXth之间摆动，就是说明拥塞控制算法太保守了，那么就增大max_p，max_p= max_p*b.其中b>a>1.

⑵　FRED

FRED 对每个业务流( 或 连 接) 都 实 施 单 独 的一个RED算法,它通过对每个活跃的数据流进行记帐，对使用不同带宽的流做出不同的标记包的决策，从而提高了不同的流享用带宽的公平性。使用RED时，主要会产生公平性问题：对一些强壮的流，这些数据流能够对网络中发生的拥塞做出反映，并可以充分利用现有的网络条件继续发送数据，但对一些脆弱流，他们也可以做出反映，但这些数据流要么对丢包过于敏感，要么对更多可用的带宽适应很慢，比如TELNET.。

当一个包进入路由器时，不在是单单的采用RED算法来进行数据包的丢弃，如果平均队长Avq小于MAXth，并且该包所属流在缓冲区中排队包的数量小于最小队列长度，该包总被接收。这样，FRED就保护了脆弱的流。当该流的队列长度大于最大队列长度时，则标记该流的概率就会大大增加。

⑶　SRED

SRED的基本思想就是比较。当有一个包到达buffer时，就和buffer中随机选出的一个包进行比较，若两个包属同一个流，则称为"击中"（hit）。为了使系统有更长的记忆，SRED设计了一种数据结构，称为"僵尸"列表（Zombie List）。这个列表可以被认为是一种流Cache，其中记录了最近流经该buffer的m个流及其一些额外信息："count"和"时间戳"。起初列表为空，当有一个包到达时，只要列表非空，则该包的流标识（源、目的地址等）加入列表，其僵尸的count设为0，时间戳为该包的到达时间。 一旦僵尸列表满了，则作如下工作：当一个包到达后，它和僵尸列表中随机选出的僵尸进行比较：
击中：一旦到达包的流与僵尸匹配，称为一个hit，在此情况下，僵尸的count 值加1，timestamp值更新为新到达包的时间。

没击中：如果两者不是同一个流，称为“No-hit”，在此情况下，以概率p 重写僵尸中的流描述符，count 值设为0，timestamp设为新到包的时间，以1-p 的概率维持原有僵尸表。

SRED用一个函数Hit(t)来记录第t个包是否击中，如果击中，则Hit(t)取值为1，否则为0。从恶意流相比较良好流更易引发"击中"，这个意义上说，如果一个包引发"击中"，则可认为该包属于恶意流。如果一个包"击中"并且该僵尸的count值很大，就更明显了。

4 算法比较与评价

以上RED算法均有改进之处，RED允许网关同时获得较高吞吐量和较低的平均延迟，但是它对参数的设置十分敏感，同样的参数设置在不同的网络环境下获得的网络性能会有很大的差异，因此需要根据网络环境的变化来动态地调节RED参数，ARED较好地解决了这个问题。

FRED改进了带宽分配的不公平性，如果拥塞比较持久，意味着RED的Avq高于MINth。这时丢包率是一个非零的值，即使占用带宽较小的值也有包丢弃，且对于相同类型的传输也会有短暂的不成比例的包丢弃。针对上述几个问题，FRED进行了有效的改进。与RED的随机选择某一个连接进行拥塞通告的方式不同，FRED有选择地向那些队列中有较多数据包地连接发送反馈信息，它能有效地隔离不规矩的连接，对突发数据较多和低速的连接提供了更好的保障，提高了不同数据流带宽分配的公平性。

SRED 的主要目的是保持FIFO队列的稳定(与活跃流(Active flows )的数量无关);另外一个目的是鉴别恶的流(Misbehaving flows )其主要思想是通过估计网络中流的个数调整分组标记/丢弃概率。而流的个数是通过概率统计的方法来获得的，所以SRED中不需要使用Per-flow信息。SRED在相当大的负荷范围内，都能保持队列的稳定而与活跃流的数量相独立，从而有效的减小了延迟抖动。而且也给出了鉴别恶意流的方法并且对其进行惩罚。

5 小结

从以上讨论可以看出,FRED, ARED和SRED几乎在所有方面都要优于RED算法,而这几种算法之间则很难说哪种算法性能更好.它本身各有其优势之处，但改进算法在完善了RED的基础上大都很难解决自身的参数设置问题，如何解决这个问题有待我们进一步研究。

参考文献：

1 潘爱民 ,徐明伟 .计算机网络 . 清华大学出版社,北京 : 2004年

2徐恪，徐明伟.高等计算机网络——体系结构，协议机制，算法设计与路由技术

3S.Athuraliya, V H. Li, S. H. Low, Network, vol. 15, no. 3, pp. 48-53 and Q. Yin, "REM: Active queue management," IEEE May/June 2001.

4 陈帅 ,杨洪波 .主动队列管理拥塞控制算法研究. 2002年

5 W Feng. D Kandlur, D Saha, K Shin. Techniques for eliminating packet Loss in Congested TCP/IP network[R].US: University Of Michigan,CSE-TR-349-97, 1997.

6 http://network.ccidnet.com/art/226/20021108/30259_1.html