（管理科学与工程专业论文）基于流量优化控制的tcpip拥塞控制研究.pdf

独创声明 y - 5 9 8 7 3 3 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得( 注：如没有其他需要特别声明的，本栏可 空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 城缘 导师签字：zo 娟冬 i 签字日期：2 00 4 年4 月蚜日 签字日期：20 0 4 年手月z 扩曰 妻妻华考、导师阔静 禽垒文公布 一一” 基于流量优化控制的t c p i p 拥寒控制 i ) f 究 摘要 近年来，i n t e r n e t 经历了飞速的发展，用户数量的膨胀和新的应用不断产生，使得网 络拥挤问题更加引人注目。由于拥塞控制是确保互联网鲁棒性的关键因素，也是各种管理 控制机制和应用的基础，因此关于互联网的拥塞控制问题一直是网络研究的一个热点。 本文绪论介绍了拥塞的基本概念、产生的原因以及拥塞控制的分类，探讨了t c p 拥 塞控制机制，分析了当前拥塞控制中存在的主要问题。 第2 章首先介绍网络上存在的两种流量控制机制，一种是端到端流控制机制，另一种 是i p 层流控制机制。然后分析了两种流量控制机制在处理拥塞现象中存在的问题。最后详 细介绍了优化流量控制机制的基本原理、发展过程和处理拥塞问题时的优势与不足。 第3 章提出了一种基于流量优化控制的t c p i p 拥塞控制机制方案一o c c ( o p t i m i z a t i o nc o n g e s t i o nc o n t r 0 1 ) ，阐述了它的总体设计目标和算法目标。该算法分为l p 层和发送端两部分，i p 层算法利用队列长度和优化理论估计网络拥塞程度，通过对数据包 的标记反馈到发送端：发送端算法根据被标记的数据包的个数估计i p 层拥塞程度并调整发 送速率。在o c c 方案中，通过i p 层算法和发送端算法的协同工作，兼顾了发送端的发送 速率和瓶颈链路的可用带宽。o c c 还使得各种数据流的能够友好共存，并对它所涉及的网 络区域的性能进行了优化。 为了验证算法的合理性和有效性，在第4 章中对此算法进行了大量的仿真实验来评价 算法多方面的性能。为了使实验环境更接近现实网络，在验证算法的公平性的试验中使用 了自相似的背景流来模拟网络的状态变化。实验表明算法对网络拥塞状态的变化能做出灵 敏的反应，同时对协议内部和协议之间的公平性以及协议对网络拓扑结构的鲁棒性也很 好。试验平台是n s 模拟器，n s 是目前国际上应用广泛的网络仿真软件，在分析和评价 网络性能方面发挥了重要作用，本文实验均是在n s 中进行仿真分析的。 第5 章首先说明了用自相似流作为网络仿真试验背景的必要性，简介了几种常用的自 相似的等价理论定义及网络仿真实验中产生自相似网络通信量的方法，然后介绍用n s 模 拟器产生自相似流的方法。最后探讨了自相似参数应用在拥塞控制中可能性。 关键词：拥塞控制，o f c ，t c p i p ，优化，网络仿真，i n t e r n e t ，发送端，i p 层 分类号：t p 3 9 3 山东师范大学顺士学位论文 r e s e a r c ho ft c p f l p c o n g e s t i o nc o n t r o l b a s e do nt h em e t h o do f a b s t r a c t o p t i m i z a t i o n f l o wc o n t r o l i n t e m e th a sb e e nd e v e l o p e dr a p i d l yi nr e c e n ty e a r s t h ei n f i a t i o no fu s e r sq u a n t i t ya n dt h e c o n s t a n t p r o d u c i n go fn e wa p p l i c a t i o n sm a k et h ec r o w d e dp r o b l e mo ft h en e t w o r km o r e n o t i c e a b l e b e c a u s ec o n g e s t i o nc o n t r o li sa k e yf a c t o ro fg u a r a n t e e i n gt h er o b u s t n e s so fi n t e r n e t a n daf o u n d a t i o no fv a r i o u sk i n d so fm a n a g e m e n tc o n t r o l l i n gm e c h a n i s m sa n da p p l i c a t i o n s ，t h e p r o b l e mo fc o n g e s t i o nc o n t r o la b o u ti n t e r n e th a sb e e naf o c u sb e i n gs t u d i e do f t h en e t w o r ka l l t h et i m e t h ei n t r o d u c t i o no ft h i sp a p e ri n t r o d u c e st h eb a s i cc o n c e p t i o no fc o n g e s t i o n t h er e a s o n l e a d i n g t ot h e c o n g e s t i o na n dt h e c l a s s i f i c a t i o no fc o n g e s t i o nc o n t r 0 1 i tp r o b e si n t ot h e c o n g e s t i o n c o n t r o lm e c h a n i s mo f t c pa n da n a l y s e st h ec o n g e s t i o nc o n t r o lp r o b l e m sa tp r e s e n t c h a p t e r2i n t r o d u c e st w ok i n d so ff l o wc o n t r o l l i n gm e c h a n i s m sa tf i r s t 0 n ei se n d t o - e n d f l o wc o n t r o lm e c h a n i s m t h eo t h e rk i n di sb a s e do nf l o wc o n t r o lr u n n i n go nt h ei pl a y e r t h e ni t a n a l y s e st h ep r o b l e me x i s t i n gi nt h et w ok i n d so ff l o wc o n t r 0 1m e c h a n i s m sw h e nd e a l i n gw i t h t h e c o n g e s t e dp h e n o m e n o n a t l a s ti tr e c o m m e n d si n d e t a i lt h eb a s i c p r i n c i p l e o ft h e o p t i m i z a t i o nf l o wc o n t r 0 1m e c h a n i s m ，t h ee v o l u t i o n 。t h ea d v a n t a g e a n dd i s a d v a n t a g ew h i l e d e a l i n g w i t ht h ec o n g e s t e d p r o b l e m c h a p t e r 3 p u t s f o r w a r dan e ws c h e m e o c ct h a ti sat c p i p c o n g e s t i o n c o n t r o l m e c h a n i s m0 nt h eb a s i so f o p t i m i z a t i o nf l o wc o n t r o la n dp r o p o s e si t so v e r a l ld e s i g no b j e c ta n d a l g o r i t h mt a r g e t s t h i ss c h e m e c o n s i s t so f t w o p a r t s i na l g o r i t h mo f i pl a y e rl e n g t ho f q u e u e a n d t h eo p t i m i z a t i o nt h e o r ya r eu s e dt oe s t i m a t et h ec o n g e s t e dd e g r e eo ft h en e t w o r ka n dt or e s p o n d t ot h ec o n g e s t e dd e g r e et h r o u g hm a r k i n gp a c k e t s i na l g o r i t h mo fd e l i v e r i n ge n dw ee s t i m a t e s c o n g e s t e dd e g r e eo ft h e l i n ka n da d j u s t st h es p e e do fd e l i v e r i n ga c c o r d i n gt ot h en u m b e ro f p a c k e t st 1 a th a sb e e nm a r k e d i nt h es c h e m eo f0 c c w i t ht h ec o o p e r a t i o no ft h ei pl a y e r a l g o f i t h ma n dt h ed e l i v e r i n ge n da l g o r i t h m i tc o n s i d e r st o 恤es p e e do fd e l i v e r i n ga n dt h e a v a i l a b l ew i d t ho fb o t t l e n e c k a l s oo c cm a k e sa 1 1k i n d so fd a t af l o w sc o e x i s t e df r i e n d l ya n d o p t i m i z e st h ep e r f o r m a n c eo f t h e n e t w o r ka r e aj n v o l v e dt oi t i no r d e rt ov e r i f yt h er a t i o n a l i t ya n d v a l i d i t yo f t h ea l g o r i t h m ，i nc h a p t e r4al a r g ea m o u n t o fs i m u l a t i o ne x p e r i m e n t sh a v eb e e nm a d et oa p p r a i s et h ep e r f o r m a n c eo fa l g o r i t h m s i no r d e rt o m a k et h ee x p e r i m e n t se n v i r o n m e n tc l o s et ot h er e a ln e t w o r k i nt h ee x p e r i m e n t so fv e r i f y i n g f a i r n e s so fa l g o r i t h mw eu s es e l f - s i m i l a rf l o wa st h eb a c k g r o u n df l o w s t h ee x p e r i m e n t ss h o w t h a tt h ea l g o r i t h mc a nm a k e q u i c kr e s p o n s e t ot h ec h a n g eo f c o n g e s t e d s t a t eo f t h en e t w o r k b o t h t h ef a i r n e s sw i t h i na n db e t w e e np r o t o c o l sa n dt h er o b u s t n e s st ot h et o p o l o g i c a ls t r u c t u r eo ft h e n e t w o r ka r ev e r yg o o d t h ee x p e r i m e n tp l a t f o l t t li san ss i m u l a t o r n si sak i n do fn e t w o r k s i m u l a t i o ns o f t w a r ew i d e l yu s e di nt h ew o r l da tp r e s e n t i th a sp l a y e da ni m p o r t a n tr o l ei n a n a l y z i n ga n da p p r a i s i n gt h ep e r f o r m a n c eo f t h en e t w o r k a l lt h ee x p e r i m e n t so ft h i sp a p e ra r e a n a l y z e da n ds i m u l a t e dt h r o u g h n s a tf i r s tc h a p t e r5e x p l a i n st h en e c e s s i t yo f u s i n g s e l f - s i m i l a rf l o wa st h eb a c k g r o u n df l o wi n n e t w o r ks i m u l a t i o n sa n di n t r o d u c e ss e v e r a lk i n d so fc o m m o n l yu s e dd e f i n i t i o n so fs e l f - s i m i l a r t h e ni ti n t r o d u c e st h em e t h o do fp r o d u c i n gs e l f - s i m i l a rf l o wi ns i m u l a t i o ne x p e r i m e n t sa n dt h e 4 基十流量优化控制的t c p i p 拥采控制研究 w a yo fu s i n gn st op r o d u c e s e l f - s i m i l a rf l o w l a s tw ed i s c u s st h ep o s s i b i l i t yo fu s i n gt h e p a r a m e t e r o fs e l f - s i m i l a ri nt h ec o n g e s t i o nc o n t r 0 1 k e y w o r d s ：c o n g e s t i o nc o n t r o l ，o f c ，t c p i ro p t i m i z a t i o n ，n e t w o r k s i m u l a t i o n ，i n t e m e t ， d e l i v e r i n ge n d ，i pl a y e r c l a s s i f i c a t i o n ：t p 3 9 3 5 山东师范大学硕上学位论文 第1 章绪论 互联网的历史可以上溯到上个世纪7 0 年代中期。a r p a ( a d v a n c e dr e s e a r c hp r o j e c t s a g e n c y ) 为了实现异种网络之间的互联与互通，推出了t c p i p 体系结构和协议规范。t c p i p 协议族为互联网提供了基本的通信机制。 根据m c i ( m a k e rc o m m u n i c a t i o n s ，i n c ) 的统计，互联网上总字节数的9 5 及总数 据包数的g o 使用t c p 协议传输。t c p 的目的就是为了解决互联网的稳定性、异质性( 接 受端缓冲区大小、网络带宽及延迟等) 、各流之间享用带宽的公平性、使用效率及拥塞控 制等问题，从而为互联网提供可靠、健壮( r o b u s t ) 的端到端通讯。“尽力而为”机制的最 大优势是设计简单，可扩展性强。互联网在过去的十几年中经历了爆炸式的增长并能够顺 利的运行，这已经充分证明了这种设计机制的成功。然而这种优势并不是没有缺陷的。例 如由于队列溢出，互联网路由器会丢弃约1 0 的数据包。因此，互联网上主要的互连协议 t c p i p 的拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 机制对控制网络拥塞具有特别重要的意义。拥 塞控制是确保互联网鲁棒性( r o b u s t n e s s ) 的关键因素，也是各神管理控制机制和应用( 如 多媒体通信中q o s 控制、d i f f e r e n t i a t e ds e r v i c e s ) 的基础，因此关于互联网的拥塞控制问 题一直是网络研究的一个热点。 1 1 网络拥塞的基本概念 1 1 1 拥塞的基本概念 网络的负荷的增加会导致用户对网络资源利用率的降低，这种现象称为拥塞。在网络 发生拥塞时，会导致吞吐量下降，如果用户仍不断的提出对网络资源的需求，严重时会发 生“拥塞崩溃”( c o n g e s t i o nc o l l a p s e ) 现象。就是说，拥塞崩溃发生在网络负载的增加导 致网络效率的降低的时候。拥塞崩溃最先在1 9 8 0 年中叶提出，主要r h 于t c p 连接不必 要的重传那些正在传送或已经被接收方接收了的数据包。f l o y d 总结出拥塞崩溃主要包括 以下几种：传统的崩溃、未传送数据包导致的崩溃、由于数据包分段造成的崩溃、日益增 长的控制信息流造成的崩溃等。 吞 吐 量 图1 - 1 网络负载与吞吐量及响应时间的关系 对于捌塞现象，我们可以进步用图1 - 1 来描述。当网络负载较小时，吞吐量基本上 6 岍，_i!_1 c - -!-i h 一嗵公 一 基于流量优化控制的t c p i p 拥塞控制研究 随着负载的增长而增长，呈线性关系，响应时间增长缓慢。当负载达到网络容量时，吞吐 量呈现出缓慢增长，而响应时间急剧增加，这一点称为k n e e 。如果负载继续增加，路由 器开始丢包，当负载超过一定量时，吞吐量开始急剧下降，这一点称为c l i f f 。拥塞控制机 制实际上包含拥塞避免( c o n g e s t i o na v o i d a n c e ) 和拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 两种 策略。前者的目的是使网络运行在k n e e 附近，避免拥塞的发生；而后者则是使得网络运 行在c l i f f 的左侧区域。前者是一种“预防”措施，维持网络的高吞吐量、低延迟状态，避 免进入拥塞；后者是一种“恢复”措施，使网络从拥塞中恢复过来，进入正常的运行状态。 1 1 2 拥塞产生的原因 拥塞产生的直接原因有以下3 点吲： 存储空间不足。几个输入数据流共同需要同一个输出端1 ：3 ，在这个端1 3 就会建立排队。 如果没有足够的存储空间存储，数据包就会丢弃。对突发数据流更是如此。增加存储空间 在某种程度上可以缓解这一矛盾，但如果路由器有无限存储量时，拥塞只会变得更坏，而 不是更好，因为在网络里数据包经过长时间排队完成转发时，它们早已超时，源端认为它 们已经被丢弃，而这些数据包还会继续向下一路由器转发，从而浪费网络资源，加重网络 拥塞。 带宽容量不足。低速链路对高速数据流的输入也会产生拥塞。根据香农信息理论，任 何信道带宽最大值即信道容量c = b l 0 9 2 ( 1 + s n ) ( n 为信道白噪声的平均功率，s 为信源的 平均功率，b 为信道带宽) 。所有信源发送的速率r 必须小于或等于信道容量c 。如果r c ， 则在理论上无差错传输就是不可能的，所以在网络低速链路处就会形成带宽瓶颈，当其满 足不了通过它的所有源端带宽要求时，网络就会发生拥塞。 处理器处理能力弱、速度慢也能引起拥塞。如果路由器的c p u 在执行排队缓存，更 新路由表等功能时，处理速度跟不上高速链路，也会产生拥塞。同样，低速链路对高速c p u 也会产生拥塞。 要避免拥塞的发生，对以上3 点原因需综合考虑。例如，提高链路速率而不改变处理 器，只会转移网络瓶颈，而不能避免拥塞。所以拥塞往往也是系统各部分不匹配的结果。 拥塞一旦发生往往会形成一个不断加重的过程。如果路由器没有空余的缓存，它就必须丢 弃新到的数据包。当数据包丢弃时，源端会超时，重传该包。由于没有得到确认，源端只 能保留数据包，结果缓存会进一步消耗，加重拥塞。目前在i n t e m e t ( i p v 4 ) 上实际使用的拥 塞控制基本上是建立在t c p 的窗口控制基础之上的。i p 层( 网络层) 的路由器所起的作用相 对较小，不过现在在i p 层控制拥塞的研究逐渐增多，已经形成了一个新的研究热点。 1 2 拥塞控制机制分类 ( 1 ) 从控制理论的角度，拥塞控制算法可以分为开环控制和闭环控制两大类。当流 量特征可以准确规定、性能要求可以事先获得时，适于使用开环控制；当流量特征不能准 确描述或者当系统不提供资源预留时，适于使用闭环控制。i n t e r n e t 中主要采用闭环控制 方式。闭环的拥塞控制分为以下3 个阶段：检测网络中拥塞的发生，将拥塞信息报告到拥 塞控制点；拥塞控制点根据拥塞信息进行调整以消除拥塞。闭环的拥塞控制可以动态地适 应网络的变化，但它的一个缺陷是算法性能受到反馈延迟的严重影响。当拥塞发生点和控 制点之间的延迟很大时，算法性能会严重下降。 ( 2 ) 根据算法的实现位置，可以将捌塞控制算法分为两大类：链路算法( 1 i n ka l g o r i t h m ) 山东师范大学颇士学位论文 和源算法( s o u r c ea l g o r i t h m ) 。链路算法在网络设备( 如路由器和交换机) 中执行作用是检 测网络拥塞的发生，产生拥塞反馈信息。源算法在主机和网络边缘设备中执行，作用是根 据反馈信息调整发送速率。拥塞控制算法设计的关键问题是如何生成反馈信息和如何对反 馈信息进行响应。 源算法中使用最广泛的是t c p 协议中的拥塞控制算法。近年来，t c p 中采用了很多 新的算法，包括慢启动( s l o ws t a r t ) 、拥塞避免、快速重传( f a s tr e t r a n s m i t ) 、快速恢复( f a s t r e c o v e r y ) 、选择性应答( s a c k ) 等，大大提高了网络传输的性能。t c p 中使用的拥塞控制 算法已经成为保证i n t e r n e t 稳定性的重要因素。 链路算法的研究目前集中在主动队列管理【3 ( a c t i v eq u e u em a n a g e m e n t ，简称a q m ) 算法方面。和传统的队尾丢弃( o r o p t a i l ) 相比，a q m 在网络设备的缓冲溢出之前就丢弃或 标记报文，a q m 的主要优点是：a 、减少网关的报文丢失。使用a q m 可以保持较小的队 列长度，从而增强网关容纳突发流量的能力。b 、减小报文通过网关的延迟。减小平均队 列长度可以有效地减小报文在网络设备中的排队延迟。c 、避免l o c k o u t 行为的发生。a q m 的一个代表是r e d ( r a n d o me a r l yd e t e c t i o n ) h 。研究表明，r e d 比d r o p t a i j 具有更好的 性能。但是r e d 的性能对算法的参数设置十分敏感，所以至今没有在i n t e r n e t 中得到广 泛的使用。 ( 3 ) 根据反馈信息的反馈机制不同，可以将拥塞控制机制分为显式拥塞控制机制和 隐式拥塞控制机制两种。显式拥塞控制机制的代表为e c n ( 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 ) 算法 5 1 ，即端系统通过报文中网关设定的标志位检测拥塞，而不完全依赖报文丢失来判断 拥塞的发生。 1 3t o p 拥塞控制原理介绍 1 9 8 6 年初，j a c o b s o n 开发了现在在t c p 应用中的拥塞控制机制。运行在端节点主 机中的这些机制使得t c p 连接在网络发生拥塞时回退( b a c ko f f ) ，也就是说t c p 源端会 对网络发出的拥塞指示( c o n g e s t i o nn o t i f i c a t i o n ) ( 例如丢包、重复的a c k 等) 作出响应。 1 9 8 8 年j a c o b s o n 6 】针对t c p 在控制网络拥塞方面的不足，提出了“慢启动”( s l o w s t a r t ) 和“拥塞避免”( c o n g e s t i o na v o i d a n c e ) 算法。1 9 9 0 年出现的t c pr e n o 版本增加了“快 速重传”( f a s tr e t r a n s m i t ) 、“快速恢复”( f a s tr e c o v e r y ) 算法，避免了网络拥塞不严 重时采用“慢启动”算法而造成过大地减小发送窗口尺寸的现象，这样t c p 的拥塞控制 就由这4 个核心部分组成。近几年又出现t c p 的改进版本如n e w r e n o 和选择性应答 ( s e l e c t i v ea c k n o w l e d g e m e n t ，s a c k ) 等。正是这些拥塞控制机制防止了今天网络的拥 塞崩溃。 t c p 协议的目的是为上层应用提供可靠的服务，其主要特征在于：确保各流享用带 宽的公平性，动态发现当前可利用的带宽，拥塞避免及控制机制以避免拥塞崩溃 ( c o n g e s t i o nc o l l a p s e ) 的发生。 标准版本的t c p 使用基于窗口的的和式增加积式减小l ，j ( a d d i t i v ei n c r e a s e m u l t i p l i c a t i v ed e c r e a s e ，a i m d ) 方式控制发送速率，以保证稳定性及带宽享用的公平性。 错误控制机制是一个可靠传输协议的关键部分。它对协议的性能有很大的影响，包括吞吐 量、能量消耗及可靠性。错误控制通常包括错误检测和错误恢复两部分。为了保证数据传 输的可靠性，t c p 要求接收端在正确接收到数据段( d a t as e g m e n t ) 后向发送端发送一个 确认包，确认包中包含了期望接收到的下一个数据段的序号。t c p 发送端通过监测确认包 的序号来检测是否发生了错误。如果发生超时或者发送端收到一定数量( 通常是3 个) 重 复的确认包，则认为传输过程中发生了错误，数据段被丢弃。由于有线网络的位出错率很 基于流量优化控制的t c p i p 拥塞拄制研究 低，因此t c p 假设丢包是由于网络拥塞引起的。在错误恢复处理过程中，t c p 重传丢弃 的数据段、减小发送端窗口大小并且在超时情况下重置超时时钟。 t c p 拥塞控制四个主要过程简要介绍如下： 慢启动阶段：早期开发的t c p 应用在启动一个连接时会向网络中发送大量的数据包， 这样很容易导致路由器缓存空间耗尽，网络发生拥塞，使得t c p 连接的吞吐量急剧下降。 由于t c p 源端无法知道网络资源当前的利用状况，因此新建立的t c p 连接不能一开始就 发送大量数据，而只能逐步增加每次发送的数据量，以避免上述现象的发生。具体地说， 当建立新的t c p 连接时，拥塞窗口( c o n g e s t i o nw i n d o w ，c w n d ) 初始化为一个数据包 大小。源端按c w n d 大小发送数据，每收到一个a c k 确认，c w n d 就增加一个数据包发送 量，这样c w n d 就将随着回路响应时间( r o u n dt r i p t i m e ，r t t ) 呈指数增长，源端向网 络发送的数据量将急剧增加。事实上，慢启动一点也不慢，要达到每r t t 发送w 个数据 包所需时间仅为r t t l o g w 。由于在发生拥塞时，拥塞窗口会减半或降到1 ，因此慢启 动确保了源端的发送速率最多是链路带宽的两倍。 拥塞避免阶段：如果t c p 源端发现超时或收到3 个相同a c k 副本时，即认为网络发 生了拥塞( 主要因为由传输引起的数据包损坏和丢失的概率很小( s s t h r e s h ，t c p 就执行拥塞避免算法，此时，c w n d 在每次 收到一个a c k 时只增加1 c w n d 个数据包，这样，在一个r 厂内，c w n d 将增加1 ，所以 在拥塞避免阶段，c w n d 不是呈指数增长，而是线性增长。 快速重传和快速恢复阶段：快速重传是当t c p 源端收到到三个相同的a c k 副本时， 即认为有数据包丢失，则源端重传丢失的数据包，而不必等待r t o 超时。同时将s s t h r e s h 设置为当前c w n d 值的一半，并且将c w n d 减为原先的一半。快速恢复是基于“管道”模 型( p i p em o d e l ) 的“数据包守恒”的原则( c o n s e r v a t i o no fp a c k e t sp r i n c i p l e ) ，即同一 时刻在网络中传输的数据包数量是恒定的，只有当“旧”数据包离开网络后，才能发送“新” 数据包进入网络。如果发送方收到一个重复的a c k ，则认为已经有一个数据包离开了网络， 于是将拥塞窗1 ：3 加1 。如果“数据包守恒”原则能够得到严格遵守，那么网络中将很少会 发生拥塞。本质上，拥塞控制的目的就是找到违反该原则的地方并进行修正。 图1 2 所示t c p 慢启动和拥塞避免、快速重传和快速恢复： 拥 辜 窗 口 图1 - 2 慢启动和拥塞避免、快速重传和快速恢复 经过十多年的发展，目前t c p 协议主要包含有四个版本：t c pt a h o e 、t c pr e n o 、 t c pn e w r e n o 和t c ps a c k 。t c pt a h o e 是早期的t c p 版本，它包括了3 个最基本的 拥塞控制算法一“慢启动”、“拥塞避免”和“快速重传”。t c pr e n o 在t c p t a h o e 基础 山东师范大学顺： 学位论文 上增加了“快速恢复”算法。t c p n e w r e n o 对t c p r e n o 中的“快速恢复”算法进行了 修正，它考虑了一个发送窗口内多个数据包丢失的情况。在r e n o 版中，发送端收到一个 新的a c k 后退出“快速恢复”阶段，而在n e w r e n o 版中，只有当所有的数据包都被确 认后才退出“快速恢复”阶段。t c p s a c k 关注的也是一个窗口内多个数据包丢失的情况， 它避免了之前版本的t c p 重传一个窗口内所有数据包的情况，包括那些已经被接收端正 确接收的数据包，而只是重传那些被丢弃的数据包。 另外，在1 9 9 4 年，l s b r a k m o 惮1 等提出了一种新的拥塞控制策略- - t c p v e g a s 。由 于r t t 值与网络运行情况有密切关系，因此，t c p v e g a s 通过观察t c p 连接中r t t 值 改变感知网络是否发生拥塞，从而控制拥塞窗口大小。如果发现r t t 值变大，v e g a s 就认 为网络正在发生拥塞，于是开始减小拥塞窗口；另一方面，如果r t t 变小，v e g a s 就认为 网络拥塞正在解除，于是再次增加拥塞窗口。这样，拥塞窗口在理想情况下就会稳定在一 个合适的值上。t c p v e g a s 的最大优点在于拥塞机制的触发只与r t t 的改变有关，而与包 的具体传输时延无关。由于t c p v e g a s 不是利用丢包来判断网络可用带宽，而是以r t t 的变化来判断，因此能更精确地预测网络的可利用带宽，其公平性、效率都较好。但是 t c p v e g a s 并未能在互联网上大规模使用，主要是因为使用t c p v e g a s 的流在带宽竞争能 力方面不及未使用t c p v e g a s 的流，从而导致网络资源享用不公平，而不是算法本身的问 题。 1 4 问题提出 传统的t c p 拥塞控制机制不能从i p 层得到拥塞指示和拥塞控制，为了进行拥塞控制， 必须使用诸如确认、超时等信息来推断网络拥塞情况。所以它本质上是端到端的控制机制， 即单一的t c p 流是根据自己对网络状况的探测决定数据发送的时间和数据报的长度，而 不考虑它所经过的链路上的其它数据流的状况。所以从宏观角度t c p 拥塞控制存在以下 问题： 第一、网络流量的自相似( s e l f - s i m i l a r i t y ) 性问题。近年来的研究发现，t c p 的拥塞控 制也会产生具有短相关( s h o r l r a n g e d e p e n d e n c e ) 和长相关( 1 0 n g - m n g e d e p e n d e n c e ) 的 自相似数据流( s e l f - s i m i l a rt r a f f i c ) ( 可以用h u r s t 参数描述) ，而这一特性与更高层的应用或 协议无关。文献【9 】用t c p 拥塞控制的混沌本性( c h a o t i c n a t u r e ) 从另一侧面证明了这一观 点。网络流量自相似性反映了业务在所有( 或至少一个较大范围) 时间尺度上的统计相似 性，突出表现为突发( b u r s t ) ，没有明确的长度，我们不可能将它们平滑掉。 但是目前在t c p 拥塞控制机制研究中，我们大多使用泊松模型模拟网络通信量，当 业务源数目增加时突发性会被吸收，聚集业务将变得越来越平滑。就是说传统的网络模型 忽略了t c p 的拥塞控制所导致网络流量的自相似性。如果在新的拥塞控制算法的仿真中 或在网络排队性能分析中仍使用传统的网络模型，对于网络的突发性分析将会存在偏差。 第二、用户利益与网络整体性能的矛盾。在流量由小增大的过程中，开始的阶段用户 效率和网络性能( 如吞吐量指标) 都会随之增加，同时i p 层缓冲被充满、路由器队列变 长。如果流量进一步变大，缓冲溢出、队列延迟继续增加，拥塞发生，用户效率和网络性 能就会受到影响。所以一个好的拥塞控制算法在网络相对稳定后应能够保证链路的最优负 荷并满足用户的需求，即网络应该工作在某个点的附近，在这个点上网络运行状态最优。 第三、公平性指的是在发生拥塞时各源端( 或同一源端建立的不同t c p 连接或u d p 数据报) 能公平地共享同一网络资源( 如带宽、缓存等) 。处于相同级别的源端应该得到相同 数量的网络资源。产生不公平性的根本原因在于拥塞发生必然导致数据包丢失，而数据包 丢失会导致各数据流之间为争抢有限的网络资源发生竞争，争抢能力弱的数据流将受到更 0 拱十流量优化控制的t c p i p 拥塞控制研究 多损害。t c p 层上的公平性问题表现在两方面：面向连接的t c p 和无连接的u d p 在拥塞 发生时对拥塞指示的不同反应和处理，从而导致对网络资源的不公平使用问题；一些t c p 连接之间也存在公平性问题( c o m p e t i n g t c p ) 。产生问题的原因在于一些t c p 在拥塞前使 用了大窗1 ：3 尺寸，或者它们的r t t 较小，或者数据包比其它t c p 的大，这样导致它们也 会多占带宽。 1 5 本文的主要工作及内容 本文针对上述问题，基于t c p v e g a s 协议和r e m 设计了一种新的基于流量优化控制 的t c p i p 拥塞控制机制，并在网络模拟器n s ( n e t w o r ks i m u l a t o r ) 上对该算法进行了 详细的性能分析，实验结果表明该算法在t c p 友好性和灵敏性方面显示出令人满意的效 果。本文的研究内容组织如下： 第二章介绍网络上存在的两种流量控制机制，一种是端到端的流控制机制，另一种是 基于l p 层的流量控制机制，然后分析了两种流量控制机制在处理拥塞现象中存在的问题。 最后详细介绍了优化流量控制机制的发展过程、基本原理和处理拥塞问题时的优势。 第三章首先提出了一种基于流量优化控制的t c p i p 拥塞控制机制方案一o c c ( o p t i m i z a t i o nc o n g e s t i o nc o n t r 0 1 ) ，然后阐述了它的总体设计目标和算法目标。该算法分 为l p 层和发送端两部分，l p 层算法利用队列长度和优化理论估计网络拥塞程度，通过对 数据包的标记反馈到发送端；发送端算法根据被标记的数据包的个数估计i p 层拥塞程度并 调整发送速率。在o c c 方案中，通过i p 层算法和发送端算法的协同工作，兼顾了发送端 的发送速率和瓶颈链路的可用带宽，照顾了网络全局。0 c c 还使得各种数据流的能够友好 共存，并对它所涉及的网络区域的性能进行优化。 第四章介绍了对上述算法进行网络仿真实验与分析的结果。仿真实验在网络模拟器 n s 上进行，对算法进行了大量的仿真实验以评价算法多方面的性能，详尽分析了算法的 灵敏性，公平性及各种网络状态下算法的行为和性能，分析了算法的合理性和有效性。特 别地，在验证算法的公平性试验中，使用自相似流作为背景流模拟网络运行状态。仿真结 果表明，与t c p v e g a s 算法相比，提高了公平性和稳定性，能对网络拥塞状态的变化能 做出灵敏的反应，同时对协议内部和协议之间的公平性以及协议本身的可扩展性也有较好 的改善。 第五章研究了自相似网络通信量。首先讨论了用自相似流作为仿真试验背景流的必要 性及自相似的等价定义，然后用n s 模拟器实现了自相似流。根据自相似参数h 与丢包率 之间的正比关系，进一步改进i p 层算法的信息收集，并进行仿真试验进行验证。 山东师范大学砸士学位论文 第2 章优化流量控制机制 本章首先介绍网络上存在的两种流量控制机制，然后分析了两种流量控制机制在处理 拥塞现象中存在的问题。最后详细介绍了优化流量控制机制的基本原理、发展过程和处理 拥塞问题时的优势与不足。 2 1t c p ip 协议的流量控制机制 高速网络大量涌现、网络用户增加、新旧技术的并存，造成了网络中间节点处数据包 的到达速度和处理速度不匹配、链路速度不匹配等现象，使严重的拥塞问题逐渐暴露出来。 t c p 利用滑动窗口进行端到端的流量控制，当网络中发生拥塞时，发送方根据上述几个拥 塞控制算法对滑动窗口的大小进行调整，减少注入网络的流量，达到缓解拥塞的目的。l p 层的路由器作为连接的中间节点，一般采用简单的先来先服务调度算法和缓存满即丢弃的 缓存管理机制，在网络发生拥塞时所起的作用相对较小。 拥有流量控制机制对某种网络的畅通运行是十分重要的。在t c p i p 协议中存在两个 的控制问题：( 1 ) 互联网协议需要源主机和最终目的主机之间端到端的流控制。如：当一 台微机与一台大型服务器相互通信时，微机必须能够调节数据流的入速率，否则它的协议 缓冲很快就会溢出。t c p 协议就提供了这样的端到端的流控制以确保可靠的数据交付。( 2 ) 互联网的路由器和链路等网络的核心部件需要一个流量控制机制。i n t e r n e t 的迅速发展使 拥塞控制问题日益得到人们的重视，虽然传输控制协议( t c p ) 在拥塞控制中一直发挥着 至关重要的作用，但考虑到数据流所经过的端到端的通路是多条链路和路由器所组成的串 联系统，路由器是网络中的核心部件，是网络状态的更直接的感受者，为实现网络的更有 效的控制，路由器端也应采取相应的措施，把中间系统能够获知的网络状况并告知源主机， 以免它们发送的通信量超出自己的承受能力。因此，数据流的端到端的行为将最终受到它 所迸过的链路的状况和路由器的状况所决定。拥塞控制需要端系统和网络中间部件( 路由 器) 的相互配合。 2 1 1 t c p 的流控制方案 t c p 使用一个专门的滑动窗口机制来解决两个重要问题：传输效率和流量控制。t c p 的滑动窗口机制可以在收到确认信息之前发送多个数据报，使得网络处于忙碌状态。不仅 提高了整个网络的吞吐率，还令接收方在拥有容纳数据的足够缓冲空间之前对传输进行限 制。t c p 的滑动窗口机制可如图2 1 所示： 3456789 ljlj 图2 - 1t o p 的滑动窗口机制 数据包被编上序号，发送端对每个连接保留了三个指针。位于滑动窗口