（控制理论与控制工程专业论文）网络拥塞控制中主动队列管理及其公平性研究.pdf

硕士论文 网络拥塞控制中主动队列管理及其公平性研究 摘要 随着网络用户的增长和新业务的不断涌现，i n t e m e t 已发展为传送数据、语音、视 频等多媒体信息的综合业务网络。而数据流量的增长给路由节点造成了很大的负担，使 得i n t e m e t 面临不断增加的丢包率和网络延时，导致了越来越严重的网络拥塞问题。 拥塞控制是保证网络运行和鲁棒性的关键，然而许多流在协议中缺少拥塞响应机 制，在竞争资源时会抢占更多的网络带宽，造成了资源分配的不公平性。因此，寄希望 中间节点的主动队列管理( a q m ) 来解决网络拥塞和保证服务质量。本文针对网络中的稳 定性与公平性问题进行了研究，并对几种a q m 算法的缺陷给出了解决方案。 ( 1 ) 分别研究了基于单神经元梯度学习的自适应a q m 算法n g l 与基于单神经元强化学 习的自适应a q m 算法n r l 。n g l 算法采用梯度学习，算法简单，易于实现：n r l 算法是在梯度算法的基础上给出的，采用强化学习，能够根据网络环境自适应调整 神经元权值参数，具有较好的稳定性和对环境的适应性。它们不依赖于对象的模型， 对非线性，时变系统具有很强的自适应性。 ( 2 ) 针对c h o k e 算法队列的稳定性问题，将c h o k e 算法中流的鉴别机制与n r l 算法 相结合，给出了c h n r l 算法；针对c h o k e 算法在低负载时丢包率过大的问题，将 输入链路速率引入到算法中作为拥塞指示，并增加了一个启动门限值，给出了 r d t - c h o k e 算法。最后通过仿真验证了算法的有效性。 ( 3 ) 针对c s f q 算法的丢包策略不适用于t c p 流以及公平性能对缓存过于依赖的问题， 给出了采用r e d 缓存管理策略改进的c s f q 算法( r - c s f q ) ，对公平共享速率口的估 算进行了改进，将丢包概率与缓存占用率结合起来，减少了对t c p 流的过度丢弃， 降低了对缓存的依赖程度，更好地保证公平性。 关键词：网络拥塞控制，主动队列管理，强化学习，公平性，稳定性 a b s t r a c t w i mt l l eg r o w t ho fi n t e r n e tu s e r sa n dt h ec o n t i n u o u se m e r g e n c eo fn e ws e r v i c e s i n t e m e t h a sd e v e l o p e di n t oa c o m p r e h e n s i v eb u s i n e s sn e t w o r kw h i c hu s e df o rt r a n s m i t t i n gd a t a , v o i c e , v i d e oa n do t h e rm u l t i m e d i ai n f o r m a t i o n b u tt h eg r o w t ho fd a t at r a f f i cc a u s e sa g r e a tb u r d e n t ot h er o u t i n gn o d e a sar e s u l t ，t h ei n t e m e tf a c e st h ei n c r e a s i n gr a t eo fp a c k e tl o s sa n d n e t w o r kl a t e n c y , w h i c hr e s u l ti nt h es e r i o u sp r o b l e mo fn e t w o r k c o n g e s t i o n c o n g e s t i o nc o n t r o li st h ek e y t oe n s u r en e t w o r ko p e r a t i o na n dr o b u s t ，b u tb e c a u s em a n y s t r e a m sa r el a c ko fc o n g e s t i o nm e c h a n i s mi n p r o t o c o l ，w h i c ho c c u p ym o r en e t w o r k b a n d w i d t h , r e s u l t i nt h e u n f a i rd i s t r i b u t i o no f r e s o u r c e s t h e r e f o r e ，a c t i v eq u e u e m a n a g e m e n t ( a q m ) i sh o p e dt os o l v et h en e t w o r kc o n g e s t i o na n dg u a r a n t e et h eq u a l i t yo f s e r v i c e t h i sp a p e rf o c u s e so nt h es t a b i l i t ya n df a i r n e s so fn e t w o r k ，a n dp r o p o s e st h es o l u t i o n a i m e da ts e v e r a la q md e f e c t s ( 1 ) t w oa d a p t i v ea q ms c h e m e ，n g la n dn r la r ep r o p o s e db a s e do nn e u r o nl e a r n i n g n g l a d o p t sg r a d i e n tl e a r n i n g , w h i c hi ss i m p l ea n de a s yt oi m p l e m e n t n r li sb a s e do nt h e g r a d i e n ta l g o r i t h m ，w h i c hu s i n gr e i n f o r c e m e n tl e a r n i n g n r lw h i c hh a sg o o ds t a b i l i t ya n d a d a p t a b i l i t yc a na d j u s tt h en e u r o np a r a m e t e r si na c c o r d a n c ew i t ht h ec h a n g eo ft h en e t w o r k e n v i r o n m e n t t h et w oa q m a l g o r i t h m sd on o td e p e n do nt h eo b j e c tm o d e la n dh a v e a d a p t a b i l i t yf o rn o n l i n e a r , t i m e - v a r y i n gs y s t e m s ( 2 ) t h ec h n r la l g o r i t h mw h i c hb a s e do nt h ec o m b i n a t i o no fn r l a l g o r i t h ma n dt h e f l o wi d e n t i f i c a t i o nm e c h a n i s mi sp r o p o s e dt os o l v et h es t a b i l i t yp r o b l e mo f q u e u ei nc h o k e a l g o r i t h m a n di no r d e rt os o l v et h ep r o b l e mo fl a r g ep a c k e tl o s sr a t ei nc h o k ea l g o r i t h m w h e nt h el o a di sl o w ，t h ep a p e r p r o p o s e sr d t - c h o k ea l g o r i t h m ，w h i c hi n t r o d u c et h ef l o w r a t ea sc o n g e s t i o nn o t i f i c a t i o na n da d dat h r e s h o l dt os t a r tt h ef l o wi d e n t i f i c a t i o nm e c h a n i s m t h es i m u l a t i o n sv 舒匆t h ep e r f o r m a n c eo f t h e s et w oa l g o r i t h m s ( 3 ) i nt h ec s f qa l g o r i t h m ，p a c k e tl o s ss t r a t e g yi sn o ta p p l i c a b l ef o rt c pf l o wa n df a i r p e r f o r m a n c ei ss e n s i t i v et oc a c h e ，t h u sr - c s f qa l g o r i t h mi sp r o p o s e d r - c s f qa l g o r i t h m w h i c hi m p r o v e st h ee s t i m a t eo ff a i rs h a r er a t ea ，c o m b i n e st h el o s sp r o b a b i l i t yw i t ht h e o c c u p a n c yr a t i oo fc a c h e ，a n de v e na d o p t st h ec a c h em a n a g e m e n ts t r a t e g ys i m i l a rt or e d t h es i m u l a t i o nr e s u l t ss h o wt h er - c s f q a l g o r i t h mr e d u c et h eo v e rd i s c a r d i n go ft c pf l o w a n da s s u r et h ef a i r n e s so fq u e u e k e y w o r d s ：n e t w o r kc o n g e s t i o nc o n t r o l ，a q m , r e i n f o r c e m e n tl e a r n i n g ，f a i r n e s s ，s t a b i l i t y i l 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名：j 起j 罗年g 月8 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：二逸j 选 罗年z 月牙日 硕士论文 网络拥塞控制中主动队列管理及其公平性研究 1 绪论 1 1 引言 随着计算机网络的发展，互联网上的用户和应用都在急剧增加，通信业务量的增长 使得主干网络变得越来越拥塞。由于i n t e m e t 中大部分数据流使用的是t c p i p 协议， t c p i p 的拥塞控制机制是确保i n t e m e t 稳定性和鲁棒性的关键，这种机制为i n t e m e t 得到广 泛应用提供了重要保证。现有的t c p 协议下的拥塞控制机制必须在源端检测到拥塞时才 能降低发送速率，这时是以丢包作为拥塞指示的，然而在源端检测到拥塞到降低发送速 率之间花去了大量的时间，在这段时间内源端仍然按照链路所不能承受的速率发送数 据，便导致了更大的丢包率，使得网络更加拥塞【l 】。 拥塞是由于网络中有限的资源使得“需求”大于“供给 。这些有限的资源由多个 用户共享使用，由于缺少“中央控制 ，网络无法对用户使用资源的数量进行控制；缺 少“接纳控制 ，网络无法对用户的数量进行限制【2 j 。目前，i n t e m e t 上用户和应用的数 量都在迅速增长，如果不使用某种机制对资源的使用进行协调，将会导致网络拥塞的产 生。尽管拥塞的产生是由于资源的短缺，但增加资源并不能使得拥塞避免，有时甚至会 使得拥塞加重【3 】。这是由于i n t e r n e t 中资源和流量分布的不均衡性，由此导致的拥塞不 能通过增加资源的方法来解决。 同时由于各种新型业务的出现，人们对网络的服务质量( q o s ) 提出了更高的要求， 高效的q o s 支持显得越来越重要。而传统的i n t e m e t 网络是基于简单的“尽力而为 ( b e s t e f f o r t ) 服务模型，拥塞会增加分组传输时间，导致吞吐量降低、延时抖动、分组丢 弃，不能保证服务质量。因此，如何针对这些新应用进行拥塞控制，保证网络的稳定性 和公平性是近年来研究的热点问题。 1 2 拥塞策略的研究与发展 目前i n t e m e t 中大部分使用的是t c p i p 协议，因此t c p i p 控制受到了广泛关注。 这种协议下的拥塞控制是以数据包的丢失作为拥塞指示的，在路由器等中间节点的缓冲 区满后，就会对新到达的数据包进行丢弃，于是源端根据超时等隐含的网络信息判断拥 塞的产生，调整其发送窗口的大小，使得注入网络的数据流量得以降低。 t c p 拥塞控制机制对于当今的网络是必须的，然而其在效率、自相似性、公平性等 方面仍然有些问题需要解决，于是研究人员开始转向研究网络的中间节点设备( 如路由 器) ，期望通过增强它们的功能来实现源端无法实现的功能。就拥塞控制而言，网络的 中间节点设备可以提前准确了解网络的拥塞状态，能够根据拥塞状况更及时的实施资源 1 绪论硕士论文 管理策略，使网络避免拥塞，或尽快从严重的拥塞状态中恢复过来【5 1 。 a q m 是i e t f 为了解决网络拥塞问题而提出的一种队列管理机制，能够控制路由器 何时丢包，从而有效地管理队列长度，以支持端到端拥塞控制【6 】。a q m 采用一定的方 法检测网络拥塞的发生以及拥塞的程度，在缓冲队列溢出之前，能够对数据包进行必要 的丢弃，达到避免拥塞的目的。目前a q m 检测拥塞有两种方式，一种是基于队列长度 的，另一种是基于流的到达速率。基于队列长度的拥塞检测是通过观察路由器队列长度 实现的，而基于流的到达速率的方法是通过估算数据包的到达速率来实现的。 然而随着i n t e r n e t 应用需求的日益丰富和技术的不断发展，特别是实时多媒体业务 的广泛应用，使得i n t e m e t 上的数据流为多种异质流混合而成。在网络发生拥塞时，响 应流在源端检测到拥塞时能够降低其发送速率，而非响应流由于没有拥塞响应机制，仍 然按照原发送速率发送数据，使得网络带宽大多被非响应流占据，造成资源分配的不公 平性。 根据中间节点的主动队列管理研究的针对性不同，将其分为常规a q m 算法与公平 性a q m 算法。常规a q m 算法主要是解决网络的稳定性与鲁棒性问题，减少网络延时， 降低丢包率；公平性a q m 算法主要是针对异质流资源分配的不公平性，解决各种流资 源分配问题。 1 2 1 常规a q m 算法 在目前的网络中，r e d 算法【7 】是i e t f 所指定的唯一的a q m 算法，该算法监控路由器 缓冲区中的队列长度，一旦发现拥塞迫近，就采用报文丢失的方式通知源端调整发送窗 口的大小，从而降低源端的发送速率，达到降低网络拥塞程度，避免对更多的数据包进 行丢弃的目的。对面向连接的t c p 数据流来说，r e d 避免了对属于同一连接的数据包的 连续丢弃，避免了网络中出现全局同步现象，提高了连接的吞吐量。然而r e d 算法存在 两个明显的缺陷，第一是对参数设置敏感，参数的改变对性能的影响很大，当连接数目 增加时，缓冲区中的平均队列长度会逐渐增加；第二就是r e d 算法不支持区分服务，无 法保证公平性。 由于r e d 算法存在这两个明显的缺陷导致了队列的振荡和不必要的丢包，使得网 络延迟变大，吞吐量下降，链路利用率降低。t h o m a s 等人【8 】指出r e d 的稳定性主要是 由最大报文丢弃概率决定，队列振荡主要是由最小阈值与最大阈值之间的差值决定，建 立了r e d 的参数与网络带宽、延时、t c p 流数目之间的关系表达式，用于设置r e d 参 数。 针对r e d 存在的缺陷，近年来提出了各种新的a q m 算法，例如自配置r e d ，a r e d ， n r e d ，l r e d ，e r e d 9 1 ，r e m ，b l u e ，n a r e d 1 0 1 ，s r e d 11 1 ，a v q 1 2 】等。这些算 法能够在某些方面改进网络的性能，但在不同的环境下也存在着局限性。 2 硕士论文 网络拥塞控制中主动队列管理及其公平性研究 f e a g 等人在文献【1 3 j 中提出了一种参数自适应配置的r e d 算法( s e l f - c o n f i g u d n g r e d ) ，针对r e d 算法静态参数配置的局限性，通过在线自动配置参数机制来决定合适 的参数。这种算法能够有效的降低丢包率，并能在网络负载较重的情况下，维持较高的 链路利用率，并且实现简单，开销低，特别适用于主干路由器，但是参数的自动配置给 最大丢包概率带来的波动比较大，导致队列波动也比较大。 r e d 算法的拥塞指示没有考虑链路上复用的活动连接数对算法性能产生的影响。而 拥塞指示的发送速度是由最大丢包力际记概率来体现的，为了解决这个问题，x u 等人在 文酬1 4 】中提出了一种在线改变最大丢包标记概率参数的自适应r e d 算法( a p e d 算法) 。 a r e d 算法基于r e d 算法，其主要思路是根据连接数目、流量的多少，在数据包到达 时更新平均队列长度，然后根据平均队列长度动态调整最大丢包标记概率的大小。当平 均队列长度在最小阈值附近振荡时，说明早期拥塞指示过度，就降低最大丢包标记概率； 当平均队列长度在最大阈值附近波动时，说明早期拥塞指示不够，就增大最大丢包标记 概率。a r e d 算法保留了r e d 的优点，并提供了比r e d 更低的包丢失率和更高的带宽 利用率。但常数口、岁的取值过大可能导致最大丢包际记概率的频繁振荡，不利于网络 性能稳定。 z h o u 等人提出的n o n l i n e a rr e d 1 5 】是基于r e d 的改进算法。由于r e d 采用线性丢 包策略，在轻负载时r e d 的参数设置使得丢包概率过大，而重负载时参数设置使得丢 包又过于柔和，导致当采用r e d 算法时的吞吐量较低，因此提出了非线性r e d 算法。 此算法认为r e d 算法的不稳定性是由于其采用的线性丢包函数，故其提出了用二次函 数来代替线性函数的a q m 策略。 r e d 算法采用队列长度作为其标记或丢弃策略的依据，这种策略尽管简单，但在动 态网络中常常是不稳定的，如果采用自适应参数调整，则可以解决这种问题。w a n g 等 人提出了一种l r e d 算法【1 6 1 ，测量最新的丢包比率，用它来作为队列长度的补充来自适 应调整丢包概率。仿真表明这种算法可以取得较快的响应速度和较好的鲁棒性。此种算 法遵从两条设计原则：当队列长度接近期望队列长度时，丢弃概率应当接近于丢包比率， 当队列长度变大( 或小) 时，丢弃概率也应该变大( 或小) 来调整队列长度。 针对队列稳定性问题，l o w 等人在文献【l7 】中提出了一种基于随机指数标记的主动队 列管理算法( r e m ) ，这种算法的目标是为了获得高的利用率和低的丢包率与延时。主要 思想是将拥塞测量同传统的基于丢包、队列长度、延时的测量方法中分离出来，提出了 基于代价的拥塞度量策略。r e m 算法具有如下特征：它试图使用户端的速率和同链路 容量相匹配，使队列稳定在一个较小的期望值附近而忽略用户数量对稳定性的影响；端 到端的标记丢弃基于对链路代价和的简单并精确的测量。为了提高r e m 的鲁棒性，t a n 等人在文献【1 8 】中提出了自适应r e m 算法，这种算法是基于动态改变r e m 的代价函数。 r e d 算法使用平均对列长度来预测拥塞程度，而f e n g 等人在文献【1 9 】中提出了比较 3 1 绪论硕士论文 著名的b l u e 算法，它通过使用实际队列长度来反应拥塞状况，使用丢包事件和链路空 闲事件来管理拥塞。该算法需要的缓冲比r e d 要小，因此可以减小数据延迟，增强了 传输实时数据的能力，但该算法缺乏r e d 早期的告警机制，对拥塞变化的反应比较慢， 从而使队列长度发生较大的波动，而且公平性较差。w e i 和q i a n 在此基础上，提出了 一种基于丢弃最高速率流的加强型b l u e 算法【2 0 1 ，在这种算法中，网络中间节点使用丢 包事件和链路历史利用信息，提示拥塞的发生，不需要使用平均队列长度作为拥塞指示。 该算法的公平性较好，延迟较低，消除了对突发流的偏见，保护了一些脆弱的流，但队 列波动比较大，不利于网络的稳定性。 针对网络拥塞控制问题，目前很多研究者基于t c p 源端和p 中间节点的结合，利 用各种控制理论的方法，有的采用经典控制理论的方法，如p i ，p i d 等，还有的利用智 能控制的方法，如模糊控制，还有的利用最优控制的方法。 有很多研究者从网络模型的角度研究网络拥塞。s h i n 等人【2 1 】研究了端到端的对偶 模型，他们利用该模型来解释由t c p a q m 构成的闭环系统的平衡性问题，通过网络源 端和中间节点的分布式计算，从而得到全局最优解。而m o r r i s 在文献瞄】中建立了近似 的流体模型，可以利用此流体模型设计控制器。该流体模型通过把网络的几个组成部分 看作各自独立的单输入单输出的连续事件模型。通过该模型了的稳态性能分析，得到 t c p 吞吐量、平均队列长度、丢包率。 在文献【2 3 】中，h o l l o t 等人将p i 控制算法运用于主动队列管理中，能够将缓冲队列 控制在期望值附近。其基本思想是通过实际缓冲队列长度g 与期望队列长度垡耐进行比 较，通过记录差值并对其进行比例积分控制来确定新到达包的丢弃概率。 由于p i 控制器在参数整定上的试凑方法具有盲目性，算法的瞬态性能指标也不够 理想，因此通过引入微分环节来增强系统的响应能力。f a n 等人在文献【2 4 】中提出了p i d 控制器，p i d 控制器设计的作用在路由器上的队列管理算法与p i 控制算法相比，不仅提 升了算法的瞬态性能，同时也没有降低系统的稳态性能。 在文献【2 5 】【2 6 】中提出了基于最优理论的a q m 算法，它的目标是为了实现一个网络系 统效用函数的最大化，效用函数的最大化是通过调节源端节点的发送速率来实现的。在 文献【2 7 】知道用户端的效用函数( 基于不同的流量控制协议) 是不同的，分别为：一1 xv , 与 logx，基于最优理论的算法描述如下：(为了使得下面的效用函数取得最大值)， j r ( x a = w r ( x a p r p b r ，x ? 、) 其中t 是用户端，的发送速率，u ( t ) 是用户，的效用函数，参数w ，与孱是为了权衡最 大的效用与最小的丢包率，p ( 墨，x ) 是奖惩函数。 1 2 2 具有公平性的a q m 算法 由于传统基于t c p 的应用所占比例不断下降，新兴的非t c p 应用得到不断增长，特 4 硕士论文网络拥塞控制中主动队列管理及其公平性研究 别是在实时多媒体应用方面，这些应用不采用拥塞控制策略，与传统基于t c p 的应用有 着不同的服务质量需求：( 1 ) 实时多媒体应用以一个固定速率发送数据，这种应用希望拥 塞控制机制对其丢包能够缓和一些，使得接收端的数据不至于出现较大的抖动；( 2 ) 由于 实时多媒体采用的是u d p 协议，不是面向连接的，不要求数据传输的可靠性，对数据的 丢失一般不要求重传。而t c p 具有响应机制，在发送端检测到网络发生拥塞时可以降低 其发送速率；而u d p 流属于非响应流，当网络发生拥塞时，其发送端仍将按照原发送速 率发送数据，这便导致u d p 流占有较大的网络带宽而具有响应机制的t c p 流只占有较小 部分的网络带宽，导致了带宽分配的不公平性【2 8 3 1 1 。针对网络的公平性问题，提出了一 些网络拥塞控制的公平算法，主要有f r e d ，c h o k e ，s f b ，b l a c k ，c s f q 等。 目前如何衡量网络的公平性并没有形成统一的标准，有几种公平性定义【3 2 1 ，其中一 种观点认为无论往返时间长短及传输链路上拥塞网关数的多少，每个连接都应获得相同 的吞吐量，而另一种观点认为每个连接在竞争时均应获得相同的网络资源。 j a i n 在文献【3 3 】中将网络的公平性定义为： 阢h ( 五) 2 以功2 籀 ，z i7 石l 其中x 表示分配给用户i 的网络资源，如响应时间、吞吐量、带宽、缓存等。0 f ( 力1 ， 完全公平时f ( = 1 ，此时所有的连接平均分配网络资源。 1 9 9 7 年l i n 和m o r r i s 提出t f r e d ( f i o wr a n d o me a r l yd e t e c t i o n ) t 3 4 】算法。该算法是最 早提出的基于r e d 的近似公平分配算法。其基本思想是：对每一个活跃流进行记账，根 据它在当前队列中的缓存占用情况( 即在当前的队列缓存中属于该流的分组个数) 来决定 该流的分组被丢弃的概率，从而提高了不同的流享用带宽的公平性。f r e d 算法建立在 r e d 基础之上，其基本框架与i 也d 一致。该算法对非响应流进行了有效的鉴别和限制， 遏制了非响应流大量侵占网络带宽，大大提高了各连接共享带宽的公平性。但该算法仍 存在缺陷：( 1 ) 计算量较大，需要维持每个流的状态表。随着通过路由器的流的数目的增 多，会给路由器带来沉重的负担；( 2 ) 在平均传输延时上会产生偏见。 p a n 等人【”j 提出 c h o k e ( c h o o s ea n dk e e pf o rr e s p o n s i v ef l o w s ， c h o o s ea n dk i i i f o ru n r e s p o n s i v ef l o w s ) 算法，此种算法可以用于区分响应流与非响应流。此算法的基本 思想是在路由器的缓冲队列中，在网络发生拥塞时，非响应流将占据更多的缓存，便可 以此来作为区分响应流与非响应流的依据。c h o k e 算法基本继承了r e d 的优点，只是少 量增加了一些额外开销。它简单、复杂性低、易于实现，并且与现有网络设施的兼容性 好，能以较低的代价在现有网络环境中实施。 f e n g 等人在文献【3 6 】中提出y s f b ( s t o c h a s t i cf a i rb l u e ) ，这个方法的思想是检测非响 应流( n o n r e s p o n s i v ef l o w ) 并限制它们的速率，使得它们不影响响应流的性能。s f b 需要 很少的状态信息，很少的缓存空间。但当非响应流的数量增加时，s f b 算法会混淆响应 l 绪论硕士论文 流和非响应流，从而限制了s f b 保护t c p 友好流的能力。 s t o i c a 等人在文献【3 刀中提出 c s f q ( c o r e - s t a t e l e s sf a i rq u e u e ) ，它的最主要的特征 是将实现公平分配所需的一些流状态信息插入到分组头部，即分组本身携带流状态信 息，在分组流经路由器时，路由器取出分组头部的状态信息，根据状态信息结合其它的 一些信息计算分组被丢弃的概率，从而对不同的流的分组实现不同的丢弃概率，实现带 宽的公平分配。 c h a t a n o n 等人在文献【3 8 中提出t b l a c k ( f o rb l a c k l i s t i n gu n r e s p o n s i v ef l o w s ) 算法， 可以用来区分响应流与非响应流，并认为之所以网络发生拥塞是由与长相关流所致，应 首先对其进行丢弃。b l a c k 的基本方法是提供一个公平带宽分配机制，目的是在不同 类型的流之间实现公平性。b l a c k 算法认为包的丢弃应该仅仅发生在必要的时候，并 随着缓存占用量的增加，丢包概率也增加。这样，当网络轻度负载的时候，不仅大的流 可以获得一部分带宽，并且大部分较小的流也得到了保护。此算法实现较为简单，只需 要少量的网络状态信息，能够很好的解决混合流占用带宽的公平性问题，存在的缺陷是 对活跃流数量估计不准确。 针对b l a c k 算法对活跃流数目估计的不准确性，l i 等人 3 9 】提出了一种新的比较方 式f n e ( f l o wn u m b e re s t i m a t i o n ) 来估计活跃流的数量。通过比较新接收到的包和队列中 随机选择的包来估计主动流的数目，并结合b l a c k 算法来计算丢包率。 1 3 本文的主要内容及安排 本文主要研究了网络服务质量以及网络中存在的公平性问题。将智能控制引入到主 动队列管理中，研究了两种基于单神经元的自适应a q m 算法，能够根据网络环境的变 化自适应调整神经元权值参数，提高了队列的稳定性；针对c h o k e 算法存在队列稳定性 差和在低负载时丢包率过大的问题，分别给出了相应的解决方案；针对c s f q 算法的丢 包策略不适合于t c p 流以及公平性能对缓存过于依赖的问题，给出了改进的c s f q 算法， 更好的保护了t c p 流，提高了公平性。 第一章阐述了网络拥塞控制的研究意义以及网络中存在的公平性问题，对主动队列 管理算法进行了分类，并重点介绍了近年来国内外在a q m 机制方面的研究现状，总结 了各种a q m 算法的优缺点。 第二章主要对t c p 流体非线性模型进行线性化，得至u t c p 窗口的动态特性和队列的 动态特性，由此得到简化的t c p 流体模型，然后对几种主动队列管理策略进行了描述， 最后通过n s 2 网络仿真软件对各种算法在吞吐量、丢包率、公平性指标等方面进行了比 较和分析。 第三章将人工智能引入到主动队列管理中，分别研究了基于单神经元梯度学习的自 适应a q m 算法n g l 与基于单神经元强化学习的自适应a q m 算法n r l 。它们以队列 6 硕士论文网络拥塞控制中主动队列管理及其公平性研究 长度和输入链路速率作为拥塞指示，不依赖于对象的模型，对非线性、时变系统具有很 强的自适应性。其中，n g l 算法采用梯度学习，算法简单，易于实现；n r l 算法是在 梯度算法的基础上给出的，采用强化学习，能够根据网络环境自适应调整神经元权值参 数，具有较好的稳定性和对环境的适应性。 第四章针对c h o k e 算法队列稳定性差的问题，采用c h o k e 算法中流的鉴别机制 与n r l 算法相结合，给出的c h n r l 算法，在保证公平性的前提下，将n r l 算法的参 数自调整机制引入到队列管理算法中，提高了队列的稳定性，保证了服务质量；针对 c h o k e 算法在低负载时丢包率过大的问题，将输入链路速率引入到算法中作为拥塞指 示，并增加了一个启动门限值，给出了r d t - c h o k e 算法，在保证公平性的前提下，降 低了丢包率，提高了带宽利用率。 第五章针对c s f q 算法的丢包策略不适用于t c p 流以及公平性能对缓存过于依赖 的问题，给出了采用r e d 缓存管理策略改进的c s f q 算法( r - c s f q ) ，对公平共享速率口 的估算进行了改进，将丢包概率与缓存占用率结合起来，并采用了类似于r e d 算法的 缓存管理策略，减少了对t c p 流的过度丢弃，降低了c s f q 算法对缓存的依赖程度， 提高了公平性。 第六章对本文的研究内容进行了总结，并提出了进一步的研究方向。 7 2 主动队列管理算法的研究硕士论文 2 主动队列管理算法的研究 本章首先通过采用流体理论和随机非线性微分方程得到t c p 流体模型，然后对几种主动队列管 理策略进行了描述，最后通过n s 2 网络仿真软件对各种算法在吞吐量、丢包率、公平性指标等方面 进行了比较和分析。 2 1 引言 基于端系统的t c p 拥塞控制对于保证i n t e m e t 的稳定性与鲁棒性起到了关键作用， 然而随着网络用户与网络服务的飞速发展，仅依靠t c p 拥塞控制机制来提高网络服务 质量是不够的，研究人员将注意力转向网络的中间节点，期望增强它们的功能来实现主 机端无法实现的目标湖】。 主动队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) 是i e t f 为了解决t c p 拥塞控制中 存在的问题而提出的一种拥塞控制机制。它能够检测到网络拥塞，并在路由器缓存队列 溢出之前，对数据包进行必要的丢弃并向端系统发出拥塞指示，端系统根据拥塞指示降 低数据的发送速率，从而达到降低丢包率和提高链路利用率的目的。 2 2t c p 流体模型 m is r a 在文献【冽提出采用流体理论和随机非线性微分方程来建 f f _ t c p 动态模型，若 忽略t c p 的超时机制，则可用如下一组非线性微分方程描述： 一d w ( t ) ：i 1 一掣微p ( ( f ) ) d t ，竺2 月( t - r ( ”一 “。 ( 2 1 ) 一d q ( t ) ：塑m c 、。 d t r 0 ) 式中参数的定义如下： 肛预期的窗口大小( 单位：包) g = 预期队列长度( 单位：包) r = 回路响应时间，等于排队延迟与传输延迟之和( 单位：秒) c b 连接能力( 单位：包秒) 陪连接数目，即网络负载 萨丢弃标记概率 上述微分方程所描述的t c p 动态模型的框图如图2 1 所示： 硕士论文 网络拥塞控制中主动队列管理及其公平性研究 图2 1t c p 流体模型框图 对式( 2 1 ) 所示的方程组进行线性化，设t c p 流的连接数目和往返时间尺为定值， 则式( 2 1 ) 可表示为： 1 佃几箩去一掣加啕 g ( w ，g ) = w ( t ) 一c h o l l o t 等人采用线性化方法，使用小信号分析法在平衡点q o = ( ，q o ，风) 处线性化 该模型，平衡点处满足矿= 0 和口= o ，则 矿= oj 眩p o = 2 删j 甄= 等 对式( 2 2 ) 中的厂( 肜，q ，p )g ( w ，g ) 在系统的平衡点q = ( ，q o ，既) 处求偏导，由 全微分方程可以得到 卜忙豢够眦卜肌咄沪静d i m 2 涮卜剐 叫， 【万香( r ) 2 菇万o ) 一去万g ( o 其中，d g = 形一甄，却= q - q 。，8 p = p p o ，均表示在工作点处的扰动。 对式( 2 4 ) 所表示的线性方程进行拉普拉斯变换可得相应的传递函数为： 一鱼竺。讽 椰= 等a p ( s ) ( 2 5 ) 币c n ( s ) ：j 辛册( s ) ( 2 6 ) j + 二 r 设名( 力表示t c p 的动态特性的传递函数，乞一0 ) 表示队列的动态特性的传递函 9 2 主动队列管理算法的研究硕士论文 数，由式( 2 5 ) 和( 2 6 ) 可得 一墨芷 o ) = 等 ( 2 7 ) 碍c n 乞。o ) ：j 年 ( 2 8 ) r 其中，( j ) 和乞雠( s ) 分别是以岛一= 一击和2 一茄为极点的低通滤波器， 通过以上建模过程的分析，可以得到如图2 2 所示的t c p i 流体模型的简化框图。 r 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一1 ： ： i ： 斗吨丑臣 叫三) 事g ： ： ： ； l _ = 图2 2t c p 流体模型简化框图 2 3 几种标准的a q m 算法 2 3 1r e d 算法 r e d 算 法( r m a d o me a r l yd e t e c t i o n ，随机早期检测) 【刀是f l o y d 和j a c o b s o n 提出的最早 的a q m 算法，也是目前最为常用的一种a q m 算法。基本思想是路由器通过监控队列的 平均队列长度来探测拥塞，一旦发现拥塞逼近，就随机地选择源端来通知拥塞，使它们 在队列溢出之前降低发送数据速率，以缓解网络拥塞。r e d 算法需要计算平均队列长度 和丢包率。 ( 1 ) 计算平均队列长度： r e d 在计算平均队列长度a v g 采用了类似低通滤波器带权值的方法：, , a v & = ( 1 一心) a v g g + q x ( 2 9 ) 其中q 是瞬时队列长度，心是一个权值，反映a v g q 叉针f q 的敏感程度，它“过滤掉由于 i n t e m e t 数据突发性导致的短期队列长度变化。 ( 2 ) 计算丢包概率： 计算平均队列长度的目的是为了反映网络拥塞，根据拥塞的程度来确定丢包概率， 需设定两个闽值m i n j l 与m a x 抽以及最大报文丢弃概率m a 】【，。当报到达路由器时，r e d 计算出平均队列长度口瞄，者ia v & r a i n 曲时，则不对包进行丢弃，若m i n 肪a v g 。m a x l l 1 0 硕士论文 网络拥塞控制中主动队列管理及其公平性研究 p = 睁呱 新到达的包将被丢弃。 a v g q o ， 0 是一个较小 的常数， z 】+ = m a x z ，0 ) ，岛( f ) 是t 时刻队列，的总的缓冲区占据量( 瞬时队列长度) ，2 5 i 是 目标队列长度，x l ( t ) 是f 时刻队列珀勺总的输入速率，c t ( t ) 是t 时刻队列，可获得的带宽。 常数q 依据不同的队列自身确定，它用来权衡传输利用率与队列延时。y 用来控制在 r e m 跟随网络状况改变的相应速度。 由易( f ) 可以求得队列z 在t 时刻的标记概率函数( 为大于1 的常数) 竹( f ) = 1 一矿“ ( 2 1 2 ) 则端到端的丢弃概率为： 卜i - ( 1 一( f ) ) = 1 一一乞t n o ( 2 ，1 3 ) l - - 1 2 3 3p i 控制算法 p i 算法【2 3 】将控制理论运用于主动队列管理中较好的改