（计算机系统结构专业论文）可靠组播协议的研究与改进.pdf

可靠组播协议的研究与改进 摘要 随着i n t e r n e t 的发展，越来越多的单点到多点的数据传输应用应运而生。 组播比传统的单播和广播协议更适合这种一对多的数据传输。传统的组播虽然 具有网络利用率高、能节省发送者的资源的特点，但却不能保证所有数据都可 靠有序地传送给每个组播成员。可靠组播协议就成了组播研究的热点问题。目 前，对可靠组播的研究和改进有很多，大部分是从差错控制和恢复、拥塞控制 方面进行研究和改进的。差错控制和恢复又分为自动重传a r q 、前向错误纠正 f e c 、a r q 和f e c 混合三种方式。自动重传a r q 由于实现较为简单而经常被 人们使用，但a r q 中的反馈机制带来的反馈风暴问题对可靠组播的可扩展性 提出了挑战。 本文首先从组播的基本概念出发，叙述了组播的工作原理、可靠组播的概 念和必要性，详细介绍了可靠组播的核心技术一一差错控制与恢复和拥塞控制。 然后，为了解决反馈内爆给可靠组播的可扩展性带来的问题，文章从n a c k 压缩角度对传统的可靠组播协议进行了改进，提出了给反馈设置定时器，并通 过使反馈基于反馈报文的长度来发送的方法，更有效的减少了系统的n a c k 报 文数量，同时，进一步设置参数，使系统在有效避免反馈风暴的基础上增强系 统的实时性。文章还通过n s 系统仿真实验，验证了改进的协议在n a c k 压缩 上的显著效果。 最后，文章介绍了改进的协议在智能公交项目中的应用。将协议应用在系 统无线下载部分，不仅减少了监控中心的工作时间和车载终端的等待时间，也 降低了反馈带来的网络流量的增加，同时，增强了数据传输的可靠性，使系统 在利用无线网络数据传输的方便性的同时，不再担心由无线网络的不稳定性导 致的数据传输的差错。 关键字：组播；可靠组播协议；差错控制；反馈抑制；n s 仿真 r e s e a r c ha n di m p r o v e m e n to nr e l i a b l em u l t i c a s tp r o t o c o l a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e t ，m o r ea n dm o r es i n g l e m u l t i p o i n td a t a t r a n s m i s s i o na p p l i c a t i o n sc a m ei n t o b e i n g m u l t i c a s t i sb e t t e r s u i t e dt h i s o n e t o m a n y d a t at r a n s m i s s i o nt h a nt h et r a d i t i o n a lu n i c a s ta n db r o a d c a s t t r a d i t i o n a lm u l t i c a s th a sag o o du t i l i z a t i o no ft h en e t w o r ka n dah i g hs a v i n gt h e r e s o u r c e so ft h ec h a r a c t e r i s t i c so ft h es e n d e r ，b u tc a nn o tg u a r a n t e et h a ta l ld a t aa r e r e l i a b l ya n do r d e r l y d e l i v e r e dt oe a c hm u l t i c a s tm e m b e r r e l i a b l em u l t i c a s t p r o t o c o lm u l t i c a s tr e s e a r c hh a sb e c o m eah o ti s s u e c u r r e n t l y ，t h e r ea r em a n y r e s e a r c h e sa n di m p r o v e m e n t so nr e l i a b l em u l t i c a s t ，m o s to ft h e mr e s e a r c ha n d i m p r o v eo nm u l t i c a s ti nt e r m so f t h ee r r o rc o n t r o la n dr e c o v e r y ，c o n g e s t i o nc o n t r 0 1 e r r o rc o n t r o la n dr e c o v e r yi sf u r t h e rd i v i d e di n t oa u t o m a t i cr e p e a tr e q u e s ta r q ， f o r w a r de r r o rc o r r e c t i o nf e c ，a r qa n df e cm i x e d a u t o m a t i cr e p e a tr e q u e s ta r q i so f t e nu s e db e c a u s ei t sr e l a t i v e l ys i m p l e ，b u tt h ef e e d b a c ki m p l o s i o nw h i c ha r q f e e d b a c km e c h a n i s ma r i s eb r i n g sc h a l l e n g e st ot h es c a l a b i l i t yo fr e l i a b l em u l t i c a s t t h i sp a p e r , s t a r t i n gf r o mt h eb a s i cc o n c e p t so fm u l t i c a s t ，d e s c r i b e dt h e w o r k i n gp r i n c i p l eo fm u l t i c a s t ，t h ec o n c e p t sa n dn e e do fr e l i a b l em u l t i c a s t ，a n d d e t a i l e di n f o r m a t i o no nt h ec o r et e c h n o l o g yf o rr e l i a b l em u l t i c a s t - e r r o rc o n t r o l a n dr e c o v e r ya n dc o n g e s t i o nc o n t r 0 1 t h e ni no r d e rt os o l v et h ep r o b l e m sw h i c hf e e d b a c ki m p l o s i o nb r i n gt ot h e s c a l a b i l i t yo fr e l i a b l em u l t i c a s t ，t h ep a p e ri m p r o v e st r a d i t i o n a lr e l i a b l em u l t i c a s t p r o t o c o lf r o mt h ep e r s p e c t i v eo ft h en a c kc o m p r e s s i o na n dp u t sf o r w a r dt h ei d e a o fs e t t i n gt h et i m e rt ot h ef e e d b a c k ，a n dr e d u c e st h en u m b e ro fn a c kp a c k e t sm o r e e f f e c t i v e l yb ym a k i n gt h ef e e d b a c ks e n tb a s eo nt h el e n g t ho fp a c k e t i ts e t st h e p a r a m e t e r s ，e n h a n c e st h er e a l t i m es y s t e m o nt h eb a s i so fa v o i d i n gf e e d b a c k i m p l o s i o ne f f e c t i v e l y t h ea r t i c l ea l s ot e s t s t h es i g n i f i c a n te f f e c to nn a c k c o m p r e s s i o no f t h e i m p r o v e dp r o t o c o lt h r o u g h t h en ss y s t e ms i m u l a t i o n e x p e r i m e n t f i n a l l y ，t h ep a p e ri n t r o d u c e st h ea p p l i c a t i o no ft h ei m p r o v e dp r o t o c o li nt h e i n t e l l i g e n tp u b l i ct r a n s p o r tp r o j e c t s t h ea p p l i c a t i o no ft h ep r o t o c o li nt h ew i r e l e s s d o w n l o a dp a r to ft h em o n i t o r i n gc e n t e rn o to n l yr e d u c e st h ew o r k i n gh o u r so ft h e m o n i t o r i n gc e n t e ra n dt h ew a i t i n gt i m eo fc a rt e r m i n a l s ，b u ta l s o r e d u c e st h e i n c r e a s e dr u n o f fo ft h en e t w o r kc a u s e db yt h ef e e d b a c k 。w h i l ee n h a n c i n gt h e r e l i a b i l i t yo fd a t at r a n s m i s s i o ns ot h a tt h es y s t e mn ol o n g e rw o r r i e sa b o u tt h ed a t a t r a n s m i s s i o ne r r o r sc a u s e db yt h ei n s t a b i l i t yo ft h ew i r e l e s sn e t w o r kw h e nu s i n go f t h ec o n v e n i e n c eo fw i r e l e s sn e t w o r kd a t at r a n s m i s s i o n k e y w o r d s ：m u l t i c a s t ；r e l i a b l em u l t i c a s tp r o t o c o l ；e r r o rc o n t r o l ；f e e d b a e k c o m p r e s s i o n ：n se x p e r i m e n t 图表清单 图2 1 单播数据流传输示意图4 图2 2 广播数据流传输示意图。5 图2 3 组播数据流传输示意图6 图3 1f e c 编码译码过程1 8 图4 1n s 体系结构图2 8 图4 2n s 网络仿真流程图2 9 图4 3 典型的组播网络模型一2 9 图4 4 发送者( 组长) 和接收者( 组员) 初始状态3 5 图4 。5 发送者广播信息3 6 图4 6 组长向组员组播数据3 6 图4 7 组员组播自己的反馈信息3 7 图4 8 不同运行时间下两种协议的n a c k 数目比较3 7 图4 9 不同节点数时两种协议的n a c k 数目比较3 8 图5 1 智能公交系统结构图3 9 图5 2 语音系统流程图4 1 图5 3 车载终端无线下载结构图4 2 图5 - 4 监控中心工作流程图4 2 图5 5 车载终端工作流程图4 3 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得 金胆王些太堂 或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意。 学位论文作者签字：砀岛撷 学位论文版权使用授权书 签字日期：溯0 孕劫 本学位论文作者完全了解 金胆王些太堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权金目墨王些太堂可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：砀毒询 签字日期：如，d 年，沙 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师掘札呼 导师签名：n ，o l 又 签字日期： t 叫0 斗1 - 电话： 邮编： 致谢 非常感谢我的导师张维勇教授。从课题方案的制定到理论知识的学习和研 究，实验的分析和完善到最后的系统软件的实现，张老师都给予我极大的指导 和帮助。两年半的硕士研究生学习期间，张老师对我思想上、学习工作上的循 循善诱和谆谆教诲，以及生活上无微不至的关怀和照顾，使我终身受益。张老 师渊博的知识、忘我的工作态度、诲人不倦的师长风范以及不断进取、精益求 精的精神，都将对我今后的学习、工作产生深远的影响，是我一生学习的榜样。 在此谨向张老师表示最由衷的感谢! 同时我要感谢分布式控制实验室智能公交项目组的所有成员，特别是马学 森老师，他们给我充分的信任和大力的支持，让我得到充分的锻炼。感谢蔡志 文师兄、唐璐师姐、江月、吴迈等同学，通过与他们的讨论，让我在自己研究 的方向上一步步前进。 感谢我的师兄任宇、季炎、李立、陶杰、许磊、时伟以及师姐彭静、张芬， 感谢他们一直以来对我学习和生活上的帮助和鼓励。同时还要感谢与我同届的 同学一一肖冰冰、程敏、樊高雁，以及我的室友郎加云、王玲玲。 最后，我要向我的父母表示最深的感谢。他们一直在默默的支持我，成为 我最大的精神支柱和前进的动力! 衷心的感谢所有关心和帮助过我的人们。 作者：陈冬梅 2 0 10 年3 月 第一章绪论 1 1 研究背景 随着计算机技术和以全球互联网为代表的各种网络在近些年来的迅猛的 发展，网络带宽越来越高，用户数量越来越多，人们对网络上的c s c w ( c o m p u t e r s u p p o r t e dc o l l a b o r a t i v ew o r k ) 、远程会议、股票交易、视频点播、远程教育、 在线拍卖、分布式交互模拟( d i s t r i b u t e di n t e r a c t i v es i m u l a t i o n ) 等分布式应用的 需求越来越显著。通过对上述应用的分析可知它们都有以下特点： 分布于不同地域的应用可以组成一个或多个组，应用可以加入一个或多 个组而成为所加入组的组成员； 组内的任何一个组成员可以不用保存该组的组信息，例如改组的成员数 目、组内具体包含哪些成员等； 任一组成员都可以向该组其它成员发送数据； 组内的任何一个组成员向该组成员发送数据时，组内其它成员都能收到 它发送的数据，如果有的应用提出了可靠性的要求，则必须保证组内其它成员 也都能正确收到它发送的数据； 任何一个组成员向该组其它成员发送数据时，非该组成员不会收到它发 送的数据。 这些特点使得传统的单播发送( u n i c a s td e l i v e r y ) 和广播发送( b r o a d c a s t d e l i v e r y ) 方式无法对上述那些应用提供良好有效的支持。因为单播对带宽和网 络流量都有较大的消耗，该发送方式的工作原理也限制了它的接收者的数量不 能过大，而且如果组成员没有保存该组内有哪些成员等组信息，则上述应用就 无法用单播发送来实现。而若采用采用单点到所有点的广播发送方式来实现， 就会存在大量主机收到与自己无关的数据，造成主机资源和网络资源的浪费。 在这种条件下，组播在这些应用中就变得越来越重要。组播( m u l t i c a s t ) 是 指将数据分组信息从一个站点发送给多个站点的通信机制。在组播中，最理想 的情况是发送者每次只发送一个数据包，而在每条数据链路上也只有一个数据 包经过。组播由于具有可扩展性较强、网络利用率高、能节省发送者自身的资 源的优点，在现代大量单点对多点的新型网络应用中发挥了极大的作用。但传 统的组播技术虽然能较好地利用带宽，尽力而为的转发数据，但却不能保证可 靠有序地将所有组播数据传送给每个组播成员，这种服务无法满足对组播传输 的有着各种不同程度质量要求的应用，于是可靠组播的概念应运而生。 可靠组播的目的是为了保证每个接收者都能正确地接收到所有的组播数 据。对组播可靠性的研究主要归结到对组播网络的反馈控制、拥塞控制、差错 检测和恢复等问题的研究上。为满足应用对组播可靠性的要求，组播必须要有 快速高效的差错检测和差错恢复机制，且其处理方式应具备高效性和可扩展 性。可靠组播协议的设计，尤其是当节点比较多、网络规模比较大时，是一个 非常困难的问题。大规模可靠组播的具有以下的特点：组播组的规模很大，接 收者的数量众多；组播成员分布在广阔的地域上，接收者的带宽常常受地域影 响，即不同地域的接收者的带宽不同，有的带宽甚至是动态变化的；接收者可 以动态加入或退出某个组播组而不影响其它接收者的工作。 1 2 论文研究的内容和意义 组播因为是基于“尽最大努力”( b e s t e f f o r t ) 传输，因此所提供的服务 是不完全可靠的：它不能保证每一个组播数据都能正确的送到该组所有的接收 者那里。但是，对于像分布式数据库管理、分布式协调计算这样的组播应用， 对系统的可靠性要求比较高，因此负责对其进行数据传输的组播的可靠性也必 须有所保障。可靠的组播主要在组播的基础上增加了状态控制、差错控制、拥 塞控制以及速率调节算法等技术，其中，差错控制和拥塞控制是可靠组播的核 心问题。 目前，对可靠组播的研究很多，但从目前国际上的发展来看，对可靠组播 协议还没有形成完全统一的思想，正处于一个开放的阶段。最短路径优先组播 路由协议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 ) 、可扩展的可靠组播协议 s r m ( s c a l a b l er e l i a b l em u l t i c a s t ) 、协议独立的组播路由协议p i m ( p r o t o c o l i n d e p e n d e n tm u l t i c a s t ) 等适用于不同应用的组播协议已经陆续提出，本文主要 从差错控制角度对可靠组播协议进行研究和改进。 可靠组播的差错控制主要包括差错检测和差错恢复两个部分，且其处理方 式应具备高效性和可扩展性。差错检测可由发送者或接收者进行，应考虑发送 者的负荷、所消耗的网络资源、差错检测的实时性和如何避免大量反馈信息带 来的“反馈风暴 这些问题。t c p 使用a c k 机制来确认数据包的接收，而这种 方式应用到组播中，就可能有大量的a c k 报文聚集在发送者那里，造成“a c k 风暴”。t c p 中发送者必须维护接收者的状态信息来确保对已发送包的确认， 且a c k 反馈要经过整条路径传送给发送者，对网络资源造成了很大的消耗。对 于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 论文的组织结构 论文的章节内容安排如下： 第一章为绪论，主要介绍论文的研究背景、研究内容和文字的组织结构。 第二章介绍了组播技术，主要包括组播的工作原理及其与单播的比较、可 靠组播的概念、必要性以及保证组播可靠性的方法，主要介绍可靠组播的核心 技术一一差错控制与恢复和拥塞控制。 第三章消息介绍当前差错控制主要采用的技术，包括自动重传a r q 、前向 纠错f e c 、混合差错控制h e c 这三种传统的技术以及当前的新研究热点一一 基于路由的差错控制。 第四章从n a c k 压缩角度对传统的可靠组播协议进行改进，并通过n s 系 统仿真实验，验证了改进的协议在n a c k 压缩上的显著效果。 第五章介绍了改进协议在智能公交项目中的应用，将该协议应用在系统无 线下载部分，可以提高系统数据无线传输的安全性和可靠性。 第六章为工作总结和展望，对本文的工作做了一个回顾总结，并提出了未 来的研究和方向。 第二章组播技术 组播( m u l t i c a s t ) 数据传输是一种单点对多点的数据发送方式，处于一个 组中的所有成员可以共享信息。组播具各可以节约网络流量以及发送者自身资 源、可扩展性较高这些特点( 尤其在网络规模较大、节点数较多的情况下，这 些特点的优势更加明显) ，因而在现在大量例如视频点播、在线教学等新型网络 应用中发挥了很大的作用。本章将全面介绍组播的工作原理、可靠组播的概念 以及保证组播可靠性的方法。 2 1 组播的必要性 由于具备单点对多点结构的应用的不断增加，单播或广播方式已经越来越 不能满足人们的需求，组播的出现和发展成为一个必然。 2 1 1 组播的工作原理 组播技术支持将一个数据包从一个站点发送到多个站点的通信方式，参与 这种通信并共享资源的所有站点组成一个组播组，所有组播组成员拥有该组播 组的地址。发送者只需把数据包发送组播组中，该组的成员就会接收到该数据 包。采用组播方式传送数据，不管要发送给多少个接收者，在每条数据链路上 都只传输单一的数据包，因此组播可以有效地节省网络带宽、降低网络流量。 2 1 2 组播和单播、广播的比较 目前网络中主要有三种通讯模式：单播、广播、组播，其中的组播出现时 间最晚，但它具备了单播和广播的优点，因而最具有发展前景。 ( 1 ) 单播： 单播的优点： 图2 一l 单播数据流传输示意图 服务器对客户机的请求能够做出及时的反应： 对于不同客户的不同请求，服务器发送不同的数据，实现个性化服务。 单播的缺点： 由于服务器是针对每个客户机来发送数据的，因而服务器的流量等于所 有客户机的所有流量，即客户机流量与客户机数量之积，故当有大量客户存在， 每个客户机流量也大时服务器负担过重。 由于城际省际主干带宽仅占其所有用户带宽之和的百分之五，因此单播 协议的使用会造成网络主干负担过重。现在的单点对单点的应用就已经使主干 经常发生拥塞，只要消耗大量网络资源的客户达到百分之五，剩下的百分之九 十五人就没有任何资源可以利用了。 ( 2 ) 广播： 广播是主机之间“一对所有”的一种通信模式。对于每一台主机发出的数据 网络都进行复制转发，因此不管是否有接收数据的需要，每一个主机都会接收 到所有的发送信息。由于广播没有路径选择，所以网络成本低廉【2 1 。有线电视 网就是典型的广播网络，电视机虽然接收到所有频道的信号，但只将正在播放 的那个频道的信号转化成画面。在数据网络中也允许广播的存在，但为了防止 广播数据影响大面积的主机，广播被限制在二层交换机的局域网范围内以禁止 广播数据穿过路由器。 图2 - 2 广播数据流传输示意图 广播的优点： 没有路径选择，布网成本低。 服务器不需要向每个客户机单独发送数据，流量负载很低。 广播的缺点： 一对多的无选择目标的发送使得组播无法针对每个客户的不同要求提供 个性化服务。 服务器提供数据的带宽是有限的，客户端的最大带宽和服务总带宽相同。 如有线电视的客户端的线路可以支持一百个频道，为提高服务质量和服务种类 采用数字压缩技术，理论上还能再增加四百个频道，但在此基础上即使提供更 多的发送设备、改成以光纤为主干，也无法支持更多的频道，因此无法提供更 个性化、更多样化的服务了。 禁止在宽带网上传输。 ( 3 ) 组播： 主机之间“一对多”的数据传输模式，即在同一个组的主机可以接收到此 组内的发送的所有数据，交换机和路由器也并不是无条件的复制并转发数据给 所有主机，而是复制并转发数据给有需求的接收者。每个主机都可以申请加入 或退出某个组。只要有组播路由器的支持，并不限制一个组中的所有主机都处 于同一个物理网络中。路由器和交换机对数据进行有选择的复制和传输，即只 将数据传输给组内的主机，这样既避免了单播方式对有相同接收需求的主机一 个个发送的麻烦，又不影响其他不需要接收数据的主机，即未加入组播组的主 机，同时还减轻了网络流量负担。 图2 - 3 组播数据流传输示意图 组播的优点： 在实现各种一对多或者多对多的网络应用中，组播对有相同接收需求的 多个接收者一次发送数据的特点可以大大减小网络流量和经费以及服务器的负 担，使得应用程序可以更加高效地运行； 组播协议是根据接收者的需要对数据流进行复制和转发的，因此可以对 不同要求的应用提供不同的服务，而且服务端的服务总带宽不受客户接入端带 宽的限制。i p 协议允许两亿多万个组播，故其提供的服务非常丰富； 组播协议允许在i n t e r n e t 宽带网上传输。 组播的缺点： 由于没有纠错机制，数据传输中发生丢包错包后很难弥补，但差错控制 机制可以对丢包和错包进行弥补。 目前的网络对组播传输在客户认证、q o s 等方面的支持并不完善，这些 缺点虽然都有比较成熟的理论解决方案，但推广应用到现存的网络中还有大量 的研究应用工作需要做。 2 2 可靠的组播 组播技术虽然具备可以节省带宽、减轻网络流量负担、节省发送者资源等 优点，但由于组播使用的是用户数据包协议u d p ( u s e rd a t a g r a mp r o t o c 0 1 ) ， 故u d p 的不可靠性使得组播的传输需要相关的机制来增强其可靠性。对于i p 层的组播通信也只提供尽力而为( b e s t e f f o r t ) 的服务，并不能保证组播中数据 传输的可靠性。近些年来，采取相关机制保证可靠的组播r m ( r e l i a b l e m u l t i c a s t ) 成为组播研究的重要方向 3 1 。 2 2 1 可靠组播的概念 可靠组播主要是在保持传统组播基本通信原理的基础上，采用差错控制和 拥塞控制等机制来增强对组播数据传输的可靠性的保证。 2 2 2 影响可靠组播性能的要素 影响可靠组播性能的要素 4 1 主要有以下两个方面： ( 1 ) 数据吞吐率 即发送的有用数据同冗余数据和控制报文的比例。故要使吞吐率最大即要 使冗余数据和控制报文最小。控制报文主要是接收者向发送者发送的反馈信息。 如果采用a c k 方法，接收者每收到一个数据包就会向发送者反馈一个a c k 报 文，这样控制报文就会比较多；如果采用n a c k 的方法，在丢失率不高的情况 下，反馈报文就很少，在这种情况下影响吞吐率的因素就取决于冗余数据。冗 余数据主要指重传报文。如果采用基于n a c k 的方法，发送者比较接收者等待 接收的包序号和自己己发送的包序号，如果后者的序号大于前者，就发生数据 包丢失。发生数据丢失的原因主要有以下几点： 由于发送者不仅需要发送原始组播数据还要负责处理反馈报文和重传 数据，因此发送者常常因为负载太大而导致数据包丢失。一般来说，发送者发 送的原始组播数据的负荷量是设计者会提前考虑到的，基本上都是发送者可以 承受的范围之内的，而且大部分的设计都是在发送者空闲时才会考虑数据的重 传，因此重传的数据并不是造成发送者负载过大的主要原因，所以如何减少控 制报文的数量是设计中主要需要考虑的问题。 网络拥塞也是导致数据包丢失的主要原因。在拥塞严重的情况下，重传 数据包会加重拥塞，使数据丢失的情况愈加严重，同时数据包发生大量丢失的 情况还会带来大量的n a c k 反馈，从而引起反馈风暴。因此现在出现了基于窗 口或速率调节等一些组播拥塞控制方法，以避免和减轻网络拥塞。 不仅发送者的负载过大会造成丢失，接收端者的载太大同样会造成相同 的结果。一般来说，接收者主要根据接收的数据包序号来判断是否发送数据包 丢失，并向发送端发送n a c k 报文，然后接收发送者重传的数据包。在组播中， 接收者的负载小于发送者的负载量。 ( 2 ) 恢复时延 最理想的可靠组播应当是吞吐率最大，而恢复的时延最小。恢复时延，即 根据组播通信过程中丢失分组报文的情况来迅速、高效地组织丢失报文的恢复， 使发送者能够将组播数据正确、有序的传送给接收者。 2 2 3 可靠组播采用的关键技术 可靠组播的基本机制是在进行组播传输的基础上，进行数据丢失和错误的 检测，并通知相应的节点进行错误恢复。根据这些工作可靠组播中的关键技术 包括数据丢失和错误检测、报文反馈、数据重传，其中数据重传又包括重传什 么数据，由谁负责组织重传和如何重传。 ( 1 ) 数据丢失和错误检侧 数据丢失和错误检测的方法很简单【4 4 1 ，前者是通过比较连续两个数据包的 序号来判断是否有数据包丢失，后者则是对数据进行校验和检查来检测传输错 误。根据进行错误检测的节点类型不同，又可以分为基于发送者启动的协议和 基于接收者启动的协议。在基于发送者启动的协议中，接收者发送反馈a c k ( 表 示正确接收数据包的反馈) 向发送者通告自己已经正确接收到了数据包，发送者 在将数据包组播出去后，核对是否收到每个接收者反馈来的a c k ，如果没有收 到任何一个或几个接收者的a c k ，发送者就认为刚才发送的数据没有正确送 达，即发生了丢失。对于有大量组成员的组播组，就会产生大量的反馈，从而 引起a c k 泛滥，因此需要a c k 抑制( a c ks u p p r e s s i o n ) 机制。另外，在基于发送 者启动的方式中，发送者需要为每个接收者都维持状相应的态信息，这样在组 播接收者众多的情况下，对发送者自己的存储空间和资源都是一样极大的消耗。 而在基于接收者启动的协议中，每个接收者只要负责维持各自的状态信息，由 接收者自己来负责检查自己是否有数据丢失或错误，如果有，则单播或组播反 馈n a c k ( 未能正确接收反馈) ，报告自己没有接收到数据。这种情况在大部分 传输条件下都比基于发送者启动的组播能减小反馈报文的数量，减少发送端和 网络的资源消耗。显然，两种协议中，基于接收者的启动协议具有更好的可扩 展性，因而更适合大规模组应用的环境。 ( 2 ) 反馈 根据反馈包含内容的不同，反馈信号可分为两种：表示正确接收的反馈 a c k 和表示不正确接收的反馈n a c k 。根据采用单播方式还是组播方式来发送 反馈报文，反馈又可以分为单播反馈和组播反馈，两种发送方式对整个网络资 源有不同程度的消耗，对接收者造成的时延也不同。采用单播方式发送n a c k ， 每个接收者的丢失情况只有自己和接收者清楚，不同的接收者彼此之间并不清 楚，因此很容易存在不同的接收者发送对同一个数据包的丢失反馈，正是考虑 到这种情况中大量冗余报文的存在，采用组播来传输反馈信号可以实现对冗余 的反馈报文的压缩，从而减小对网络资源和服务器资源的消耗；但对于组播地 域广、接收者分布稀疏且相距较远的情况，使用组播方式就会引起比较大的网 络时延，其消耗的网络资源也要远大于单播发送反馈报文。 在基于接收者启动的可靠组播协议中，如果在组播树的共享分枝上发生了 数据丢失，所有接收者的n a c k 报文都将发送到服务器，这样就会导致服务器 处理器资源和网络资源的拥塞，即所谓的“n a c k 风暴”现象。如果用单播反 馈方式来发送n a c k ，就只有发送者能接收到n a c k ，而其它接收者就无法得 知是否还有别的接收者也对同一个序号的数据包发出了n a c k 反馈，即丢失了 相同序号的数据包，这种情况下，就无法压缩重复的n a c k ，会产生大量冗余 的n a c k 。如果采用组播反馈发送n a c k ，可以采用“s l o t t i n ga n dd a m p i n g ” 算法来对n a c k 反馈进行抑制。该算法包括两个步骤：第一步是s l o t t i n g ，即接 收者在检测到数据发生丢失或错误后，并不立即发送n a c k ，而是等待随机数 个时间片后才组播n a c k ，这样做既可以避免几个接收者同时发送n a c k ，更 是为下一步的n a c k 压缩提供条件；第二步是d a m p i n g ，当接收者还在等待发 送自己的n a c k 时，收到与自己准备发出的n a c k 相同的反馈后，就取消自己 的n a c k 的发送，从而达到反馈抑制的效果。理论上，“s l o t t i n ga n dd a m p i n g ” 算法可以使每个丢失的包在众多的接收者中只产生一个n a c k ，从而节省了网 络和服务器资源，但是对于数据丢失发生在单条链路上、组播成员分布稀疏且 彼此距离较远的情况，这种算法反而会造成整个网络资源的浪费，并且会带来 额外的传输时延。 ( 3 ) 数据恢复 在可靠组播协议中，对发生错误或丢失的数据有两种恢复方式【5 j ：一种方 式是直接重传丢失的原始数据，另一种方式则是重传校验码数据，它是对预先 设定的固定数目的数据包的奇偶校验信息。比较两种数据恢复方式，可以明显 看出，重传校验码可以减少网络资源和网络带宽，但由于利用校验码来恢复原 始数据需要经过计算才能得到，因此加重了服务器和客户端的计算负担，对c p u 资源也有了更高的要求。考虑到重传校验码数据的计算要求，通常在网络资源 较为充足时( 如在局域网中) 都采用重传原始数据的方式来恢复数据。在需要 重传的数据非常多时，使用源发送端进行数据重传，工作效率往往比较低。因 为组播成员可能比较多，组播树的层次也可能较多，这种情况下，大量的需要 发送的数据不仅会增重服务器和网络的负担，并且重传数据发生丢失的可能性 也会随着组规模的增大、组播树层次的增多而增加。因此我们可以考虑分布式 的网络，采用局部恢复策略。我们可以充分利用分布式的特点，将重传的任务 分摊到多个服务器上，每个服务器需要提供处理反馈和重传的功能，并且可以 根据本地网络的不同环境，灵活的采用不同的重传策略。在局部恢复策略中， 每个接收者不再“长途跋涉”向发送者发送反馈，而是就近发送给本地服务器， 通过本地服务器来完成差错报告和恢复。这种策略充分利用了分布式的优点， 提高了带宽的利用率，减小了传输时延，增强了系统的健壮性和灵活性，但同 时也带来了成本高，难于控制等缺点。数据恢复的另一个关键性问题是采用单 播还是组播方式进行重传。这往往由协议采用的反馈处理方式来决定，例如如 果进行了n a c k 抑制，即n a c k 反馈也是采用组播方式发送时，那么表面上看 起来的一个反馈报文，可能是由多个接收者的丢失反馈压缩而成的，重传就必 须采用组播方式，以保证发生数据丢失的接收者都能收到重传的数据包。而在 每个接收者都独立的向发送者发送丢失报告时，例如单播方式发送反馈时，发 送者就可以设定一个值，如果对某个数据包的丢失反馈数目超过了这个预定的 值就采用组播重传，否则就采用单播重传。 ( 4 ) 可靠性保证 由于不同的应用对数据传输可靠性有不同程度的要求，可靠组播协议提供 两种可靠保证：一种是完全可靠的保证，另一种对数据的可靠性的保证则是在 一定的时间限制范围内，对超出规定时间范围的数据就不提供可靠性传输。两 种可靠性保证的基本工作原理是一致，都是进行错误检测，反馈处理和错误恢 复，但后者提出了可靠性的时间限制这一条件，因此后者的数据有一定的生存 期，对于超出该生存期的数据，组播就不再处理反馈和恢复错误了。如果工作 在给定的时间范围内，两种组播的可靠性性能是一致的，但如果超出了规定的 时间范围，后者就不具备差错检测和恢复的能力了，因此超出了时间限制的数 据传输是没有可靠性保证的。 2 3 保证组播可靠性的方法 组播可靠性的研究主要包括状态控制模型、差错控制和恢复、拥塞控制和 速率调节算法这几个方面，其中差错控制和恢复、拥塞控制是保证组播可靠性 的核心问题。 2 3 1 差错控制和恢复 差错恢复机制大致可以分为3 类6 1 ：自动重传请求( a r q ) 、前向错误纠正 ( f e c ) 以及a r q 和f e c 的混合h e c 。基于a r q 的机制包括两个部分：差错 检测和差错恢复。差错检测的任务既可由发送者来负责也可由接收者负责。当 接收者检测到差错( 数据丢失或数据在传输过程中发生畸变) 时，必须向发送 者或其它的接收者发出未能正确接收的应答n a c k ( 具体由单播或组播n a c k 的方式来决定要不要发送给其他接收者) 。当发送者或分布式网络中的一些指定 接收者检测到差错( 超时或者收到差错反馈) 时，发送请求重传的数据。根据 反馈方式的不同，a r q 机制可分为基于n a c k 的方式和基于a c k 的方式，这 两种方式在单播环境中都是可行的 4 5 1 。但在组播环境中，基于a c k 的方式要 求发送者为每个接收者维护各自的状态信息，这给接收者带来了额外的开销， 当接收者众多时，这笔开销就会给发送者带来极大的负担，与基于n a c k 的方 式相比，可扩展性差，因而在可靠组播协议中较少使用该方法。前向错误纠正 f e c 方式不需要重传数据，取而代之的是在传输原始数据时就增加一些校验信 息( 通常是奇偶校验信息) ，当接收者发生数据丢失时，直接利用校验信息在本 地进行重组，恢复原始数据【46 1 。发送者在发送一组含有k 个数据分组的包之后 发送h 个奇偶校验分组，对于这k + h 个分组，接收者不必全部正确接收，只要 接收到其中任意k 个分组即可以重组原来的k 个数据分组，即对于丢失小于h 个分组的情况，f e c 有很好的容错性。f e c 通常和a r q 结合起来使用，以充 分发挥两种机制各自的优点，并且根据不同的应用需求，有两种不同的结合方 法。关于差错控制和恢复机制，本文将在第三章作详细的介绍。 2 3 2 拥塞控制 随着应用中节点数目的迅速增长、数据流量的不断增加，网络的拓扑结构 和负荷能力不断受到挑战。如果网络连接失效或者必须传输的数据包数目超过 了网络的负荷能力，就很可能使大量的数据包堆积或在一个甚至多个网络节点 上，致使网络产生拥塞( c o n g e s t i o n ) ，伴随网络拥塞而来的严重后果就是网络的 性能降低，严重的拥塞甚至会直接导致网络瘫痪。因此，拥塞控制是可靠组播 必须要解决的一个重要问题，组播拥塞控制机制【7 】是实现组播可靠性的重要前 提和保障。 可靠组播的拥塞控制机制主要包括以下四个部分：拥塞反馈报告、r t 时间 测量、数据丢失的检测和测量以及速率控制策略f 8 】。拥塞控制机制可以划分为 端到端的拥塞控制和基于路由器支持的拥塞控制，在前者中，网络拥塞状况信 息通常是由组播接收者来报告给发送者的，而不是发送者自主从网络中获取。 接收者和发送者进行报文交换，进而接收者计算出r t 时间并估测出数据包的丢 失情况，反馈这些信息给发送者，然后提交给速率控制模块，由此可见，发送 者的速率控制策略和接收者的反馈协同合作来完成拥塞控制【9 1 。 ( 1 ) 组播拥塞控制机制设计中的关键问题 公平性：组播应用的增加和组播协议的应用都带来了非t c p 通信量的增 加，其在总通信量中的比例也随之不断增加，由于大部分的组播协议中的拥塞 控制机制与t c p 并不兼容，因此它们与t c p 数据流的竞争也是不公平的，这 种不公平的竞争带来的后果就是t c p 通信受到限制、网络拥塞难以控制甚至崩 溃刚。因此，为