- 1 -
一种基于模糊 RED算法的拥塞控制机制
张媛媛，徐惠民，苏放，李勇
北京邮电大学电信工程学院，北京 （100876）
摘 要：目前的基于滑动窗口的 TCP 拥塞控制机制包括：慢启动，拥塞避免，快速重传和
快速恢复四个部分。随机早期检测(Random Early Detection, RED)是目前常用的一种拥塞控
制算法，对于提高 TCP连接的吞吐量、减小路由器中的队列长度起到了一定的作用。 但由
于具有太多的可调参数,RED算法的调整十分困难,因而很难在实际网络中得到应用。主动队
列管理(Active Queue Management ,AQM)技术作为 Internet拥塞控制的一种有效方法,对于提
高 Internet的服务质量具有十分重要的作用。本文根据 TCP拥塞控制算法基于数据包丢失的
窗口变化机制,设计了一种基于模糊逻辑的主动队列管理算法。该算法依据路由器中队列长
度的变化情况,根据一定的模糊自校正原则来调整数据包的丢弃概率,从而使路由器中的队列
长度稳定在参考值附近。
关键词：拥塞控制，主动队列管理，模糊逻辑
1．引言
近年来，随着计算机和网络技术的迅猛发展以及多媒体应用的急剧增加，人们对 Internet
的服务质量提出了更高要求。目前 Internet 上 95%的数据流使用 TCP/IP 协议，因此 TCP/IP
拥塞控制的性能是保障 Internet 稳定性的关键。目前的 TCP 拥塞控制机制包括：慢开始，拥
塞避免，快速重传和快速恢复四个部分。然而，随着 Internet 的迅速发展，其网络规模日趋
庞大，结构日趋复杂，人们开始研究更为有效的队列管理算法，使网络在采用 TCP 拥塞控
制算法的基础上，实现效率最高并尽可能减小路由器中的平均队列长度，既主动队列管理技
术（AQM）。
2．TCP 拥塞控制
TCP 拥塞控制算法
目前，TCP 采用的是基于滑动窗口的拥塞控制机制。发送端所能传输的数据量大小取
决于发送端拥塞窗口和接收端宣告窗口的最小值。当数据刚刚开始传输时，采用慢开始机制，
TCP 把拥塞窗口值设置为最大报文段长度，确认报文段后，指数增加拥塞窗口的大小直至
达到慢开始阀值或者出现丢包。若达到慢开始阀值，确认报文段后，窗口值就增加一个报文
段。若发生了拥塞，则减小拥塞窗口值。这个策略是：若重传计时器截止期限到，则慢开始
阀值就设置为上次拥塞窗口值的一半，而拥塞窗口值就必须从 1 重新开始。换言之，发送端
再回到慢开始阶段。[1]
其算法描述如下：
(1) 当一个新数据包得到确认时:
if ( cwnd < twnd )
cwnd = cwnd + 1 ； / / slow start phase
else
cwnd = cwnd + 1 / cwnd ； / / congestion avoidance phase
(2) 源端接收到的重复ACK超过一定阈值时:
twnd = twnd / 2 ；
- 2 -
cwnd = twnd ； / / fast recovery
(3) 如果传输超时:
twnd = twnd / 2 ；
cwnd = 1 ；
有效窗口W = min{ cwnd , twnd }。
其中：
cwnd: 发送端拥塞窗;
twnd: 接收端宣告窗;
数学模型
对于上述TCP 拥塞控制机制,当不考虑传输超时等因素时,其数学模型可通过以下互相
耦合的非线性微分方程表示:
W(t)=1/R(t)-W(t)W(t-R(t))p(t-R(t))/2R(t-R(t))
q(t)=W(t)N(t)/R(t)-C
其中,x表示x对时间的导数,
W = 预期的TCP 拥塞窗口的大小 (单位:分组)；
q = 预期的队列长度 (单位:分组)；
R = 往返时间（单位：秒）；
C = 链路容量 (单位:分组/ 秒)；
N = 负载因数 (TCP连接的数量)；
p = 分组的丢弃概率. [2]
3. RED 队列管理
随机早期检测(Random Early Detection, RED)是目前常用的一种拥塞控制算法。其基本
思想是按一定的概率丢弃进入路由器的数据包，并且避免丢弃属于同一连接的连续数据包，
从而提高连接的吞吐量。RED算法对每条队列设置不同的门限值Qmin，Qmax，当平均排队
长度Q超过下限Qmin时，后续的数据包将被随机丢弃，其丢包率Pd为Q的函数。Qmin,Qmax
和Pmax均为可配置的RED参数。如果排队长度大于上限Qmax，则后续的IP包全被丢弃，即
Pd=1。这样，通过分摊包丢失率，RED可以在各连接之间获得较好的公平性。但是,RED算
法的有效性和可靠性取决于选择合适的配置参数，而且丢包率又是Q的静态映射，因此容易
引起网络的不稳定，当业务的突发度较强或流量抖动较大时，并不能获得满意的吞吐性能。
为了提供对各种业务的QoS保证,IETF提出了区分服务 (Diff-Serv)的策略，通过使用IPv4包头
中的业务类型(TOS)字段，并将其重新定义为DS字段，将属于不同业务的数据包按优先级进
行分类，并按照缓存队列的不同类别进行丢包处理。
RED算法对于提高TCP连接的吞吐量、减小路由器中的队列长度起到了一定的作用。 但
由于具有太多的可调参数,RED算法的调整十分困难,因而很难在实际网络中得到应用。本文
采用模糊控制原理,设计了一种更为有效的主动队列管理算法,并采用参数自校正技术,使该
算法对网络状态的变化具有很好的适应能力。[3]
4．基于模糊逻辑的主动队列管理算法
- 3 -
基于模糊逻辑的主动队列管理算法
由于路由器中的队列长度是可以实时获取的,因此可采用队列长度 q(t)和队列长度的变
化 dq(t)作为输入参数来调整数据包的丢弃概率 p(t),从而使队列长度能够稳定在一较低的参
考值去 Qref(Qref>0)。
定义q(t)、dq(t),q(t) = ^q(t)/qc ,dq(t) = q(t) - q(t-1)。其中^q(t)为t 时刻路由器中的队列长度,
qc为路由器的缓存容量；
其语言变量分别为{小(S),大(B)}和{负(N),零(Z),正(P)},其隶属度函数如图1 和图2 所
示。图中域值T1、T2、T3、T4 的取值不同对网络的效率和稳定性都可能会产生一定程度的
影响,但由于采用了 小节的自校正算法,这些域值的选择范围很大。在本文中,取T1 =
011,T2 = 016,T3 = -011,T4 = 011。
为方便地设计相应的自校正算法,本文采用T-S模糊模型。对以上所定义的变量以及相应
的隶属度函数,数据包丢弃概率可用8条IF-THEN规则来描述:
规则m: IF q(t) is A1m and dq(t) is A2m, THEN ACT = Fm(t)；其
中,A1m,A2m分别表示规则m所对应的q(t)和dq(t)的语言变量值,Fm(t)为该条规则的输出。定
义:
Fm(t) = am(t)q(t) + bm(t)(q(t) - q(t - 1))
以规则8为例:
规则8: IF q(t) is B and dq(t) is P ,
THEN ACT = F8(t) = a8(t)q(t) + b8(t)(q(t) - q(t - 1))。
对于某条具体的规则,系数am(t)、bm(t)的确定存在一定的难度, 但413小节所介绍的自校
正算法可将am(t)、bm(t)调整到相应的最佳值。
根据以上模糊规则，采用加权平均法，其t时刻的数据包丢弃概率为:
p(t)= Fm(t) wm(t) = am(t) wm(t) q(t) +
bm(t) wm(t) (q(t) - q(t - 1))
其中:wm(t) = GA1m(q(t)) GA2m(dq(t))为归一化后的权值,
即 wm(t)=1。
1
0
T1 T2
图1 队列长度的隶属度
函数
- 4 -
参数自校正算法
本小节将采用梯度下降法来调整参数am(t)、bm(t),使其达到或接近最佳值。首先定义性
能指标函数:
J(t) = 015(q(t) - qref)2 (3)
其中,qref表示参考队列长度。则参数的自校正算法如下:
am(t + 1) = am(t) - η(ЭJ(t)/Эam(t)) (4)
bm(t + 1) = bm(t) - η(ЭJ(t)/Эbm(t)) (5)
为使算法稳定,η应取一个较小的正数.由J(t)的定义(3)得:
ЭJ(t)/Эam(t)=(q(t) - qref) Эq(t)/Эam(t) (6)
其中: Эq(t)/Эam(t) = Эq(t)/Эp(t) * Эp(t)/Эam(t)
由式(2)得:
Эp(t)/Эam(t)=wm(t) q(t) (7)
队列长度q与丢弃概率p之间存在一个较复杂的函数关系,因此直接确定Эq(t)/Эp(t)存在
一定的难度。但由于函数q(t + 1) = G(p(t))在0<q<B之间是连续可导的,为简化问题,可采用如
下的数值方法来近似计算:[4]
Эq(t)/Эp(t) = (q(t)-q(t-1))/(p(t-1)-p(t-2)) (8)
综合（4）-（8）可得：
am(t+1)=am(t)-η(q(t)-qref)(q(t)-q(t-1))wm(t)q(t)/(p(t-1)-p(t-2))
同理可得：
bm(t+1)=bm(t)-η(q(t)-qref)* q(t)-q(t-1))wm(t)(q(t)-q(t-1))/(p(t-1)-p(t-2))
算法执行步骤
根据以上所介绍的模糊自校正算法,其队列管理算法可按以下步骤进行:
(1) 依据队列长度q(t)、队列长度的变化dq(t)以及各自的隶属度函数计算: wm(t) =
GA1m(q(t)) GA2m(dq(t))
(2) 依据式(9)、(10)所示的自校正算法,分别计算t时刻的参数am(t)、bm(t)；
(3) 依据式(2)计算t时刻的数据包丢弃概率[5]
p(t) = am(t)wm(t)q(t) + bm(t)wm(t)(q(t) - q(t - 1))
5. 结论
主动队列管理通过网络中间节点有控制的分组丢弃实现了较低的排队时延和较高的有
- 5 -
效吞吐量，是TCP端到端拥塞控制近来研究的一个技术热点。已有的大多数策略和算法在判
定分组丢弃时沿袭了RED的概率丢弃机制，具有一定计算复杂度的随机数生成过程不利于优
化路由器的性能。本文依据TCP拥塞控制策略基于数据包丢弃的窗口变化机制,设计了一种
基于模糊逻辑的主动队列管理算法,该算法依据路由器中队列长度的变化采用一定的模糊自
校正原则,实时调整进入该路由器数据包的丢弃概率,从而通知源端减小拥塞窗口以减少进入
网络的数据量,使路由器中的队列长度能够稳定在参考值附近。由于采用了参数自校正技术,
该算法与其它队列管理算法相比具有更高的稳定性,并对网络状态的变化具有很高的适应能
力。 该算法还可通过标记数据包的拥塞标记位,应用在具有显示拥塞指示功能的网络中。 由
此可避免由数据包丢弃而引起的重传所带来的传输延迟,从而使Internet的服务质量有更大程
度的提高。
参考文献
1 李腊元，李春林. 计算机网络技术.第2版 北京：国防工业出版社，-99
2 Postel control protocol[s].IETF RFC 793,1981
3 Athuraliya S,Li V H,Low S H,Yin : Active Queue Management[J].IEEE Network,2001,15(3):48-53.
4 ,Paxson V,W stevens. TCP Congestion Control[OL].Internet Draft,RFC 2581. April 1999.
5 Jacobson V. Congestion avoidance and control [J]. ACM SIGCOMM Computer Communication Review,
1988.
Congestion Control Based On Fuzzy Logic RED Algorithm
Zhang Yuanyuan，Xu Huimin，Su Fang，Li Yong
Department of Telecommunication Engineering，Beijing University of Post and
Telecommunication，Beijing（100876）
Abstract
Current TCP congestion control algorithm that based on glide windows contains: slow start, congestion
avoid, fast retransfer and fast recovery. Random Early Detection is a congestion control algorithm that
in common use recently. And it helps a lot in improving throughput of TCP connection and reducing
queue length of Router. However, with so many parameters that can be adjusted, RED congestion
could hardly be used in real network. As an effective method for congestion control, Active Queue
Management plays an important role in improving the QoS of the Internet. An effective self-tuning
fuzzy queue management algorithm based on the mathematical model of TCP congestion control
mechanism was presented. With the application of this algorithm, routers in IP network regulate its
packet drop probability through a fuzzy self-tuning algorithm according to the queue length in the
buffer. The main advantage of this algorithm is that the queue length can keep stable in a variety of
network environments without the difficulty of parameter configuration.
Keywords：congestion control，active queue management，fuzzy logic
