（通信与信息系统专业论文）可扩展的可靠组播传输协议设计.pdf

摘要 捅要 组播传输的可靠性问题一直是当前组播研究中的一个热点和难点，由于不同的 组播应用对数据传输的要求存在着很大的差异，所以没有一种可靠组播协议能适 用于所有的情况。论文提出的可扩展的可靠组播传输协议是针对共享白板业务的 特点，在讨论了它的需求的基础上进行设计并且实现的。 考虑到白板业务的具体应用特点，在比较各种现有的可靠组播传输方案后，最 终选定了基于接收端、序号间隔的序列号模式与时间间隔的计时器模式来检测数 据包的丢失，用基于接收端、组播n a c k 反馈信息的方式来恢复丢包数据。仅基 于以上选定的可靠传输方案还无法完全保证数据的可靠传输，因此论文还设计了 一种控制信息一会话报文一来保障发送端发送的最后一个数据包准确无误到达接 收端。随后本论文又详细阐述了协议设计原理、设计流程、报文格式等内容，对 选定的方案进行了详细的论证。在论文的结尾还对协议的实现原理以及部分实现 细节做了阐述，完善了协议设计。 关键词：共享白板i p 组播可靠传输 a b s t r a c t a b s t r a c t r e l i a b l em u l t i c a s ti sah o t s p o ta n dn o d u st ot h em u l t i c a s tr e s e a r c hp r e s e n t a st h e r ei s m u c hm o r ed i f f e r e n c ei nd e m a n do fd a t at r a n s p o r tb yd i f i e r e n tm u l t i c a s ta p p l i c a t i o n ，n o n eo f m u l t i c a s tp r o t o c o lc o u l df i ta l lt h ec o n d i t i o n t h es c a l a b l er e l i a b l em u l t i c a s tp r o t o c o l s u g g e s t e di n t h i sp a p e ri sd e s i g n e da n dr e a l i z e d w h i c hi sb a s e do nt h ec h a r a c t e r i s t i ca n d n e e d so ft h ew h i t eb o a r d t h i n k i n ga b o u tt h es p e c i a lc h a r a c t e r i s t i co fw h i t eb o a r d ，w ec h o o s ed e t e c t i n go fd r o p p a c k e tw h i c hi sb a s e do nr e c e i v e r - b a s e d t h ei n t e r v a lo fs e r i a ln u m b e r , a n dt h ei n t e r v a lo f t i m e rm o d e ，a n dr e c o v e r yo ft h ed r o pp a c k e tw h i c hi sb a s e do nr e c e i v e r - b a s e d ，m u l t i c a s t n a c km o d ea f t e rw ec o m p a r em o s to ft h em e c h a n i s mp r e s e n t s i n c et h em e c h a n i s m sw e c h o s e nb e f o r ec o u l dn o ts u r er e l i a b i l i t yi nc o m m u n i c a t i o nc o m p l e t e l y , w ca l s od e s i g na c o n t r o l l e dp a c k e t s e s s i o nm e s s a g e t og u a r a n t e et h el a s tp a c k e tt h es o u r c es e n tr e c e i v e db y r e c e i v e r s a f t e rt h a tw ee x p a t i a t eo nt h ep r i n c i p l ea n df l o wo ft h ep r o t o c 0 1 a n da l lt h ef o r m a t o fp a c k e t s a tt h ee n do ft h i sp a p e r , w ea l s oe x p a t i a t eo nt h er e l i a b i l i t yo ft h ew h o l ep r o t o c o l a n ds o m ed e t a i l s k e y w o r d s ：w h i t e b o a r di pm u l t i c a s tr e l i a b i l i t y 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已 经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做 了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：重盟日期型! ! ：童笸 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校 攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发 表论文或使用论文( 与学位论文相关) 工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部 分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵 守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：氖l 星良 本人签名：型i 墨丛 导师签名： 粤止 同期堡2 ：! ! p 日期竺，2 。 第一章绪论 第一章绪论 1 1 组播技术的发展背景 计算机技术的飞速发展把人类社会带入了信息化的时代。随着信息化进程的 不断深入，通信技术与计算机应用及网络技术相互融合，为人类的科学技术研究 和应用提供了更加有力的支持。计算机通信说到底就是将信息从网络的一端传输 至网络的另一端，在传统的计算机网络中单播和广播通信是两种最主要的通信方 式。 单播通信允许单个网络主机向网络上另一个主机发送报文，在发送者和每一 个接收者之间需要建立单独的数据信道，当有大量主机希望获得同一数据信息时 就会导致发送者负担重、数据信息迟延长，出现网络拥塞等问题；而广播通信则 允许某个网络主机将一个数据报文一次发送给子网内所有主机，无论这些主机是 否愿意接收这个报文。这样就会增加非接收者的开销。 那么有目的性发送数据报文的组播技术就应运而生。组播通信是指把同一数 据块( 报文、分组或是文件等) 从一个网络主机同时传送到一个由若干个主机组 成的集合的过程。在这个传送过程中，发送主机只需一次发送，就可以实现从一 个发送方到n 个接收方的数据传送过程。图1 1 表示了组播数据包的发送、转发 和接收的原理。图中三个节点a ，c 和d 构成一个集合，另一个节点s 向这个集合 中的三个节点进行组播传输，而主机b 并不是这个组内的成员，所以主机b 无法 收到主机s 发送的数据包。可以看出，源节点s 发出的数据包到路由器r 2 才进行 一次复制，然后到了路由器r 6 再复制一次。也就是说，组播的数据包仅在传送路 径必须分禽时才将数据包复制后继续转发。若不是组播，则在一开始，源节点s 就要发送三个数据包，数据包中的目的地址也是这三个主机的i p 地址，分别发送 给节点主机a ，c 和d 。因此，采用组播协议可以明显的减轻网络中各种资源的消 耗。 2 可扩展的可靠组播传输协议设计 主彤l d 图1 1 组播数据包的发送、转发和接收 组播是一种介于单播和广播通信之问的数据传输方式。组播允许一个主机将 一个报文发送至网络中的某个确定主机子集，这个子集称为组播组( m u l t i c a s t g r o u p ) 。组播的基本思想是，源主机只发送一份数据报文，这份数据报文中的目的 地址为组播组地址：组播组中的所有接收者都可接收到同样的数据拷贝，并且只 有组播组内的主机( 目标主机) 可以接收该数据，网络中其它主机不能够接收到。组 播组用d 类i p 地址( 2 2 4 0 0 0 2 3 9 2 5 5 2 5 5 2 5 5 ) 来标识。所以，组播也通常被称 为i p 组播。i p 组播的主要优点有： ( 1 ) 高效的多目标传送。当一个发送者有目的性的向多目标传送相同信息时， 组播通信相对单播而言，网络上传输的数据量减少，也不像广播通信那样，必须 给每个目标主机都传送数据，这样就节省了带宽资源。 ( 2 ) 传输目标不确定，参与通信的主机数量对传输过程透明。目标由一个组地 址来标识，而不是一系列具体i p 地址，发送者使用这个组地址可以向不确定的一 群接收者传输数据，接收者可以随时参加和退出组。 ( 3 ) 对等通信，即没有客户和服务器之分，参与通信的主机可以使用同一通信 程序。 基于以上这些优点，i p 组播在一些高带宽应用领域中起着不可忽视的作用， 如l p t v 、视频会议、数据和资料分发、网络音频应用、网络视频应用、多媒体远 程教育等宽带应用。也正是由于巨大的市场和发展潜力，组播从1 9 8 8 年提出到 现在经历的十几年的发展，许多国际组织和厂商一直对组播的技术研究和业务开 展做着大量的工作。随着互联网建设的迅猛发展和新业务的不断推出，组播也逐 步走向成熟。尽管目前端到端的全球组播业务还未大规模开展起来，但是具备组 播能力的网络数目在增加。 第一章绪论 1 2 可靠组播的产生及研究现状 3 t c p i p 协议中的数据传输有两种方式：利用数据流方式的t c p 协议或是利用 用户数据报方式的u d p 协议。其中t c p 协议是面向连接的，在这种方式下，两个 进行通信的应用程序之间首先建立一种虚拟的连接关系。本质上，连接是一个管 道，收发的数据不但顺序一致，而且内容相同。t c p 协议还通过差错检测、差错 恢复和流量控制等一系列手段保证数据的可靠传输；而u d p 协议则是无连接的， 在这种方式下，每个数据分组都携带完整的目的地址，各分组在网络中独立传输， 每个分组都有可能丢失，也有可能后发的分组会先到达目的地。u d p 协议提供的 数据传输只是“尽力传送 ，不能保证数据的可靠传输。 传输层协议t c p 和u d p 中，只有u d p 协议可以支持组播通信。组播使用的 是u d p 协议，因此组播通信也不保证数据的可靠传输。对于一些可靠性要求较高 的组播应用就必须在传输层之上增加控制机制来实现i p 组播的可靠传输机制。除 此之外，i p 组播是点对多点或多点对多点的通信，无法对网络的拥塞进行控制， 而且在传送过程中容易出现乱序的问题。鉴于以上这些问题就产生了对可靠组播 的需求。 1 9 9 9 年i e t f ( i n t e m e te n g i n e e r i n gt a s kf o r c e ) 成立了可靠组播传输工作组，进行 可靠组播传输标准的开发和制定。该工作组研究提出的可靠性组播技术有三种：1 1 1 ( 1 ) 环状组播( r i n g b a s e d ) ：仿造令牌环网的设计方案，利用令牌来保证成功发 送。特点是可靠性高，效率高。缺点是管理起来比较困难，不支持接收方数量较 大的情况。只适合2 0 0 个节点以下的网络发送。 ( 2 ) 云状组播( c l o u d b a s e d ) ：在发送方发送信息时，加上顺序号码，接收方负 责核对是否收到所有的分组，如果发现丢包，向发送方发送没有收到的信号，发 送方重新发送丢失的数据包。这肿方式可以支持更多的节点，而且容易操作。 ( 3 ) 树状组播( t r e e b a s e d ) ：将所有的接收方组成层式的树状结构，由树状顶层 向下一层发送，依此类推，并负责确认下一层是否收到，这样就可以支持有大量 的组播成员，但在管理接收方回送确认信息时，会造成额外的管理开销和麻烦。 这种方式适用于卫星通信和w a n 。 关于可靠组播的问题，目前有很多人正在从事该方面的研究并获得了一些成 果。他们当中比较有代表性的有可靠组播协议r m p ( r e l i a b l em u l t i c a s tp r o t o c 0 1 ) 弘j 、 可扩展可靠组播协议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 ) i3 1 、基于同志的可靠组播 l b r m ( l o g b a s e dr e l i a b l em u l t i c a s t ) 4 j 和可靠组播传输协议r m t p ( r e l i a b l e m u l t i c a s tt r a n s p o r tp r o t o c 0 1 ) 1 5 1 。群件通信系统，如t o t e m 6 1 和t r a n s i s 7 1 ，同样使用 可靠组播在组内共享信息。 r m p 使用坏状组播技术，t o t e m 和t r a n s i s 允许多个发送者将信息发送到接收 4 可扩展的可靠组播传输协议设计 者，与t o t e m 和t r a n s i s 强行指定发送者发送报文顺序所不同的是，r m p 允许用户 按数据组播的需要指定发送的顺序。但是以上这几个协议都依赖于一个单独的协 议协调器来对发往同一组播组的信息进行排序，用户端响应的时间较长，协调器 会成为性能的瓶颈，并且如果协调器出现故障，则整个组播传输就会中断，因此 这些协议的扩展性和可靠性较差。 九十年代初，c l a r k 和t e n n e n h o u s e 提出的a l f 8 ( a p p l i c a t i o nl e v e lf r a m i n g ) 协议是依靠t c p 单播来保证组播的可靠传输，虽然可靠性得以实现，但对网络造 成了严重的负荷。1 9 9 6 年，由s a l l yf l o y d 等人针对共享白板( s h a r e dw h i t e b o a r d ) 应用提出的s r m 协议一允许多个发送者同时将信息组播传输并且不对数据到达接 收者的顺序进行强行的规定，相对于舢l f 很好的解决了网络负担重的问题，所以 s r m 是当前分布式白板应用中最广为人知的可靠组播协议。但是，s r m 也有不足 之处：对丢失数据的重传要求总是导致将数据重传给所有的接收者。这种方式浪 费了宝贵的网络带宽并使所有接收者进行不必要的重传数据处理。当仅有较少接 收者要求重传数据时，单播( u n i c a s t ) 重传比s r m 的组播重传机制更高效地利用网 络带宽。另外，如果数据丢失只发生在网络的一个局部，s r m 将数据重传到所有 接收者就显得没有必要。 l b r m 和r m t p 引入了层次概念并使用网络中特定的部件来为发送者承担重 传数据的任务，因此，这两种协议的扩展性能都很好。对于一个拥有大量接收者 的网络，l b r m 依靠的是随机挑选出来的一部分接收者返回的肯定方式的确认信 息，而与需要重传信息的接收者的数目无关。对这些接收者的挑选如果不适当， 就相当于对使用组播重传或单播重传的选择不适当，而肯定方式的确认将影响扩 展性。 r m t p 提供了流量控制机制来调节发送者的传输速率以便处理用户计算机失 效或网络拥塞的情况，这种功能在l b r m 中没有提供。另外，r m t p 是一种能够 满足我们需要的扩展性和在异构环境下运行要求的可靠组播协议。但是，由于 r m t p 协议一开始是为可靠地组播文件而设计的，因此需要加以扩展才能可靠地 组播连续数据流。 除了可靠性，可扩展性对组播协议的性能也有很大的影响，这罩所说的可扩 展是指组播成员数目的可扩展性。本文针对共享白板业务而提出的组播协议采用 的可靠传输方案，理论上具有良好的可扩展性，比如采用基于时间间隔的定时器 模式，理想情况下网络中针对同一个丢失数据包的请求包、修复包只有一个，这 样就能够容纳比较多的组播成员。 第一章绪论 1 3 本文的主要工作 5 与传统点到点的可靠数据传输协议不同的是，“o n es i z ef i t s 舢l ”的定律并不 适用于可靠组播传输，不同的组播应用对数据传输的要求存在着很大的差异，没 有一种可靠组播协议能适用于所有的情况，比如说音频视频等媒体信息的组播更 注意实时性，对可靠性要求较低；白板等会议工具对延时比较敏感，并且要求有 一定的可靠性作为保证；而数据传输应用只关心数据的完整性。这就造成了底层 的可靠机制有很大差别：在数据传输应用中，丢失的数据包可以在一轮传输后进 行重传；在会议工具中，丢失的数据包必须尽可能快地恢复；而在音频视频等媒 体信息的组播中不能应用重传来恢复丢失的数据包。因此可靠组播的研究必须针 对某种具体的应用进行。 本论文针对白板( w h i t eb o a r d ) 应用进行了分析，试图找出一种适合于白板类业 务的可靠组播传输方法，最终以s r m 协议为基础进行研究并设计并设计了一套新 的可扩展可靠组播协议。本文首先介绍了可靠组播产生的背景，着重分析了根据 不同应用的可靠组播的不同侧重点；其次，分析电子白板的需求，提出一套针对 白板业务的可靠组播传输方案；在此基础上提出协议的整体设计方案，并对各个 部分的功能作了详细的定义和说明；然后以软件实现的角度分析了协议实现的要 求和部分细节，最终总结了全文工作以及进一步的研究方向。各章节内容安排如 下： 第二章可扩展可靠组播协议设计方案 本章首先根据现有的可靠组播通信协议及相关文献，对各种保证组播传输可靠 性的方法和机制做了详细的分析和研究，并最终确定了本论文在针对白板业务设 计协议时所选取的解决方案。 第三章协议原理设计详述 本章首先对整个协议的工作过程作了简要的介绍，其次主要论述了协议整体的 流程设计，最后对实现过程中一些技术难点进行讨论。比如白板应用要求在一定 可靠性保证的基础上尽量减小时延，那么如何在最短时延内保证组播数据的可靠 传输，定时器要如何设置；要实现组播传输的可靠性，各种类型的数据包的首部 要如何设计等等问题。 第四章协议算法实现方案 根据前两章的理论分析和研究，本章主要论述了如何用代码实现协议系统。按 照设计要求，给出设计的协议系统类层次图以及部分重要程序实现细节。 第二章可扩展町靠组播协议设计方案 第二章可扩展可靠组播协议设计方案 7 本文所论述的可扩展可靠组播协议主要是针对共享白板这一业务来设计完成的。共 享白板实际上就是绘图程序与计算机通信程序有机结合在一起的产物，它比起文件分发 应用来说，对于组播的可靠性要求并不那么高。共享白板是一种实时更新的业务，这就 意味着只要在一个规定的时延内将数据信息传送至接收者，或者在这个时问段内允许一 定概率的丢包，那么白板还是能够有效的工作。针对这样的特点，本章就如何在保证可 靠性的前提下，尽力降低组播迟延来设计整个协议。由于共享白板应用的参与用户数可 能较多，各用户在地理上可能距离较远，因此在设计可靠组播协议时需要考虑可扩展性， 以保证在共享白板组播组规模较大时可靠组播协议的性能不会有明显下降。 2 1 共享白板应用的需求分析 可靠组播的通信模型主要可由两种方式来实现，一种是应用层的组播：每个站点与 其他所有参与站点建立单播连接，其本质是通过多个单播实现“组播”的效果，微软的 n e t m e e t i n g 就是应用层组播的应用之一；另外一种方式是可靠的i p 组播：通过组播地 址，发送者将i p 数据包传送到一组接收者，其可靠性通过可靠组播协议来保证。图2 1 示出了两种类型通信模型。 接收者 发 发 ( a ) 应用层组播 接收者 图2 1 可靠组播通信模型 应用层组播的基本思想是保持互联网原有的简单、单播的转发模型，由主机实现组 8 町扩腱的可靠组播传输协议 搜计 播的转发功能。其优势在于：对于不同的应用层组播的不同算法，只需改变端系统即可， 便于实现和推广，同时也便于针对特定应用进行优化。但其缺点也是显而易见的：一般 比i p 组播使用更多的网络资源；端系统可能不稳定，导致组播的可靠性受到影响；增 加了端系统的开销，可能导致延迟、转发速率等性能下降。应用层组播研究主要集中于 视频会议、媒体流的分发系统( 如视频广播) 和订阅分发系统( p u b l i s hs u b s c r i b es y s t e m ) 等，主要用于实时的多媒体传输。 共享白板是以i p 组播传输为基础。其目标之一是提高成员间的协调配合和协同工 作水平，而它所要达到的一个主要目标就是“你见即我见 ，也就是说在共享白板的会 议模式中，任何一个成员在白板中添加文本、图像或对其修改都会实时的传送到其它成 员那里去，以使其想法、意图被别人所了解。这样，仅仅用i p 组播这种不可靠传输的 方式显然会使某些信息无法传送至其他成员。所以，要在白板的组播传送中加入可靠传 输机制以使得白板系统的功能更加完善。 虽然在共享白板的通信过程中要求有可靠性的保证，但是毕竟不像文件传输一样要 求完全可靠，即百分之百的零丢包率。它具有实时性，只要在一定丢包率的条件下尽量 保证迟延小就可以使得白板进行组播通信。根据这样的需求就设计出如下的可靠性实现 方案。 2 2 1 组播可靠性概述 2 2 协议可靠性的实现方案 对于单个接收者，使用t c p 就可以较好的实现可靠传输。但对于多个接收者的组播 而言，t c p 就不可能较好的实现可靠传输。组播的可靠性传输可分为部分可靠性、有时 间限制的可靠性和完全可靠性等几种类型。部分可靠性传输，顾名思义它只尽力提供可 靠的数据传输，不能保证数据百分之百被所有接收者接收到；有时间限制的可靠性适用 于对实时性要求很高的组播应用，如果数据在规定时间内没有收到，那么就认为其数据 包丢失且不再重复传送；完全可靠性，这类可靠性传输要求所有组播数据全部正确传输 到接收者，即数据的传输丢失率为零，通常适用于对正确性要求很高但对实时性要求不 高的情况，比如文件分发应用。从广义上讲，可靠性还包括旧1 ： ( 1 ) 接收者数目，即保证组播组中的每个成员都能接收到发往该组的组播数据或非 该组成员都接收不到该组的数据。 ( 2 ) 有序，即要求接收者接收到的组播分组是按一定顺序排列的。除了按发送时间 顺序外，还可能有几种不同的排序定义，如单个源排序、多个源排序、多个组排序等等。 第二章可扩展可靠纽播协议设计方案 9 ( 3 ) 拥塞控制，拥塞控制对于可靠组播传输来说是非常困难的。组播拥塞控制通常表 现为两种形式：首先是需求维护所有接收者保持相同的速度：其次是允许接收者低于它 的接收速度接收。 为满足可靠性要求，必须要有快速高效的丢包检测和重传机制，且其处理方式应满 足高效性、可扩展性的要求。 2 2 2 数据包丢失的检测方法 数据包丢失的检测就是要知道在数据传输过程中某个数据包是否正确地到达目的 主机，这就要从两方面来讨论：如何来检测数据包是否丢失以及由谁来负责这个检测。 如何检测丢包 一般丢包检测的实现模式有两种n 0 1 ： ( 1 ) 基于序号间隔的序列号模式：指当接收者发现连续接收到的数据包的序列号不 连续时，就认为发生了数据包的丢失，认为缺少的序列号所代表的数据包没有正确到 达接收方主机。这种模式在一般情况下检测到数据包丢失的时间相对比较短，但是如 果发生了连续的或是爆炸性的数据包丢失现象，等待下一个数据包到达的时问将很难 预测，而只有在接收到不连续数据包的序列号时，才能断定数据包出现丢失情况，所 以基于序号间隔的序列号模式遇到连续的或爆炸性数据包丢失的情况时，将无法及时 检测到数据包的丢失。 ( 2 ) 基于时间间隔的计时器模式：接收主机未能在指定时间间隔t 内收到预期的数 据包或是控制信息，就认为发生了数据包的丢失。如果某个数据包没有丢失，只不过 因为网络阻塞经过了较大的时延( 大于t 值) 才到达接收主机，此时接收主机仍认为 此数据包丢失，启动丢包修复机制，从而使得网络阻塞更加严重。因此t 值的设置应 充分考虑网络拥塞可能导致的数据延时。本论文通过每一个成员多播发送会话报文 ( s m ) 这一控制信息来实时计算主机之间的链路时延来避免由于数据包时延而导致“丢 包”，下面的章节会详细论述。因此基于时间间隔的计时器模式可能造成比较大的通讯 延时。 谁来负责检测丢包 根据由谁负责检测丢包可以把可靠组播丢包检测方法分为两类：基于发送者的丢包 检测方法和基于接收者的丢包检测方法3 。 ( 1 ) 基于发送者的丢包检测方法由发送者负责组播数据的可靠传输，发送者判断在 数据传输过程中是否出现了丢包，如果出现了丢包就要负责重传丢失的数据包。在丢包 1 0 可扩展的町靠组播传输协议设计 检测的具体实现上，只能使用基于时间间隔的计时器模式进行差错检测。在这种方法里， 发送者要求每个接收者对自己所收到的每个数据包都要回送一个肯定确认( a c k ) 信息。 当发送者的计时器超时，发送者检查收到的a c k 信息来判断在数据信息在传输过程中 是否发生了差错。基于发送者检测的算法比较简单，但是等待接收者回送的a c k 信息 增加了数据传输中的延迟，并随着一个组播组里的接收者数量的增加，发送者不得不处 理越来越多的来自接收者的a c k 信息。由于丢包的检测和重传都由发送者负责，而且 对每一个发送者都有一个或多个接收者，这样在接收者数目很大时，不仅会使发送者的 负担过重不堪忍受，而且使网络拥塞严重，也就很不利于可扩展可靠组播协议的应用。 这就是在组播传输中由于进行可靠性控制而产生的“反馈爆炸 问题。 ( 2 ) 基于接收者的丢包检测方法由接收者负责组播数据的可靠传输，每一个接收者 负责自己的数据丢失检测和发送重传请求。在丢包检测的具体实现上，可以使用上述两 种丢包检测模式。当计时器超时或是接收到的数据包序列号不连续的时候，接收者确信 发生了数据传输错误，这时就向数据发送者或者有能力响应的组播成员发送否定确认信 息( n a c k ) ，请求数据发送者或是其它组播成员重新传输指定的数据包，以此来进行丢 包恢复。因为在绝大多数的情况下，数据传输发生错误的概率都要远远小于数据j 下确到 达接收者的概率，所以在基于接收者的丢包检测中，由接收者向发送者发送的否定确认 信息n a c k 的数量都要远远小于在基于发送者的差错检测中由接收者发送的确认信息 a c k 的数量，因此基于接收者的丢包检测可以减少“反馈爆炸 问题的发生。并且基 于接收者的丢包检测模式大部分处理任务在接收端完成，只有在需要重发数据时，接收 端才向发送端发送否定确认信息，也就使得协议具有了良好的可扩展性。总之，在最大 的数据传输吞吐量上，基于接收者的丢包检测方法比基于发送者的丢包检测方法的性能 都要好。 已有的结论也表明“2 l ：基于接收者的组播丢包检测方法优于基于发送者的丢包检测 方法，并且在越大的网络区问里面，基于接收者的组播丢包检测方法所获得的性能益处 就越大。 2 2 3 数据传输中的丢包恢复 以上讨论的丢包检测就是如何判断数据包在传输过程发生了丢包，发现了丢包以后 就要考虑如何恢复这些丢包。进行丢包恢复的基本原则就是进行重传，把发生了数据传 输错误的数据包进行重传，就可以纠正这些差错。这也要从两个方面来讨论：如何来恢 复丢失的数据包以及由谁来负责这个恢复。 如何恢复丢包 第二章町扩展可靠组播协议设计方案 出现丢包的数据恢复的基本原则是重传这些数据包，重传的方式有单播重传和组播 重传两种。单播重传方式是指数据发送者对发出重传请求的接收者单播发出丢失数据的 修复包：组播重传方式是指数据发送者对所有的组播组成员或是部分组播组成员( 组播 域) 发出正确的数据包。 组播重传方式的传送代价一般比较大，因为重传的数据包已经被大多数的接收者正 确接收了，没有收到这些数据包的只是少数的接收者。但在网络出现故障时，就会发生 大规模的数据包丢失的情况，在这种情况下，组播重传方式要比单播重传方式的恢复效 率高。有些可靠组播协议允许采用单播重传和组播重传两种方式进行丢包恢复，根据丢 包发生的规模( 数据包传输出错的百分比) 来具体选择；另一种折中的选择是采取在一 定范围内进行组播重传的方法。 谁负责数据包重传 在可靠组播数据传输中，负责完成数据包重传任务的可能有发送者、某个已经正确 接收到数据包的接收者或是一个特定的代表。由发送者负责进行的数据包重传称为集中 式恢复，其它的情况称为分布式恢复，分布式恢复又可进一步分为本地式恢复和全局式 恢复。 集中式恢复由发送者负责完成数据包的重传，当发送者收到接收者返回的请求重传 信息时，采用单播重传或是组播重传方式向没有正确接收到数据包的接收者进行数据重 传；分布式恢复一般用在采用树状组播技术的组播传输中，其中本地式恢复是指，如果 某一个子树中有一个节点a 没有正确接收到某个数据包，它发送的n a c k 信息只在同一 个子树中传播，由同一子树中已经正确接收到的数据包的某个节点负责把已经正确接收 的数据向a 进行重传的方式，本地式恢复只在发生了数据包丢失的本地组内部进行重传； 如果由整个组播分组中任何一个已经正确接收到数据包的组播成员负责进行的重传方 式就是全局式恢复。 集中式恢复的算法比较简单，但是发送者的负担比较重，不能适应大规模的应用； 分布式恢复的效率要比集中式恢复的效率高，但是在具体实现上要比集中式恢复复杂的 多。 2 2 4 丢包检测方法的选择 根据上面对可靠组播差错控制方法的分析和研究，在本协议的设计中采用基于接收 者的计时器策略和序列号策略相结合的方法来负责数据包丢失的检测。理由如下： 丢包检测根据负责者的不同有基于发送者的方法和基于接收者的方法，基于发送者 的方法由于需要大量的a c k 消息来保证实施，当组播成员数目过大时，可能导致发送者 的负担过重，网络带宽急剧消耗，容易引起“反馈爆炸 的问题；而基于接收者的方法 1 2 可扩展的可靠组播传输协议设计 由每个接收者负责自己所接收数据的丢包检测，分担了发送者的负担，可以减小“反馈 爆炸”问题发生的可能性。并且，现有的结论也已经证明，基于接收者的方法性能要优 于基于发送者的方法。所以，本方案选用基于接收者的可靠组播差错检测方法。 实现差错检测的方法由计时器策略和序列号策略两种，计时器策略是指当在一个制 定的时间内，始终没有收到预期的数据包或是控制信息，就认为发生了数据包的丢失， 这种方法需要多个会话报文中的时间戳来确信检测到的丢包现象不是数据丢失，因此导 致了很大的通讯延迟。序列号策略是指根据收到的数据包编号是否连续来确定是否发生 了数据包丢失，当遇到连续的或爆炸性数据包丢失情况时，将难以预测何时能够检测到 数据包的丢失。 计时器策略与序列号策略各有不足之处，本论文使用计时器策略与序列号策略相结 合的方法来进行差错检测，可以综合两者的长处。具体方法如下：接收者收到一个数据 包以后，根据数据包的编号来检测是否是期望的数据包，如果不是就设置一个计时器， 在计时器超时时发送n a c k ，再设置另一个计时器来等待接收要求的数据包。如果计时 器超时仍然没有收到期望的数据包，那么就再次发送n a c k ，如果发送n a c k 的次数超过 了预定值，则数据恢复失败。 使用这样的丢包检测和丢包重传机制，使得组播成员之间能够相互探测到对方的状 态，从而抑制网络中多个相同的控制信息传输，节约了网络资源，非常有益于协议的可 扩展性的提高。 2 2 5 丢包恢复方法的选择 单播重传方式可以很好的保证一点对一点的通信传输的可靠性，然而如果在组播通 信中也用这种单播方式，即每个没有正确收到数据包的接收者都要发送n a c k 到发送 者去要求重传，这样如果发生大规模的丢包情况，就会严重地增加发送者的负担，也会 使网络造成拥塞。出于这样的考虑，本论文将采用组播重传方式来保证组播通信中的可 靠性传输。而本文是针对白板业务的组播传输进行分析与研究的，由于白板业务的数据 量不大，就只需要用本地恢复的机制来保证差错恢复就可以了。 2 2 6 最后一个数据包判断丢失和可靠重传问题 因为n a c k 算法( 即以上论述的差错检测和恢复的算法) 是通过后一个接收到的 数据包编号来判断前面的数据包是否有丢失。可是当发送者发送了最后一个数据包，而 接收者又恰好没有收到此数据包，由于没有后续数据包作为判别丢包的依据，故接收者 无法判断发端最后一个数据包是否丢失。 这个问题可以通过设计定时组播控制信息的方法来解决。即规定组播的每个成员定 时组播一个会话报文，这个报文要包括自己当前所发送数据包的最大序列号。这样，接 第二章可扩展町靠组播协议设计方案 收者就可以根据收到的这个报文中序号来判断自己是否丢了最后一个数据包。 2 2 7 假丢包问题 1 3 随着计算机网络的快速发展，网络承受的压力越来越大，时常会出现网络拥塞的情 况。那么在这样的情况下由某一个主机先发送的数据包就有可能会比后发送的数据包晚 到达接收者，并且如果应用层的业务要求保障可靠性，那么应用层会认为发生了丢包， 就会启动丢包修复机制。但这只是由于网络迟延，这个数据包晚到达了接收者，接收者 发送了n a c k 反馈信息，就白白浪费了网络带宽，加重了网络负担，这也就是所谓的 “假丢包 问题。 要解决这样的问题，本论文采取了如下的方案。在组播通信过程中，当某一主机检 测到了数据包序列号的缺失时，接收主机并不急于立即启动丢包修复机制，而是通过数 据包序列号的缺失第二次检测到丢包时才启动丢包修复机制对第一次检测到的丢包进 行修复。这样可以允许由于网络拥塞而使得某一个数据包在网络中有一定的迟延。但是 又会产生这样的问题：当某个主机发送完了最后一个数据包，而接收者只对两次检测到 丢包中的第一次完成了修复，由于发送主机没有数据包发送，也就没有可能再次检测到 丢包，那么第二次检测到的丢包就无法实施恢复。本论文中采取在2 2 6 节中讨论的会 话报文来解决这个问题。某个发送主机发送了最后个数据包，而当接收者收到发送主 机发送的会话报文时，发现会话报文中的“最大序列号字段中的值比本主机接收到的 最大序列号值大，就立即启动丢包修复机制，将所有缺失序号的数据包都进行恢复，从 而保证组播通信的可靠性。 第三章协议原理设计 第三章协议原理设计 1 5 根据第二章对协议实现机制的讨论，本章将对协议原理做一个详尽而完整的研究和 设计，以软件实现的角度来描述协议实现的流程和状态转移，设计报文的格式及定时器 的设置。 3 1 协议中术语的定义 ( 1 ) 请求包r q d ( r e q u e s td a t a ) ：当主机发现丢包时，为了请求其它主机对本主机进行 丢包修复而发送的否定确认信息n a c k 。 ( 2 ) 修复包r p d ( r e p a i rd a t a ) ：响应其他主机的重传请求而发送的丢包的副本。 ( 3 ) 会话报文s m ( s e s s i o nm e s s a g e ) ：在组播组内每个成员定时组播的用来表明自己状 念的信息报文。 ( 4 ) 数据包o d ( o r i g i n a ld a t a ) ：由应用层交付下来或者要交付给应用层的数据信息。 ( 5 ) 请求随机定时器r a n d o m r q t ( r a n d o mr e q u e s tt i m e r ) ：为避免多个主机因同时发送 r q d 而引起的“反馈爆炸 ，在发送请求包前设置的一个随机时长定时器。 ( 6 ) 修复随机定时器r a n d o m r r t ( r a n d o mr e p a i rt i m e r ) ：与r a n d o m r q t 类似，为避免 多个主机因同时发送r p d 而引起数据包“爆炸”在发送修复包前设置的一个随机时 长定时器。 ( 7 ) 修复定时器r t ( r e p a i rt i m e r ) ：发送请求包后设置的随机时间等待接收修复包，若 超时则要重发请求包要求修复。 ( 8 ) 状态周期定时器s c t ( s t a t ec y c l et i m e r ) ：用于定时组播本主机状态信息而设置的定 时长定时器。 其中( 1 ) 、( 2 ) 、( 3 ) 被定义为控制信息，( 4 ) 被定义为数据信息，定时器( 6 ) 、( 7 ) 的时长 是由报告报文中的时间戳来确定的。 3 2 协议工作原理 若主机a ，b ，c 和d 都在同一个组播组内，当主机a 的应用层向下层交付数据时， 通过逐层打包，主机a 将数据包组播到整个组播组，如图3 1a 所示。此时，由于网络 或是主机自身原因，主机c 和主机d 没有能够正确接收到主机a 中的某一包数据， 1 6 可扩展的叮靠组播传输协议设计 主 主 主机d 图a 主机d 图c 主 生 主机d 图b 主# t d 图d 第二三章协议原理设计 主 主 主机d 1 7 图e图f 图3 1 协议工作原理详解 如图3 1b 所示。此时，主机c 、d 根据序列号的差错检测策略检测到了丢包，准备各 自发送请求包r q d ，再根据定时器模式来恢复丢包，假设主机d 的请求随机定时器 r a n d o m r q t 首先超时，发送出请求包，如图3 1c 所示。当主机c 收到主机d 发出的 请求包，检查到与本机即将发送的请求包相同，则抑制本机请求包的发送，设置修复定 时器r t 准备接收此丢包的修复包。与此同时，主机a 、b 均收到主机d 发出的请求包， 设置自己的修复随机定时器r a n d o m r r t 准备应答，假设主机b 的链路距离( 即传播时 延) 比主机a 到主机d 近，主机b 的修复随机定时器首先超时，发送出本机对丢包的 修复包r p d ，如图3 1d 所示。当此修复包到达主机a 时，主机a 检查到此修复包与本 机即将发送的修复包相同，则抑制本机修复包的发送，取消本机的修复随机定时器。同 时，此修复包被丢包主机c 、d 收到，完成丢包主机的修复工作，确保了组播传输的可 靠性。但如果由于链路问题，如图3 1e 所示，主机c 未能收到主机b 发送的修复包， 那么主机c 的修复定时器就会超时，并将再次发送请求包，表明本机未能得到丢包的应 答。那么就再次重复图c 所示的过程，请求修复。当然在此过程中，无法判断某主机发 送的最后一个数据包是否被每个成员正确接收，那么每个主机成员就要按照状态周期定 时器s c t 所设置的时长，定期的组播出自己的会话报文s m ，如图3 1f 所示。报文罩 面含有源主机标识( 源i d ) 、页标识( 页i d ) 、发送时问戳和本机发送数据的最大序列 号。根据这些信息每个成员检查自己是否丢失了最后一个数据包，检查到有丢包，则按 照图3 1c 的过程对丢包进行恢复。 1 8 可扩展的可靠组播传输协议设计 3 3 协议设计原理图及模块交互 3 3 1 可靠组播在协议栈中的位置 由于组播技术都采用u d p 这种不可靠协议传输，可靠组播( r e l i a b l em u l t i c a s t ，r m ) 协议是实现组播传输的可靠功能，需要使用u d p 的端口号和校验和，这就决定r m 必 定在u d p 之上实现其可靠性。根据t c p i p 的分层，r m 应属于传输层协议，由r m 的 应用程序将数据封装在r m 信息包中，每个r m 信息包又被封装在u d p 消息段中，然 后再封装在l p 数据包中进行传输。同时为了简化了传输层处理，将部分传输层协议功 能( 比如流量控制) 上移到应用层完成。而从应用开发人员的角度看，可以把r m 看成 是应用层协议的一部分。 3 3 2 系统原理图 经过对组播的了解和深入研究，设计出如图3 2 的协议系统原理图。整个系统主要 由丢包检测、缓存管理及控制单元等模块构成。从u d p 的数据段中拆分出来的数据信 息就是本协议所规定的报文。当收到数据包时则送入丢包检测单元进行丢包检测。若检 测到丢包，请求控制单元对丢包进行修复，即在定时器的作用下发送出请求包来请求其 它主机对本主机的丢包进行修复；若无丢包，则送入缓存管理模块存放起来，继而递交 给上层应用；若收到控制包则送入控制单元进行相应的处理，在本章后面的小节里会详 细阐述。最终将缓存模块中的数据递交给上层应用。上层交付下来的数据也先存入缓存 管理模块再依次发送以避免处理时延过大而引起丢包，并帮助其它主机进行丢包修复。 第三章协议原理设计 图3 2 协议系统原理图 3 3 3 各个模块功能及其相互交互 ( 1 ) 丢包检测：丢包检测是保证组播可靠传输的基础。由于组播不是点对点的通仨 方式，所以仅仅用序号来保证传输可靠性是根本不够的，还需要区别不同的主机发送酐 数据包。根据a l f 协议提出的应用数据单元a d u s ( a p p l i c a t i o nd a t au n i t s ) 将数据包的枥 识由一个全球唯一的源端主机标识“源l d ”、“页l d ”及在整个组播组域内唯一的包序 号组成。在缓存里给每个成员都分配一段动态内存空间，用来存放每个成员所发送的赘 据包。当检测到某个成员某一页上数据包的序号有所缺失，立即将丢包信息传给控制牟 元，由控制单元完成此丢包的修复工作。 但) 缓存管理：在组播通信中，如果所有主机的丢包都到源端主机修复，就会给溺 端主机造成严重负荷，也会使网络拥塞。所以，要求一台主机不但能够检测到丢包并逆 行丢包重传，同时也要能够响应其它主机丢包，帮助其修复丢失的数据包。考虑到这一 点每个主机就需要一个缓存来存放数据包，帮助其他主机进行丢包修复。同时，为了黟 止应用层交付的数据包速率过快、处理时延过长而导致丢包，应把应用层交付的数