（计算机应用技术专业论文）自相似环境下的拥塞控制算法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着社会的快速发展，信息的传播越来越多、越来越快。i n t e m e t 上的信息量更是 呈爆炸式增长，以致目前网络带宽和缓存容量等硬件资源难以满足业务流增长的需求， 由此引发网络拥塞。网络拥塞影响拥塞窗口大小及瞬时队列长度的稳定性，使响应速 度等性能严重降低，从而无法确保好的网络服务质量。因此网络拥塞控制已经成为近 些年来网络通信领域研究的重点。另方面，大量的研究结果表明，当前的网络流量 具有普遍的自相似和长相关特性，这使网络中原有的以m a r k o v 模型为基础的协议、策 略及评价方法不够准确，导致丢失率上升，网络性能下降。但同时由于自相似流量具 有可预测性，这也给研究人员研究拥塞控制算法时提供了新的思路。 本论文结合自相似流量的特点，探讨了自相似流量环境下基于端系统拥塞控制算 法研究的新方法，并与传统业务情况下的一些拥塞控制算法进行了仿真比较。重点研 究h s t c p 拥塞控制算法在自相似流量环境下的应用，以及利用自相似流量的特性对 r t t 的估值公式进行适当的修改来提高自相似流量环境下网络的性能。论文的主要工 作及成果如下： ( 1 ) 研究常见的基于端系统的拥塞控制算法，分析了t c pr e n o 、v e g a s 算法的工 作原理及优缺点，并利用o p n e t 网络仿真器比较了传统拥塞控制算法在自相似流量环 境下与在传统流量下算法的性能。 ( 2 ) 研究了流量预测的方法，从理论上证实了流量预测的可行性。 ( 3 ) 提出了在自相似流量环境下改进的h s t c p 拥塞控制算法。利用自相似流量 的可预测性来预测下一时间点的拥塞窗口大小。把预测的窗口应用到h s t c p 拥塞控制 算法中来动态的改变其窗口调整参数，使其能更加体现自相似流量网络环境下的实际 状况。最后用仿真验证了其有效性。 ( 4 ) 在自相似流量环境下的一些自相似流量特性必然会反映到r t t 上，本论文利 用这些特性对r t t 的估值公式进行适当的修改，使其能更加适合自相似流量网络环境。 并利用修改后得到的r t t 值来探知网络的拥塞情况，并根据拥塞等级来动态的调整拥 塞窗口调整参数。最后用仿真来验证估值公式改变前后的效率。 关键词：自相似；拥塞控制；流量预测；拥塞窗口；网络仿真 西南交通大学硕士研究生学位论文 第1 i 页 ii ii mi a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fs o c i e t y , t h et h r a n s m i s s i o no fi n f o r m a t i o ni sm o r ea n d m o r eq u i c k l ya n dm u c hm o r et h a ne v e et h ea m o u n to fi n f o r m a t i o no nt h ei n t e r a c ti s e x p l o d i n g ，s ot h en e t w o r k b a n d w i d t ha n dh a r d w a r er e s o u r c e ss u c ha sc a c h ec a p a c i t yc a nn o t m e e tt h eg r o w i n gd e m a n df o rb u s i n e s sf l o w s ，r e s u l t i n gi nn e t w o r kc o n g e s t i o n n e t w o r k c o n g e s t i o nd e c r e a s e st h es t a b i l i t yo fc o n g e s t i o nw i n d o ws i z ea n di n s t a n t a n e o u sl e n g t ha n d t h es y s t e mp e r f o r m a n c es u c ha sr e s p o n s es p e e ds e v e r e l y , r e s u l t i n gi nt h ep o o rn e t w o r k q u a l i t yo fs e r v i c e t h e r e f o r e ，c o n g e s t i o nc o n t r o lh a sb e c o m er e s e a r c hf o c u si nt h ea r e a so f n e t w o r kc o m m u n i c a t i o n si nr e c e n ty e a r s o nt h eo t h e rh a n d ，al a r g en u m b e ro fs t u d i e ss h o w t h a tt r a f f i co ft h ec u r r e n tn e t w o r kh a su n i v e r s a ls e l f - s i m i l a r i t ya n dl o n g - r a n g ed e p e n d e n c e w h i c hm a k e sp r o t o c o l 、s t r a t e g i e sa n de v a l u a t i o nm e t h o d so nt h en e t w o r kb a s e do no r i g i n a l m a r k o vm o d e li sn o ta c c u r a t ee n o u g h ，r e s u l t i n gi ni n c r e m e n tl o s sr a t ea n dt h ed e g r a d a t i o no f n e t w o r kp e r f o r m a n c e o nt h eo t h e rh a n d ，a ss e l f - s i m i l a rf l o wi sp r e d i c t a b l e ，i ta l s op r o v i d e s an e ww a yt oc o n g e s t i o nc o n t r o la l g o r i t h m i nt h i st h e s i s ，b yc o n s i d e r i n gt h es e l f - s i m i l a rc h a r a c t e r i s t i c ，an e wm e t h o do fs e l f - s i m i l a r c o n g e s t i o nc o n t r o li sd i s c u s s e d ，a n dt h ep e r f o r m a n c eo ft r a d i t i o n a lc o n g e s t i o na l o g r i t h mi s c o m p a r e dw i t hs e l f - s i m i l a rc o n g e s t i o nc o n t r o la l g o r i t h mt h r o u g hs i m u l a t i o n t h et h e s i s f o c u s e so na p p l i c a t i o no fh s t c pc o n g e s t i o nc o n t r o la l g o r i t h mi nt h en e t w o r k su n d e r s e l f - s i m i l a ra n du s e ss e l f - s i m i l a rc h a r a c t e r i s t i c st oa p p r o p r i a t em o d i f yt h ef o r m u l ao fr t t i n o r d e rt oi m p r o v et h en e t w o r kp e r f o r m a n c eu n d e rt h ee n v i r o n m e n to fs e l f - s i m i l a rt r a f f i c t h e m a i nr e s e a r c hw o r k sa n da c h i e v e m e n t so ft h i st h e s i sa r ea sf o l l o w s ： f i r s t l y , t h ec o m m o nc o n g e s t i o na l g o r i t h m si ss t u d i e d ，a n dt h eb a s i cp r i n c i p l ea n dm e r i t s a n df a u l t so ft c pr e n o ，v e g a sa l g o r i t h ma r ea n a l y z e d t h ep e r f o r m a n c eo ft h e s ea l g o r i t h m s w i t ht r a d i t i o n a ls h o r t - r a n gd e p e n d e n tt r a f f i ci n p u ti sc o m p a r e dw i t ht h a to fw i t hs e l f - s i m i l a r t r a f f i ci n p u tb ys i m u l a t i n gw i t ho p n e tm o d e l e r10 0 s e c o n d l y , t h em e t h o d so ft h et r a f f i cp r e d i c t i o na r es t u d i e d ，a n dt h ef e a s i b i l i t yo ft r a f f i c p r e d i c t i o ni sc o n f i r m e d i nt h e o r y t h i r d l y , a n o t h e ri m p r o v e dh s t c pc o n g e s t i o nc o n t r o la l g o r i t h mi sp r o p o s e du n d e rt h e e n v i r o n m e n to fs e l f - s i m i l a rt r a f f i ci n p u t t h ep r e d i c t a b i l i t yo fs e l f - s i m i l a rf l o wi su s e dt o f o r e c a s tt h ec o n g e s t i o nw i n d o ws i z eo ft h en e x tt i m e t h e nt h ef o r e c a s tw i n d o wi sa p p l i e dt o h s t c pc o n g e s t i o nc o n t r o la l g o r i t h mt od y n a m i c a l l ya d j u s tt h ew i n d o wp a r a m e t e r s i ti sa b l e t or e f l e c tt h es e l f - s i m i l a rn e t w o r ke n v i r o n m e n tb e t t e rt h a nt h em e t h o do ft r a d i t i o n a l t h e e f f e c t i v e n e s so ft h ei m p r o v e da l g o r i t h mi sv e r i f i e dt h r o u g hs i m u l a t i o n f i n a l l y ，b e c a u s et h ec h a r a c t e r i s t i co fs e l f - s i m i l a rm u s tb er e f l e c t i n gt or 丌i nt h i st h e s i s w eu s et h i sf e a t u r et om o d i f yt h er t tv a l u a t i o nf o r m u l a i tc a l l b em o r es u i t a b l ef o r e n v l r o n m e n to fs e l f - s i m i l a rn e t w o r k t h en e wr t tv a l u ei s u s e dt od e t e c tt h eg r a d eo f c o n g e s t i o na n da d ju s t e dd y n a m i c a l l yt h ec o n g e s t i o nw i n d o wb a s e do nt h e c o l q l g e s t i o nl e v e l s t h ee f f e c t i v e n e s so ft h ei m p r o v e da l g o r i t h mc o n s i d e r i n gt h ec h a n g eo ft h er t t v a l u a t i o n f o r m u l ai sv e r i f i e dt h r o u g hs i m u l a t i o n k e yw o r d s ：s e l f - s i m i l a r i t y ；c o n g e s t i o nc o n t r o l ；t r a f f i cp r e d i c t i o n ；c o n g e s t i o nw i n d o w ： n e t w o r ks i m u l a t i o n 西南交通大学曲南父遗大字 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权西南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密d ，使用本授权书。 ( 请在以上方框内打“4 ”) 学位论文作者签名：7 灯籀碧 指导老师签名： 日期：沙d 7 , u 谭献殇 f i 凝： o ，7 、参 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： ( 1 ) 建立网络仿真模型，并在此基础上仿真验证自相似流环境对基于传统理论的 拥塞控制算法性能的影响。 ( 2 ) 研究h s t c p 拥塞控制算法在自相似环境下的应用。在自相似流量环境下， 根据流量的可预测性，可用前一段时间的拥塞窗口值来预测后一个时间段的拥塞窗口 值。在此条件上对h s t c p 拥塞控制算法的拥塞窗口控制参数进行修改。 ( 3 ) 在自相似流量环境下对i 盯t 估值公式进行适当的修改。在自相似流量环境 下，自相似流量的一些性质必然体现在r t t 上，可以对r t t 的估值公式进行修改使之 能更加体现自相似流量网络的实际情况。在此基础上可根据i h t 值了解网络的拥塞状 况，动态的改变拥塞窗口控制参数。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成 果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰 写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确的说明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：筒镏袭 同期：尹p - 7 、j 一 西南交通大学硕士研究生学位论文第1 页 i i_ii_iii i i 1 1 课题的背景 第1 章绪论 伴随着科学技术与社会的迅速发展，产生的信息量呈爆炸式增长。与人们生活关 系密切的计算机网络也承载着巨大的信息量，随之而来的就是严重的网络拥塞。目前 网络的发展朝高速和应用多元化发展，以致于不断地给网络研究人员带来挑战。网络 拥塞导致的直接后果是整个网络的性能下降【l j ：包括分组丢失率增加、端到端延迟增 大、网络吞吐量( t h r o u g h p u t ) 下降、甚至有可能使整个系统发生拥塞崩溃( c o n g e s t i o n c o l l a p s e ) 。当网络处于拥塞崩溃状态时，微小的负载增量都将使网络的有效吞吐量急 剧下降。近年来，国内外许多研究人员都在从事着拥塞控制方面的研究。拥塞控制算 法主要包括t c p 的拥塞控制算法和路由器端实现的主动队列管理算法。t c p ( t r a n s m i s s i o nc o n t r o lp r o t o c 0 1 ) 是如今i n t e m e t 上使用最广的传输协议。t h o m p s o n 等 人【2 】指出，目前网络中百分之九十的数据流和大部分业务都是基于t c p 的。而且t c p 所使用的拥塞控制算法是保证当今网络在不断发展的同时又能有效避免拥塞崩溃【3 】的 主要方法。但是一些研究人员的研究【4 , 5 , 6 1 表明传统t c p 拥塞控制算法在高速网络中难 以充分利用带宽，原因在于传统t c p 拥塞控制算法在拥塞避免阶段采用的a i m d ( a d d i t i v ei n c r e a s em u l t i p l i c a t i v ed e c r e a s e ) 策略，窗1 5 增加慢，当拥塞发生时，窗e l 剧烈减小，导致了大拥塞窗口在拥塞发生后恢复慢，限制了获取带宽的能力。假定i 盯t 为1 0 0 m s ，包的大小为1 5 0 0 b y t e ，如果要达到1 0 g b p s 的速率，丢包概率不能大于2 十1 0 0 0 ， 也意味着5 3 小时内只能发生一次拥塞事件，在目前的硬件条件下显然是难以到达到。 s a l l yf l o y d 正是在这种情况下提出了h s t c p 拥塞控制算法。 二十世纪末，一些研究人员开始研究网络中的自相似现象。通过对w a n ( w i d e a r e a n e t w o r k ) 、l a n ( l o c a la r e an e t w o r k ) 等多种业务测量表明，在这些业务中普遍存在 长相关( l o n gr a n g ed e p e d e n c e ) 特性 岿j ，这是原来一直所用的经典模型( 泊松或贝 努利) 所无法准确描述的。主要表现在突发没有明确的长度，在不同的时间尺度下表 现出相同的突发特性且不能将它平滑掉。这种长相关特性打破了原来网络流是短相关 ( s h o r tr a n g ed e p e d e n c e ) 的假设，也带来许多与原来假设不同的特征( 如流量特征、 排队特征) 与操作方法( 缓存大小的选取，拥塞控制策略) 。例如，传统模型中的缓存 队列大小服从指数分布，而在长相关下，队列大小服从韦伯分布或者双曲线分布。因 为韦伯分布和双曲线分布比指数分布具有更严重的拖尾，即衰减得更慢，使得网络性 能有所降低，表现为排队时延和丢失率增加。长相关( 自相似) 虽然给原本复杂的网 西南交通大学硕士研究生学位论文第2 页 络控制问题带来了新的困难，但同时也为解决此类问题提供了新的思路。t u a n 和 p a r k 9 1 ，针对网络的自相似流量的可预测性提出了s a c ( s e l e c t i v ea g g r e s s i v e n s sc o n t r 0 1 ) 算法。主要思路是通过对网络流量的预测获得未来网络的空闲度，从而利用获得的网 络空闲度进行拥塞控制，这种方法在网络自相似性越强的情况下越有效。不过这种方 法主要依赖于网络流量测量，在现有网络环境下比较难以实施。本论文也是利用自相 似流的可预测性，选取适当的时间尺度对网络流量进行预测，并根据预测结果执行改 进后的拥塞控制算法，从而提高整体网络性能。 1 2 课题的研究意义 随着软硬件的发展，网络的速度会越来越快，也就是说高速将会成为网络的一个 最要特征。下一代互联网发展与建设的趋势表明：未来几年内，大规模高速网络试验 环境将形成，互联网骨干将升级到超1 0 g b p s 的高速链路，并且还很有可能持续增长。 同时，很多新型应用对网络数据传输的需求也不断提高，有越来越多的人已经开始利 用高速网络传输1 0 g b p s 到1 t b p s 数据。带宽提高了，研究人员开始研究传统的拥塞控 制算法在高速网络中是否能发挥好的性能。实践证明按a i m d 规则调整窗口，将会使 丰富带宽资源在很长时间内无法得到充分的利用。研究能把大网络带宽充分利用，能 够传输大数据量的网络拥塞控制算法就显得比较重要。因此，研究人员经过研究提出 了一些高速网络下的拥塞控制算法。如h s t c p ( “曲s p e e dt c p ) 引、s t c p ( s c a l a b l e t c p ) 10 1 、f a s tt c p 1 1 1 等。 传统的网络业务模型所描述的流量序列是短相关的，即网络流量序列自相关函数 随时间间隔增大而呈指数衰减。而目前大量研究结果证实，分形或者自相似【4 , 1 2 , 1 3 , 1 4 】是 现代网络的一个关键特性。网络中的数据在绝大部分的时问尺度范围内呈现统计相似 性和重尾特性。自相似特性对网络控制将会产生意料之外的影响，如对丢包率、时延、 吞吐量等性能指标的影响，这将使网络的设计、分析、管理和控制变得更加复杂。目 前网络中采用的拥塞控制算法，无论是高速拥塞控制算法和传统的拥塞控制算法，都 是基于传统网络业务模型( 泊松或贝努利模型) 。如果将基于传统模型上的拥塞控制算 法应用到自相似流量环境下，最终会导致丢失率的增加和网络性能的下降。所以，研 究自相似流量业务下的拥塞控制算法，特别是针对未来网络发展趋势的高速网络拥塞 控制算法的意义非常重要。 由于条件所限，不能直接在真实的网络上进行实验，那么只能通过计算机仿真进 行检验。通过软件产生自相似流，然后把其加载到业务模型上，通过大量的仿真观察 和总结，找出在运行和设计中出现的问题。接着，根据出现的问题提出相应的策略， 最后加以改进，为自相似流量下的网络性能的优化提供参考。这是提高网络性能的一 西南交通大学硕士研究生学位论文第3 页 个比较实际的做法。同样，要想设计出适合自相似流量环境下的拥塞控制算法也可采 用此方法，不断的仿真然后加以改进。最后用网络仿真对拥塞控制算法进行评价并对 网络性能进行评估。可见，对自相似流量下网络的仿真研究同样有非常重要的意义。 1 3 国内外研究现状 1 9 8 8 年v j a c o b s o n 指出了t c p 在网络拥塞控制方面的不足f l5 j 并提出了慢启动 ( s l o ws t a r t ) 、拥塞避免( c o n g e s t i o na v o i d a n c e ) 算法，即t c pt a h o e ，这是最早的t c p 协议。1 9 9 0 年v j a c o b s o n 在t c pt a h o e 基础上增加了快速重传和快速恢复算法，即t c p r e n o 1 6 】。t c pr e n o 算法避免了在网络拥塞不够严重时启用慢启动算法而造成窗口减少 过分剧烈的问题，从而能有效解决快速重传后通道为空的现象。但r e n o 算法没有考虑 到一个窗口内丢失多个报文的现象，在快速恢复算法中如果发送方收到一个不重复的 a c k ( a c k n o w l e d g e m e n t ) 就退出快速恢复状态。针对这个问题1 9 9 6 年f l o d y 等人提 出了t c pn e w r e n o 【1 7 j ，在n e w r e n o 算法中只有当全部报文都收到a c k 后才退出快速 恢复算法。1 9 9 5 年m m a t h i s 等提出了s a c k 算法【l 引，算法的思想是如果目的端口缓 存中存在不连续序列号的数据，就向源端发送有s a c k 选项的重复a c k ，源端据此就 能知道哪些数据目的端已经正确接收或者正在接收缓存区排队，从而能有选择的重传。 s a c k 算法能够有效减少无谓的t c p 重传，同时也不需要等到定时器超时就可以恢复 多个丢失的报文段，提高了重发效率和信道的利用率。除此之外还有1 9 9 4 年l s b r a k m o 等提出的t c pv e g a s 算法9 j 等。随着光通信技术的发展和软硬件技术的不断进步，目 前已经出现了带宽超过1 g b p s ，甚至1 0 g b p s 以上的高速网络，这些传统的t c p 协议在 高速网络中运行就会存在缺陷。原因之一是传统t c p 为了达到高吞吐率需要非常低的 丢失率，目前的硬件条件根本法到达。二是数据包丢失后恢复到比较大的窗口需要非 常长的时间，导致链路的利用率比较低。针对这些问题，很多学者和研究人员丌始研 究高速网络下的拥塞控制算法。目前一些有代表性的高速t c p 算法有：s f l o y d 等人提 出的h s t c p 、t k e l l y t 等人提出的s t c p 、i r h e e 等人提出的b i ct c p 2 0 】和加州理工的 n e t l a b 实验小组研究出的f a s tt c p 2 1j 等。 上述算法都很少涉及网络业务呈现自相似的情况，它们大多数研究工作都是以经 典的网络模型为基础，即以短相关流量作为研究背景。而最近大量研究人员的研究结 果表明，分形或者自相似是现代网络业务的关键特性。网络中的数据在绝大部分的时 间尺度范围内呈现统计相似性和重尾特性( 突发) 。自相似或者长相关特性给网络控制 带来了更多的复杂性，但同时由于自相似所具有的一些不同特性也给研究人员解决这 些问题带来新的途径。 t u a n 和p a r k 在文献 9 】当中提出了利用自相似流量网络可预测性的s a c 算法。s a c 西南交通大学硕士研究生学位论文第4 页 算法在感知未来网络如果空闲时就收回带宽，通过未来网络空闲程序及依赖度函数来 调节拥塞程度。这种方法网络自相似性越强越有效。不过文献 9 采用的方法过分依赖 于对网络流量的预测，本文作者认为虽然理论上有价值，但在现实的网络环境中却难 以实施。 文献 2 2 g a 作者从自相似流量模型和p a r e t o 重尾分布这两个角度解释了为什么对 于长相关业务流，如果一个区间的平均流量数值较大，那个下一个区间的平均流量数 值较大的可能性也比较大；如果一个区间内的平均流量数值较小，那么下一个区间平 均流量数值较小的可能性也较大，这也从一方面论证了长相关业务流在长时间尺度上 的可预测性。另外根据b e r a nj 曾经对自相似过程中采样平均值的预测期望和方差分析 得知，用过去一段时间内的流量均值直接作为未来一段时间内均值预测的可行性，而 且还肯定了自相似流量网络中如果用前一段时间的流量值来预测下一个时段的流量 值，预测的结果将比短相关流更为准确。此文献作者根据以上理论对传统拥塞控制算 法进行了下面改进。第一是根据缓存队列长度的变化调整窗口增加值a 。第二，根据窗 口平均值的变化调整窗口下降的b 值。第三，改变最大窗口数值。第四，第一种算法 和第二种算法的综合，即a 和b 联合调整。 文献 2 3 1 中作者在研究h u r s t 参数与相关长度之间定量关系的基础上，提出了基于 小波变换的预测端到端流量的自回归预测方法，并利用预测的值来改进t c p 拥塞控制 算法。论文主要是针对网络中广泛应用的r e n o 算法在无线网络中性能下降，网络利用 率降低的问题，结合自相似网络流量的可预测特性来改进t c p 拥塞控制算法。其思想 是根据动态选取的网络流量进行小波变换得到小波系数，然后用自回归算法预测下一 小波系数，最后再用预测到的小波系数进行小波逆变换，重构得到的流量。 文献 2 4 1 中作者同样利用自相似流量的可预测性，选取适当的时间尺度，采用可以 直接观测到的往返时延或者其它间接参数进行网络拥塞程度的预测，并在此基础上提 出改进的拥塞控制算法。其思想是计算归一化吞吐量即吞吐量的梯度的一个比值来衡 量网络的拥塞程度。作者认为当网络到达它的容量时，吞吐量的增加随负荷的增加而 趋于平缓，而在少量负荷下，吞吐量随负荷增加线性增加，因此吞吐量曲线的梯度可 作为拥塞程度的一个指示。如果增加连接，曲线开始变得扁平，而当删除连接时曲线 变得更加线性化。吞吐量梯度的比值是在 0 ，1 范围变动的变量，根据这个变量可以动 态调节网络的拥塞程度。 文献 2 5 1 中作者提出了基于路由的c h a r e d 算法，其思想是对传统r e d ( r a n d o m e a r l yd e t e c t i o n ) 算法在自相似流量网络中存在的缺点所做的改进。文献首先指出队列缓 存溢出概率p 与自相似h 参数的关系：h 参数越大，溢出概率也越大。因此在队列管 理r e d 算法中应该引入h 参数，以便能更好的了解网络的流量特征。同时当自相似参 数h 越大时，队列的丢弃概率也应该越大。算法主要做了两方面的改进，第是对r e d 西南交通大学硕士研究生学位论文第5 页 算法最大丢弃概率静态取值的改进，其主要是根据l a s k i n 等提出的在自相似流量网络 环境下队列缓存溢出概率与缓存容量需求的关系来对最大丢弃概率公式进行改进，得 出最大丢弃概率与h 参数的关系，从而能根据h 参数动态调节最大丢弃概率进而改变 丢弃概率，最后达到提高自相似流量环境下排队性能的目的。第二是对r e d 算法丢弃 概率线性的改进，作者采用升半柯西分布的隶属函数来描述拥塞避免中丢弃概率各阶 段的分布，同时引入h u r s t 参数来根据流量的自相似程度动态配置最大丢弃概率。 文献 2 6 中作者认为传统r e d 算法是以网络流量服从泊松分布为基础，因此把传 统的r e d 算法应用在自相似流量网络环境下便呈现出些缺点。其主要是因为在传统 模型下突发业务在长时间尺度下的均值是平稳的，而自相似流在长时间尺度下却不能 将其平滑掉。文献根据自相似流量的特点对r e d 算法加以改进，提出了一种基于时间 间隔的r e d 算法。这种算法主要是通过控制平均队列长度来避免网络进入拥塞状态。 另外由于在自相似流量环境下如果某一时间区间内的平均流量较小，那么下一时间区 间较小的可能性很大，反之如果平均流量值较大，那么下一时间区间较大的可能性也 比较大，所以没有必要在每个分组到达时都进行采样，完全可以根据测量时间间隔来 计算丢弃概率，每隔一个时间间隔来更新一次丢弃概率，这样就可以提高系统性能。 文献 2 7 中作者主要对主动队列管理进行研究，充分考虑了自相似流量对主动队列 管理算法的影响。首先，文献以f b m ( 分形布朗运动) 作为自相似流量模型来研究r e d 算法。其思想是将自相似h 参数引入权值中并估计下一时刻系统的平均队列长度，然 后用f b m 模型对自相似流量进行分析，根据队列长度的均值和方差计算最大阂值和最 小阈值，接着以n o r r o s 等人提出的基于f b m 模型的缓冲区溢出概率公式为根据动态 修改最大丢包率公式，并用所得结果与传统的r e d 算法结合实现动态管理。其次，文 献提出了基于流量预测的a q m ( 主动队列管理) 算法。其思想是用f a r i m a 分形模 型预测下一时刻的流量，并将预测的结果加入到主动管理算法中，使其能更好的控制 平均队列长度，提高系统性能。 以上所提及文献的作者都根据传统业务模型在自相似流量环境下的不足，分别在 端系统或者中间节点上对一些传统算法进行些改进，但是如果网络控制算法的研究 以未来网络的发展趋势为基础，那么算法的研究将更有意义。首先，自相似既然已经 被监测到是目前网络中一种普遍现象，而且自相似与传统的基于短相关的业务模型理 论基础不同，那么我们就不能忽视自相似现象。其次，未来网络的传输速率在突破软 硬件瓶颈后必然会呈现高速增长。目前很多用户用上了传输速率在l o g 或者以上的网 络。针对以上所述，为了保证网络能良好的运行，有必要研究基于自相似流量环境的 高速网络拥塞控制算法，这个研究既可以基于端系统又可基于中间节点。以上所述文 献所提及的基于自相似流量环境下制定的中间节点算法也可以用在高速网络上，但是 对基于端系统的传统拥塞控制算法在自相似流量环境下所做改进却不能应用到高速网 西南交通大学硕士研究生学位论文第6 页 _i i_ - - i ii i 络上，因为即使应用这个算法，也不能达到充分利用网络带宽的目的。 1 4 本论文研究工作及论文的内容安排 围绕上面所述的自相似网络业务下网络拥塞研究的现状以及研究工作中存在的问 题和不足，首先本论文简单介绍产生拥塞的原因、基于端系统拥塞控制的原理和h s t c p 拥塞控制协议。其次，提出基于自相似流量环境下的改进的h s t c p 算法，并利用仿真 比较了原h s t c p 算法和改进后的h s t c p 算法在自相似流量环境下和在传统业务下性 能。最后，结合网络自相似流的可预测性提出改进后的r t t 估值公式，根据新的i h t 估值公式估计i 玎t 值的大小来判断网络拥塞程度，并根据网络拥塞程度动态调节拥塞 窗口大小。最后仿真比较改进前后算法在自相似流量环境和传统流环境下的性能。 论文的组织结构如下： 第1 章绪论。论述课题背景、课题研究意义、国内外研究现状及论文的主要研 究内容。 第2 章自相似流的产生及预测。分析网络中自相似流对网络性能的影响，并根 据论文的需要介绍自相似流量的产生及流量预测的方法。 第3 章自相似对网络性能影响的仿真分析。首先介绍o p n e t 仿真软件，并详细 介绍仿真模型的建立、仿真数据的生成及参数的配置并验证模型的j 下确性。然后用建 立的模型仿真自相似对网络性能的影响，提出研究自相似环境下拥塞控制算法的意义。 第4 章自相似流量环境下h s t c p 改进算法。目前的h s t c p 算法理论基础基于 传统的理论模型，将其用于自相似流量环境下就会存在一些问题。同时自相似流具有 可预测性，可以用前一段时间的拥塞窗口值来预测一下段时间的拥塞窗口值，然后与 h s t c p 的数学模型结合来动态的调整拥塞口的大小，使这种改变更加能体现网络的实 际状况。 第5 章自相似流量环境下往返时延改进算法。自相似流量环境下由于长相关性， 即在一个长时间尺度下，不能将其突发性给平滑掉。在自相似流量环境下如果某一时 间区间内的平均流量较小，那么下一时间区间较小的可能性很大，反之如果平均流量 值较大，那么下一时间区间较大的可能性也比较大，这种特性必然会体现在往返时延 ( i 玎t ，r o u n d t r i pt i m e ) 上，所以可以选取适当区间去重新估算i 订t ，这种算法估 算出的i u t 值能更加反映网络的实际状况。在这章中本论文还将重新估算的i 盯t 用来 判断网络的拥塞程度，并根据拥塞程度动态计算改变拥塞窗口的两个参数。 总结与展望。总结本论文的主要工作，并提出存在的问题及论文存在的不足。最 后提出该课题需要进一步研究的问题。 西南交通大学硕士研究生学位论文第7 页 i | 1 _i i 第2 章自相似流量产生及预测 白相似的概念来源于分形( f r a c t a l ) 并且是它的一个重要特征。法国数学家b e n o i t b m a n d e l b r o t 给出了分形的定义【2 8 l ：其组成部分以某种方式与整体相似的形态称作分 形。自相似性是自然界中普遍存在的一个特性。例如，m a n d e l b r o t 在研究海岸线等曲 线时发现，取出该曲线图形的任何一部分，放大到原来的尺寸后，得到的图形与原来 图形有惊人相似。虽然自相似性在自然界中是一种普遍现象，但是在网络中是否存在， 如果存在其特性是什么，对网络性能有何影响等问题都需要去研究，这样才能有针对 性的研究出适合自相似流量环境的网络控制算法。所以在本章中首先介绍网络中的自 相似现象以及对网络性能的影响，接着介绍自相似的定义和一些性质。由于本论文研 究的重点为自相似流量环境下的传输层控制算法的研究，其理论根据是自相似流量的 可预测性，所以本章节的重点是介绍自相似流量的产生及如何对自相似流进行预测。 2 1 网络流量自相似性及其对网络性能影响 2 1 1 网络流量自相似性 在自然界发现自现自相似现象后，一些研究人员丌始猜测计算机网络中是否也存 在自相似性。二十世纪末，很多研究人员开始从各种网络上收集数据。研究员d v w i l s o n 等【2 弘3 1 j 使用了一种精密的网络监测设备对b e l l c o r em o r r i sr f d 中心的一些以太网中的 业务流进行深入研究，他们从实际网络中获得的数百万个数据包；p a x s o n 和f l o y d 3 2 , 3 3 】 从w a n ( w i d ea r e an e t w o r k ) 上收集大量数据；e r r a m i l l i 和w i l l i n g e r t 3 4 j 等人收集大量 从i s d n ( i n t e g r a t e ds e r v i c ed i g i t a ln e t w o r k ) 和v b r ( v a r i a b l eb i tr a t e ) 视频业务中 得到的数据；b e l l c o r e 研究人员从c c s n ( 共路信令网) 上收集了大量业务数据；h e y m a n 等人测量了a t m ( a s y n c h r o n o u st r a n s f e rm o d e ) 网络上的视频业务的一些特性【3 5 j ； c r o v e l l a 等观察分析了反映数以千计文档请求的w w w ( w o r l dw i d ew 曲) 业务【9 】； a d d i e ，z u c k e r m a n 和n e a m e 从高速数据网上收集了大量业务数据【36 | 。这些研究人员从 实际网络中采集大量数据，并利用统计的方法分析网络流量检测网络中是否存在自相 似特性，而且对表征这种自相似特性的参数进行估计。研究人员从这些工作中发现虽 然当用户数量、拓扑结构、服务类型等发生变化时，通信流量中却始终存在自相似现 象，这也为自相似特性在网络中普遍存在提供了有力支持。自相似现象在网络流量中 主要表现在突发没有明确的长度，在不同时间尺度下突发特性相同，也就是说业务是 长相关的，而且不能将其突发特性平滑掉。但是传统模型包括泊松过程( 连续时间) 西南交通大学硕士研究生学位论文第8 页 或者贝努利过程( 离散时间) ，这些过程只能处理短相关业务。如图2 一l 所示。左边为 实际阿络流量，右边为传统模型泊松分布产生的流量。从图中可以看出，实际网络突 发性更强，在不同的时间尺度下突发性都存在且具有相同的统计特征。而泊松分布产 离 ；嚣 n l 剐z o o 堇 如幽蝰幽l ； o o o o t u 3 oo on o o引o t n - 1 0 d o ， d o o 0 n 口 o - 0 0 18 自 实际网络流越传统模型流簟 凹2 1 传统模型与实际网络业务产生流量对比 生的流量在大时自j 尺度范围内突发性明显被平滑掉了，所以传统理论将突发经过统计 变得平滑与实际网络中的流量特性存在差异。 212 自相似对网络性能的影响 网络的吞吐量、丢包车( p a c k e t l o s s r a t e ) 、时延( t i t i l e d e l a y ) 是衡量阿络性能的置 个重要的指标。在中问节点中都存在入口队列和出口队列，每个队列都有一定的缓 存来临时保存到达的数据包。如果包的发送速率小于包的到达速率这些还没有发送 的数据包就会在队列中排队等待转发，这样就会产生时延。若包的到达