（管理科学与工程专业论文）应用层组播最小延迟树生成、维护及其节点转发策略研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 由于i p 组播难于在因特网上部署，研究人员提出了应用层组播。应用层组播 将组播相关功能实现于终端主机，在应用层实现组播服务。由于终端主机的处理 能力和带宽有限，组播过程中复制转发工作消耗的时间比较长，导致应用层组播 延迟较大；并且终端主机容易失效或者退出组播组，导致组播树分裂，影响下行 节点接收数据。针对应用层组播延迟较大以及组播树分裂问题，论文以优化延迟 为目标研究应用层组播树的生成、维护以及组播节点的转发策略。本文的主要研 究内容和创新点如下： 首先，分析应用层组播中影响延迟的因素，包括链路通信延迟、节点度和节 点的转发能力。在应用层组播最小延迟树模型d c m d 的基础上提出一种新的模型 d n m d ，改进d c m d 模型未考虑节点转发能力差异的不足，并用遗传算法对模型 进行求解。在m a t l a b 环境中编程实现算法，进行仿真试验，验证了算法的有效 性和模型的合理性。 其次，研究了应用层组播树维护问题，包括组播树的分裂恢复和新节点加入。 借鉴r o t 恢复算法的思想提出一种混合恢复策略，以优化延迟为目标恢复组播树， 根据节点状态差异采取不同的恢复策略；针对新节点加入问题，以加入节点到根 节点的延迟最小为目标寻找合适的加入位置。 最后，提出了一种组播节点的数据转发策略，通过合理安排组播节点向其子 节点转发数据的顺序优化组播树的延迟。推导证明了组播节点按照该策略转发数 据，组播树的延迟最小。用一个实例说明策略的具体应用方法，并在m a t l a b 环 境中进行仿真试验，验证了策略的有效性。 主题词：应用层组播最小延迟组播树组播树生成组播树维护转发策略 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t r e s e a r c h e r sp r o p o s ea p p l i c a t i o nl e v e lm u l t i c a s tb e c a u s ei pm u l t i c a s ti sh a r dt o d e p l o y a p p l i c a t i o nl e v e lm u l t i c a s tp r o v i d e sm u l t i c a s ts e r v i c e si nt h ea p p l i c a t i o nl e v e l b yi m p l e m e n t i n gm u l t i c a s t sf u n c t i o no nt h eh o s tc o m p u t e r s ，w h i l ef o r w a r dd a t ab yi p u n i c a s ti np h y s i c sn e t w o r k b e c a u s et h ef i n i t ep r o c e s sc a p a b i l i t ya n db a n d w i d t ho fh o s t c o m p u t e r s ，r e p l i c a t i o na n df o r w a r d i n gd i s s i p a t em u c ht i m ea n dr e s u l ti nh i g hd e l a yi n m u l t i c a s t c o n t e m p o r a r y ，t h eh o s tc o m p u t e r st e n dt ov a l i d a t eo rd r o po u tf r o mt h e m u l t i c a s tg r o u pr e s u l ti ns p l i to ft h em u l t i c a s tt r e e sw i l li n f l u e n c et h ed o w n s t r e a m n o d e sr e c e i v et h ed a mf r o mt h em u l t i c a s tr e s o u r c e m sp a p e rm a i n l yr e s e a r c ht h e c o n s t r u c t i o na n dm a i n t e n a n c eo fm u l t i c a s tt r e ew i t hm i n i m u md e l a ya n dt h ef o r w a r d i n g p o l i c yo ft h em u l t i c a s tn o d e si no r d e rt or e s o l v et h ep r o b l e mo ft h eh i g l ld e l a ya n d d i s r u p t i o no fa p p l i c a t i o nl e v e lm u l t i c a s t 1 r i l em a i nc o n t e n t sa n df r u i t so ft h i sp a p e r a r e o u t l i n e da sf o l l o w s ： f i r s t l y ，t h i sp a p e ra n a l y s i st h ef a c t o r st h a ta f f e c tt h ed e l a yo fa p p l i c a t i o nl e v e l m u l t i c a s tw h i c hi n c l u d e st h ed e l a yo ft h ec o m m u n i c a t i o nl i n k ，d e g r e ea n df o r w a r d c a p a b i l i t yo fn o d e s an e wm o d e ln a m e d a sd n m di sp r e s e n t e db yi m p r o v et h ed c m d m o d e lb e c a u s ei td o e s n tt a k et h ed i v e r s i t yo fn o d ef o r w a r dc a p a b i l i t yi n t oa c c o u n t t h e ng ai su s e dt or e s o l v ed n m dm o d e li ns u c c e s s i o n t 1 1 ev a l i d i t yo ft h ea l g o r i t h m a n dr a t i o n a l i t yo ft h em o d e li sp r o v e db ys i m u l a t i o n s e c o n d l y ，t h ed y n a m i cm a i n t e n a n c eo fm u l t i c a s tt r e ei n c l u d e sr e c o v e r yo ft h e d i s r u p t e dt r e ea n dt h en e wj o i nn o d e sp r o c e s sh a sb e e ns t u d i e di nt h i sp a p e r am i x e d r e c o v e r yp o l i c yi sp r o p o s e db yt a k et h ea d v a n t a g eo fr o ta l g o r i t h m a c c o r d i n gt ot h e d i f f e r e n c eo fn o d es t a t e ，d i e f f e r e n tp o l i c yi su s e dt or e c o v e rt h em u l t i c a s tt r e ei no r d e rt o o p t i m i z et h ed e l a y a i m i n ga tt h en e wn o d ej o i np r o b l e m ，a na l g o r i t h mi sp r o p o s e dt o f i n dm i n i m u md e l a yf r o mt h en e wn o d et ot h er o o ti so b j e c t l a s t l y ，t h i sp a p e rp r o p o s eaf o r w a r d i n gp o l i c yo fm u l t i c a s tn o d e st oo p t i m i z et h e d e l a yo fac o n s t r u c t e dm u l t i c a s tt r e eb ya r r a n g eap r o p e ro r d e rw h e nan o d ef o r w a r d d a t at oi t sc h i l d r e nn o d e sa n dp r o v et h a tt h ed e l a yo fm u l t i c a s tt r e ei so p t i m u mi ft h e n o n - l e a fn o d e sf o r w a r dd a t aa c c o r d i n gt ot h ep r o p o s e dp o l i c yb yr e a s o n i n g t h e na n e x a m p l ei su s e dt oi l l u s t r a t eh o w t ou s et h ep o l i c y 1 1 1 ev a l i d i t yo ft h ep o l i c yi sp r o v e d b ys i m u l a t i o nt h a tc a r r i e do u ti nm a t l a b k e yw o r d s ：a p p l i c a t i o nl e v e lm u l t i c a s t 。m i n i m u md e l a ym u l t i c a s tt r e e ， c o n s t r u c t i o no fm u l t i c a s tt r e e ，m a i n t e n a n c eo fm u l t i c a s tt r e e ，f o r w a r d i n g p o l i c y 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表1 1 口单播、i p 组播以及应用层组播对比3 表3 1 度约束值与节点转发能力2 4 表3 2 新节点加入计算实例节点延迟3 5 表3 3 新节点加入计算实例节点延迟之和3 5 表4 1 节点转发延迟4 4 第1 i i 页 国防科学技术大学研究生院硕士学位论文 图目录 图1 1p 单播、口组播、应用层组播数据转发示例图2 图2 1n i c e 示意图7 图3 1 示例树t 15 图3 2 示例树t 的矩阵编码方式。1 6 图3 3 剪枝法示意图1 8 图3 4 选择操作流程图1 9 图3 5 交叉操作示例树t l 、t 2 2 0 图3 6 交叉操作示例树t 3 、t 4 2 0 图3 7 变异操作示意图2 1 图3 8 遗传算法流程图。2 2 图3 9 延迟矩阵2 3 图3 1 0 种群最优个体进化过程2 4 图3 1 1 生成树矩阵表示2 4 图3 1 2 生成树图表示2 5 图3 1 3 不同模型生成树直径对比图2 5 图3 1 4 不同转发能力生成树直径对比图2 6 图3 15 组播树分裂示意图2 6 图3 。1 6r o t 算法示意图。2 8 图3 1 7r o t 算法导致延迟很大的例子2 9 图3 18p c p 算法示意图2 9 图3 1 9 改进r o t 算法示意图3 l 图3 2 0 恢复算法实例求解示意图3 4 图4 1 转发延迟原理3 6 图4 2 延迟分析示意图3 8 图4 3 两层树转发策略分析示意图3 9 图4 4 三层树转发策略分析示意图4 1 图4 5 多层树转发策略分析示意图4 2 图4 6 转发策略应用实例4 4 图4 7t d l 对比图4 6 图4 8t d 2 对比图。4 6 图4 9t d 3 对比图4 7 图4 1 0 转发策略优化效果对比图4 7 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目： 廛翅星玺搔量! 延堡挝生盛：丝塑丞基芷。叁整筮筮堕塑究 学位论文作者签名：挺兰垂军 日期：莎护召年i1 月p 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名： 作者指导教师签名： 日期：7 彳移各年i 月o 日 日期：砌b 年月日 日期：d 们豸年1 1 月p 日 国防科学技术大学研究生院硕士学位论文 1 1 1i p 层组播面临的问题 第一章绪论 1 1 研究背景 随着i n t e r n e t 技术的快速发展，视频会议、视频点播等各种多媒体业务的出现， 网络用户的不断增加，传统的点到点的i p 单播通信方式由于其严重的带宽浪费和 低效率已经不能适应这些要求了，于是人们提出了组播的概念。组播是一种有效 的将数据报文从单点发送到多点的通信方式，组播源把数据包发送到特定组播组， 只有属于该组播组的主机才能接收到数据包。组播能节省网络资源，降低网络管 理要求，为数据的多点并发提供有效的途径。文献 1 】中提出了m 组播体系，在口 层增加对组播通信的支持，将具体的组播功能( 如组成员管理、组播报文路由) 实现于路由器。虽然相关研究进行了十多年，但由于技术和非技术因素的影响， 层组播并未大规模的部署 2 - 4 。 o ) i p 组播提供的是一种“尽力而为”的服务，缺乏对可靠性以及拥塞控制有 效的处理机制。 ( 2 ) 同时口组播打破了传统的基于“输入流 的计量机制，未考虑到i n t e m e t 服务提供商( i s p ) 的经济利益，因此他们不愿意在广域环境下提供对组播服务的 支持。 ( 3 ) i p 组播的实施涉及到对现有网络基础设施的更新，需要改变现有的网络底 层，阻碍了口组播的大规模应用。 1 1 2 应用层组播的提出 由于i p 组播面临上文中所提到的一些问题，近年来国内外一些研究人员开始 研究新的组播架构，试图绕开口组播的种种难题，提出了应用层组播【m 】。在应 用层实现组播的功能，不再依靠网络层路由器来实现。利用网络终端用户的资源， 屏蔽底层物理网络的拓扑结构，将参与组播的成员组织为一个逻辑覆盖网络 ( o v e r l a yn e t w o r k ) 7 ，引，在应用层实现组播服务。应用层组播直接在组成员之间建立 数据分发树，将组播相关功能组成员管理、报文复制、数据分发等实现于终端主 机p j ，在网络层仍采用口单播实现数据传输，取消对网络基础设施( 如组播路由 器) 的依赖。应用层组播的配置、部署毋需更改现有i n t e m e t 基础设施，可解决i p 组播中所面临的大多问题，近年来受到学术界的广泛关注。这种组播方法不需要 改变任何网络底层架构实现组播，为组播的大规模应用提供了一种新的途径。 第1 页 国防科学技术大学研究生院硕士学位论文 1 1 3 应用层组播与i p 单播、i p 组播对比 ( 1 ) 数据转发原理 应用层组播的基本思想是保持网络原有的简单、单播的转发模型，由端系统 实现组播转发功能。不考虑底层物理网络的拓扑细节，将组成员节点组织成一个 逻辑覆盖网络，并在应用层提供组播路由协议来构建和维护该网络，提供高效、 可靠的数据传输服务【3 】。应用层组播将组播树构造、维护，数据转发，组播组成员 管理等组播功能实现于终端主机，在底层主机之间通过i p 单播实现数据的传输。 终端主机通过查询组播路由表获得子节点的i p 地址，将数据打包转发，重复这个 过程，直到所有的子节点都收到数据。 i p 单播 e s 3es3 i p 组播应用层组播 物理连扣数据流向一+ 图1 1i p 单播、组播、应用层组播数据转发示例图 图1 1 中显示了i p 单播、i p 组播以及应用层组播转发数据的原理。图中 e s , ( i = 1 ，2 ，3 ，4 ) 为终端主机，墨，心为路由器。假设组播任务为硒向啦，硒， 哦分发数据。口单播中硒向避，鹕，e s 4 各分发一次数据。组播中，终 端硒向路由器墨发送数据包，墨向鹕和马转发数据包，坞再向西，硒转发 数据包，完成整个分发过程。应用层组播中，函以单播的方式先后向磷和哦 分发数据包，醚再向磷转发数据包。 从上面的组播过程中可以看出p 组播中同一数据包在物理链路上只传输一 次。而应用层组播中组播路径会重复经过同一条物理链路，上图中在硒一一墨， 啦一一坞这两条物理链路上都有同一数据包重复经过同一条底层链路。并且应用 层组播过程中需要端系统转发数据，这势必会增加节点之间的通信延迟。 ( 2 ) 数据路径质量度量 应用层组播建立在覆盖网络之上，主要通过强度、伸张度、节点度以及延迟 等指标来评估数据路径的质量。 强度( s t r e s s ) ：同一条物理链路中分发的相同数据包的数量。在单播、 i p 组播以及应用层组播中，图1 1 中硒到足的物理链路上的强度分别为3 、1 、2 。 伸张度( s t r e t c h ) ：应用层组播中从源节点到目的节点的延迟与i p 单播的 第2 页 国防科学技术大学研究生院硕士学位论文 延迟的比值。 节点度( d e g r e e ) ：组播树中与该节点相连的节点数。 延迟( d e l a y ) g 数据从源节点传送到目的节点所消耗的时间。 文献【1 0 】对三种通信模式作了仿真试验对比，其结果如下表1 1 所示。 表1 1i p 单播、口组播以及应用层组播对比 i p 单播口组播应用层组播 强度最大最小中 伸张度最小中 最大 最大延迟中最小最大 平均延迟中 最小最大 1 1 4 论文针对的问题 i p 组播虽然在数据路径质量上优于应用层组播，但由于其在可靠传输、流量 计量和可扩展性等方面存在一些不足，并且需要更改底层物理网络，因此难以大 规模的部署。应用层组播将组播相关功能实现于终端主机，能避开实现i p 组播所 面临的种种难题，便于部署。但同时也带来了一些新的问题需要解决。 ( 1 ) i p 组播中是路由器转发数据，而应用层组播中转发数据的中间节点是普通 的终端主机，处理能力和带宽有限，复制转发工作消耗的时间比较长。从表1 1 中 可以看出在三种通信模式中，应用层组播的最大延迟和平均延迟都是最大的。因 此对应用层组播，建立合适的组播树，对延迟进行优化很有必要。 ( 2 ) 由于应用层组播转发数据的节点大多是普通终端系统，而端系统不稳定， 容易失效或者退出组播组，导致组播树分裂，影响下行节点接收数据。所以有必 要研究维护应用层组播树的联通性，保证组播数据能分发到所有组播成员。同时 在组播过程中会有新的节点要求加入组播组，因此需要在满足约束的前提下为新 节点寻找合适的加入位置。 针对应用层组播延迟较大以及组播节点不稳定造成组播树分裂等问题，论文 以优化最大延迟为目标研究生成和维护组播树以及组播节点的转发策略。 1 2 论文研究内容与结构安排 1 2 1 论文研究内容 本文围绕优化应用层组播树的最大延迟，主要研究以下几方面的内容。 ( 1 ) 最小延迟组播树生成。优化应用层组播延迟，首要工作是构造一棵应用层 组播最小延迟树。在分析影响应用层组播树延迟关键因素的基础上，针对现有应 第3 页 国防科学技术大学研究生院硕士学位论文 用层组播树最小延迟模型的不足，提出一种新的问题模型。用遗传算法对模型进 行求解，并在m a t l a b 环境中对算法进行仿真分析，验证算法的有效性和模型的 合理性。 ( 2 ) 组播树的维护。组播树的动态维护主要包括两方面内容，组播树的分裂恢 复和新节点加入组播树。分析现有恢复算法的特点以及不足，借鉴现有恢复算法 的思想，以优化组播树延迟为目标恢复组播树。根据节点的状态差异，对不同的 节点提出不同的恢复策略。在组播服务过程中当有新的节点加入组播组时，以优 化延迟为目标为该节点选择合适的父节点。 ( 3 ) 应用层组播中节点的转发策略分析。分析组播节点转发过程中转发延迟的 原因，根据节点转发延迟的特点，研究合适的节点转发策略，优化应用层组播的 延迟。用实例说明策略的应用过程，并进行仿真试验，验证策略的有效性。 1 2 2 论文结构安排 本文结构安排如下： 第一章，绪论。介绍论文的研究背景，提出了本文的研究内容与主要工作。 第二章，相关研究。介绍应用层组播树的相关研究内容。 第三章，应用层组播最小延迟树生成与维护。分析影响应用层组播延迟的关 键因素，建立合理的应用层组播最小延迟树问题模型，并用遗传算法求解模型； 以优化组播树延迟为目标维护组播树，包括组播树的分裂恢复和新节点加入。 第四章，基于转发延迟的节点转发策略。在分析应用层组播中影响节点转发 延迟的因素的基础上，研究节点转发数据的策略，优化组播树的延迟。 第五章，结论与展望。总结全文并提出进一步的研究内容。 第4 页 国防科学技术大学研究生院硕士学位论文 第二章相关研究 本章主要介绍应用层组播树的相关研究。第一节介绍应用层组播协议以及几 种典型的应用层组播方案；第二节介绍组播树模型及其相应的求解算法：最后对 本章进行小结。 2 1 应用层组播协议 由于技术和非技术原因，m 组播未能大规模的部署。作为m 组播的替代技术， 应用层组播应运而生。为实现应用层组播服务，组播协议需要提供可靠的组管理 算法，并生成有效的数据组播树。 2 1 1 应用层组播协议分类 根据不同的分类标准，应用层组播协议有多种分类方法【l l 1 2 1 。 ( 1 ) 根据协议构造方法，可以分为集中式和分布式两大类。 集中式算法有一个全局会话控制点，通过会话控制节点管理所有成员的加入、 离开，构建并维护组播树，优化覆盖网络等【1 2 1 。集中式算法数据拓扑结构的计算 是集中进行的，树的所有节点的信息首先汇集到会话控制点，然后由会话控制点 计算一个最优的整网拓扑结构，最后由会话控制点将计算结果通知所有节点。由 于采用集中式方法计算路由，使得计算出的组播树是全局最优的。组播节点为维 护全局状态信息必须频繁更新以适应网络拓扑动态变化，对于大规模网络，通信 开销和控制开销较大。 分布式算法中没有集中会话控制点。节点维护局部信息，并完成组成员的管理 以及数据拓扑控制。与集中式算法不同，分布式路由算法中每个节点仅维护本地 的局部状态信息，路径通过分布式计算获得，因此路由建立的时间较短，。避免了 集中式算法中源节点计算量大的缺点，算法的扩展性较好。但由于没有详细的链 路状态信息和网络拓扑，很难设计有效的解决n p 完全问题的分布式启发算法。并 且当不同节点维持的网络状态不一致时，路由计算容易产生环路，导致路由算法 失败。 ( 2 ) 根据构造控制拓扑和数据拓扑的先后顺序可以分为树优先、网优先和隐式 三类【1 2 】。 基于树优先的组播协议先根据节点局部信息构造一棵组播树，然后每个组播节 点根据一定算法发现一些在组播树中并不是邻接节点的其他节点，并和这些节点 保持控制连接，进而建立控制拓扑。基于网优先的方法首先将组播组成员组织为 第5 页 国防科学技术大学研究生院硕士学位论文 一个连通的覆盖网络，然后通过路由算法在网格上建立组播树。隐式法中定义控 制拓扑和数据拓扑没有严格的先后顺序，成员之间也没有额外交互，根据控制拓 扑建立方法隐式法又可以分为层次型、p 2 p 路由等几种类型。 2 1 2 几种典型的应用层组播方案 上文简单介绍了应用层组播协议的分类，不同的分类对应不同的应用层组播方 案。下面介绍几种应用层组播方案。 ( 1 ) a l m i a l m i l l 3 】是一种集中式应用层组播方案，每个会话包括一个会话控制器和若干 个会话成员。会话控制器控制覆盖网络的全局信息，负责组成员的管理和组播树 的构造和维护。为降低控制负载，a l m i 协议采取基于局部信息的优化算法，对每 个节点所监视的邻居节点数进行限制。为保证协议效率，会话控制器根据所有组 成员反馈的最新链路信息定期重新计算并生成组播树。可以根据不同的性能要求 生成不同的组播树，如带宽、延迟等。同时控制器根据成员的监测报告的信息对 组播树进行优化。 ( 2 ) y o i d y o i d l 4 是一种树优先的应用层组播协议，由a c i 研究中心在2 0 0 0 年提出，为 应用层组播的实现提供了一个完整的框架，包括了应用层组播之上的可靠、安全、 拥塞控制等机制，将主机组织成网状网和共享的组播转发树。y o i d 协议包括拓扑 管理协议y m t p ，传输控制协议y d p ，身份识别协议y i d p 等。 ( 3 ) e s m e s m 3 , 1 4 j 是卡耐基梅隆大学研制的应用层组播系统，n a r a d a 是e s m 的应用层 组网协议，定义了一个汇聚点r p ( r e n d e z v o u sp o i n t ) 。新成员要加入组播组首先 需要通过r p 获取成员信息列表，然后随机选择成员分支，并作为这些成员的邻接 节点加入网格。加入后，新成员与其他成员交换更新信息。控制拓扑中，组成员 定期与网格中的邻接节点交换信息，及时检测失败节点，维护控制拓扑的连通性。 n a r a d a 采用路由算法在m e s h 上为各个发送源分别建立数据分发树。为提高数据传 输质量，由每个节点周期性探测与其他成员的相互位置关系，并根据探测结果决 定是否添加新链路，从而优化m e s h 拓扑。2 0 0 1 年，在因特网中实际运行了基于 e s m 的视频会议，验证了n a r a d a 协议可以在动态的、异构的因特网中支持较小规 模的视频应用。 ( 4 ) n i c e n i c e 5 】是一种分层的应用层组播协议，具有很好的可扩展性。将组播组成员划 分为不同的层次，由下向上对每一层编号。每一层又被分为若干个具有一定大小 第6 页 国防科学技术大学研究生院硕士学位论文 限制( 一般介于七一3 k 一1 之间，七为配置常数) 的簇，并选取簇中一点作为簇头， 厶层的全部簇头构成厶+ 层。协议根据簇的拓扑结构选择中心节点作为簇头，簇头 到其他所有节点的距离都比较小。下图是3 层结构的示意图，厶层的簇头m 。、屹，、 鸭。组成了厶层，厶层的簇头构成了厶层。根据层次结构定义控制拓扑和数据拓 扑。控制拓扑中，每个层中簇的成员相互之间相互发送周期性的更新消息，可以 快速获得对等成员的变化信息。 图2 1n i c e 示意图 n i c e 协议中，采用分层路由算法直接在层次拓扑上建立以自己为根节点的组 播树。在分层路由中，每个节点保存有经过聚合的全局信息，此信息包括此节点 所在组的详细状态信息和其他组的聚合信息。根据这些信息，路由计算按层次采 用至顶向下、逐层展开的方式进行。 2 , 2 应用层组播树 应用层组播在端系统之间构造组播树，针对其可靠性和通信效率不高的问题， 应用层组播研究的一个主要目标是如何构建一棵高效的应用层组播树。组播路由 算法根据网络拓扑结构，建立覆盖网络的模型，在此基础上建立一棵组播树，并 优化目标函数，不同的应用具有不同的目标函数。 2 2 1 覆盖网络的模型 参与应用层组播的主机之间通过i p 单播实现数据的传输，任意节点之间都存 在逻辑链路相连，网络中每个节点之间都是相邻的，因此能将覆盖网络抽象为无 向的完全图表示。一个图g 是指一个有序三元组( 矿( g ) ，e ( g ) ，九) ，其中矿( g ) 是非 第7 页 国防科学技术大学研冗生院硕士学位论文 空的顶点集，e ( g ) 是不与矿( g ) 相交的边集，靠是关联函数，它使g 的每条边对 应于g 的无序顶点对( 不必相异) f 1 5 1 。在不混淆的情况下有时记v = y ( g ) ， e = e ( g ) 。点集v = v l ，v 2 ， ，边集e = e l , e 2 ，) ，边集e 中的元素e k 与y 中的某两个元素 m ，v ，) 对应，记缸= v i ，或者e k = v ，q 。称气与m ，v ，相关联，m ，1 ，为 e k 的端点，且m ，是相邻的。图g 也可以记为g = ( y ，e ) 。图g 中顶点1 ，的度( 或 次) 指g 中与，关联的边的数目，记为d e g g ( 1 ，) i s 】。对g 的每一条边e ，赋一个实 数“p ) ，称为e 的权，g 连同它边上的权称为赋权图。 覆盖网络可以用赋权完全图g = ( 矿，e ) 表示，v 是节点的集合表示网络中的主 机或者路由器，e 是边的集合，表示节点间的逻辑连接。对于e e 具有权值c ( e ) ， c ( e ) r + ，c ( e ) 表示链路的通信代价；对于1 ，v ，其度约束值为d e g 咖, ( v ) 表示节 点v 能连接的节点数，一般为一个正整数。覆盖网络可以描述为( g ，c ，d e g 一) ，其 中g = ( y ，e ) ，v e e ，3 c ( e ) r + ，v v v ，3 d e g 。, ( v ) z + 。 2 2 2 组播树模型及其求解算法 根据优化目标不同，可以建立不伺的组播树问题模型。 2 2 2 1s t e i n e r 树和最小生成树 ( i ) l h - 题描述 s t e i n e r 树问题是指在一个图中连接给定目的节点的最小树问题。在构造组播 路由树时，常用组播树总费用对组播树的优劣进行度量。组播树的总费用是指树 中所有链路费用的总和，链路的费用是一个广义概念，可以是链路的通信代价， 带宽等。组播路由算法将建立一棵以组播源为根、覆盖所有组播目的节点，使树 的总代价最小的问题归结为图论中的s t e i n e r 树问题【1 6 1 。路由算法中的节点还需要 满足一定的约束条件，如节点的度约束和节点的延迟约束，这类问题称为带约束 的s t e i n e r 树问题。 对于组播源，。，带约束s t e i n e r 树问题描述为： r a i n c ( e ) ，fd e g ( v ) d e g , 。( v ) “1 沈伽( 叱) 如( v ) 比如( 吧) 表示节点v 与根节点屹之间的延迟，d e 虬( v ) 表示节点v 能容忍的 最大延迟。 ( 2 ) 求解算法 第8 页 国防科学技术大学研究生院硕士学位论文 s t e i n e r 树问题已经被证明了是n p c o m p l e t e 问题【l7 1 。有许多精确求解算法和 启发式算法可以求解，但精确算法的计算量随节点数呈指数级增长。所以现实而 合理的办法是设计快速启发式算法求解。目前有很多的启发式算法用来解决 s t e i n e r 树问题n h 。 求解无约束的s t e i n e r 树问题的方法中k m b 墙】算法最具代表性。k l v i b 算法 主要借鉴p r i m 算法的思想构造一个完全距离图。k l v i b 算法步骤为： s t e p l ：在原完全图g 上构造一个只包含源节点和目的节点的完全距离图g ，完 全距离图指任意两个节点间的最短路径连接； s t e p 2 ：用p r i m 算法在图g 求最小生成树t ； s t e p 3 ：将丁中的边用g 中的最短路径，得到连通图g ”； s t e p 4 ：再用p r i m 算法求g “的最小生成树t ”； s t e p 5 ：删除丁”中非目的节点的叶子节点，直到所有叶子节点都为目的节点。 求解带约束的s t e i n e r 树问题的算法有k p p 2 0 1 ，b s m a 2 1 】算法等。k p p 算法 是求解具有延时约束的s t e i n e r 树问题的典型算法，借鉴了k l v i b 算法的思想。k p p 算法描述为： s t e p l ：构造包含源节点和目的节点的完全图g ，g 中的边为原图中两节点之 间满足延时约束且费用最小的路径； s t e p 2 ：使用p r i m 算法从完全图g 生成一棵满足延时约束的生成树r 。 当s t e i n e r 树中的目的节点包括图g 中的所有节点时，s t e i n e r 树问题就转化为 最小生成树问题。求解最小生成树问题最具有代表性的是p r i m 算法。 2 2 2 2 最小延迟组播树 ( 1 ) p l 题描述 s t e i n e r 树主要是从整个树代价最小的角度出发去优化组播树。应用层组播一个 主要的问题是高延迟，这主要是由两方面的原因引起的1 2 2 。首先应用层组播与物 理层独立，并不是从物理层的角度去优化其通信模型。其次应用层组播通过终端 转发数据也导致了高延迟。而实时系统要求将信息延迟限制在一个很小的范围内， 在实际应用中不将总的通信代价作为最重要的目标，更重要的是任意两点之间的 通信延迟。目前已有很多与延迟相关的组播树的论文【2 3 - 2 7 】。其求解思路大多采用 启发式算法求近似解。根据是否有确定的组播源，最小延迟组播树可以分为最小 半径树和最小直径树。 有确定组播源时，构建一棵以组播源v 为根节点有度约束的最小半径树。 组播树的延迟半径是指组播树中任意节点到根节点的最大延迟。 其数学模型为： 第9 页 国防科学技术大学研究生院硕士学位论文 m i n 尺( 丁) ir ( 丁) = m 努比枷( k u ) j j ” 【d e g ( v ) d e g 一“) 丁表示生成树，足( 丁) 表示组播树半径，矿表示所有组播节点的集合。 无确定组播源时，如需要进行视频会议时，任意点都可能是组播源，这时 就需要构建一棵延迟直径最小的组播树阎。组播树的延迟直径指组播树中任意两 点间延迟的最大值。最小直径树问题可以描述为，给定一个无向图，寻找一个覆 盖所有节点满足度约束的生成树，并且直径最小。其数学模型为： r a i nd ( 丁) d ( 丁) 2 黝如伽( v 巧) ，v ，e r 。 d e g ( v ) d e g 嘣( v f ) d e g ( v j ) d e g 。麒( u ) d ( 丁) 表示生成树丁的直径。 根据对问题模型描述的不同，最小延迟树问题主要有m d m l 2 5 1 、m d d l 2 3 1 和 d c m d 2 6 1 模型。m d m 模型中节点和边都带权值，但未考虑节点的度约束；m d d l 模型是度约束边带权，但节点不带权的问题模型。文献【2 6 】在m d m 和m d d l 模 型的基础上提出了更合理问题模型，同时考虑边权值c ( e ) 、节点权值c ( v ) 和节点度 约束d e g 一( v ) ，并且节点的权值和节点的度之间存在函数关系c ( v ) = f ( d e g ( v ) ) 。本 文将在第三章中详细分析d c m d 模型。 ( 2 ) 求解算法 对于m d m 模型，文献 2 5 】提出了基于最大延时路径的贪婪算法h m d m 。 该算法先考虑延迟较大的节点，按照延迟的从大到小将节点排序。算法的主要步 骤： s t e p l ：初始化t = ，。) ； s t e p 2 ：计算所有不在树丁中的节点到根节点v 。的最短路径； s t e p 3 ：选择其中最大的节点，并将其路径上所有的节点加入树丁中； s t e p 4 ：重复s t e p 2 , s t e p 3 直到所有节点都纳入组播树中。 可以看出h m d m 算法并未考虑节点的度约束。 对于m d d l 问题，文献 2 3 】提出了c t 算法用于求解。c t 算法类似于p r i m 算法，先处理延迟较小的节点，但对相关节点的度没有限制。 对于d c m d 模型，文献【2 6 】提出了基于度的算法和基于延迟的d c m d h 算 法。基于度的算法描述为： 第l o 页 国防科学技术大学研究生院硕士学位论文 s t e p l ：初始化t = 屹 ； s t e p 2 ：计算所有不在树丁中的节点到根节点v 的最短路径，并选择其中最短的 k 个节点： s t e p 3 ：从七个节点中选取节点度约束值最大的，并且该节点到根节点的路径上 的所有节点满足度约束值，将其加入到树r 中； s t e p 4 ：重复s t e p 2 , s t e p 3 步直到所有节点都纳入组播树r 中。 d c m d h 算法将在第三章中介绍。 对于最小直径树，文献【2 7 】中证明了带度约束的最小直径生成树问题是n p c 问题，并且提出一种贪婪算法解决这个问题。文献【2 2 】提出了一种启发式的应用层 组播最小直径树生成算法，但其并未考虑节点的度约束以及结点的转发延迟的影 响。文献【2 9 】在考虑节点度约束的情况下，提出了一种启发式的遗传算法求解应用 层组播直径树，但也未考虑节点的权值。 2 2 2 3 负载均衡 当s t e i n e r 树和最小延迟树在优化通信代价和延迟时，未考虑节点的负载均衡， 容易造成系统利用率低和会话拒绝率高。文献 3 0 提出了构造负载均衡的应用层组 播树，优化节点的负载。其数学模型如下： m i n m a x ( d e g 一( 力一d e g ( v ) ) 。id e g ( v ) d e g m 。( v ) 【d e c a y ( m ) 5d e 切，咄( v ) 2 3 本章小结 本章主要介绍了应用层组播树的相关研究现状。首先介绍了应用层组播协议 的分类标准和几种常见的应用层组播方案；接着介绍了应用层组播覆盖网络的模 型，然后介绍了应用层组播树模型分类方法及其相应求解算法，并分析了算法存 在的一些不足。 第1 1 页 国防科学技术大学研究生院硕士学位论文 第三章应用层组播最小延迟树生成与维护 本章主要研究应用层组播树的生成和维护。第一节在介绍应用层组播最小延 迟树d c m d 模型的基础上，分析其存在问题，然后提出一个新的应用层组播最小 延迟树模型d n m d ；第二节用遗传算法求解该模型，并进行仿真试验；第三节研 究组播树的动态维护，在分析现有分裂恢复算法的基础上提出了适合最小延迟树 恢复的算法，并对实例进行求解；最后总结全章。 3 1 组播树生成问题分析 应用层组播是建立在虚拟覆盖网上的，虚拟覆盖网络可以用无向的完全图表 示。根据不同的应用目标，人们建立了不同的问题模型，在此基础上设计出了不 同的算法。主要有以下几个方面的目标，一是优化端对端之间的延迟，二是使总 的通信代价最小，三是负载均衡，即有效的使用网络资源。求解应用层组播树主 要包括两方面的工作，一是将应用层组播的覆盖网络映射成图，二是根据应用需 求，在抽象图的基础上建立问题模型并用合适的算法进行求解。 3 1 1d c m d 模型中存在的问题 ( 1 ) d c m d l 2 6 1 模型 目前大多数研究优化组播延迟的文献中都只考虑了边的权值 2 2 - 2 4 ，2 9 1 ，未考虑 节点的权值，即忽略了节点的处理时间。应用层组播在底层靠i p 单播转发实现， 且应用层组播中的中间节点大多是普通的主机，