（通信与信息系统专业论文）端到端拥塞控制的强制实施及多流控制器.pdf

摘要 厂、 ，一、0 端到端拥塞控制机制t c p 是i n t e m e t 鲁棒性的一个极端重要的因素，但是t c p 得以成立的一个基本假设是用户自觉地使用拥塞控制算法。今天的i n t e m e t 也经 成长为一个面向大众的信息服务平台，期望这里的每一个用户都自觉使用端到 端拥塞控制显然已经不再现实；同样的，出于各种不同的目的，大量网络应用 软件丌发商都自觉不自觉地在他们开发的i n t e m e t 应用中绕过拥塞控制算法，诸 如在i n t e m e t 上不断涌现的分组语音，分组视频等基于u d p 的应用。所有这些 应用由于没有搠塞避免算法或者没有正确地实现拥塞避免算法会使得i n t e m e t 又很快面临拥塞崩溃的危险【l 】。 解决这个问题包括两个方面。首先，需要在路由器实现一种鼓励使用端到 端捌摩控制的机制。天于这一点，f l o y e d 已经在文献【2 】中明确指出了端到端拥 塞控制对于防止网络崩溃的极端重要性，指出需要在路由器实现一种鼓励使用 端到端拥塞控制的机制，这种机制能够识别并惩罚非t c p 友好流，并保护t c p 友好流。其次，为了在i n t e m e t 稳定运行的前提下使得连续流业务也能够在i n t e m e t t x ,， l 大j 规模门：展，需要找到种适合连续流业务的棚塞控制机制：y 本文的研究针对这两个方面展开。针对第一个方面，本文耆先提出了垃圾 桶算法，这个算法能够对速率超过它应该得到的带宽的流进行识别和惩罚针 对第二：个方面，本文提出了一种新的适合连续流业务的传输机制c t f r c 。最后， 在垃圾桶算法的基础上，本文提出了多流控制器，它能够用于多流的相互关系 的控制、流速率测量以及流数目测量等方面。 本文的主要贡献如下： 1 本文提出了一种实用的无状态惩罚算法垃圾桶算法，这个算法能够 对速率超过它应该得到的带宽的流进行识别和惩罚，从而强制经过同 个链路的各个流公平的共享带宽在垃圾桶算法的基础上，提出了垃圾 桶算法与c h o k e 联合使用的的方法。仿真和理论分析证明了这个算法 的可行性。 2 本文提出了双友好机制的框架，在这种框架下：连续流业务有权获得与 7 f c p 平均速率一样发送的发送速率，但是由于连续流本身的特性所限， 它无法完全使用它应该得到的发送速率，那么连续流业务就应该有权根 据它应浚享受但是又没有能够享受的带宽从网络要求获得其他服务质量 j ， 的优惠。( 在t f r c 和r e d 的基础上，本文给出了一种实现这种框架的具 体方法- - c t f r c ，这个机制通过类似t f r c 的终端协议来保证t c p 友好 性，通过选择适当的优惠函数来标记连续流的带宽使用情况，并通过网 络对不同优惠值分组的不同丢失特征来保证连续流的传送质量。仿真表 明这个机制能在刁i 伤害t c p 性能的前提下，明显改善连续流所得到的服 叫 务质量。 0 3 本文提出了多流控制器的概念，多流控制器按照某种目标同时对多个 流之间的关系进行约束，本文给出一种基于随机碰撞的多流控制器的 实现方式。这种多流控制器能够识别汇聚流中的最大速率流并把它从 汇聚流中分离出来，它可以用于汇聚流特征的测量、非拥塞响应流的 惩罚等多个领域。本文分析了静态条件下的多流控制器数学模型，给 出了有限记忆长度多流控制器工作特性的精确描述和无限记忆长度下 多流控制器i ：作特性的极限形式，数值计算了精确描述向极限形式逼 近的近似过程，本文通过大量n s 仿真和对实测数据的仿真，证明了本 文给出的数学描述与多流控制繁特竺譬一致性! 时揭示j 多流控制器的大量潜在应用的可能性a 溶还给出了用多流控制器进 行流数目估计的方法， 明多流控制器进行流效 分析结果表 【关键词】t c p ，r e d ，t f r c ，无状态公平队列，t c p 友好流，带宽分配，拥塞 控制 h a b s t r a c t i o n t h ee n d t o e n dc o n g e s t i o nc o n t r o lm e c h a n i s m so ft c ph a v eb e e nac r i t i c a l f a c t o ri nt h er o b u s m e s so ft h ei n t e r n e t o n ep r e s u m p t i o nf o rt c p t ob es u c c e s s f u li s t h eu s e r sa r ew i l l i n gt ou s et c pc o n g e s t i o n h o w e v e r , t h ei n t e r n e ti sn ol o n g e ra s m a l l c l o s e l y - k n i tu s e rc o m m u n i t y , i ti sn ol o n g e r t or e l yo na l le n d - n o d e st ou s ee n d t o e n dc o n g e s t i o nc e n t r e lf o rb e s t - e f f o r tt r a f f i c s i m i l a r l y , d e v e l o p e r ss o m e t i m e sd o n o t i n c o r p o r a t e e n d - t o - e n d c o n g e s t i o n c o n t r o li nt h e i r a p p l i c a t i o n s f o rs o m e m o t i v a t i o n s u c h 髂v i d e oo ra u d i oa p p l i c a t i o nb a s e do nu d p s ot h ei n t e r a c tw i l lf a c e t h ec r i s i so f c o n g e s t i o nc o l l a p s e ”a g a i nf 11 t h e r ea l et w or e s p e c t st os o l v et h i sp r o b l e m i no n eh a n d ，w en e e dt oi m p l e m e n t am e c h a n i s mt h a tc a nf o r c eu s e rt ou s ec o n g e s t i o nc o n t r 0 1 f l o y df l1p o i n t so u ta i l i n c r e a s i n gd e p l o y m e n to f t r a f f i cl a c k i n ge n d t o - e n dc o n g e s t i o nc o n t r o lc a nl c a dt o c o n g e s t i o nc o l l a p s ei nt h ei n t e r a c t , a n da r g u e st h a tr e u t e r ss h o u l dd e p l o ym e c h a n i s m s t h a tp r o v i d ea ni n c e n t i v es t r u c t u r ef o rf l o w st ou s ee n d - t o - e n dc o n g e s t i o nc o n t r 0 1 t h e m e c h a n i s mc a l li d e n t i f ya n dp e n a l i z eu n r e s p o n s i v ef l o w , a tt h es a m ct i m es h i e l d r e s p o n s i v ef l o w i nt h eo t h e rh a n d ，i no r d e rt od e p l o yr e a l - t i m ea d p t i c a t i o no nt h e i n t e r a c ta n dm a i n t a i nt h ei n t e r a c ts t a b i l i z a t i o n w en e e dt of i n dac o n g e s t i o nc e n t r e l m e c h a n i s ms u i t a b l ef o rr e a l t i m ea p p l i c a t i o n n 地r e s e a r c hi nt h i sd e s s e r t a t i o nt a r g e ta tt h e s et w o r e s p e c t s f o rt h ef i r s tr e s p e c t t r a s ha l g o r i t h mw a sp m p n s e d , t h i sa l g o r i t h r ac a l lp e n a l i z et h o s ef l o w sw h o s er a t e e x c e e d i n gf a i rr a t e ，o n ep r o m i n e n ta d v a n t a g eo f t h i sa l g o r i t h mi si ti sv e r ys i m p l et o i m p l e m e n t f o rt h es e c o n d ，r e s p e c t ，an e wc o n g e s t i o nm e c h a n i s mt h a ti ss u i t a b l ef o r r e a l t i m e a p p l i c a t i o ni sp r o p o s e d ，w en a m e di t 鹋c t f r c a tl a s t 。w ep r o p o s e d m u l t i p l ef l o wr e g u l a t o r sb a s e do nt h et r a s ha l g o r i t h m ，i th a sm a n yu a p p l i c a t i o n ， s u c ha sf l o wn u m b e r e s t i m l 吐i o n , n 瞰i m i t mf l o w 糟l cm e d a l n 地m a i nc o n t r i b u t i o n so f t h i sd i s s e r t a t i o n 玳l i s t e db e l l o w ： 1 t r a s h as t a t e l e s sp e n a l t ya l g o r i t h mf o rn o n - t c pf r i e n d l yf l o wi sp r o p o s e di n s e c o n dc h a p t e ro ft h i sd i s s e r t a t i o n b yk p i n gt h ei n f o r r 州t i o ni nt h ed i 鲫t r d e d p a c k e t s ，t h ea l g o r i t h m 啪d i s c r i m i n a t ea n dp u n i s h 彻枷t h ef l o w , w h i c hs u b m i t m o r e p a c k e t s t h a ni sa l l o w e db yt h e i rf a i rs h a r e n 埒s i m u l a t i o nr e s u l t ss h o w t h a t o u ra l g o r i t h mh a sb e t t o tp e n a l t yp e r f o r m a n c ei nf a l m 船so fb a n d w i d t ha l l o c a t i o n t h a nt h a to fc h o k e m a t h e m a t i c sm o d e lo ft h i sa l g o r i t h mi sd i s c u l l e d 船w e l l n em e t h o do ft ou c h o k ea n dt r a s ha ts a m et i m ei sp r o p o s e dt o oi ns e c o n d c h a p t e r 2 an e wm e c h a l l i s i ni sp r o p o s e di nt h i r dc h a p t e rt h a ti sf r i e n d l yt ob o t hc o n t i n u o u s s t r e a ma n dt c p b ym o d i f y i n gt f r c 【3 6 1a n dr e d 【2 3 】w i t ht h i sm e c h a n i s m ， c o n t i n u o u ss e r v i c e 嘲t r a d es m a l l e rl o s sp r o b a b i l i t yw i t hs e n d i n gr a t et h a tt h e c o n t i n u o u ss e r v i c es h o u l do w n t h i sm e c h a n i s m g u a r a n t e e st h et c p f r i e n d l i n e s s b yu s i n gat e r m i n a lp r o t o c o ls i m i l a rt ot f r c t h er e l a t i o nb e t w e e nt h ea c t u a l l y i n c o n s u m e db a n d w i d t ha n dt h ea v a i l a b l eb a n d w i d t hb yt c pi si n d i c a t e dw i t ha s t a m p c a r r i e di ne a c hd a t a p a c k e t h e a d e ln e t w o r kp r o v i d e sd i f f e r e n t q o s a c c o r d i n g t ot h i s s t a m p s i m u l a t i o n r e s u l t ss h o wt h a tt h i sm e c h a n i s mc a n p r o m o t e t h eq o so f ac o n t i n u o u ss t r e a mw i t h o u t h u r t i n gt c p 3 m u l t i p l e f l o wr e g u l a t o r ( m f r ) ，an o v e in e t w o r kc o m p o n e n tt h a ti s e a s yt o i m p l e m e n t ，i sp r o p o s e di nf o u r t hc h a p t e r d i 虢r e n tf r o mw e l l - k n o w ns i n g l ef l o w r e g u l a t o rs u c ha sl e a k yb u c k e t ，m f rr e g u l a t e sm u t u a lr e l a t i o n sa m o n gi n d i v i d u a l f l o w sw i t i l i na na g g r e g a t e df l o w am f rb a s e do nt h er a n d o ms a m p l i n ga t e p r o p o s e da n di t sf l o wr a t er e g u l a t i n gp r o p o r t yi si d e n t i f i e di nt h i sd e s s e r t a t i o n a s ar a t ef l o wr e g u l a t o r , t h i sk i n do fm f r r e g u l a t e st h eo u t p u tr a t eo fe a c hf l o w a c c o r d i n g t ot h e i n p u t r a t e so f a l lf l o w s m f rc a nn o t o u l y b eu s e dt oi d e n t i f ya n d d e t a c ht h ef l o ww i t ht h em a x i m u mr a t ef r o ma na g g r e g a t e df l o w , b u ta l s ot o m e a s u r ec h a r a c t e r so fa na g g r e g a t e df l o w , a n dt op e n a l i z en o n r e s p o n s i v ef l o w s s t a t i cm a t h e m a t i c a lm o d e lo fm f rw i t hf i n i t em e m o r ya n di n f i n i t em e m o r ya r e f o r m u l a t e da n d a n a l y z e dr e s p e c t i v e l y n l ea p p r o a c h i n g p r o c e s s o fm f r s b e h a v i o rw i t l lf i n i t e m e m o r yt o t h e l i m i t i n g f 0 1 t ni s s t o d i e d n u m e r i c a l l y s i m u l a t i o nr e s u l t s ，c o n d u c t e dw i t hn s 2a n dl e a lm e a s u r e df l o w s s h o wt h a tt h e b e h a v i o ro fam f rf i t st h em a t h e m a t i c a l d e s e r i p t i o n sp r o v i d e d i nt h i s d e s s e r t a t i o n l a r g ea p p l i c a t i o np o t e n t i a l so f m f ra 聆r e v e a l e d 犯w e l l a ti 船tp a r to f t h i sc h a p t e r , w ed i s c u s s e dh o wt oe s t i m a t et h ef l o wn u m b e rw i t hm f r b o t h o f a n a l y s i sa n d s i m u l 砒i o nm e t h o d sa r es t u d i e d k e yw o r d s ：t c p ，r e d ，t f r c ，s t a t e l e s sf a i r q u e u e 。c o n g e s t i o nc o n t r o l i l 办他人；7 ! ! i | ，+ 他沦t第一币缔论 第一章绪论 1 1 引言 t c p 的端到端拥耀控制机制是i n t e m e t 鲁棒性的一个极端重要的因素，但是 t c p 得以成立的。个基本假设是用户自觉地使用拥塞控制算法。今天的i n t e m e t 也经成长为一个面向大众的信息服务平台，期望这里的每一个用户都自觉使用 端到端拥塞控制显然已经不再现实；同样的，出于各种不同的目的，大量网络 应用软件开发商都自觉不自觉地在他们开发的i n t e r n e t 应用中绕过拥塞控制算 法，渚如在i n t e m e tt 不断涌现的分组语音，分组视频等基于u d p 的应用。所 有这些应用，由于没有拥塞避免算法或者没有正确地实现拥塞避免算法，会使 得i n t e m e t 又很快面临拥塞崩溃的危险【1 1 。 解决这个问题至少包括两个方面。首先，需要在路由器实现一种鼓励使用 端到端拥塞控制的机制。关于这一点，f l o y d 已经在文献【1 】中明确指出了端到 端拥摩控制对于防止网络崩溃的极端重要性，并且指出需要在路出器实现一种 鼓励使用端到端捌塞控制的机制的重要性，并指出这种机制应能识别并惩罚非 t c p 友好流，保护t c p 友好流。其次，多媒体通信的网络应用成为网络进一步 发展的一个新驱动，为了在i n t o m e t 稳定运行的前提下使得连续流业务能够在 i n t e m e t 上大规模开展，就迫切需要找到一种适合连续流业务使用的拥塞控制机 制。 本文的研究就是针对网络进一步发展所急需解决的这个问题的上述两个方 面展丌。针对第一个方面，本文在第二章提如了对不负责任流进行惩罚的垃圾 桶算法。针对第二个方面。本文在第三章提出了一种适合连续流业务的传输机 制c t f r c 。随着研究工作的深入，我们发现不警是对不负责任的流进行惩罚， 或是为媒体流构架满足端到端掘塞控制的传输机制，都可以包括在如何对多流 进行有效控制的概念框架之下，因此我们比拟漏桶的思想，提出并建立了多流 控制器的概念，并对多流控制器的可能实现和解析模爨进行了深入的分析。我 们发j 见，与基于漏桶技术的单流控制嚣一样，多瀛控制嚣可以作为一个简单的 网络厄件，在网络的控制和测量方面找到大量扮潜在应用。本文在第四章给出 了这方面的研究。 本文讨论的拥塞控制的网络背景是以尽力传送业务为主的i n t e m e t 。综合业 北方交通人学博i j 学位论义第一荦绪论 务网和和某些区别业务网能够通过c a c 和u p c 实现端到端带宽的定量保证， 因此这类网络可能不需要实现端到端的拥塞控制。确实存在相当的工作在讨论 i n t e m e t 向这类网络过度的可能性，但这将在本质上改变目前的网络风格，因此 不在本文的研究范围之内。 本文研究的目标是在不根本改变当前网络风格的前提下寻求技术创新，解 决实际应用中提出的迫切解决的技术问题，因此研究工作的第一要点是寻找确 实可行的技术解决方案，正是遵循这一点，我们已就本文涉及的研究成果申请 了两项中国发明专利，公开了一项i e t fd r a f t 。本文的研究方法是本着仿真和 数值分析、理论建模和解析并重的路线展开的，本文将提供大量的仿真结果证 明我们所提出的概念和算法的可信性，并通过较为严格的数学模型和数学推导 来深化对概念和算法的理解，并从理性上证明它们的正确性。 1 2 i n t e r n e t 中的拥塞控制 i n t e r a c t 得以稳定运行的关键因素是t c p i p 的广泛使用，而t c p ，妒中对维 护网络稳定运行起核心作用的机制是拥塞控制。t c p ，i p 拥塞控制的本质思想是 通过调整发送端的发送速率来控制网络的负荷量。具体地说，t c p 不断地通过 加大发送的速率来对当前网络的实际承载能力进行探测，并随时准备对网络发 回的拥塞信息作出响应，即迅速减小发往网络的信息速率，并在新的起点上继 续对网络进行试探。 1 2 1t c p i p 中拥骞控棚的发展历史 i n t e r a c t 一开始的设计风格就是使网络尽量简单而将复杂性尽量推向用户。 为使得网络尽量简单，网络不对流的状态进行记录和管理，这带来一个缺点， 网络无法对用户的发送行为进行约束当网络没有一个机制隔离各个流并且用 户又不自觉地约束自己的发送行为时，这个网络的稳定运行就面临危险，实际 上，这个现象在八十年代初就已经出现，并被称为“拥塞崩溃”【2 】 t c p 开始的定义包括了一个基于窗口的流量控制【3 】。这个流量控制机制主 要目的是防止发端发送的数据把接受端淹没。【3 l 报告了由于网络拥塞可能导致 分组丢失，但它没有提出根据网络拥塞的情况谒节流量窗口的大小。这个版本 的t c p 无法解决“拥塞崩溃”这个现象 防止“拥塞崩溃”现象的方法由v a nj a c o b s o n 提出。1 9 8 6 年，v a nj a c o b s o n 2 北方交通人学博l 学位论文 m译绻论 提出了拥塞避免算法，现在使用的t c p 都要求包括这个算法 4 1 1 8 3 1 。这螳算法 在终端主机实现，当拥塞发生时它将使t c p 的发送速率降低。我们称t c p 流 对拥塞信号( 如分组丢失) 发生响应。正是这些拥塞避免算法使得现在的i n t e r a c t 避免了拥塞崩溃。 1 9 8 8 年以后，学术界在i n t e m e t 的动态行为方面作了相当多的研究。事实证 明尽管t c p 的拥塞避免机制是必不可少的且也是很有效的，但是它不能保证在 所有的情况下都能够提供好的业务质量 4 】。除了研究新的拥塞控制机制，需要 研究如何通过路由器的机制作为端到端拥塞控制机制的补充。 1 9 8 4 年， 2 】建议路由器惩罚不能对i c m p 分组发生响应的连接。但是判断 一个连接是否对i c m p 发生响应并不是一个简单的问题。而现在大量的文献中 讨论的问题是路由器如何检测并惩罚不能执行端到端拥塞控制的流 1 】。 由t c p i p 拥塞控制的发展可以看出t c p i p 对于维护网络稳定运行的必要 性，f l o y d 在 1 】对这一点作了更为详细的讨论。t c p 能够对网络的稳定性起作 用有一个基本假设：它要求所有的用户都使用t c p 协议。但是t c p 是一个终 端协议，是否使用它要靠用户的自觉性。由于i n t e m e t 的迅速发展，使用i n t e m e t 的用户数目也迅速增加，所有的用户都自觉地使用t c p 这个假设受到越来越多 的质疑，下一节讨论这方面的问题。 1 2 2t c p 拥塞控制面临的危机 捌塞时t c p 的后退使得多个t c p 能够菇享一个拥塞链路的带宽，并且经 历网络环境相同的流所获得的带宽也基本相同。这些流能够获得基本相同的带 宽是因为这些流使用相同的拥塞控制算法。对于t c p 来说，这些流使用的拥塞 控制算法符合r f c 7 9 3 1 3 1 、r f c l l 2 2 1 5 和r f c 2 5 9 l 【4 】的规定。 i n t e m e t 的快速增长导致了大量不同的t c p 实现版本。因为软件质量问题， 它们中的一些没有实现t c p 的拥塞避免机制【6 】。其他的些有意识地实现一些 更为贪婪地拥塞避免算法，因为这样可以使得软件销售商宣称他们的软件能够 实现“快速t c p ”。这样做的后果将会使得t c p 的实现越来越贪婪，最终彻底 抛弃拼j 塞避免算法，i n t e m e t 将又会出现拥塞崩溃现象。 还有一个著名的方法可以不用改变传输层协议就可以获得更多的带宽，这 个，j 法就是改变流的颗粒度，既对同一个f j 的地同时打开多个t c p 连接，过去 j t 方交通大学博i 学位论史 第一革续l ,ii i i i 育些浏照器已经这样做了。这样做将导致更为贪婪的浏览器。 这引出了对公平牲帮摺塞控制静颗粒度流的定义。根据r f c 2 3 0 9 1 7 ：流的 定义有如下三种：1 ) 一个t c p 或者u d p 连接( 源地址，端口，目的地端口) ； 2 ) 一个源地址目的地地址对：3 ) 一仑绘定的源主枫或毒一个绘定的韪的地主 机。我们认为在大多数情况下一个源地址，目的地地址对佟必流的定义更为合 适。作为拥塞管理的颗粒发，流的定义需要进一步的探讨。 根据r f c 2 3 0 9 1 7 ，t c p 友好流的定义如下：在稻同的网络条件下( 如相 同的丢失率，端到端时延r 1 t 等) ，如果一个流驻够对糖塞信号发生响应并且 平均速率不超过个t c p 滤占用的带宽，那么这个漉裁称为t c p 友好流。 可以恕流分为三类：( 1 ) t c p 友好流。( 2 ) 不嫡应流。如：当发生拥塞时 不对拥塞信号嫡应豹流。( 3 ) 能够对拥塞信号发生响应但不是t c p 友好流。后 面这两类流较为贪婪，对i n t c m e t 的性能构成威胁。 l 。2 3 小结 由上强讨论可知，端到堂| ； 期塞控制对手维护网络的稳定性起着极为重要的 作用，但是隧着i n t e m e t 网络用户群的增加，所有的终端用户都使用端到端协议 这一假设受到了挑战，从而i n t e m e t 的稳定往也面晒危机，因此有必要在路由器 中实现一种机制，这种机制能够强制终端用户使用拥塞控剁，惩罚不使用端到 端拥塞控制的漩，从恧维护i n t e m e t 的稳定性。f l o y e d 在文献f l 中明确指出了 这一点。 1 。3 适合予连续流蛾务的拥塞控制 多媒体概念的炒馋，确实打动了千家万户的心，为计算机业秘嬲络业务提 供巍带来了无限的囊枫，同时也绘网络带来了沉重豹受祷。由于舀箭韵t c p 协 议无法很好支持媒体流的不争攀实，和媒体流需螫安对传送的特点，使得人们 寻求绕过端蠹 端捅塞控制机制来寻求网络对媒体流传送的支持。这自然引发了 网络工作者对i n t e r n e t 重掰如现拥塞崩溃的极度担心，因此对网络多媒体的大 力接崇_ 毂关于警惕网络出现新拥塞崩溃的告警凡乎同时达到了高潮，形成了现 实需求和现实技术极不协调的二个音符。戳制阏络多媒体的使用并不怒解决网 络拥褰崩溃的积极办法。因此真芷的出路应该是为多媒体滤剁造出一套适合它 i 盘茎翌盔兰壁：主竺鲨苎釜耋笙鲨 们应用的端到端拥塞控制机制。 1 3 1t c p 不能用于连续流业务 目前网络上大量的多媒体应用是向客户回放存储的视频或音频信息，并不 需要有苛刻的实时交互，而且随着信源信道编码技术、信号处理技术和存储回 放技术的突破，已经可以作到在带宽和端到端时延有较大变化的条件下支持传 统的实时多媒体业务，但采用t c p 协议所引发的带宽和端到端时延的变化仍大 大超出目前技术所能允许的变化范围。如前所述，i n t e r n e t 的大部稳定性要归 功于t c p 的端到端的拥塞控制机制。网络出现拥塞以及为了防止拥塞所进行的 调整必然会引起用户在通信带宽和端到端时延上的波动，这样就构成了拥塞控 制和对多媒体流支持上的一对矛盾。因此为了使网络在涌如入了大量多媒体业 务后继续强壮，就必须开发出既能满足多媒体通信要求的、又具有拥塞控制能 力的端到端拥塞控制协议。 t c p 对于很多新的应用来说是不适合的。( 1 ) t c p 的突发重传以及突然的、 经常的传输速率的波动会造成多媒体应用的时延差和质量突然下降。( 2 ) 对于 无线网络、线缆调制解调器、a d s l 和卫星网络之类的非对称网络来说，反向连 接的带宽缺乏使得t c p 中对于每个( 或大多数) 分组的传输确认很不适合。( 3 ) 同时，非对称网络中反向路径上的分组丢失以及时延造成了基于r t t 的协议( 如 t c p ) 的性能的严重下降。这使得带宽利用率、公平性及可扩展性都收到了影响。 ( 4 ) 组播的应用也带来了问题。在有着很多接收方( 1 0 0 0 0 到1 m ) 的大范围的 组播应用中，发给发送方的反馈会带来严重的拥塞。 因此，目前的多媒体应用大多是用u d p 承载的。u d p 对于拥塞是没有反应 的，同时，目前占i n t e r n e t 流量9 5 的t c p 会在拥塞时降低其发送速率。采 用u d p 来支持象多媒体应用的这样连接时间较长，所需带宽较高的业务时应采 用拥塞控制机制，不仅改善了对于t c p 的公平性，也使得其本身的分组丢失率 下降。 1 3 2 现有的为连续流业务提供服务质量保证的方法 过去几年t 人们对此进行了大量的研究，目前提出了资源预时 8 、优先 5 北方交通人学博i + 学位论史 弟一币绪论 权机制 9 和应用层适配 1 0 ( 即终端主机的应用能根据网络拥塞状况来调整其 使用的网络带宽) 等方法。 资源预留是最直接的方法。但由于预先不能了解流的确切的特征，结果常 常是预先分配了过多的资源而使得利用率下降。另外，在网络负载较轻时，资 源预留机制不能利用额外的带宽来提高应用的质量。此外，这种方法需要对 i n t e m e t 做较大的改变，大规模实现较为困难。 优先权机制将不同的分组或流分为不同的等级，在路由器处进行不同处 理。这种方法不需要信令，路由器处的控制机制也较简单，因此较资源预留方 法来说，更容易实现。但是，设置优先权的具体机制、控制不同级别的路由器 机制以及这种方法可获得的真正好处目前还没有确切的答案。 应用层适配按探测到的网络变化情自适应地调节信源编码的输出速率，这 一个思想包括广义的分层编码，如r e a la u d i o ，r e a lv i d e o ，f r e ep h o n e 和c d i w a 话音等实用编码方案，也有一般意义上的动态分层编码的讨论，主要策略有两 类，一类主要用于图象，层问业务质量之间的关系是“相加”性质的，即较高 层的数据是对较低层数据的补充，多接收到一个更高层的信息就会对恢复的业 务质量有所改善，但若只接收到了高层而未接收到低层，则恢复的业务质量几 乎没有保障：另一类主要用于语声，层间业务质量之间的关系是“覆盖”性质 的，即从每一层的编码都能完全恢复业务，只是不同层的编码输出速率不同， 相应的所对应的业务质量也不同。应用层适配的好处是能够结合具体的业务特 征选择最好的网络适配方案，因此能够在相同条件下得到最好的业务质量，但 它也有很明显的缺点，一是应用层和网络层( 泛指下四层) 间需要紧偶合，网 络层对网络的探测参数必须与应用层的要求一致，网络层必须随时向应用层报 告探测的结果；这样就违反了工程设计上所一直追求的层间独立的原则；二是 当网络的控制管理行为发生变化时，很有可能会牵动对应用层的重新设计，前 两点赢接违反了我们一直在追求的层间独立原则；三是必须为每一个不同应用 设计不同的网络适配部分，增加了业务开发的成本和难度。 应用层适配适用于单播和小范围的组播。关于应用层适配的具体实现方 案人们提出了很多分级数据的方法 1 1 1 1 2 1 3 】。这些方法是基于将数据流分 6 第一章绪论 为个包括最低质i 要求信息的基本层和一系列增进层，不同的层送至不同的 会i 。接收方需决定要加入哪些会话并根据它们的要求和能力调整q o s 。 j s 锊分层数据传输解决了异类网络的问题，它有可能带来额外的时延。不 的j a j + 能使_ h j 小州的传输路径因此有不同的i m ，接收方需要将数据重新同 步。j 外，如果只有低比特率的层被接收，数据分层可能导致漂移问题。分层 传输还大大增加了端系统的复杂程度。 由于应用层适配存在的各种问题，直接从传输层解决支持多媒体流的拥塞 控制问题就成为一个有吸引力的解决方案，下面我们就来讨论直接从传输层解 决支持多媒体流的拥塞控制问题，并把注意力集中在单播的情况。对于这个问 题近年来发表了大量的研究工作，提出了多种控制机制。这些机制的目的是为 了保证网络资源的合理共享，因此对于多媒体业务尚不多的网络环境中，使用 了这螳拥塞控制机制，有可能使得业务质量相对于不负责任的使用u d p 时所得 纠的业务质量有所下降，但却能保证绝大多数的t c p 用户的权益，这样看来， 多媒体用户自觉使用拥塞控制机制的积极性似乎不会太高，因此在路由器中实 施对小使用拥塞控制的流进行惩罚，可能是使用户自觉使用拥塞控制的可靠保 障。但从另一个角度着眼。当网络中的多媒体流占了相当数量之后，如果大家 都不使用拥塞控制机制，则会造成网络的不必要拥塞，从而阻断所有人的通信 、1 k 务，出于集体利益的考虑大多数理智的人会自觉的使用端到端拥塞控制机制 的，只要这个机制的使用不会在本质上降低可能的通信质量。目前的一些实验 也表明，使用了适用于多媒体流的拥塞控制机制并不会对业务质量带来太多的 影响，与用t c p 支持多媒体通信的方法相比较而言，所带来的业务质量有了本 质上的提高。 1 3 3 小结 出上面的讨论可知，多媒体业务是网络发展的一个新的重要支撑点，对多 媒体业务的支持是网络应用急需解决的问题，传统的t c p 不能适合作为连续流 业务的传输层协议，而现有的为连续流提供业务质量的方法又不尽如人意，而 端到端拥塞控制又对维持i n t e m e t 的稳定性又至关重要，因此寻找一个适合连续 流业务使用的传输层协议就非常的重要，如果路由器如1 2 节所述使用了鼓励 j l 疗，( 删人 似l f t 论正 第一节绪沈 端到端拥塞控制的机制，则这一点就显得更为迫切了。 1 4 本文的主要贡献 随着非t c p 友好流在i n t e m e t 上的涌现，i n t e m e t 又一次面临拥塞崩溃的危 险。本文提出了一种新的对非t c p 友好流的惩罚机制一垃圾桶算法，该机制 通过利用已经被丢弃的分组的信息来加强对非t c p 友好流的识别及惩罚。 水文还提出了垃圾桶算法与c h o k e 联合使用的方法。对垃圾桶算法进行了 仿真和数学建模分析。 本文提出了双友好机制的框架，在这种框架下：连续流业务有权获得与t c p 平均速率一样发送的发送速率，但是由于连续流本身的特性所限，它无法 ，乙拿使用它应该得到的发送速率，那么连续流业务就应该有权根据它应该 享受但是又没有能够享受的带宽从网络要求获得其他服务质量的优惠。在 t f r c 和r e d 的基础上，本文给出了一种实现这种框架的具体方法- - c t f r c ， 这个机制通过类似t f r c 的终端协议来保证t c p 友好性，通过选择适当的优 惠函数来标记连续流的带宽使用情况，并通过网络对不同优惠值分组的不 同丢失特征来保证连续流的传送质量。 本文提出了多流控制嚣的概念，多流控制器按照某种目标同时对多个流之 州的关系进行约束，本文给出一种基于随机碰撞的多流控制器的实现方式。 这种多流控制器能够识别汇聚流中的最大速率流并把它从汇聚流中分离出 来。它可以用于汇聚流特征的测量、非拥塞响应流的惩罚、流数目的估计 等多个领域。本文分析了静态条件下的多流控制器数学模型，给出了有限 记忆长度多流控制器工作特性精确描述和无限记忆长度下多流控制器工作 特性的极限形式，数值计算了精确描述向极限形式逼近的近似过程，本文 通过大量n s 仿真和对实测数据的仿真，证明了本文给出的数学描述与多流 控制器实际工作特征的一致性，同时揭示了多流控制器的大量潜在应用的 可能性。本文还给出了用多流控制器进行流数目估计的方法，并且给出了 数学分析和仿真分析，分析结果表明多流控制器进行流数目估计具有一定 的实用意义。 1 5 本文的结构和安捧 本文余下部分的安排如下：第二章提出了垃圾桶算法，对其进行了仿真分 i t ，j 交通人学博f ：学位论史第一苹绪论 析和数学建模。第三章双友好机制，对其进行了仿真分析。第四章提出了多流 控制器，对其进行了仿真分析和数学建模。第五章是结论与展望。 最后，本章的绪论只覆盖了第二章和第三章，第四章多流控制器的内容相 对独立，因此我们在第四嚣中单独给出多流控制器的绪论。 9 北方，丑大7 产博士学侄论疋第二章：垃圾椭并法 第二章垃圾桶算法 i n t e r n e t 中应用最为广泛的拥塞控制方法是路由器的先进先出( f i f o ) 和端 到端的拥塞控制方法。这个方法易于实现，并且端到端拥塞控制机制不需要连 接经过的整条路径都使用同样一种缓存管理方法，符合i n t e m e t 异种网络、分散 控制i n 风格。但是这种方法也有严重的缺点。其中之一是这个方法不能提供即 使是州对的业务质量，现在i e t f 提出了区别业务模型来解决这个问题。f i f o 调度的第二个缺点：不使用端到端拥塞控制的连接可以在f i f o 这种调度机制 下获得较大的带宽份额，最终危害i n t e m e t 稳定的基石。 爆管所有的证据显示当前绝大部分业务都使用友好的端到端拥塞控制，并 且i n t e m e t 还没有出现严重的运行问题。但是人们致认为应该在路由器处增加 能够保护t c p 友好流不受非t c p 友好流伤害的机制。 本誊的主要内容如f ： ! l背景知识介绍，包括已有的惩罚算法介绍和流速率分布的介绍。 s 2 2 提出纯垃圾桶算法，并给出仿真结果； 2 3 给出垃圾桶算法和c h o k e 算法联合使用的方法，并给出仿真结果； 2 4 给出纯垃圾桶算法的理论分析，将理论结果与仿真结果进行了比较； 25 总结全章。 2 1 背景知识介绍 2 1 1 已有的惩罚算法 图2 1 画出了对流处理的可能性【1 4 】。需要记住每一个流状态的公平排队算 法和完全不需要流状态的f i f o 、r e d 处于两个极端，处于中间的机制需要记 录部分流的状态。 叼o m p m a p m 口 怖耐 = 怒勰龋