《应用层组播的最小延迟生成树算法(.doc》由会员分享，可在线阅读，更多相关《应用层组播的最小延迟生成树算法(.doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、曹佳 等:应用层组播的最小延迟生成树算法1773应用层组播的最小延迟生成树算法*Supported by the National High-Tech Research and Development Plan of China under Grant No.2002AA742052 (国家高技术研究发展计划(863)作者简介: 曹佳(1978),女,新疆库尔勒人,博士生,主要研究领域为组播路由;鲁士文(1944),男,研究员,博士生导师,主要研究领域为计算机网络协议.曹 佳1,2+, 鲁士文11(中国科学院 计算技术研究所,北京 100080)2(中国科学院 研究生院,北京 100049)A
2、 Minimum Delay Spanning Tree Algorithm for the Application-Layer MulticastCAO Jia1,2+, LU Shi-Wen11(Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100080, China)2(Graduate School, The Chinese Academy of Sciences, Beijing 100049, China)+ Corresponding author: Phn: +86-10-
3、62565533 ext 8837, E-mail: jiacao, Received 2004-07-16; Accepted 2005-03-11Cao J, Lu SW. A minimum delay spanning tree algorithm for the application-layer multicast. Journal of Software, 2005,16(10):1766-1773. DOI: 10.1360/jos161766Abstract:Real time transmission, which is delay sensitive, is an imp
4、ortant aspect of application-layer multicast. It is crucial to build an efficient multicast tree to guarantee the lower delay. This research is focused on the algorithms of the minimum-delay spanning tree for the application-layer multicast. Firstly, it is stated that the total delay is affected by
5、communication delay, processing delay and the degree of nodes. Then the network is modeled into the node-and-edge-weighted directed graph with the limited degree of nodes. In this model the problem is shown to be NP-hard. Therefore, two kinds of heuristic algorithms are proposed, which are based on
6、the maximum degree and the maximal length path respectively. Finally, the simulation demonstrates that the proposed algorithms are valid.Key words:application-layer multicast; minimum delay spanning tree; NP-hard; real time transmission摘 要:实时传输是应用层组播技术的一个主要应用领域,对网络延迟有严格的限制.保证低延迟组播成功的关键在于构建高效的应用层组播树,
7、研究构建最小延迟应用层组播树的算法.首先分析影响延迟的3个因素:链路的传输时间、结点的发送/转发时间和结点度,然后把求解应用层组播树的问题抽象成对边和点都带权的有向图求解“度约束最小延迟生成树”的问题,同时证明这个问题属于NP-hard,并且提出了两类启发式近似算法:基于度的算法和基于最大延迟路径的算法.最后通过模拟实验说明了所提出算法的有效性.关键词:应用层组播;最小延迟生成树;NP-hard;实时传输中图法分类号:TP393文献标识码: A组播是一种一对多的通信方式,常用于视频会议、内容发布、远程教学等网络应用.IP组播是一种较早的组播实现机制,虽然具有较高的传输效率,但是对底层的网络设备
8、有支持组播协议的要求,所以在现阶段不能在广大范围内普及.为此,人们提出了应用层组播,希望它既能继承组播的传输特性,例如节约带宽、传输快捷,也可以脱离对底层基础网络提升的依赖,在近期就可以实现较大范围的组播通信.因此,应用层组播成为倍受瞩目的组播实现机制.人们已经研究了多种应用层组播协议,如Narada,NICE,Yoid,ALMI和Scribe等4.无论何种协议,“保证组播参与者尽快收到组播包”一直是应用层组播的主要追求目标,它对实时传输有重要的意义.解决这个问题的关键在于构建高效的应用层组播树,主要涉及两个方面: 如何将应用层组播的覆盖网络映射成图,即如何抽象问题模型; 如何求解映射图的最小
9、延迟生成树.目前求解应用层组播树算法的主要差异是人们根据不同的应用需求提出了不同的问题模型1-6,见表1,然后设计出不同的求解算法.这些问题大多属于NP-complete,不存在多项式时间解.文献2-6将覆盖网络抽象成一个边带权、结点度受限的图,未考虑结点的权值,也就是说,忽略了中间结点的处理时间.然而,现实中应用层组播的中间结点大多是普通主机,它们不具备线速转发的能力,因此在抽象问题模型时不能忽略转发处理时间. MDM模型1相对要完善一些,它将覆盖网络抽象成一个结点和边都带权的图,但是没有约束结点的度,这是因为文献1的作者认为通过他们设计的算法(H-MDM算法)求得的生成树本身就具有较小的结
10、点度,同时也具有较低的树延迟.但是,在本文的第2.2节中,我们将通过一个反例证明这个假设是不合理的.Table 1 Delay-Constrained spanning tree problems in application layer multicast表1 与延迟相关的带约束生成树问题TargetProblemAverage delay minimumDelay-Constrained minimum spanning tree problem (DCM)4Minimum average-latency degree-bounded directed spanning tree prob
11、lem3Minimum delayMinimum-Diameter degree-limited spanning tree problem (MDDL)2Minimum delay multicast problem (MDM)1Delay-Constrained shortest path tree problem6Constrained delayDelay-Constrained minimum spanning tree problem (DCMST)5针对这些问题,我们抽象出一个新的更全面的求解应用层组播树的问题模型DCMD(degree- constrained,minimum
12、delay spanning tree for node-and-edge-weighted directed graph).DCMD模型同时考虑了边权、点权和结点度约束3方面的问题.另外,本文针对DCMD模型提出了一个最小延迟应用层组播树的生成算法,通过这个生成树来发布信息,可以保证所有的组播参与者尽快地收到组播包.由于DCMD是一个新的问题模型,到目前为止,关于同时涉及度约束和结点边均带权3个因素的最小延迟生成树的研究很少,尤其是针对结点的权值随着结点度值的变化而变化的情况的相关研究更是少见.因此,我们分别调研了两个应用层组播树的问题模型MDM问题(结点和边均带权值的最小延迟生成树问题)和
13、MDDL问题(度约束边带权最小延迟生成树问题)的求解算法.对于MDM问题,文献1提出了一种基于最大延迟路径的贪婪算法的H-MDM算法.该算法首先考虑接收延迟最大的结点,然后再逐步处理较“近”的结点.其中所有结点对之间的最短路径的距离采用Floyd-Warshall来计算.我们将在第2.2节对H-MDM算法作详细分析.对于MDDL问题,文献2提出了CT算法,类似于Prim方法,先处理接收延迟最小的结点,对相关结点的度没有限定值;文献10又分别提出分割式构造算法和极网格构造算法.然而,这些算法解决的MDM问题和MDDL问题都没有同时考虑度约束、结点和边均带权3个因素,而这3个因素都直接影响着应用层
14、组播树的树延迟,所以都不可忽略.关于最小延迟生成树,本文所做的主要工作是对这些算法进行修改,从而解决DCMD问题.本文第1节定义DCMD问题,证明DCMD属于NP-hard.第2节给出两类启发式近似算法:基于度的算法和基于最大延迟路径的算法.第3节通过模拟实验评估算法的有效性.1 问题模型应用组播通过覆盖机制在应用层上实现组播功能,参与者首先在应用层上构建逻辑组播树,然后通过底层的单播IP网络进行点到点的实际互连.在应用层组播传输数据包的过程中,组播源准备数据,查询组播路由表,获得孩子的单播IP地址,再分别打包、转发.数据包通过相应的单播路径传输给孩子,孩子接收数据包后查询路由表,再分别打包、
15、转发.这一过程重复进行,直到所有结点都收到数据包为止.显然,中间结点需要完成数据的复制转发工作.如前所述,由于这些结点通常是普通的主机,不能进行线速转发, 所以复制转发工作消耗的时间较大.鉴于此,计算应用层组播延迟(简称“树延迟”,记做D)不能忽略结点的转发处理时间(下文将中间结点的转发处理时间和源结点的发送时间统称为“发送延迟”,记做Se).考虑到这个因素,我们需要把树延迟表示成:(1)其中,P表示从源到叶结点的路径,传输延迟Tri表示从源结点到结点i之间路径的传输延迟.除了发送延迟和传输延迟以外,树延迟还受拓扑结构的影响.拓扑结构与结点度有直接关系,结点度越大,树的深度越小,树延迟也越小.
16、在底层是采用单播传输机制的条件下,某个结点的度大,意味着这个结点需要多次转发同一个数据包,对应的发送延迟越长,导致树延迟增大.由此可见,通过调整结点度来均衡传输延迟和发送延迟这两个参量,可以减小树延迟.因此,影响树延迟有3个因素:传输延迟、发送延迟和结点度.需要说明的是,之所以要适当约束结点的度,除了考虑到可以降低树延迟以外,还有两个原因.一是如果某个主机结点的下行用户数目太多,那么它的工作负载会相当重,所以约束结点的出度可以降低这个结点的工作量;二是从网络传输环境来看,主机的上行带宽受限也要求约束结点的度.应用层组播的覆盖网络可以被映射成图论中的图,可以将求解最小延迟应用层组播树问题定义如下
17、:定义1(DCMD问题).已知:一个图.结点,具有权值,出度与满足,f(x)表示权值函数;结点v具有最大度约束,v在G中的出度满足;边带权.求解:最小延迟生成树T(V,E),并且在树T中结点的度degTv满足.DCMD问题可归约到具有NP-complete难度的电话广播TB问题8.TB问题描述这样一类问题:给定一个图G(V,E),一个处理机和一个处理机集合;规定每个时间段允许每个处理机结点选择一个邻居结点,并发送一个消息.电话组播TM问题要求计算出一个最快的转发方案,使得从s向T的结点发送消息的时间最短.当T=V时,这个问题就成为电话广播TB问题.定理1. DCMD问题属于NP-hard.证明
18、:已知,为了证明,只需证明.对于任意实例通过下面这个多项式时间变换可以得到实例IDCMD:(1) ;(2) .从而得到实例I,然后求解I得到最小延迟生成树T .显然,这个T 就是TB的最小延迟生成树T,因此解决DCMD的算法可以也可以解决TB问题.故得证,.2 算法描述为了下面叙述方便,我们先描述几个术语.设G(V,E)是连通图,待求树T(V,E).初始状态时,T=,即VT=,表示T相对于图G的补集,;生成树的过程是将中的每个结点以及相关的一条边逐一纳入到T的过程.这样T与之间存在一些边,边的一个端结点属于T,另一个端结点属于,我们称这些边组成的集合为“反圈”.设表示反圈中的边,两个端结点分别
19、是,.我们称结点i的集合为“反圈在T中的点集合”,记作I;结点j的集合为“反圈在中的点集合”,记作J.生成树的过程就是从J中选择一个结点u,从反圈中选择一条相关边,直到所有的结点都纳入到T的过程.求解NP-hard类问题通常有两种算法:确切算法和近似算法.确切算法基于枚举,时间复杂度呈指数特性,不适合于具体的应用.近似算法为了获得多项式时间的求解速度,从一定程度上降低了解的准确度,但是因为比较快,得到的结果不是很差,所以较为实用.我们为DCMD问题设计了两种启发式近似算法:基于度的算法和基于最大延迟路径的算法.2.1 基于度的算法2.1.1 基于最大度的算法该算法的核心思想是尽量选择度最大的结
20、点.因为只考虑结点的度,所以求得的生成树比较粗壮.算法1. 基于最大度的算法.输入:图G(V,E),图中每个结点的,边权值,源结点r,权值函数f(x).输出:树T.初始化待求树T=,将源结点r纳入到树T中.(1) 从J中选择一个dmax值最大的结点u;(2) 从I中选择结点v,degTv满足degTvdmaxv,且边e(v,u)存在,边权值pv,u最小;(3) 将结点u和边(v,u)纳入到树T中;(4) 修改集合I和J,同步反圈.重复(1)(4),直到所有的结点都纳入到T中.算法1逐一处理每个结点,每次最多进行|V|次比较,时间复杂度为.设任意两结点的距离dis(u,v)满足0g+f(dmin
21、) depthopt,其中表示度约束树的最小深度;算法1得到的生成树T的最大延迟满足llh+ f(dmax)depthopt,由此推出,所以的近似比满足.通常,权值函数f(x)是线性函数,表示结点的度越大,需要的转发延迟越长,因此的近似比满足.2.1.2 基于度和最近距离的算法在算法1中选定结点后,才局部考虑边权,不能得到最优解.为此做如下改进:首先选择k个到源的路径最短的点集合K,然后从中选dmax值最大的结点加入到T中.参数k在这里作为权衡因子.当k较大时,侧重于选择结点度较大的结点;当k较小时,侧重选择边点权值较小的结点.算法2既考虑权值,也考虑结点的度约束,其解比算法1更优.详细描述如
22、下:算法2. 基于度和最近距离的算法.输入:图G(V,E),图中每个结点的dmax,边权值,源结点r,权值函数f(x).输出:树T.初始化待求树T=,将源结点r纳入到树T中.(1) 从J中选择k个距离源最近的结点ui,放入集合K;(2) 从K中选择一个dmax值最大的结点u;(3) 从I中选择结点v,degTv满足degTvdmaxv,且边e(v,u)存在,边权值pv,u最小;(4) 将结点u和边(v,u)纳入到树T中;(5) 修改集合I和J,同步反圈;根据cx=f(degx)修改结点u和v的权值.重复(1)(5),直到所有的结点都纳入到T中.算法2逐一处理每个结点,每次最多进行次比较,时间复
23、杂度为O(|V|2).2.2 基于最大延迟路径的算法由于基于最大延迟路径的DCMD-H(DCMD-heuristic)算法起源于H-MDM (heuristic-MDM)算法,因此,本节首先介绍用来解决MDM问题的H-MDM算法1;然后列举一个反例说明在某些情况下算法H-MDM不适合用来构建应用层组播树;最后我们改进H-MDM算法,设计了一种用于解决DCMD问题的DCMD-H算法.在H-MDM算法中,结点的“接收延迟”表示从源向这个结点发送一个数据包的延迟,结点的“延迟路径”表示从源到这个结点的最短路径,该路径的长度(通常是“延迟”)叫做延迟路径长度.初始状态下,将源r纳入到空树T中,然后再按
24、照下列步骤依次进行.H-MDM算法.(1) 计算中每个结点的最小接收延迟;(2) 选择其中具有最大接收延迟的结点;(3) 将这一结点及其延迟路径加到T中.重复(1)(3),直到所有的结点都纳入到T中.按照H-MDM算法,为图1(a)所示的覆盖图构建生成树,可能导致一些结点的度很大,如图1(b)所示.其中结点a到结点bi的距离为,i=1,2,3,m,p(a)表示结点a转发一个包的发送处理时间,结点bi到结点bj的距离为e,e是一个足够小的正数.结点a在生成树中的度maL/p(a).当L足够大时,ma将很大,此时a的转发工作量很大,可能不能及时接收数据,造成数据丢失.所以,H-MDM算法不能直接用
25、来解决DCMD问题.(a) The input graph(a) 输入图ab1bmbib2ab1bmbib2(b) The H-MDM tree(b) HMDM树Fig.1 Example that node degree is very large in the H-MDM tree图1 H-MDM算法导致结点度很大的例子为此,我们对算法H-MDM做了改进,得到算法DCMD-H.其基本思路是,对于算法H-MDM的第2步,不仅考虑延迟路径长度,还考虑相关结点的度是否超出限制,如果超出就选择次长路径,直到找到合适的结点为止.显然, DCMD-H算法考虑了约束结点度的问题.约束结点度会引起度约束生
26、成树问题,这是一个NP-complete问题7.我们不直接解决这个问题,而是利用应用层组播中主机结点的任意互连性,采用了回避策略.当算法失效时,需要由没有被纳入到树中的结点提供额外的连接信息来保证算法的两次可运行.我们对320个中小规模的图采用这种策略后发现,只有3例失效,需要两次信息补充,其余的失效情况只需一次信息补充,因此这个策略可以用于实际应用.基于最大延迟路径的算法关键是求解延迟路径,为此我们引出如下定理.定理2. 任意延迟路径l上的任意结点i的延迟路径li也必定属于l.证明:设l表示从源结点r到结点g的延迟路径lrg,设路径,xl,表示路径lrx的长度.设结点x的延迟路径,表示结点x
27、的延迟路径的长度.由延迟路径的定义可知,也就是说, ,这个与“lrg是r到g的延迟路径”的已知条件矛盾.因此,定理得证.根据定理2容易推出每个结点的延迟路径必定先经过已经纳入树的结点和边,然后再经过还未纳入到树的结点和边,这就为求解结点的延迟路径的长度提供了一个简化途径.可以先记录所有的iI的延迟路径长度lri,然后计算结点的延迟路径,其中iI.下面给出DCMD-H算法的描述.算法3. 基于最大延迟路径的算法.输入:图G(V,E),每个结点的dmax,边权值,源结点r,权值函数f(x)=w0+xw.输出:树T.初始化待求树T=,将源结点r纳入到树T中.(1) 修改每条边的权值p(u,v)=p(
28、u,v)+w0;(2) 计算每对结点的延迟路径Path(u,v),uV,vV和延迟路径长度l(u,v);(3) while (|V|T|) doI. 从中选取一个结点u,满足源r到u的l(r,u)最大的条件;v为这条路径在T中的最后经过的结点,显然vI;同时,选取的u必须保证degvdmaxv,否则重新选取l(r,u)次小的结点u;II. 将延迟路径(r,u)中不在T中的边和点添加到T中;III. 修改v在T中的结点的度degTv+1和结点权值cTv.采用单源最短距离算法Dijkstra来求解结点对之间的延迟路径及长度,时间复杂度为O(|V|3);While循环最多执行|V|次,需要重新计算结
29、点延迟路径,时间复杂度为O(|V|4).故算法3的时间复杂度为O(|V|4).总体来说,DCMD-H算法的基本思想起源于H-MDM算法,二者都基于最大延迟路径的贪婪算法,首先保证距离最“远”的结点的延迟,然后再逐步处理距离较“近”的结点.它们的不同之处在于DCMD-H算法用来解决DCMD问题模型,而H-MDM算法用来解决MDM问题模型.第1节的分析指出,由于性能方面的原因,必须要约束应用层组播的主机结点的出度.虽然算法H-MDM的设计者认为,通过算法H-MDM求得的生成树本身不会出现度很大的结点,同时还保证了较低的树延迟,但是,本节的反例证明了在某些特殊情况下H-MDM求得的生成树的某些结点度
30、可能很大,也就是说,这个假设不合理.因此,当对应用层组播进行数学抽象时,需要明确地约束结点的度,所以DCMD-H算法更适合用来构建应用层组播树.3 模拟实验本节模拟分析对于中小规模网络,我们提出的3种算法的平均优化情况.在现实中,网络活动地点往往围绕着不同的城市,呈“簇”状分布,城市的分布呈随机态.因此,我们这样来描述应用层组播的用户分布:各个“簇”呈随机分布,每个簇的用户相对自己所在簇的中心点呈正态分布.故在模拟网络中,分别采用随机拓扑和正态拓扑两种结构.我们直接用GT-ITM生成随机网络,scale=100,n=|V|,=结点对之间的互连概率p,表示|V|个结点随机分布在100100的平面
31、上.正态拓扑表示结点的x,y坐标分布呈正态性,xN(50,50),yN(50,50),且0x,y100.因为GT-ITM不支持正态拓扑,所以我们自己构建了新的拓扑生成器.利用当l20时泊松分布近似于正态分布的性质,通过泊松数列生成算法Knuth来改进GT-ITM,从而生成仿正态拓扑网络.然后为每个结点随机生成一个结点的最大度约束值1dmax10.假设线路延迟与距离成正比.由于问题DCMD属于NP-hard,不容易精确计算出树延迟最小的生成树.为衡量本文算法的优化度,我们以为参考值,其中延迟路径长度i=,i表示延迟路径.显然,dismax小于等于树延迟的最优解.3.1 与参考值dismax的比较
32、注意,我们采用结点的平均邻居个数Ne来替代p,例如当Ne=4时,如果|V|=20,那么p=0.2;如果|V|=400,那么p=0.001.我们测试320个随机图/正态图,规格见表2,每个规格有20个图.权值函数f(x)=w0+degvw,w0=4,w=1.算法2的权衡因子k=5.表2的数据是相应20个图的平均值.从表2可以看出,用算法3所得的解离dismax最近,近似比最好;算法1的所得解较差,平均情况都可能是dismax的5倍,并且随着结点个数的增多,解越来越差;从图2、图3可以明显看出,用算法2和算法3求得的生成树的树延迟在平均情况下比较接近dismax.Table 2 Computati
33、onal results of the three algorithms for DCMD problem表2 3种算法求解DCMD问题的计算结果ScaleNe=4Ne=6Ne=8dismaxSpanning tree delaydismaxSpanning tree delaydismaxSpanning tree delayAlg 3Alg 2Alg 1Alg 3Alg 2Alg 1Alg 3Alg 2Alg 1Randomgraph2050100150200300400500211286300291364362414425216293316304379379432425229309345
34、3484123834745053335456057779041 0981 2421 3551541842502402322622803011602042692622752893013211742162872823183193313672533976076828209421 0861 357122154183181207220218-134176200203234241227-142192240243259285311-1973395666386928281 040-Normaldistributiongraph205010015020030040050067879896113105126133
35、7497110109128122142150841031071261361301531531121722042563103663834514758757682819592547388929910411311857871001001041101261318713319622427231437743140516464687973-48657983899695-53758990102107106-79120183202228273325-Note: (1) Alg=algorithm;(2) “Normal distribution graph” means the graph where node
36、s coordinate follow Normal Distribution.为了进一步定量描述算法3的优化度,我们对每个图计算百分比相对差值的均值 100%,这样可以较为准确地衡量树延迟与dismax之间的差距,其中Li表示算法3得到的生成树的延迟,的计算结果见表3.我们得到如下结论: 当网络比较稀疏、结点比较分散时,算法3所得解较好,d3%5%. 如果结点位置不变,增加互连概率,则d增加.d越大表示算法的解越来越差. 我们所测试的320个图的平均情况,最差情况d=150%.这表明,在我们的实例中,算法3所得的解平均比dismax大14%,其中最差的解是dismax的5倍.dismax A
37、lgorithm 3Algorithm 2010020030040050060001002003004005006000100200300400010020030040050060001002003004000100200300400500(a) Ne=4 (b) Ne=6 (c) Ne=8 Fig.2 The relation graph of scale (x axis) and the spanning tree delay (y axis) in the random graph图2 随机图的规模(x轴)与树延迟(y轴)曲线关系图0501001502000100200300400500
38、60005010015001002003004005006000501001500100200300400500(a) Ne=4 (b) Ne=6 (c) Ne=8Fig.3 The relation graph of scale (x axis) and the spanning tree delay (y axis) in normal distribution graph图3 正态图的规模(x轴)与树延迟(y轴)曲线关系图Table 3 Comparsion between dismax and the computional results of Algorithm3表3 算法3的解与
39、dismax的对比ScaledRandom graphNormal distribution graphNe=4Ne=6Ne=8Ne=4Ne=6Ne=82050100150200300400500335445454.211.17.99.56.6117.86.810.415.69.412.613.110.114.2-111013141416131314.929.117.32219.926.020.82021.529.22632.532.422.632.5-Average4.1258.112512.21321.2528.13.2 与网络稠密度的关系第3.1节的模拟显示:d随着网络稠密度的增加而增大
40、(正态图相对随机图要稠密一些),即算法所得的树有变坏的趋势.那么是否随着网络稠密度的增加,解是否会越来越坏?为此我们测试20个规模为500个结点的随机图,通过算法2得到最大树延迟和互连概率p的曲线关系(如图4所示).可以看出,当p0.2时,随着p的增加,最大延迟下降较为平缓;p从0.2上升到0.5,最大延迟仅仅降低了1/10.当p=0.2时,算法2的解是dismax的2倍.所以随着稠密度的增加,我们的算法不会越来越远离参考值dismax.这个结果很容易理解,结点位置基本决定了延迟属性.虽然增加互连概率可以减少链路的中转次数,节省转发处理时间,但是延迟属性还是没有发生变化;另外,受结点度的限制,
41、不是所有的结点对都能够直接连接,必须经过一些中转结点的中转处理,这样延迟路径上中转结点的数目必然会随着网络规模的扩大而增加.所以,当互连概率达到一定的值后,优化的余地就越来越小.总体而言,当结点比较分散、网络比较稀疏时,算法3与参考值dismax十分接近,所得解比dismax大约多10%左右;算法2略差,所得解大约比dismax多20%左右.算法1虽然计算简单,但是所得解很差,同等情况下,大约是dismax的35倍左右.当网络比较稠密时,例如500个结点随机分布在100100的平面上,当互连概率达到0.2时,算法2所得的解大约为dismax的2倍;此后,随着互连概率的增加,这种情况基本保持不变
42、,解有轻微变好的趋势.010020030040001020304050CPSTDAlgorithm2dixmaxFig.4 |V|=500, the relation graph of the spanning tree delay (SPD)and the connection probability (CP)图4 |V|=500,树延迟与互联概率p的曲线关系4 结 论本文主要研究了构建应用层最小延迟组播树的问题.文章的主要贡献包括,专门针对应用层组播定义了一种更加全面的问题模型DCMD,并且证明这个问题属于NP-hard.DCMD与现行的模型不同,结点与边都带权,且结点的最大度受限.我们提
43、出两类近似的启发式算法:基于度的算法和基于最大延迟路径的算法.其中基于最大度的时间复杂度为O(|V|2),近似比为O(|V|);基于最大延迟路径算法的时间复杂度为O(|V|4).模拟结果显示,在所提出的3种算法中,算法3相对最优;当结点比较分散、网络比较稀疏时,算法3求得的生成树延迟比参考值dismax大约多10%左右,算法2多20%左右.随着网络稠密度的增加,算法2、算法3求得的最小延迟生成树延迟大约与参考值dismax保持常数倍的关系,也就是说,此时算法2、算法3的近似比是常数.在今后的研究中,我们将继续改进求解DCMD的算法,以获得更好的近似比;同时我们将致力于大规模应用层组播树的研究,
44、对于大规模组播树的构建,不能仅仅依靠算法来获得优化解,需要实施某种策略才能获得较好的应用层组播树.References:1 Broash E, Shavitt Y. Approximation and heuristic algorithms for minimum delay application-layer multicast trees. In: INFOCOM 2004, the 23rd Annual Joint Conf. of the IEEE Computer and Communications Societies. Vol 4, 2004. 2697-2707. http:/www. ieee-infocom.org/2004/Papers/56_1.PDF2 Shi SY, Turner JS. Multicast routing and bandwidth dimensioning in overlay networks. IEEE Journal on Selected Areas in Communications, 2002,20(8):1444-1455.3 Banerjee S, Kommareddy C, Kar K, Bhattacharjee B, Khuller