（计算机应用技术专业论文）多速率组播拥塞控制算法研究.pdf

硕士学位论文 m a s t e r st h e s i s 中文摘要 近年来，多媒体应用在i n t e m e t 中占据越来越重要的位置。如果多个用户同时 要接收同样的多媒体数据，组播是最有效的单点到多点的数据传输方式。传统的组 播以单一速率发送给所有的接收端。然而由于i l l t e m e t 固有的异构性和接收端的不 同需求，使得单一速率的组播不再适用。因为单一速率要么使得慢速的接收端发生 拥塞或者使得快速的接收端无法按照其可接收的速率接收而造成资源浪费。因此使 接收端能根据各自的接收能力和网络带宽以不同的速率接收即多速率组播成为一 个热点问题，特别是在视频应用中。而多速率组播研究的核心问题即是多速率组播 拥塞控制算法。 本文以多速率组播拥塞控制算法为研究对象，首先介绍了多速率组播拥塞控制 算法的两大评价标准：公平性和可扩展性，接着分析和探讨了现存的三大类多速率 组播拥塞控制算法，最后提出了一种提高全局视频质量的多速率组播拥塞控制算 法。 此算法是对一接收端驱动、源端调节的算法的改进，主要是对源端进行层速率 调节时目标的改进。考虑到组播应用的多样性，本文提出了全局质量因子g q i ，不 仅考虑了接收端的满意程度和加入层数的稳定性，还考虑了组播组的网络带宽。然 后以最小化此因子为优化目标，构造了一个层的速率分配的优化问题，并阐述了解 决此问题的可行算法，最后用仿真验证当用此因子作为衡量组播组全局视频质量的 标准时，能够保证所要优化的目标，达到用户的需求。 关键词：多速率组播；拥塞控制；分层组播；全局视频质量 a b s n a c t r e c c n t l y m u l t i m e d i aa p p l i c a t i o n st a k eag r o 、v i n gp l a c ci nt l l eh i t e m e t i fm u l t i p l e u s e r sw a n tt or e c e i v et h es a m em u l t i m e d i ad a t aa tt h es 锄et i m e ，m u l t i c a s ti st h em o s t e f f i c i e n tw a yo fo n e t o m a i l yt r a l l s m i s s i o n h lt r a d “i o n a lm u m c a s t i n 吕a ur e c e i v e f so ft h e s 锄em m t i c a s tg r o u p 辑c c i v cd a t aa tm es a m er a t e 。h o w e v c r ，t h ei n t e m e t si n t r i n s i c h e t e m g e n e i t ya n dd i v e r s er c c e i v e r sm a k es i n g l e r a t em u l t i c a s tu n s u i t a b l e f o rs i n 醇e r a t e m u l t i c a s ti sl j l 【e l yt oo v e r w h e l i nt h es l o wr c c e i v e r sa n ds t a n r et h ef a s to n e s t h u s ， m u l t i m t em u l t i c a s t ，w h c r ct l l er e c e i v e r so ft h es a m em u l t i c a s t 伊o u pc a nr e c e i v ed a t aa t d i 丘b r e n tr a t e sc o m m e n s u r a t e 、i t ht l l c i rd i v e i s cr c q u i r e m e n t s 锄da l s ow i t ht h ec a p a c i t y o ft h cp a t hl e a d i n gt oi tt f o mt h cs o u r c c ，h 镐r c c c i v e da 孕e a td e a lo fa t t e n t i o n ，e s p c c i a n y i i lv i d e oa p p l i c a t i o n 1 h em a i np r o b l 锄o fm u l t i r a t em u l t i c 髂tr e s e a r c hi sm u l t i r a t e m u l t i c a s tc o n g c s t i o nc o n t r o la 培。五t h m ht h i sp a p e r ，w ef o c u s 叩t h er e s e a r c ho fm u l t i r a t em u l t i c 硒tc o n g e s t i o nc o n t i d l a l g o r i m m s f i r s t ，w ei n t r o d u c et w o m e 仃i c st oe v a l u a t e 舢1 t i r a t em u l t i c a s tc o i 培e s t i o n c 0 曲r o la l g o r i t l l l s ：f a i m e s sa n ds c a i a b i l “y ，t l l e nw e 粗a l y z ca n dd i s c u s st h r e eb n d so f m u l t i r a t em u l t ：i c 髂tc o n g e s t i o nc o n 仃o la i g o r i t h m s ，瓤a l l y ，w cp r o p o s ean e wm l l l 蛳e m u l t i c 弱t0 0 n g e s t i o nc o n 廿o la l g o r i t h l na i l i l i n ga ti m p r o v i n gt h eg l o b a lv i d c oq u a l i 何 1 1 l i sn c wa l g o r i t h n lj s 柚i m p m v e m e n to v e r ar e c c i v c r _ d r i v e n ，s 叫r c ea d a p t i v e a l 窘0 州h l i l ，m a i n l yo v e ro p t 洫i z 撕o no b j e c t i v eo fs o u r c cl a y c h a l ea d j u s t i i l g c c m s i d e f i l l g t l l ed i v e r s i i yo f 印p c a t i ；0 n s ，w ci n 讯) d u c ca9 1 0 b a lq u a l i t y 觚e x ( g q dt h a tc h a r a c t e r i z e s t h ed e n s i t y0 fs a t i s f i e d 姗i v c r s ，t h ea m o u n to fa ：o c a t e dn e 帆r kb a n d w i d t ha n dt l l e s t a b i l i t yo ft h eq u a l i t yo f 也er c c e i v e r s t 1 l e nw ef 0 衄u l a t et h eo p t i m a l l a y e r 豫t c a l l o c a t j o np m b l e mw i mt l l eo b j e c t i v eo fm 血m i z i n gt l l i si n d e xa i l dd e r i v ea ne m c i e n t a l g o f j t h mt os 0 1 v et h ep r o b l 锄，s i m u l a t i o nf e s u l t sd e m o i l s t r a t et h a tu s i n gt h i si n d c x ，t h e u s e r s o b j e c t i v ec a i lb ea c h i e v e d k e yw o r d s ：m u l t i r a t em u l t i c a s t ；c o n g e s t i o nc o n t r o l ；l a y e r e dm u l t i c a s t ； g l o b a lv i d c oq u a l i t y i i 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名蓬勃卿 日期：力卯z 年多月驴日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 作者签名：墨勃椰 日期：弘年占月g 日 导师签名： 日期：砀燎东丁乙年易月g 日u 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。回童途塞握童后进后! 旦坐生；旦= 生；旦三生筮壶! 作者签名：蓬劾卿 日期：渺6 年6 月岔日 刊醛各批顷一 日期：2 御易。年6 月雪日 硕士学位论文 m a s t e r st h e s i s 引言 近年来，随着h t e m e t 的迅速普及和爆炸性发展，在i n t 咖e t 上产生了许多新的 应用，其中不少是高带宽的多媒体应用，譬如网络视频会议、网络音频视频广播、 视频点播、股市行情发布、多媒体远程教育、远程会诊、在线信息恢复，软件或代 理缓存更新等。这就带来了带宽的急剧消耗和网络拥塞问题，组播是一种解决单点 到多点通信的非常有效的方式，能有效地节省大量带宽，因而得到了广泛的重视。 传统的组播是以单一速率发送给所有的接收端。然而由于m t e m e t 固有的异构 性和接收端的不同需求，使得单一速率的组播不再适用。因为单一速率要么使得慢 速的接收端发生拥塞或者使得快速的接收端无法按照其可接收的速率接收而造成 资源浪费。因此使接收端能根据各自的接收能力和网络带宽以不同的速率接收口多 速率组播成为一个热点问题，特别是在视频应用中。 虽然组播是解决单点到多点的有效的数据传输方式，然而至今仍无法得到i s p ( h t e m c ts e r v i c cp r o v i d c r ) 的广泛应用，一个重要的原因在于组播没有提供合适的 拥塞控制算法。作为组播的一种，多速率组播研究的核心问题就是其拥塞控制算法 的研究。 本文主要研究多速率组播拥塞控制算法，结构如下： 第一章中将给出多速率组播的概念，同时还将给出多速率组播拥塞控制算法的 两个重要的评价标准：公平性和可扩展性。 第二章将介绍三类多速率组播拥塞控制算法：源端动态调整的、接收端驱动的 和接收端驱动源端动态调整的，并将对其中一些典型算法进行分析和探讨，比较其 利弊。 第三章将给出一种提高全局视频质量的多速率拥塞控制算法。源端能根据用户 的不同需求( 通过全局质量因子反映) 调节层的速率，从而满足用户的需求，仿真 表明该算法有较好的性能。 第四章将总结全文。 硕士学位论文 m a s t e r l st h e s l s 1 多速率组播与拥塞控制 各种多媒体应用的出现、h t e m e t 固有的异构性和用户的不同需求使得多速率组 播成为研究的热点问题之一。在多速率组播中，接收端能根据其不同需求和网络所 提供的不同带宽以不同的速率接收。组播作为一种解决单点到多点通信的有效方 式，其引入虽然节约了网络带宽但同时也给i n t e m e t 带来了很多潜在的问题【“。而多 速率组播作为组播的一种，也不可避免地存在着组播本身固有的一些问题，例如： 组播安全问题、拥塞控制问题、组播路由问题和错误恢复问题等，而其中组播拥塞 控制是所有问题中重要但难以解决的问题之一，同时也是最令人关注的问题之一。 至今组播无法得到i s p ( i n t e m e ts e i c cp r o v i d e r ) 的广泛应用，一个重要的原因就在于 组播并没有提供恰当的拥塞控制机制或根本没有拥塞控制机制。就像单播t c p 的成 功源于其有效、实用的拥塞控制技术一样，组播技术要想取得成功就必须完善其拥 塞控制技术。如果组播拥塞技术不能得到很好的解决，这不但会给组播本身的发展 带来限制，而且会造成网络的不稳定，带来拥塞崩溃。如果组播应用不能对网络拥 塞做出正确响应，将会给i n t e m e t 带来比单播( u n i c 弱t ) 投递应用产生的拥塞更为严重 的影响。这主要因为：( 1 ) 组播组可能产生大量数据流和控制流沿其组播树广泛分 布于整个h t e m e t ；( 2 ) 组播数据流的接收方具有异构性，每个接受方的处理能力不 同，其分组路径也可能有不同的带宽和差错特性；( 3 ) 组播发送方需处理比单播 ( u n i c a s t ) 多得多的反馈报文，有可能产生反馈爆炸，使网络处于持续拥塞状态。因 此随着计算机网络技术的不断发展，越来越多的网络应用需要使用组播 ( m u m c a s t ) ( 包括多速率组播( m l l l t 曲t em u n i c a s t ) ) 的支持，以便节省网络带宽，提高 应用的可伸展性，而解决其拥塞问题提高服务质量将对组播的发展起着十分重要的 作用。 1 1 多速率组播 异构性是h l t e m e t 网络的固有特征，网络中资源分配的不均匀以及端系统处理 能力的差异是这种异构性存在的根源，并且随着未来越来越多不同种类的网络接入 i n t e m e t ，h t e f n e t 的规模不断扩大，异构性问题将更加突出。在这里我们将给出一 个简单的异构网的示意图( 图1 1 ) ，并假设有个组播网现运行在此异构网上，阐述 多速率组播与单速率组播最终的速率分配结果，从而看出多速率组播的优越性。 2 硕士学住论文 m a s t e r st h e s i s 图1 1 简单的异构网 在图1 1 中，我们给出了一个简单的一个源端( s ) 4 个接收端( 吒，r 2 ，3 ，r 4 ) 的拓扑结构。从图中可以看出，这4 个接收端可接收的速率各不相同，如果是传统 的单速率组播，源端为了避免网络的拥塞和减小丢包率，可能会以2 8 8 k b p s 的速 率发送，从而会使得其他3 个接收端的些带宽浪费掉。在多速率组播中，则可以 使得各个接收端都能按照自己的接收能力接收，而不受到其他接收端能力的影响， 也就是说，这4 个接收端可能可分别以接近于1 2 8 k b p s 、4 5 m b p s 、2 8 8 k b p s 和1 0 0 m b p s 的速率接收，从而能充分利用网络的带宽，并满足用户的需求。 1 2 拥塞控制 随着计算机网络用户数量的膨胀和对网络资源需求的增加，网络的拥塞问题显 得日益严重。拥塞是一种持续的网络超负荷状态【甜。简单来讲，拥塞是指用户的需 求超过了网络的供给，比如说当多个用户同时向某一节点申请某一资源时，就可能 使得此节点在此资源上发生拥塞。拥塞将会导致网络的性能大大下降。 图1 2 拥塞发生时系统的情况 文献【3 ，4 谰图2 来表示拥塞的发生。当负载较小时，吞吐量的增长与网络负载的 增长基本呈线性关系，而延迟增长缓慢；在负载超过k h e e 点之后，吞吐量的增长趋 3 b 曲 飞 硕士学位论文 m a s t e r st h e s i s 于缓慢，但延迟增长加快；当负载超过c l 证点之后，吞吐量急剧下降，延迟急剧上 升。可以看出，负载在k n e e 点附近时网络的使用效率最高。 拥塞控制主要考虑端节点之间的网络环境，目的是使负载不超过网络的传送能 力。通常拥塞控制算法包括拥塞避免( 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 n r e c o v e f y ) 这两种不同的机制。拥塞避免机制的目的就是使网络工作在k n e e 点附近； 拥塞恢复机制的目的就是当网络工作在c l i f f 或a i f f 点以后时，使网络回复至k n e e 点前后。拥塞避免策略是预防性的，其目标是避免网络进入拥塞状态，使网络能够 在高吞吐量、低延迟的状态下运行；而拥塞恢复策略是救治性的，其目标是当拥塞 发生后，使得网络复原至正常的工作状态，它用于把网络从拥塞状态中恢复出来。 若没有拥塞恢复机制，当拥塞发生时网络有可能崩溃。因此，即使使用了拥塞避免 策略，仍需要拥塞恢复策略来保持吞吐率。此外网络中源节点发送数据的起始时间、 发送速率及数据量具有不可预测性和突发性，这些也有可能会导致网络的拥塞。本 文探讨的多速率组播拥塞控制算法主要是拥塞恢复策略，即在发现有拥塞状况时， 迅速调整源端的发送速率或者接收端的接收速率，从而缓解网络中的拥塞状况，使 网络恢复至正常状况。 1 3 多速率组播拥塞控制中的评价目标 多速率组播作为组播的一种，组播设计的评价目标也适用于多速率组播。归纳 起来，组播拥塞控制算法( 包括多速率组播) 的评价目标，主要体现在以下2 个方 面：( 1 ) 可扩展性；( 2 ) 公平性。 1 3 1 可扩展性 组播拥塞控制算法的可扩展性是指协议在性能( 包括吞吐率、延时) 下降前可以 支持多少用户【2 】o 可扩展性是衡量组播算法的一个非常重要的因素，现今h t 唧e t 的用户越来越多，网络负载越来越大，只有当算法能支持大量用户的使用时才有其 可行性。它受到四方面因素的限制： ( 1 ) 任务复杂性：当组成员的数量变得越来越大时，拥塞控制任务的复杂性会 急剧上升，从而限制协议的可扩展性。可以通过在源端和接收端之间进行合适的分 工来解决这个问题。 ( 2 ) 反馈爆炸问题【5 】：拥塞控制需要考虑所有组成员的拥塞状况，随着组规模 的增加，大量的反馈可能淹没源端。为了解决反馈爆炸问题，在目前的组播协议中 4 硕士学位论文 m a s t e r st h e s l s 主要采用的反馈控制算法有以下几种。 夺基于定时器的抑制，每个接收端在发送反馈信息之前，需要等待一段随机 时间，如果在等待期间收到来自其他接收端的对同一数据包的反馈信息， 则取消自己的反馈，否则如果定时器超时，则将反馈发送到发送方，并以 组播的方式发送给其他接收端【6 】。 夺基于代表的抑制，在个接收端中，指定k 个符合一定条件的接收端作为 代表来反馈信息，其他接收端不发送反馈【4 ”，这个方法的难点在于如何选 择合适的代表。 夺基于轮询的抑制，发送方周期性地向各个接收端轮询网络的拥塞情况，每 次只有收到轮询的接收端才能发送反馈【羽。 然而上述方法中，完全由源端来负责拥塞控制，所以组播组不能太大，因为源 端必须为多个连接维持状态信息，负载较重。因此需要可扩展的组播拥塞控制机制。 不过e c n ( e x p l i c “c o n g e s t i o n t i f i c a t i o n ) 例的应用将能使反馈量大大减小，从而使 得此问题得以缓解，同时分布式算法也是解决此问题的方法之一。 ( 3 ) i j p m 问题1 1 0 】：目前的m 组播模型中，源端不了解组播组的拓扑结构，无法 综合接收端的拥塞信号。通常，源端响应多个拥塞路径产生的信号之和。随着组规 模的增加，组播树的数据丢失路径会随之增加，从而导致大多数分组至少会经历一 次丢失，如果源端对每一次丢失做出响应，组播吞吐量可能下降为0 m r o p t o z e r o ) ， 当数据分组独立地丢失在多个路径中时，这些路径的下游接收点将都发送拥塞信号 给源端，必然引起源端发送速率的迅速恶化。这就是组播中的丢失路径多样性( l o s s p a 血m u l t i p l i c i t y ，简称l p m ) 问题。适当的反馈聚合和反馈抑制可以减轻i j p m 问题 对组播组性能的影响。 ( 4 ) 网络随机延迟的影响【1 1 】：即使在非常理想的网络环境中( 网络中无分组丢 失，路由器缓存无限大) ，随着组规模的增加，网络中随机分布的队列延迟( 路由器 的服务延迟) 也会给组播组的性能造成影响。多速率组播可以减轻此问题。 1 3 2 公平性 在组播拥塞控制中，公平性( f a i m e s s ) 【1 2 】是每个组播拥塞控制算法所追求的设 计目标之一，也是其能否得到广泛应用的基础之一。组播拥塞控制中的公平性主要 表现在两个方面： ( 1 ) 协议间的公平性( h t e i - d m t o c o lf j j m e s s ) 现今t c p 在i n t e m e t 网中占据了主要地位，组播的加入使得非t c p 通信量所占 硕士学位论文 m a s t e r st h e s l s 比重增加，而这些协议大都没有与t c p 兼容的拥塞控制机制，它们以一种不公平的 方式与t c p 流竞争：当遇到拥塞时，所有参与的t c p 流立即减小它们的速度试图减 轻拥塞，而非t i 卫流继续以原速发送，这种极度不公平的情形会遏制t c p 通信， 甚至导致拥塞崩溃，当网络中可利用的带宽被耗尽，所有的包在到达目的地之前将 会因拥塞而被丢弃。因此组播协议应该保证当组播流与t c p 流共享瓶颈链路时，双 方可以公平地占用网络带宽，公平地竞争资源。因此在制定组播拥塞控制标准时， i e t f ( i i i t c m e te n 酉n e e r i n gt a s kf o r c e ) 要求组播拥塞控制算法必须做到t c p 友好 ( t c p f f i e n d l v ) ，即满足协议间的公平性( i n t e r - p r o t o c o lf a i r i l e s s ) 。 1 p f r i e n d l v 存在多种定义，文献1 1 3 】给出的定义是：“非t c p 流量的长期吞吐 量不超过相同情况下t c p 流量的吞吐量”。文献【1 4 蛤出了更为严格的定义： 夺单播t c p 友好，是指在相同网络条件下，如果一个单播流量对其他并存 t c p 流量的长期吞吐量的影响( 减少) 不大于另外一个t c p 流量对后者的 影响，此单播流量被认为是t c p 友好的； 夺组播t 凹友好，是指在源端与每个接收端之间，如果流量具有单播流量 t i 四友好的特性，此组播流量被认为是t c p 友好。 值得一提的是，目前对于组播t c p 友好的定义还存在很多争论。有些定义指出， 由于组播流量为多个接收端服务，因此应该允许组播流量使用比单播流量稍多的带 宽。文献【8 】采用下面的公式来定义组播t c p 友好： 4 卯srs 6 c p ( 1 1 ) 其中r 表示瓶颈链路上的组播流的速率，k ，表示相同情况下t c p 流的速率，口 和6 是流接收端数目的函数。当6 1 时，以上两种定义是相同的。 其中t c p 的吞吐量通常使用文献【”】提出的如下公式计算： r = = - ；，( 1 2 ) f r 玎p 其中r 代表吞吐量，p 表示丢包概率，f 。指从源端发送数据包至收到接收端确认 的时间间隔，有时也称作础r i ( r o u n dt r i p 砸m e ) ，5 指包的大小，c 是在o 8 7 到1 3 l 之间的常量，取决于a c k ( a c k n 0 、i e d g e m e t ) 的利用率与测量丢失事件的周期。 但公式( 1 - 2 ) 并没有考虑代p 超时。文献1 1 5 l 给出了一个更为复杂的公式，更为精确 地描述了t c p 的吞吐量： 硕士学位论文 m a s t e r l st h e s i s r | m i “等哥甄孟丽l n 3 其中是拥塞窗口的最大值，6 是每个a c k 应答的分组数量，。是重传超时值。 ( 2 ) 协议内的公平性( i n t r a p m t o c o lf a i m e s s ) 组播是一对多的通信，在组播会话中有多个接收端。协议内的公平性指各接收 端之间的接收速度应该相互不受影响。协议内的公平性可以说就是一个组播会话中 各个接收端的公平性( i n t e 卜r e c e i v e r f a i m e s s ) 。文献【1 6 】给出了一个计算接收端公平性 的函数： e ( ，) = r r ；竺煎! 生( 1 4 ) = 一 、1 ， m a x 以，r ) 其中 为用户f 可接收的最大速率，为用户接收的实际速率。当e ( r ) = 1 时，接收 端达到最大公平性。在文献m 中有类似的定义。 在单速率组播中，接收能力强的接收端的接收速率一般都会受到接收能力弱的 接收端的接收速率的影响。而多速率组播算法的设计目的之一就是希望各接收端能 根据自己的接收能力而确定自己的接收速率，即使协议内的公平性达到最大。因此 多速率组播拥塞控制算法设计的初衷就是使协议内的公平性达到最大，从而缓解网 络的异构性所带来的问题。 由上可知，多速率组播拥塞控制算法首先要实现接收端能按照自己的接收能力 确定不同的接收速率( 即协议内公平性比较好) ，其次此算法必须能在网络发生拥 塞时，迅速使网络恢复到正常状态( 有合适的拥塞控制机制) ，最后此算法还应该 有较好的扩展性和协议间公平性。 7 多速率组播拥塞控制算法 目前组播拥塞控制算法的分类方式有很多种，按照数据发送方式可分为单速率 和多速率两大类【1 4 l ；按照控制方式可分为基于速率和基于窗口的两大类算法【1 4 】；按 其是否需要路由器的支持可分为端到端( c n dt oe n d ) 和路由器支持( r o u t e rs u p p o r t e d ) 的算法【1 8 】。这里根据其驱动方式将多速率组播拥塞控制算法分为三大类：基于源端 动态调整、基于接收端驱动和接收方驱动一源端调整的综合算法。 2 1 基于源端动态调整的多速率组播拥塞控制算法 这类算法的主要特点是拥塞算法放置在发送方，每个接收方按照一定的时间间 隔周期性地向发送方发送反馈报文，发送方则从反馈报文中获取有关信息，并以此 来调整发送速率。下面将介绍几种通过优化方式来实现的基于源端动态调整的多速 率拥塞控制算法。 下面三种算法都是基于文献【1 9 】所提出的受制于链路带宽限制，最大化所有接收 端的效用函数的优化算法。文献1 给出了对应于网络实际问题的原始和对偶算法， 文献【2 1 】则给出了收敛于最优解的对偶算法。文献【加2 1 】所提出的算法都是针对于单播 而言，单播源根据拥塞信息( “拥塞代价”) 更新其速率，网络则根据源速率更新其 拥塞信息，是典型的源端驱动的算法。下面三种算法都是采用与文献【1 9 】类似的方式 将多速率组播问题构造成同一个优化问题，然后通过不同的算法对此问题求解。 多速率组播对应的优化问题p ： p ：m a x y 【厂，o ，) 怨 受制于： 罗婴照z ，5c f 工 ( 2 1 ) 翩嘞“ z ，盖，v ，r( 2 2 ) 其中各个参数所代表的含义如下： r ：所有组播组的接收节点集合； x ：接收节点，的速率； u ，( z ，) ：接收端r 的效用函数，递增的凹函数( c o n c a v ef i l n 嘶o n ) ，选择不同的效用函 硕士学住论文 m a s t e r st h e s i s 数可使得接收端获得不同的公平性【2 2 矧，如最大最小公平性( m a ) 【- m i nf a i m e s s ) ，比 例公平性( p r o p o n i o n a lf a i m e s s ) 【2 0 1 ，最小延迟公平性( m i i l i m u md e l a yf a i m e s s ) 【翊， 从而使得此算法满足不同的协议内公平性； m ：组播组的集合； 墨：流经链路f 的接收端的集合； 凡：组播组m 中的接收端的集合； 工：网络中所有无向链路的集合； c ，：链路f 的带宽： 盖，：接收端r 速率所在的范围瞻，耳】，其中6 ，为接收端r 要求的最小速率，曰，为接 收端r 所能接收的最大速率。 sn r 。表示组m 中流经链路f 的接收端的集合。了m a 【z ，则表示组川在链路f 上。 息q 他。 的速率。 2 1 1 基于优化的多速率组播速率控制算法 由于问题p 中的m a ) 【函数是非线性的，且有几个变量，使得直接求解很困难， 此算法f 2 4 】将问题p 中的链路限制线性化，转化为如下问题： p ： m 缸u ，( ) ，j ) 受制于： 荟_ ) ，一瓠荟) ，产r 舵工 ( 2 3 ) y ，s y 。( ，) w js ，石( ，) 妒 ( 2 4 ) y 巧 ， 其中各个参数所代表的含义如下： 蠢：所有组播组的分支节点( j u n c t i o nn o d e ) 的集合； 豆：ru 晨，所有的接收端和分支节点的集合； 厂：与接收节点直接相连的分支( b r 趾c h ) 的集合( r e c e i v e r b r a i l c h e s ) ； j ：与分支节点直接相连的分支的集合( i l l n c t i o nb r 孤c h e s ) ： 9 硕士学住论文 m a s t e r l st h e s i s ，：j u j ，所有分支的集合； k 。：蜀，流经链路z 的分支集合； y ，：分支j 对应的节点的速率，即与分支相连的接收节点或分支节点的速率，其 中j j ； r ( j ) ：与分支j ，相连的接收端或分支节点的集合； u ，：与分支，相对应的接收节点r ( ，) 的效用函数； z ( ，) ：分支，的父亲分支，即从分支，到源节点的路径上所经过的最近的分支，如图 2 1 中，。是，。的父亲节点，相对应地j 。是，。的孩子节点： c j ：节点，的所有孩子节点，c ，一 ，：石，= n y 。鼢薹导娜为籼，掣的任觏 这里给出一个简单的示意图： 图2 1 多速率组播树及其参数的示意图 1 0 硕士学位论文 m a s t e r s t h e s i s 对应于问题p 的对偶问题是： d ： m i 是d ( p ，q ) d ( p ，q ) = 1 警l ( y ，p ，q ) 2 丢6 ，o ，g ) + 荟p f c ； 其中 嘶，_ f 乏舞留：0 繁，”黟 其中】，= ( y ，y ：y ，一w 歹； ，：与链路限制( 2 3 ) 相对应的对偶变量； f ，：分支，上所有的链路代价之和，f ，一。，a ； 丁，：组删中分支，的所有下游分支集合； 孽，：附加变量，鼋，y ，表示0 的接收端为使用巧外的链路而付的代价。 此优化算法的基本思想是：接收端根据其效用函数和收到的网络拥塞反馈 ( f c p ) 决定其速率，并向其父亲节点反馈，分支节点聚集所有的请求( b c p ) ，选 择其中最大的速率反馈给其父亲节点。反馈一直向上传递到源节点。源节点则根据 反馈选择发送速率。利用子梯度( s u b g m d i e n t ) 算法求解问题d ，所得分布式算法的 示意图： 图2 2 多速率组播分布式算法的示意图 硕士学位论文 m a s t e r st h e s l s 具体的分布式算法如下： 链路f 的算法： 如果接收到一个b c p ： 读其f 区域得知更新的伪速率，更新链路代价p ，如下： p f 一【p l + a ( 弓一c j ) 】+ ，并将b c p 传递到下一个链路 凰 如果接收到一个f c p ： 将其链路代价加到f c p 的f 区域中，并转发到下一链路。 源端s 的算法： 如果接收到一个b c p ： 1 读其j 区域知道其孩子节点所要求的新速率； 2 发送一个f c p 包到其孩子节点，并将包的f 区域设为0 。 接收节点r ( ，) 的算法： 如果接收到一个f c p ： 1 读其f 区域得到其当前的更新代价，计算其新速率： 。j 。y j 。盯8 篱o ) 廿j y 2 发送一个b c p 到其父亲节点，使得i ，一z ，弓一y ， 分支节点，( ，) 的算j 去： 如果接收到一个f c p ： 1 读其f 区域得到其合适的更新代价，计算其新速率： ，一哪学蝠一荟 2 发送一个f c p 包到其孩子节点，设置亏r 一口，。 如果接收到一个b c p ： 1 让r ( ，) 代表发送其b c p 的孩子节点，读其i 和f ， ( a ) 更新9 ，：口，一k ，+ a ( y ，一y 棚+ ( 6 ) 更新实际速率：z ，“翼茅i ， 2 接收到所有孩子节点的b c p 后，发送b c p 到其父亲节点，使j ，一z ，弓一y 。 图2 3 基于优化的多速率组播分布式算法 1 2 这个算法的优点在于考虑了接收端节点的公平性，即协议内部公平性；但是算 法中的伪速率，可能与实际速率有一定的差别，使得算法不是很精确；而且分支节 点需要存储一些伪速率和代价，这些可能是实数，使得此算法的代价过高，扩展性 受到了限制；此算法在异步环境下的收敛性缺乏理论证明；此算法没有考虑协议间 的公平性，即此算法不是t c p 友好的。 2 1 2 可扩展的，低代价的多速率组播控制算法 此算法【硎与上述算法比较类似，同样地其需要将问题p 中的m a ) 【函数转化为可 分割的线性函数，为此此算法又引入了以下参数： ：节点，和其父亲节点石之间的所有链路集合： 爱：流经链路z 的所有直接分支节点和接收端的集合； r ：根节点为，的所有接收端，其中，为分支节点； z ，：分支节点，的速率，一m a x ，配x ，； a 和足都是保证算法收敛的步长因子。 因此限制条件( 2 1 ) 变为：商_ sc ，。问题p 即可由迭代算法求解。其分布式 算法与上述算法类似，只是传递的包中的变量改变了，其含义也改变了，f c p 改变 为c p ( c o n g e s t i o np a c l 【c t ) ，其中包含的变量为拥塞因子f ，b c p 变为r p ( r a t e p a c k e t ) ，其中包含的变量为速率i 。 其具体的分布算法如下： 硕士学位论文 m a s t e r st h e s i s 源端s 的算法： 如果接收到一个r p ： 1 读其i 区域知道其孩子节点所要求的新速率； 2 发送一个c p 包到其孩子节点，并将包的f 区域设为0 。 接收端r 的算法： 如果接收到一个c p ： 1 读其f 区域得到其当前的拥塞代价 2 发送一个r p 到其父亲节点，将其i 区域设为j ，。 周期性地： 1 更新接收端的速率： z ，- x ，+ 札l o ，) 一印， 其中p ，是当前节点，的拥塞因子的估计值，如果z ，t 6 ，则z ，一6 ，如果x ，占， 则x ，一丑，。 分支节点r 的算法： 如果接收到一个c p ： 1 发送一个c p 包到其所有的孩子节点，按如下规则设置其中的f 区域： ( a ) 选择集合c ，。( 孩子节点中要求最大速率的节点集合) 中的任一节点，将其f 区 域的值设置为从父亲节点来的c p 包的f 区域的值： ( b ) 设置所有其他孩子节点的c p 包f 区域的值为o 。 如果接收到一个l l p ： 1 读其牙区域知道其孩子节点所要求的新速率； ( a ) 根据x ，_ m a x ，雹z ，更新其速率。 ( b ) 根据c 严一 r ：z ，- - x ， 更新集合c ? “。 2 接收到所有其孩子节点的r p 包后，发送一个r p 包到其父亲节点，设置其牙为z ，。 图2 4 可扩展的，低代价的多速率组播分布式算法 此算法较前一种算法的好处在于，其选用了代价因子，只需要传送o 或1 ，甚 至可以通过e c n 来实现，减少了网络运行的代价，扩展性更好，而且其存储的变 量为节点的真实速率，使得算法更为精确，算法的收敛性更好，同时也考虑了如果 接收端的速率无法连续变化的情况如何执行。但此算法最大的缺憾仍然在于没有考 虑t c p 友好性。 1 4 顾士学位论文 m a s t e r st h e s l s 2 1 3 公平资源分配的多速率组播拥塞控制算法 此算法f 2 6 】同样是求解问题尸，考虑到当n 足够大时， 因此将问题p 转化为： p ”： m a x 荟u 。，) 受制于： 一( 魁f 。 ) i s c f v f 三 x ，盖，v r r ( 2 5 ) ( 2 6 ) 此算法是根据文献【2 0 】的速率变化和l y 叩岫o v 函数的关系得出的启发式算法， 具体的分布式算法如下：( 此算法仅写了当源端向接收端发包时，链路，分支节点 和接收节点的算法，省略了接收节点向源端反馈的算法) 如果包的e c n 位为l ，就称其为标记了的包。 链路f 的算法： 假设链路f 有个自变量为链路中所流经的总速率的标记函数p f ( ) 如果接收的包 的e c n 位为o ，则以概率p f ( 设置包的e c n 位为1 ，否则不改变包的e c n 的值。 分支节点的算法： 接收到个标记了的包后，将其发送到任意一个与当前分支节点速率相同的孩子 节点，然后将此包的e c n 标记改为o ，再转发到其余孩子节点。 接收节点的算法： 每个接收端都估计其所接收的标记了的包的数目。如果让帆) 表示在时隙 以，2 i “】内收到的标记了的包的数目，则m “) ，( f m k ) 就可作为标记的包接收 的速率的估计值。 接收端的速率根据如下公式更新： 斗“+ 1 ) - m 缸p r j r 以) + 6 ( 1 一z 彘竺字与) ，其中6 “川- f t ，是速 率更新的时间间隔，口为足够大的一个正数。 图2 5 公平资源分配的多速率组播分布式算法 此算法的稳定性得到了理论上的证明，同时此算法利用e c n 来传递拥塞信息， 代价较小，易于扩展；此算法的中间节点仅需存储要求速率最大的孩子节点，易于 实现，此算法也考虑了t c p 友好度，声称当选择合适的参数时，其能达到t c p 友 好；同时此算法考虑了当接收速率离散时的执行结果。此算法较前面两种算法要更 硕士学住论文 m a s t e r st h e s i s 为完善一些，但是其参数的选择更为复杂些，而且由于其用到了当n 足够大时， 1 ( 罗，z ：) 1 一m a x ，o ，) 这一近似估计，使得此算法不够精确，且中间节点的存储仍 需要路由器进行一定的改进。 对于上面介绍的三种算法将其归类于源端驱动的算法可能有所争议，因为这三 种算法的接收端都根据网络拥塞状况调整了接收速率，可能不能完全算是源端驱动 的，更接近于接收端驱动源端调整的算法，不过由于它们都是从单播的源端驱动的 优化算法扩展而来，而且它们与后面接收端驱动的算法或接收端驱动源端调整的算 法的实现方式也有很大的不同，故此我们还是将它们放在源端驱动的算法中介绍。 基于优化的多速率算法不限于已介绍的三种，如文献1 2 7 j ，就给出了一个基于市场和 代价的优化算法。不过从上面三种优化算法的分析可知，基于优化的多速率组播算 法首先要是收敛的，即能使网络从拥塞中恢复，也即要有个合适的接收端速率更新 算法，同时考虑如何将网络中的拥塞状况信息( 一般通过代价方式) 反馈到接收端 的速率更新中；最后即是该算法的代价，性能和t 1 四友好度。注意到这三种算法都 是先从解纯粹的优化问题的角度出发，然后对其中的变量和实际问题相连，赋予合 适的解释，从而使得算法的求解有其针对性和实际意义。 下面我们还将介绍一种不是基于优化求解的源端驱动的多速率组播算法。 2 1 4s a m m ( s o u r c ea d a p t i v em u i t i l a y e r e dm u i t i c a s t ) 文献【”l 介绍了基于网络的s a m m 和端到端的s a m m 两种算法。由于基于网络 的s a m m 算法有潜在的实施困难，这里就主要介绍端到端的s a m m 算法。 & w m 算法用到了分优先级传输，在这种方法中，源端按照重要性将各层分成 几个优先等级，在拥塞情况下，路由器最先放弃低优先级的分组，这种方法非常稳 定因为高优先级的分组总是被保护得很好。另外，s a m m 要求路由器能实现“流 独立( n o wi s o l a l i o n ) ”，即区分开s a m m 流和其他流，从而避免了s 蛳m 流对t c p 流的吞吐率所产生的不利影响，这样就实现了t c p 友好性。 s a m m 算法中的源端依照接收端带宽报告调整分配的层数和各层的速率，为了 避免反馈风暴，这些带宽报告不是直接从接收端送到源端而是送给最近的反馈聚合 者( f e e d b a c km e r g c r ) ，这些反馈聚合者将在将反馈信息转发给源端之前利用启发式算 法来