基于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，MINthMAXth）比较。当平均队列长度小于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;

Pb＝maxp((Avq- MINth)/( MAXth- MINth) );

Pa=Pb/ (1-count*P);}

else if(Avq= MAXth)丢弃分组

else count=-1;

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

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

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

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

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

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

⑵　RED算法的缺陷

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

图2