共查询到20条相似文献,搜索用时 125 毫秒
1.
应用层组播(ALM)树的构建是一个NPC问题,目前已经提出几种启发式组播树构建算法,各种启发式算法因为考虑因素的制约都存在一定的局限性.本文根据当前网路链路状态,通过计算比较选择父节点构建组播树,提出了在满足最大网络连接带宽、度约束、足够可用性时间的前提下使组播树的资源利用率最优的算法.通过仿真实验对此算法的数学模型进行验证,根据组播树的数据吞吐量分析,与通常组播树构建算法相比,基于此算法构建的组播树更加合理稳定. 相似文献
2.
针对无线网络中资源受限的组播路由问题,考虑网络节点的节点度限制和网络链路的带宽约束,以最小化组播路由开销为目标,提出了一种二进制编码方式的基于灰狼优化算法的组播路由策略.在给定的网络拓扑下,基于灰狼优化算法的组播路由策略可以迅速找到一棵包含源和目的节点的最小开销组播树.仿真结果表明,相比于遗传算法,所提出的基于灰狼优化... 相似文献
3.
光组播路由代价与波长使用量的联合优化方法 总被引:1,自引:1,他引:0
为解决光组播路由中组播中路由代价和波长资源消耗单一化造成的组播路树路由的代价过高问题,在分光节点约束条件下,提出了光组播路由代价与波长使用量联合优化的长路优先(LPF)方法和短路优先(SPF)方法。算法通过检查最小光组播树是否存在节点分光约束的问题,根据设置的波长使用代价控制因子,使LPF或SPF的路由代价和波长使用量最小。LPF方法首先选择组播树最长路径或新波长通道重路由受分光约束的目的节点,SPF方法先选择组播树中最短路径或新波长通道重路由受分光约束的目的节点,仿真结果表明,本文提出的两种联合优化方法都能实现路由代价较低和波长需求较少的目的。 相似文献
4.
5.
为了将网络编码技术引入到全光组播网络中,提出了能够在多项式时间完成的基于网络编码的双路径组播树生成算法.该算法主要包括两大步骤:首先,从给定的组播网络中根据节点间度平衡的原则为源节点和每个目的节点之间确定一条有向路径,从而建立一棵传统有向树并保证有向树中任意节点的出度尽可能小,减少节点之间的关联性;其次,在所建立的传统有向树的基础上,从每一个目的节点到源节点根据冲突回溯原则建立源节点和每个目的节点之间的第二条路径,并保证源节点到任意目的节点间的两条路径为分离路径.算法中包含的约束原则能够保证所建立的双路径组播树包含最少的编码节点,从而使得所建立的组播树支持光域网络编码高效率实现,实现基于网络编码的全光组播并提升全光组播的性能. 相似文献
6.
7.
8.
一种支持QoS的拓扑自适应动态组播路由算法 总被引:3,自引:0,他引:3
YAM、QoSMIC、DSDMR等一类支持QoS的动态组播路由算法允许组播成员动态地加入和离开,同时为接收方提供多个可选择的组播接入路径,以满足不同应用的QoS需求。但这些算法普遍存在控制信令开销大和结点加入时延长,可扩展性不好等问题。本文在分析这些算法的基础上,提出改进的支持QoS的动态组播路由算法,即拓扑自适应动态组播路由(Topology Adaptive Dynamic Multicast Routing,TADMR)算法。该算法避免了以往算法中大部分盲目的路径搜索,并使结点加入时延不再受限于固定的等待时钟,而与网络拓扑相自适应。性能分析和仿真结果表明,该算法具有较低的控制信令开销和结点加入时延,适用于各种网络规模和群组规模,具有良好的可扩展性。 相似文献
9.
10.
基于蚁群算法的正反馈机制提出了一种基于树的蚁群算法,并用它来求解度约束组播路由问题.在该算法中,蚂蚁按照一定的概率选择一条链路加入组播子树,然后检查加入点的度约束情况,如果该点的度约束情况达到饱和,则蚂蚁以后不再选取与该点连接的链路.通过计算模拟分析方法证明了该算法的有效性,计算机仿真结果显示,在解决度约束组播路由问题时,该新型蚁群算法的收敛速度大大快于已有的蚁群算法,找到的最优解性能稍好于已有的算法,算法的空间复杂度也得到降低. 相似文献
11.
As multicast applications becoming widely popular, supporting multicast in wavelength division multiplexing (WDM) networks is an important issue. Currently, there are two schemes to support multicast in WDM networks. One scheme is opaque multicasting which replicate bit stream in electronic domain. And the other is transparent multicasting which replicate bit stream all optically by a light splitter. However, both of two schemes have drawbacks or difficulties. This paper investigates an alternate translucent multicasting scheme, in which a fraction of branch nodes replicate bit stream at electronic domain and the other branch nodes replicate bit stream all optically. Replicating bit stream at electronic domain will introduce electronic processing overhead and extra delay. To satisfy the delay requirement of multicast session, the maximum number of electronic hops of a multicast tree must be less than an upper bound. In this paper, a hop-constrained multicast routing heuristic algorithm called shortest path based hop-constrained multicast routing (SPHMR) is proposed. A series of simulations are conducted to evaluate the effectiveness of translucent multicasting scheme. Simulation results show that the translucent multicasting scheme achieve a good compromise between network performance and network cost as well as power losses caused by light splitting. 相似文献
12.
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. 相似文献
13.
The advances in wavelength-division multiplexing (WDM) technology are expected to facilitate bandwidth-intensive multicast
applications through light splitting. Due to complexity and cost constraints, light splitting (or optical multicast) nodes
are sparsely configured in a practical WDM network. In this article, we investigate the multicast routing problem under the
sparse light-splitting constraint. An efficient sparse splitting constrained multicast routing algorithm called Multicast
Capable Node First Heuristic (MCNFH) is proposed. The key idea of MCNFH is to include the shortest path, that includes most
of the multicast capable nodes, for configuring the multicast tree. Simulations and comparisons are used to demonstrate the
performance of MCNFH. Simulation results and analysis show that MCNFH builds multicast trees with the least wavelength channel
cost and with the smallest number of wavelengths used per link. In addition, MCNFH requires only one transmitter at the source
node. 相似文献
14.
A heuristic algorithm of establishing a minimum coding nodes multicast tree on which a two-channel all-optical network coding scheme can be performed is presented.To minimize the coding nodes,the heuri... 相似文献
15.
提出了一种适合目的节点动态加入的、时延受限低代价多播路由的启发式算法DLHMA算法。该算法基于MPH算法的基本思想进行扩展,在满足时延限制条件和多播树代价增加最小的基础上,逐步将目的节点添加到多播树上。最后,证明了算法的正确性,分析了算法的动态性,并进行了仿真实验。结果表明,该算法可以实现新加目的节点的动态加入,并保证所获得多播树的低代价。 相似文献
16.
17.
A core-based forwarding multicast tree is a shortest path tree rooted at core node that distributes multicast packets to all group members via the tree after the packets are sent to the core. Traditionally, the bandwidth cost consumed by transmitting a packet from the core via the tree is evaluated by the total weights of all the edges. And, the bandwidth cost is minimized by constructing the multicast tree that has minimum total weights of edges to span all group members. However, when the local broadcast operation is used to multicast a packet, we found that the bandwidth cost is supposed to be evaluated by the total weights of all senders that include the core and all non-leaves. Since the multicast tree with the number of nodes greater than or equal to three has minimum bandwidth cost only when the core is not a leaf, it leads us to find the multicast tree with the minimum number of non-leaves when each sender node has a unit weight. However, no polynomial time approximation scheme can be found for the minimum non-leaf multicast tree problem unless P = NP since the problem is not only NP-hard but also MAX-SNP hard. Thus, a heuristic is proposed to dynamically reduce the number of non-leaves in the multicast tree. Experimental results show that the multicast tree after the execution of our method has smaller number of non-leaves than others in the geometrically distributed network model. 相似文献
18.
Chakraborty Debasish Zabir Salahuddin Muhammad Salim Chayabejara Apichet Chakraborty Goutam 《Telecommunication Systems》2004,25(3-4):299-315
Single point, sender based control does not scale well for multicast delivery. For applications, such as group video or teleconferencing a low total cost multicast tree is required. In this article we present a destination driven algorithm to minimize the total tree cost of multicast tree in a dynamic situation for the whole session duration. In this heuristic approach we considered the staying duration of participants are available at the time of joining. The performance of our algorithm is analyzed through extensive simulation and evaluated against several other existing dynamic multicast routing and also against one well known near optimum heuristic algorithm used for solving Steiner tree problem. We have further tested our algorithm using erroneous information given by the joining participants. Simulation results show that its performance does not degrade that much even when the range of error is considerably high, which proves the robustness of our algorithm. 相似文献
19.
We study online multicasting in WDM networks with shared light splitter bank. Our objective is either to maximize the network
throughput or to minimize the blocking probability. Due to the nature of dynamic requesting for network resources by online
multicast requests, the network usually is unable to allocate the resources needed for each request in advance. Instead, it
either accepts the request by building an economic multicast tree for the request, in terms of the utilization of the network
resources if it has sufficient resources available, or rejects the request, otherwise. It is desirable that the cost of realizing
each multicast request be minimized, and the network throughput will be maximized ultimately through the cost saving on each
individual request. Since optical light splitting and wavelength conversion switching in optical networks is cost expensive
and its fabrication is difficult, it is assumed that only a limited number of light splitters and wavelength converters are
installed at a node, which will be shared by all the incoming signals at the node. In addition, it is further assumed that
only a fraction of nodes in the network are installed with such optical switches. In this article we first propose a cost
model for realizing an online multicast request under such network environments with limited light splitters and wavelength
converters, which models the cost of utilization of network resources, particularly in modeling the light splitting and wavelength
conversion ability at nodes. We then show that finding a cost-optimal multicast tree for a multicast request under the proposed
cost model is NP-complete, and instead devise approximation and heuristic algorithms for it. We finally conduct experiments
to evaluate the performance of the proposed algorithms. The results show that the proposed algorithms are efficient and effective
in terms of network throughput.
相似文献
Weifa LiangEmail: |