A distributed multicast routing protocol for real-time multicast applications

Multicast routing is establishing a tree which is rooted from the source node and contains all the multicast destinations. A delay bounded routing tree is a tree in which the accumulated delay from the source node to any destination along the tree does not exceed a pre-specified bound. This paper presents a distributed routing protocol which constructs delay bounded routing trees for real-time multicast connections. A constructed routing tree has a near optimal network cost under the delay bound constraint. The proposed algorithm is fully distributed, efficient in terms of the number of messages required, and flexible in multicast membership changes. A large number of simulations have been done to show the network cost of the routing trees generated by our method is better than the other major existing algorithms.     

受时延约束的组播路由算法

提出了一种新的受时延约束的组播路由算法。算法借鉴了MPH算法的思想,最初的组播树只包含源结点,然后每次将到达组播树的代价最小且满足时延约束的结点及其相应的路径加入到组播树,直到所有的成员加入为止。谊算法能够快速地得到一棵满足时延约束的组播树,并且组播树的代价也很小。实验表明：该算法简单,复杂度低,性能良好,易于在分布式环境中实现,可应用于实际的应用系统中。     

Reconfigurable multicast routing for Networks on Chip

Several unicast and multicast routing protocols have been presented for MPSoCs. Multicast protocols in NoCs are used for cache coherency in distributed shared memory systems, replication, barrier synchronization, or clock synchronization. Unicast routing algorithms are not suitable for multicast, as they increase traffic, congestion and deadlock probability. Famous multicast schemes such as tree-based and path-based schemes have been proposed originally for multicomputers and recently adapted to NoCs. In this paper, we propose a switch tree-based multicast scheme, called STBA. This method supports tree construction with a minimum number of routers. Our evaluation results reveal that, for both synthetic and real traffic loads, the proposed scheme outperforms the baseline tree-based routing scheme in a conventional mesh by up to 41% and reduces power consumption by up to 29%.     

EMRPP：一种DTMSN组播路由算法

针对容迟移动传感器网络（Delay Tolerant Mobile Sensor Network,DTMSN）网络的容迟及节点的移动性特点,提出了一种新的基于概率预测的能量均衡组播路由算法（Energy-balanced Multicast Routing based Probability Probabilistic,EMRPP）。该算法采用到达概率选择路由下一跳的方式,且考虑了节点能量对算法性能的影响。仿真结果表明,EMRPP算法在数据传输率和平均传输延迟方面的性能要优于改进之前的PROPHET算法,是一种有效的容迟移动网络组播路由方案。     

度约束QoS组播路由遗传算法

有度约束的QoS组播路由问题在通信网络中具有重要意义。提出一种基于遗传算法的度约束组播路由算法,采用节点连接路径形式的编码方法构成一棵组播树的表示,设计了相应的具有树形结构的交叉和变异算子,以及节点度的改变算法。算法可以实现具有树形结构染色体的遗传进化。数值实验表明算法具有找到最优解的能力,特别适合于求解大规模网络有度约束的QoS组播路由问题。     

利用分散搜索算法实现受时延约束的多播路由

提出一种新的基于分散搜索算法 （Scatter Search,SS） 来解决受时延约束的多播路由的方法。作为进化算法的一种,分散搜索算法不但继承了进化算法中通过杂交和变异算子来增强性能的机制,还独创性地运用了“分散 - 收敛集聚”的迭代机制。通过在受时延约束多播路由算法上应用 SS 算法,寻找包含所有组播节点在内的最小代价树。实验表明,本算法具有较好的收敛性和分布性。     

SpiNNaker: Enhanced multicast routing

The human brain is a complex biological neural network characterised by high degrees of connectivity among neurons. Any system designed to simulate large-scale spiking neuronal networks needs to support such connectivity and the associated communication traffic in the form of spike events. This paper investigates how best to generate multicast routes for SpiNNaker, a purpose-built, low-power, massively-parallel architecture. The discussed algorithms are an essential ingredient for the efficient operation of SpiNNaker since generating multicast routes is known to be an NP-complete problem. In fact, multicast communications have been extensively studied in the literature, but we found no existing algorithm adaptable to SpiNNaker. The proposed algorithms exploit the regularity of the two-dimensional triangular torus topology and the availability of selective multicast at hardware level. A comprehensive study of the parameters of the algorithms and their effectiveness is carried out in this paper considering different destination distributions ranging from worst-case to a real neural application. The results show that two novel proposed algorithms can reduce significantly the pressure exerted onto the interconnection infrastructure while remaining effective to be used in a production environment.     

反应式组播路由协议

介绍了Ad hoc网络中基于网格的反应式组播路由协议RMMP。当网络中有数据要发送时,RMMP协议分布式地选出核心节点,由核心节点负责网格的建立和维护。发送节点无需加入组就可进行数据的传递,协议的实现也不依赖任何单播路由。通过NS 2对RMMP协议进行仿真并与ODMRP协议的性能对比和分析表明,RMMP协议减少了网络中的洪泛控制信息和冗余链路,从而降低了控制开销和数据传递开销,减轻了网络中的拥塞,明显提高了数据传递的效率和网络的可扩展性。     

基于分簇结构的无线移动网络多播路由协议

移动自组网（MANET,Mobile Ad hoc Networks）是一种特殊的、应用前景广阔的新型移动无线网络。特有的网络特性使它在诸如灾难救助、战场、传感器网络、分布式计算等领域有着广泛的应用前景。结合在移动自组网络中应用最为广泛的分层结构——簇结构的特点,提出了一种基于簇结构的移动自组网多播波路由协议。协议通过对移动自组网进行簇划分,形成由簇头、簇间节点和簇内节点构成的分簇网络结构,并且在由簇头和簇间节点形成的虚拟骨干网基础上,对其进行回路检测和冗余剪枝算法处理,最终得到一个能满足多播要求的多播树,从而实现在移动自组网中的多播路由。通过对仿真实验结果的分析,该协议具有稳定的数据包发送率和较低的路由建立时间。     

求解QoS组播路由的生长竞争蚁群算法

基于生长竞争蚁群算法,提出一种解决QoS组播路由问题的算法。算法引入生长竞争机制,使算法更好更快向最优解逼近。实验结果表明,该算法是可行和有效的。     

A flexible multicast routing protocol for group communication

Multicast routing, once dominated by a single routing protocol, is becoming increasingly diverse. It is generally agreed that at least three routing protocols, PIM, DVMRP, and CBT will be widely deployed and must interoperate. This signals a shift from the Mbone as one large domain to a collection of administrative domains where each domain selects its own multicast routing protocol.This paper proposes another multicast routing protocol, Conference Steiner Multicast (CSM), that is suited for domains that implement OSPF as the unicast routing protocol. CSM is targeted towards (sparse) multicast conferencing and online discussion groups. Characteristics of such discussion groups include any member being a speaker or listener and dynamic changes in the group membership. CSM is futhermore well suited for domains with mobile hosts because its basic architecture can support a mobile environment.CSM is based on the use of a shared, heuristic Steiner minimal tree for interconnecting group members. A key component of the design is that it dynamically and reliably shifts to a different tree as changes warrant. CSM supports rudimentary entry control for security and permits application assistance over routing decisions (termed Application Assisted Routing).This paper describes the architecture of CSM as well as a prototype implementation. Several CSM routers have been interconnected to form a Multicast Steiner Backbone (Msbone). Standard applications such as vat, vic, and wb [V. Jacobson, Multimedia Conferencing on the Internet, Tutorial 4, ACM SIG-COMM 94, August 1994] have been modified to run on Msbone. CSM is designed to connect to the Mbone via interoperation with DVMRP, and as interoperation standards develop it should be capable of implementing these standards.     

A tree-based particle swarm optimization for multicast routing

QoS multicast routing is a non-linear combinatorial optimization problem. It tries to find a multicast routing tree with minimal cost that can satisfy constraints such as bandwidth, delay, and delay jitter. This problem is NP-complete. The solution to such problems is often to search first for paths from the source node to each destination node and then integrate these paths into a multicast tree. Such a method, however, is slow and complex. To overcome these shortcomings, we propose a new method for tree-based optimization. Our algorithm optimizes the multicast tree directly, unlike the conventional solutions to finding paths and integrating them to generate a multicast tree. Our algorithm also applies particle swarm optimization to the solution to control the optimization orientation of the tree shape. Simulation results show that our algorithm performs well in searching, converging speed and adaptability scale.     

Algorithms for multicast connection under multi-path routing model

Given a source node and a set of destination nodes in a network, multicast routing problem is usually treated as Steiner tree problem. Unlike this well-known tree based routing model, multicast routing under multi-path model is to find a set of paths rooted at the source node such that in each path at most a fixed number of destination nodes can be designated to receive the data and every destination node must be designated in a path to receive the data. The cost of routing is the total costs of paths found. In this paper we study how to construct a multicast routing of minimal cost under multi-path model. We propose two approximation algorithms for this NP-complete problem with guaranteed performance ratios.     

An orthogonal genetic algorithm for multimedia multicast routing

Many multimedia communication applications require a source to send multimedia information to multiple destinations through a communication network. To support these applications, it is necessary to determine a multicast tree of minimal cost to connect the source node to the destination nodes subject to delay constraints on multimedia communication. This problem is known as multimedia multicast routing and has been proved to be NP-complete. The paper proposes an orthogonal genetic algorithm for multimedia multicast routing. Its salient feature is to incorporate an experimental design method called orthogonal design into the crossover operation. As a result, it can search the solution space in a statistically sound manner and it is well suited for parallel implementation and execution. We execute the orthogonal genetic algorithm to solve two sets of benchmark test problems. The results indicate that for practical problem sizes, the orthogonal genetic algorithm can find near optimal solutions within moderate numbers of generations     

QoS多播路由算法研究

随着当前Intemet的发展和各种多媒体应用的出现,多播技术得到大量应用。多播路由算法主要用来建立一棵性能良好的多播树,并使它能够满足各种业务的服务质量需求。将多种群并行技术和退火技术相结合,克服了基于标准遗传算法的多播路由算法过早收敛和后期搜索速度较慢的缺陷,且使用树状编码方法,提出求解带宽、时延、时延抖动和分组丢失率约束的代价最小多播树的多种群并行退火遗传多播路由算法。对QoS多播路由选择问题进行了描述,给出多种群并行退火多播路由遗传算法和一种有效去除冗余信息的遗传算法编码设计技术,通过仿真实验证明了算法的正确性,分析了算法的时间性能,表明该算法快速有效。     

求解动态组播路由问题的混合优化遗传算法

分析了具有网络时延和时延抖动限制的动态组播路由问题的数学模型。在此模型的基础上提出了一种基因库(GP)与传统遗传算法(GA)混合的优化算法GP-GA。该算法利用基因库保存进化过程中得到的解路径以指导后继进化过程,同时改进了交叉和变异算子来加快算法的收敛速度。考虑到问题可能陷入的局部最优情况,又构造了基于“保留和不保留”的进化控制策略来增强寻优能力,很大程度上避免了算法“早熟”现象的发生。大量的仿真实验表明：GP GA算法相对现有的遗传算法求得最优解的概率更高,相对于动态的组播环境也有很好的代价性能。     

基于遗传算法的无线网状网QoS多播路由算法

探讨了基于遗传算法的无线网状网QoS多播路由算法,选用边集表示方式对多播树进行编码,其空间复杂度为O(N),给出了该编码方式下的初始种群生成算法RandWalkMT,同时对传统的遗传操作进行改进使子代个体中不会产生非法多播树,从而避免了复杂的惩罚机制或多播树修复算法。实验表明该算法收敛快且性能较好。     

动态优化的分布式组播路由算法

为了在真实的网络环境中寻找一棵延迟受限、耗费最小的组播转发树,以便更好地支持组播通信,提出了一个可以动态优化的分布式组播路由算法,该算法利用蚁群思想解决上述组播路由问题.由于不同代的蚂蚁之间可以通过信息素来实现间接通信,而信息素又是一种可以反映环境变化的媒介质,因此,该算法能够根据网络环境的变化及时做出调整.结合实际的网络拓扑,进行仿真实验,实验结果表明,通过蚂蚁一代代的进化,算法可以找到一棵满足延迟约束并且耗费尽可能小的组播树.