A note on distributed multicast routing in point-to-point networks

The distributed algorithm for a multicast connection set-up, based on the ‘cheapest insertion’ heuristic, is reviewed. The multicast routing problem is translated into a Steiner tree problem in point-to-point networks where nodes have only a limited knowledge about the network. A solution is proposed in which the time complexity and the amount of information exchanged between network nodes are proportional to the number of members of the multicast group. The Steiner tree is constructed by means of a distributed table-passing algorithm. The analysis of the algorithm presented, backed up by simulation results, confirms its superiority over the algorithm based on ‘waving technique’.Scope and purposeMulticasting is a mechanism used in communication networks that allows distribution of information from a single source to multiple destinations. The problem of finding a multicast connection for a static group of communicating entities in connection-oriented point-to-point network can be formulated in graph theory as a minimum Steiner tree problem. Due to NP-completeness of the Steiner tree problem multicast, routing algorithms are based on heuristics. The diversity of network environments and the lack of centralised information about network topology require an effective distribution of the multicast routing algorithms among the network nodes. This article presents an alternative to the distributed algorithm proposed by Rugelj and Klavzar that implements the same heuristics for the construction of a minimum cost multicast connection in point-to-point networks. The present algorithm constitutes a substantial improvement over that previously proposed with regard to running time and the amount of the information exchanged between network nodes.     

一个快速的时延有界低代价多播路由算法

基于ＱｏＳ的多播路由算法需要在满足每个个体ＱｏＳ需求的同时,又能高效管理网络资源,提出了一种满足端端时延限制的低代价多播路由算法。算法使用一个修改的Ｓｔｅｉｎｅｒ树近似算法先构建时延有界的低代价多播树,再通过最小时延路径与其它尚不在多播树的且结点相连。     

多媒体通信中带度约束的多播路由算法

随着多媒体业务的发展,多播技术应用日益广泛,多播路由是要寻找连接源节点和一组目的节点的一棵多播树,这个问题在数学上归结为Steiner树问题,它是一个NPC问题。在实际网络中,网络节点具备不同的多播能力,有些节点不支持多播,有些节点支持多播,但为了保证网络速度和节点负载平衡,支持多播的节点要限制其复制信息的数量,即节点的多播能力受限。在这种情况下,寻找多播树变得更加困难,该文用节点的约束来表示敏个节点具备的多播能力,节点多播能力受限情况下的多播路由问题被称为带度约束的多播路由问题,其仍是一个NPC问题。该文提出了一种求解带度的约束多播路由问题的双层遗传算法。算法的基本思想是最优多播树应是一棵满足度约束的最小生成树,因此问题的关键在于如何找到包括在最优生成树中的Steiner节点。遗传算法 采用二进制编码方式,内层算法用于求解满足度约束的最小生成树;外层算法进行全局搜索。该文将算法在稀疏图上进行实验,为了更好地模拟真实网络,稀疏图中每个节点具有不同的多播能力,并且多播目的节点数目相比于网络节点数要小。实验对算法进行了三方面比较：（1）解的质量;（2）计算时间;（3）算法的收敛性。实验结果表明,文中提出的遗传算法能够找到费用较小的多播树,但是当网络规模增大时,算法的求解时间也较长。     

基于服务质量的多媒体通信初始路由建立算法的研究

基于服务质量的路由选择机制是从根本上提供分布式多媒体应用所需的服务质量保证的重要手段之一。该文提出了两种基于服务质量的多媒体通信初始路由建立算法。一种算法支持在两个通信方之间建立基于服务质量的初始路由,既可以作为点对点多媒体通信的基于服务质量的路由选择／初始路由建立算法,也可以作为初始成员为两个的多媒体动态组通信的基于服务质量的初始路由建立算法,另一种算法支持在多个通信方之间建立基于服务质量的初始路由,既可以作为多媒体静态组通信的基于服务质量的路由选择／初始路由建立算法,也可以作为初始成员为多个的多媒体动态组通信的基于服务质量的初始路由建立算法,文中还探讨了这两种算法的正确性。     

一种延时约束费用最小分布式动态组播路由算法

多媒体应用一般包含多个组播成员,它消耗大量的网络资源且有严格的端端延时约束.针对这个问题,提出了一种延时约束费用最小的分布式动态组播路由启发算法DDDDCLCMR(distributeddynamicdelay-constrainedleast-costmulticastroutingalgorithm).在DDDDCLCMR算法中,组播源点很少或根本不参与路由计算;即使组播成员发生改变,组播树变化也很小,算法扩展性好.实验结果表明,无论组播成员改变与否,DDDCLCMR算法都能获得满足延时约束且费用很低的组播树.     

Multicast Algorithms for Hypercube Multiprocessors

Depending on different switching technologies, the multicast communication problem has been formulated as three different graph theoretical problems: the Steiner tree problem, the multicast tree problem, and the multicast path problem. Our efforts in this paper are to reduce the communication traffic of multicast in hypercube multiprocessors. We propose three heuristic algorithms for the three problem models. Our multicast path algorithm is distributed, our Steiner tree algorithm is centralized, and our multicast tree algorithm is hybrid. Compared with the previous results by simulation, each of our heuristic algorithms improves the communication traffic in the corresponding multicast problem model.     

结合集中式与分布式特征的多路径QoS组播路由协议

提出了一个结合集中式算法与分布式算法优点的多路径启发式QoS组播路由算法和协议，它以单播路由协议OSPF传播链路的代价信息为基础，运用最小代价Dijkstra算法计算端节点到当前在树节点的最小代价路径，然后启动一个分布式计算过程得到一个可选路径集，加入节点通过一个综合性启发式选择其中的最佳路径连接到组播树．算法能够有效地支持延时和带宽受限的代价优化组播树构造，具有无环选路、呼叫接收成功率高、呼叫建立时间短、伸缩性好等特点．     

基于受限泛播技术的可伸缩性QoS组播路由协议

随着远程会议、远程教育和交互式仿真等分布式多媒体应用的兴起,组播技术受到网络研究人员的重视.而这些应用的QoS(quality of service)需求又进一步推动了QoS敏感的组播路由协议的发展.在已提出的各种QoS组播路由协议中,如何提高呼叫成功率、增强规模伸缩性、降低控制报文开销,仍然是一个有待探索的问题.提出了一个新的QoS组播路由协议,其基本思想是使路由器只存储其两层邻居节点的可达性信息以及链路的QoS状态信息,以减少路由器存储开销,提高协议的规模伸缩性(scalability).协议采用受限的泛播技术,构造了一个接受节点发起的、采用多路径技术的、分布式路由算法.描述了协议的数据结构、组播树的构造算法,并给出了模拟实验结果.分析表明,基于受限泛播技术的组播路由协议具有节点存储开销小、呼叫接收成功率高等特点.虽然该协议付出了泛播引起的额外带宽开销较大的代价,但是由于协议所需要的控制数据总量不大,加上两层存储结构在一定程度上限制了泛播通信量,因此该方案具有很好的性能.     

一种减轻组播网络节点负载的贪婪策略

组播网络的路由机制是网络资源优化技术的一个主要研究领域,对路由节点负载能力有严格的要求。保证低负载组播成功的关键在于高效地减轻路由节点负载,研究最小化路由节点转发信息量的算法。基于多点传输机制,兼顾组播组的个数和各组播组中接收者的数量两个影响组播负载的重要因素,运用分布式计算和贪婪策略的思想,提出了一种可以使组播组中路由节点存放的转发信息量的最大值得到最小化,从而减轻组播路由节点负担的策略。通过算法分析和实验仿真说明了所提策略的有效性     

一种适用于移动网络的低代价动态多播路由算法

多播由于能够有效地利用网络资源并减轻服务器的负担因而受到广泛关注,但在移动网络环境中,由于多播组成员的位置可以动态改变,已有的动态多播算法不能获得较好的性能。论文提出了一种适用于移动网络的动态多播路由算法,该算法为目的节点建立最短多播路径时采用了结合链路代价和多播目的节点数的平摊代价函数,以便构建出的多播树在整个通信过程中平均总代价较小。模拟实验结果表明论文提出的算法所构建的多播树的平均总代价要低于其它动态算法。