（计算机应用技术专业论文）基于xcp协议的拥塞控制算法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 x c p 协议是针对高带宽时延乘积网络而提出的一种新协议。x c p 协议扩展 了e c n 显式拥塞指示机制，它通过在拥塞头携带控制信息极大地改善了英特网 的拥塞控制。路由器能通知发送端瓶颈链路的拥塞程度而不是网络是否拥塞， 发送端就可以根据网络的状态相应的增加和减少它的发送窗口。无论在传统 的网络环境中还是在高带宽时延乘积网络的环境中，x c p 比t c p 在效率性、公 平性以及稳定性方面表现得都更出色。 本文首先对t c p 协议存在的问题进行了阐述，随着每一流的带宽时延乘 积的增长，在不考虑排队方案的条件下，t c p 协议变得不稳定和效率低下。 接着对拥塞控制国内外研究现状进行了简单介绍。然后对x c p 协议的结构和 执行算法进行详细分析，并对协议做了相应仿真，仿真结果表明在高带宽时 延乘积网络中，x c p 协议比t c p 协议能更好的保持效率、公平性和稳定性。 然后，根据对x c p 协议的参数a 和卢进行的实验研究；发现a 对网络的利用 率影响较大，声对于清空路由器中的队列的时间有着明显的影响。参数都是 效率和稳定性之间的折衷，还有可以调节的范围。 针对x c p 的口参数在网络中流的个数变化明显以及链路带宽相差比较大 的网络环境中影响带宽利用率提高的问题，采用了一种自适应的改进算法，该 算法基于平均队列变化率来判断网络的稳定状态，并依此调整参数a 。运用 n s 2 仿真工具对使用改进算法后的网络的吞吐量、网络链路带宽利用率进行 分析，结果表明，该算法能有效提高网络带宽利用率，同时能保持网络的稳 定状态。 关键词：拥塞控制；x c p ；自适应算法：高带宽时延乘积 西南交通大学硕士研究生学位论文第1 i 页 a bs t r a c t e x p l i c i t c o n t r o l p r o t o c o l ( x c p ) i sn e w l yp r o p o s e d f o r h i g l l b a n d w i d t h - d e l a yp r o d u c tn e t w o r k s x c pa c h i e v e sas i g n i f i c a n ta d v a n c ei ni n t e r n e t c o n g e s t i o nc o n t r o lb yc a r r y i n gt h ec o n t r o li n f o r m a t i o ni nt h ec o n g e s t i o nh e a d e r a n dg e n e r a l i z i n gt h ee 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 np r o p o s a l ( e c n ) t h er o u t e r s c a ni n f o r mt h es e n d e ra b o u tt h ed e g r e eo fc o n g e s t i o na tt h eb o t t l e n e c ki n s t e a do f j u s tc o n g e s t i o no rn o t t h i sa 1 1 o w ss e n d e r st oi n c r e a s eo rd e c r e a s et h e i rs e n d i n g w i n d o w sr e s p o n s i v e l ya c c o r d i n gt os t a t u so fn e t w o r k x c po u t p e r f o r m st c pb o t h i nt r a d i t i o n a le n v i r o n m e n t sa n di nh i g hb a n d w i d t h d e l a yp r o d u c tn e t w o r k s ，a n d f u r t h e rr e m a i n se f f i c i e n t ，f a i r , a n ds t a b l e f i r s to fa l l ，t h et h e s i si n t r o d u c e st h ep r o b l e m so ft c pb r i e f l y w i t ht h e p e r - f l o wp r o d u c to fb a n d w i d t ha n dl a t e n c yi n c r e a s e s ，t c pb e c o m e si n e f f i c i e n ta n d p r o n et oi n s t a b i l i t y , r e g a r d l e s so ft h eq u e u i n gs c h e m e a n dt h e ni n t r o d u c et h e r e s e a c hs i t u a t i o no fc o n g e s t i o nc o n t r o la th o m ea n da b r o a d t h e nt h et h e s i s a n a l y s i s e st h es t r u c t u r ea n dt h ep e r f o r m a n c ea l g o r i t h mt ot h ex c pp r o t o c 0 1 t h e r e s u l t so fs i m u l a t i o nd e m o n s t r a t et h a tt h ee x p l i c i tc o n t r o lp r o t o c o l ( x c p ) o u t p e r f o r m s t c pa n dr e m a i n se f f i c i e n t ，f a i r , a n ds t a b l ei nt h e l a r g e b a n d w i d t h d e l a yp r o d u c t ( b d p ) n e t w o r k s a f t e r w a r d s ，b a s e do nt h er e s e a r c ho f t h ep a r a m e t e ro fx c p , w ed i s c o v e rt h a tp a r a m e t e r 口i n f e c t i n gt h en e t w o r k u t i l i z a t i o no b v i o u s l y , p a r a m e t e rf l i n f e c t i n gt h et i m eo fe m p t i n gq u e u ei nt h e r o u t e r a l lt h ep a r a m e t e r sa r et h et r a d e - o f fb e t w e e no fe f f i c i e n c ya n ds t a b i l i t y , w h i c hs t i l lh a v er e g u l a t i n gr a n g e w i t ht h ec h a n g e dd a t as t r e a mn u m b e r sa n dv a r i o u sl i n ki nt h en e t w o r k ，t h e p a r a m e t e r ao fx c pl i m i t st h eu s eo fb a n d w i d t h s o ，a d a p t i v ea l g o r i t h mh a db e e n b r o u g h tf o r w a r d i tc a na d j u s taa c c o r d i n gt ot h es t a t eo ft h en e t w o r kw i t c hc a n b e j u d g e db yt h ec h a n g e si nt h ea v e r a g eo fq u e u e s i m u l a t i o nr e s u l t sp r o v et h a tt h e s c h e m ei se f f e c t i v e u s i n gn s 2t oa n a l y s et h en e t w o r k st h r o u g h p u ta n db a n d w i d t h u t i l i z a t i o no ft h en e t w o r ko ft h ei m p r o v e da l g o r i t h m s ，t h es i m u l a t i o nr e s u l t ss h o w t h a t ，a d a p t i v ea l g o r i t h mc a ni m p r o v eb a n d w i d t hu t i l i z a t i o no f t h en e t w o r k ，a n d k e e ps t a b i l i t yn e t w o r k st h r o u g h p u t 西南交通大学硕士研究生学位论文第1 ii 页 k e yw o r d s ：c o n g e s t i o nc o n t r o l ；e x p l i c i tc o n t r o lp r o t o c o l ；a d a p t i v ea l g o r i t h m ； l a r g eb a n d w i d t h d e l a yp r o d u c t 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将 本论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密舀使用本授权书。 ( 请在以上方框内打“4 ) 学位论文作者签名：釜畏 日期：如g 军i 目i 冬d 指导老师签名：么李迎 黾强：咖话6 b 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工 作所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和 集体，均已在文中作了明确的说明。本人完全意识到本声明的法律结果由 本人承担。 本学位论文的主要创新点如下： 对x c p 协议的缺陷进行了相应分析，发现当系统处于较稳定的状况并 且链路有空闲带宽时，适当提高口参数的取值，可以提高带宽利用率，同 时也能保持链路的稳定性。于是采用了基于平均队列变化率来判断网络稳 定状态的自适应算法动态调整口参数的值。并且对该算法做了仿真分析， 仿真结果表明不仅提高了链路的网络利用率，而且保持了链路的稳定性。 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 问题的提出 随着计算机和通信技术的发展，i n t e r n e t 网络在过去几年中迅 猛发展，导致拥塞问题越来越严重，现有的拥塞控制协议远远无法 满足当前与未来的需要，成为制约网络发展和应用的一个瓶颈。目 前主要有如下问题： ( 1 ) 未来高的带宽时延乘积网络( h i g hb a n d w id t hd e l a y p r o d u c tn e t w o r k s ) 的新要求； ( 2 ) 网络中远距离传输超大数据集( p 比特级，1p = i0 0 万g b ) 的新要求，目前的t c p 拥塞控制协议根本无法在网络计算中应用； ( 3 ) 无线链路的广泛接入； ( 4 ) i n t e r n e t 业务的多元化、多种非t c p 友好流的激增、用 户数量的剧增等； ( 5 ) 满足o o s 的需要。这方面主要围绕i n t s e r v r s v pm o d e l ， d i f f s e r vm o d e l ，m p l s 和t r a f f i ce n g i n e e r i n g 进行。同时，随 着网络复杂性不断增加，i n t e r n e t 能否持续稳定发展已成为令人关 注的问题。 1 2t c p 拥塞控制协议算法存在的问题 t c p 是目前在i n t e r n e t 中使用最广泛的传输协议根据m c i 的 统计，总字节数的9 5 和总报文数的9 0 使用t c p 传输近年来t c p 中采用了很多新的算法，包括慢启动( s lo ws t a r t ) 、拥塞避免、快速 重传( f a s tr e t r a n s m i t ) 、快速恢复( f a s tr e c o v e r y ) 、选择性应答 ( s a c k ) 等，大大提高了网络传输的性能尽管网络层也试图管理拥塞 控制，但是绝大部分繁重的任务是由t c p 来完成的，t c p 中使用的 拥塞控制算法已经成为保证i n t e r n e t 稳定性的重要因素。 t c p 算法的出现已经有2 5 年历史了，它是针对当时带宽时延乘 积较小的网络设计的，随着高带宽( 如光纤链路) 和高延迟( 如卫 星链路) 网络越来越普遍的应用，t c p 算法体现出越来越多的问题。 主要体现在如下几个方面： t c p 算法是建立在假定超时是由拥塞引起的基础上的，凶为由于 西南交通大学硕士研究生学位论文第2 页 传输错误导致的分组丢失的情况很少出现。虽然这个假设具有一定 的合理性，但是把丢包作为拥塞发生的信号并不是很好，特别是在 出错率比较高的无线网络中，这种假设并不合理。 在高带宽网络t c p 算法的效率比较低。假设在一个10 9 b p s 的网 络中，最大包是10 5 b it ，r t t 为1o o m s ，需要10 4 才能占据整个带宽。 实验和理论推导都证明随着带宽时延乘积的增加，不管是用什么排 队模式，如r e d ，r e m 2 1 ，p i 引，a v q 4 1 等算法都使t c p 变得越来越低 效和不稳定。此外， k a t a b ia n d b l a k e1 5 j 表示当链路容量变得很 大时( 如g b i t 链路) ，自适应的a v q 6 j 也会变得不稳定。 t c p 的公平性也存在着问题，主要表现在两方面： 一是拥塞响应的t c p 流和非拥塞响应的u d p 流之间资源享用不 公平； 二是t c p 流之间资源享用的不公平。不同的窗口大小、r t t 值及 数据包的尺寸都会影响t c p 流对带宽的占用。窗口较大，或者r t t 较小，或者数据包较大的流往往能占用更多的带宽。 为了适应这些发展，需要极大的扩展现有的协议或者用一个全 新的协议替换现有的协议，因此当前的研究一部分集中在修改现有 的t c p 协议参数以满足新的需求，一部分旨在提出新的协议以满足 未来的综合网络环境和q o s 等新的应用需求。同时随着网络复杂性 的不断增加，i n t e r n e t 能否持续稳定地发展也便成为一个令人关注 的问题，良好的工程环境与仿真实验固然必不可少，但也需要更为系 统的分析与设计手段，因此国外有部分原来进行控制理论和非线性 动力学的研究人员也相继转而进行网络的拥塞控制研究，并且在这 方面取得很大的成绩。 根据t c p 存在的问题和高带宽时延乘积网络的特点，美国麻省 理工大学的d i n ak a t a b i 提出了一种新的i n t e r n e t 拥塞控制框架， 该协议称为x c p ( e x p l i c i tc o n t r o lp r o t o c 0 1 ) ，显式控制协议【7 j 。 x c p 是一种联合端系统和路由器共同协作的协议，将拥塞控制从带宽 分配策略中解耦。实验证明x c p 比t c p 在高带宽时延乘积网络的环 境中有着更好的性能，在效率性、公平性、灵活性以及稳定性方面 表现都非常出色。甚至是在传统的环境中，x c p 也能提高网络带宽的 利用率，减小队列长度，使丢包的情况降至极低。 西南交通大学硕士研究生学位论文第3 页 1 3 国内外研究现状 1 t c p 拥塞控制协议算法最新进展 端系统拥塞控制协议的改进集中在协议参数的修改上，并考虑 加入一些与网络层配合的新机制，同时密切关注i n t e r n e t 流的自相 似特性和混沌特性的研究与建模，利用中间节点反馈的一些信息进 行发送速率的调节，如e c n 机制和链路影子价格机制的研究与应用 等。以往的拥塞控制研究基本上都是基于主观的方法，缺乏严谨科 学理论的指导，因此国内外有部分原来从事控制理论和非线性动力 学工作的研究人员也相继转而进行网络的拥塞控制研究，并且在这 方面取得很大的成绩，提出了一些严格的理论模型，其中突出的有 l o w 等基于优化理论提出了t c p a q m 对偶性模型1 8 9 l ；p a g a n in i 等 利用多变量鲁棒控制理论【1 ，设计了个新的拥塞控制系统，它对 于任意网络拓扑、容量及时延能保持局部稳定性；m is r a 等提出了 t c p a q m 的微分方程f l u i d f l o w 模型1 1 l 】。 2 慢启动方面的改进 慢启动有两个问题： ( 1 ) 由于它从发送一个报文段开始，因此要经过多个r t t 才能 达到一个最优的流量点，这对小流量但链路延迟又较大的t c p 流很 不利。 ( 2 ) 由于发送端并不了解可利用的网络资源，采用指数方式增 长经常错误地引导发送端过快过多地发送突发报文段，从而引起瓶 颈链路的拥塞。针对第一个问题，有人提出采用大的初始窗口和t c p 快速启动等方法。目前公认较好的初始化窗口为m in ( 4xm s s ，m a x ( 2 m s s ，43 8 0b y t e s ) ) ，其中m s s ( m a xi m u ms e g m e n t s iz e ) 为网络能 传输的最大数据单元。这样就缩减了到达接收方报告窗口所需的时 间。第二个问题中，采用估算的慢启动阂值s s t h r e s h 来取代默认设 置，h o e 建议使用p a c k e t p a l r 算法和测量r t t 为s s t h r e s h 估计合 适的值i l 引，以此来适时结束慢启动阶段。但由于受到各方面干扰， 估算合理的s s t h r e s h 值并不容易，因此该方法的效果是有限的。文 献 13 提出的s m o o t h s t a r t 较为平滑地从慢启动过渡到拥塞避免， 减少报文段丢失和突发的通信量，从而提高t c p 拥塞控制的性能。 文献 14 综述t c p 拥塞控制采用大初始窗u 时的优点和弊端。 西南交通大学硕士研究生学位论文第4 页 1 ) t c p w e s t w o o d ( t c p w ) 协议 其关键革新思想是在t c p 发送端通过检测返回的a c k 速率来持 续测量有效带宽，这是一个与t c p r e n o 友好的、在发送端自适应修 改拥塞窗口的拥塞控制算法，与在发生拥塞时盲目执行乘性减少拥 塞窗口算法的t c pr e n o 相比，当拥塞发生时，t c p w 通过执行端到端 可用带宽的计算与估计来适应性地设置一个与发生拥塞时有效带宽 一致的慢启动阈值和拥塞窗口，这里把这种机制称为更快恢复 ( f a s t e r r e c o v e r y ) 1 1 5 j 。t c p w 完全遵从端到端的t c p 协议设计原则， 并对随机丢包不太敏感。而t c pr e n o 却对随机丢包和拥塞丢包十分 敏感，因而不能像t c p w 一样可以正确地区分随机丢包和拥塞丢包。 实验观察到使用t c p w 可使吞吐量改进5 0 ，表明可以显著提高吞吐 量和公平性，在高速网络、无线和有线混合网络中极其有效。另外， t c p w 的执行也无须专门的链路层协议支持。 2 )h i g h s p e e dt c p ( h s t c p ) 协议 它是f l o y ds 于2 0 0 3 年2 月递交给i e t f 的一个面对高速链路 修正的t c p 拥塞控制新算法，旨在改善带有大拥塞窗口的t c p 连接 性能，它被设计成在拥塞事件发生率十分低的环境下使用，而传统 的t c p 是在丢包率至少为1 0 。3 的环境下正常工作1 1 6 j 。h s t c p 使用变 动的拥塞窗口调节参数，保证在不同拥塞程度变化的网络中也能正 常工作，它给出平均拥塞窗口w 和稳定丢包率p 之间的新关系，h s t c p 的响应函数需要增加3 个参数：l o w w in d o w ，h ig h w in d o w ， h ig h p ，若当的拥塞窗口小于l o w w in d o w 时，h s t c p 和传统的t c p 一样；若当前拥塞窗口大于l o w w i n d o w 时，h s t c p 则使用自己的响 应函数，n ig h - w in d o w 和h ig h - p 是用来作为h s t c p 响应函数的上限， h i g h - p 的设置要求h s t c p 有一个大小为h i g h w i n d o w 的平均拥塞窗 口，h s t c p 设置了新的a i m d 参数。这些参数依据当前的c w n d ( 下式 记为w ) 进行调整，在拥塞避免阶段，可用式( 卜1 ) 和( 1 - 2 ) 表达： a c k ：w w + a ( w ) w ，( 1 一1 ) 拥塞：w w b ( w ) w( 卜2 ) 3 )f a s tt c p 协议 它是c h e n gj ，d a v i dxw 和s t e v e vhl 等人在2 0 0 2 年和 2 0 0 3 年发展起来的，并于2 0 0 4 年3 月在香港召丌的i e e ei n f o c o m 西南交通大学硕士研究生学位论文第5 页 会议上发表的针对高速网络的一个新的t c p 拥塞控制算法f 1 7 l 。f a s t t c p 是在l o w 等基于优化理论提出的对偶性模型理论基础上设计的 一个新算法，其设计思想十分简单：为保持稳定性，f a s tt c p 通过 设置一个稳定的均衡b a s e r t t 目标值，源端计算每个r t t 大小，然 后依据这个值成比例地缩减其响应，拥塞窗口调整规则为r t t ： w w b a _ s e r t t + 口，可见若上一个包的r t t 比b a s e r t t 大，则会降 r t t 低拥塞窗口( 即可认为网络性能在下降，此时需降低发送速率) ，反 之则增加。另外，有模拟表明接收端的接收波动与网络抖动一致， 能否应用这种一致性让接收端具有主动反馈功能值得考虑。而且， 考虑t c p 发送窗口不是以线性增长而是以分段速率递进以尝试寻找 最优速率，这是提到的较新的值得研究的思想。 3 x c p ( e x p l i c i tc o n t r o lp r o t o c 0 1 ) 协议 针对目前基于窗口的t c p 拥塞控制机制的不足，最近m i t 的 k a t a b id ，r o h r sc 和u cb e r k e l e y 的h a n d l e ym 共同提出一种新的 互联网拥塞控制机制x c p 。x c p 协议极大地扩展了e c n 和c s f q ( c o r e s t a t e l e s sf a i rq u e u in g ，核心无状态公平排队算法) 【1 8 l 。 x c p 在中间节点引入两个控制器：拥塞控制器( 又叫效率控制器， e f f i c i e n c yc o n t r o l l e r ，e c ) 和公平控制器( f a i r n e s sc o n t r o l l e r ， f c ) ，利用解耦控制，其机制使中间节点的反馈更为直接清楚。在端 点数据包头包含当前的c w n d ( hc w n d ) ，r t t 估计( ht r r ) 和 f e e d b a c k ( h f e e d b a c k ) 3 个域，发送端使用h f e e d b a c k 域请求希望 得到拥塞窗口调整的变化量么，中间节点修改f e e d b a c k 域的值，当 一个新a c k 到达时，若反馈值为正，则发送端增大c w n d ，若为负则 减小，具体为c w n d = m a x ( c w n d + h f e e d b a c k ，s ) ( s 为一个包的大 小) 。拥塞控制器使用m i m d ( 乘性增加或乘性减少) 来做到快速响应 ( f a s t r e s p o n s e ，g r a b r e l e a s el a r g eb a n d w i d t ho u i c k l y ) ，其目 标是使输入流与链路容量、输出队列相匹配，拥塞控制器将各个单 一的流视为一个整体来对待，并且计算聚集流的反馈值么，么与可 用的空闲带宽、负队列长度成比例，具体为 = a d 。曙* s p a r e 一声木q 舭。，d 是平均r t t 。通过稳定性分析可知，口， 多为常量，无须进行参数调节。计算结果将传送给公平控制器。公 西南交通大学硕士研究生学位论文第6 页 平控制器在拥塞控制器之后接着执行，并使用a i m d 算法分配 f e e d b a c k 给各个包以达到公平性，公平控制器此时区分对待每个单 一流，当网络有空闲带宽时( 即么 o ) ，则将带宽平均分配给每个流； 当网络发生拥塞( 即么 0 ) 时则要求各个单一流成比例地减少其当 前发送速率。计算后的结果填入h _ e e d b a c k 域。在这些过程中，中 间节点无须保存每个流的状态。实验表明，与传统的t c p 拥塞控制 机制相比，x c p 具有链路利用效率高、公平性好、可扩展性强、排队 时延小的优点，并且路由器的开销也非常小。 传统的t c p 是采用a i m d 规则，试图通过对包级别的控制达到流 控级的目标。从上面的分析可以看到前即关于端节点协议算法方面 的研究主要是在慢启动规则以及拥塞窗口的调整规则上，那么研究 的主要集中点便在于如何正确及时的获得反馈信息以及在得到反馈 信息的基础上如何正确及时的调整拥塞窗口。而第三种算法，即x c p 协议则是一种全新的协议。它引入一个新的概念解耦效率控制和公 平控制，即将拥塞控制从带宽分配策略中分离出来。这能够更为高 效率的利用网络资源，并能够更为灵活的执行不同的带宽分配策略。 x c p 协议增加了包的头部信息，则可以显式的、精确的完整的反馈网 络的拥塞状况。x c p 与其它的协议相比较获得的反馈信息更直接，更 准确，它具有很好的鲁棒性，在高带宽时延乘积环境下有很好的性 能表现。因此我们认为x c p 是一种设计合理，考虑较全面并且可行 的协议，是未来高带宽时延乘积网络协议中的强有力竞争者，因此 我们选择x c p 协议做进一步研究。 1 4 本文研究的主要内容和论文安排 l 、本文主要对x c p 协议进行了研究，并基于n s 2 平台进行仿真。 主要内容和方法如下： 1 ) 对拥塞控制协议x c p ( e x p licitc o n t r o lp r o t o c 0 1 ) 进行研 究。在分析传统t c p 的拥塞控制机制不足的基础上，对x c p 协议的 进行了剖析，研究基于x c p 协议实现拥塞控制的基本原理。同时在 n s 2 下编写脚本实现仿真，构建网络拓扑结构，通过链路带宽利用效 率、收敛至公平性时间快慢，丢包率几个指标，以说明x c p 协议 在拥塞控制性能上比传统的t c p 协议更优越。 2 ) 研究x c p 协议的缺陷，采用基于平均队列变化率的自适应算 西南交通大学硕士研究生学位论文第7 页 法，通过判断网络稳定状态动态地调整参数口，最后通过仿真结果验 证该算法在保持网络稳定的同时进一步提高了网络的带宽利用率。 2 、本论文从x c p 协议的实现原理研究出发，对x c p 协议路由器 参数存在的缺陷进行了研究，着重分析了在网络稳定和空闲带宽比 较大的情况下提高网络的带宽利用率的具体算法。采用了一种自适 应算法，可以针对网络的具体情况自动的调整路由器的参数，提高 网络的带宽利用率，并在n s 2 平台上对采用改进后的算法与采用标 准算法的网络带宽利用率进行了比较。其安排如下： 本文的第2 章首先对x c p 协议进行了分析，通过分析可以得知 x c p 协议无论在传统的还是在具有高带宽时延乘积的环境下，x c p 的 性能都优于t c p 。此外，它还达到了公平的带宽分配、很高的链路利 用率、极短的排队队长( 极低的排队时延) 和较小的丢包率。 在第3 章中，对在n s 2 下实现的x c p 协议分为发送端，接收端 和路由器代码分别做了深入分析。在此基础上，通过编写相应的脚 本代码对x c p 协议进行了仿真实验。仿真结果显示x c p 协议在提高 链路利用率和保持较小的平均队列值以及极低的丢包率都有良好的 表现。 本文的第4 章通过对x c p 协议路由器参数的具体分析，采用了 一种自适应算法，在网络稳定和有大量空闲带宽的情况下适当的提 高参数值可以提高网络链路的带宽利用率。 本文的第5 章简单介绍了仿真的基本条件，然后从带宽利用率 和吞吐量两个指标对第4 章中改进的算法进行了仿真与分析比较。 最后，总结了全文并展望后续的研究工作。 西南交通大学硕士研究生学位论文第8 页 第2 章x c p 协议框架结构分析 针对基于窗口的t c p 拥塞控制机制的不足，m i t 的d k a t a b i 、 c r o h r s 和u cb e r k e le y 的m h a n d le y 于2 0 0 2 年共同提出了一种新 的互联网拥塞控制机制x c p ( e x p l i c i tc o n t r o lp r o t o c 0 1 ) ，并且于 2 0 0 4 年10 月作为r f c 草案发布。x c p 通过网络中的路由器给发送端 主机显式的反馈来实现拥塞控制。实验证明，无论在传统的还是在 具有高带宽时延乘积的环境下，x c p 的性能都优于t c p 。此外，它还 达到了公平的带宽分配、很高的链路利用率、极短的排队队长和极 低的丢包率。 2 1 t c p - r e n o 拥塞控制协议的稳定性分析 本小节研究当前i n t e r n e t 上广泛采用的拥塞控制协议 t c p r e n o 的动态行为，采用流体流近似对t c p - r e n o 拥塞控制机制建 模，并基于该模型分析t c p - r e n o 的拥塞控制机制【1 9 】。 2 1 1 建立模型 采用了一个延迟微分方程模型用来描述t c p r e n o 拥塞控制算 法。考虑一个具有多个源通过一个路由器连接到多个相应目的网络， 模型中用到的参数定义如下： n ：数据源数( 即连接数) ：c ：路由器输出li n k ( 链路) 的容量； 彬o ) ：时刻t 时第i 个连接( f l o w ) 的拥塞窗口；x ；( f ) ：时刻t 时 第i 个连接( f l o w ) 的发送速率；ro ) ：第i 个连接( f l o w ) 的环回时 间( r o u n d t r i pt i m e ，r t t ) ；o ) ：时刻t 时路由器li n k ( 链路) 的 丢包概率；z o ) ：时刻t 时路由器总的包到达速率。 假设网络中n 个源使用相同的t c p - r e n o 拥塞控制算法，由于 t c p 慢启动阶段持续时间较短，快速重传后的恢复阶段对网络连接 吞吐量的影响不明显，建立模型主要考虑平衡点附近“拥塞避免” 阶段，不考虑通告窗口的影响，即对t c p - r e n o 的a i m d ( 和式增加积 式减少) 算法进行建模，a i m d 算法描述如式( 2 1 ) ： 西南交通大学硕士研究生学位论文第9 页 彬+ 。( f ) = 啪) + 志，矿行。妇 ( 2 - 1 ) 丢， 砌妇 在周期t 中，源以x ；( f ) 速率发送数据包并以近似相同的速率接 收反馈来的肯定或否定确认，假设每个包都被确认。这样，平均来 说，源i 单位时间收到x ；( t ) ( 1 一乞0 ) ) 个肯定确认，每个确认增加 窗1 31 彬o ) ；收到x ；( f ) 。o ) 个否定确认( 即丢包) ，每个确认减少 窗1 ：3 去彬o ) ，则t c p r e n o 拥塞避免阶段的模型为式( 2 2 ) ： 旁r o ) = 三二垒- = 兰铲一i 1 x i o - t ) p r ) 彬( f ) ( 2 - 2 ) 由于x ；o ) 近似等于彬( t ) r ；o ) ，则公式( 2 2 ) 可变换为公式 ( 2 3 )： x 。i ( f ) ；x , ( t - t ) z ( _ 1 ；- _ e j ( t - - t ) 一) 一! x ，o 一丁) ( f r ) x f o ) ( 2 3 ) “ g o ) 置o ) 2 “ 7、”7 路由器l i n k ( 链路) 的丢包概率o ) 是包到达速率的函数，即式 ( 2 - 4 ) ( f ) = f ( z ( t 一丁) ) ( 2 - 4 ) 而z ( t ) 为链路上所有连接的包到达率之和，为式( 2 5 ) z o ) = x ，o ) ( 2 5 ) 2 1 2 稳定性分析 为了简化分析，假设网络中n 个源使用的r t t 相同，观察周期 t 为一个r t t 时间，不考虑延迟的影响，认为包丢失与收到相应反 馈的时刻相同，则( 2 3 ) 式可改写成式( 2 6 ) ： 西南交通大学硕士研究生学位论文第1o 页 x i ( t ) = 半m ( 2 - 6 ) 为了确定式( 2 - 6 ) 给出的拥塞控制器的稳定性，我们首先将它在平 衡点附近线性化。由( 9 - 6 ) 式，令xr o ) = 0 ，可求出x ，( f ) 在平衡点 的值： ； 1 af 2 r o ( 2 - 7 ) 这里， r 。和分别是平衡时的 r t t 和丢包率。定义 积；x j x ；，& 号一。，则式( 2 5 ) 的拥塞控制算法的线性化形式为 式( 2 - 8 ) ： 6 i 一。j 鹕一嗉+ 粒曲 浯8 ， 由于丢包概率的函数形式一般相当复杂，为了简化分析，我们假设 ，( z o ) ) 具有如式( 2 - 9 ) ： z c ，( z ) = m a x ( 0 ，孚) ( 2 _ 9 ) 这个形式可看成是丢包概率的流体流近似，即如果包到达速率低于 链路的容量，则丢包概率为零；否则丢包概率为超过部分的一定比 率。定义配= z z 。，综合( 2 4 ) ，( 2 - 5 ) ，( 2 9 ) 式，在平衡点附 近有： 踮丢弘。，( 2 - 1 0 ) 在平衡点，可设各连接的速率为x 一，。c n ，利用平衡式( 2 7 ) 的关 系与( 2 一l0 ) 式，可将( 2 8 ) 式整理为： 西南交通大学硕士研究生学位论文第11 页 6 x i + k 1 d y f + k 2 a y f ( f r o ) = 0 其中：k 。：。j ；，k ：委i ；+ ! _ ( 2 11 ) 么 r 0 2x 由h a y e s 引理【2 们，如果下列条件之一满足，则描述t c p - r e n o 动态性的 线性化泛函微分方程( 2 1 1 ) 稳定： 条件( 1 ) k 1 2 k 2 ； 条件( 2 ) k 1 k 2 且k 2 r o 对条件( 1 ) ，如要满足，则三1 尺；j ，( 2 e o - 1 ) 1 ，至少必须。丢，这显然 不现实，因为这意味着要求至少一半的包在路由器上被丢弃。 对条件( 2 ) ，可整理为： 导r 。 2 ox fr o 1 ，+ 要i ；r ； 、 二 而前面的平衡公式( 2 - 7 ) 可变成： 1 2 ( 1 - - e o ) = ( 万c 民) 2 ( 2 - 1 3 ) ( 2 一1 2 ) 如果设c n 为一常数，并增加r t t ，则由( 2 一l2 ) ，显然占。必定减小。 这样，对大的r t t ，n - - j - 近似地令占o = 0 ，从而由( 2 1 2 ) 可得到下列稳 定条件： 丙c r 。 0 ，每个数据流的吞吐量增加相同的值； 如果m 0 ，每个数据流减少的数值与他当前它吞吐量成正 比。 采用这种策略只要聚合反馈值不为零，就可以确保持续的收敛 到公平状态。当利用率接近最优即西0 的时候，为了避免出现收敛 失速的情况，因此引入了带宽重洗概念。在每一个平均r t t 内，至 少1o 的数据流量要根据a i m d 策略进行重新分配，10 的选择是权衡 了收敛到公平的时间和对已经接近最优利用的系统带来的扰动做出 的。对带宽同时的分配和去配保证了总的数据率不改变，也使得每 一个流的吞吐量逐渐接近自己的合理份额。重洗部分流计算公式如 下： h = m a x ( o ，y y h ) ( 2 16 ) 这里y 为输入流的总速率，) ，为常数，值设为0 1 。 反馈的计算：公平控制器的带宽分配需要为每个包分别的计算 反馈值 西南交通大学硕士研究生学位论文第17 页 ( 2 17 ) h f e e d b a c k i 为第i 个包的反馈值，p ，为正反馈，n 。为负反馈。 p i 咱专 ”。s t ( 2 18 ) 根据式： | i l + m a x ( 妒，o ) 。壹p ， + m a x ( 一如) 。壹咒。( 2 1 9 ) 亭口：垒二三翌兰型螋 亭。； 亏，2 i i 一 毛2 詈 h + m a x ( 一，0 ) ( 2 - 2 0 ) 公平控制器在控制周期的开始获得正负反馈的总和，然后逐步 将其分配，直到达到目标j i l + m a x ( 妒，0 ) 和h + m a x ( 一妒，o ) ，这样可以限 制聚集流的分配错误并且可以和效率控制器紧密协同工作。 虽然公平控制器使用的是a i m d 法则，它比t c p 能更快的收敛至 公平。t c p 收敛至公平是通过一系列的和式增加和乘式减少。但是 t c p 中的乘式减少是与丢包相关的，丢包是少数事件。而x c p 的乘 式减少与丢包是解耦的，在每个平均r t t 计算一次，因此收敛速度 更快。 2 5x c p 协议基于价格框架的分析 基于价格的网络框架主要有s u m n e t 和m a x n e t 两种网络结构。 s u m n e t 和m a x n e t 是两种不同的拥塞控制体系结构。s u m n e t 体系结 构使用的是e n d - t o - e n d 路径中所有链路的累计信息控制源端的速 率。m a x n e t 体系结构使用的是e n d t o e n d 路径中拥塞最严重的瓶颈 链路的信息控制源端的速率。m a x n e t 对于一般的有不同需求函数的 的源端的网络可以达到最大最小公平速率分配，并且不需要链路中 维持每个流的状态。在拥塞控制中广泛的使用宏观经济理论和控制 西南交通大学硕士研究生学位论文第18 页 系统理论。一般的，源端和链路的过程描述如下： s o u r c e i ：r j ( f + 1 ) = d ( s ( f ) ) l i n k l ：d ，( f - i - 1 ) = g ( y ，( f ) ，d ，( f ) ) ( 2 - 21 ) ( 2 - 2 2 ) r f ( t ) 是源i 在时间t 的速率，s f ( t ) 是与源i 相关网络拥塞 信号，d ，( t ) 是由链路1 生成的拥塞信号，y ，( t ) 是链路1 的聚集 流的到达速率。源端的发送速率由其需求函数确定，d 。( s ；( t ) ) 是基 于拥塞反馈s ；( t ) 的，每个需求函数d 。与一个效用函数u 。相关联， 两者关系为d 。= u f 。链路通过拥塞算法g ( y ，( t ) ，d ，( t ) ) 设置拥塞价格 d ，( t ) 从而控制需求。与源端i 相关的拥塞信号s ；( t ) 是使用 e n d - t o e n d 通信链路中每个链路的拥塞价格d ，( t ) 计算的。在目前 的i n t e r n e t 中，如r e m 算法，是典型的s u m n e t 结构，拥塞 控制的总价格是e n d t o e n d 链路中拥塞价格的 和： s ；vd ，( f ) ( 2 2 3 ) “口 b d n m e c t 止l i i 厶二衄a d 胆埔 图2 - 4 为单源系统的s u m n e t 结构示意图。目前i n t e r n e t 使用使用 的是丢包作为拥塞信号，每个链路j 在时间t 以平均速率m ，( t ) 随 机的生成拥塞信号( 丢包或者是标记包) ，在目前的i n t e r n e t 中， 通告拥塞的速率即为链路价格d ，( t ) = i l l ，( t ) 。m ( t ) 是给定n 个瓶颈 链路的e n d - t o - e n d 链路的源端收到的