（通信与信息系统专业论文）ip网络主动队列管理算法研究.pdf

哈尔滨工程大学硕士学位论文 摘要 近年来，音频、视频等多媒体应用在h t e m e t 上不断涌现，越来越严重 的网络拥塞问题逐渐暴露出来在网络通信中，拥塞容易造成延迟和吞吐量 等q o s 性能指标下降，是影响带宽、缓存等网络资源利用率的关键因素，为 解决这些问题，仅增加互联网的容量是远远不够的，还需要有灵敏和有效的 网络拥塞控制的方法。因此拥塞控制一直是网络研究领域的热点问题。 研究的主要内容及创新点如下： 本文首先介绍了m t e r n e t 中的拥塞控制机制，主要讨论了p 层的拥塞控 制策略，针对目前广泛使用的主动队列管理策略中的r e d 算法进行了详细研 究，本人在论文中完成的主要工作如下： ( 1 ) r e d 算法的平均队列长度是在分组到达时利用e w m a 形式计算的平 均队列长度，所以平均队列长度的计算反映更多的是分组到达速率而不是缓 存的当前及下一时刻的占用情况。即使下一时刻的缓存中队列为空，丢弃可 能还在继续，这将造成链路利用率的大大降低。针对这一问题，本文就r e d 算法做了改进，在平均队列长度的计算中考虑下一时刻的数据包的速率和缓 存占用情况，并将两者结合起来进行丢弃决策，解决了网络利用率的问题。 利用网络模拟软件n s 进行仿真，实验结果表明，改进r e d 算法在分组丢弃 比例和链路利用率上都优于r e d ，增强了r e d 的自适应性。 ( 2 ) 研究了网络的非线性、时滞、不确定特点，结合预测控制理论提出 一种新型主动队列管理( a q i v 0 策略p s r e d ，该算法基于单值预测控制思想， 为了实现快速控制，采用混合神经网络构造预测器，估计未来时刻队列的丢 弃概率。该算法实现了模型的在线反馈校正，对模型的精度要求不高，且速 度较快。仿真实验表明，该算法对网络参数变化具有很强的鲁棒性。 关键词：拥塞控制；随机早期检测；主动队列管理；预测控制；神经网络 哈尔滨工程大学硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，t h ea u d i of r e q u e n c y , t h ev i d e of r e q u 髓e ya n ds oo i l t h e m u l t i m e d i aa p p f i e a t i o n su n c e a s i n g l ye m e r g e do ni n t e r n e t , t h em o l ea n d1 1 1 0 1 e s e r i o u sn e t w o r kj a mq u e s t i o ne x p o s e dg r a d u a l l y i nt h en e t w o r kc o r r e s p o n d e n c e ， t h ej a me a s yt oc r e l l t eq o sp e r f o r m a n c ei n d i c e sa n ds o0 1 1t h ed e t e n t i o na n d v o l u m eo fg o o d sh a n d l e dd r o p s , i sa f f e c t sn e t w o r kl t c s o u r c , e s 啪f a c t o ra n ds oo n t h eb a n dw i d t h , b u f f e rk e ya t s p e c t s ，f o rs o l v e st h e s ep r o b l e m s ，o n l yi n c r e a s e st h e i n t e r n e tt h ec a p a c i t yi sb yf a ri m u t t i e i e n t , b u ta l s on e e d st oh a v ek e e na n dt h e e f f e c t i v en e t w o r kc o n g e s t i o nc o n t r o lm e t h o d t h e r e f o r et l a ec o n g e s t i o nc o n t r o l a l w a y si st h en e t w o r kr e s e a r c ha r e ah o tt o p i c n 瞎r e s u l t so f s t u d ya n dm a i ni d e ai nt h ep a p e ra 糟g i v e na sf o l l o w s ： i nt h i sp a p e r ! lt h ep r i n c i p l e so fc o n g e s t i o nc o n t r o lm e c h a n i s m sa 地i n t r o d u c e d f i r s t l y , a n dt h ec o n g e s t i o nc o n t r o li nt h ei pl a y e ri sd i s c u s s e di nd e t a i l 1 疆d a l g o r i t h mi nt h ea q m i st h ef o c u so f t h i sp a p e r m a i nr e s e a r c hw o r ki nt h ep a p e r a sf o l l o w s ： ( 1 ) a sl j u s tu t h ea v e r a g eq u e u el e n g t hw h e np a c k e t sa r r i v e s ，t h u st h e c o m p u t a t i o ns h o w sa v e r a g i n go fp a e k e ta r r i v a lr a t er a t h e rt h a nt h ec u r r e n tb u f f e r o c c u p a n c y t h ed r o p p i n go fp a c k e t sw i l lc o n t i n u ef o ral o n gt i m ee v e na t t e rt h e q u e u eh a sb e c o m ee m p t y t 1 l i sw i l ll e a d st oar a p i dd e g r a d a t i o no ft h el i n k u t i l i z a t i o n t on ，s o l v et h eq u e s t i o n , r e da l g o r i t h mi si m p r o v e di nt h ep a p e r , i n t h ea v e r a g ef o r m a t i o ni a 唱l hc o m p u t a t i o na n du t i l i z a t i o nb u f f e rs t o r a g e ，w h i c h c o m b i n e se w m aw i t hi n s t a n t a n e o u sq u e u es i z ef o rd r o p p i n gd e c i s i o n s f i n a l l y t h ec o m p u t e rs i m u l a t i o ni sc a r r i e di nn e t w o r ks i m u l a t i o ns o f t w a r en s s i m u l a t i o n s t u d i e ss h o wt h a tt h ei m p r o v e dr e da l g o r i t h mg i v e sb e t t e rl o s sr a t ea n dl i n k u t i l i z a t i o nc o m p a r e dt ot h eo r i g i n a lr e d a l g o r i t h m s ( 2 ) c o n s i d e r i n gt h en o n l i n e a r , t i m e v a r y i n ga n dt l n e c r t a i nc h a r a c t e r i s t i c so f n e t w o r k s , an e wa c t i v eq u e u em a n a g e m e n t ( a q m ) a l g o r i t h m i e p s r e dw a s 哈尔滨工程大学硕士学位论文 p r o p o s e db a s e d o i lp r e d i c t i v ec o n t r o lt h e o r y , w h i c hr e q u i r e sl e s sm o d e la c c u r a c y i no r d e rt or e a l i z et h ef a s tc o n t r 0 1 ap r e d i c t o rw a sc o n s l m c t e du s i n gm i xn e u r a l n e t w o r kt o p r e d i c tf u t u r ef r e q u e n t l yf o r m a t i o n sd i s c a r d i n gp r o b a b i l i t y b y e x p l o i t i n gf e e d b a c ka d j u s t m e n t , t h ep r o p o s e da l g o r i t h mr e q u i r e sl e s sm o d e l a c c u r a c y , t o g e t h e r 谢t hd e c r e a s e dc o m p u t a t i o na n df a s t e n e ds p e e d s i m u l a t i o n r e s u l t ss h o wt h a tt h i sa l g o r i t h mp o s s e s s e sr o b u s t n e s sa g a i n s tv a r i a n c e so fn e t w o r k p a r a m e t e r s k e y w o r d s ：c o n g e s t i o nc o n t r o l ；r a n d o me a r l yd e t e c t i o n ；a c t i v eq u e u e m a n a g e m e n t ；p r e d i c t i v ec o n t r o l ；n e u r a ln e t w o r k s 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献等的引用已在文中指出，并与参考文献相对应。除文中 己经注明引用的内容外，本论文不包含任何其他个人或集 体已经公开发表的作品成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 作者( 签字) ： 日 期彩叼年月日 哈尔滨工程大学硕士学位论文 第1 章绪论 从i n t e r a c t 发展趋势及设计机制出发，本章对碑网络中的拥塞进行了描 述，分析了拥塞产生的原因，对拥塞崩溃进行了理论研究，从而总结了拥塞 控制策略研究的意义及其目所在。在此基础上，给出了论文的研究内容和章 节安排。 1 1 引言 随着计算机、网络、控制等信息技术的发展，计算机网络已经成为了大 量分布式应用的基础。历史上主要采用传统电路交换的电话网，在电路交换 中，通信两端一旦建立连接，便拥有一条实际的物理线路，双方独占此线路。 由于线路独占，即使在通信两端不使用信道，即信道空闲时其他用户也不可 以使用该信道，造成了资源的浪费。但是在建立通话时预留足够的资源就可 以避免拥塞。 在过去的十几年中，i p 网络得到了迅速发展，所谓i p 网络即是采用 i p ( i n t e m e tp r o t o c 0 1 ) 协议的网络。随着网络规模、用户数量及业务量的爆炸式 增长，i n t c m c t 已经成为目前使用范围最广、发展速度最快的全球性i p 网络 信息基础设施。据统计，i n t e m c t 上9 5 的数据流使用的是t c m p 协议 最初设计的i n t e r n e t 是非面向连接的分组交换网络，所有的业务分组被不加 区分地在网络中传输。网络能给出韵唯一承诺就是尽自己最大的努力传输进 入网络的每一个分组，但它无法给出一个定量的性能指标，比如，吞吐量， 端到端的延时和分组丢失率等服务质量( q u l i t yo f s e r v i c e ，q o s ) 的界。相应地， 用户也无需进行业务许可请求，因此网络的性能不仅仅是其本身可以确定的， 还受用户施加负载的影响，很显然，这种网络体系结构缺乏一定的隔离和保 护机制，但是建立在这种体系结构上的传统网络应用与网络协议具有较强的 灵活性和适应性。随着网络的发展，其应用领域不断拓展，应用模式不断丰 富，加之商业化进程的推动，越来越需要对网络所传输的业务类型有一个较 哈尔滨工程大学硕士学位论文 为具体和明确的定义，即所谓的网络业务模型。从早期的综合服务数字网 o n t 呵a t e as e v c i c ed i g i t a ln e t w o r k ，i s d n ) 到集成服务( i n t e g r a t e ds e r v i c e ， i n t s e r v ) 资源预留( r e s o u r c er e s e r v a t i o np r o t o c o l ，r s v p ) ，再到后来的区分服 务( d i f f e r e n t i a t e ds e r v i c e ，d i f f s e r v ) ，这些都是结合应用的需要和技术的发展 提出来的。无论最终采用哪一种业务体系结构，其技术的核心都需要在恰当 的层次和粒度上对流量进行必要的管理，其中包括接纳控制、流量成形、队 列管理、调度和拥塞控制等诸多方面，但最基本和最核心的应该依旧是拥塞 控制”，因为很难想象一个时常有可能出现严重拥塞且无法及时加以恢复的 网络能够实现良好的q o s 保证。 事实上，拥塞现象的发生和h i t c m c t 的设计机制有着密切的联系，我们 可以采用以下几点对i n t c r n c t 的设计机制进行抽象”1 ； ( 1 ) 报文交换，与电路交换相比，报文交换通过共享提高了资源的利用效 率。但在共享方式下，如何保证用户q o s 是一个很棘手的问题。在报文交换 网络中可能出现报文“乱序”现象，对乱序报文的处理增加了端系统的复杂 性。 ( 2 ) 无连接网络。i n t e m e t 的节点之间在发送数据之前不需要建立连接。 无连接模型简化了网络的设计，在网络的中间节点上不需要保存和连接有关 的状态信息。但是使用无连接模型难以引入“接纳控制”算法，在用户需求 大予网络资源时难以保证q o s ；在无连接模型中对数据发送源的追踪能力很 差，给网络的安全带来了隐患；无连接也是网络中“乱序”报文出现的一个 主要原因。 ( 3 ) “尽力而为”( b e s t - e f f o r t ) 的服务模型。b e s t - e f f o r t 即网络不对数据传输 的q o s 提供保证。这个选择和早期网络中的应用有关。传统的网络应用主 要是f t p 、t e l n e t 、s m t p 等，它们对网络性能( 带宽、延迟和丢失率等) 的变 化不敏感，b e s t - e f f o r t 模型可以满足需要。但b e g - e f f o r t 模型不能很好地满足 新出现的多媒体应用的要求，这些应用对延时、速率等性能的变化比较敏感， 这要求网络在原有服务模型的基础上进行扩充。 2 哈尔滨工程大学硕士学位论文 1 2i p 网络中的拥塞 拥塞是一种持续过载的网络状态，此时用户对网络资源( 包括链路带宽， 存储空间和处理器处理能力) 的需求超过了其固有的容量。也就是说，拥塞发 生在通过网络传输的分组数量开始接近网络处理能力时。图1 1 描述了拥塞 发生时吞吐量与延时、负载的关系。 蠹 茎 嚣 ( 1 ) 吞吐量曲线 负载数据包 负载数据包 ( b ) 延时曲线 图1 1 拥塞发生时吞吐量和延时与负载的关系 当网络负载较小时，吞吐量的增长和负载相比基本呈线性关系，延时增 长缓慢。当负载超过膝点( k n e e ) 之后，吞吐量增长缓慢，延时增长较快，网 络中数据分组开始排队、丢包，这时网络进入了一个中等的拥塞状态在这 个区域，网络继续传送负载，延时也在增长。当一些节点经历到中等的拥塞 时，其他节点则可能经历着严重的拥塞，以至于必须丢弃一些数据包。当网 络上的负载继续增加，超过崖点( 1 i 绚后，吞吐量急剧下降接近零，延时趋于 无穷。拥塞控制的目的就是在网络接近于拥塞崩溃点c l i f f 时能尽快检测到， 并采取措施减小网络负载，使网络恢复到正常状态，保持负载在c l i f f 点左侧 运行 拥塞一旦发生若不加以控制，往往会导致恶性循环，如果路由器没有空 闲的缓冲区，它必须丢弃到来的分组，当扔掉一个分组时，转发该分组的路 由器可能因为超时丽重传该分组，或者要重传多次，这样拥塞进一步加重， 出现了严重的延时。在通信量非常高的情况下，网络完全瘫痪，几乎没有分 3 g、艘譬 哈尔滨工程大学硕士学位论文 组能够到达。一般情况下，珀网络在每个节点( 路由器或其他设备) ，每一个 传输信道上都有一个分组队列。如果分组到达和排队的速度超出分组能够被 传输的速率，队列大小就不停的增长而分组经历的延时就变得越来越大一 般当接收分组排队线路的利用率超过8 0 时，队列的长度的增长速率就值得 警惕。这种队列的增长意味着分组在每一个节点经历的延时增长，同时队列 最后一定会溢出。 一般来说，拥塞产生的直接原因主要有以下三点： ( 1 ) 存储空间不足。几个输入数据流共同需要同一个输出端口，在这个端 口就会建立排队。如果没有足够的存储空间，数据包就会被丢弃，对突发数 据流更是如此。增加存储空间在某种程度上可以缓解这一矛盾，但如果路由 器有无限存储量时，拥塞只会变得更坏，而不是更好，因为在网络里数据包 经过长时间排队完成转发时，它们早己超时，源端认为它们已经被丢弃，而 这些数据包还会继续向下一路由器转发，从而浪费网络资源，加重网络拥塞。 ( 2 ) 带宽容量不足。高速数据流输入低速链路也会产生拥塞。根据香农信 息理论，任何信道带宽最大值即信道容量c = b l 0 9 2 ( 1 + s n ) ( n 为信道自噪声的 平均功率，s 为信源的平均功率，b 为信道带宽) 。所有信源发送的速率r 必 须小于或等于信道容量c 。如果r c ，则在理论上无差错传输就是不可能的， 所以在网络低速链路处就会形成带宽瓶颈，当其满足不了通过它的所有源端 带宽要求时，网络就会发生拥塞。 ( 3 ) 处理器处理能力弱、速度慢。如果路由器的c p u 在执行排队缓存， 更新路由表等功能时，处理速度跟不上高速链路。也会产生拥塞。同样，低 速链路对商速c p u 也会产生拥塞。 在网络通信中，拥塞是影响数据传输，造成延时，抖动等q o s 指标下降 和带宽、缓存等网络资源利用率降低的关键因素，如何更好的预防和控制拥 塞对于提高网络性能具有重要的意义。 1 3 拥塞崩溃的描述 i n t g “m e t 协议体系基于使用口协议，实现了无连接的端到端分组交换服 务。采用无连接设计给其带来了灵活、鲁棒的优势，但同时也要求人们必须 4 哈尔滨工程大学硕士学位论文 精心设计以使i n t e r n e t 在重载情况下也能提供良好的服务。实际上，不重视 分组交换的动态性会导致q o s 的严重下降或i n t e r n e t “彻底垮台”，这种现象 在技术上称之为“拥塞崩溃“1 。拥塞崩溃对i n t e r n e t 的威胁可以追溯到其早 期的发展中，1 9 8 4 年n a g l e f 壤告了由于t c p 连接中不必要的重传所诱发的 拥塞崩溃，1 9 8 6 - - 1 9 8 7 年间这种现象曾经多次发生，严重时一度使美国l b l 到u cb e r k e l e y 之间的数据吞吐量从3 2 k b p s 跌落到了4 0 b p s ”。除此之外，还 有其他一些诱发拥塞崩溃的原因，例如，未传递数据包( u n d e l i v e r e dp a c k e t s ) 导致的网络崩溃，分片拥塞崩溃”，即网络传输了大量的分组分片，但因为 无法在接收端重装成有效的分组而只好将它们丢弃；网络传输大量用户不再 需要的陈旧分组会导致另一种形式的拥塞崩溃现象。 通常情况下，拥塞崩溃发生在网络负载增加导致网络效率降低的时候。 在2 0 世纪8 0 年代中期最先提出的时候，拥塞崩溃主要是由于t c p 连接不必 要的重传那些正在传送或已经被接收方接收了的数据包。我们将这种由于不 必要的重传数据包而引起的拥塞崩溃称为典型拥塞崩溃。典型拥塞崩溃是导 致吞吐量只是正常情况下很小部分的稳定状况。典型拥塞崩溃的问题已经通 过定时器和改进t c p 应用中的拥塞控制机制而基本得到解决。 拥塞崩溃的另外一种潜在的形式则是由于未传递数据包而产生。当网络 传送的数据包在到达最终目的地之前被丢弃而导致带宽被浪费的时候，就会 出现由于未传递数据包而发生拥塞崩溃。由于处于拥塞连接中的部分带宽需 要用于其它任务，不同情况下可能会产生不同程度的拥塞崩溃。此类拥塞崩 溃的危险主要来源于网络上不断增加的大量开环应用，它们往往没有采用任 何端到端的拥塞控制机制。当数据包丢弃率增加时，采用。尽力而为”服务 机制的应用将会相应地提高发送速率，如此将会导致更加严重的灾难性后果。 一个由未传递数据包而引起的拥塞崩溃可以通过表1 1 所示仿真结果进 行阐释。该网络环境由三个t c p 流和一个u d p 流组成，它们共享一条带宽 为1 5 m b p s 的链路，u d p 流接收节点的接入带宽为1 2 s k b p s ( 相当于共享链路 带宽的9 ) ，其他各节点的接入带宽均为1 0 m b p s 当u d p 源端的发送速率 超过1 2 8 k b p s 时，大部分u d p 数据包将会在到达接收端之前被丢弃。表1 1 给出了在拥塞的1 s m b p s 链路上发送端的u d p 到达速率、u d p 有效流量( 定 义为u d p 接收端实际的接收速率) 、t c p 有效流量( 定义为t c p 接收端实际 s 哈尔滨工程大学硕士学位论文 的接收速率) 以及总的有效流量，以占拥塞链路带宽的百分比为单位。随着 u d p 发送速率的不断增加，t c p 有效流量几乎呈直线下降，而u d p 有效流 量基本保持不变。因此，随着u d p 数据流负载增加，它将影响t c p 数据流 和总的有效流量。在拥塞链路上，u d p 流浪费了本应属于t c p 流的带宽， 从整体上使得网络的有效流量降低至整个拥塞链路带宽的一个很小部分。 表1 1 三个t c p 流加一个u d p 流的网络仿真 u d p 发送速u d p 有效流t c p 有效流量合计有效流量 0 7o 79 8 59 9 2 1 81 7 9 7 39 9 1 2 6 2 69 6 o9 8 6 5 35 2 9 2 7 9 7 9 8 88 48 7 19 5 5 1 0 58 48 4 89 3 2 1 7 58 47 7 38 5 7 5 2 68 43 8 14 6 4 6 5 78 42 8 53 6 8 8 7 68 41 1 31 9 7 1 0 5 28 43 4 1 i 8 1 3 1 58 42 4l o 7 为了消除上述拥塞崩溃的潜在危险，有必要在终端节点上采取有效的端 到端拥塞控制策略，同时避免在拥塞链路上产生较高的丢包率。如果终端无 法辨识拥塞瓶颈链路只有一条还是多条，防止瓶颈链路高丢包率的最可靠的 方法就是采用端到端的拥塞控制机制，在出现丢包发生时降低发送速率。 1 4 拥塞控制策略的发展进程及现状 1 4 1t c p 拥塞控制 拥塞控制的主要目标是控制进入网络的数据流量，保证通信子网不会被 用户发送的数据流湮没，合理地使用瓶颈资源。 6 哈尔滨工程大学硕士学位论文 拥塞控制的研究开始于8 0 年代中期，1 9 8 4 年，n a g l e 首次提出了复杂 t c p i p 网络中存在的拥塞问题，特别是在由路由器连接的带宽差异较大的网 络中，容易发生“拥塞崩溃”现象，但在科研界没有引起足够的重视。直到 1 9 8 6 年l o 月，i n t e m e t 首次出现了一系列的拥塞崩溃现象，网络吞吐量急剧 下降，从l b l 到u cb e r k d e y 的数据流量从3 2 k b p s 降到了4 0 b p s 。此后， j a e o b s o n 等人开始对此进行研究，发现这是由于在网络拥塞状态下t c p 的行 为失常所致，为此j a c o b s o n 在t c p 中增加了拥塞控制算法( 即1 pt a h o e ) ， 于1 9 8 8 年提出了著名的“慢启动”( s l o ws t a r t ) ，“拥塞避免”( c o n g e s t i o n a v o i d a n c e ) 算法、“快速重传”( f a s tr e t r a n s m i t ) ；1 9 9 0 年的t c pr e n o 版本增 加了“快速恢复”( f a s tr e c o v e r y ) 算法，避免了网络拥塞不够严重时采用“慢 启动”带来的大幅度减小发送窗口大小的现象。后来又相继产生了几个主要 版本的t c p 端系统拥塞控制算法，即t c pn e w r e n o 。t c ps a c k , t c pv e g a s 。 版本不同，但都是遵守a i m d ( a d d i t i v e - i n c r e a s em u l t i p l i c a t i o n - d e c r e a s e ，加性 增加倍乘减小) 的窗口管理算法原理，即网络出现拥塞时，t c p 连接通过丢包 发现拥塞，窗口从w 减少至( 1 b ) w 。t c p 拥塞控制机制在i n t e r a c t 中的执行 有效地避免了拥塞崩溃现象的发生。 1 4 2 主动队列管理 以前路由器中最常用的队列管理是“尾丢弃”( 1 姒d r o p ) 从拥塞控制的 角度分析，它是一种拥塞恢复机制，已经在i n t e m c t 上成功工作了许多年。“首 丢弃”( f r o n td r o p ) 是另一种由队列溢出触发的缓存管理策略，当有新的分组 到达时，选择位于队列头部的分组丢弃。“随机丢弃”( r a n d o md r o p ) 在分组 丢弃策略中引入了随机概念，使得那些导致拥塞的主要链接在拥塞的恢复中 承担了主要的责任，“随机丢弃”网关增强了公平性，提高了大时延链接的吞 吐量。 如果路由器在拥塞发生前能采取一些预防措施，那么满队列问题是可以 得到解决的。主动的而非响应性的分组丢弃就是一种有效的手段，相应的队 列管理策略被称为“主动队列管理”( a c t i v eq u e u em a n a g e m e n t l ，a q m ) ，它是 近年来队列管理研究中的一个热点。a q m 和e c n “”( e x p l i c i tc o n g e s t i o n 1 哈尔滨工程大学硕士学位论文 n o t i f i c a t i o n , 显式拥塞指示) 结合，使得通知拥塞的信号不再是唯一的分组丢 弃。而可以采用标记分组来通知源端减速，这样会进一步提高链接的有效吞 吐量( g o o d p u t ) 。a q m 的主要技术目标是在减少排队时延的同时保证较高的 吞吐量。 虽然b r a d e n 等人在i e t f 提出a q m 的研究是在1 9 9 8 年。但与其密切相 关的“随机早期检测”( r a n d o me a r l yd e t e c t i o n ，r e d ) 算法的研究却是由来已 久了。早在1 9 9 3 年，f l o y d 和j a c o b s o n 就提出了i 疆d i “，当时的主要目的是 克服“早期随机丢弃”算法路由器偏袒突发业务而造成的不公平性问题。因 为在提出a q m 的研究时，r e d 是唯一一个能实现它技术目标的算法，所以 r f c 2 3 0 9 将其推荐为a q m 的唯一候选算法。本课题的研究重点也就是r e d 及对它的改进研究。 1 5 本文的工作和章节安排 本文的研究工作基于i p 层次，重点研究主动队列管理( a q m ) 策略，针对 r e d 算法提出了相应的改进，并在网络模拟器n s ( n e t w o r ks i m u l a t o r ) 中进行 了仿真实验。论文研究的主要内容及创新点包括以下几个方面： ( 1 ) 综述了口网络拥塞控制策略研究：分析了口网络中拥塞控制研究的 动机，从端系统和路由器两方面着手，介绍了i p 网络中现有拥塞控制策略的 研究和应用现状，对各主要算法的性能进行了分析。 ( 2 ) 重点介绍了随机早期检测r e d 算法，分析算法先进性和不足之处， 并对各种改进算法进行了介绍，对本文使用的仿真软件n s 进行了基本的介 绍，给出了本文仿真的一般步骤。 ( 3 ) 提出基于速率的改进r e d 算法。r e d 利用e w m a 形式计算平均队 列长度只在分组到达时进行，所以平均队列长度的计算反映的更多的是分组 到达速率而不是缓存的当前及下一时刻的占用情况。即使下一时刻的缓存中 队列为空，丢弃可能还在继续。这将造成链路利用率的大大降低。针对这一 问题，本文提出了一种改进的r e d 算法，在平均队列长度的计算中考虑下一 时刻的数据包的速率，并将两者结合起来进行丢弃决策，最后在网络模拟软 件n s 进行仿真，实验结果表明，改进r e d 算法在分组丢弃比例和链路利用 s 哈尔滨工程大学硕十学位论文 率上都优于r e d ，增强了r e d 的自适应性 ( 4 ) 基于预测控制理论提出了一种的有效的新型a q m 策略，针对网络的 非线性、时滞、不确定特点，为了实现快速控制，该策略采用混合神经网络 构造预测器，基于单值预测控制思想，估计未来时刻队列的丢弃概率。算法 实现了模型的在线反馈校正，对模型的精度要求不高，且速度较快。仿真实 验表明，该算法对网络参数变化具有很强的鲁棒性。 本文各章节的内容组织如下： 第2 章着重介绍了i n t e m e t 中t c p 基于窗口的端到端拥塞控制方法以及 球层采用的拥塞控制机制。 第3 章着重介绍随机早期检测算法r e d 算法拥塞控制机制及其改进算 法，并对其性能进行分析。 第4 章提出基于速率的改进r e d 算法，网络仿真实验表明这种改进方法 是有效的。 第5 章提出用混合神经网络预测机制来解决网络拥塞问题。 9 哈尔滨工程大学硕士学位论文 第2 章t c p i p 拥塞控制策略 t c p i p 协议族作为当今互联网的基石，有力地推动了网络技术的发展。 i n t e m e t 的成功很大程度上取决于拥塞控制的有效执行。本章主要分析基于源 端的t c p 拥塞控制机制和中间节点的m 拥塞控制机制，并对两者进行了对 比分析这也是本文研究工作的理论基础。 2 1t c p i p 协议 传输控制协议因特网协议( t r a n s m i s s i o nc o n a v lp r o t o c o la n di n t e r n e t p r o t o c o l , t c p f l p ) ”1 簇己经成为计算机网络世界开发系统互联的事实标准。 t c p 仰代表了一系列因特网互联协议，是具有相似特征的一簇协议的总称。 它定义了通过i n t e m e t 进行传输交换，处理传输中发生的故障，管理传输路 径等功能。t c p m 体系结构和开放系统互连参考模型( t kr e f e r e n c em o d e lo f o p e ns y s t e m si n t e r c o n n e c t i o n ，o s i r m ) ”体系结构类似，如图2 1 所示，采 用了分层体系结构，每一层完成特定的功能，各层之间采用标准接口传送数 据，和拥塞控制相关的有网络层、传输层、和应用层。 应用层f 1 h t t p1 e l n e ts m t pp o p 3s n h 伊d n s 传输层 t c p u d p 。 网络层i pi c h 缸a r pi g m p 网络接口层 e 出e r n e tf d d ia t mf rx 2 5i s d n 1 p ，i p 应用层 表示层 会话层 传输层 网络层 数据链路层 物理层 图2 1t c p i p 参考模型及各层主要协议。右侧o s i 参考模型层次结构 l o 哈尔滨工程大学硕十学位论文 网络层：定义了正式的分组格式和协议，即i p 协议。它的功能就是传输 由其它用户发送的口分组，并发送到正确的目的端。网络层往往是载体和用 户的接口 传输层：整个协议层次结构的核心，t c p 协议是一个面向连接的协议 传输层的任务是从发送端到目的端提供可靠、有效的数据传输服务，而与当 前网络或使用的网络无关。它可以使发送端和目的端主机上的对等实体进行 会话。同时，它还要处理流量控制，以避免高速发送方向低速接收方发送过 多报文而导致接收方无法处理。 应用层；享受以下各层为它提供可靠的传输，它包含所有的高层协议。 对用户来说，它是一些实际应用。最早引入的应用包括虚拟终端协议 ( t e l n e t ) 、文件传输协议( f t p ) 和电子邮件协议( s m t p ) 等。 t c p i p 作为一种因特网互联通信协议，目的是将各种异构计算机网络或 主机通过该协议实现互联现有的互联网包括成几十万个的全球范围内的局 域网，这些局域网通过主干广域网进行互连。 2 2t c p i p 拥塞控制策略 现有的拥塞控制策略从实施控制的位置，可以分为基于端主机的t c p 拥 塞控制和基于通信子网的i p 拥塞控制，端到端的拥塞控制仅在端系统执行， 此时中间节点仅负责向端系统产生和转发必要的反馈信息；后者是在网络的 中间节点处执行的，路由器除了转发数据包外还要负责通知端系统发送多少 数据进入网络，如图2 2 所示。 一节输 雉 嚣由 图2 2t c p i p 网络拥塞控制示意图 i l 叩 一l 吕 一 而刍一 星一 一厂二j 二套 。一一堕玺鎏苫薹鏊兰堡拦堡丝茎。 2 3 传输层拥塞控制策略- t c p 拥塞控制机制 2 3 1t c p 拥塞控制 t c p 采用基于窗口的速率控制机制，根据网络反馈信怠增加或减小发送 速率，利用分组丢失作为隐式的拥塞信号，从源端对数据传送的速率进行限 制。近年来，很多新的算法被引入到t c p 的传输控制中，这些算法包括慢启 动、拥塞避免、快速重传和快速恢复、选择性应答( s a c k ) 等。同时提出了不 同的t c p 实现版本，如t c pt a h o e 、t o pr e n o 、t c pv e g a s 等。t c p 拥塞控 制中用到的几个重要的参数如表2 1 。 表2 it c p 协议中的主要参数 参数含义 拥塞窗口p 栅叻 发送端在拥塞控制情况下一次最多能发送分组的数量 是接收端给发送端预设的发送窗口大小，只在t c p 连接建 通告窗 ( a w i n ) 立的初始阶段起作用 发送窗口( w i n ) 是发送端每次实际发送数据的窗口大小 慢启动阀值( s s t h r e s h ) 是拥塞控制中慢启动阶段和拥塞避免阶段的分界点 一个t c p 分组从发送端发送到发送端收到接收端确认 回路响应时闻( r 丁r ) a c k 的时间间隔 描述分组从发送到失效的时间问隔是判断分组丢失与否 超时重传计数器( r t o ) 网络是否拥塞的重要参数通常设为2 r t t ，或4 r i t 是能触发快速重传的发送端收到重复确认包a c k 的个 快速重传阀值 数，当超过阀值时网络就进入快速重传阶段，缺省值为3 t c p 拥塞控制主要由以下四个部分组成“”“： ( 1 ) 慢启动阶段 当建立新的t c p 连接时，c w n d 初始化为一个数据包大小( 缺省为 5 1 2 b y t e s ) ，源端按c w n d 大小发送数据，每收到一个a c k 确认，c w n d 就增 加一个数据包发送量。很显然，c w n d 在慢启动阶段每一个r t t 内加倍一次， 呈指数级增长：1 个、2 个、4 个、8 个，源端向网络中发送的数据量将急 1 2 哈尔滨工程大学硕士学位论文 剧增加。 ， ( 2 ) 拥塞避免阶段 当新的伽以 s s t h 础出，就执行拥塞避免算法，发送端在每次收到一个 a c k 时只增加l c w n d 个数据包，所以在拥塞避免算法中f w n d 的增长不是指 数的，而是线性的。发送端对最近未确认的数据包维护着一个重传定时器， 每收到一个新的a c k ，重传定时器的r t o 就重新设定。当源端发现超时时， 即认为网络发生了拥塞( 这一假定是基于由传输引起的数据包损坏和丢失的 概率很小( 小于1 ) ) ，此时s s t h r e s h 被设置为当前“俐的一半，c w n d 还要被 置l ，结果c w 耐 = s s t h r c s h ，t c p 就重新进入慢启动过程 ( 3 ) 快速重传和恢复阶段 当数据包超时时，c w n d 要被置为l ，重新进入慢启动，这会导致过大地 减小发送窗口尺寸，降低t c p 连接的吞吐量。快速重传就是在源端收到3 个 或3 个以上重复a c k 时，就断定数据包已经丢失，而不必等到r t o 超时。 快速恢复将s s t h r e s h 置为当前c w n d 的一半，重传丢失的数据包，设置 e w n d = s s t h r e s h + 3 。以后每收到一个重复的a c k 就将e w n d 增加l ，当收到新 的a c k 时退出快速恢复，设置c w 删v - - s s t h r c s h ，进入拥塞避免的状态。图2 3 显示了拥塞窗口随时间在四个阶段的变化情况。 董 芝 暑 o 时闯詹 ( i ) 慢启动和拥塞避免 勺 董 美 暑 ( ”拥塞避免及快速重传和恢复 图2 3 拥塞窗口随时闻在四个阶段的变化情况 以下是t c p 拥塞控制的算法： 初始化： w i r m r i m ( e w n d , a w i n ) 1 3 哈尔滨工程大学硕士学位论文 c w n d = l s s t h r e s h = 6 5 5 3 5 b y t e s ( 缺省街 当新有确认包a c k 到达时： i f ( c w n d s s t h r e s h ) s l o ws t w r t 删甩矛i a w l ( 升l d s e c o n g e s t i o na v o i d a n c e c w n d - - - c w n d + l c w n d ； 当收到等于或超过3 个重复a c k 时； s s t h r e s h = c w n d 2 ： c w n d = s s t h r c s h + 3 如果继续收到重复的a c k ； c w n d - - c w n d + i ； 如果收到新的a c k ； c ，眦趣s t h r c s n ；超时： s s t h r e s h = m a x ( 2 ，m i n ( c w n d 2 ，a w i n ) ) ； c w n d = - i ： 2 3 2t c p 拥塞控制的改进 t c p r c n o 算法源端在检测到拥塞后，要重传自数据包丢失到检测到丢失 时发送的全部数据包，而实际上其中有些数据包是正确传到接收端，不必重 传：t c p r c n o 算法在检测到单个包丢失时效果不错，但是如果在一个数据发 送窗口出现多个包丢失，由于一个r t t 只能重传一个数据包，所以必须等待 重传超时才能继续传输数据。针对t c pr e n o 算法存在的这些问题，s a c k 和n c w - r c n o 算法提出了相应的解决方案。s a c k 算法是在r e n o 基础上进行 扩展，对数据包进行有选择地确认和重传，这样源端就能准确地知道哪些数 据包正确地传到接收端，从而避免不必要地重传，减少延时，提高网络吞吐 量。n c w - r e n o 对r e n o 算法做了一些小的改进，消除了有多个分组从同一个 数据窗口丢失时对重传定时器的等待。改进考虑到源端在“快速恢复”阶段 1 4 哈尔滨工程大学硕士学位论文 收到的恢复a c k 是确认部分而不是全部出现在“快速恢复”阶段的分组。 n e w - r 翻a o 直到所有在“快速恢复”阶段开始时出现的分组都被确认。才会 退出“快速恢复”。v e g a s 算法”就是通过观察以前的t c p 连接中r t t 值