（计算机应用技术专业论文）抑制nack技术与基于可靠主动结点的可靠多播通信的研究.pdf

摘要 f 随着i n t e r n e t 网的发展，涌现了大量的新应用，如软件分发、视频会议、 远程教学和共享“白板”等，这些新应用都有个共同的特征：一对多或多对 多的可靠通信，其潜在的接收者可能成百上千，所以，要求发送者能够高效地 把数据传送给所有接收者。由于i n t e m e t 网的体系结构是针对点对点设计的， 使传统i n t e m e t 网技术受到了极大的挑战。为了满足新应用的要求，多播通信 技术应运而生。但在i n t e m e t 网上丌展多播通信应用，不可避免地会遇到一些 新问题。本论文重点研究并解决如下问题：n a c k 爆炸、局部恢复数据以及 减轻发送者负载，并且取得了如下创造性成果： 本文提出了两种抑制n a c k 的定时器设置方法。在可伸缩可靠多播通信 中存在反馈信息爆炸、局部恢复数据困难等问题，为了解决反馈信息爆炸的问 题，本文针对基于接收者启动、使用集成f e c 的系统，详细讨论了如何使用 定时器避免n a c k 爆炸，提出了设置定时器时问的两种方法：基于指数分布、 均匀分段方法和基于指数分布、非均匀分段方法，并且分析了它们抑制n a c k 的能力和由定时器引起的n a c k 延时长短，通过分析可知：对接收者数量达 到l o 数量级的多播通信，这两种方法都能避免反馈信息爆炸，且由定时器引 起的n a c k 延时短，并且后一种方法优于前一种方法。 本文提出了基于可靠主动结点的可靠多播通信协议r a n r m ( r e l i a b l e a c t i v en o d er e l i a b l em u l t i c a s t ) 。i n t e m e t 网使用端到端的可靠性思想，仅由t c p 层负责数据的可靠性，i p 层不保证数据的可靠传递，这样，可靠性实现简单 且具有较高的传输效率，但对于不可靠网络，端到端可靠性会增加恢复数据的 延时，且实现可靠性的丌销大，同时也增加了主机的负担。这是i n t e m e t 网设 计上固有的问题，如果在i n t e m e t 网上进行多播通信，则问题更加突出，并且 不可避免地将出现反馈信息爆炸、丢失数据恢复困难等问题，本文建立了主动 网络中多播通信的协议分层模型，并且提出了基于可靠主动结点的可靠多播通 信协议r a n r m 。可靠主动结点指能处理与可靠性相关问题的主动结点，引入 可靠主动结点后，数据能在可靠主动结点间逐点可靠传输，从而实现可靠多播 通信。( p a n p 洲协议有如下优点：反馈信息量少，能避免反馈信息爆炸；具有 局部恢复错误数掘的能力，减轻了发送者的负担；能及时发现错误数据，降低 错误数据恢复的延时；不必在网络中传送错误数据，有效地节约带宽。文中分 析了r a n r m 占用带宽和数据恢复延时的性能，与协议n 2 比较表明：r a n r m 占用带宽少，数据恢复延时短。，晒 本文使用d e s i g l v c p n 建立了r a n r m 协议的c p n 模型，通过仿真运行 详细检查了所有可达标识，此外，还进行了动态特性分析，构造了r a n r m 的c p n 模型的状态空问，证明了r a n r m 协议的正确性。 本文还利用a n t s 模拟实现了r a n r m 协议，通过模拟程序分析了 r a n r m 的性能，并通过实验数据比较了r a n r m 与n 2 的性能。( 实验表明： r a n r m 协议是f 确的、可行的，并与理论分析结果相吻合。模拟程序对实现 r a n r m 协议具有指导意义。) ，一矿 关键宇：可靠多播通信，抑制n a c k ，定时器，指数分布，均匀载非均 匀分段，哥专主动结点，主动网络。 j 1 j a b s t r a c t w i t ht h ed e v e l o p i n go fi n t e r n e t ，m a n yn e wa p p l i c a t i o n sh a v ec o m ef o r t h ，s u c h a ss o f t w a r ed i s t r i b u t i o n ，v i d e oc o n f e r e n c e ，d i s t a n c el e a r n i n ga n ds h a r e db o a r d a l lo f t h ea p p l i c a t i o n sh a v eac o m m o nf e a t u r e ，i e o n et om a n yo rm a n yt om a n yr e l i a b l e m u l t i c a s tc o m m u n i c a t i o n ，a n dt h ep o t e n t i a lr e c e i v e r sh a v eh u n d r e d sa n dt h o u s a n d s t h e r e f o r e ，t h ea p p l i c a t i o n sr e q u i r e t h es e n d e rt od e l i v e rt h ed a t a e f f i c i e n t l y h o w e v e r , t h et e c h n o l o g yo f i n t e r n e tf a c e sg r e a tc h a l l e n g e sb e c a u s et h ea r c h i t e c t u r e o ft h ei n t e m e ti s d e s i g n e df o rp o i n tt op o i n tc o m m u n i c a t i o n t h et e c h n o l o g yo f d e p l o y i n g t h em u l t i c a s tc o m m u n i c a t i o no v e ri n t e r n e th a sb e e np r o p o s a lt os o l v et h e p r o b l e m s t h i sd i s s e r t a t i o nf o c u s e so n h o wt os o l v et h ef o l l o w i n gp r o b l e m s ：n a c k i m p l o s i o n ，l o c a lr e c o v e r yt h em i s s i n gd a t aa n dd e c r e a s i n gt h eb u r d e no f t h es e n d e r i ns h o r t ，w eo b t a i naf e wb r e a k t h r o u g h sa sf o l l o w s ： f i r s t l y , w ep r o p o s et w om e t h o d so fs u p p r e s s i n gn a c k b a s e do nt h et i m e r t h e r ea r es e v e r a lp r o b l e m si ns c a l a b l ea n dr e l i a b l em u l t i c a s t ，s u c ha s ，f e e d b a c k i m p l o s i o n a n dl o c a l r e c o v e r y , e t c a i m a tt os o l v et h e p r o b l e m o ff e e d b a c k i m p l o s i o n ，w ed i s c u s sc a r e f u l l yh o w t os e tt h et i m e rt oa v o i dt h en a c k i m p l o s i o n i nr e c e i v e r - i n i t i a t e d ，i n t e g r a t ef e cs y s t e m w ep r o p o s et w om e t h o d s ： d i v i d e d t i m ee q u a l l ya n db a s e do ne x p o n e n t i a ld i s t r i b u t i o nt os e tt i m e r s ， d i v i d e dt i m e u n e q u a l l ya n d b a s e do ne x p o n e n t i a ld i s t r i b u t i o nt os e tt i m e r s b ya n a l y z i n gf o ru pt o 10 r e c e i v e r s ，b o t ho ft h e mc a na v o i dt h en a c k i m p l o s i o na n df e e d b a c kd e l a y d u e t ot i m e r si s1 0 w , t h er e s u l ta l s os h o w st h es e c o n dm e t h o di sb e t t e rt h a nt h ef i r s to n e s e c o n d l y , w ep r o p o s ear e l i a b l e m u l t i c a s tp r o t o c o lb a s e do nr e l i a b l ea c t i v e n o d e ( r a n r m ) a sr e l i a b l em u l t i c a s to v e ri n t e m e th a sm a n yp r o b l e m sc a u s e db y t h ei pp r o t o c o lt h a td o e sn o tg u a r a n t e et h er e l i a b i l i t y i nt h el a y e r i n gm o d e l ，r i v i l a y e ri n c l u d e sm a n a g e m e n ts u b - l a y e ra n dr e l i a b i l i t ys u b l a y e r o u rr e s e a r c hm a j o r s t h er e l i a b i l i t ys u b - l a y e r i nr a n r m ，t h ea c t i v en o d e sa r ed i v i d e di n t ot w oc l a s s e s ： t h er e l i a b l ea c t i v en o d e sa n dt h ef o r w a r da c t i v en o d et h er e 】i a b l ea c t i v en o d e sd e a i w i t hs o m et a s k sr e l a t i n gt ot h er e l i a b i l i t y i no t h e rw o r d s ，t h er e l i a b l ea c t i v en o d e s i m p l e m e n t t h e r e l i a b i l i t ys n b l a y e r t h ef o r w a r da c t i v en o d e sh a v et h es a m e f i m c t i o na st h et r a d i t i o n a li pn o d e su s i n gt h er e l i a b l ea c t i v en o d e si nt h ea c t i v e n e t w o r kc a ng u a r a n t e et h a tt h ed a t ai sr e l i a b l yd e l i v e r e df r o mo n er e l i a b l e a c t i v e n o d et oa n o t h e r w i t ht h ef l e x i b i l i t yo fa c t i v en e t w o r k ，t h ea p p l i c a t i o nl a y e rs h o u l d c u s t o m i z et h eq u a n t i t ya n dt h el o c a t i o no ft h er e l i a b l ea c t i v en o d e si na c t i v en e t w o r k w e s u g g e s t t h a tt h er e l i a b l ea c t i v en o d e ss h o u l db et h o s ew h i c hl o c a t ea tt h e ”e d g e s ” o ft h eb a c k b o n el i n k s i ns h o r t ，r a n r mh a sm a n ya d v a n t a g e s ，t oa v o i df e e d b a c k i m p l o s i o nb e c a u s eo n l yaf e wf e e d b a c km e s s a g e sa r e h a n d l e db yt h es e n d e r , t o r e d u c et h eb u r d e no fh a n d l i n gl o s sf e e d b a c kb yu s i n gt h ea b i l i t yo fl o c a ll o s s r e c o v e r y ，t or e d u c et h er e c o v e r yl a t e n c yb yf i n d i n gt r a n s m i s s i o ne r r o r si nt i m e ，a n d a l s ot oe f f i c i e n t l yr e d u c en e t w o r kb a n d w i d t hc o n s u m p t i o nb yn o tt r a n s f e r r i n gt h e c o m t p t e dd a t a t h e r e f o r e ，t h ep r o t o c o lc a n s o l v et h ep r o b l e m so ft h er e l i a b i l i t ya n d s c a l a b i l i t y , a n d c a nc o m b i n et h e r e l i a b i l i t y w i t h h i g h t r a n s m i s s i o n e f f i c i e n c y t h e o r e t i c a la n a l y s i ss h o w st h a tt h ep r o t o c o lp r e s e n t e dh e r ei s ，c o r n p a r i n gw i t ht h e t r a d i t i o n a ln e t w o r kp r o t o c o l ，b e t t e rf o rb a n d w i d t ha n dl o s sr e c o v e r yd e l a y t h i r d l y , c p nh a sb e e na d o p t e dt o d e s c r i b et h er a n r v 1 a st h ec p no f r a n r m i sc o n s t r u c t e d ，t h e ya r ei n v e s t i g a t e db ym e a n so ft h ec p ns i m u l a t o r a l l d e t a i l so ft h er e a c h e dm a r k i n g sa r ei n s p e c t e d ，m o r e o v e r , w ec o m p l e m e n ts i m u l a t i o n w i t ht h ec o n s t r u c t i o no f t h es t a t es p a c e s f o u r t h l y , a n t sh a sb e e na d o p t e dt os i m u l a t er a n r m ，a n dt h es i m u l a t i o n r e s u l t ss h o wt h es a m ec o n c l u s i o no ft h e o r e t i c a la n a l y s i s t h ep r o g r a mo fs i m u l a t i o n c a n g u i d eh o w t oi m p l e m e n tt h er a n r m p r o t o c 0 1 k e y w o r d s ：r e l i a b l em u l t i c a s t ，s u p p r e s s i n gn a c k ，t i m e r , e x p o n e n t i a ld i s t r i b u t i o n ， d i v i d e dt i m ee q u a l l yo ru n e q u a l l y , r e l i a b l ea c t i v en o d e ，a c t i v en e t w o r k 电子科技人学i 尊一 论文 第一章导论 1 1i n t e r n e t 网的发展现状 i n t e r a c t 网是2 0 ! 纪末期发展最快、规模最大、涉及面最广的科技成果之 一，它起源于美国。1 9 6 8 年，美国国防部下属的高级研究计划局a r p a 决定 建立一个分布式计算机网络，网络采用如下的设计思想：网络上各结点具有平 等的地位，每个结点都能够生成、接收和传送信息；对传送信息进行分组，从 不同的传输路径把分组从源结点传送到目的结点。这些分组到达目的结点后， 再进行组装，恢复成原始信息。这种设计思想主要考虑到战争的需要即使网 络上某些结点遭到破坏，网上信息仍能正确地送达目的地。1 9 6 9 年，一个实 验性的网络开始运行，网上总共只有4 个结点，这就是a r p a 网的原型。 在a r p a 网中互联的、运行用户程序的计算机称为主机( h o s t ) ，主机之问 通过接口报文处理机i m p ( i n t e r f a c em e s s a g ep r o c e s s o r ) 连接起来。主机负责处 理数据，为用户提供资源和服务，i m p 负责通信，这样在逻辑功能上形成两 级子网结构：由i m p 和它们之间的通信线路及通信设备构成的通信子网：与 通信子网相连的各种资源( 包括所有硬件、软件和数据库等) 构成资源子网。 通信子网负责整个网络的数据传输工作，资源子网负责处理用户数掘，提供资 源共享。两级子网结构既有利于提高通信线路的利用率，又能保证主机的工作 效率。 i n t e m e t 网是在a r p a 网的基础上，互联了众多的其他网络，经过不断发 展变化而形成的网间网。下面简要介绍i n t e r a c t 网的关键技术。 1 1 1t c p i p 协议 习惯上人们把i n t e r n e t 的一组通信协议统称为t c p i p 协议。其主要协议 是i p 协议和t c p 协议。 第一苹导沦 1 i p 协议 i p 协议的重要功能包括无连接数据报传送、数据报寻径以及差错处理三 部分。 i p 协议采用无连接的数据报机制，对数据进行“尽力传递”，即只管将分 组传往信宿机，无论传输f 确与否，不做验证、不发确认，也不保证分组的正 确顺序。 i p 协议本身不涉及具体的寻径技术细节，它只描述数据报寻径的一般原 理和规则，包括表驱动寻径原理、寻径与网问网体系结构及i p 地址的关系、 寻径的分类等。具体的寻径技术如寻径表的建立与刷新机制，由一组独立的寻 径协议描述，如内部路由选择协议r i p 、o s p f ，外部路由选择协议b g p 、e g p 等。 1 p 协议的差错处理主要通过i c m p 协议来完成。 2 t c p 协议 t c p 协议提供面向连接的可靠数据流传输。它提供的可靠性被称为端到 端可靠性，其优点是：简洁清晰、效率高。 t c p 协议采用的最基本的可靠性技术是：确认与超时重传。流量控制与 拥塞控制也是t c p 协议实现可靠性的一种措施。 影响确认与超时重传最关键的因素在于定时时间片的大小。t c p 采用一 种适应性重传算法，其思路是：t c p 监视每一条连接的性能，由此推算出合 适的时间片，当连接性能发生变化时，t c p 随即改变时间片值。 t c p 协议使用滑动窗口机制进行流量和拥塞控制。 1 1 2 网络服务 - i n t e r n e t 网能够迅速发展，把越来越多的人吸引到i n t e r n e t 中来，并被网上 l 无所不包的资源所征服，与i n t e m e t 网提供的众多服务是分不丌的。i n t e r n e t i 网提供了大量的网络服务：网络浏览、电子邮件、远程登录、文件传输、电子 公告牌等。 随着i n t e m e t 网的发展，也涌现出一些新的服务，如视频会议、远程教学- 电子科技人学博十论文 等，7 i z ”l = 由于这些新服务的出现，使i n t e r a c t 网的技术面临新的挑战。 1 2 使用多播通信的原因 随着i n t e m e t 网的普及，使用i n t e r n e t 网的人越来越多，应用i n t e m e t 的领 域也不断扩大，因而，涌现出大量的新应用，如软件分发、视频会议、信息发 粕( 如股票信息、w e b 缓存更新) 、远程教学和共享“白板”等 1 ，2 , 3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，这些新应用都有一个共同的特征：一对多或多对多的可 靠数据通信，其潜在的接收者可能成百上千，所以，要求发送者能够高效地把 数据传送给所有接收者。由于i n t e m e t 网的体系结构是针对点对点设计的，如 t c p 协议支持两台主机进行端到端的可靠通信，使传统i n t e r n e t 网技术受到了 极大的挑战。为了使这些新应用能高效地传递数据，多播通信技术应运而生。 多播通信能把数据从一个发送者高效地传送给一个通信组的所有接收者， 与多路单目( u n i c a s t ) 方式相比，多播通信能显著地降低网络与端系统的丌销。 在迸一步阐述多播通信特性之前，我们先明确几个基本概念。单目( u n i c a s t ) 通 信是指一台主机发送数据给另一台特定的主机。广播( b r o a d c a s t ) 指- - 台主机发 送数据给一个子网内的所有接收者。多播( m u l t i c a s t ) 指一台主机发送数据给一 个通信组内的所有接收者，这些接收者既可以是同一子网中的主机，也可以是 不同子网中的主机。因此，如果不使用多播通信方式，仍然使用i n t e m e t 的 u n i c a s t 方式，则上述新应用必须使用多路u n i c a s t 方式来实现，即发送者与每 一个接收者建立一个u n i c a s t 来传递数据。下面我们举一个简单的例子来说明： 必须在i n t e m e t 中使用多播通信技术才能有效地满足新应用高效传递数据的要 求。 我们使用多播通信树来描述多播通信的网络结构，如图1 1 所示。树的根 结点是发送者，叶子结点是接收者，中白j 结点( 非叶子结点) 是路由器。在进 行多播通信时，每个非叶子结点为每条分枝复制包，这样由根结点发出的每个 包在传送给接收者时，仅遍历树的每条边一次，而多路u n i c a s t 通信必然导致 树中的某些边被多次遍历，所以，相对于多路u n i c a s t 传输来说，多播通信最 大的优势就是能节约网络带宽，减少网络丌销。例如，设有一棵多播通信树， 它是一棵高度为h 的完全d 叉树( 见图1 1 ) 。假设现简单地将网络丌销定义 第一章导论 为一个包在树中遍历的边的总数。使用多路u n i c a s t 方式传输数据时，从根结 点发送一个包给所有dn 个接收者，需要遍历的边的总数为d “h 。相反，使用 多播方式传输数掘时，每条边只需要遍历次，所以，需要遍历的边的总数为 n ：d ，。假设多播通信树有2 7 个接收者，对于多路u n i c a s t 方式，遍历的边 的总数为33 * 3 = 8 1 ；而多播通信遍历的边的总数仅为3 1 + 3 2 + 3 3 3 9 ，节约丌销 近5 1 。并且随着接收者的增加，多播通信节约网络开销的能力更强。 接收者 图1 1 多播通信树示意图 从这个简单的比较中，我们知道，对于上述新应用，必须使用多播通信来 提高传输效率。i n t e m e t 网的i p 协议 1 0 ，1 1 ，1 2 经过扩展后可以支持多播通 信。i p 协议规定的i p 地址有不同类型，其中a 、b 、c 类地址用于支持两台 主机之间的通信；d 类地址即是为多播通信而保留的地址。x e r o xp a r c 的s t e v e d e e r i n g 就开发了基于i p 层的多播通信，它允许从一台主机发送i p 数据包到 一个“多播通信组”中的多个主机。i p 多播通信组的成员可以是动态变化的， 主机可以随时加入或退出多播通信组。 由于i n t e m e t 的体系结构并不是针对多播通信来设计的，所以，在i n t e r n e t 网上开展多播通信必须解决诸多问题。 1 3 面临的问题 可伸缩可靠多播通信必须确保大量的接收者可靠地接收数据，而不是保证 4 电子科技人学博十论文 仅有一个接收者正确收到数据。虽然多播i p 地址支持多播通信但其传递数 据的方式与u n i c a s t 传递一样，不保证数据的可靠性，仅“尽力传递”数据， 这样数据可能在传递过程中丢失或不能到达所有接收者，所以，多播通信必须 解决可靠性问题。由于传统i n t e r n e t 网的技术本身还存在一些有待解决的问题， 如q o s ，进行多播通信时也将遇到相同的问题；另外，i n t e r n e t 的体系结构是 针对点对点设计的，在其上开展多播通信应用，也不可避免地会遇到一些新问 题。下面概括了多播通信面临的关键问题，也是本论文研究的重点问题。 1 3 1 反馈信息爆炸 为了确保发送者可靠地传输数据给所有接收者，接收者向发送者反馈信息 是非常重要的。t c p 协议就使用反馈信息来解决数据可靠传递的问题：当接 收者f 确接收到每个包后，就发送确认信息a c k 给发送者，如果接收者检测 到包丢失，则反馈负确认信息n a c k 给发送者。发送者根据收到的反馈信息 可以知道哪些包已被接收者f 确收到，哪些包需要重传。对于u n i c a s t 来说， 这种方式能正确地解决可靠性问题，并且不会带来更大的负面影响。但是，如 果在多播通信中也使用这种方式，当接收者数量大时，对每个被f 确收到的包 都反馈确认a c k ，将使a c k 数量急剧增加，导致所谓的“a c k 爆炸”，使发 送者只能忙于处理大量的a c k ，而没有时间发送数据。同时，基于a c k 的方 法要求发送者对每个包维护一张接收者的a c k 表。这样，将导致发送者负担 过重，特别是当有大量的接收者时。由于存在a c k 爆炸和需要大量丌销来维 护每个接收者的请求，所以，基于a c k 的方法不能适合用于可伸缩可靠多播 通信。另一种方法就是基于n a c k 的方法，它将恢复丢失数据的责任交给了 接收者接收者f 确收到每个包后，不向发送者反馈a c k ，只有当接收者检 测到包丢失后，才发送n a c k ，请求重传该包。因为n a c k 的数量明显少于 a c k ，所以，在多播通信中使用基于n a c k 的方法更具有可操作性。同时， 发送者不必识别接收者的请求，可以不维护针对每个接收者的n a c k 表，从 而降低了发送者的负担，所以，基于n a c k 的方法更适合多播通信。但当网 络中接收者数量巨大且网络丢包概率大时，仍然会有n a c k 爆炸的问题。所 以，在设计可伸缩可靠多播通信协议时，一个重要的问题就是如何处理a c k 第一章导论 或n a c k 爆炸。 为了处理a c k 爆炸或n a c k 爆炸，国外前期工作有两个研究方向： ( 1 ) 使用随机定时器方法来抑制n a c k 1 3 ，1 4 ，1 5 。这种方法的基本思 路是：当接收者检测到丢失包后，等待一个随机时问，再使用多播通信方式发 送n a c k ，这样，不但向发送者请求了重传数据，而且让通信组中的所有成 员都知道已经发出了重传请求。如果接收者在随机等待时问内，收到了请求同 一个包的n a c k ，则抑制自己的n a c k ，即不再发送相同的n a c k 。这样， 就可减少n a c k 的数量，从而避免n a c k 爆炸。 ( 2 ) 等级结构方法 1 6 ，1 7 ，1 8 ，1 9 。这种方法的基本思路是：接收者、路 由器或服务器、发送者构成一棵等级结构树，对树进行子树分割，即对接收者 进行分区，每个区选择一个接收者作为代理( 如r m t p 1 6 中的d e s i g n a t e d r e c e i v e r ) ，由代理负责处理n a c k 和数据重传。代理的主要工作是实现n a c k 的融合和数据重传。d r 缓存所有的数据，当它收到来自接收者的n a c k 时， 首先检查自己的缓冲区中是否有请求的数据，如果有，则向请求者重传该数据， 如果没有，则再检查是否已经向上级结点发送了请求该数掘的n a c k ，如果 已经发送，则进行融合处理，不再重复向上级结点发送相同的n a c k ，从而 减少n a c k 的数量，避免n a c k 爆炸。 等级结构方法具有较好的局部恢复数据的能力，但子树分割和选择代理非 常困难，也难以适应动态变化的网络，且数据的可靠性与代理直接相关。定时 器方法能适应网络的变化，且由发送者负责处理n a c k 和重传数据，可靠性 更能得到保证。 1 3 提出了定时器方法，但没有对定时器的设置方法进行深入 的分析， 2 0 针对仅使用a r q ，接收者数量达到1 0 6 的多播通信，分析了设 置定时器时间的概率按指数分布时，能避免反馈信息爆炸，且由定时器引起的 延时短，但没有讨论引入f e c 技术后设置定时器的方法及性能分析。本文将 提出在集成f e c 系统中的设置定时器的两种方法。 1 3 2 重传范围 接收者检测到一个包丢失后，请求发送者重传该包。发送者在重传请求包 时，有两种方式：使用u n i c a s t ，仅重传丢失包给请求者；使用多播方式，重 电子科技人学博七论文 传丢失包给组内所有成员。当丢包概率高和接收者多时，可能有多个接收者请 求同一个包，所以，使用u n i c a s t 方式重传丢失包效率低。而使用多播方式重 传包则效率相对较高，因此，重传数据也最好使用多播方式。但是多播重传数 据也引起了另一个问题。如果在同一个多播通信组中多播重传包，则组中所有 接收者都将收到该重传包，而不是仅丢失包的接收者收到重传包。这样，没有 丢失包的接收者将浪费带宽和进行不必要的重复处理。所以，国外不少研究者 提出了局部恢复数据的方法，如等级结构方法就有较好的局部恢复数据的能 力，但它却有等级结构划分困难等问题。本论文将提出基于可靠主动结点的方 法，能很好地实现数据的局部恢复，避免浪费带宽。 1 3 3 恢复负载 当接收者数量多或丢包概率高时，至少有一个接收者丢失包的概率就非常 大。假设有r 个接收者，每个接收者丢包事件是相互独立的，且其独立丢包 概率均为p ，则至少有一个接收者丢包的概率是1 - ( 1 p ) 8 。假设p = 0 0 1 ，当 有5 0 0 个接收者时，至少有一个接收者丢包的概率为o 9 9 3 4 ，几乎等于1 。而 在实际应用中，接收者数量可能远大于5 0 0 ，这样几乎每个包都需要重传，且 可能多次重传。在这种情况下，发送者与发送者邻近的链路就容易形成瓶颈而 降低性能。所以，发送者如何高效地恢复丢失数据也是一个重要的问题。 要解决发送者负载过重的问题，同样也必须提高网络局部恢复数据的能 力。本论文提出的基于可靠主动结点的方法，其局部恢复数据的能力很强，从 而可以减轻发送者的负担。 1 4 论文贡献 本文主要研究可伸缩可靠多播通信的问题，重点解决n a c k 爆炸、局部 恢复数据等关键技术。其主要贡献是： 提出了两种抑制n a c k 的定时器设置方法； 评述了国内外常用的多播通信协议，据此，提出了基于可靠主动结点 的可靠多播通信协议( r a n r m ) ； 第一章导论 使用c p n 对r a n r m 协议进行了建模分析： 通过模拟程序分析了r a n x m 的性能，对实现r a n p 洲具有指导意义。 1 5 本文的章节安排 第二章论述了多播通信的基本技术，阐述了多播通信的机制与功能，涉及 有关多播通信寻径、端到端系统及应用程序等方面的问题，还提出了设计多播 通信协议时需要考虑的一些基本问题；最后总结了国外已提出的常见多播通信 协议。 第三章针对可伸缩可靠多播通信中存在的反馈信息爆炸的问题，提出了基 于定时器的抑制n a c k 的两种方法：基于指数分布、均匀分段方法和基于指 数分布、非均匀分段方法。分析表明：对接收者数量达到1 0 ”数量级的多播通 信，这两种方法都能避免反馈信息爆炸，且由定时器引起的n a c k 延时短。 第四章建立了主动网络中多播通信的协议分层模型，并提出了基于可靠主 动结点的可靠多播通信协议r a n r m ( r e l i a b l e a c t i v en o d er e l i a b l e m u l t i c a s t ) 。分析了r a n r m 占用带宽和数据恢复的延时，与协议n 2 1 5 比较 表明：r a n r m 占用带宽少，数据恢复的延时短。 c p n ( c o l o u r e dp e t r in e t ) 是由丹麦的j e n s e nk u r t 在p e t r i 网基础上定义的一 种高级网系统。第五章建立了r a n r m 协议的c p n 模型，进行了仿真运行和 动态特性分析。 第六章利用a n t s 设计模拟程序，验证r a n r m 协议能否进行正常的多 播通信，并通过实验数掘比较了r a n r m 与n 2 的性能。 第七章对全文进行了总结，提出了进一步的工作方向。 电子科技人学博十论文 第二章多播通信的基本技术 这一章我们将阐述多播通信的基本技术，它涉及三方面的问题： ( 1 ) 多播通信的机制与功能，包括多播通信寻径、端到端系统及应用程序 的相关问题； ( 2 ) 设计协议需要考虑的一些问题； ( 3 ) 目前已提出的常见多播通信协议。 2 1 多播通信机制与功能描述 这一节将讨论多播通信的机制与功能，但没有采用传统的分层结构来描述 多播通信 2 2 。下面将从三个方面来描述多播通信的机制与功能：( 1 ) 与寻径 相关的问题；( 2 ) 与端到端系统相关的问题i ( 3 ) 与应用程序相关的问题。 2 1 1 驿站到驿站( h o p - b y h o p ) 1 多播通信组地址与组员管理 前一章我们提到在i n t e m e t 网上存在三种数据传递方式：u n i c a s t 方式、广 播方式和多播方式。t c p i p 协议早期只支持前两种方式，经过扩展后，i p 协 议支持多播方式，但多播方式需要依赖于u n i c a s t 或广播。作为硬件基础的低 层物理网络技术本身，只有很少的硬件支持多播方式。 在i n t e m e t 网上进行多播通信，需要为每一个多播通信组分配一个唯一的 i p 地址，以便i p 层能对不同的多播通信组进行识别。i p 地址中的d 类地址就 是多播地址，可以用于多播通信。 如果某主机加入多播通信组时需要跨越物理网络，则必须事先将加入某多 播通信组的信息通知本地多播网关，该信息叫作组员身份信息。然后，各多播 网关之间再互相交换各自的多播通信组信息，以建立多播传送路径。多播网关 第二二章多播通信的基本技术 与参与多播传送的主机之问交换组员信息的协议叫作“i n t e r n e t 网组管理协议” r 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 n t e r n e t 网上的其他多播网关通告此组员身份信息，以建立必要的路径；为 适应组员身份的动态变化，本地多播网关周期性地查询本地主机，以确定哪些 主机仍然属于哪些多播通信组。假如查询结果表明某多播通信组中已无本地主 机成员，多播网关一方面将停止通告相应的组员身份信息，同时不再接收相应 的多播数据报。 2 寻径 ( 1 ) 寻径的基本理论 多播通信组中成员可能发生改变，网络拓扑结构也可能发生变化，所以， 设计多播通信的寻径算法是一个复杂的问题。设计多播通信的寻径算法必须考 虑如下问题： 最小化网络负载：包括网络资源优化、避免出现寻径圈、避免流量集 中于某一链路或子网中。 支持可靠传输：理想情况是路由的改变不影响向剩余成员传递数据； 某连接线路故障不增加传输延迟或降低可用资源。 根据可用资源、带宽、链路数、费用、端到端延时等因素进行优化； 使路由器保存的状态信息最小化。 泛滥算法是最简单的寻径算法，其算法思路是路由器收到一个包后，向与 该路由器相连的所有端1 3 传送该包，这样，必然导致非常低的传输效率和链路 利用率。显然，该算法不适合多播通信，更不能支持可伸缩多播通信。生成树 算法对泛滥算法进行了改进，支持在互联的l a n 中广播包，其效率更高。 理想的寻径算法应该生成一棵多播通信树，其结点只有组内成员，并且包 含下列特性： 必须区分组内成员，并能将包传递给它们，且只传给这些成员； 结点保持信息最少；根据丌销优化路由； 电子利技人学i 尊1 一论文 避免流量集中于某一子网的链路和少量结点。 具有代表性的三个生成多播通信树的基本算法是： 基于源寻径：r p f ( r e v e r s ep a t hf o r w a r d i n g ) 2 3 】：是基于源的寻径算法， 被广泛地用于i p 多播通信。r p f 算法根据传输延迟为每个源计算生成树。对 于接收者分和稠密的网络，可以优化r p f 算法，并能以分布方式实现该算法。 由于树是一个有向图，所以使用r p f 不会形成寻径圈。r p f 算法的优点是只 需要传统的u n i c a s t 寻径表，而不需要请求其他资源。 多播通信需要处理通信组中成员的加入与离去。r p f 算法使用剪枝变化 ( t h ep r u n i n gv a r i a n t ) 来解决这个问题。其思想是：通过记录“组成员”完成基 本的r p f ，只有当组成员在树的下端时才传递包。路由器周期性地清除组状 态信息，并抛弃保存在结点的剪枝消息。当传输新数据时，使用泛滥算法，并 激活新的剪枝消息，构造新的剪枝后的多播通信树。r p f 的主要问题是：剪 枝请求的每个源和每个组的状态信息必须保存在每个结点中。当通信组少和每 个组中的源少时，这种情况还能被接受，反之，路由器的内存占用就将趋于饱 和。 s t e i n e r 树：根据最小费用生成多播通信树。使用集中计算方法( 启发 式算法可以分布计算) 。其特点如下： s t e i n e r 问题是一个n p 一完全问题。也就是说，发现最小s t e i n e r 树是 一个对数级丌销。己证明s t e i n e r 树的最小丌销是o ( n l o g n ) ，n 是网络 中的结点数 2 4 。 树是单向的，即只有当网络中的所有链路是对称的才能将它用于多播 通信中。 每一次组成员或网络拓扑结构变化，都必须重新计算一次多播通信 树，这将导致s t e i n e r 树的效率大幅度降低。 基于中一心的树：是一种较新的算法，针对多发送者和多接收者的情况， 有代表性的算法是c b t 树( c o r e b a s e dt r e e 2 5 ) ，它是一种完全基于接收者的 方法，适合稀疏分布的接收者，且不增加过多额外的延迟。其算法分三步： 选择个固定的结点作为通信组的中心结点。为了提高容错能力和降 低延时，可以使用多核心方法。 潜在的组成员向中心结点发送加入组的消息。中问结点的作用是标记 第一二章多播通信的基本技术 从哪个接口收到多播包，从哪个接口发送包给中