- 1 -
基于主动网拥塞控制 RED算法的改进与实现
张景春，单吉峰，张坤，刘卫华
兰州大学信息科学与工程学院，甘肃兰州 （730000）
摘 要：近年来，随着网络技术的高速发展，网络规模也迅速扩大，大量不同类型的数据流
在路由器处交汇，给路由节点造成了很大的拥塞问题，拥塞问题己经成为制约网络发展和应
用的一个瓶颈，闭环拥塞控制机制已经成为当今网络的标准，但在一些持续传输比特流的应
用中，由于流媒体数据交换服务会占用更多的网络带宽，仍然会使一些节点产生拥塞。本文
利用主动网允许网络节点对通过自己的数据流进行估算的特性,对RED算法中的缺点进行定
位，设计了一种高带宽时延拥塞控制算法。该算法既缓解了节点的拥塞状况，又使得网络资
源的浪费最小化。实验结果也证实了其在限制高带宽连接方面的有效性。
关键词：拥塞控制；主动网络；主动式队列管理；RED算法
中图分类号：
1．引 言
近年来，随着网络技术的高速发展，网络规模也迅速扩大，新的网络应用的不断涌现和
用户数量的迅速增加，使得 Internet 的流量急剧增长，其中除了传统的 WWW, FTP, Telnet
等数据流外，还出现了大量的实时多媒体数据流。由于大量不同类型的数据流在路由器处交
汇，给路由节点造成了很大的拥塞问题，导致延迟和吞吐量等 QoS（Quality of Service）性
能指标下降。拥塞成为影响带宽、缓存等网络资源利用率的关键因素。如果发生拥塞却没有
及时处理，往往会导致恶性循环，甚至使得网络完全瘫痪。拥塞问题己经成为制约网络发展
和应用的一个瓶颈，因此,有效解决拥塞问题对于提高网络性能具有重要意义，如何更好地
预防和控制拥塞一直是近年来研究的热点问题。
本文设计了一种拥塞控制机制：利用主动网的特性对 RED算法中的缺点进行定位，并
限制了由高带宽应用流引起的网络性能的降低，使主动过滤器移动到最靠近高带宽连接源的
地方将其过滤。实验结果也证实了高带宽时延拥塞控制算法在限制高带宽连接方面的有效
性。
2．基于主动网拥塞控制算法
高带宽时延拥塞控制算法是一种控制由无响应连接和由高带宽应用引起的网络拥塞最
小化主动机制。其主要目标是限制高带宽应用在网络节点处的冲突，为包队列在网络中间节
点提供宽松的带宽，防止网络资源的闲置或过载，从而使各中间节点包队列对带宽的利用率
达到最大，丢包最少。它扩展了 RED（随机早期检测算法）的队列管理技术来探测中间节
点发生拥塞的开始。
算法的设计实现
图 2-1描述了高带宽时延拥塞控制算法的流程图。下面对该算法的关键部分进行说明。
检测节点包队列：当网络资源被耗尽时，网络开始拥塞，网络节点首先受到影响。当某
个节点发生拥塞时，长长的包队列会占用大量系统资源；当队列溢出时，甚至会迫使节点丢
掉包。因此，在网络中间节点检测拥塞状况的理想对象是包队列。
在瓶颈链路中，带宽消耗情况与节点的队列占有情况直接相关[1]。一个链路上占有高带
宽的链接，相应的包队列在节点上占有的资源也多。在 RED网关中，当平均队列长度 avgQ
- 2 -
超过最大阈值 maxth时，非高带宽连接的队列占有量和高带宽连接的队列占有量之间的差值
会达到最大。此时包队列就会溢出，这种状态的节点很容易被判断出存在高带宽流。
开始
检测节点包队列
由移动过滤
包机制控制
挑出一个高带宽流
没有发
生拥塞
发生拥塞
对于高带宽流 对于其它流
由 RED机
制控制
图2-1 高带宽时延拥塞控制算法的流程图
检测高带宽流：为了确定严重拥塞节点中的高带宽流，首先要设定一个包队列平均数 f。
f和某节点一段期间内的总包队列占有量和总链接数的关系如下：
f=总包队列占有量/总链接数 (1)
例如，设某主动节点上共有 5个链接，75个包队列竞争带宽，那么这个包队列平均数 f
＝75/5＝15。理论上，为保证带宽的公平分配，节点上每个链接不应该有超过 15 个的包缓
存。所有包队列占有量超过 f的链接都是无响应的。由于以下几个原因，有响应的链接可以
有超过包队列平均数的队列缓存：英特网流量的突发特性；在节点接收端口的高延迟－带宽
链接；不同阶段的连接操作。可以用因数 k（k>1）来体现这些差异。这个因数决定了允许
高带宽资源和非高带宽资源之间不平等的程度。如果 k选择一较小值，会导致算法把一个有
响应的链接当作高带宽连接。而值太大，算法就不可能检测到高带宽连接。经多次实验，我
们最终选择 k为㏒ e（3n），在对占有不同比例带宽流的识别进行参数选择时，Bernard Suter
的配置是基于 TCP 源的连接往返时间是假定的[2]，而本文探测高带宽连接的方法是在节点
拥塞时仅基于连接的包队列占有情况的。如果 minth 和 maxth 之间的差值非常大，avgQ 不
大可能有时间从 minth 增加到 maxth，因此，当平均队列长度大于 maxth，竞争带宽的连接
之间的包队列占有量存在较大差别，就可以假定在拥塞节点上的包缓存非常大的连接是高带
宽和无响应连接。例中 k=㏒ e（3*5）=。此外，本文定义有响应的平均包队列占有量：
⎡ ⎤f*k=r (2)
本例中 ⎡ ⎤=r ，所以，在严重拥塞状态期间，队列中最多有 41个包的连接（即包
队列占有量约为 %）是有响应连接。所有超过有响应的平均包队列占有量的连接就是
无响应连接。在上面定义的无响应连接中，拥塞节点上包缓存最大的连接被记做“最大带宽
连接”。结合等式(1)(2)可以得出： ⎡ ⎤(p/n))*(3n)(loge=r ，包队列占有量的百分比为：
q=100*r/p=100*㏒ e（3n）/n
图 2-2展示了随着连接数和包队列占有量的百分比之间的关系。可以看出，随着连接数
的增多，包队列占有量的百分比急剧减小。其中也隐含了当节点的拥塞是由很少的连接引起，
允许对包队列占有量进行大范围的调整。在 n＝1时，情况特殊，即使连接耗尽了节点的包
- 3 -
缓存资源，连接也不会被标记为高带宽连接。实际上这很必要，它保证了单独一个连接不会
被过滤掉，因为没有连接和它竞争。
图 2-2 连接数和包队列占有量之间的关系
隔离高带宽流：我们知道，在高带宽连接中，拉伸控制回路的做法是无效的[3]。因此，
对高带宽连接引起拥塞的控制是在网络上进行的，而不是依靠在发送端降低包的传输效率。
我们利用主动网的可编程能力，采用主动过滤包来控制高带宽流的方法来控制高带宽连接；
为阻止严重拥塞节点性能降低为 drop-tail节点，应对无响应的高带宽流进行控制[4]。控制高
带宽连接包流入的有效方法是为连接增加一个主动过滤包，一直过滤到包队列在拥塞节点的
缓存占有量减小到可接受的程度。此时，有响应的非高带宽连接就能竞争到先前被拒绝的平
均带宽数。拥塞节点第一次识别到高带宽连接时就启动包过滤器。包过滤器会越来越多的向
高带宽连接的源端迁移，直到连接第一次越过节点。这样是为了及早丢弃过滤包以减少对网
络资源的消耗。
移动过滤
移动过滤进程是从拥塞节点的队列缓存中提取出属于高带宽连接的包开始运行的。从此
包中可以知道连接的源端。一个高带宽连接标识符（GCI）形成了，它由源端的 IP 地址和
端口号组成。然后，通过 GCI从路由表可获得连接了拥塞节点和拥塞源端的虚拟链路对象，
节点利用 GCI 在这个虚拟链路的接收端口建立一个包过滤器。包过滤器安装后生存一个预
定的时间间隔，该时间被称为中间节点过滤器生存时间（Itime）。接着过滤器开始丢弃已识
别的高带宽连接的数据包。虚拟链路能显示出主动节点同哪里相连。该主动节点的 IP 地址
和端口号被称为前跳标识符（PHI）。节点会建立一个主动包，并将它发送到前一跳进行主
动过滤。
例如，在图 2-3中，假定 G是高带宽连接，在拥塞节点 N4被移动过滤进程识别。该连
接同其它四个有响应的源端竞争链路 V9，N4 从包队列中解析出一个属于高带宽连接 G 的
包，得到一个高带宽连接标识符 GCI，利用 GCI并查找它的路由表，节点 N4发现数据包来
自于同 N3连接的链路 V6。N4便第一次建立了一个包过滤器来接收链路 V6的包，丢弃属
于 G的包。接着 N4会发送一个携带着 GCI的主动包到 N3请求主动过滤服务，以及识别高
带宽连接 G的前跳节点。N3节点接收到主动包后也安装一个带有 GCI的包过滤器，并复制
携带着 GCI的主动包，再用相同的方法发送给靠近 G的源端的上一个节点 N2。这个过程一
直继续到前跳节点就是高带宽连接源 G的节点 N1。节点首先判断自己是不是首跳节点，如
果是，按照以下方法停止主动包的复制。在建立主动过滤信息前，每个节点都会进行前跳检
查，就是把 GCI域和 PHI域进行比较。如果相同，说明过滤器已经到达高带宽连接的首跳
节点。包过滤器需要一个比较长的生存时间，首跳过滤器生存时间（FHTime）。节点不会再
向前复制主动过滤信息，即使将主动过滤信息发送到高带宽连接的源端也没用。当主动过滤
- 4 -
信息到达节点 N1时，发现 GCI和 PHI中的 IP地址都是 G的地址，过滤器就不再向前复制。
图 2-3 有一个拥塞节点的网络拓扑图
一旦一个高带宽连接被识别出，拥塞节点开始过滤包，希望包队列占有量能够下降。但
是，同立即减少的队列长度相比，avg的变化是逐步的，这和低通滤波器的机制是一样的，
甚至在包队列占有量减小后，avg的值依然比 maxth大。这将再次触发高带宽时延拥塞控制
算法。为了确保在很短的时间间隔内，算法不会多次被触发，在两次连续触发的高带宽时延
拥塞控制算法之间，设定一个最小空闲周期 Tx。两个时间参数，ITime和 FHTime的选择是
主动过滤机制成功的关键。ITime参数是基于主动过滤包沿着高带宽连接的路径，从一个中
间节点迁移到它的前跳节点所花费的时间设定的。如果它的值设定的太大，这两个连接都要
承受过滤高带宽连接的开销。如果它的值设定的太小，包过滤在中间节点上被中止的时候，
还没在前跳节点上开始执行。FHTime的选择决定了主动包在首跳节点上对高带宽连接的过
滤时间。如果 FHTime选择太小，无响应连接不能在足够的时间内被过滤，就可能使网络再
次拥塞。如果太大，连接已经关闭，而包过滤器还存在，会增大它所在节点的不必要的开销。
通过不断试验，将 ITime的值取为 5秒，FHTime取为 100秒。
3．仿真实验
实验环境包括主动节点和非主动节点。主动节点采用 Linux作为操作系统，非主动节点
为Windows，ANTS为执行环境。
识别和过滤高带宽能力的实验
在本实验中测试了高带宽时延拥塞控制算法正确过滤高带宽的能力。仿真网络由六个有
响应源，一个无响应源，一个中间节点，和一个接收节点组成，如图 3-1。节点 1是高带宽
源，节点 2，3，4，5，6和 7是有响应连接源。节点 7既是有响应源也是将来的严重拥塞节
点。节点 8是所有源的接收节点。双箭头表示的是虚拟链路。当所有的源同时开始发送包时，
节点 7 进入拥塞状态。为了防止因为 TTL域的时间用完而导致的丢包现象，所有进入网络
的包的 TTL初始值都设为 10秒。节点 7的队列参数设为，队权为 ，maxth＝25，缓冲为
50。有响应源注入 50个包，每个源的初始 TCP慢启动上限为 16。高带宽源注入 200个包。
- 5 -
图3-1 识别和过滤高带宽能力的实验的网络拓扑图
图3-2 节点7中到达包与平均队列的关系
图 3-2中显示了包在节点 7的到达情况与队列长度的关系，y＝25表示节点设定的 maxth
值，可以看出，当平均队列长度超过 maxth时，高带宽时延拥塞控制算法被触发。此时节点
7的总队列占有量是 39个包，共七个连接。平均队列占有量 39/7=，允许因数 k=ln（21）
＝，那么允许队列占有量为 ⎡ ⎤* =17。在节点 7的队列中连接 1有 21个包，
正确识别为高带宽连接。因为节点 7是该连接的首跳节点，因此不需要包过滤器迁移，连接
1的包过滤器在节点 7生存 FHTime时间（100秒）。接着，节点 7上所有来自连接 1的包都
会被丢弃。而在高带宽时延拥塞控制算法发生作用后，可观察出其它有响应连接的吞吐量达
到了 100%，高带宽连接的吞吐量降为 %。如果执行 RED算法，响应连接的吞吐量必然
小于 100%，因为当节点发生拥塞时，RED算法会丢弃所有到达节点 7的包。
下面来证明算法在只隔离高带宽连接并将其动态过滤方面也是成功的。一旦高带宽连接
被过滤，它的包队列占有量会突然下降，这个在图上高带宽时延拥塞控制算法被触发后的区
域可以体现出来。最后，队列长度被控制在 B 点。图中，从高带宽时延拥塞控制算法发挥
作用（A 点）到平均队列占有量减少到小于 maxth（B 点）的这段时间称为 T。它说明了为
什么要在连续两次触发高带宽时延拥塞控制算法之间设置空闲时间 Tx （Tx>T），如果不设
置 Tx，在时间段 T内由于 avgQ>maxth，尽管已经有主动过滤包过滤连接，但是高带宽时延
拥塞控制算法还是会被多次触发。
下面来证明算法确保非高带宽的无响应连接不会被主动过滤器过滤。重复上面的实验，
节点1在3秒内匀速发送200个数据包，对于节点7来说，节点1现在模拟的是中等带宽要求的
匀速包源。图3-3显示了节点7上包到达数和队列长度之间的关系。图中队列长度瞬间的突然
变化是由连接中的脉冲特性引起的。
- 6 -
图3-3 主动过滤器不会过滤非高带宽的无响应连接
可以观察到，此时节点 7 的平均队列长度始终低于 10，说明源端需求没有超过供给。
因此，节点 7没有发生拥塞，高带宽时延拥塞控制算法也没有触发，包队列占有量始终低于
25，没有包丢失，所有 7个连接的吞吐量都是 100%。
主动过滤器移动的实验
本实验将检验主动过滤器向源端移动的情况以及过滤器在节点的安装情况。高带宽时延
拥塞控制算法在拥塞节点上识别并过滤了一个高带宽连接以后，它利用主动消息把包过滤器
向识别的高带宽连接的源端动态移动。这样，高带宽连接的包在很靠近发送源的地方就被过
滤了，因而减少了网络资源的浪费。
网络的拓扑结构如图 3-4所示。节点 1是无响应包源，节点 2、3、4、5是有响应包源，
为拥塞节点 I3提供复杂的通信量。节点 S是所有包的接收端，节点 I1、I2、I3是它的中间
节点。I3的缓存设为 60，maxth值设为 36，w为 。每个响应源的 TCP慢启动窗口设为
32，响应共注入 250个包，非响应源在 200毫秒内注入 250个包。为检测网络中数据包，按
如下方法标记不同源的包。连接 1的包标为 a1到 a250，连接 2的包标为 b2到 b250，连接
3、4、5的包用同样的方法标记。
图3-4主动过滤器移动实验的网络拓扑图
图 3-5中，x轴代表到达 I3的包的数量，y轴代表测量出 I3的包队列的长度。当平均队
列长度超过 35时，高带宽时延拥塞控制算法被触发。此时，I3收到 122个连接 1的包，84
个连接 2的包，91个连接 3的包，85个连接 4的包，66个连接 5的包，共 448个包，图中
用虚线标出。根据在节点上的队列占有量，连接 1被识别为高带宽连接，因此为连接 1安装
一个包过滤器，生存期 ITime秒。I3发送一个主动过滤消息给它的前跳节点 I2，在包过滤器
的生存期内，节点 I3会将连接 1的包丢弃。很快 I2也会安装一个包过滤器，对连接 1的控
制会越来越靠近发送源。这个过程一直持续到包过滤器迁移到首跳节点。丢弃连接 1的包的
程序在 I3、I2以及 I1递归的执行。图 3-6显示了高带宽时延拥塞控制算法触发后，各中间
节点的各种数据包的数量。
- 7 -
图3-5 节点I3中到达包与平均队列的关系
图3-6 算法触发后各种数据包的数量
多个高带宽连接实验
本实验测试了高带宽时延拥塞控制算法处理多个高带宽连接的能力。网络的拓扑结构如
图 3-7所示。节点 1和 3是高带宽连接，2、4、5、6、7是对带宽中等要求的无响应连接。
节点 8是所有源的接收节点。节点 1、3发送 300个包，其它节点 2、4、5、6、7各发送 120
个包。节点 7的队列参数设置为权 ，maxth为 35，缓存为 250，设置大缓存的目的是便
于观察节点 7上队列占有量，以及防止队尾丢弃。
图3-7多个高带宽连接实验的网络拓扑图
图 3-8 显示了节点 7 中包队列占有情况。开始，平均队列长度小于 10，一旦高带宽源
开始发送数据包，平均队列长度开始猛增并超过 maxth值（A 点），现在高带宽时延拥塞控
制算法被触发，主动过滤器开始过滤连接 1的包。很快队列长度开始下降，但是很快带宽被
第二个高带宽连接占用，这种情况持续了 Tx秒，在这期间，虽然平均队列长度已经超过了
maxth值（在 D点），但是因为两次触发高带宽时延拥塞控制算法的时间间隔必须大于 Tx秒，
所以直到 B 点高带宽时延拥塞控制算法又被第二次触发，并开始过滤第二个高带宽连接。
节点 7在 C点结束拥塞。
- 8 -
图3-8节点7中到达包与平均队列的关系
通过对节点 8的包队列的观察，可以发现所有中等带宽的连接吞吐量都达到了 100%，
而两个高带宽连接的吞吐量分别为 %和 46%。
4. 结论
本文设计了一种拥塞控制机制，限制贪婪链接拥塞控制机制，并对其进行了实现和评估。
它利用主动网的特性对 RED算法中的缺点进行定位，并限制了由高带宽应用流引起的网络
性能的降低。用移动的方法使主动过滤器在最靠近高带宽连接源的地方将其过滤。这样即缓
解了节点的拥塞状况，又将网络资源的浪费最小化。实验结果也证实了高带宽时延拥塞控制
算法在限制高带宽连接方面的有效性。
参考文献
[1] Lin D, Morris R. Dynamics of early detection. Proceedings of ACM SIGCOMM 97 Conference, Cannes,
France, September 1997
[2]Bernard Suter, T. V. Laxman, Dimitrios Stiliadis and Abhijit Choudhury, Efficient Active Queue Management
for Internet Routers. IEEE/ACM Transactions on Networking, April 1988
[3]Fei Peng, Victor C M Backward Congestion Notification Mechanism for TCP Congestion
, 2002
[4] Tan L S, Yin M. A rate-based PD congestion cont roller for high-speed computer communication networks [J].
Acta Automatica Sinica, 2003
[5]李洪春,刘群,丛延奇,刘骁建.一种基于 ECN的带优先级的队首标记拥塞控制算法. [J].计算机应用,2005,7
Base on Active networks Congestion control ameliorate
and come true of RED mechanism
Zhang Jingchun, Shan Jifeng, Zhang Kun, Liu Weihua
LanZhou University (730000)
Abstract
In recent years, with high-speed network technology development, the size of the network has
expanded rapidly, A large number of different types of data streams in the Department convergence
router, routing node to cause a lot of congestion problems, congestion problems have been restricted
network development and application of a bottleneck,many applications in Internet such as Internet
telephony and fast data exchange services tended to "grab" as much network bandwidth as available. In
this paper we presented a new algorithm based on active network to limit the impact of high bandwidth
connections at a congested node. The new mechanism was proved to be efficient and valuable through
the experiments.
Keyword：Congestion control; Active networks; Active Queue Management; RED mechanism
