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

摘要 组播是因特网的新型网络技术，利用组播传输多媒体数据可以节约大量的带宽，并 且它是一种解决点到多点通信的非常有效的方式。因此组播在视频会议、远程教学等系 统中被广泛应用。然而，基于u d p 协议的组播都不提供拥塞控制机制，导致这些业务和 t c p 业务共存时出现了带宽占用的不公平性，因此组播拥塞控制便成为一项重要的研究 课题。 基于接收端驱动的分层组播工作模式是源端仅负责以固定的多个速率发送数据，而 接收端根据网络拥塞状况选择自己合适的接收速率接收数据。本文分析了基于接收端驱 动的分层组播拥塞控制中现今存在的若干问题，研究了相关工作，在此基础上提出了一 种改进的的接收端驱动的分层组播拥塞控制算法一i r l m c c ( i m p r o v e dr e c e i v e r d r i v e n l a y e r e d 酗u l t i c a s tc o n g e s t i o nc o n t r 0 1 ) 。 首先将g a i 肋算法引入到该算法的拥塞控制策略中，它模仿t c p 的a i 如拥塞控制 算法，有利于保证t c p 友好；通过参数调节，在保证t c p 友好的前提条件下提高了系统 的响应速度。 其次设计了一个无反馈的基于接收端驱动的拥塞信号检测策略，缓解了源端的负 担，解决了反馈爆炸问题，同时避免了反馈处理带来的协议复杂性，提高了分层组播的 可扩展性。 最后通过仿真实验来评价算法的性能，用n s 2 进行模拟实验。实验主要集中于 i r l 肼c c 的公平性、吞吐量、可扩展性等方面评价。 关键词：拥塞控制：分层组播； i r l m c c ；t c p 友好 a b s t r a c t m 缸c a s ti san e wn e t w o 呔t c c h n o l o g yi nh t c m e i tc a ns a v e 砌c hb a n d w i d 也b y 仃j m 跖面痂喀m l l l 缅c d i ad a t a ，s u c h 硒、，i d e o c o n f h c e 觚d 姗o t et c a c h i n g s o i ti s c o n s i d e r e d鹤锄e 街c i e n tm e a n st 0圮s o l v e 拙峙 c o m m m l i 训p b l e m s o f p o i n t 珏删们廿p o i n t b u tm i l l t i c a s tb 勰c d u d pc 锄1 0 to 脑c o n g e s t i o nc o n n d la t 血e 雕s e m m e ，t h a l 耐s t i n gt c pa p p h c a t i o 璐，勰t h em a j na p p l i c a t i o mi i lt l l eb t e m c t ， o 饪打 c o n g e s t i o nc o 删h a v em a d ei ti m p o i t a mt o 即脒m ef 抵豁w h e n 加幽c a s tc o e ) 【i s t s 触 t c p 胛呦c o l s t h e 删o t h e s e a r c h 吼i n i c a s tc o n g e s t i c 伽仃o l i s b c c o m i n g 蛆 i n l p 讲恤t 州e c t t h ep r i 丑c i p l eb a s e do nr e c e i v 盱d r i v 阻l a y e r e dm l l l 矗c a s tc o n g e s t i c 们l i st h a tt h e s e n d e ro n l y n d sd a l aa taf i x e dm t e ，锄d 曲峙r e i v e r sr e c e i v e 咖砒af h t i n g 确t ea c c o r d i n g t ot h cp 湖tc o i l g e s t i o ns t a _ c i l e t l l i sp a p 盯a n a l y 猫m ee 对s t i n gp r o b l e m sb f 嘲mo nt h e r e c e i v * d r i v l a y e r c d 删6 c a s tc o n g e s t i c o 蛐r o la tp r e m f i n gt h e q u e s t i o 璐m p r c s 伽临ai m p f o v e dr e i v e r - “v e nl a y e r o dm 枷c a s tc o n g e s 6 0 nc o n t r o la l g o r i t h m 一 环工m c c ( h n p r 0 v e dr e c e j v 埘v c l ll a y 即c dm u l t i c a s tc o n g e s t i o nc 0 蛐1 ) f i r s t l y ，t h i sm u l t i c a s t n g e s “o nc o m la l g c 哦t h 芏na d j m ；t s 舡na l i c ! m a ：c c s 托倪“i n g 船l e b yg a m a l g o r i t h m 鹤t oa v o i dc o n g c s t i o 几g 帅a l g o 删m 锄l l l a 【e sa m m a l g o r i m m ，w h i c hh a v eb e e n 耐d e l yu di nt c pp r o t o c o l s nc 锄衄s u t l 黼m e 鹳w h 哪m c a s tc o e ) 【i s 协谢t ht c pp r d t o c o l s b ya d j u s 廿n gp a 姗c t e r s ，i tc a ne n l l a n c em es y s 咖s r e s p d i l l gs p e c d 唧d e r 也ec o n d i t i o no f t c p 伍c n m y s e c o n d l y t h i sp 印髓p r e 涮豳a 姗c h a i l i s mo fc o n g e s t i s i 霉l a ld 酏硎o n 蒯的m f e e d b a c ki n l p l o s i o n s ot h i sa l g o r i m m 翎l i g 龇e nt h e n d e r sb u r d s ，缸也es 锄e 血n e ，i t m a l 【e 也ep r o t o c o l sm o m s i m p l e 姐ds c a l d b l e f i l l a l l y ，n s 2 ，a 诵d e l yu s e dn 酣o r ks i 枷l a t i o nt o o l ，i sl l s e dt 0 觚a l y a n d v a l i d a ：t cm e p 蚓b m 瑚i c eo fa 1 9 0 r n h r 璐o nt t i c 船p e c t so f f h i r l l e s s 、m r o u g h p m 、s c a l a b l e 越d o m k e yw o r 凼：c o n g 鹤t i 0 c o n t m l ；l a y e r 蝴m u i t i c a s t ；i i 也m c c ；t c p 舾e n d l y 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 舡痔 日期：矽年f 月，口日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 鲚支涛 日期： 吵年r 月，。日 导师签名： 吼刁年j 自t u 日 1 1 研究背景 第一章绪论 i n t e r n e t 在近十年得到了迅猛发展，它深入到我们社会和生活的方方面面，从商务 到通信，从教育到娱乐。许多高带宽需求的多媒体应用不断产生，视频传输带来的网络 带宽问题更为突出。为了缓解网络的瓶颈问题，减轻主干网的负担，组播( 札l t i c a s t ) 技术由此产生。 组播业务是未来多媒体网络的重要业务之一。组播即将成为各种信息包括数据、图 形、话音、特别是音视频的一种传输机制，新出现的一些i p 业务如视讯会议、视频点 播和电子自板等多媒体应用要求网络将一个数据流传送给多个用户。智能小区的数字电 视接入系统是一个典型的基于组播技术的多媒体应用系统，它可以替代传统的有线电视 网络，使用计算机网络实现数字电视的用户接入。它的底层网络采用交换式以太网结构， 应用类型属于非交互式的实时多媒体应用，通信模式采用一点到多点的组播方式。 互联网上i p 组播机制的实施减少了网络上的通信流量，提供了对新的服务模式的 支持，更重要的是组播系统使大规模的网络业务不再因为负载和带宽的限制局限在传统 的局域网范围之内，而是扩展到整个i n t e r n e t 上，包括分布广泛的商业系统网络。 i p 组播技术有其独特的优越性：组播是一种将数据分发到大量接收者的有效方式， 与使用多个单播连接相比，组播会话可以大大减小数据源和网络的传输代价。在组搔网 络中，即使用户数量成倍增长，主干带宽不需要随之增加，这个优点使它成为当前两络 技术中的研究热点之一组播报文是通过u d p ( 用户数据报协议) 进行传输的，它缺乏 t c p 传输控制协议所提供的可靠传输的功能，所以必须对组播传输进行差错控制和拥塞 控制n 1 。 1 2 i p 组播工作原理 组播是一种允许一个或多个发送者( 组播源) 发送单一的数据包到多个接收者的网 络技术。组播源把数据包发送到特定组播组，而只有属于该组播组的地址才能接收到数 据包。简单地说，主机通过使用i n t e r n e t 组管理协议加入到组中，并且可以动态离开 组，即成员关系常有变化，路由器跟踪这种关系并试图形成一条到达组播成员的无回路 路径。 将i n t e r n e t 上的一些主机分成一个组播组，为每个组播组分配一个i p 地址，这些 主机通过组播路由协议( d v 胍p ，p i m 、c b t ，m o s p f 等) 构成一棵分布树，组播源发送目 的地址为组地址的数据包，路由器沿着分布树来复制和转发数据包，从而保证了从源刭 目的地的每条网络链路上同一数据包的只传输一次【4 1 。 组播可以大大的节省网络带宽，因为无论有多少个目标地址，在整个网络的任何一 条链路上只传送单一的数据包。 三种传输方式比较如下： 单播( u n i c a s t ) 传输：在发送者和每一接收者之间需要单独的数据信道。如果 一台主机同时给很少量的接收者传输数据，一般没有什么问题。但如果有大量主机希望 获得数据包的同一份拷贝时却很难实现。这将导致发送者负担沉重、延长网络拥塞时间。 为保证定的服务质量需增加硬件和带宽。 组播( m u l t i c a s t ) 传输：它提高了数据传送效率。减少了主干网出现拥塞的可 能性。组播组中的主机可以是在同一个物理网络，也可以来自不同的物理网络。 广播( b r o a d c a s t ) 传输：是指在i p 子网内广播数据包，所有在子网内部的主 机都将收到这些数据包。广播意味着网络向子网主机都投递一份数据包，不论这些主机 是否乐于接收该数据包。广播的使用范围非常小，只在本地子网内有效，因为路由器会 隔离广播通信。广播传输增加非接收者的开销。 从图1 1 中，我们可以看出组播与其它传播方式的不同。 a ： 网络单播传输方式b ： 网络组播传输方式 c ： 网络广播传输方式 图1 1 三种通信方式的传输比较 2 1 3i p 组播拥塞控制 i p 组播技术有其独特的优越性：组播是一种将数据分发到，滢接收者的有效方式， 与使用多个单播连接相比，组播会话可以大大减小数据源和网络的传输代价。在组播网 络中，即使用户数量成倍增长，主干带宽不需要增热，这个优点使它成为当前网络技术 中的研究热点之一。组播报文是通过u 】) p ( 用户数据报协议) 进行传输的，它缺乏t c p 传输控制协议所提供的可靠传输的功能。所以必须对组播传输进行差错控制和拥塞控 制。 ， 组播引入虽然节约了网络资源，减少了网络管理费甩，但同时也给i n t e 功e t 带来 了许多潜在的问题，例如：组播安全问题、拥塞控制问蘑、组播路由问题和错误恢复问 题等，而其中组播拥塞控制是所有问题中重要但又雉解决的一个闯题，同时也是最令入 关注的问题之一。如果组播应用不能对网络拥塞做出正确响应，将会给i n t e r n e t 带来 t 匕单播( u n i c a s t ) 投递应用产生的拥塞更为严重的影响。这主要因为：1 ) 组播数据流 可能沿着其多点投递树广泛分布于整个i n t e r n e t ；2 ) 组播数据流的接收方具有异构性， 每个接受方的处理能力不同，其分组投递路径也可能有不同的带宽和差错特性；3 ) 组播 发送方需要处理比单点投递多得多的反馈报文，对这些报文如果不加以处理，不仅可能 淹没发送方，而且它们本身也是对网络资源的一种极大的开销。 因此如今i p 组搐拥塞控制仍存在许多困难问题，如公平性问题、可扩展性问题等， 针对这些问题，近几年来出现了很多组播掘塞控制技术，本章介绍了组播拥塞控制中韵 关键技术和目前组播拥塞控制中较有影响力的拥塞控制算法，并对当前各种组播拥塞控 制算法进行了分析和比较，指出了其中存在的问题以及提出的一些改进措藏。 b e s t 吨f f o r t 服务模型和拥塞控制 传统的i n t e r n e t 使用b e s t e f f o r t 服务模型，所有分组受到同等对待，网络尽力 发送每个进入网络的分组，不保证服务质量( 吞吐量、端到端延迟、丢失率等) 。由于 i n t e r n e t 没有提供接入控制( a d i n i s s i o nc o n t r 0 1 ) ，用户获得的服务质量不仅取决于髓 络自身，也取决于其他用户在网络中产生韵负载，这使得整个两络完全缺少隔离和保护。 拥塞是一种持续的网络超负荷状态。当用户需求大于网络供给时，网络就会发生拥 塞。拥塞与b e s t e f f o r t 服务模型有紧密的联系，在i n t e r n e t 中用户无法协作共享 资源。多个用户可能对同一网络资源提出请求，从而导致拥塞。文献 2 使用图1 2 描 述拥塞。网络负载较小时，吞吐量与网络负载基本保持线性关系，网络延迟缓慢增加； 弼络负载超过第1 个关键点k n e e 后，网络吞吐量增长变慢。网络延迟增长变快；网络 负载超过第2 个关键点c l i f f 螽，网络吞吐量急剧下降，网络延迟迅速增加拥塞控制 的目标就是使网络在关键点e e 附近工作。 l c l i f f ， k n 图1 2 网络拥塞控制 i p 组播中的拥塞控制 s t e p h e n 在文献中描述了基于i p 的标准组播模型。i p 组播通过组播路由协议在网 络中建立组播转发树，转发树负责将发送端数据转发到接收端。然而与传统i p 相同， i p 组播不提供速率控制。因此，组播流量可能耗光所有的网络资源，导致网络拥塞。为 i p 组播设计合适的拥塞控制成为迫切需要解决的问题。i e t f 将组播分为两种模式：单 点对多点、多点对多点。后者在组播树生成和组管理等方面存在较大的难度，现阶段在 i n t e r n e t 上推广的希望不大，而且它可以通过多组单点对多点通信来实现。本文主要讨 论单点对多点模式的组播拥塞控制。 1 4 l p 组播拥塞控制基本问题 组播拥塞控制协议有很强的针对性，大部分协议都是针对某些特定问题提出的。在 单播通信中，t c p 协议可以满足很大范围内的应用需要，但是不同的组播应用对组播流 有不同的要求。例如，视频会议不要求保证可靠传输，但希望速率变化尽量平滑：文件 分发则要求保证数据的可靠性等等。各式各样的需求对组播拥塞控制协议的设计造成很 大的影响。i e t f ( i n t e r n e te n g i n e e r i n gt a s kf o r c e ) 和i r t f 已经取得共识：拥塞控制 协议不可能满足所有的需求，必须针对不同的应用设计不同的协议。i p 组播拥塞控制技 术的关键问题主要是可扩展性问题和t c p 友好问题即协议公平性问题，以及快速响应问 题，解决好这些问题，对组播拥塞控制技术将有积极的作用。 1 4 1 可扩展性问题 可扩展性是指随着组播翅模的增太，组播拥塞控制协议不会造成组播性能下降。它 是评价组播拥塞控制性能的一个重要指标。它主要受到三个问题的限制： 丢失路径多样化l p m 网问题在组播树中存在多条端到端的路径，一个传输的数 据分组可能在组播树的多条路径上独立地丢失即使发送端仅仅对每个包的一个丢失指 示l i ( l o s si n d i c a t i o n s 减小速度，发送端对每个传输的分组至少收到一个l i 的机会 将随着路径数口的增加而增大。那么当组播成员不断增加时这一组播会话的平均带宽会 趋于零，即带宽d r o 旷t o z e r o 问题【1 0 l 。适当的反馈聚合和反馈抑制可以减轻l 嗍问题 的影响，另外多速率分层组播拥塞控制也能很好地抑制这个问题。 反馈爆炸问题拥塞控制需要考虑所有组播组成员的拥塞状况，随着组播组的 规模增加，大量接收端的反馈可能淹没发送端，使组播组的性能明显下降。这个问题可 以通过适当的反馈聚合和反馈抑制来解决。 网络随机延迟的影响即使在非常理想的网络环境中( 网络中无分组丢失，路 由器缓存无限大) ，随着组播组规模的增加，稠络中随机分布的队列延迟( 路由器的服 务延迟) 也会给组播组的性能造成影响。因此，在大规模的组播组中，多速率分层组播 是更好的选择。 可扩展性除体现在接收端的数量上，伺时也要求组播拥塞控制协议能够适应网络 的异构性。连接在i n t e r n e t 等广域网的计算机往往是不同的，它们可能是个人计算机、 硬携式计算机、企业服务器、小型机等等，这些计算机具有不同的硬件结构和操作系统。 另外，网络的拓扑结构也是不尽相同的，所以一个好的组播拥塞控制协议要具有更好的 适应性，能够适应不同的网络环境。 1 4 2 协议公平性 在组播拥塞控制中，公平性( f a i r n e s s ) 是每个组播拥塞控制算法所追求的设计目 标之一，也是其可否得到广泛应用的基础之一。组播拥塞控制中的公平性主要表现在两 个方面： 协议内的公平性 协议内的公平性是指发送方在通信过程中对每一个接收方都按照同样的标准发送 数据包。在组播中，发送方的发送速率一般受到组中所有接收方的制约，而且通常是由 最差的接收方的发送速率来决定。 协议间的公平性 组播协议除了保证各种组播应用之间的公平性外，还应确保与其他行为良好的协议 公平分享网络资源，因此组播协议应该保证当组播流与t c p 流共享瓶颈链路时，双方可 以公平地占用网络带宽，公平地竞争资源。因此在制定组播拥塞控制标准时， i e t f ( i n t e r te n g i n e e r i n gt a s kf o r c e ) 要求组播拥塞控制算法必须做到t c p 友好， 即协议间的公平性。 目前网络中数据流多使用t c p 作为可靠传输协议，若组播拥塞控制与t c p 不同，可 能会导致两者无法公平地共享网络带宽，甚至可能因抑制t c p 流而导致整个i n t e r 舱t 的崩溃。 当前对于组播t c p 友好存在多种定义。文献 8 给出的一种定义是“非t c p 流量的 长期吞吐量不超过相同情况下1 仰流量的吞吐量” ， 1 ) 单播t c p 友好，是指在相同网络条件下，如果一个单播流量对其他并存t c p 流 量的长期吞吐量的影响( 减少) 不大于另外一个t c p 流量对后者的影响，此单播流量被认 为是t c p 友好。 2 ) 组播t c p 友好，是指在发送端与每个接收端之间，如果流量具有单播流量t c p 友好的特性，此组播流量被认为是t c p 友好。 值得一提的是，目前对于组播t c p 友好的定义还存在很多争论。有些定义指出，由 于组播流量为多个接收方服务，因此应该允许组播流量使用比单播流量稍多的带宽。 1 4 3 实现复杂度 组播拥塞控制需要处理源到不同接收者的多个路径上的拥塞，通常复杂度较高。拥 塞控制本身包括速率调整和拥塞检测等几个部分，拥塞检测和接收速率的选择通常由接 收者负责，而传输速率的调整由源端负责。但是为正确设置会话速率，源端需要处理不 同接收者的拥塞反馈，导致源端复杂度过高。 1 5i p 组播拥塞控制研究现状 对组播拥塞控制的研究兴起于9 0 年代后期，针对不同的应用出现了许多算法，按 调节参数的不同可以分为两类：基于速率拥塞控制和基于窗口的拥塞控制。 基于速率拥塞控制 很多基于速率的拥塞控制协议仅仅简单的模仿t c p 的a i 行为，而另外一些协议 则根据t c p 流量模型显式或隐式地调整发送速率。基于速率的协议在保证可扩展性上主 要面临两个难题：l p m 问题，防止反馈爆炸；为了保证t c p f r i e n d l y ，协议需要解决大 规模r t t 测量问题。与基于窗口的机制相比，基于速率的拥塞控制实现起来比较简单， 由发送者控制数据包的平均传输速度，根据网络拥塞指示来动态地调整传输速度。为了 保证t c p 友好性。许多基于速率的组播拥塞控制机制都利用对t c p 吞吐量的理论分析来 计算传输速度。分析了t c p 拥塞控制算法的理论吞吐量，将吞吐量作为数据包大小、r t t 、 包丢失率的函数。给出如下公式1 5 】： r = c ( 1 )r ( p ) = t m 、3 p ( 2 ) 其中t 代表吞吐量，p 表示丢包率，。指从源端发送数据包至收到接收端确认的 时间间隔，有时也称作r t t ( r o u n dt r i pt i m e ) ，s 指数据包的大小，b 表示每个a c k 确 认的包的个数，通常为2 ，c 是在0 8 7 到1 3 1 之间的常量，取决于a c k 的利用率与测 量丢失事件的周期。这些公式通常用在组播拥塞控制机制中作为计算速率的参考。 1 9 9 8 年m h a n d e l e y 和s f l o y d 提出的t f m c c 针对基于n a c k 的协议， 6 t 眦c ( t c p - f r i e n d l y 咖l t i c a s tc o n g e s t i o nc o n t r 0 1 ) 1 6 j 是对t f r c 协议的扩展。t f r c 堤一个针对多媒体应用的单播拥塞控制协议，t f l l c c 将它扩展到组播中。与t f r c 相同， 1 f i l c c 也基于复杂的t c p 流量模型调整速率。接收端使用平均丢失间隔算法( a v e r a g e 1 0 s si n t e r v a l 舱t h o d ) 计算丢失率。协议还使用额外的机制防止接收端对单个丢失事 件反应过于强烈，同时保证丢失率能迅速适应长期无分组丢失的情况。启动后，发送端 立刻进入慢启动阶段，通过快速地增加速率获得公平共享带宽。第1 个丢失事件发生后， t 眦c 终止慢启动。 1 f m c c 给出了一种大规模测量l m 的方法：发送端在数据分组中携带时间标记 ( t i m e s t a m p ) ，接收端根据时间标记计算r 1 u r 。接收端根据r t t 、丢失率和t c p 流量模型， 计算出速率并反馈给发送端。发送端从中选出一个瓶颈接收端作为代表，t 眦c 称之为 c l r ( c u r r e n tl i m i t i n g r e c e i v e r ) ，此后仅根据c l r 韵反馈来调整速率。c l r 减轻了屯明 闯题带来的影响。另外，为了舫止反馈爆炸，协议使用指数加权随机时钟来抑制接收端 的反馈数量。t f 峨的主要缺点是，在起始阶段，接收端的硼盯初始化需要耗费较长的 时间另外，如果选择了错误的代表，可能导致组播流量的t c p - u n f r i e n d l y 行为。 1 9 9 8 年x l i ，s p a u l ，a n dm 加啦掰提出了基于反馈的分层视频组播l v 陬1 丌， l v 豫( l a y e r e dv i d e o 跚l t i c a s t i n g 耳i t hr e t r a n s m i s s i 锄s ) 是一个为尽力而为的异步 网如i n t e r n e t 上的分布式押e g 编码设计的算法。它使用与j l i l m 僻】类似的方法将视频信 号分层，并分层传送。其主要贡献在于：首先是在层次性的网络中使用分布式n g e n t ，这 些a g e n t 主要用来协调接收端加入或离开的决定，8 9 e n t 之间使用t c p 连接来交换信息 但其带来了大量的带宽开支，特别是在实时视频中。同时该算法并没考虑t c p 友好度和 多个组播组之间的公平性。 1 9 9 6 年s m c c 柚n e ，v j a c o b s a n dm v e t t e r l i 提出了接收端驱动的分层组播。 捌瑚( r e e e i v e r d r i v e n1 8 y e r e d 黜l t i c a s t ) 吲是在分层组播方面最早的工作之一，是第 一个面向实时组播流的、t 端到端的、基于接收端的速率控制算法，被普遍认为是解决视 频组播异构性的最佳方式。然而r u t 没有考虑t c p 友好性，通过判断丢包来加入或退出 一个层次的机制可能导致当前r l m 各个组播组之间带宽分配的不公平 4 9 9 8 年，lv i c i s a n o ，l r i z z oa n dj c r 伽c r o f t 提出了接收端驱动分层拥塞控制 赳c ( r e c e i v e r d r i v e n1 a y e r e d o n g e s t i o nc o n t r 0 1 ) 瞄l ，并对r 珊进行了很大的改进。 为了达到驰p 友好，：r l c 提出一种层分配方案：按指数递增分配每层的带宽。通过这种 分层方案和等待时间机制，乳m 模仿了t c p 的矗i 胁行为。从丽提高t c p 友好性。罚时这 种层分配方案减少了编码复杂度和层的数量。 但是由于r l c 算法基于指数分层的策略只允许接收速率加倍或减半，所以其调整速 率粒度较粗糙，使接收端无法充分利用带宽。另外r l c 的s p 点是周期性的，r l c 仍然是 采用突发周期来探测带宽而加入新层的。这样可导致大量数据丢失。同时也不利保证t c p 友好。 7 2 0 0 2 年s f l o y d 等提出了t f r c 【5 l ，这些工作为基于速率的组播拥塞控制奠定了基础。 t f r c 是对单播u d p 的t c p 友好控制算法，采用t c p 吞吐量的复杂公式来调节发送速度， 其中部分速率调节机制和一些参数估计的方法和思想可以借鉴。 基于窗口的拥塞控制 目前基于窗口的组播拥塞控制算法主要是通过接收方或发送方维护一个拥塞窗口， 模仿个c p 通过a i 岫窗口调节进行拥塞控制。与t c p 类似，发送一个数据分组会占用拥塞 窗口的一部分，收到一个分组的应答后会释放占用的部分；拥塞窗口有空闲时，发送端可 以继续发送数据。没有拥塞时，增加拥塞窗口；拥塞发生时减小拥塞窗口。以便保证t c p 友好性。为了将基于窗口的拥塞控制机制推广至组播，必须解决丢失路径多样化l 蹦 ( l o s sp a t h 舢l t i p l i c i t y ) 问题【”和反馈爆炸( f e e d b a c ki m p l o s i o n ) 问题。 与t f m c c 类似，2 0 0 0 年l r i z z o 提出的p g m c c 算法( p r a 鲫a t i cg e n e r a l 舢1 t i c a s t c o n g e s t i o nc o n t r 0 1 ) 捧j 也是一种基于代表的拥塞控制协议。协议从组成员中选择一个瓶 颈接收端作为代表，负责对每个接收到的分组进行确认，这种机制允许在发送端和代表 之间使用与t c p 类似的拥塞控制。在基于代表的算法中，拥塞控制和分组修复彼此之间 是互相独立的，因此这种方法不仅适用于不可靠传输，也可以与可靠性机制结合起来。 基于代表的最大闷题是如何挑选出合适的代表。在p g 婀c 中，每个接收端使用t c p 流量模型计算出期望的速率，由n a c k 将速率期望值携带到发送端；发送端将拥有最低 速率期望的接收端选为代表。 基于代表的技术使p g m c c 避免了l p m 问题和反馈爆炸问题。如果选择了正确的代表， p g m c c 可以很好地保证t c p f r i e n d l y 。问题在于p g m c c 仅仅根据接收端粗略的速率估计 来选择代表，如果选择了错误的代表，将会对算法的性能造成很大影响。 1 9 9 9 年i r h e e 等提出的册c p ( m u l t i c a s tt c p ) 算法【9 j ，是一个针对可靠组播的拥塞 控制协议。协议生成棵多级的逻辑树，逻辑树的树根是发送端，树的其他节点是接收 端。在逻辑树中，父节点负责处理子节点的反馈和丢失分组的重传。子节点向父节点发 送两种反馈：a c k 或n a c k 。每个父节点维护两个窗口：拥塞窗口和传输窗口。对拥塞窗口 的管理与t c p 类似；传输窗口负责跟踪还没有被子节点确认的分组。 使用反馈树来聚集来自接收者的反馈，并由接收者进行类似t c p 的窗口调节，提高 了算法的可扩展性，但是建立和维持树状比较复杂。值得指出的是，基于窗口的调节容 易引起数据的突发性，不适合组播的环境。因此当前许多可靠组播拥塞控制研究都采用 基于速率的杌制来调节通信。 1 6 i p 组播拥塞控制发展趋势 组播拥塞控制是一个新的领域【3 l ，尽管取得了很大进展，但还有许多问题急待解决， 未来的研究可以在以下几个方面进行。 1 ) 基于组播树的组播拥塞控制 一些组播拥塞控制协议使用基于树【4 l 】的技术，接 8 收端被组织到一个树型结构中，例如t r 删协议中的修复树。为了简化协议设计和实现， 这些协议使用底层组播路由协议产生树型拓扑，但拥塞控制属于传输层协议，很多情况 下无法直接获得网络层的路由信息。而且，是否应将组播拥塞控制放到网络层，与路由 结合，这是一个值得研究的问题。 2 ) 多速率机制的改进在上面的讨论中，可以看出多速率机制在扩展性和公平性 方面比单速率有很大提高，但其设计相对要复杂，实现要困难的多。因此如何利用新的 或己有的技术来简化多速率组播拥塞控制的复杂性是目前一个有很大研究价值的课题。 3 ) 基于模型公式的控制算法在一些基于速率的拥塞控制机制中使用了t c p 通信量 的模型公式来计算速率，但模型公式的推导过程本身存在许多人为设定的条件，这些前 提假设在真实的组播环境中不经常遇到【4 2 】，此外，应用模型公式进行拥塞控制。其中参 数的估计也比较困难，算法中要求每个接收端都要精确估计往返时间r 1 v r ，丢失率等参 数，这对于普通异质的组播接收端来说，在短时间内是很难做到的。，如何进一步弱化这 些参数估计对算法的影响，提高算法韵可扩充性也是一个值得研究的问题。 4 ) 分层组播的研究分层组播可以不受瓶颈接收端的限制，在可扩展性上比单速率 的组播拥塞控制占有优势。分层组播在组播路由密集模式下工作很好，但是i n t e r 脯t 的层次化使密集模式不适合大规模的应用1 4 3 】。相比之下，稀疏模式组播路由协议更适合 i n t e r n e t 。但是在稀疏模式中，组播树可能由于网络的拥塞，l 出现共享树到源树的互相 转换，在这个过程中，分层组播频繁的加入与离开操作可能造成路由协议进入不稳定状 态刖。如何使稀疏模式与分层组播拥塞控制更好的结合，是一个需要研究的问题。 5 ) 应用层组播应用层组播的基本思路是在应用层建立发送端和接收端之间的逻 辑树。也就是由应用层负责组播路由。这种技术将组播的复杂性从网络转移到端系统， 这种策略符i n t e r n e t 豹设计思想，：而且它赢接使用传统的单播拥塞控制，避开了组播 拥塞控制的难题。应用层组播最主要的问题是如何合理的建立逻辑树，这类似于传统的 组播q o s 路由问题。 1 7 本文的主要内容及创新点 本文分析了现今基于分层的组播拥塞控制中存在的若干问题，研究了相关工作，在 此基础上提出了一种改进的的接收端驱动的分层组播拥塞控制机制一i r 瑚c c ( i 叩r o v e d r e c e i v e r d r i v e nl a y e r e d l t i c a s tc o n g e s t i o nc o f l t r 0 1 。 本文主要创新点： 将g a i 如算法引入到本文的拥塞控制策略中，好处有：第一，它模仿牝p 的a i 髓 拥塞控制机制，有利于保证t c p 友好；第二，通过参数调节，在保证t c p 友好的前提条 件下减少了组播的速率抖动，提高了速率的平滑性。 设计了一个无反馈的基于接收端驱动的拥塞控制策略，在设计中增加r t t 测量， 细化了时间粒度，同时通过利用丢包数来判断网络拥塞状况，而不是向服务器发送网络 9 拥塞的反馈信号来调整速率，避免了反馈处理带来的复杂性，解决了反馈爆炸问题， 提高了分层组播的可扩展性。 最后本章通过仿真实验来评价算法的性能，用n s 2 进行模拟实验。实验主要集 中于i r 眦c 的公平性、可扩展性及协议平滑性等方面。 本文的主要内容如下： 第一章：介绍i p 组播的工作原理以及现今i p 组播存在的问题。 第二章：对i p 组播拥塞控制机制做了针对性研究，阐述了i p 组播三个基本问题： 可扩展性，协议公平性及实现复杂度。最后分析了基于速率的组播拥塞控制，以及组播 拥塞控制今后的发展方向。 第三章：重点研究了基于接收端驱动的组播拥塞控制的原理，分析目前对该拥塞控 制机制所做的研究工作和不足之处。 第四章：有针对的设计了一种改进的的基于接收端驱动的拥塞控制算法，主要解决 组播反馈爆炸问题，并使该算法达到t c p 友好，提高系统响应速度。 第五章：使用n s 2 对该算法进行了仿真实验，实验表明，本文设计的组播拥塞算法 基本达到了预先提出的要求。 l o 第二章 ip 组播拥塞控制方法分析 目前，组播拥塞控制中存在许多困难问题，如公平性问题、司扩展性问题等，针对 这些问题，近几年来出现了很多组播拥塞控制技术，前章介绍了组播拥塞控制中的关键 问题和目前组播拥塞控制研究的最新进展，在此基础上本章重点讨论了组播拥塞控制算 法的分类标准，并对比较典型的几种分层组播拥塞控制算法进行了分析和比较，指出了 算法的研究目标以及组播拥塞控制算法现存的若干问题 2 1组播拥塞控制算法分类 拥塞控制算法可以根据多个标准进行分类如果按照数据发送的方式来分类，组播 拥塞控制算法可以划分为：基于单窗口和多窗口的组播拥塞控制和基于单速率和多速 率的组播拥塞控制：如果按照控制算法的驱动方式可以划分为发送方驱动的组播拥塞控 制和接收方驱动的组播拥塞控制。下面我们将讨论组播拥塞控制的分类标准。 2 1 1单窗口和多窗口组播拥塞控制 单窗口组播拥塞控制f 9 l s l 是指发送方面则只需维护一个发送窗口。在多窗口组播拥 塞控制中【 捌，发送方需要为每个接收方维护一个窗口，从而可以在接收方和发送方之 间产生灵活的带宽分配。 基于单窗口和多窗口的组播拥塞控制与t c p 中窗口机制类似在组播窗口拥塞控制 机制中，在端系统设立窗口，通过窗口来控制未应答的分组数目，窗口的维护由端系统 来完成每发送一个数据分组，窗口的一部分会被占用，直到此分组的a c k 信号收到后 才会释放。当窗口有空闲时，发送方可继续发送数据，没有拥塞时增加窗口数；发生拥 塞时则减少窗口数目。发送方始终要保证被所有接收方确认的报文个数小于窗口的大 小。在基于单窗口和多窗口的组播拥塞控制中，不需要估计r t t ，只需要采取与t c p 类 似的行为，就能保证组播流的t c p 友好 单窗口组播拥塞控制中，一般发送速率和窗口的数目受到具有最差的接收方( 即发 送速率最慢的接收方) 的制约，而且整个组播组的吞吐量会受到拥塞最严重的接收方( 瓶 颈接收方) 的限制。 在多窗口组播拥塞控制中，多窗口传输虽然能有效利用网络资源，但由于发送方器 要维护大量的窗口及不同的缓存数据，在由单播向组播扩展时，为了使组播吞吐量最大， 发送方需为每个接收方维护一个独立的窗口；随着组规模的扩大，发送方需维护的窗口 数增多，拥塞控制任务变得十分复杂，可扩展性差；而且如果发送方接收所有接收方的 反馈，易产生反馈风暴。此外，所有基于窗口的拥塞调节算法均需将拥塞控制与数据恢 复结合在一起，大大地增加了算法的复杂度。 2 1 2 单速率和多速率组播拥塞控制 单速率组播拥塞控制1 3 州是指发送方只按一种速率来发送数据；在多速率组播拥 塞控制中【2 6 】，发送方可使用多种速率来进行数据发送。 基于单速率和多速率的组播拥塞控制所调整的拥塞控制参数是发送速率 ( t r a n s m i s s i o nr a t e ) 。拥塞控制算法根据网络的状态调整发送速率，使其不超过某个 期望值。一般在组播中这种拥塞控制的实现方法与单播通信中类似。为了实现协议间的 公平性，通常有以下几种常用的方法： 1 ) 用a i 岫算法运用于组播拥塞控制洲：这种方法与t c p 协议中a i 如( a d d i t i v e i n c r e a s ea n dm u l t i p l i c a t i v ed e c r e a s e ) 行为类似。这种方法实现起来虽然十分简单， 但速率在短期内易出现与t c p 相似的锯齿形。 2 ) 基于稳态下t c p 响应函数的拥塞控制i l2 1 4 ，1 5 t 1 6 】：为了保持速率变化的平衡性，实 现与t c p 公平共享网络带宽，并且不失对拥塞进行响应，可采用稳定状态下t c p 速率响 应函数作为其响应函数。 利用基于速率的组播拥塞控制，可以不需要像基于窗口的组播拥塞控制那样维护窗 口，而且在单播或组播中的实现方法类似，可扩展性好。但是这种方式必须测定r t t ， 在组播中测量r t t 比在单播中复杂的多：发送方也需从接收方收集控制参数，若不采取 适当的反馈抑制机制，发送方也会遇到反馈风暴问题。 由上可知，利用多速率、多窗口拥塞控制可以比较有效的利用网络的资源，但是其 协议过于复杂，系统开销较大；为提高拥塞控制的能力，在设计时需要考虑并解决决策 同步的问题。在组播组规模扩大时，拥塞控制的粒度比较粗糙，接收方对带宽的利用率 低，难以保证t c p 友好。 在使用基于单窗口、单速率组播拥塞控制时，系统的可扩展性比较好，实现起来比 较简单，无需向多速率和多窗口组播拥塞控制那样，考虑对数据的分层、编码，以及决 策同步等问题。但是，在这种方法中，一般以最低速率发送数据，因此对于具有较高带 宽的接收方是不公平的，即使在网络比较理想的情况下，随着组播规模的扩大，采用这 种方法会比较严重的影响组播的性能。 2 1 3 发送方驱动和接收方驱动组播拥塞控制 发送方驱动的组播拥塞控制方式【1 1 1 8 扎3 2 柏1 与t c p 协议类似。拥塞算法放置在发送 方，每个接收方按照一定的时间周期向发送方发送反馈报文，发送方则从反馈报文中获 取有关的信息，并以此来调整发送速率。在这种方式中，发送方需接收并处理大量的反 馈报文，极易发生反馈爆炸。为解决此问题，目前有一种采用基于代表的方梨3 1 1 来减少 1 2 反馈报文的数目，捏却需增加额外的网络设备或向现有网络设备中添加复杂的归并算 法，因此并不能从根本上解决伸缩性问题。 利用发送方驱动的组播拥塞算法，发送方能及时地了解整个组播组的状况，并可以 做出响应。但是在发送方需要处理大量的反馈报文，并且要进行大量的计算，开销过大， 容易造成网络瓶颈，可扩展性较差。 在接收方驱动的组播拥塞控制中。3 5 筇删，数据被组织成不同的层次，发送到不同 曲晚播组。接收方根据当前网络情况定阅适当的层次在这种方式中大量的计算任务交 由接收方完成，减轻了发送方的计算开销。 但是接受方驱动的组搔方式中也存在不少缺陷f 3 7 鳓螂： 1 ) 在进行大数据传输时，对数据不易自然分层而且为了数据的嗷性和有序性， 分层难以实现j 2 ) 由于编码和译码的复杂性，可用层次数较少，咽此会限制拥塞的自适应范围l 3 ) 当接收方加入和离开组播组时，会增加系统的开铺，丽且会过分依赖组播路由 协议l | 4 ) 大多数接收方驱动的协议中主要通过n k s ( g a t i v e 丑c k n 沛l e d g 瞻n t s ) 来确定 网络拥塞程度，如果发送方没有收到反馈的剞a k s ，坝q 有可能错误地推断网络无捆塞或拥 塞己清除； 哪