（计算机应用技术专业论文）应用层组播转发树重构技术研究.pdf

郑卅l 大学硕士学位论文 摘要 近年来，一对多、多对多通信的需求使得i p 组播和基于端系统的应用层组播成为了 网络研究的热点课题。i p 组播目前面临许多问题，影响了其在i n t e m 战上的部署，而应 用层组播虽然易于部署，但端系统的不稳定性导致了转发树的不稳定。因此，在应用层 组播中，转发树的重构就尤为重要。目前针对转发树的重构有两种策略：一种是前向 式，另一种是后向式。由于前向式重构是在父节点失效前预先计算备用节点，减少了重 构时间，因而能更好的提高转发树的可靠性。 针对转发树的重构问题，本文进行了两部分工作：第一部分工作是对现有的几种前 向式重构算法进行了对比实验研究。研究表明，p c p 算法在寻找备用节点的开销方面小 于r o t 算法，但是找到的备用节点的延迟特性不如r o t 算法。相对而言，r o t 算法 更适合于转发树结构相对固定的应用场合。第二部分工作，在对上述几种前向式重构算 法研究的基础上，提出了新的重构算法p l a 算法。该算法的核心思想是在“链路预 留”思想的基础上，考虑了链路延迟约束。本文将该算法同其它前向式重构算法进行了 对比试验，结果表明：在平均加入开销与备份链路延迟这对矛盾中，p l a 算法作了比较 合适的调和。同p c p 算法相比较，p l a 算法虽然在平均加入开销上有所增加，但是重 构的组播树的备用链路延迟降低了；同i 的t 算法相比较，虽然p l a 算法的备份链路延 迟不如r o t 算法，但是p l a 算法的平均加入开销耗费的较少。研究表明，p l a 算法更 适合于在节点相对不稳定的h 峋n 甙中部署，尤其是那些既考虑通信质量又要求连接开 销的应用场合，譬如网络电视，b t 下载以及大规模流媒体的实时应用等。 关键词：计算机网络，应用层组播，转发树重构，前向式重构 应用层组插转发树重构技术研究 a b 8 t 隋c t m 1 1 l d c a s t h a s k 髓1 t 1 1 e h o t t o p i c i l l l l l e r e s e 疵b o f c o m 咖n 咖r ka s t h e p o i n t - t o m l 帕p o i n td a 诅a n s f e ra p p l i c a l i o n s 撕s e h o w e v e r ，m o r e 血趾a d e c a d ea f t e ri t s “在a lp r o p o s a l ， d 印l q 【e mo f 舻c a s th 鹊b e e ni i m i t e d 趾l ds p a r s e 血l et os o m e r e a s o n s h lo r d e rt 0r e s 0 1 v e t h ep m b l e m s ，s o m er e s e a 圯h e r sp r o p o s e 印p l i a 狐o nl e v e lm i l l 廿c a s t ( a i j m ) t h en o n l e a f n o d e s i 1 1m e 廿e ea r en o r m a lc n dh o s t s ，w h i c ha r ep o 删a l l ym o r es u s c 印廿b l et 0f h i l u r e s t h u sa i l i i l l p 删p r o b l 锄i 1 1a l m i sh o wt or e c o v e r 丘d mr 砌ed e p a m l r e s 0 nm eq u e 嘶o n ，t l l e r ea r e t w oa p p r o a c h e st om er e c o v e r ) ro f 也ea p p l i c a d o nl e v e lm 叭c a 眦n 七e o n ei s 也er e a c 缸v e a p p i | 0 a c h a n o t h e ri st 1 1 ep r o a c d v ea p p f o a c l l ，w 1 1 i c hp l 锄sf o rd 印a r t l 鹏sb e f o r et h c yh a p p e n w m lt h ea i do f p r o a c 廿v ea p l 邶a c h ，an e wd e l i v e r y 心e ec a nb eq u i c h yr e g t o r e d t h er e s e a r c hw o r ki sc c i i t e r e do nr e c o i l s m 】c t i o no f f 0 删i n g 订c e 1 1 1m i s 也e s i s ，也e r ea r e 栅op a r 臼证t h em a i l lw o r k f i i 钝b a s eo nt h ec o m p a r a t i v e 狮a l y s i so f a p p a c h e st ot 1 1 e r e c o v e r yo f t h eo v e r l a ym u m c a s 【廿_ e e ，w ec i l o o s et h ep m a c t i v ea p p m a c ha se f n p ：h a s e s h 1m e p a n ，曲e 硎i z a d o no f 幽删m mi s 洳p o n a n t t h r o u 曲s 妇l l l 面o ne x p 矧妇e n 招，w eh a v e r e a l i z e ds e v e r a la l g o r i 廿l m so f p r o a c t i v ea p p r o a c ha n d 删y z e dm ea d v a i l t a g e sa n d d i s a d v a n ：c a 嘻e so f 也e s ea l g 耐t l l r n s s e c o n 也b 勰eo nm ec o m p 趾咖e 砌y s i s ，w ep r o p o s e da n e wa l g 叭p l a ，t h ec o r eo f w 【l i c hi sap r e - p l a nm o d e lb a s e do nt 1 1 ep r o a c 血忙a p p r o a c h i n 吐l i sp a n ，e x 删m e n t si sa 1 1i l n p o 胁tp 甜t h cs i m l l l a l i o n 嘲财i i l l e n 乜h a v eb e e nm a d eb 粥e d o nt 1 1 en e wa l g o r i 也ma n de 珥) e d m e n t a lr c s u l 乜a r e 删y z e d t h r o u g he x p e r m l e n t 刮丘o na i l d r e s e 础，m ef 0 1 1 0 w i n gc o n c l l l s i o 璐a r e 栅：p l aa l g 嘶也mc a nr e c o n c i l ct t l ec o n _ 妇d i c t i o no f 弘加一c d a n d 6 叩嘲矿加h 妇幻，；p l aa 1 9 0 痂h mc 觚r a i s e 缸p e r f 0 i l a i mo f n i u d 吐c a s c f o 脚m n g 订c e k e y w o r d s ：c o m p u t e rn 咖o r k ；a p p l i c a t i o nl e v e lm u m c a s t ；r e c o n s 眦垃o no f f 删j n g1 慨；p m a 蒯v er e c o n s n l 枷o n 郑重声明 工 3 ，& ， j 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、抄袭等违 反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的一切法律责任和法 律后果，特此郑重声明。 学位论文作者( 签名)：秘书 l g 只乙日 年否妒 郑州大学硕士学位论文 第1 章引言 1 1 课题背景及选题依据 近年来，随着网络技术的不断发展，f t p l 、h t l p 、s m t p 3 等传统数据业务已经难 以满足人们对信息业务的需求，视频点播、远程教学、新闻发布、视频会议、股市行隋 发布、多媒体远程教育、c s c 咿协同计算等业务在应用中变得日益重要。这类业务的 特点是显著的高带宽的多媒体应用，这些应用需要比较大的网络带宽，会引发带宽的急剧 消耗和网络拥挤问题，信息在一个组内以一对多或者多对多的形式进行传输。例如新闻 发布信息由一个服务器发布，大量不固定的接收端接收。如果采用单播方式来传输这 些信息，那么发送源就必须维护每个客户信息。当客户数目很多时，对于发送源来说还 需要很高的传输速率。另外，相同的数据可能在同一个链路上传输多次，消耗大量的网 络带宽。为了缓解网络瓶颈，人们提出了组播口m u m c a 啪 1 技术方案。但是从因特网中 p 组播的应用现状看，i p 组播并没有取得预期的成功。由于组播路由器需要为每个活动 的组维护路由状态信息，网络中大量的活动组将需要路由器巨大的存储和处理开销；开 放的口组播模型在开放的i n t e m 融环境中难以支持有效的管理和控制机制。以上这些因 素都制约了p 组播的发展。于是，一些研究者提出将复杂的组播功能放在端系统( e 1 1 d _ s y s 衄n ) 2 3 实现的新思想，也就是使用应用层组播( a p p l i c 鲥o nl a y e rm u l t i c a s t ) 技术来 替代传统的m 组播技术，由于应用层组播保持了互联网的“单播、尽力发送”模型，并 且部署方便等优点，得到了迅速的普及，成功地案例有香港理工大的c o o l s h a m ，华中 科大的p p l i v e 等。 应用层组播和传统的p 组播技术相比，可以避开网络层实现组播功能的许多难题： 1f n e t m s r t 晰o c o l 2l 帅d 1 矾1 协s 断p m l o c 0 1 3s 呻l em 日i l 撇p r o t o c o l 4c o “p u s 1 1 p p 0 删c 0 a 呻稍v c w o 血 应用层组播转发树重构技术研究 1 应用层组播的状态在主机系统中维护，不需要路由器保持组的状态，解决了业务 的扩展性问题； 2 组播应用可以随时部署，不需要网络设备的升级和功能扩展； 3 可以简化组播的控制、可靠等功能的实现，建立在网络连接之上的应用层组播可 以使用传输层的t c p 、u d p 协议，如可以利用t c p 的可靠和拥塞控制简化组播 的可靠和拥塞控制。当然应用层组播对带宽的节省不如m 组播；协议额外的 开销比较大。但是因为其开发方便，部署简单应用层组播还是具有比较好的应 用前景。 由于应用层组播是基于端系统来构造其转发树，因而端系统的稳定性决定着应用层 组播转发树的稳定性。应用层组播不像传统的m 组播那样，转发树中的叶节点通常是 端系统，这些节点潜在的比路由器更易失效或频繁的退出转发树，一旦发生这种情况， 那么该节点下游的所有节点将受到影响。因此，在应用层组播应用中，一个很重要的问 题就是如何迅速的恢复转发树，使得受影响的这些节点尽量缩短其服务中断。 鉴于此，应用层组播转发树的重构问题逐渐被提了出来，并成为热点问题。 1 2 国内外研究现状 目前，在树的重构问题上，有两种策略，一种称为后向式( r e a c 垃v ea p p r o a c h ) 策 略，该方法是在节点失效后，再进行树的重构，代表的方法有( 4 5 】 6 】，这种事后补救 的方法会花去不少时间，用于在多个节点间选择一个合适的加入点，来重新构造转发 树。这样就使得受到影响的节点会有一个比较长的服务中断；另一种方法称为前向式 ( p r o a c t i v ea p p m a c h ) 策略，代表算法有r o t 7 】、p c p 8 】和p r m 9 】，这种方法的特 点是在节点失效之前预先计算好节点的新的父母节点，一旦该节点的父母节点退出，就 可以根据预先计算的结果快速地找到新父母节点，避免花太多的时间用于寻找新加入 点，从而减少服务的中断时间。 2 郑卅l 大学硕士学位论文 1 3 课题所做的工作及论文结构 1 3 1 本文主要工作 本文工作主要分为两部分，前期工作是对现有几种主要技术的实验、分析、比较几 种前向式算法的优缺点；后期针对上述算法的优缺点提出了一种新的重构算法p l a 算 法，这是一种结合了p c p 【8 和r o t 7 两种典型前向式重构策略的算法，其核心思想是 节点采用了“链路预留”的思想，为自身寻找备份链路，进行树的重构。 本课题的研究目标为：利用前向式重构策略，在重构应用层组播转发树的过程中， 在控制节点加入转发树的花费开销基础上，尽量降低备份链路的延迟，减少数据丢失 率，使得流媒体等高带宽应用在h e n l e t 上的应用更加流畅。 1 3 2 论文结构 通过对现有应用层组播转发树重构技术的研究，实现了一个基于m 仅c a s t 1 0 应用 层组播通信模型的组播转发树重构算法，该算法在稍微增加了节点加入开销的基础上， 大大降低了重构后转发树的备份链路延迟，由于该算法的灵活性秘可扩展性，因而比 r o t 算法更易于部署。 本文组织如下： 第二章“相关技术”，介绍了应用层组播转发树重构技术所涉及的相关技术。其 中包括组播、应用层组播、m 黜等通信模型。 第三章“前向式重构的相关解决方案及实验分析”，介绍了目前几种前向式策略的 具体方案，继而通过仿真实验、分析、验证了p c p 算法和r o t 算法在几个重要衡量指 标上的优缺点。 第四章“基于p l a 算法的重构解决方案”，通过对p c p 算法和r o t 算法的优缺 点比较分析，提出了一个基于p c p 算法的p l a 算法，并通过仿真实验来分析验证了 p l a 算法对p c p 算法在重要衡量指标上的改进。 第五章“结束语”，给出本文的结论，同时根据存在的问题，提出了下一步的研究 方向。 应用层组播转发树重构技术研究 第2 章相关技术 本章将介绍分析一些本课题所涉及到的相关技术，内容组织如下：首先讨论并比较 了目前可用的群组通信模型，包括；口组播、应用层组播和m i 】【c a s t 1 0 。接着介绍在 m i ) 【c a s t 中所涉及到的一些相关技术。 2 1 组通信模型 组通信在分布式系统和并行计算机系统中有着非常广泛的应用。组是动态的，可以 创建新的组，也可以注销旧的组。参与者可以动态的加入或退出组，因此需要一种机制 来管理组和组的成员。组通信模型的优势是避免了传统点对点通信模型中，针对每个接 受者，发送者都要转发次数据包，浪费网络资源的情况。组通信模型中，数据往往同 时传递给组内多个接受者，一次传输，多点到达，节省了网络资源。因而组通信成为网 络研究中的热点课题。 2 1 1 碑组播 早在1 9 8 8 年，斯坦福大学的博士生s e d e e r i n g 就提出了p 组播机制。它是最 早的、最有效的组播传输机制。主机之间一对一组的通讯模式，将坤数据报从一个源 传送到多个目的地，将信息的拷贝发送到一组地址，到达所有想要接收它的接收者。也 就是加入了同一个组的主机可以接受到此组内的所有数据，网络中的交换机和路由器只 向有需求者复制并转发其所需数据。群组的各个成员可以分布于各个独立的物理网络 上，主机根据组地址( g f o u p a d d r e s s ) 可以向路由器发送i g 口5 履m d 6 1 1 】 1 2 】请求，请 求加入或退出某个组，路由器收到用户请求后，根据运行的组播路由协议的不同，在路 由器间构造共享树( r p f 7 ) 或者源树( s p r ) ，来保证组播数据自旨够从发送者正确到 5 i c l t e m e 亡( 抽u p m 柏a g 1 舶c p 忉幻c o l 6m u l 髓a s t l i s 【e 咐d i s c o v 哪 7r d c a p o h n t | 8s h o n e s t p 耐1 1 慨 4 郑州大学硕士学位论文 达接收者。网络中的路由器和交换机有选择的复制并传输数据，即只将组内数据传输给 那些加入组的主机。这样既能一次将数据传输给多个有需要( 加入组) 的主机，又能保 证不影响其他不需要( 未加入组) 的主机的其他通讯。 2 1 1 1p 组播协议 i p 组播协议主要分为组管理协议和路由协议两类。其中组管理协议负责主机和路由 器之间的交互，主机通过组管理协议来告知路由器加入或者离开组播组；组播路由协议 负责在路由器之间构造组播转发树，以完成组播数据的分发。 组管理协议主要有m v 4 环境下的i g 咖p v l 【1 】、i g m p v 2 1 1 】和i g m p v 3 【1 2 ，m v 6 环 境下的m d v l 1 3 】和m 国v 2 1 4 ，其中i g 棚p 1 ，2 和d v l 功能基本类似，目前较为普 及。 在组播路由协议方面，早期的协议，例如d 、，】诳冲9 1 5 、m o s p f l 0 1 6 等，由于可 扩展性较差，以及依赖于单播路由协议，因此逐步被淘汰。目前的组播路由协议主要分 为两大类，即域内组播路由协议和域间组播路由协议。域内协议主要有p - d m 17 、 p d 讧s m 1 8 】，其中p 正d m “采用洪泛加剪枝的工作模式，不适合较大规模的网络； p 订s m l 2 采用接收者发起构建共享树的工作模式，是目前使用较多的组播路由协议， 其主要缺点是协议比较复杂。 在域间协议中，目前较为成熟的方案是p d “一舒d 伍佃( m m s d p 三个协议结合起 来，由p m s m 协议负责域内的组播转发树构建，m b g p l 3 协议( i9 传递不同a s 间的组 播路由信息，m s d p 协议【2 0 传递不同域内的组播源通告信息。m s d p 协议的主要缺点 是当自治域数量较多时，该协议的可扩展性不是太好，因此被看作是一种过渡方案，只 9d r p ：距离向量组播路由协议 m o s p f ：摄短路径优先组播 “p r a t o c o l i r l d c p 曲d 眦m u 惦c a s t 蛐m o d e up r a i o c 0 1 i f l d e p d 咖m u m c a s t s p a 瓶m o d e 1 3 m n 币州o c o ib o r d e rg 锄州a yp r o t o c o i 应用层组播转发树重构技术研究 是在v 4 环境下使用，在i p v 6 环境中没有被采用。除了m s d p l 4 协议，肼还提出了 另一种域间组播解决方案，即m a s c l 5 b g 啪p 1 6 协议【2 1 ，但是由于协议本身过于复 杂，没有得到广泛的采用。 i p 组播工作模式如图2 1 ： 口庸盘鞲+ h 蟪斌嘏措捧输蟪掩 。接收董l 一一一散捌传相溉向 毅掘秤童帆 图2 1i p 组播 口组播的优点： 1 需要相同数据流的客户端加入相同的组共享一条数据流，节省了服务器的负 载。具备广播所具备的优点。 2 由于组播协议是根据接受者的需要对数据流进行复制转发，所以服务端的服务 总带宽不受客户接入端带宽的限制。p 协议允许有2 亿6 千多万个组播，所以 其提供的服务可以非常丰富【2 2 。 3 此协议和单播协议一样允许在锄e t 宽带网上传输。 m 组播的缺点： 4m u m c a s t s o u r c e d i s 。o v e i yp r a 幻0 0 1 5 m u l c 嚣t a d d f e 嚣s 吐a a h n 6b o i d c r g a l c w a y m 山石鼬吐p 啪c o l 郑州大学硕士学位论文 1 与单播协议相比没有纠错机制，发生丢包错包后难以弥补，但可以通过一定的 容错机制和q o s 加以弥补。 2 访问控制较为困难，对于运营商而言，如果想在网络中使用组播技术，就希望 能够进行流量统计，以便于计费功能的实现，而传统的组播难以实现这样的功 能。 3 路由协议复杂。目前使用的组播路由协议，无论是域内的还是域间的，都比较 复杂。在设计核心路由器的时候，一般需要用硬件来实现组播数据报文的转 发，但是目前普遍采用的协议，有许多交互操作，致使协议实现较为复杂，且 不利于高端路由器使用硬件进行加速。同时，这些协议的健壮性和百，扩展性也 不够理想。 4 加重了路由器的负载。为了使路由器支持组播通信机制，就必须在路由器中支 持各种组播路由协议和组管理协议，同时，路由器还要支持组播转发表的构造 以及完成组播数据报文的转发。当组播组数目比较多时，会给路由器增加不少 负载。 5 i p 组播要求所有路由器支持组播，而有些i s p 的路由器不愿意支持组播功能， 所以组播服务的部署、推广变的很困难。 2 1 2 应用层组播( a l m ：a p p l i c 甜o nl e v e lm u 城c 髂t ) 面对疋组播业务在因特网中的困境，一些研究者开始反思疋组播体系结构本身的 问题，提出将复杂的组播功能放在端系统实现的新思想。端系统实现组播业务的思想是 将组播作为一种叠加的业务，实现为应用层的服务，因此，端系统组播又称为应用层组 播( a p p l i c a t i o nl e v e l m u m c a s o 2 3 。应用层组播网的节点是组播成员主机，数据路由、 复制、转发功能都由成员主机完成，成员主机之间建立一个叠加在p 网络之上的、实 现组播业务逻辑的功能性网络，称为叠加网( o v e r l a y n 酣 的r k ) 2 4 ，主机基于自组织 算法建立和维护叠加网。应用层组播的数据在主机间实现复制和转发，数据报沿着逻辑 链路转发，多跳逻辑链路可能经过同一条物理链路。应用层组播的基本思想是保持互联 应用层组播转发树重构技术研究 网原有的简单、不可靠、单播的转发模型，由端系统实现组播转发功能。工作模式如图 2 2 ： 口路由器 熬抛积土机 。接收生机- ，澎捌瑶魁捂转篾纠 图2 _ 2 应用层组播 应用层组播与网络层组播最大的区别在于，网络层组播依赖路由器来构造转发树； 而应用层组播是在主机之间构造转发树，处于网络层的路由器只需支持单播就可以了， 这样就大大简化了组播在网络层的部署难题。图2 3 所示为口层组播与应用层组播的区 别：a 为数据源，b 、c 、d 为接收端。左图采用网络层组播技术，在路由器1 、2 、3 、 4 、5 之间构造转发树，其中路由器l 为树根。数据从数据源a 到达路由器1 后，数据 就沿着口层组播转发树转发到各个路由器，然后再由路由器把数据转发到各个接收 端。右图采用应用层组播技术，路由器1 、2 、3 、4 、5 就不需要做那些工作。数据由主 机a 传递到主机b 、d ，再由b 将数据传递到主机c ，这样就完成了整个数据的分发与 接收。在这个过程中完全屏蔽了物理网络的拓扑结构。实际上是在主机之间建立一个叠 加在p 网络之上的、实现组播业务逻辑的叠加网。 郑州大学硕士学位论文 口 蹄山器 艘朋豫封l 措转粒橱 o。i ：机料| 扮船维播转笈树 图2 _ 3 口层组播与应用层组播 但是，相对口组播而言，应用层组播在节点的稳定性、传输效率等方面面临严峻 的挑战。由于构建者是普通的网络主机，这些主机彼此不知在拓扑中的相互位置关系， 必须自己获得一个拓扑，并且在上面构建转发树。概括而言，影响应用层组播传输效率 不高的主要因素有以下几点： 1 担当复制转发任务的普通终端主机的性能不高； 2 复制转发工作在应用层通过软件实现； 3 通过主机自己测试产生的拓扑可能会导致构建出一个无法充分利用底层网络设 施的转发树； 4 为了弥补口组播在安全可靠方面的缺憾，应用层组播还要增加诸如安全可靠 之类的服务，这将进一步消耗主机的资源。 前三点就足以导致应用层组播的性能相对口组播大打折扣，可能会导致整个服务 不可用。对于这个问题，我们只能够在第3 点上作一些研究工作，同时尽量开发出效 率高的应用层组播软件。一些研究人员在致力于开发更好的转发树构建方法 2 5 】 2 6 。 无论如何，应用层组播为我们提供了个解决组播问题的途径。 应用层组播转发树重构技术研究 2 1 3m i x c a s t m i x c a s t 1 0 】是一种混合了单播和组播的通信模型，其基本的出发点来源于h 】t e n l e t 核心简单化、边缘复杂化的目标。骨干网中的核心路由器承担着大量的数据转发任务， 应当尽量简化，一些复杂的控制功能应当尽量向边缘转移，m i ) ( c a s t 的思路就是在域间 采用单播通信，域内采用组播通信。其工作模式如图2 4 ： 口 瞎m 器戍刚聪昭撬传输线蘸 款撵游书机_ _ 耐热瑶组撬传输缝路 。接收j 二桃( )m d p i m l x c 雌t 数荆代理) 图2 4m i x c a s t 通信模型 域：在m i ) 【c a s t 通信模型中，域的概念是指一个可完全管理的接入网，比如个校 园网，或者一个企业网，或者一个小区宽带网；例如图2 4 中的域a 到域e 这5 个域。 m d p ：在每个域内，都有一个设备充当该域的m i ) 【c a s t 数据代理( m i x c a s td a _ i a p r o 珂) ，不同域之间的m d p 组成一个应用层组播转发树，用于在域间转发组播数据。 m d p 之间通过单播的方式进行通信。 如图2 _ 4 ，数据源位于域a 中，它首先把数据发送到所在域的姗d pa ，然后以该 m d p 为根，在所有接收端的啪) p 间构造应用层转发树，转发树之间采用单播通信，当 数据到达m d p 后，在域内采用m 组播通信，将数据分发给域内的每个接收端。 】o 郑州大学硕士学位论文 2 _ 2m i ) 【c a s t 通信模型中转发树的构造 在m 政c a s t 通信模型中，转发树的构造是基于m r p 协议 8 】 1 0 。在m r p 中，节点 加入算法的处理流程为：对于一个想加入树的新节点n ，它首先向根结点发送一个j o n 请求，如果根节点还有剩余的出度，就会接受节点n 成为其子女，如果根结点的出度 已经满了，就会拒绝接受n 成为其子女，同时会把其子女节点的信息告诉n ；接下来， n 就在这些节点中，选择个合适的节点进行加入，如果这些节点的出度全部为o ，则 不在这一层进行选择，而是继续往下走。 至于选取节点的原则，有两个策略：( 1 ) 宽度+ 延迟优先( m t p l ) 【8 。n 在有剩 余出度的节点中，选择r r r 值最小的节点加入，如果所有节点的出度都为o ，则选择 r 盯最小的节点往下递归寻找加入位置；( 2 ) 深度+ 延迟优先( m t p 2 ) 【8 】。n 只选择 f m 最小的节点，如果该节点有剩余出度，则n 成为该节点的子女，如果该节点没有 剩余出度，则直接沿着这个节点往下寻找加入位置。 在下面的仿真试验中，m r p l 、m t p 2 算法，就是构造转发树的两种策略算法，我 们的实验分析，也是基于这两种不同构树策略来进行横向比较的。 2 3 本章小结 本章主要介绍了网络通信的几种模型，并分析了其优缺点，其中主要是m c a s t 模 型。它是一种结合了口组播和应用层组播两种技术的新的通信模型。本课题组播树的 重构实验就是基于该模型，通过该模型的组播树构造算法m 冲1 ( 广度和延迟优先) 和 m t p 2 ( 深度和延迟优先) 分别来构造两棵转发树，进而在这两种转发树上分别运行重构 算法。 应用层组播转发树重构技术研究 第3 章前向式重构技术研究和实验分析 本章研究的重点是应用层组播转发树前向式重构技术的研究和实验分析。首先描述 了现有的几种前向式重构算法，然后针对p c p 算法和r o t 算法进行了仿真对比实验， 最后是对实验结果进行了分析和评价。 3 1 前向式算法 3 1 1p r m 算法 p r o b a b i l i s t i cr e s i l i 锄tm l l l t i c 勰t ( p r m ) 算法【2 7 提出了一种随机推进的方法，每个 节点随机选择固定数目的其他节点，以小概率给每个选择的结点转发数据。在节点失效 的情况下，该算法可以达到较高转发率。另外，p r m 算法是一种数据层面的重构策 略，它只是随机向前推迸数据，没有其他什么限制，具体算法示意图如图3 1 。 囵 繇三一 图3 1p r m 算法 其中：o 代表节点，代表失效的节点或链路，一代表数据流向，曲线代表随机推 进的数据流向。 由于p r m 算法在数据层面上随机转发数据，因而会有一定的重复数据包，浪费一 定的带宽。而我们研究的重点则是下面两种重构策略，r o t 算法和p c p 算法，这两种 算法是基于控制层面来进行树的重构，p r m 算法则可以作为这两种算法的很好补充。 3 1 2r o t 算法： r 0 r r 算法 7 中对于每一个非叶节点来说，它必须为它的所有孩子节点找到一个备 用父母节点。一旦该节点失效，它的孩子节点能够准确知道谁是它的新的父母节点。因 郑州大学硕士学位论文 而，当父母节点失效后，对于每一个孩子节点来说能够迅速地连接到它的备用父母节 点，能够迅速地从失效中重新恢复中断的服务。 具体算法描述： 对于节点n 来说，节点n 为其孩子节点计算备用节点。首先节点n 从所用孩子节点 中选择一个到节点n 的父母节点开销最小的节点c 1 ，把该节点的备用父母节点指向节 点n 的父母节点。然后把c l 节点及其孩子节点放入集合a 中，把节点n 剩余的孩子节 点放入集合b 中，然后从集合a 、b 中选择连接开销最小的两节点，把这两个节点建立 起备用连接。同理直到集合b 中没有节点。 其主要思想如图3 2 ，预失效的节点( 5 ) 为孩子节点( 8 ，9 ，1 0 ) 计算备用父母节点。主要 考虑的是延迟优先。 4 瓜。氏 6 1 51 6 、j 71 81 9 ：2 02 l2 2 、一- _ # + ， 图3 2r o t 算法 3 1 3p c p 算法 p c p 算法 8 】采用了“链路预留”的思想进行树的重构，借鉴q o s 中采用的“资源 预留协议”( r s v p l 7 ) ，在转发树中预留些链路，用于树的重构。 7r c s m 矾e r e s 州甜彻p t 蝴l 应用层组播转发树重构技术研究 对于要计算预留链路的节点n 来说，首先将指针指向n 的父母节点p ，如果p 没有 兄弟节点，则沿着树往上走，将p 指向原节点的父母节点。然后判断节点p 是否有预留 链路，有预留链路则p 就是要找的节点，算法结束：如果p 没有预留链路，但是p 有兄 弟节点，则循环结束；否则，继续往上游走，如果一直没有合适的节点，会一直到达根 节点，循环结束。如果找到了合适的p ，则将p 的兄弟节点信息，写入一个队列q ，队 列q 中存放着候选节点的列表，n 可以以先进先出的次序从队列q 中取出节点，进行选 择；从队列q 中依次取出候选节点；将p 指向从队列中取出的节点；如果节点p 的预留 链路还有，则p 就是要找的节点，跳出循环；否则，将节点p 的子女节点加入队列q 中，继续循环。 其主要思想是节点为自己寻找备份链路，具体算法示意图如图3 3 。 1 5l6l7 1 81 92 02 l2 2 图3 0p c p 算法 3 2p c p 算法与r o t 算法实验分析： 评价标准： 实验中的评价指标有以下几种： 平均加入时间( a v e r a g ej o i l lt i m e ) ：节点寻找到备用父母节点所花的时间的 平均值，这个指标说明寻找备用节点的时间开销； 加入控制负载( j o i l l c o 呦1d ，酣1 e a d ) ：所有节点找到备用父母节点所用的控 制报文的个数，这个指标说明了寻找备用节点所占用的网络资源； 郑州大学硕士学位论文 各用链路平均延迟( b a c k u pl i n ka v e 豫g ed e l a y ) ：节点采用备用链路后的平 均延迟，这个指标说明了备用链路对转发树通信延迟的影响。 实验目的： 实验的主要目的，通过对p c p 算法和r o t 算法在基于m ，r p 协议构造的转发树上 进行转发树重构的对比实验，获得上述的几种评价指标的实验结果，从结果中比较这两 种算法在传输性能、控制负载规模以及加入时间方面的优劣及性能差别。 实验方法和内容： 实验所需的网络拓扑构造采用( * m 2 8 生成，实验中涉及的算法，使用c 群语言 在w i n d o w s2 0 0 3s e c r 上进行了实现，实验主机配置为p e 以u m42 8 gc p u ，1 g b 内 存，1 2 0 g bs a t a 硬盘，1 0 0 m 以太网接口。 针对上面的3 个评价指标，在节点数目不同和节点出度后为5 的情况下，对 p c p 算法和p l a 算法进行了对比实验。 对于节点规模n ，分为小规模网络、中等规模网络、大规模网络三种情况进行实 验，节点规模的集合分别用m ， ，2 ，3 表示，如表格3 1 。 瓣渊溯湖黼嘲趱麟黼燃黼黛斓麓 啪 1 0 ，2 0 ，3 0 ，4 0 ，5 0 ，7 0 ，8 0 ，9 0 ，1 0 0 )小规模网络 ( 1 0 0 ，2 0 0 ，3 0 0 ，4 0 0 ，5 0 0 ，8 0 0 ，7 0 0 ，o中等规横网 ，9 0 0 ，1 0 0 0 ，络 鞑3 1 0 0 0 ，2 0 0 0 ，3 0 0 0 ，4 0 0 0 ，5 0 0 0 ，0 0 ，7犬觌模网络 0 0 0 ，8 0 0 0 ，9 0 0 0 ，1 0 0 0 0 ) 表格3 。l 节点规模 测量指标中，平均加入时间用a j 表示，备份链路延迟用b d 表示，加入控制负载 用j o 表示如表格3 。2 。 应用层组播转发树重构技术研究 溪黼黎鬟豢黧黧l 雾| | 瀵糍麟蘸麓阑黼 a j平均加入时问 b d备份链路延迟 j 0加入控制负载 表格3 2 测量指标 m t p 协议，m t p l 协议用p l 表示，m 邛2 协议用p 2 表示，如表格3 _ 3 。 表格3 - 3 m t p 协议 在实验中，髓n 1 郇t o 口l 就表示，出度为5 ，节点规模为小规模，采用m 仲l 协 议构造的转发树上运行r o t 算法得到的平均加入时间的值。 实验结果及其分析： 3 2 1 平均加入时间 图3 - 4 平均加入时间_ n 1 郑州大学硕士学位论文 图3 _ 5 平均加入时间p 眩 图3 6 平均加入时间予昭 从图中可以看出，r o t 算法的平均加入时间总体上都大于p c p 算法的平均加入时 间，但是随着节点规模的增加，基于m t p l 生成树，r o t 算法与p c p 算法的差距增 大，而基于m r p 2 生成树，r o t 算法与p c p 算法的差距较小。 结论： 1 、p c p 算法的平均加入时间优于i 的t 算法； 2 、i t o t 算法与p c p 算法的差距，基于m t p l 树相差较大，而基于m r p 2 树相差 较小。 应用层组播转发树重构技术研究 3 2 2 备用链路延迟 图3 7 备用链路延迟- n 1 图3 8 备用链路延迟_ n 2 郑州大学硕士学位论文 图3 9 备用链路延迟- 量旧 从图中不难看出，采用i t 算法的备用链路平均延迟均小于采用p c p 算法的结 果，这主要是因为在r o t 算法中，主要是在节点的子树中来构造一棵新的转发树，这 些节点在物理上本身就相距较近；而在p c p 算法中，是在祖先节点的兄弟节点及其子 树中寻找备用节点，因此，p c p 算法选择的备用节点会比r o t 算法的备用节点的物理 距离要远一些，实验结果也说明了这一点。 结论： 一般情况下，r o t 算法的备用链路平均延迟优于p c p 算法；但是在大规模网络 下，基于m r p 2 生成树的p c p 算法优于r o t 算法。 应用层组播转发树重构技术研究 3 2 3 加入控制负载 图3 1 0 加入控制负载n 1 图3 1 l 加入控制负载 郑州大学硕士学位论文 图3 1 2 加入控制负载n b 从图中可以看出，无论节点规模如何增加，采用r o t 算法的控制负载总是略高于 p c p 算法。 结论：p c p 算法的加入控制负载优于r o t 算法。 3 3 本章小结 通过前面的实验，可以得到两种算法的比较结论。p c p 算法的平均加入时间和平均 加入负载优于r o t 算法，但是备用节点链路平均延迟不如r o t 算法，这说明p c p 算 法在寻找备用节点的开销方面小于r o t 算法，但是找到的备用节点的延迟特性不如 r o t 算法。相对而言，r o t 算法更适合于转发树结构相对固定的应用场合。 应用层组播转发树重构技术研究 第4 章基于p i a 算法的重构解决方案 本章研究的重点是p l a 算法的实现和仿真实验分析。主要内容为，首先是在p c p 算法的基础上，针对p c p 算法的一些缺陷，提出并实现了p l a 算法。然后通过实验对 p c p 、p l a 和r o t 算法进行对比仿真实验，最后是实验结果分析。 4 1 具体算法： 该算法借鉴了r o t 算法和p c p 算法的思想，在p c p 算法的基础上进行了改进。具 体思想： 1 采用了“链路预留”的思想进行树的重构 2 节点为自己寻找备份链路 3 充分利用了预失效节点的父母节点的剩余出度 4 对节点间的连接开销进行比较，优先选择延迟最低的建立连接 设对于节点f ，总出度为d ( f ) ，已经使用的出度是吃( f ) ，未使用的出度为4 ( f ) ， 未使用的出度中，预留链路的出度为d 。( f ) ，则有： d ( f ) = 吒( f ) + 4 ( f ) + 以( f ) 4 1 1 算法描述： 设要选择备用父母节点”的节点为甩，p 为指向某个节点的指针，p l a 算法的伪码 描述如下： 1 p r o c e d u r ep l a 0 ) 2 p 2 n p a r e m 3 肝= m i l l d e l a y 0 ) 选择最小延迟的节点 4 i f ，f m 5 h p a r c r l b b c 7 p 糊n ； ，虚链路 6 r e l 胁： 7 e l s e i 印p a r e n t n u l l 姐d p p a r e m d p o 郑州大学硕士学位论文 8 9 e l s e 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 0 3 1 3 2 3 3 3 4 3 5 3 6 3 7 r e n m p p 黼t预留链路 ( w m e p s i b l i i l 黔i sn u l l p 2 p _ p 嬲l t ； i f p d p 0 r e t i 】r n p ) i f p s i b l i n g s = n u l l n ol i l l k p r o v i d e d e x i t e l s e a d dt 咖p p s i b h n g s & 叻 a d d ( a ，b ) 把d p 0 的节点加入到a 中 w k l ea = 1 1 u l la n db c n u l l 向r 翩c h ( r l o d e i n b ) ( r 肌o v e ( 1 1 0 d e ) a d dt e i l l 邸舯d e 枷l d r e n ) ) a d d ( 凡b ) ) w l l i l ea m m p = m i l l d d a y j r e l i n k ( a ，n ) 选择最小延迟 r e t u m p ) ) 应用层组播转发树重构技术研究 3 8 1 3 9 r e t 哪o 4 0 e n dp r o c o d u r e 具体算法描述： 行l ，算法开始，参数为节点玎，代表要计算的节点 行2 ，首先将指针指向”的父母节点p 行3 ，节点口计算最小延迟节点聊 行4 6 ，如果n = 聊，节点甩与p 的父母节点建立虚链路，算法结束 行7 - 8 ，如果p 的父母节点非根节点且有预留链路，则p 的父母节点就是要找的节 点，算法结束。 行9 ，如果非上述情况，则算法继续。 行1 0 一1 6 ，如果p 有预留链路，则p 就是要找的节点，算法结束；如果p 没有预留 链路，但是p 有兄弟节点，则循环结束：否则，继续往上游走，如果一直没有合适的节 点，会一直到达根节点，循环结束。 行1 7 1 9 ，如果一直找到根结点都找不到合适的p ，则结束寻找过程，返回o ； 行2 0 ，如果找到了合适的珐算法继续 行2 1 。2 2 ，将p 的兄弟节点信息以及节点聊，写入一个集合b 中，集合b 中存放 着临时候选节点的列表 行2