（模式识别与智能系统专业论文）基于神经网络的aqm算法研究.pdf

大连理工大学硕士学位论文 摘要 随着h n e m e t 的迅猛发展，作为提高网络性能的重要手段之一的网络拥塞控制是网 络的热点研究领域之一。拥塞控制的目标就是达到吞吐量的最大化、分组延迟的最小化、 各用户之间资源分配的合理化和尽可能少的丢弃数据包。作为t c p 端到端拥塞控制的 辅助手段，主动队列管理( a c t i v eq u e u em a n a g 锄e n t ) 使得中间节点参与到拥塞控制中， 是近年来拥塞控制的热点研究领域。 以r e d 算法为代表的主动队列管理( a q m ) 方案作为中间节点设备的增强机制， 在保证较高吞吐量的基础上有效控制队列长度，从而实现了控制端到端的时延，保证 q o s ( 服务质量) 的目的。但是研究表明大多数a q m 方案对网络的连接数变化、业务类型 及延时大小等网络状态非常敏感，不正确的参数设置常引起队列的振荡、吞吐量降低和 时延抖动加剧等不良作用。 本文针对上述问题，介绍了主动队列管理( a q m ) 的背景、优势和性能评价，并 简单分析了各种已有的a q m 算法。描述了t c p + a q m 拥塞控制机制的控制理论建模过 程，介绍了仿真平台n s 2 。采用神经网络及预测控制技术提出了一种新的a q m 的p i d 算法；同时对单神经元自适应p i d 算法加以改进，并对所提出的两种算法进行了深入系 统的仿真研究。仿真试验表明本文方法在一定程度上改进了某些现有算法的不足，改善 了系统的暂态性能，增强了对延迟、用户数变化等不确定性的鲁棒性，提高了网络利用 率。 关键词：主动队列管理；控制算法；神经网络；p i d ；预测控制 大连理工大学硕士学位论文 t h ef o m a tc r i t e r i o no fm a s t e r sd e g r e ep 印e ro fd u t a b s t r a c t w i 也t l l er 印i dd e v e l o p m e n to ft l l ei n t e n l e t ，n e t w o r kc o n g e s t i o nc o 曲o l ，嬲o n eo f 廿l e m 出m e a n st 0e i l l l a n c et 1 1 ep e r f b n n a n c eo ft h ei l e 铆o r k ，b e c o m e so n eo fm eh o tr e s e a r c h a r e a s t h ea i mo fc o n g e s t i o nc o n t r o l i st 0m a x i m i z et l l el i i l l 【u t i l i z a t i o n ，m i i l i m i z et l l ep a c k e t s d e l a y ，d i s 仃i b u t et l l en e 似r o r kr e s o u r c e sa m o n gu s e r s 陀a s o n a b l ya i l dd r o pp a c k e t sa sf i e w 嬲 p o s s i b l e a st h es u p p l e m e n t a r ym e a n so fm et c pe n d t o e n dc o n g e s t i o nc o l l 仃o l ，a q m ( a c t i v eq u e u em a i l a g e m e n t ) m a l ( e st l l ei m e 咖e d i a t en o d ej o i nn e 铆o r kc o n g e s t i o nc o n 缸d l ， a l l db e c o m e sah o tr e s e a r c ha r e ai nc o n g e s t i o nc o m r 0 1t l l e s ey e a r s a sa i le i l l l 锄c e m e n tm e c h a l l i s mf o rt h ee n d - t o e n dc o n g e s t i o nc o 劬l ，a c t i v eq u e u e m a i l a g e m e n t ( a q m ) s u c h 硒r e dc a nc o n 仃o lq u c u e1 e n g t t le 蚯c i e n t l yo nt h eb 嬲i so fk e 印i n g h i g h e rt h r o u 曲p u t b u tr e s e a r c hr e s u h ss h o wt h a tm o s ta q m s c h e m e sa r ev e 巧s e n s i t i v et 0 t h en e t w o r ks t a t e ss u c ha st h ev a r i e t yo fl i i l l 【n u m b e r ，s e i c e 帅ea i l dt i m ed e l a y t h e i n c o r r e c tp a r 锄e t e rs e t t i n gc a no f t e nb r i n gq u e u eo s c i l l a t i o n ，t h r o u g h p u td e 笋a d a t i o na n d d e l a y j i 仳ra c u 时a i l ds oo n t 协st h e s i sp r e s e n t st h eb a c k g r o 吼d ，a d v 锄t a g e s 龇l dp e r f - o 加1 a n c ee v a l u a t i o no fa c t i v e q u e u em a n a g e m e n t ，a n da n a l y s e st l l e e x i s t e da q ms c h e m e sa tf i r s t t h e nt l l em o d e l i n g m e m o do ft c p + a q mc o n g e s t i o nc o n 仃0 lm e c h a i l i s mb 舔e do nc o n 仃0 lt h e o r yi sd e s c 曲e d i n t 】r o d u c em ep l a t f o mn s 一2 ，b yu s i n gn e u r a ln e 觚o r ka i l dp r e d i c t i v ec o n 们l ，1 h sp a p e r p r o v ean e wa q ma l g o r i m mt h a tb 嬲e do nn e u r a ln m w o r k 强dp r e d i c t i v ec o m r 0 1 t h e s i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t l l m si m p r o v et h e 位m s i e n tp e 晌m a i l c e ，砒l di n c r e a s e r o b u s t n e s sa g a i n s tu n c e n a i r 哆s u c h 弱t i m ed e l a y 趾dv 撕e t yo fn u m b e ro fu s e r s ，锄di m p r o v e n e t ：w o r k sl l t i l i 洲o n k e yw o r d s ：a c t i v eq u e u em a n a g e m e n t ；c o n 勃吣la 1 9 0 r i t l l m ；n e u r a ln e t w o r k ；p i d ； p r e d i c t i v ec o r m - 0 1 i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定 ，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 彳 作者签名：生童蜩 导师签名：堕趁翌 猃墨年上月日 大连理工大学硕士学位论文 引言 i m e m c t 自出现以来得到了蓬勃发展，在过去相当长的时间里，t c p i p 协议族一直 是i i i t e n 俄网络稳定并获得健康发展的重要保证。传统网络应用的极大丰富和成功证明 了t c p 口协议族的成熟性。但是，近几年来i n t e n l e t 取得了飞速的发展，用户对网络资 源的访问需求呈现出爆炸性的增长。另外，随着网络的发展，其应用领域不断拓展，应 用模式不断丰富，如出现了v o d 点播以及视频会议等。新的服务对于服务质量( q o s ) 提出了更高的要求，然而当前的m e t 只能提供尽力而为的服务，而尽力而为的服务 并不能对这些新业务提供良好的q o s 保证【l 】。这些新需求的共同特点是要求有较低的网 络延迟和抖动，较高的访问带宽以及较低的数据包丢失率，这些比较严格的服务质量指 标暴露了传统网络协议和网络设备的一些重要问题，如协议在设计时缺乏性能优化方面 的考虑，网络运行效率较低，拥塞控制机制不够完善，没有有效的服务质量控制机制等。 针对这些新业务，t f 提出了一些服务模型和机制来满足服务质量要求，如集成服务 和区分服务等，这些技术的核心都需要在恰当的层次和力度上对流量进行必要的管理， 其中包括接纳控制，流量成形，队列管理，调度和拥塞控制等诸多方面，但最基本和最 核心的应该依旧是拥塞控制，因为很难想象一个有可能出现严重拥塞，无法及时加以恢 复的网络能够实现良好的q o s 保证。实施拥塞控制应该是其他q o s 机制正常工作的必 要前提。 主动队列管理是目前e t 拥塞控制的一个热点，其算法保证i n t e m e t 的稳定具有 十分重要的作用。网络中的拥塞来源于网络资源和网络流量分布的不均衡性。所以，拥 塞控制是尽量避免拥塞以及在拥塞发生时进行有效的控制并加以消除的重要手段，对保 证h t e m e t 的稳定性起着至关重要的作用。 1 9 9 8 年，b r a d e n 等人在i e t f 提出在路由器中使用主动队列管理技术( a 嘶v eq u e u e m a l l a g e m e n t ，a q m ) ，采用排队算法和数据包丢弃策略监控路由器缓冲区队列，提前检 测拥塞的到来并通知数据发送方。这样发送方可以在路由器缓冲区溢出之前调整数据的 发送数率，避免更严重的拥塞发生，并降低丢包率和提高链路利用率。s f l o y d 等人提 出的r e d ( 胁d o me 砌yd e t e c t i o n ，随机早期检测) 算法作为最早的主动队列管理算法， 已被广泛用来提高系统的综合性能。但是r e d 算法的性能对算法参数设置相当敏感， 随后又有很多改进r e d 算法和新算法相继被提出，比较有代表性的有s r e d ，f r e d ， d r e d ，b l u e ，r e m 等等，不过这些算法的提出都是基于启发式思维和仿真，缺乏系 统的方法，因此算法的稳定性和鲁棒性较差，一般只适用于特定的网络环境。 基于神经网络的a q m 算法研究 c h o l l o t 等人在2 0 0 1 年将经典控制理论引入到了a q m 算法的设计中，并利用频域 校正法设计了p i 控制器。由于p i 控制器的调节时间太长，于是又有人将带有反映队列 变化数率的微分环节的p i d ，p i d 控制器应用于a q m ，以获得更加的性能，后来又出 现了采用非线性控制理论的变结构控制器。随着智能控制理论的发展，智能控制的应用 领域也得到不断扩大，将智能控制理论应用于a q m 的设计也得到不断尝试，比如基于 神经网络的a q m 算法，能根据不同数据流的优先级动态调整丢包概率；基于单神经元 的p d 控制算法，可将现有多种算法视为它在某种情况下的特例。 控制理论的发展和应用，为主动队列管理算法的设计开辟了一条崭新的道路，使得 a q m 算法的设计可以转化为一种控制器的设计。通过给出一个包含t c p 源端和路由器 动态特性的网络受控模型，可以方便地进行算法性能分析和控制器设计，并且可以根据 控制目标进行参数整定，从而有效的提高拥塞控制效果。就本文的工作重点来说，主要 是集中于网络系统的控制机制来提高网络的性能。 大连理工大学硕士学位论文 1 主动队列管理 由于新的流类型发生了很大的变化，除了传统的e m a i l ，f t p ，t e l n e t 流量外，出现 了大量的多媒体数据流( 实时或非实时的视频，音频等) 。同时，网络的流量具有突发性， 自相似性，因而给网络的路由节点造成很大的负担，使得拥塞情况不断发生。在i n t e m e t 中避免高的包丢失率是非常重要的。当一个数据包在达到目的之前被丢失时，在它传输 过程中消耗的所有资源都被浪费，这无疑也造成了网络带宽利用率的降低。造成包丢失 率高的原因之一是，网络不能预见将可能出现的拥塞，并及时地提示数据源降低数据的 发送数率或者限制某些连接的传输数度，从而避免拥塞的出现。 因此，仅靠执行在端系统中的t c p 拥塞机制来避免拥塞的能力是有限的，必须在 网络的路由节点中引入相应的拥塞控制机制才能更有效地对拥塞进行检测和预防，因此 才引入了主动队列管理的思路【2 】。在a q m 中，网络中的路由节点提前检测拥塞的出现 并通知发送方，这样发送方可以在更严重的拥塞之前启动拥塞避免算法以缓解拥塞。 1 1 拥塞控制研究的目的与意义 当对网络资源的需求超过资源的可用容量时，拥塞发生。拥塞的结果导致数据分发 的延时，由于丢弃或丢失分组而造成的资源浪费，甚至严重时可能造成整个网络的崩溃。 因此，为了获得较好的网络性能，就需要采用特定的机制来阻止网络长时间拥塞。处理 拥塞主要有两种方法：拥塞控制和拥塞避免。前者是工作在网络过载后，也就是检测拥 塞，而后者是在网络过载发生之前采取一定措施来避免拥塞。一般来说，这两种方法都 用拥塞控制来描述。拥塞控制主要是设计一些机制和算法来限制网络资源的供需失调或 者当这种供需失调现象发生时能够动态地调整和控制网络传输业务。显然如分配更多的 缓冲区、提供更快的链路或者更快的处理器等静态方法无法达到拥塞控制的目的。 1 1 1 拥塞产生的原因以及拥塞控制的意义 在q o s 算法中，拥塞预防与控制机制是一个重要的组成部分，甚至可以说是网络提 供q o s 保证的前提条件。统计表明，出现网络性能下降的现象时，有3 1 是因为设备 故障，6 9 则是因为网络拥塞。如果网络中出现拥塞而无法及时处理，就根本谈不上任 何服务质量保证。必须具备灵活高效的拥塞检铡、预防与控制机制，才能保证网络的运 行效率和端到端的服务质量。需要注意的是，拥塞控制算法不是一种单独、孤立存在的 算法，网络中间节点( 路由器、交换机等) 所具备的一些通用功能组件，如流分类、测速、 标记、排队、队列调度、整形、选择性丢弃等，都可以认为具有进行拥塞控制的辅助职 基于神经网络的a q m 算法研究 能。在这些功能组件的共同作用下，才能提供比较完善的拥塞控制与q o s 保证机制，从 而在这些核心机制的支撑下更好地满足网络业务的各种需求。 网络拥塞有多方面的原因，网络中的各种构成组件都有可能成为拥塞的根源。可能 是由于端系统不负责任地发送大量数据包，也可能是中间路由器的处理速度相对缓慢或 缓冲区管理方案不善，也可能是网络上某些输出链路带宽过小等。当网络发生拥塞时， 整个网络的资源利用率下降，用户感受到的网络服务质量被降级，严重时甚至会产生拥 塞崩溃。此时，网络不断地在传送将会被丢弃的无用包，而主机则不断地因为发送超时 而进行重传，形成一个恶性循环，使得网络的有效吞吐量接近于零，整个系统处于崩溃 的边缘，所有用户的服务都受到影响。 当网络发生拥塞时，最直观的解决方案就是为网络扩容，增加c p u 速率、路由器 缓冲区大小以及链路带宽等网络资源。但事实证明，这种方案只能局部地解决眼前问题， 拥塞在全局范围内仍然存在，只不过是从一个地方转移到了网络中另一个地方而己。由 此可见，网络拥塞的预防与控制应该是一个从全局角度进行考虑的问题。只有主机与路 由器均实现了有效的拥塞控制机制，消除通信路径上的瓶颈链路，整个网络才有可能高 效运转。应该注意到，仅仅有这些措施仍是不够的。除了提供这些机制外，还必须有应 用程序设计人员、网络供应商、网络管理人员的共同合作，才能真正让每个网络用户满 意、公平地使用公共网络资源。例如，应用程序设计时，要考虑到可能给网络造成的拥 塞，不能只为自己争取最大带宽而不顾其他用户的利益；网络供应商要采用部署了拥塞 控制机制的路由器；网络管理员要在自治域内定义良好的管理策略，控制用户对资源的 占有份额。 1 1 2 拥塞控制算法的分类 拥塞控制算法按照控制论的观点来看，可分为开环和闭环控制两大类。前者的关键 在于，它致力于通过良好的设计来避免问题的出现，确保问题在一开始就不会发生。一 旦系统安装并运行起来，就不再做任何中间阶段的更正。开环控制工具的功能包括决定 何时接受新的数据流( 接纳控制，a d m i s s i o nc 彻n d l ) ，何时丢弃分组( 缓冲接受算法，b u 翻f e r a c c 印t a l l c e 砧g o r i t ，以及丢弃哪些分组( 行为识别算法，b e h a v i o ri d e n t i f i c a t i o n a l g o r i t l l l l l ) ，还包括在网络的不同节点作调度【3 j 。所有这些功能的共同之处显现出，它们 在做出决策的时候不考虑网络的当前状态，是一种醉态解决方案。与之相比较，闭环解 决方案建立在动态反馈的基础上。这种方法要解决三个问题：1 ) 监控网络状态，检测 何时何地发生了拥塞；2 ) 将信息传送到可能对拥塞负责的地方；3 ) 调整系统操作以 更正问题。从另一个角度来说，在数据报子网如i n t e m e t 中，根据拥塞控制措施所在的 层次，可分为端系统的传输层拥塞预防与控制方案，以及子网内部网络层的拥塞控制。 大连理工大学硕士学位论文 ( 1 ) 主机端t c p 基于窗口的端到端拥塞控制机制 t c p 的拥塞控制采用的是基于窗口的端到端的闭环控制方式【3 】1 4 】【5 1 。t c p 的拥塞控 制包括4 个核心技术：1 9 8 8 年出现了“慢启动”( s l o ws t a l d ，“拥塞避免 ( c o n g e s t i o n a v o i d a n c e ) 算法：1 9 9 0 年增加了“快速重传”( f a s tr e 仃趾s m i t ) ，“快速恢复 ( f a s t r e c o v e r y ) ，算法避免了网络拥塞不够严重时采用“慢启动”算法而造成过大地减小发送 窗口尺寸的现象【6 】，后来的学者和研究人员在此基础上对t c p 的拥塞控制进行了更为细 致而深入的研究，不断完善和改进了算法中存在的缺陷，相继产生了5 个主要版本的 t c p 流量控制算法，他们分别是t a l l o e ，i ：己i e n o ，n e w 黜n 0 ，s a c k 和v e g a s t c p t a l l o e 【7 j x t c p 的早期版本，它包括了最基本的t c p 拥塞控制算法，由“慢启动”、“拥塞避免 和“快速重传 三部分组成。“快速重传根据3 个重复的确认分组来判断分组丢失的 出现，从而减少等待“重传时钟”超时的过程，提高了分组的传输速率。除此之外，t a l l o e 对往返时间的计算也作了相应的改进，以便更准确地设定超时重传的时间。r e n o 瞵1 在 t a h o e 的基础上增加了“快速恢复”算法来提高拥塞恢复的效率。在r e n o 中，源端在 接受到足够多的重复a c k 之后，用接着到来的重复a c k 触发新数据分组的发送。只有 在接收到新发分组的a c k 后，源端才退出“快速恢复 阶段。r e n o 的“快速恢复优 化了单个分组从数据窗口丢失时的情况，比t a l l o e 的性能大有改进，但有多个分组从同 一数据窗口丢失时，依旧存在性能问题。s a c k 【9 j 是有效恢复同一窗口中多个分组丢弃 的一种技术途径。它在r e 肿上扩展，对数据包进行有选择地确认和重传，这样源端就 能准确知道哪些数据包正确地传到接收端，从而避免不必要地重传，减少时延，提高网 络吞吐量。n e w - r e n o 【1o 】没有选用s a c k 方法，而是尽力避免了r e n o 在快速恢复阶段的 许多被重传超时，利用一个a c k 确认部分发送窗口，立即重传余下的数据包。由于r 盯 ( 回路响应时间) 与网络运行状况有密切关系，所以出现了利用r t t 控制拥塞的v e g a u s 算 法【l l 】。v e g 嬲就是通过观察以前的t c p 连接中i 汀t 值改变情况来控制拥塞窗口。各个 版本的t c p 流量控制己被作为标准在i i l t e m e t 上广泛使用，但是依旧不够完善，需要新 的策略与算法来完善研究与应用中发现的新问题。近年来，又出现了t c p 显式拥塞通 告( e x p l i c i tc o n g e s t i o nn o t i f i c a t i o n ，e c n ) 和t c p 速率控制( t c pr a t ec o i l 仃0 1 ) ，其目的在 于让拥塞发现得更及时，让主机的行为更友好。这样有利于用户间达到全局协调，让整 体利益得到最优化。基于窗口的拥塞控制算法是依靠源端来限制数据包的发送，在源端 不需要对发送的流量进行整形。它的优势是易于实现，具有很好的健壮性。基于速率的 控制算法要对发送的数据流进行整形。以防止突发数据流的出现。这种算法的优点在于 如果源端的传输速率和网络匹配，就能减少路由器所需的缓冲区。 ( 2 ) 子网内部i p 层的拥塞控制策略 基于神经网络的a q m 算法研究 t c p 基于窗口的端到端拥塞控制对于i n t 锄e t 的稳定性起到了关键作用。然而随着网 络规模越来越庞大，结构日趋复杂，仅仅依靠端到端的拥塞控制是不够的，i p 层也必须 参与资源的控制工作。l p 层拥塞控制策略是指在路由器中采用包调度算法和缓冲管理 技术。目前，i p 层处理拥塞的方法有以下几种：随机早期侦测算法( r 锄d o me 砌y d e t e c t i 伽，r e d ) 1 2 】、轮转调度算法( r o u i l dr o b i i l ，r r ) 、公平排队算法( ( f a i rq u e u i n g ，f q ) 、 加权公平排队算法( w e i g h t e df a i rq u e u i n g ，w f q 等。其中r e d 算法提出较早，比较有名， 是少数被具体实现的算法之一。 1 2 主动队列管理算法 队列管理作为调度( s c h e d u l i n g ) 和缓存管理( b u f j 衙m a n a g e m e n t ) 机制的有效补充，目 的是通过适当丢弃进入路由器的数据包来控制队列长度。目前i n t 锄e t 中普遍采用的队 列管理方式是在路由其中设置每个队列长度的最大值，并在队列长度达到这一最大值时 就丢弃进入路由器的数据包，从而将队列长度控制在一定值之内。通常根据数据包丢弃 策略的不同，可将队列管理分为“去头”( d r o p 舶m 舶n t ) ，“去尾”( 怕pt a i l ) 和“随机 丢弃”m d o md r o p ) 几种形式。 所谓“去尾 就是当路由器缓存占满时丢弃最后到达的数据包，它是目前i n t e m e t 中所普遍采用的队列管理方式。去尾队列管理有两个主要缺陷：首先，由于只有当缓存 占满时才进行分组丢弃，因而源端获得拥塞信息相对较迟，从而使队列在多数时间内都 保持在近满的状态，造成了不必要的传输延迟；更为严重的是，采用去尾队列管理将有 可能导致网络的全局同步，由于当队列占满时，将会造成多个信源的分组丢失，这将使 它们同时降低自己的传输数率，从而使链路的利用率急剧下降。与去尾队列管理相反， 去头队列管理方式通过丢弃队列前端的分组使源端可以更快的获得链路的拥塞信息，从 而使网络的性能得以提高。除以上两种队列管理方式外，为避免全局同步的产生，还可 采用随机丢弃的队列管理策略。以上几种队列管理方式有一个共同的缺点就是：由于只 有当拥塞真正产生之后才进行分组丢弃，因而队列长度在多数时间内都保持在满的状 态。而降低队列在稳定状态时长度是非常重要的；同时，它也应该是队列管理的最重要 的目标。 在延迟和吞吐量之间应该有一个简单的折中。使队列维持在一个非满状态，也就是 维持一个低的端到端时延比高的吞吐量更加重要。然而，在流量突发性非常严重的 i n t e m e t 中，该建议并没有引起人们的足够重视。在i n t e m e t 中，即使t c p 限制了流量 窗口的大小，分组依然经常突发性的到达路由器。如果队列是满的或接近于满的状态， 大连理工大学硕士学位论文 那么突发数据流就会导致多个分组的丢弃。于是由于数据流同时降低发送数率导致了全 局同步，从而会持续一段时间的较低的链路利用率，导致整个网络吞吐率的下降。 在当前的i n t e m e t ，丢包是对端节点拥塞指示中的一个关键的机制。满队列的解决 方案是，路由器在队列满之前开始丢弃分组，从而端节点可以在缓存溢出之前对拥塞做 出反应。我们称这种主动的方法为主动队列管理算法( a q m ) 。通过在缓存溢出之前丢弃 分组，主动队列允许路由器决定何时丢包以及丢包的数量。 主动队列管理技术在拥塞产生以前，就根据链路的拥塞信息随机丢弃或标记进入路 由器的数据包，从而避免了网络拥塞。除此之外，主动队列管理还可以避免全局同步的 产生：避免对突发信息量的偏见；减小路由器中的平均队列长度；降低分组丢失率并可 提供低延迟的交互式服务。 1 2 1 主动队列管理算法的研究现状 a q m 技术的本质是对拥塞进行早期的检测并向端系统发出拥塞指示，端系统通过 相应的机制在路由器缓冲区队列溢出和丢包产生之前降低数据的发送数度，从而达到降 低丢包率和提高链路利用率的目的。下面介绍几种a q m 策略算法： ( 1 ) 弃尾算法 路由器传统的队列管理策略是队尾丢弃，即设置一个大容量的缓冲区，将所有新到 达的又来不及处理的数据包都保存在缓冲区内，当系统空闲时再来处理这些保存起来的 数据包。该算法最大的优点就是简单，直观，易于实现。但算法无法保证t c p 流的公 平性，同时存在的“全局同步 现象使得物理线路的利用率很低，网络吞吐率很小。此 外，缓冲区大小受限，不能无限制的增大。 ( 2 ) 随机早期检测算法 r e d 是最著名的a q m 算法，执行r e d 的路由器在缓存占满之前就按一定的概率 丢弃、标记进入路由器的数据包，丢包或标记的概率由动态变化的平均队列长度所决定， 如果缓冲区最近一段时间空闲，则不进行丢包或标记；当缓冲区相对较满时，表明出现 了拥塞，新到达的包有可能被丢弃或标记。 r e d 算法包括两部分：平均队列长度的计算和对新到达包的丢弃或标记。 ( 1 ) 平均队列长度的计算 a v g l e n - ( 1 - w e i g h t ) 宰a v g l e n + w e i g h t q 式中：a v g l e n 为平均队列长度，o w e i g b k l ，q 是采样测量时的队列长度。 ( 2 ) 丢包、标记策略 i 也d 对每个队列设置两个门限m i ( 最小阈值) ，m a x t l l ( 最大阈值) 及一个最大丢包、 标记概率p m 积。如果a v g l e n _ m i 姚，数据包入队列，包丢弃、标记的概率为0 ：如果 基于神经网络的a q m 算法研究 m i n m = m a x t l i ， 数据包全部被丢弃、标记。 丢弃、标记概率p 不仅是a v g l e n 的函数，也是上个数据包被丢弃后距当前的时间 的函数。计算公式如下： t e m p p - p m 瓢木( a - v g l e n m i n 恤) ( m a x t i l - m i n 曲 p = t e m p p ( 1 一c o u n t + t e m p p ) 式中：t e m p p 是p 的变量，计算器c o m l t 记录有多少刚到的数据包已经入队列( 未 被丢弃) 。随着c o u m 的增加，p 缓慢增加，包丢弃将随时间较均匀的分布，而不是倾 向于成簇的发生，这样就避免了对突发性流的不公平性，也避免了产生全局同步。r e d 算法比较简单、易于实现，有很好的防突发能力，其随机性可打破产生全局同步的条件， 避免l o c k o u t 现象，它较大的提高了链路的利用率，并保证了一定的公平性。另外， i 也d 算法使用的系统开销小，不会给路由器造成很大负担。但i 也d 对参数设置很敏感， 置参数通常要考虑实际环境中的包长、包到达率、突发性以及允许的时延等因素。而到 目前为止，这些参数还没有明确的设定方法。 ( 3 ) 灿迮d 算法 l 迮d 算法的拥塞指示没有考虑链路上复用的活动连接数对算法性能产生的影响。而 拥塞指示的发送数度是由最大丢包、标记概率p m 觚来实现的，为解决这个问题，文献【3 】 中提出了一种在线改变p m 觚参数的自适应i 也d 算法一灿迮d 。 6 岫d 算法基于r e d 算法，其主要思想是根据连接数目、流量的多少，在接受包 时更新平均队列长度，然后根据平均队列长度动态调整p m 瓢的大小。当平均队列长度在 m i 附近振荡时，说明早期拥塞指示过度，就降低p m 积；当平均队列长度在m a x m 附近 波动时，说明早期拥塞指示不够，就增大p m 戤。具体算法如下( q 、b 为常数) ： e v e r ya v g l e nu p d a ：t e i f ( m i a v g l e n m a x t l l ) s t a t l 】s = b e t 、m e e n ； i f ( a v g l e n f b e e z e l 蜘e ) t l l e n p m = p m + ol l 哪u p d a t e = n o w u p o n1 i i l l 【i d l ec v e m ： i f ( ( n o w l a s tu p d a t e ) 五陀e z e j i i n e ) t l ：i e n p m = p m o2 l 斛u p d a t e = n o w 其中，p m 为单一的丢包、标记概率。如果队列持续丢包和队列长度超过了设定值， b i u e 就增加p m ，这样就增加了发送拥塞标记的数率。在队列长度超过某设定值时增加 p m 可以为突发性流预留一定的空间，并且在队列长度较大时可以有效地控制队列延时。 缸e z e j i m e 参数决定连续两个p m 改变的最小时间间隔，n o w 表示当前时间，l 戤u p d a t e 表示p m 改变的最后时间。为了避免全局同步，缸e z e j i m e 的值是随机产生的。另外两 个参数。卜o2 分别表示队列溢出时p m 的增加步长和队列空闲时p m 的减少步长。 在b l u e 算法中设置参数时要遵循以下原则：骶e z 9 - t i m e 的值应在平均值r 盯附 近，这样在其它的变化出现之前就可以改变p m ：为了适应负载突然发生变化的情况， 在选择ol 和o2 的值时，要保证p m 值能在几秒左右覆盖整个o 1 或l o 区间。 b i u e 算法所需要的缓冲区比i 迮d 要小，这样就减少了端到端的延迟，增强了在 i i l t e m e t 上传输实时数据的能力，与参数配置合理的r e d 算法相比，它的性能有很大的 提高。但是，当i m 时间或者活动连接数目n 变化很大时就会使参数的配置无效，而 基于神经网络的a q m 算法研究 且还会导致在高丢失率和低带宽利用率之间来回振荡。同时，由于p m 的变化量由常数 ol 和o2 决定将会导致当活动连接数目发生大幅度变化时系统的不稳定。 ( 5 ) 基于频域的p ，p i ，p i d 的主动队列管理算法 基于频域的p ，p i ，p i d 的主动队列管理算法，使用不同的机制将队列的动态特性 同标记频率p 联系起来，就得到不同的p i d 策吲1 3 j 。 p 控制器由队列的瞬时长度决定标记队列，控制器只需要跟踪队列长度。p i 控制器 则需要同时跟踪当前和上一个采样值，这样会减少系统的相对稳定性，给p i 控制器加 上微分( d ) 控制可以提高系统的稳定性，减少反馈系统的超调量。d 控制意味着我们需 要跟踪队列长度的二阶微分或者是队列平均数据包到达率的一阶微分。a q m 管理的一 个目的就是在各种各样的网络条件下通过设置合适的参数使系统达到稳定。基于经典控 制理论频域主动队列管理控制器也有它的优点和不足。其中传统的p 控制器加快了系统 的响应时间，比i 也d 算法能够达到跟好的性能。c h o l l o t 等人提出的p i 控制算法，在 a q m 算法中加入积分环节，积分作用改善队列的稳态特性，从经典控制理论上说，针 对误差的存在问题，积分控制可以有效地消除误差。p i 控制器把队列长度控制在目标值 附近，克服连接数目和往返时间等扰动，从而使终端很容易控制分组在网络中的排队延 迟。p i 控制器虽然能够消除余差，但是调节时间过长，对路由器缓存大小的依赖也过强， 所以在p i 的基础上加入微分环节形成的p i d 控制器可以增加系统的响应能力，并能够 提高系统的稳定性，进一步提高系统性能，标准的p i d 在配置参数时，都使用静态配置 或在期望的网络条件下整定。这就体现了p i 和p i d 控制器的不足。其控制方法可用于 一般的网络结构，有完整的稳定性分析过程，不足是平衡点线性化方法没有考虑网络中 的非线性特性和未建模动态的不匹配性特征，因而对参数的较大变化不具有鲁棒性。关 于p i 具体内容将在以后的章节中详细介绍。 ( 6 ) 其他a q m 算法 g i b b e n s 和k e l l y 提出了虚拟队列i m l a lq u e u e ) 的概念，并将之应用到主动队列管 理算法中，便有了g k v q 策略【5 】。所谓虚拟队列是路由器维护的实际上并不存在的一种 逻辑队列，与其连接的虚拟链路容量小于实际容量，而缓存大小与实际队列相同。当有 分组进入实际队列时，更新虚拟队长以反映新分组的到达。如果虚拟队列溢出，则丢弃 或标记实际队列中的分组。从本质上讲，虚拟队列策略也属于早期分组丢弃技术的一种， 因为没有对队列长度的显式控制，很难在高吞吐量和低时延之间做出合理的平衡。 h o n g g a i l gz h a n g 【6 】等人提出的具有自校正结构的a q m 控制算法能够处理链路容量 等网络参数变化的情况，这类算法有s t r e d 、s t p i 等，它主要通过在线估计负载数、 时延和链路容量等参数，然后计算丢弃概率用以丢弃或标记分组。以前讨论的大多数算 大连理工大学硕士学位论文 法都是基于线性模型讨论的，它仅仅在平衡点附近有效，但是t c p 动态模型也是包括 非线性在内的，如u d p 非响应业务流h t t p 和t e l n e t 等短期业务。 p e n g y a i l 【7 j 等人提出的变结构控制器考虑了非线性和未建模动态的影响。它采用队 列长度和到达的业务流量来产生标记概率用以丢弃分组，试验表明变结构控制器响应数 度快，当业务负载有较大变化时，其稳定性和鲁棒性都比较强，它的不足之处是没有考 虑时延的影响。 1 2 2 主动队列管理算法的优势 主动队列管理算法是一种积极的管理资源机制【1 4 1 ，它对网络上可能出现的拥塞情况 进行预判，然后在情形恶化之前采取一定的机制来通知数据发送方，从而可能避免真正 拥塞的发生。较之于传统的队列管理或调度机制，主动队列管理算法具有一下的一些优 点。 ( 1 ) 减少路由器的丢包数量； 在分组网络中，分组的突发性是不可避免的。如果路由器的队列空间已经“忠于 稳定状态的数据流或者缓存空间不足，那么路由器就没有能力来缓存突发数据流。主动 队列管理通过维持一个小的平均队列长度，可以提供更大的能力来吸收自然出现的突发 数据流，而不用丢弃分组。 再则，如果没有主动队列管理，当队列确实溢出时，将会有更多的分组被丢弃。这 种情况是不期望出现的。原因有三：第一，队列共享和去尾会导致不必要的全局同步现 象，从而会降低链路利用率，导致整个网络吞吐量的下降。第二，相较于从单一分组丢 失恢复而言，t c p 从突发的大量分组丢失恢复会更加困难。第三，不必要的分组丢失意 味着从发送节点到丢失分组节点之间的带宽可能被浪费了。 ( 2 ) 提供低延迟的交互服务； 主动队列管理可以通过维持较小的平均队列长度来减少数据流可感知的延迟。这对 于一些交互的或实时的应用尤为重要，如短的w e b 数据流，t e l n e t 传输，或者交互的声 讯会议等等。这种类型的应用对丢包并不是非常敏感，个别的分组丢失不会造成应用的 很大的障碍，但是延迟对这类应用的影响将是巨大的。 ( 3 ) 避免l o c k o u t 行为 主动队列管理几乎可以保证随时为新来的分组提供缓存空间，从而能够避免 l o c k o u t 行为的发生。同样的，主动队列管理可以阻止路由器对低带宽高突发性的数据 流形成偏见。 l o c k o u t 行为在一组数据流中形成一个总量的不公平，因而应该避免其发生。然而， 实际上我们很想表明这种行为是有助于“增加公平”的，因为数据流之间的全局公平性 基于神经网络的a q m 算法研究 需要单一数据流的状态，而队列管理是无法提供这个状态的。例如，在一个只提供f i f o 调度的队列管理的路由器中，两个数据流会仅仅因为具有不同的回路响应时间而导致获 得的带宽差别很大，而且一个不遵守拥塞控制机制的数据流会比使用拥塞控制的数据流 获得更多的带宽。要获得全局公平性的单一数据流状态应该由单一数据流调度算法来维 护，比如公平排队算法( f a i rq u e u i n g ，f q ) 或者基于分类的调度机制如c b r 等。 另一方面，甚至使用单一数据流调度算法如f q 或基于分类的调度机制如c b r 的路 由器同样需要主动队列管理算法。那是因为单一数据流调度算法本身对控制整个队列长 度或单一队列长度都是无能为力的。控制整个队列长度需要用到主动队列管理，从而当 出现突发数据流的时候可以得到有效缓存而避免丢包。另外，主动队列管理也应该被用 来管理各个单一数据流或各个分类的队列长度，从而可以避免不必要的高延迟。 1 2 3 主动队列管理算法的性能评价 拥塞控制算法的评价标准有很多，就源算法和链路算法而言，其评价的侧重点又不 尽相同。而且由于各种拥塞算法作用于网络的不同部分，因此算法对网络拥塞所作出的 贡献就会有很多种不同的表现方式。影响主动队列管理算法的指标，也就是评价主动队 列管理算法的性能可以通过以下几个方面进行。 ( 1 ) 算法的稳定性 a q m 算法的目的是控制路由器中的队列长度，因此算法稳定与否直接关系到路由 器中队列长度的变化情况，而队列长度的变化又直接影响到网络的服务质量。一方面， 对于一个特定的t c p 连接，由于其传播延迟是固定的，因此该连接传输时延和时延抖 动的大小主要是由路由器中的队列长度所决定的；另一方面，路由器中的队列长度直接 关系到其输出链路的资源利用率，只有当队列长度不为零时才能保证网络资源的有 效利用。因此一个好的a q m 算法应能使队列长度稳定在一个较低的值。 同时，算法的稳定程度还表现在吞吐量方面。一个好的拥塞控制算法在网络动态变 化的过程中，虽然数据发送方和数据接收方的变化很大，但注入网络的流量总量相对稳 定的情况下，应该能够提供一个平滑的吞吐量曲线。而且，更重要的是，应该保证整个 网络的有效吞吐量不会出现剧烈动荡。 ( 2 ) 算法的复杂程度 算法的复杂程度是决定a q m 算法是否实用的一个关键因素。近年来，随着网络带 宽的迅速增加，路由器的处理数度成为影响网络性能的一个主要因素，因此应尽可能降 低a q m 算法的复杂程度以减小路由器的计算量。由于骨干路由器的负荷相当重，瓶颈 链路非常繁忙，因此一个简单高效的拥塞检测方法以及标记策略对于算法的利用及有效 推广是至关重要的。 大连理工大学硕士学位论文 ( 3 ) 对网络状态变化的适应能力 i n t e m 就的复杂性和异构性决定了网络状态的变化是难以避免的，因此一个好的 a q m 算法应该对网络状态的变化具有很好的适应能力，在网络负载，传输延迟等因素 发生变化时，仍可实现较好的传输性能 1 3 本文的研究工作 在查阅了国内外大量的相关文献的基础上，我们认