一种路径对约束下构造最低代价我播树的探索算法

提出了一种新的探索算法,它根据源与目的节点的时延约束,构造最低代价的多播树。并且可以在网络节点请求加入或离开时,通过更新现有的多播树,实现多播的动态维护。对该算法进行了仿真,并与现有的一些算法进行了比较。     

无线mesh网中最小编码代价低时延多播路由

提出了一种无线mesh网中最小网络编码代价低时延多播路由协议(MNCLDMR, minimal network coding and low delay multicast routing)。MNCLDMR的目标是选择合适的网络编码节点,最小化网络编码代价,降低网络时延。MNCLDMR主要思想是引入拓扑关键节点和网络编码关键节点的概念,以下一跳的节点是否是网络编码关键节点或拓扑关键节点作为路由判据,采用MNCLD算法构造多播树。仿真结果表明,MNCLDMR可以达到预定目标,合理形成网络编码机会,能实现最小网络编码代价低时延多播路由。     

一种基于拉格朗日松弛的时延约束多播路由算法

提出了一种基于拉格朗日松弛方法的时延约束最小代价多播路由算法(LR-DLMA)。该算法充分利用拉格朗日松弛方法的特点，通过构建封闭图，对封闭图进行拉格朗日松弛求得满足条件的多播树。仿真实验结果表明本算法性能稳定，其代价性能接近性能最好的BSMA算法，并具有快速、低时延的特点。     

一种多约束QoS多播路由算法

提出了带宽时延约束、代价最小的QoS多播路由模型,并提出了一种启发式算法求解该问题,分析了算法的复杂度。仿真试验证明,该算法是稳定有效的。它能够在满足两种约束的情况下,使多播树的代价优化。     

基于时延约束的改进型实时QoS多播路由算法

多播技术是将特定数据选择性地传送至多个客户端的方法,因而其服务质量是评价其优劣的关键.结合FLSPT算法和贪婪法思想,提出一种基于时延约束的改进型实时QoS多播路由算法,它利用启发式策略,使得节点在多播树时能满足时延约束的条件下建立最小代价路径.测试结果表明,采用该算法可获得较小的端到端时延,能改善网络服务质量,适用于成员数目变化频繁的多播应用.     

一种改进的多播路由算法

低代价最短路径树是一种广泛使用的多播树,它能够在保证传送时延最小的同时尽量降低带宽消耗。DDSP(Destination-Driven Shortest Path)算法是一个性能较好,计算效率较高的低代价最短路径树算法,在该算法基础上,通过改进结点的搜索过程,提出一种改进的快速低代价最短路径树算法。由算法分析和实验比较得出,改进算法的计算效率高于DDSP算法,且算法构造的最短路径树的性能也优于DDSP算法构造的树．     

支持延时约束的覆盖多播路由协议的研究

研究有度和延时约束的覆盖多播路由问题,提出了一个新的覆盖多播路由协议-延时受限的树协议(DBTP)。该协议采用分布式和树优先的策略,使多播组成员之间能自组织地构建一棵基于源的覆盖多播树。DBTP协议采用了一种新的启发式局部优化算法,通过调节启发因子,能灵活地在延时和代价之间进行折衷。仿真实验表明,无论在静态还是动态节点模型下,选择适当的启发参数,DBTP都能获得较高的节点接纳率。     

多播群组通信中服务质量受限的Core Placement算法

与面向源节点的路由算法不同，Ｃｏｒｅ Ｂａｓｅｄ多播路由算法在网络中为一个多播组上 的多个多播连接只建立一棵共享树，从而实现了提高了网络资源利用率的目的。本文针对 Ｃｏｒｅ Ｂａｓｅｄ多播路由中 ｃｏｒｅ节点的定位问题，提出了一个同时最小化多播时延及目标节点间时延抖动的 ｃｏｒｅ节点定位算法 ＱＯＣＰ。由仿真结果可知，这里提出的方法在优化服务质量性能指标方面明显优 于文中涉及的其他算法。     

基于人工鱼群算法的组播树演化寻优

提出了一种双域模型人工鱼群算法。算法采用前驱节点指向的编码方法形成多播树表示人工鱼,将搜索空间分为可行域和非可行域。分别赋予可行域和非可行域的人工鱼不同的游动目标,设计行为算子自适应地执行4种人工鱼行为。数值实验结果表明,提出的算法可以有效利用非可行个体,具有较好的求解时延约束最小代价多播树的性能。     

基于SimCT的多播路由及故障恢复研究

在数据交换网络中,颜色树是一种通过节点不相交的多路径路由数据报文的有效方法。这种方法中组建两棵以某一节点为根节点的颜色树,即Red树和Blue树,网络中各节点到根节点的路径是节点不相交的。本文在分析和研究SimCT算法的基础上,提出了一种基于颜色树的多播树生成方法及单节点/链路故障的多播通信恢复方案。该方法根据SimCT算法构造的颜色树来组建一棵多播转发树,在多播树中单节点或单链路故障后,故障检测节点本地执行故障恢复方案,将受影响的故障节点的下游子树重新连接到多播树。仿真实验表明,本文所提出的多播树生成方案相比现有方案可以减少网络资源的浪费,并且故障恢复后的代价与原多播通信树相当。     

基于灰狼算法的无线网络组播路由优化

针对无线网络中资源受限的组播路由问题,考虑网络节点的节点度限制和网络链路的带宽约束,以最小化组播路由开销为目标,提出了一种二进制编码方式的基于灰狼优化算法的组播路由策略.在给定的网络拓扑下,基于灰狼优化算法的组播路由策略可以迅速找到一棵包含源和目的节点的最小开销组播树.仿真结果表明,相比于遗传算法,所提出的基于灰狼优化算法的组播路由策略可以得到一棵开销更小的组播树,并且在相同的时间复杂下具有更强的算法稳定性.     

A new heuristic algorithm for finding minimum‐cost multicast trees with bounded path delay

This article presents a new heuristic algorithm called DDBMA (Dynamic Delay Bounded Multicast Algorithm) to construct a minimum‐cost multicast tree. The heuristic depends on (1) bounded delay along paths from source nodes to each destination node; (2) minimum cost of the multicast tree; (3) dynamic multicast tree status which is maintained by updating the existing multicast tree when nodes in the network request to join or leave. Copyright © 1999 John Wiley & Sons, Ltd.     

适于低轨卫星IP网络的核心群合并共享树组播算法

为了解决低轨卫星IP网络中现有典型源组播算法的信道资源浪费问题,该文提出了一种低树代价的组播算法,即核心群合并共享树(CCST)算法,包括动态近似中心(DAC)选核方法和核心群合并组播路径构建方法。DAC方法基于逻辑位置形成的虚拟静态、结构规则的网络拓扑选择核节点。在核心群合并方法中,以核节点作为初始核心群,通过核心群和剩余组成员的最短路径方法逐步扩展直至整棵组播树构建完成,从而使得组播树的树代价最小,大大提高了网络的传输带宽利用率和组播传输效率。最后,与低轨卫星IP网络中的其他几种典型算法进行了性能对比,仿真结果说明,CCST算法的树代价性能比其它算法有较大改善,而端到端传播时延略高。     

基于传输路径质量的无线mesh网络可靠多播

提出了一种可靠多播网(RM)模型,探讨了无线链路和节点可靠性对多播路径选择的影响。首先,建立了无线链路的相关性和多播路径的可靠性模型,并提出了多播传输的可靠性判据;同时,结合首树算法和多路径树算法提出了构造可靠多播网的算法。可靠多播网具有并行的多播路径,通过在多播源节点和目的节点之间选择多播链路和节点构成了可靠的多播路径,提供了多播路径的"负荷分担"和"热备份"功能,从而支持了多播业务可靠性。     

Restricted dynamic Steiner trees for scalable multicast in datagramnetworks

The paper addresses the issue of minimizing the number of nodes involved in routing over a multicast tree and in the maintenance of such a tree in a datagram network. It presents a scheme where the tree routing and maintenance burden is laid only upon the source node and the destination nodes associated with the multicast tree. The main concept behind this scheme is to view each multicast tree as a collection of unicast paths and to locate only the multicast source and destination nodes on the junctions of their multicast tree. The paper shows that despite this restriction, the cost of the created multicast trees is not necessarily higher than the cost of the trees created by other algorithms that do not impose the restriction and therefore require all nodes along the data path of a tree to participate in routing over the tree and in the maintenance of the tree     

光组播路由代价与波长使用量的联合优化方法

为解决光组播路由中组播中路由代价和波长资源消耗单一化造成的组播路树路由的代价过高问题,在分光节点约束条件下,提出了光组播路由代价与波长使用量联合优化的长路优先(LPF)方法和短路优先(SPF)方法。算法通过检查最小光组播树是否存在节点分光约束的问题,根据设置的波长使用代价控制因子,使LPF或SPF的路由代价和波长使用量最小。LPF方法首先选择组播树最长路径或新波长通道重路由受分光约束的目的节点,SPF方法先选择组播树中最短路径或新波长通道重路由受分光约束的目的节点,仿真结果表明,本文提出的两种联合优化方法都能实现路由代价较低和波长需求较少的目的。     

Multicast routing and wavelength assignment in multihop optical networks

This paper addresses multicast routing in circuit-switched multihop optical networks employing wavelength-division multiplexing. We consider a model in which multicast communication requests are made and released dynamically over time. A multicast connection is realized by constructing a multicast tree which distributes the message from the source node to all destination nodes such that the wavelengths used on each link and the receivers and transmitters used at each node are not used by existing circuits. We show that the problem of routing and wavelength assignment in this model is, in general, NP-complete. However, we also show that for any given multicast tree, the wavelength assignment problem can be solved in linear time.     

基于网络编码的双路径组播树生成算法

 为了将网络编码技术引入到全光组播网络中,提出了能够在多项式时间完成的基于网络编码的双路径组播树生成算法.该算法主要包括两大步骤:首先,从给定的组播网络中根据节点间度平衡的原则为源节点和每个目的节点之间确定一条有向路径,从而建立一棵传统有向树并保证有向树中任意节点的出度尽可能小,减少节点之间的关联性;其次,在所建立的传统有向树的基础上,从每一个目的节点到源节点根据冲突回溯原则建立源节点和每个目的节点之间的第二条路径,并保证源节点到任意目的节点间的两条路径为分离路径.算法中包含的约束原则能够保证所建立的双路径组播树包含最少的编码节点,从而使得所建立的组播树支持光域网络编码高效率实现,实现基于网络编码的全光组播并提升全光组播的性能.     

A distributed algorithm of delay-bounded multicast routing formultimedia applications in wide area networks

Multicast routing is to find a tree which is rooted from a source node and contains all multicast destinations. There are two requirements of multicast routing in many multimedia applications: optimal network cost and bounded delay. The network cost of a tree is defined as the sum of the cost of all links in the tree. The bounded delay of a routing tree refers to the feature that the accumulated delay from the source to any destination along the tree shall not exceed a prespecified bound. This paper presents a distributed heuristic algorithm which generates routing trees having a suboptimal network cost under the delay bound constraint. The proposed algorithm is fully distributed, efficient in terms of the number of messages and convergence time, and flexible in dynamic membership changes. A large amount of simulations have been done to show the network cost of the routing trees generated by our algorithm is similar to, or even better than, other existing algorithms