（电路与系统专业论文）可靠组播网络中差错恢复算法的研究[电路与系统专业优秀论文].pdf

鬻塞瓣电犬擎鞭圭研究生学位论文撬要 摘要 组播是在标准i p 技术上的一个扩展，其主要鳃特点是通过i p 组播地址囱一个主机组发 送数据。组播技术从本质上减少了对网络带宽的需求，克服了集中式会话中服务器负载随 客户数目增加丽急剧加重的阅题。组播的缺点是不可靠和无序，但是基于组播的各秘掰的 应用，例如多媒体会议、数据分发、交互式仿真等都要求可靠的组播传输。可靠组播( r e l i a b l e m u l t i c a s t ) 的目标就是要解决这些阀题，除了宠成基本的组播功能，可靠组搔协议还必须 针对差错控制、差错恢复、流量控制、拥塞控制和端到端的延迟等问题提出解决办法。 在组播可靠性的众多技术领域中，差错检测与恢复技术也逐渐成为当曩 研究的热点， 本文首先介绍了差错检测与恢复的各种方法和机制，以及一种具有较好可扩展性的差错恢 复算法r r m p ，分析了r r m p 算法的些优点，比如，把差错恢复的负担随枫地分配到组 成员，从丽避免了一些可靠组播协议中所用到的专用恢复服务器负担过重及意外故障造成 丢包丽无法恢复等闯题。但是r r _ m p 算法也存在一些不足，当一个域中的戏员检测到丢失 时，它将同时启动本地恢复过程和远程恢复过程，这样不仅浪费了带宽，而且也存在较大 携时延。针对这个潮题，本文在r 1 l v i p 算法的基础上提出了一群改进算法e r r m p ，该算 法中增加了数据丢失类型判断机制，有了这种机制后，当一个成员检测到丢失后，它要么 盛动本地恢复过程，要么窟动远程恢复过程，丽不需要两个过程都同时启动。这样就减少 了丢失请求包和恢复包的通信量，从而节省了带宽，也降低了时延。最后通过实验进行仿 真，仿真懿结果验证了这些绪论的正确性。 关键词：可靠缰播，随枧，差错獗复，n a c k ，本地域，丢失类型 南京邮电大学硕i j 研究生学位论文a b s t r a c t a bs t r a c t m u l t i c a s te x t e n d sf r o mt h es t a n d a r di pt e c h n o l o g y ，i t sm a i nf e a t u r ei si tc a ns e n dd a t at oh o s t g r o u pt h r o u g hi pm u l t i c a s ta d d r e s s m u l t i c a s tt e c h n o l o g yr e d u c et h ed e m a n do nn e t w o r k b a n d w i d t hi nn a t u r e ，s o l v et h ep r o b l e mt h a tt h es e r v e rl o a da g g r a v a t es h a r p l ya l o n gw i t ht h e i n c r e a s ei nt h en u m b e ro fu s e r si nc e n t r a l i z e dc o n v e r s a t i o n t h ed i s a d v a n t a g e so fm u l t i c a s ta r e u n r e l i a b l ea n do u t o f - o r d e r , b u ts o m en e wa p p l i c a t i o n sb a s e do nm u l t i c a s t ，s u c ha sm u l t i m e d i a c o n f e r e n c e ，d a t ad i s t r i b u t i o n ，i n t e r a c t i v es i m u l a t i o na n d s o o i l ，r e q u i r e r e l i a b l em u l t i c a s t t r a n s m i s s i o n t h et a r g e to fr e l i a b l em u l t i c a s ti st or e s o l v et h e s ep r o b l e m s i na d d i t i o nt o c o m p l e t i n gt h eb a s i cf u n c t i o n s ，s o m ea p p r o a c h e sm u s tb ep u tf o r w a r di nr e l i a b l em u l t i c a s t p r o t o c o lt or e s o l v ee r r o rc o n t r o l ，e r r o rr e c o v e r y , f l o wc o n t r o l ，c o n g e s t i o nc o n t r o la n de n d - t o - e n d d e l a y i nan u m b e ro ff i e l d sa b o u tm u l t i c a s tr e l i a b i l i t y ，e r r o rd e t e c t i o na n dr e c o v e r yt e c h n o l o g y b e c o m eh o t s p o ti nc u r r e n tr e s e a r c hg r a d u a l l y f i r s t l y , t h i sp a p e ri n t r o d u c e sv a r i o u sm e t h o d sa n d m e c h a n i s m sa b o u te r r o rd e t e c t i o na n dr e c o v e r y t h e nw ei n t r o d u c et h ee r r o rr e c o v e r ya l g o r i t h m r r m pw h i c hh a sb e t t e rs c a l a b i l i t y s o m ea d v a n t a g e so ft h er r m pa l g o r i t h mh a v eb e e na n a l y z e d i nt h i sp a p e r , f o re x a m p l e ，t h eb u r d e no ft h ee r r o rr e c o v e r yi s a s s i g n e dt ot h eg r o u pm e m b e r s r a n d o m l y , s oa st oa v o i da ne x c e s s i v eb u r d e no ns p e c i a lr e c o v e r ys e r v e ra n dt h ep r o b l e mt h a tl o s s p a c k e tc a nn o tb er e c o v e r e db e c a u s eo fa c c i d e n t a lm a l f u n c t i o ni ns o m er e l i a b l em u l t i c a s t p r o t o c 0 1 b u tt h e r ea r ea l s os o m ed e f i c i e n c i e si nr r m e w h e nam e m b e ro fad o m a i nd e t e c t e di t s l o s s ，i tw i l ls t a r tl o c a la n dr e m o t er e c o v e r yp r o c e s sa tt h es a m et i m e ，w h i c hm e a n sn o to n l ya w a s t eo fb a n d w i t h ，b u ta l s ol a r g e rd e l a y f o rt h i sp r o b l e m ，t h ep a p e rp u tf o r w a r da ni m p r o v e d a l g o r i t h me - r r m pb a s e do nr r m e t h ea l g o r i t h ma d d sam e c h a n i s mt oj u d g et h el o s s t y p e ，w h e nam e m b e rd e t e c ti t sl o s s ，i tw i l ls t a r te i t h e rl o c a lo rr e m o t er e c o v e r yp r o c e s s ，r a t h e rt h a n s t a r tb o t ha tt h es a m et i m e t h a tw i l lr e d u c et h et r a f f i co fr e q u e s ta n dr e c o v e r yp a c k a g e s ，s a v i n g b a n d w i d t ha n dr e d u c i n gd e l a y t h es i m u l a t i o nr e s u l t sw eo b t a i n e df r o mt h ee x p e r i m e n ta l s o v e r f i e st h ec o r r e c t n e s so ft h ec o n c l u s i o n s 。 k e yw o r d s ：r e l i a b l em u l t i c a s t ，r a n d o m ，e r r o rr e c o v e r y ，n a c k ，l o c a lr e g i o n ， l o s st y p e 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：王盘查堕日期：型 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名： 导师签名：2 謇三趣日期：型 南京邮电人学硕：l ：研究生学位论文第一章绪论 i i 引言 第一章绪论 随着流媒体、视频点播、软件分发、大容量数据快速传送等方面应用需求的不断增加， 单播数据传输模式在当前的i n t e m e t 网络条件下已经不能满足应用的要求，因为单播占用的 带宽比较高，同时对用户数量的可扩展性也相当不好。在这种条件下，组播在这些应用中 就变得越来越重要。组播( m u l t i c a s t ) 是指从一个站点将数据分组信息发送给多个站点的 通信机制，在组播中，最理想的情况是发送方只发送每个数据分组一次而每条链路上也只 有一个数据分组通过。传统的组播技术能较好地利用带宽，尽力转发数据，但不能保证所 有组播数据均可靠有序地传送给每个组成员，这种服务无法满足实际应用中对组播传输的 各种质量要求。于是就出现了可靠组播【l 】。 可靠组播是为保证每个接收者都能正确地接收到所有的组播数据。对组播可靠性问题 的研究又归到对组播网络的反馈控制、拥塞控制、差错恢复等问题的研究。为满足可靠性 要求，必须要有快速高效的差错检测和差错恢复机制，且其处理方式应满足高效性和可扩 展性。对于数据分组是否正确传递，根据丢失检测是由发送者还是接收者进行，分为肯定 ( a c k ，a c k n o w l e d g e m e n t ) 确认和否定( n a c k ，n e g a t i v ea c k n o w l e d g e m e n t ) 确认两种。 在组播网络中，因为考虑到反馈内爆问题，所以常采用否定确认机制。关于差错恢复问题， 因为考虑到发送者的负担与及恢复时延等问题，人们开始考虑树型的本地恢复方法，如文 献 2 1 q = 采用专用恢复服务器的方式进行数据恢复，这样把发送者的负担转移到了组播树上 的专用恢复服务器，从而降低了发送者的负担，也大大降低了恢复时延。因为差错恢复在 组播网络中的重要性，所以对于它的研究也一直被人们重视。 1 2 课题的提出 要使组播网络中的组成员能够快速、准确地接收到发送者组播过来的数据，就需要解 决一系列的问题，其中包括拥塞控制，可扩展性，低时延等可靠性问题，为能保证可靠性， 我们需要解决反馈内爆问题，在实际网络中，因为网络的丢失率不会很高，所以般采用 n a c k 反馈机制。还有一个需要解决的可靠性问题是数据的差错恢复，这也是本文主要讨 论的问题，因为这个问题关系到组播网络数据传输的质量，也关系到组播网络是否有好 的可扩展性，是否能最大限度地降低时延。围绕这些问题，人们已经取得了很多的研究成 1 南京邮电大学硕士研究生学位论文第一荦绪论 果，比如，在文献 2 】中提出的基于树的传输路径及本地恢复技术都提高了组播的可靠性， 也增加了可扩展性，但也存在一些问题。文献 3 提出了一种随机化差错恢复算法，解决了 文献【2 中恢复服务器的重负载问题，当然，这种随机化的差错恢复算法也存在很多不足， 于是，基于这些人的研究成果之上，本文提出了一种随机化的差错恢复算法的改进算法 e r r mp 。 1 3 课题的研究现状 2 0 世纪8 0 年代中期，斯坦福大学的博士生sed e e r i n g 发表h o s tg r o u p ：am u l t i c a s t e x t e n s i o nt ot h ei n t e m e tp r o t o c o l ( r f c 0 9 6 6 ) 和h o s te x t e n s i o n sf o ri pm u l t i c a s t i n g ( r f c 0 9 8 8 ) 两篇论文，提出了i p 组播的可能性；他的文章还描述了主机成员规格的协议，这成为今天 因特网组管理协议( i g m p ) 的依据，另外，sed e e r i n g 还提出了一种基于距离向量的组 播路由协议，成为距离向量多目路由选择协议( d v m r p ) 的基础，而且在几年后又被他 进一步扩展，这两份协议开创了关于i p 信息包网络模型的成功延伸，即允许组播被扩展到 o s i 模型的第3 层。从此，在i p 组播技术方面的探索一直在继续进行。随后就出现许多关 于组播技术领域的研究。有组播通信协议的可靠性研究；组播的可扩展性问题；组播的拥 塞问题、差错恢复问题、时延问题及安全等方面的问题。围绕这些问题，人们提出了很多 有意义也很有价值的解决方案，比如在文献 2 】中提出用专用恢复服务器来减少网络的拥 塞，文献 4 】中讨论了差错恢复对可靠组播协议拥塞控制的影响。总之，相关的研究越来越 多，也为研究的进一步完善和发展奠定了基础。 1 4 论文结构安排 论文的主要内容分为六章。第二章为组播概述，讨论了组播的基本原理、组成员管理、 路由等相关技术。第三章是组播的可靠性技术，研究了组播的可靠性问题，包括组播网络 中的状态控制和反馈控制，拥塞控制与拥塞处理，差错检测与恢复等问题。第四章阐述了 组播网络中差错恢复的各种技术，介绍了一种随机的差错恢复算法，并进行相关的分析， 也详细讨论了这种算法的的优点与缺点。第五章提出了一种基于r r m p 算法的改进算法 e r r m p ，并通过网络仿真对改进算法进行了相关的性能比较和分析。第六章对全文作了 总结，并对需要深入研究的问题作了展望。 2 南京邮i 乜大学硕十研究生学位论文第一二章组播概述 第二章组播概述 2 1 组播技术产生的原因 传统的i p 通信有两种方式，第一种是在一台源i p 主机和一台目的i p 主机之间进行通 信，即单播( u n i c a s t ) ；第二种是在一台源i p 主机和网络所有其它的i p 主机之间通信，即 广播( b r o a d c a s t ) 。如果要将信息发送给网络中的多个主机而非所有主机，则要么采用广 播方式，要么由源主机分别向网络中的多台目标主机以单播方式发送i p 包，要是采用广播 方式实现，则不仅会将信息发送给不需要的主机而浪费带宽资源。也可能由于路由回环引 起严重的广播风暴；采用单播方式实现时，由于i p 包的重复发送会白白浪费掉大量的带宽。 也增加了服务器的负载。所以，传统的单播和广播通信方式都不能有效地解决单点发送多 点接收的问题。 i p 组播是指在i p 网络中将数据包以尽力传送( b e s t e f f o r t ) 的形式发送到网络中的某 个确定节点集，这个子集称为组播组( m u l t i c a s tg r o u p ) 。i p 组播的基本思想是：源主机只 发送一份数据，这份数据中的目的地址为组播组地址；组播中的所有接收者都可以接收到 同样的数据拷贝，并且只有组播组内的主机( 目标主机) 可以接收该数据，组播组用d 类 i p 地址( 2 2 4 0 0 0 2 3 9 2 5 5 2 5 5 2 5 5 ) 来标识。 2 2 组播技术的基本原理 组播技术涵盖的内容相当丰富，从地址分配，组成员管理，到组播报文转发，路由建 立，可靠性等诸多方面【1 】。 2 2 1 组播协议的体系结构 根据协议的作用范围，组播协议分为主机一路由器之间的协议，即组播成员管理协议， 以及路由器一路由器之间的协议，主要是各种路由协议。组成员关系协议包括i g m p ( 互 联网组管理协议i n t e r n e tg r o u pm a n a g e m e n tp r o t o c 0 1 ) ：组播路由协议又分为域内组播路由 协议和域间组播路由协议两类。同时为了有效抑制组播数据在二层网络中的扩散，引入了 i g m p 和二层组播协议。在路由器和交换机中建立起直联网段内的组成员关系信息，具体 地说就是哪个接口下有哪个组播组的成员，域内组播路由器协议根据i g m p 维护的这些组 南京邮电大学硕士研究生学位论文第二章组播概述 播组成员关系信息，运用一定的组播路由算法构造组播分发树。在路由器中建立组播路由 状态，路由器根据这些状态进行组播数据包转发。域间组播路由协议根据网络中配置的域 问组播路由策略，在各自治系统( a s ，a u t o n o m o u ss y s t e m ) 间发布具有组播能力的路由 信息以及组播源信息，使组播数据能在域间进行转发。 2 2 2 组播的地址机制 i p 组播地址用于标识一个i p 组播组，i a n a 把d 类地址空间分配给组播使用，范围 从2 2 4 0 0 o 一2 3 9 2 5 5 2 5 5 2 5 5 。如图2 1 所示( 二进制表示) 。i p 组播地址前四位均为 “1 1 1 0 ”。如图2 2 所示为组播地址划分 3 2 位i p 地址 1 字节o + li 宇节1 + l卜字节2 叫卜字节3 + i 固定位1 1 1 0 2 3 9 2 5 5 2 5 5 2 5 5 2 3 9 0 0 0u u 一 2 3 8 2 5 5 2 5 5 2 5 5 2 2 4 01 2 2 4 ，0 0 2 2 2 4 0 0 图2 1i p 地址划分 本地管理组播地址 用户组播地址 预舀组播地址 南京邮电大学硕上研究生学位论文第二章组播概述 4 8 位m a c 地址 3 2 位p 地址 母星罗目目 歪，乃刀自圈目 2 3 组播管理 2 3 。1 组播成员管理 图2 3 组播地址到m a c 地址映射 g m p 协议运行于主机和与主机直接相连的组播路由器之间，i g m p 实现的功能是双向 的。一方面，通过i g m p 协议，主机通知本地路由器希望加入并接收某个特定组播组的信 息；另一方面，路由器通过i g m p 协议周期性地查询局域网内某个已知组的成员是否处于 活动状态( 即该网段是否仍有属于某个组播组的成员) ，实现所连网络组成员关系的收集 与维护。通过i g m p ，在路由器中记录的信息是某个组播组是否在本地有组成员，而不是 组播组与主机之间的对应关系。i g m p 有三个版本，i g m p v l ( r f c l l l 2 ) q b 定义了基本的组 成员查询和报告过程：目前通用的是i g m p v 2 ，由r f c 2 2 3 6 定义，在i o m p v l 的基础上添 加了组成员快速离开机制；i g m p v 3 中增加的主要功能是成员可以指定接收或指定不接收 某些组源的报文，i g m p v 2 的原理如图2 - 4 所示。当同一个网段内有多个组播路由器时， i g m p v 2 通过查询器选举机制从中选举出唯一的查询器，查询器周期性地发送通用组查询 消息进行成员关系查询。主机发送报告消息来响应查询。主机发送报告消息的时间是随机 性的，当检测到一个网段内有其它成员发送同样的消息时，则抑制自己的响应报文。如果 有新的主机要加入到组播组，不必等待查询器的查询消息，而是主动发送报告消息。当要 离开组播组时，主机发送离开组消息，收到离开组消息后，查询器发送特定组查询消息来 确定是否所有组成员都已经离开。对于作为组成员的路由器而言，其行为和普通的主机一 样。响应其它路由器的查询。通过上述机制，在组播路由器里建立起一张表，其中记录了 路由器的各个接口所对应的子网的数据上都有哪些组成员。当路由器接收到某个组g 的数 据报文后，只向那些有g 的成员的接口上转发数据报文。至于数据报文在路由器之间如何 转发则由路由协议决定，不是i g m p 协议的功能。 南京邮电大学硕士研究生学位论文第二章组播概述 图2 4i g m p v 2 的工作原理 二层环境中组成员管理的实现：i g m p 组播成员管理机制是针对第三层设计的。在第 三层，路由器可以对组播报文的转发进行控制。只要进行适当的接口配置和对t t l 值的检 测就可以了。但是在很多情况下，组播报文要不可以避免地经过一些二层交换设备，尤其 是在局域网环境里。如果不对二层设备进行相应的配置，则组播报文就会转发给二层交换 设备的所有接口，这显然会浪费大量的系统资源。i g m p 监听( i g m ps n o o p i n g ) 可以解决 这个问题。i g m p 监听的工作原理是主机发出i g m p 成员报告消息，这个消息是给路由器 的，在i g m p 成员报告经过交换机时。交换机对这个消息进行监听并记录下来。形成组成 员和接口的对应关系。交换机在收到组播数据报文时，根据组成员和接口的对应关系。仅 向具有组成员的接口转发组播报文。i g m p 监听可以解决二层环境中的组播报文泛滥问题。 但要求交换机具有提取第三层信息的功能。其次，要求交换机对所有的组播报文进行监听 和解读。这会产生很多的无效工作；此外，组播报文监听和解读工作也会占用大量的c p u 处理时间。 2 3 2 组播组网业务管理一受控组播 i p 组播技术对于新的多媒体业务的开展具有重要的意义。但是，组播业务目前在运营 方面还存在用户管理等方面的问题。首先，组播协议中没有提供用户认证支持，用户可以 随意加入一个组播组，并且可以任意离开。组播源无法知道用户何时加入，何时退出。无 法统计出某个时间网络上共有多少个用户在接收组播流量。组播源也缺少有效的手段控制 6 堕室坚坐奎兰堡：! 翌窒生堂垡笙兰三 墨三至里堡塑垄 组播信息在网络上传送的方向和范围。另外，组播协议在安全上也没有提供可靠的保证。 在网络上的任何用户都可以作为组播源发送组播流量。在组播系列协议中缺乏对组播源可 靠的控制。同样也无法对用户进行有效控制。在一个支持组播的网络中，存在组播节目冲 突问题，也存在非法组播源传播的问题。因此，尽管组播技术具备开展新业务的许多优势。 并且协议曰渐完善，但开展组播业务还面临着组播用户认证。组播信源安全性和组播流量 扩散安全性等问题。结合目前网络的特点、组播技术和应用的实际情况，国内外有些公司 在完全符合标准组播协议的基础上。提出受控组播技术( 包括组播信源管理，组播用户管 理和组播安全控制) ，有效的解决了当前组播业务开展所遇到的各种问题。 ( 1 ) 组播信源管理 信源管理是指在组播流进入骨干网络前，组播业务控制设备应负责区分合法和非法媒 体服务器，转发合法的组播信息流，阻断非法的组播信息流。在网络规模比较大的情况下， 手工配置信源管理信息的工作将变得非常复杂，这样阻碍了网络的发展。为了解决上述问 题。国内外有些公司采用q u i d w a y 业务管理平台实现组播信源管理，采用q u i d w a y 业 务管理方式，可以很容易完成信源管理配置，增加和删除信源控制表项，保证整个网络表 项的一致性。实现了信源的控制后。弥补了由于组播协议自身缺点带来的非法媒体服务器 对网络带宽的占用，保证了骨干网络的安全和稳定性。 ( 2 ) 组播用户管理 组播业务管理的另一个内容是用户管理。标准组播协议没有考虑用户的管理，而且从 目前组播应用的情况看，在很多组播业务运营( 包括国内外目前正在运行或测试的组播业 务) 中，用户管理仍未得到很好的解决。组播业务作为一项增值业务，对用户进行控制管 理是必不可少的。 整体上讲，组播业务的用户管理可以分为两大类。一、用户已经接收到组播数据，但 必须通过认证后才能“看到”相应的组播内容；二、用户必须先通过认证才能接收和“看到” 相应的组播内容。第一类用户管理的实现对中间设备的要求比较低，中间设备只需支持标 准的组播协议。保证用户收到组播数据。其它工作都由客户端软件完成。即基于客户端软 件实现组播用户管理。基于软件模式的组播用户控制实现上比较简单。虽然可以控制到具 体用户。但却是以网络带宽被占用为代价( 没有权限的用户也会收到组播流量) ，这也不 利于组播的统一管理。第二类用户管理目前的解决方式是：控制到二层交换机的接口或 v l a n ，通过8 0 2 1 x 协议来实现。二层设备首先根据8 0 2 1 x 对用户的组播权限进行验证。 如果验证通过，n - 层设备接收用户的i g m p 加入( 离开) 的信息，并建立相应的转发表 项，允许用户接收组播流量。否则，丢弃用户的i g m p 报文，禁止用户接收组播流。 7 南京邮电火学硕十研究生学位论文 第二章组播概述 为了进一步提高用户的权限控制，在上述验证通过后，q u i d w a y 业务管理平台可以 为该用户建立组播访问规则表项。用户只能访问授权的组播服务。当用户加入某个组播组， 二层设备首先到q u i d w a y 业务管理平台进行用户的业务认证。如果认证通过，二层设备 生成用户的组播通道，否则禁止用户加入。二层设备与q u i d w a y 业务管理系统结合起来， 可以在全网范围内进行组播用户认证和授权。 ( 3 ) 组播安全控制管理 在标准的组播中，接收者可以加入任意的组播组，也就是说，组播树的分枝是不可以 控制的，信源不了解组播树的范围与方向，安全性较低。为了实现对一些较重要的信息保 护，需要控制其扩散范围。静态组播树方案就是为了满足此需要而提出的。静态组播树就 是组播树事先配置，控制组播树的范围与方向，不接收其它动态的组播成员的加入。这样 能使组播信源的报文在规定的范围内扩散。通过配置静态组播树，可以满足高价值用户的 安全需要。 2 4 组播路由 组播路由可以分为两大类：信源树( s o u r c et r e e ) 和共享树( s h a r e dt r e e ) 。如图2 5 所示。信源树是指以组播源作为树根，将组播源到每一个接收者的最短路径结合起来构成 的转发树。由于信源树使用的树从组播源到接收者的最短路径。因此也称为最短路径树 ( s p t ，s h o r t e s tp a t ht r e e ) 。对于某个组，网络要为任何一个向该组发送报文的组播源建 立一棵树。共享树以某个路由器作为路由树的根，该路由器称为汇集点( r p , r e n d e z v o u s p o i n t ) ，将r p 到所有接收者的最短路结合起来构成转发树。使用共享树时，对应某个组， 网络中只有一棵树，所有的组播源和接收者都使用这棵树来收发报文。组播源向树根发送 数据报文，之后报文又向下转发到达所有的接收者。 信源树的优点是能构造组播源和接收者之间的最短路径，使端到端的时延达到最小， 但是付出的代价是：在路由器中必须为每个组播源保存路由信息，这样会占用大量的系统 资源，路由表的规模也比较大。共享树的最大优点是路由器中保留的状态树可以很少，缺 点是组播源发出的报文要先经过r p ，再到达接收者，经由的路径并非最短，而且对r p 的 可靠性和处理能力要求很高。 南京邮电大学硕二i = 研究生学位论文第二章纽播概述 2 4 1 组播转发过程 树2 图2 5 信源树和共享树 组播报文转发与单播报文的转发相比较为复杂些。一方面，组播路由类型与单播路由 不同，是点到多点的一棵路由树：另一方面组播报文转发的处理过程也有所不同。单播报 文的转发过程中，路由器并不关心组播源地址，只关心报文中的目的地址。通过目的地址 决定向哪个接口转发，在组播中，报文是发送给一组接收者的，这些接收者用一个逻辑地 址标识，路由器在接收到报文后，必须根据源和目的地址确定出上游( 指向组播源) 和下 游方向。把报文延着远离组播源的方向进行转发。这个过程称作r p f ( r e v e r s ep a t h f o r w a r d i n g 逆向路径转发) 。 r p f 执行过程中会用到原有的单播路由表以确定上游和下游的邻接结点。只有当报文 是从上游邻接结点对应的接口( 称作r p f 接口) 到达时，才向下游转发。r p f 的作用除了 可以正确地按照组播路由的配置转发报文外，还能避免由于各种原因造成的环路，环路避 免在组播路由中是一个非常重要的问题。r p f 的主体是r p f 检查，路由器收到组播报文后， 先对报文进行r p f 检查，只有检查通过才能转发，否则丢弃。r p f 检查中使用的是从路由 器到组播源或r p 的最短路径所对应的接口。因此称作逆向路径转发。 南京邮电火学硕士研究生学位论文 第二章组播概述 2 4 2 域内组播路由协议1 5 l 参与组播的主机可来源于不同的物理网络，广域环境中的组播报文转发需要组播路由 器的支持。不同位置的组播路由器有不同功能，与终端主机相连的叶子网络( 1 e a f n e t w o r k ) 中的组播路由器主要实现i g m p 功能，而位于过渡网络( t r a n s i tn e t w o r k ) 的组播路由器则参 与分发树管理和报文转发。 稠密型路由协议d v m r p ( d i s t a n c ev e c t o rm u l t i c a s tr o u t i n gp r o t o c 0 1 ) 、m o s p f ( m u l - t i c a s to p e ns h o r t e s tp a t hf i r s t ) 、p i m d m ( p r o t o c o li n d e p e n d e n tm u l t i c a s t s p a r em o d e ) 适用于 发送者和接收者距离相对较近，接收者数量较多且带宽充足的区域。这类协议常常为每个源 ( p e rs o u r c e ) 建立一个单独的分发树。稠密型路由协议能构造效率很高的组播树，但可扩充 性不好。特别在组成员稀散分布情形下，稠密型路由协议由于要定期跨越许多非稳定链路 传输数据报文( 女i i d v m r p ) 或组关系报告信息( 如m o s p f ) ，容易造成报文丢失，降低系统效 率。稀疏型路由协议c b t ( c o r e b a s e dt r e e s ) 、p i m s m ( p r o t o c o li n d e p e n d e n tm u l t i c a s t - s p a r e m o d e ) 显式创建路由树( 枝) 方法和共享树( s h a r e dt r e e ) ，有效地维护了协议树状态、减少了 控制信息。协议依赖性规定了获取组播路由的依赖条件，协议相关组播需要利用特定的协 议来完成组播树的计算。d v m r p 扩展了类似p 的“距离一向量”单播协议，m o s p f 是一种 基于链路状态的路由协议，已对单播o s p f 协议做了扩展。协议无关组播的实现不需要依赖 于特定的单播路由协议，这类协议非常适用于大型异构网络环境。 组播树生成方式是组播路由协议设计的关键部分，在很大程度上决定了协议的性能。 泛洪剪枝( f l o o d p r u n e ) 协议使用反向路径转发r p f ( r e v e r s ep a t hf o r w a r d i n g ) 技术为每个数 据源计算一棵组播树。路由器收到从特定源发送的第一个组播报文后向所有非该报文接收 接口转发报文，不含组播成员的叶子路由器将向上层反馈剪枝消息，阻止后续组播报文的 转发，组播树被剪枝成由每个接收者到发送者的最短路径组成的最小树。d v m r p 、p i m d m 都采用了这种协议机制。这类协议的缺点是需要周期性发送泛洪消息来发现接收者，并要求 所有组播路由器无论是否存在到接收者的路径都要为每个组播组保存状态信息。s p t ( s h - o r t e s t p a t ht r e e ) 方法用t - m o s p f 协议，通过链路状态为每一对源组播f l j ( s o u r c e g r o u p ) 在路 由器的高速缓存中构造一棵组播树。m o s p f 基本上能在缓存中执行“r p f + 剪枝”来计算 组播树，而不用实际的扩散组传输的第一个分组，该协议仅适用于那些使用o s p f 作为路由 协议的互联网络。由于m o s p f 要在网络中广播成员信息，并且d i j k s t r a 最短路径树计算需 要较大的路由器系统开销，因此很难在大型系统中得到应用。显式- d n i 剪枝( e x p l i c i t l yj o i n p r u n e ) 方法是基于中心的组播树生成协议，协议将组播地址映射到某个组播路由器上的单 1 0 南京邮电大学硕士研究生学位论文第二章组播概述 播地址，然后以此为核心构造组播树，每个接收者都要显式向该核心发送预定组播报文请 求。c b t 和p i m s m 都属于这样的协议。c b t 建立的是双向共享树，每个收到报文的路由器 可从组播树中除接收端口外的所有端口转发该报文，协议只要求在组播树上的路由器存储 该组的路由信息，没有路由器需要存储与数据源有关的信息，因此，中心路由器的选择决 定了c b t 组播树的效率。为增加冗余和容错能力，c b t 允许有多个中心路由器，c b t 中心路 由器的放置直接影响着算法效率。p i m s m 把c b t 的中心路由器称为集合点r e n d e z v o u s p o i n t ( r p ) 。p i m s m 对c b t 的重要改进是将发现发送者和建立组播树两过程分离，p i m s m 在共享树形成后优化，使与发送源有关的状态信息只存在于最短路径树上。p i m s m 中对 r p 的选择要求能达到负载均衡。 2 4 3 域间组播路由协议 域间组播目前仍然处于研究和实验阶段，现在比较成型的解决方案是下面三个协议的 组合：m b g p ( m u l t i c a s tb o d e rg a t e w a yp r o t o c o l 组播边界网关协议) ，用于在自治域之间 交换组播路由信息；m s d p ( m u l t i c a s ts o u r c ed i s c o v e r yp r o t o c o l 组播信源发现协议) ，用 于在i s p 之间交换组播信源信息；p i m s m ( p r o t o c o li n d e p e n d e n tm u l t i c a s t s p a r em o d e ) ，用 作域内的组播路由协议。由图2 6 可以看出，p i m s m m b g p m s d p 组合方案实际上是 p i m s m 协议在域间环境下的扩展，如果把整个p i m s m 府v i g b p m s d p 组合方案机制看作 p i m s m ，则所有域的i 冲的集合就是p i m s m 协议中的“r p ”，而p i m s m m g b p l s d p 无非是增加了下面两个过程： h o s t1 h u b h o s t2 图2 6p i m s m m s d p m b g p 组合方案的j ：作过程 南京邮电大学硕士研究生学位论文第二章组播概述 ( 1 ) 信源信息在r p 集合中的泛滥，以实现信源和成员在“r p ”点的会合。 ( 2 ) 域间组播路由信息的传递，目的是保证组播报文在域间的顺利转发，在上述过 程中，a s 3 中的r p 和收端向a s 2 中的远端建立逆向路径的过程中都需要用到 m b g p 传递的组播拓扑信息。 南京邮电入学硕士研究生学位论文 第三章纽播的可靠性技术 3 1 概述 第三章组播的可靠性技术 可靠性是许多应用的基本要求，i p 组播模型建立在“尽力而为”的报文传输服务之上， 不能保证报文的可靠传输。组播流投递点的分散性和接收者的异构性使组播可靠性研究要 比单点投递复杂得多，很难设计出“一劳永逸( o n es i z ef i t sa l d ”的可靠组播方案，因此传统 的类似于t c p 方式的可靠单播机制难以移植到组播中。所以就需要为组播的可靠性传输 寻求一些特别的控制、检错与恢复等机制。组播可靠性保证可以分为三种。( 1 ) 严格可靠： 既是不仅要保证数据的完整性，还要保证数据接收的顺序同数据发送的顺序一致。组播数 据是封装在u d p 报文中传输。在传输过程中，每个u d p 报文都是独立路由，因此组成员 接收到数据的顺序可能同数据发送的顺序不一致。对于用组播方式来传输文件的应用来 说，接收顺序的不一致将导致致命错误。因此严格可靠组播中将提供这两个方面的可靠性 保证。( 2 ) 普通可靠：相对于严格可靠来说，普通可靠仅仅保证数据的完整和无差错性， 而不考虑数据的接收顺序。( 3 ) 部分可靠：是级别最低的一种可靠性，即不完全保证数据 的完整性，也不保证数据的接收顺序与发送顺序一致。部分可靠组播允许数据传输在一定 程度的差错。本文研究的组播可靠性属于普通可靠。组播可靠性研究主要包括状态控制、 反馈控制机制、差错恢复、拥塞控制方法等方面。 3 2 状态控制与反馈控制 3 2 1 组播的状态控制 根据负责跟踪连接状态和控制重传方的不同，可靠组播常被分成基于发送方和基于接 收方两种状态控制模型。基于发送方的状态控制方法要求每个接收者向发送方发送反馈信 息，发送方根据反馈重传丢失报文。对层次式数据传输应用，该方法使发送者可根据反馈 动态调整数据层次，从而有效利用带宽。但该方法要求发送方为每个接收者维护状态信息， 而且随着组播规模增大易产生反馈风暴。基于接收方的方法将状态控制移交给了接收方， 接收者在监测到丢包时向发送方或上级反馈n a k 报文，该控制方法能避免反馈风暴，使差 错恢复能在局部进行，但基于接收方的状态控制方法也有许多缺点： ( 1 ) 发生n a k 丢失时不能判断拥塞： 南京邮电大学硕：l ：研究生学位论文第三章组播的可靠性技术 ( 2 ) 在随机n a k 抑制技术中足玎计算开销大； ( 3 ) 要求接收方有较大缓存来同步数据。文献 6 对这两种方法进行了详细比较。 3 2 2 组播的反馈控制 反馈报文包括肯定确认报文( a c k ) 、否定确认报文( n a k ) 、选择确认报文( s a c k ) 三种 类型。组播反馈控制的中心任务是合理利用这些报文，避免反馈风暴。可靠组播反馈机 制可以分成五个等级： ( 1 ) 仅采用n a c k 报文； ( 2 ) 带全等树的n a c k 报文： ( 3 ) 所有接收者反馈a c k 报文，n a c k 报文可选： ( 4 ) 不带全等树的层次式a c k ； ( 5 ) 带全等树的层次式a c k 。 根据组逻辑关系的不同，可靠组播路由协议可分成平面型、环型、树型。在平面型中， 接收方以单播或组播方法将反馈信息发送给发送方及其他组成员，这种结构比较容易产生 反馈风暴，通常采用反馈抑$ 1 ( f e e d b a c ks u p p r e s s i o n ) 途径来解决。具体方法有： ( 1 ) 随机时延法。接收者等待一个随机时间，在定时器超时后发送反馈信息，该方法的关 键是准确确立随机时延范围； ( 2 ) 由发送方发起的定期轮询方案： ( 3 ) 概率方案，在发送反馈的概率大于某个阀值时发送反馈报文； ( 4 ) 基于代表的方案，从接收集中选取符合特定条件的若干代表发送反馈报文。 环型结构一般借鉴令牌思想，只有持有令牌的接收者才能发送反馈信息。在树型结构 中，以发送者为根节点，接收者为叶子节点，枝节点可以