（计算机应用技术专业论文）基于主动队列管理的路由器拥塞控制技术的研究.pdf

华北电力大学硕士学位论文 摘要 本文的目标是要提出一个新的基于路由器的主动队列管理算法，在网络爆 发网络蠕虫或者分布式拒绝服务攻击等大规模网络恶意数据流时，能够提高网 络关键设备在数据包处理方面的公平性，从而合理的分配网络带宽资源，限制 资源滥用，提高网络自身对恶意数据流的遏制作用，确保网络在大规模攻击下 的健壮性和鲁棒性。 本文首先研究了对路由器造成冲击的恶意数据流的特点和本质；接下来对目 前主要的主动队列管理机制和i p 拥塞控制算法的性能进行了研究：最后在上述 基础上，提出了一个新的基于路由器的主动队列管理算法c c u 。 实验证明，c c u 算法能够精确的检测出恶意数据流，并能够显著的抑制恶 意数据流对路由器造成的攻击；相比其他主动队列管理算法能够有效提高路由 器在大规模网络攻击下的鲁棒性和健壮性。 关键词：主动队列管理，拥塞控制，恶意数据流 a b s t r a c t t h i sa r t i c l ea i m e dt op r o p o s ean e wa c t i v eq u e u em a n a g e m e n tr a q m ) a l g o r i t h m w h i c hc a ne n h a n c et h ef a i r n e s si np a c k e t sp r o c e s s i n ga m o n gh e t e r o g e n e o u sf l o w sf o r k e ye q u i p m e n t sw h e nt h ew o r m so rd d o sb u r s to u ti nl s na s w e l la si n s u r et h e n e t w o r kr o b u s t n e s sa n ds t r o n g n e s sb yl i m i t i n gt h en e t w o r kr e s o u r c em i s u s ea n d i m p r o v i n gt h ef u n c t i o no fr e s t r a i n i n gm i s b e l i e v i n gf l o w s f i r s t l y ，t h i sa r t i c l er e s e a r c h e da n da n a l y z e dt h er o u t e r sp e r f o r m a n c ei nb a c k b o n e n e t w o r ku n d e rh i g hb a n d w i d t ha r a c k s e c o n d l y ，t h es c h e m ea n dp e r f o r m a n c eo fc u r r e n t c l a s s i ca q m a l g o r i t h m sa n di pc o n g e s t i o nc o n t r o la l g o r i t h m sw e r er e s e a r c h e d ；a tl a s t ，a n e wa q m a l g o r i t h mw a sp r o p o s e db a s e do nr e s e a r c ha b o v e i th a sb e e np r o v e dt h a tc c uc a nd e t e c tp r e c i s e l ym i s b e l i e v i n gf l o w sa n dr e s t r a i nt h e p a s s i v ei n f l u e n c ei m p o s e do nr o u t e ra n di m p r o v et h er o b u s t n e s so fr o u t e ru n d e rh i g h b a n d w i d t ha t t a c k sc o m p a r e dw i t ho t h e ra q ma l g o r i t h m s z h a ol iy u a n ( c o m p u t e rs c i e n c e ) d i r e c t e db yp r o f l i uk eq i 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 g e s t i o nc o n t r o l ，m i s b e l i e v i n gf l o w 华北电力大学硕士学位论文 摘要 本文的目标是要提出一个新的基于路由器的主动队列管理算法，在网络爆 发网络蠕虫或者分布式拒绝服务攻击等大规模网络恶意数据流时，能够提高网 络关键设备在数据包处理方面的公平性，从而合理的分配网络带宽资源，限制 资源滥用，提高网络自身对恶意数据流的遏制作用，确保网络在大规模攻击下 的健壮性和鲁棒性。 本文首先研究了对路由器造成冲击的恶意数据流的特点和本质；接下来对目 前主要的主动队列管理机制和i p 拥塞控制算法的性能进行了研究：最后在上述 基础上，提出了一个新的基于路由器的主动队列管理算法c c u 。 实验证明，c c u 算法能够精确的检测出恶意数据流，并能够显著的抑制恶 意数据流对路由器造成的攻击；相比其他主动队列管理算法能够有效提高路由 器在大规模网络攻击下的鲁棒性和健壮性。 关键词：主动队列管理，拥塞控制，恶意数据流 a b s t r a c t t h i sa r t i c l ea i m e dt op r o p o s ean e wa c t i v eq u e u em a n a g e m e n tr a q m ) a l g o r i t h m w h i c hc a ne n h a n c et h ef a i r n e s si np a c k e t sp r o c e s s i n ga m o n gh e t e r o g e n e o u sf l o w sf o r k e ye q u i p m e n t sw h e nt h ew o r m so rd d o sb u r s to u ti nl s na sw e l la si n s u r et h e n e t w o r kr o b u s t n e s sa n ds t r o n g n e s sb yl i m i t i n gt h en e t w o r kr e s o u r c em i s u s ea n d i m p r o v i n gt h ef u n c t i o no fr e s t r a i n i n gm i s b e l i e v i n gf l o w s f i r s t l y ，t h i sa r t i c l er e s e a r c h e da n da n a l y z e dt h er o u t e r sp e r f o r m a n c ei nb a c k b o n e n e t w o r ku n d e rh i g hb a n d w i d t ha r a c k s e c o n d l y ，t h es c h e m ea n dp e r f o r m a n c eo fc u r r e n t c l a s s i ca q m a l g o r i t h m sa n d i pc o n g e s t i o nc o n t r o la l g o r i t h m sw e r er e s e a r c h e d ；a tl a s t ，a n e wa q m a l g o r i t h mw a sp r o p o s e db a s e do nr e s e a r c ha b o v e i th a sb e e np r o v e dt h a tc c uc a nd e t e c tp r e c i s e l ym i s b e l i e v i n gf l o w sa n dr e s t r a i nt h e p a s s i v ei n f l u e n c ei m p o s e do nr o u t e ra n di m p r o v et h er o b u s t n e s so fr o u t e ru n d e rh i g h b a n d w i d t ha t t a c k sc o m p a r e dw i t ho t h e ra q ma l g o r i t h m s z h a ol iy u a n ( c o m p u t e rs c i e n c e ) d i r e c t e db yp r o f l i uk eq i 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 g e s t i o nc o n t r o l ，m i s b e l i e v i n gf l o w 声明 本人郑重声明：此处所提交的硕士学位论文基于主动队列管理的路由器拥塞控制 技术的研究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工 作和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示了谢意。 学位论文作者签名：l 毫社日 期：塑二羔 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件：学校可以采用影印、缩印或其它复制手 段复制并保存学位论文：学校可允许学位论文被查阅或借阅：学校可以学术交流为 ， 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播学 位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：墨釜翠盘 日期：艘尘上 导师签名：型杰蒸 华北屯力大学硕士学位论文 1 1 研究背景 第一章引言 从1 9 6 9 年美国国防部远景规划局提出a r p a n e t 到今天的下一代互联网计划，几 十年来网络技术得到了突飞猛进的发展。特别是近十年来伴随着以t c p i p ( t r a n s f e r c o n t r o lp r o t o c o l i n t e r n e tp r o t o c 0 1 ) 协议为基础的i n t e r n e t 的发展，网络已经彻底改变 了人们的生活方式，包括从简单的电子邮件服务、在线视频服务到复杂的电子商务、 远程教育和远程医疗。i n t e r n e t 的设计当初充分考虑了其开放性，互连性和共享性等 特点，但是网络的安全性、健壮性、鲁棒性却没有被充分的考虑和认识到，随着 i n t e r n e t 自身的发展，这些问题越来越成为人们关注的焦点。 近年来，人们更为关注的是当网络中爆发大规模的蠕虫病毒和分布式拒绝服务 攻击( d d o s ，d i s t r i b u t e dd e n i a lo fs e r v i c e ) 时，整个网络所表现出的脆弱性。1 9 9 8 年1 1 月2 日爆发的莫里斯蠕虫病毒，在短短几个小时内，就使得上前台计算机陷入 瘫痪。而1 9 9 8 年d d o s 的第一次爆发，就向人们显示了分布式拒绝服务攻击的巨大 危害性和对网络造成的巨大灾难。这种攻击通过大量的分布式的协同数据源向目标 主机发送大量的无用数据流量，恶意的占用带宽和系统资源，以达到通过流量淹没 服务器的目的。2 0 0 0 年2 月这种d d o s 攻击达到了高潮，著名的互联网内容提供商 如y a h o o ! 、c n n c o r n 和a m a z o n c o m 都遭到了d d o s 攻击，瘫痪从几小时到数天。 2 0 0 1 年9 月爆发的n i m d a 蠕虫病毒的凶猛性和破坏性更是前所未有，它通过多种模 式复制传播，轻而易举的穿透防火墙，把蠕虫攻击技术推向了巅峰，n i m d a 蠕虫病 毒一直在i n t e r n e t 上泛滥了几个月才开始被遏制衰减，造成了巨大的财产损失。 尽管目前从个人主机到大型系统、网站等都采用了防火墙等基于端系统的安全 技术，但是在面对来势凶猛的网络攻击时却显得不堪一击。这无疑与网络最初的设 计原则有关。i n t e r n e t 的最初设计原则是：对于网络数据流的管理，对于与流有关的 状态的维护和处理，都应该在端系统上实现。但事实上，这一原则依赖两个基本的 假设； 1 网络中所有的( 或者几乎所有的) 流都采用了拥塞控制机制； 2 这些流采用的机制都是同质的，或者大体上相同，即在相似的环境下可以 根据某一条件，如丢包率、r t t ( r o u n dt r i pt i m e ，往返时间) 、m t u ( m a x i m a l t r a n s f e ru n i t ，最大传输单元) 等按比例占用带宽，但不会占用比t c p 流更 多的带宽。 但随着近十年来计算机网络的爆炸式增长，上述假设由于以下几点原因不再成 华北电力大学硕士学位论文 立3 | - 1 以多媒体应用和组播应用为代表的业务流没有采用拥塞控制机制，因而不 能对拥塞做出反应； 2 即使有些应用使用了拥塞控制算法，但并不是t c p 友好的( t c p f r i e n d l y ) ， 比如接收端驱动分层组播r l m ( r e e e i v e r - d r i v e nl a y e r e dm u l t i c a s t ) 采用的就 是这种算法。 3 一些用户由于有意或无意的原因，使用了非t c p 的拥塞控制算法。比如修 改t c p 。使得窗口的初始值很大并且保持不变，即所谓的“快速t c p ”。 4 另外，我们知道，i n t e r n e t 上的流量是由无数条异质的数据流混合而成的。 从有无有效拥塞控制机制的角度可以将这些异质的流分为以下三类【4 1 ： t c p 友好流( t c p f r i e n d l y l ； 无反应( u n r e s p o n s i v e ) 流：这种流是由于上述原因( 1 ) 造成的； 响应( r e s p o n s i v e ) 流但非t c p 友好流，这种流是由于上述原因( 2 ) 和( 3 ) 引起 的。 由此，我们可以看到，随着i n t e r n e t 的快速发展，这两点假设均不再成立。 事实上，在爆发大规模的蠕虫病毒或者d d o s 攻击时，那些以恒定的高速率发 送数据包的恶意数据流不但没有采用拥塞控制机制，而且在网络发生拥塞时，由于 t c p 流启动拥塞避免机制后自身的“回退”，导致这些恶意数据流占用了更多的网 络资源，结果使得网络中正常业务被“拒绝服务”。 即使在网络的负载正常情况下，那些基于u d p ( u s e r d a t a g r a m p r o t o c o l ，数据用 户报协议) 的应用的语音和视频服务，也有可能会导致网络拥塞，以致当这些无反应 流的业务量超过网络负载上限之后，就有可能导致网络崩溃【5 1 。当网络发生轻度拥 塞时，这些应用发出的业务流在接收到拥塞通知时，并没有按照希望的那样适当降 低发送数据包的速度。结果，相比那些对拥塞通知具有适应性的t c p 流，这些对于 拥塞通知没有反应的流，很快就对有限的带宽资源侵占得越来越多，远远超过了其 应该获得公平分配。这同样可能会最终导致网络崩溃( i n t e r n e t m e l t d o w n ) ，造成网络 拒绝服务1 6 1 。 因此，在如何有效抑制恶意数据流对于网络造成的攻击的问题上，尽管基于端 节点的t c p 拥塞控制机制是必须的，但我们仍然需要从宏观上采取有效的遏制办 法，对基于端节点的拥塞控制机制进行有效的补充。 当我们从宏观的角度研究i n t e r n e t 各个构件的功能时，可以发现，由于网络中 间节点有可能更及时，甚至能够提前了解网络的拥塞状态，并依此实施有效的资源 管理策略，可以使网络能有效地避免拥塞，或尽早从严重的拥塞状态中恢复过来 7 ： 另一方面，基于路由器的拥塞控制技术把网络拥塞作为高带宽恶意数据流爆发的一 种指示或者现象；通过拥塞的发生，启动恶意数据流的检测确认机制以及采取相应 2 华北电力大学硕士学位论文 恶意数据流的惩罚控制措施：同时，中间节点更是把d d o s 恶意数据流的控制直接 看作一种拥塞控制的问题f 8 】。由于i n t e r n e t 数据本身具有多时间尺度突发 ( m u l t i r e s o l u t i o nb u r s t y ) 的本质( 例如d d o s 或者蠕虫的宏观大规模爆发就是一种宏观 时间尺度上的突发或者也可以叫做异常) 1 9 l ，路由器队列的重要作用就是吸收突发的 数据包，因此基于路由器的拥塞控制技术的第三个目的就是要在维持较小的队列长 度、降低排队延迟、提高吞吐量的同时，还能保持较大的队列空间来吸收突发数据 包，即就是要维持网络处于低延迟高吞吐量的状态【l 。因此，研究基于中间节点， 即路由器的拥塞控制、检测并防范恶意数据流的技术，对于提高 n t e r n e t 的宏观免 疫能力、防止大规模网络蠕虫，d d o s 病毒爆发显得十分必要。 基于路由器的拥塞控制技术包括：队列调度( q u e u es c h e d u l i n g ) 算法和队列管理 ( q u e u em a n a g e m e n 0 算法。其中，队列管理算法又包括：被动队列管理f p q m ，p a s s i v e q u e u em a n a g e m e n t ) 和主动队列管理( a q m ，a c t i v eq u e u em a n a g e m e n t ) 。 p q m 只有在拥塞发生时，才会对后来到达路由器的数据包不分区别的加以丢 弃，但是会导致：死锁( 1 0 c ko u t ) 问题、满队歹r j ( f u l lq u e u e ) 问题和t c p 全局同步( g l o b a l s y n c h r o n i z a t i o n ) 问题j 。而a q m 能够在拥塞发生之前，就能感知链路的使用状况， 在接近拥塞边界时，会给发送源端系统发送拥塞通知，这样就会尽量提前避免路由 器被动的陷入拥塞状态。 近年来，基于路由器的拥塞控制技术，尤其是基于a q m 的路由器拥塞控制技 术，已经成为网络研究越来越活跃的领域。该技术从上世纪9 0 年代中期被提出， 到目前已经成为i n t e r n e t 鲁棒性的重要保护机制，也成为了i n t e r n e t 鲁棒性研究的重 点。尽管研究者们提出了许多的a q m 算法，但是在实际中获得应用的算法仍然很 少，这主要是由于算法自身的局限性和网络实际环境的瞬息变化，使得算法不能在 各种情况下，保持较低的丢包率和对恶意数据流进行有效的监测和防范。因此，研 究有效的基于路由器的a q m 拥塞控制技术对于加强路由器在大规模网络攻击下的 鲁棒性和强壮性显得非常迫切。 1 2 国内外研究现状 d r o p t a i l 是最早的队列管理算法，但是是一种p q m 。d r o p t a i l 和f i f o ( f i r s ti n f i r s t o u t ) 队列的f c f s ( f i r s t c o m e f i r s ts e r v i c e ) 结合成为目前路由器的主要管理调度 策略【l ”。当队列充满也就是达到可容纳数据包的最大值时，d r o p t a i l 不分区别的丢 弃此刻以后来到的任意数据包，也就是“结尾丢弃”。d r o p t a i l 存在三个显著的缺 点：死锁问题，即仅允许几个流独占缓存队列，阻止其他流的包进入队列；满队列 问题，即只有在队列满时才会发出拥塞信号，因此会使得队列在相当长时间内处于 华北电力大学硕士学位论文 充满( 或几乎充满) 的状态；t c p 全局同步问题，即由于i n t e r n e t 上数据的突发本质， 到达路由器的包也往往是突发的。如果队列是满的或者几乎是满的，就会导致在短 时间内连续大量地丢包。而t c p 流具有自适应特性，源端发现包丢失就急剧地减小 发送窗口，包到达速率就迅速下降，于是网络拥塞得以解除，但源端得知网络不再 拥塞后又开始增加发送速度，最终又造成网络拥塞，而且这种现象常常会周而复始 地进行下去，从而在一段时间内网络处于链路利用率很低的用状态，降低了整体吞 吐量，这就是所谓的“t c p 全局同步”现象【l “。 针对如何解决“死锁问题”、“满队列问题”和“t c p 全局同步问题”，b r a d e n 等人于1 9 9 8 年在i e t f ( i n t e r n e te n g i n e e r i n gt a s kf o r c e ，i n t e r n e t 工程任务组) 上提出 了主动队列管理的研究动议：采用主动的而非响应性的分组丢弃对路由器中的数据 包进行管理，相应的队列管理策略被称为“主动队列管理”( a q m ) 。a q m 与e c n 结合，通告拥塞的信号不再是唯一的分组丢弃，而是采用分组标记来通知源节点减 速：a q m 的主要技术目标就是在减少排队时延的同时保证有较高的吞吐量。a q m 要解决的问题包括以下四个方面： 1 早期探测路由器可能发生的拥塞，并通过随机丢弃或者标记分组来通知源 端采取措施，以避免可能发生的拥塞； 2 公平处理包括突发性、持久性和间隙性的各种t c p 业务流； 3 避免多个t c p 连接由于队列溢出而造成t c p 同步，进入“慢启动”状态： 4 维持较小的队列长度，在高吞吐量和低时延之间做出合理的平衡。 尽管a q m 研究动议是在1 9 9 8 年被提出的，但是与此相关的r e d ( r a n d o m e a r l y d e t e c t i o n ，随机早期检测) 算法的研究却是由来已久了。早在1 9 9 3 年，f l o y d 和 j a c o b s o n 就提出了r e d j 。当时的主要目的是克服“早期随机丢弃”( e a r l yr a n d o m d r o p ，e r d ) 网关偏袒突发业务而造成的不公平问题。由于在提出a q m 的研究时， r e d 是唯一一个能够实现该技术目标的算法，所以r f c 2 3 0 9 t 1 4 1 将其推荐为a q m 的 唯一候选算法。随后，围绕a q m 和r e d 的研究逐渐丰富起来。 r e d 通过以一定概率丢弃到达的数据包或者标记数据包的方式，通知源端网络 的拥塞状况。r e d 采用指数加权移动平均数( e w m a ，e x p o n e n t i a l l yw e i g h t e dm o v i n g a v e r a g e ) 的方法，计算平均队列长度a v g q ，并以a v g q 度量网络的拥塞程度，然后以 线性方式将拥塞信息反馈给源端；r e d 使用最小队列长度阈值( m i n t h ) 、最大队列 长度阈值( m a x t h ) ( 铂最大丢包概率( m a x 。) 等几个参数计算丢包概率。尽管r e d 算法 是d r o p t a i l 的改进，但是仍然存在许多问题，包括： 1 r e d 对参数配置很敏感，参数的改变对于算法的性能有明显的影响，到目 前为止，这些参数的配置还没有明确的设定方法； 2 随着网络中“流”( f l o w ，一对连接) 数目的增加，路由器的平均队列长度会 逐渐增加； 4 华北电力大学硕士学位论文 3 。在网络中包含多种异质流时，尤其包含以无反应流为代表的高带宽恶意数 据流时，r e d 难以保护t c p 流和t c p 友好流，主要表现之一就是非t c p 友好的数据包很容易独享队列，造成t c p 友好流的数据包大幅丢弃。 针对第二个问题，很多研究者提出了解决方案，包括a r e d ( a d a p t i v e r e d ) ”“、 s r e d ( s t a b i l i z e d r e d ) t 哺】、f r e d ( f l o w r e d ) 17 】和b l u e t 埽】等。它们的主要思路就是根 据网络中负载的情况对标记丢弃数据包的概率进行动态调整。a r e d 的主要思想是 根据网络负载的情况调整m a x 。，当平均队列长度a v e , q 小于m a x t h 时，就减小m a x 。； 当平均队列长度a v g q 大小于m a x t h 时，就增加m i l k ；s r e d 的主要思想是通过估计 网络中流的个数来调整数据包标记丢弃概率。在s r e d 中，流的个数通过概率统计 的方法获得。相比a r e d 和s r e d ，f r e d 则通过对每个活跃流( p e r a c t i v e f l o w ) 进 行记账，并维持“单流信息”( p e r f l o w i n f o r m a t i o n ) 来对使用不同带宽的流做出不同 的标记包的决策，从而提高不同的流使用带宽的公平性。b l u e 的主要思想是通过链 路空闲和队列缓存溢出的情况来调整数据包标记，丢弃的概率，如果缓存溢出，就增 大丢包概率；如果缓存空闲，就减少丢包概率。 针对第三个问题，a o m 研究者们提出了以下三个比较全面的抑制不良行为数 据流的方法。 r p a n 等提出一种基于r e d 的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 l lf o ru n r e s p o n s i v ef l o w s ) 1 9 】算法来惩罚行为不端的数据流( 主要是针 对无反应流) 并保护适应流。其基本思想是：当一个包到达拥塞的路由器时，c h o k e 从f i f o 队列中随机选择一个数据包进行比较。如果它们属于同一个流，则这两个 包都被丢弃；否则，留下被抽样数据包，而刚到达的包则依r e d 算法处理。r a t u l m a h a j a n 和s a l l yf l o y d 等人提出了r e d p d ( r e dw i t hp r e f e r e n t i a ld r o p p i n g ) 口w 算法， 根据r e d 丢包历史判断无反应流的高带宽数据流，并通过增加丢包率进行带宽控制 来惩罚这些行为不端的数据流。作为b l u e 的改进算法，s f b ( s t o c h a s t i cf a i r b l u e ) 口” 的基本思想就是采用记账的方法鉴别无反应流并对它们进行速度限制。s f b 把内存 分为l 层，每层n 个柜子( b i n s ) ：同时维持l 个独立的h a s h 函数，每个h a s h 函数 都对应于某一层b i n s 。所有来自于某一个源端的数据流都要通过这个h a s h 函数被映 射到每一层的某一个b i n 上，每个b i n 也要维持一个丢包概率只，该只- 随着b i n 中 数据包的多少面变化；当某一个流映射到l 个b i n s 中最小的只超过了一定的阈值， 则可认为该流属于无反应流，从而对其限速。 国内在a q m 的研究上，主要从控制系统的角度对a q m 的目标和策略进行分 析。针对网络状态参数的时变性，国内研究者把鲁邦控制理论中控制器的设计和分 析方法应用于a q m 策略中，并借助于滑模变结构控制器的设计方法，提出了性能 较好的s m v s 算法 2 引，并正努力从智能决策技术的角度，研究新的a q m 机制。 华北电力大学硕士学位论文 1 3 本文的主要研究内容 本文首先研究了对路由器造成冲击的恶意数据流的特点和本质；并对目前主要 的主动队列管理机制和i p 拥塞控制算法的性能进行了研究；最后在上述基础上，提 出了一个新的基于路由器的主动队列管理算法c c u ( c o m p a r ea n dc o n t r o l u n r e s p o n s i v ef l o w s ) 。 1 3 1 研究对路由器造成冲击的恶意数据流的特点和本质 首先我们将对恶意数据 b 枉( m i s b e h a v i n gf l o w s ) 的本质和特点进行深入研究和分 析：非t c p 友好性( n o nt c p f r i e n d l yf l o w s ) ，非响应性( u n r e s p o n s i v ef l o w s ) 燃 带宽占用性( d i s p r o p o n i o n a t e b a n d w i d t hf l o w s ) ，并研究了恶意流对于网络造成的影 响：网络拥塞崩溃和对于t c p 流t c p 友好流造成的“带宽饥饿”。 1 3 2 通过仿真，研究基于路由器的a o m 算法性能 对于基于路由器的a q m 算法性能，我们主要考察以下几个方面： 岔乎拦：这里所说的公平性实际上就是路由器在网络发生大规模攻击时，应该 具有的健壮性，即能够有效抑制恶意数据流，保护正常t c p 流和t c p 友好流。在 a q m 算法中，对于公平性的考虑主要包括：抑制恶意数据流对路由器的入侵，控 制恶意数据流对网络有限带宽资源的占用；在保证t c p 流占用公平带宽的同时，确 保t c p 流内部的分配公平。 算偿对于量磁膨暂感携：基于a q m 的路由器拥塞控制机制的许多算法，为了 保证对于缓存队列较少的占用、确定拥塞程度、判断恶意数据流和正常流等，都配 置了一些参数。但是，这些参数必定带有局限性。例如r e d 算法的性能就敏感于设 计参数和网络状况，在特定的网络负载情况下依然会导致多个t c p 的同步，造成队 列震荡，吞吐量降低和时延抖动加剧。因此对于算法参数的敏感性也是我们衡量标 准之一。 脂否架痔寝掰膨缓存占劈和易于胃日孽：由于路由器队列的重要作用就是吸收突 发的数据包，因此队列的管理的目标除了要维持较小的队列长度，降低排队延迟， 提高吞吐量外，还要能保持较大的队列空间来吸收突发数据包。例如，b l u e 算法就 能在使用较少的缓冲区的同时，完成拥塞控制。这样就可以减少端到端的延迟，提 高t c p 流的吞吐量。另外，较小的缓冲区需求也会使得路由器有更多的自由空间来 执行其他的路由器功能，如存储更大的路由表，从而提高路由器的性能等等。算法 6 华北电力大学硕士学位论文 是否易于配置，也是衡量算法的一个方面，尽管s f b 能够很好的区分有反应流和无 反应流，但是由于过于复杂，也会大大增加路由器的开销。 1 3 3 提出新的基于a q m 的路由器拥塞控制机制算法 我们的最终目标是要在研究现有的基于路由器的a q m 拥塞控制算法的各种性 能的基础上，提出新的a q m 算法。新算法将以确保公平性、增加路由器在网络攻 击下的健壮性和带宽分配的公平性为主要实现的目标，并在保证上述性能的同时， 尽量保持较低的队列占用，减少端到端的延迟，提高路由器性能。 华北电力大学硕士学位论文 第二章恶意数据流特点的分析与研究 本章，我们将对恶意数据流( m i s b e h a v i n gf l o w s ) 的本质和特点进行深入研究和 分析，首先介绍什么是恶意数据流，以及恶意数据流的三个主要特点，接下来研究 恶意数据流对网络造成的影响，包括：异质流之间的带宽分配不公平和网络拥塞崩 溃。 2 1 恶意数据流的特点 恶意数据流具有三个主要特点：非t c p 友好性，非响应性和高带宽占用性”i 。 2 1 1 非t o p 友好性 对于网络中遵循t c p 拥塞控制机制的流，统称为t c p 友好流( t c p f r i e n d l y f l o w s ) ；反之，对于网络拥塞没有采取相应的拥塞控制机制，则称其为非t c p 友好 流( n o nt c p f r i e n d l yf l o w s ) 2 4 】【2 5 1 ，恶意数据流的第一个本质特征就是非t c p 友好性。 对于t c p 友好流的定义：如果一个流是t c p 友好流，那么该流到达路由器的 速度一定不会超过在相同环境下t c p 流到达路由器的速度【5 1 。具体来说，当网络发 生拥塞时，t c p 流至少会降低拥塞窗口的一半作为拥塞响应；拥塞停止后，则以某 一恒定速率增加拥塞窗口，但增加的速率最多是每个i 玎t 一个数据包，通常如果一 流具备这一特征，则被认为是t c p 流。根据t c p 流的这一特征，可以判断：t c p 流在一定的丢包速率、数据包大小和r t t 下，必然有一个最大平均发送速率。假定 丢包速率为p ，平均发送速度为tb y t e s s ，则 ，1 5 4 2 3 b ( 2 1 ) 八万一 、。 其中b 是数据包大小( b y t e ) ，r 为含有队列延迟的r t t ( s ) 。 根据上述论断，如果某一流为t c p 友好流，则其到达路由器的速度不会超过t ； 反之，如果在相同环境下，某一流到达路由器的速度超过t ，则我们可认为该流属 于非t c p 友好流，恶意数据流就是有着这个明显的特征，在通常情况下，其到达路 由器的速度t 都远远超过t c p 流的到达路由器的速率，即 ， ! ：型! ! 蝥里 ( 2 - 2 ) r 4 p 华北电力大学硕士学位论文 2 1 2 非响应性 一般来说，遵循t c p 拥塞控制的流都是适应流( r e s p o n s i v ef l o w s ) ，即当其丢包 速率不断增加时，其到达路由器的速度也会不断降低。以t c p 流为例，根据公式 ( 2 1 ) ，某一流如果在很长一段时间内的丢包速率以因子x 不断增加，那么其到达路 由器的速率应该以x 下降【5 l 。例如：如果某一流的丢包率在很长一段时间内以因子 4 不断增长，那么其到达速率应该以因子2 来减少。 而恶意数据流通常对数据包的丢弃没有任何反应，即尽管该流的数据包丢弃速 率不断增加，其到达路由器的速率仍然保持相对稳定，甚至或者不断增加。 2 1 3 高带宽占用性 一方面，由于恶意数据流既没有慢启动机制，也没有采用拥塞控制机制，其到 达路由器的速率远远大于t c p 流或者t c p 友好流的到达速率：另一方面，即使发 生了数据包丢失，也不会降低其发送数据包的速率，这两方面原因导致了恶意数据 流在网络中占用的带宽普遍高于其他流的带宽。 2 2 恶意数据流对于网络的影响 恶意数据流的存在会导致带宽分配不公平和网络拥塞崩溃等问题1 2 ”。带宽分配 不公平指的是：由于恶意数据流不能在网络拥塞时降低自身的发包速度，大量占用 网络有限带宽资源，远远超出了公平带宽，结果导致正常流无法获得应有带宽，而 陷入了“带宽饥饿”；网络拥塞崩溃则一般是由于恶意数据流持续的以高速率发送 大量数据包，处于负荷严重超载的网络忙于传送这些数据包，但是这些数据包却在 到达最终目的地之前就被丢弃了，结果造成了网络有限带宽资源的浪费【2 ”。 2 2 1 带宽分配不公平 缺乏端到端的拥塞控制机制所导致的第一个问题，就是不公平性【27 1 ，其具体表 现就是当正常流与恶意流共同竞争有限带宽资源时，由于恶意流缺乏拥塞控制机 制，占用的带宽远远超过公平带宽，以t c p 流为代表的正常流没有获得应有的带宽 分配，结果正常流的丢包速率不断增加，面对数据包丢失时，正常流会降低发包速 率，启动拥塞控制机制，而对拥塞毫无反应的恶意流则会趁机“抢占”那些被t c p 流释放的可用带宽资源，结果正常流可占用的带宽越来越少，最后就会陷入“带宽 饥饿”。 9 华北电力大学硕士学位论文 我们采用实验仿真的办法，对这一现象进行了演示。如图2 1 所示，其中s 1 - s 3 之间为t c p 连接，t c p 连接发送速率不设上限；s 2 s 4 为u d p 连接；r l 和r 2 两 个路由器之间的缓存管理使用d r o p t a i l 算法，链路速度为1 5 m b p s ，延迟为3 m s ， 对于所有的连接，只维持一个输出队列缓存；s 1 r 1 、s 2 r i 、r 2 s 3 和r 2 s 4 的链 路速度均为1 0 m b p s ，延迟分别为：2 m s 、3 m s 、1 0 m s 和5 m s 。 定义：g o o d p u t ，一对连接中的接收端所获得的实际带宽，被称为该连接的 g o o d p u t 。 我们将仿真随着u d p 流的发送速率不断增加，u d p 连接g o o d p u t 、t c p 连接 g o o d p u t 和总的g o o d p u t 变化的情况，具体实验结果如图2 2 所示。 图2 - 1 仿真试验拓扑 从图2 2 中可以看出：当u d p 流的发送速率较小时，t c p 流能够获得较高的 g o o d p u t ，占用r l - r 2 之间总带宽比例也较高；但是随着u d p 流发送速率的不断增 加，u d p 流占用总带宽的比例越来越高，而t c p 流由于不能获得足够的带宽而导 致了数据包的丢失并启动了拥塞控制机制，结果发生了回退( b a c ko f f ) 。 图2 - 2 路由器采用d r o p t a i l 算法时，仿真t c p u d p 竞争有限带宽资源 由此可见，采用了毫无保护正常流机制的d r o p t a i l 算法管理路由器缓存队列时， 当无反应流( u d p 流) 增加发送数据包的速度时，就会和有反应流( t c p 流) 相互竞争 有限的带宽资源，并不合理的占据较多带宽资源，最终导致带宽分配的不公平性问 题，这种情况下，很容易就会使有反应流陷入带宽饥饿状态下。 当我们把t c p 流的个数增加到1 0 个，u d p 流的个数仍保持为1 个时，u d p 发 华北电力大学硕士学位论文 送速率从0 2 m b p s 增加到1 4 m b p s ，进行上述试验，实验结果如图2 - 3 所示，其中x 轴是t c p 流的流i d ，y 轴是u d p 流的发送速率，z 轴是带宽占用情况。根据实验 结果，随着u d p 流发送速率的增加，所有的t c p 流的带宽占用都呈现出下降趋势。 这进一步证明了恶意流的对于网络拥塞的非响应特性和高带宽占用特性造成了网 络的带宽不公平分配。 图2 - 3 路由器采用d r o p t a i l 算法时，模拟i o t c p i u d p 竞争有限带宽资源 2 2 2 网络拥塞崩溃 2 2 2 1 网络拥塞崩溃概述 一般来说，当不断增加的网络负载导致了网络有效工作的减少时，拥塞崩溃就 有可能发生。关于拥塞崩溃的第一次报道是发生在上世纪8 0 年代，这次网络拥塞 主要是由于t c p 连接不断的重传数据包，而相同的数据包要么已经在上次传输中被 发送出去，要么已经被接收端所接收到，这种毫无必要的数据包重传导致了网络拥 塞崩溃【2 引。我们把由于无必要的重传数据包导致的网络崩溃称之为“传统拥塞崩溃” ( c l a s s i c a lc o n g e s t i o nc o l l a p s e ) 。传统拥塞崩溃能一直保持稳定的状态，使得实际使用 带宽远远小于正常情况下的实际使用带宽。由传统网络崩溃所导致的问题已经被改 进t c p 慢启动计时器和现有t c p 协议采用的拥塞控制机制所解决【2 ”。 第二种形式的拥塞崩溃，是由于数据包不可达所导致的1 3 0 】。数据包被送到最终 目的地之前就被丢弃而使得带宽发生浪费时，就会引发由于数据包不可达所导致的 拥塞崩溃。这被认为是当今在拥塞崩溃问题上所不能解决的最大危险。这主要是因 为网络中越来越多的应用采用了开环应用( o p e nl o o p ) ，而这些应用却没有采用端到 端的拥塞控制机制；另一方面是网络中存在着尽力而为( b e s t e f f o r t ) 的应用，这些应 用即使在数据包丢弃速度越来越大的情况下，也会继续增加数据包的发送速度。 i l 华北电力大学硕士学位论文 2 2 2 2 恶意流导致的网络拥塞崩溃 从对网络产生的影响来说，恶意流由于其非t c p 友好性、对于丢包事件的非响 应性和高带宽占用的特性，更能导致上述所提到的：由于数据包不可达所导致的网 络带宽浪费，进而使网络有效服务的吞吐量下降，最终使得整个网络出现了拥塞崩 溃。d d o s 就是一个典型的例子。 图2 4 路由器采用d r o p t a i l 算法时，摸拟网络拥塞崩溃 我们使用图2 1 的网络拓扑结构，模拟了当网络中的无反应流增加发送数据包 速度时，导致网络拥塞崩溃的情景。 其中我们把r 2 s 4 的链路速度设置为1 2 8 k b p s ，这样在r 2 s 4 链路速度有限的 情况下，当由u d p 流模拟的无反应流增加发送数据包速度时，r 2 端必然会发生丢 包事件。这样一方面会导致带宽浪费，另一方面会导致t c p 流由于不能获得足够的 带宽，而吞吐量下降。在该实验中，我们仍然采用g o o d p 。u t 作为t c p 接收端和u d p 接收端是否获得正常带宽吞吐量的衡量标准。 如图2 - 4 所示，