基于优先度的应用层组播协议

1、基于优先度的应用层组播协议基于优先度的应用层组播协议俞俊俞俊（1980-），男，2003年获浙江大学计算机学士学位, 现在浙江大学计算机系攻读硕士学位。研究方向为分布式系统和应用层组播。E-mail: yujun116.，陈岭陈岭（1977-），男，1999年获浙江大学计算机学士学位，2004年获浙江大学计算机博士学位。现为浙江大学计算机系讲师，研究方向为计算机支持协同工作和协同虚拟环境。，陈根才陈根才（1950-），男， 1973年获杭州大学物理学士学位，现为浙江大学计算机系教授。研究方向为计算机网络、数据库和计算机支持协同工作。（1,2,3 浙江大学计算机科学与技术学院，杭州310027）

2、摘 要：本文提出了一种用于分布式虚拟环境的应用层组播协议基于优先度的应用层组播。与之前提出的其他应用层组播协议相比，它的优势在于将实体在虚拟环境中的优先度作为构建组播树的参数之一，而别的应用层组播协议仅仅考虑了网络层因数。因此它更加适用于那些实体优先度不同的应用，例如：分布式虚拟环境（DVE）。通过仿真实验得出：基于这种应用层组播协议建出的组播树在节点扇出和总带宽利用率上都比单播方式高效。同时优先度对建树起到了指导作用，即优先度大的实体，它到根节点的延时就小。由这几点可以证明，基于优先度的应用层组播很好的满足了DVE系统的特点。关键词：优先度；分布式虚拟环境；应用层组播协议571. 引言近几年

3、以来分布式虚拟环境得到了广泛的应用（DVE）。随着用户的不断增多，研究者们将注意力集中到如何减少用户获得的无关数据。高层体系结构1（HLA）是一种用来过滤无关数据的机制，它为每个发送实体建立发送区域，并由此建立发送组，以及对组中成员采用组播的方式发送信息。目前的HLA是采用了IP组播的方式来实现组播功能，这是一种目前广泛采用的组播机制2（ALM）。但它同时存在不足，随着用户的增多，组播组必然增多，而IP组播一个很大的不足就是IP组播地址的缺乏。目前被提出用来取代IP组播的机制就是应用层组播2。应用层组播的目的是将组播功能在应用层上实现，这样就不需要在网络层有特殊的硬件的支持。目前，已提出的AL

4、M体系有：ESM(End System Multicast)、ALMI(Application Level Multicast Infrastructure)、YOID(Your Own Internet Distribution)三种体系。ESM体系由CMU大学网络实验室提出，采用NARADA2协议。它针对的应用是网络视频点播系统。它采用了两步建树过程：首先所有节点（已加入到系统中的节点）被连接成一个连通子图，之后再由连通子图生成最短路径树作为组播树3。ALMI4由华盛顿大学提出，其设计的目的是通过应用层组播实现分布式数据库。它与NARADA不同之处在于它的多点发送。虽然也是采用了两步建树方

5、式，但却是采用了最小生成树作为所有节点的共享树。ACIRI（AT&T Center for Internet Research at ICSI）研究中心提出的YOID5与前两种不同，它采用了单步建树的方式，同时还加入了避免循环产生机制。以上列出的应用层组播协议只将网络层因素（如带宽，延时）作为建树依据，它们仅适用于那些不存在节点优先关系的应用，例如视频点播。在这些应用中，所有节点都具有相同的优先度。而分布式虚拟环境中的实体却由于位置的不同而具有不同的优先度。与状态更新实体接近的节点需要更短的更新时间，这就需要在建树过程中将实体的优先度考虑进来。通过仿真实验发现，本文提出的基于优先度的应

6、用层组播协议可以满足DVE的建树要求。2. 研究背景随着网络的发展，许多基于网络的应用被开发出来。这其中很多应用需要用到组播，例如，网络视频会议，网络聊天室，大规模网络游戏等。而它们对组播的运用与当初设计IP组播的初衷有很大不同，这表现在：1. 这些应用的组播规模较小，而IP组播是被设计进行大规模组播应用的。2. 由于组播数目的增大，路由器需要保存和更新的路由表的数量增多了，这增大了路由器的负担。所以针对这些应用，研究者试图设计出一种可以用来代替IP组播的机制。它可以更加灵活的实现组播功能。应用层组播被设计出来代替IP组播进行小规模的组播。它有以下几个特点：1. 它不需要特殊的硬件支持，一切都

7、是通过上层的软件来实现。2. 它设计的应用是小规模的组播应用。其中ESM，ALMI和YOID(是三种具有代表性的体系。I、ESMESM具有以下几大优点： 从技术上来说，视频点播系统需要发送节点有足够的发送带宽支持。连接的用户越多则消耗的带宽越大。当服务器的可用带宽用尽时，则新用户难以再加入到系统中。ESM系统允许通过转发的方法来实现视频点播，即用户不直接从服务器获取视频数据，而是从别的用户那里获得。这种实现方式就是一种应用层组播的方式。它可以降低服务器的带宽利用。 在ESM系统中，不必考虑底层网络的实现，而仅需要考虑如何更好的提高组播效率。ESM采用NARADA作为组网协议，它采用两步建树方式

8、： 第一步是建立连通子图，它是建立在完全连通图的基础之上（complete virtual graph）。 第二步是采用最短路径树算法在连通子图上建组播树。NARADA建树过程中采用了距离矢量路由算法6（Distance Vector Routing）。每一组成员都记录了本节点到别的节点的最短路径。II、ALMIALMI为所有的系统提供了控制节点，该节点负责组播树的一致性和有效性。建树和维护树都由它完成。ALMI分为两部分：控制节点和组成员。控制节点：它的任务是用来建树和维护树。它有以下功能： 若有成员离开或是加入时，它被用来维护组播树的连通性。 它不断接收邻节点的更新信息，并且不断的计算最小

9、生成树以保证组播树的连通性。组成员：它有以下功能： 它负责数据的接收和转发。就好象IP组播中的路由器的作用。 它监控周围若干节点的状态更新情况，并不断的把更新信息传给控制节点。它采用周期性探测的方式，即每隔一段时间发送一个探测包到邻节点。ALMI 与NARADA 一样采用两步建树的方式。不同处在于ALMI是利用了MST(Minimum Spanning Tree)的建树策略。III、YOIDNARADA和ALMI的两步建树方式提供了建树的稳定性和最优性。当有组播成员加入或离开时，它影响的仅仅是连通子图，而组播树不受影响。但两步建树也有缺点，那就是建树的收敛时间慢，往往需要较长时间。这对于一些组

10、成员变化不大的应用当然没问题，一旦组变化频率增大，就有可能造成抖动。YOID采用单步建树方式来缩短建树时间，同时，如何防止循环是其需解决的另一个关键问题。在YOID中有一个节点作为起始节点，任何新加入的组成员都到起始节点获取邻节点信息，然后再在这些邻节点中选取一个作为父节点。YOID采用了单步建树方式并且加入了防止循环产生的机制。3. 基于优先度的应用层组播 之前提出的三种应用层组播协议仅仅是利用网络层参数作为建树依据。在这些协议中，每个节点的优先度是相同的。在一些应用中的确存在这样的情况，例如：视频点播，视频会议等。但在其他一些应用却有不同的情况。如：大规模网络游戏，大规模分布式仿真系统等。

11、节点在这些系统中由于所处位置不同而具有不同的优先度。优先度越大的实体则它收到的更新时间越短，也就意味着两个节点之间的路径越短。而当节点的优先度小时，两个节点之间的路径不是最优，协议会根据优先度选择合适的路径给这两个节点。3.1 基于优先度的应用层组播协议它在结构上被分为两部分：起始节点：在系统启动的初级阶段，选定一个节点作为起始节点，它的IP地址通过广播的方式通知所有别的系统成员。这个节点一方面记录分布式虚拟环境中所有实体的位置，并不断更新它们的位置，另一方面根据这些实体的位置采用HLA机制，为每个有状态更新的实体确定组播组。并把组播成员信息发送给这个状态更新实体所在的节点。它本身不参与数据发

12、送，同时也不参与建树过程。这样做最大限度的保证了系统的稳定性，一旦起始节点出现异常，也不会影响到整个系统的工作。仅仅是新的节点无法加入到系统中。发送节点：发送节点就是那些有状态更新的实体所在的节点。这些节点负责组播树的构建，它们自身是树的根节点。在建树过程中，根据从起始节点收到的成员的优先度来构建组播树。3.2 建树的过程1. 首先由起始节点计算出组播组中成员的优先度。在分布式虚拟环境中每个实体都具有两个区域：碰撞区域和发现区域。当发送实体和接收实体之间距离小于发现区域的值时，则它进入到组播组中。实体优先度的计算如下： 2. 当每个发送实体所在节点接收到组播成员信息和优先度信息时，若实体的优先

13、度等于1，则它进入到队列1中；若是小于1，则进入到队列2。采用两个队列的目的是为了方便的构建出基于优先度的组播树。3. 若队列1不为空，则所有队列1中的实体所在节点直接连到发送节点上，而队列2中的节点会选择队列1中的节点作为其父节点，这一选择是周期性的。在此不考虑节点的带宽承受能力。若队列1为空，则队列2中的节点会直接连接到发送节点上。这样即充分考虑到了实体优先度的作用，同时也充分利用了带宽。随着节点状态的更新，以上算法会重复执行，以保持组播树的有效性。这种建树方式的优点是：1. 那些具有较高优先度的节点会进入到队列1中，因此在建树中会直接连到发送节点上去。直连表示的路径是最短的，也就是符合了

14、依靠优先度建树的思想。2. 组播树的不会超过3层，同时又是单步建树，所以建树的时间要短于最小生成树。3. 同YOID一样，这里采用的是单步建树。但有一点与YOID不同，它不需要循环检测机制，这是由于每个节点都有优先值的原因。同时优先值大的不会成为优先值小的子节点，所以不可能产生循环的情况。图1给出了虚拟环境中实体的位置情况。其中A是状态更新实体，而B、C、D在实体A的碰撞区域中，而E、F、G中实体A的发现区域中，所以B、C、D进入队列1中，而E、F、G进入队列2中。根据图1 而构建的组播树见图2。HEFGDABCColisionRegionObservationN Region图1 实体在分布

15、式虚拟环境中的位置图2 实体A的组播树4. 仿真实验设计4.1 拓扑图设计采用Geog-Tech7的拓扑图生成器产生出30个节点的拓扑图。它被用来作为仿真实验的主干网络。同时30个工作站被假设连接到了这30个节点上，但不考虑连接带来的延迟。所有网络上的参数都是静态的。通过拓扑图生成器预先设定好，然后基于静态的拓扑图构造出应用层上的完全连同图。采用的算法是最短路径算法。4.2 分布式虚拟环境设计在虚拟环境中有30个实体，它们都有自身的运动速度和运动方向。这30个实体都有状态更新，同时它们的碰撞区域和发现区域被设为相同的。当实体运动到了虚拟环境的边界上的时候，它会反向以不变速度继续运动。4.3 仿

16、真实验中评价参数的设计两种协议用在本仿真实验中，分别为应用层组播协议和单播协议。评价参数如下：1） 带宽占用量带宽占用量被分为两部分统计。一部分统计根节点的扇出度，另一部分统计节点所有带宽的占用，包括节点的扇出和扇入。它被用来测量带宽的利用率。2） 组播树的延时代表了组播组中实体的个数。是代表了根节点到任意节点的延时。3） 组播树的优先度是代表了树中每个节点的优先度。通过组播树延时和组播树优先度可以反映出是否依据了优先度建树的方针。5. 仿真结果和分析图3 和图4 统计了两部分带宽。在图3中X轴代表了所有在仿真过程中构建出的组播树。Y轴代表了根节点的扇出。这里扇出是指在一次仿真中所有组播树根节

17、点的扇出的总和。由图3 可以看出unicast中根节点的扇出要远大于基于优先度的应用层组播的扇出。这表明基于优先度的应用层组播可以有效提高带宽利用率。图3 中有若干点上，根节点的扇出相同，这些点的出现是由于当队列1为空时，则队列2中的节点会直接连到根节点上，这会增大节点的扇出。但这种情况出现的很少。图4 是从整体的角度来记录带宽利用率。节点的扇出和扇入都被记录下来。目的是全面评价算法在带宽利用上的表现。从图4 中我们可以得出与图3 几乎相同的结论，这表明仿真实验的数据是客观真实的。也确实说明基于优先度的应用层组播协议可以有效降低带宽。同时结合图3 和图4 来看，在图的后半部分，曲线呈现出平稳趋

18、势，表明最后趋向于稳定。图3 根节点的扇出图4 节点占用带宽总和基于优先度建立应用层组播的主要目的是为了将优先度结合进组播树的构建过程。通过图5 看到，当优先度变大时，通过应用层组播可以有效降低组播树的延时。反之当优先度变小时，则组播树的延时变大。这证明算法达到了预期的目的。同时图6并没有表现出这个趋势。所以应用层组播比单播更加适用于分布式虚拟环境。它满足了分布式虚拟环境的要求。图5 组播树延时与其优先度的比较图6 单播树的延时与其优先度的比较6. 结束语本文提出了一种用于分布式虚拟环境的应用层组播协议基于优先度的应用层组播，与之前提出的其他应用层组播协议相比，它的优势在于将实体在虚拟环境中的

19、优先度作为构建组播树的参数之一，通过仿真实验得出：基于这种应用层组播协议建立的组播树在节点扇出和总带宽利用率上都比单播方式高效。同时优先度对建树起到了指导作用，即优先度大的实体，它到根节点的延时就小。由这几点可以证明，基于优先度的应用层组播很好的满足了DVE系统的特点。今后的工作中重点是为节点加上带宽限制，并在有带宽限制的条件下构建组播树。参考文献：1 K. L. Morse, M. Zyda. Multicast grouping for data distribution management. In Proc of Computer Simulation Methods and Appl

20、ications Conference, 2000.2 Y. H. Chu, S.G. Rao, S. Seshan, H. Zhang. A case for end system multicast. IEEE Journal on Selected Areas in Communications, Vol. 20, No. 8, 2002: pp.1456-1471.3 L. Wei, D. Estrin. The trade-offs of multicast trees and algorithms. In Proc of International Conference on Co

21、mputer Communications Networks. 1994.4 D. Pendarakis, S. Shi, D. Verma, M. Waldvogel. ALMI: An application level multicast infrastructure. In Proc of USNIX Symposium on Internet Technologies and Systems, 2001:pp.49-60.5 P. Francis, Y. Pryadkin, P. Radoslavov, R. Govindan, B. Lindell. YOID: your own

22、internet distribution. In Proc of Peer to Peer workshop, 2002.6 D. Waitzman, C. Partridge, S. Deering. Distance Vector Routing. RFC 1075, 1988.7 K. L. Calvert, M. B. Doar, E. W. Zegura. Modelling internet topology. IEEE Communications Magazine, Vol. 35, No. 6, 1997: pp. 160-163.Priority based Applic

23、ation Level Multicast protocolYU Jun, CHEN Ling, CHEN Gencai(College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China)Abstract: This paper proposes an application level multicast protocol based on priority used for Distributed Virtual Environment. Compared with other a

24、pplication level multicast protocols, the advantages of this protocol lie on using both the entities priority in DVE and the nodes network layer metric to construct the multicast tree. The simulation results show that the tree construction method based on priority has a better performance on bandwid

25、th usage than the unicast; meanwhile the priority is a very constructed parameter when build the multicast tree. From the above, the protocol is more suitable for DVE in which the nodes priorities are different.Key words: Priority; Distributed Virtual Environment; Application Level Multicast （责任编辑：曾

26、 丹）（上接第13页）（5）由于粗糙集理论的容错能力较强，因此该粗糙神经网络的容错能力也较强；（6）该网络可以处理动态非线性复杂系统。参考文献：1 曾黄麟.粗集理论及其应用. 重庆：重庆大学出版社, 1998. 2 Pawlak Z.Rough Sets. Theoretical Aspects of Reasoning About Data, Kluwer Academic Publishers, 1991.3 Keming Xie,Zehua Chen.Application of Rough Sets in Intelligent Control , Proc of 4th ISTM., Shanghai China, 2001:pp.291-294.5 Lingras P. Comparison of Neofuzzy and Rough Neural Network .Information Science