共查询到20条相似文献,搜索用时 31 毫秒
1.
提出了一个结合集中式算法与分布式算法优点的多路径启发式QoS组播路由算法和协议,它以单播路由协议OSPF传播链路的代价信息为基础,运用最小代价Dijkstra算法计算端节点到当前在树节点的最小代价路径,然后启动一个分布式计算过程得到一个可选路径集,加入节点通过一个综合性启发式选择其中的最佳路径连接到组播树.算法能够有效地支持延时和带宽受限的代价优化组播树构造,具有无环选路、呼叫接收成功率高、呼叫建立时间短、伸缩性好等特点. 相似文献
2.
通过对无线mesh网络的特性分析及其对路由的影响,提出一种基于预测时延的路由选择的组播路由算法,该算法通过选择从源节点到目的节点传输时延最小的路径,通过路径合并,形成组播路由树。这种路由算法具有低时延QoS保障能力,并具有局部修复能力。基于NS2对算法进行仿真,结果证明了算法的有效性。 相似文献
3.
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. 相似文献
4.
5.
6.
7.
Multicast routing over semi-permanent VP (virtual path)s in an ATM (asynchronous transfer mode)-based B-ISDN (broadband integrated services digital network) determines a set of VPs connecting from a source node to destination nodes. The problem of finding the optimal constrained multicasting tree over the semi-permanent VPs in an ATM network is known to be NP (nondeterministic polynomial time)-complete. We develop an optimization methodology for searching a constrained multicast routing tree with minimum cost, using simulated annealing technique. We define the problem-dependent components such as state space and cost function, and refine the implementation-dependent factors including initial temperature and cooling schedule. The simulation results show that our optimization methodology demonstrates good behavior in terms of performance on a variety of graphs modeling the sample ATM networks. 相似文献
8.
9.
基于共享边的时延约束组播路由算法 总被引:1,自引:2,他引:1
为了优化在时延约束下的组播树代价,降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了最短路径启发式(MPH)算法的执行过程,以此为基础提出一个基于共享边的时延约束组播路由算法ESAMPH.该算法在构建组播路由树时能够优先采用包含有较多的最短路径经过的节点,这样后面的组播成员节点到树上的最短路径也有可能经过这些节点,由此实现边的共享,降低了组播树的代价.仿真结果表明,ESAMPH算法在代价、延迟和计算时间之间能获得较好的平衡,综合性能较好. 相似文献
10.
基于蚁群系统的动态QoS多播路由算法 总被引:1,自引:0,他引:1
基于蚁群系统的自组织能力,提出了一个分布式的动态QoS多播路由的算法。与其他算法不同,在该算法中,蚁群从多播组的目的结点出发进行搜索,将每次迭代选中的符合QoS约束且具有最小代价的路径加入到多播树中,而多播树以“拉”的模式分布式地被构造。仿真结果表明,与其他两种算法相比,该算法具有更好的性能,能够快速有效地找到动态QoS多播路由问题的全局最(近)优解。 相似文献
11.
《Computer Networks》1999,31(1-2):101-110
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. 相似文献
12.
In this paper, we define the cost optimal solution of the multi-constrained multicast routing problem. This problem consists in finding a multicast structure that spans a source node and a set of destinations with respect to a set of constraints, while minimizing a cost function. This optimization is particularly interesting for multicast network communications that require Quality of Service (QoS) guarantees. Finding such a structure that satisfies the set of constraints is an NP-hard problem. To solve the addressed routing problem, most of the proposed algorithms focus on multicast trees. In some cases, the optimal spanning structure (i.e. the optimal multicast route) is neither a tree nor a set of trees nor a set of optimal QoS paths. The main result of our study is the exact identification of this optimal solution. We demonstrate that the optimal connected partial spanning structure that solves the multi-constrained multicast routing problem always corresponds to a hierarchy, a recently proposed generalization of the tree concept. We define the directed partial minimum spanning hierarchies as optimal solutions for the multi-constrained multicast routing problem and analyze their relevant properties. To our knowledge, our paper is the first study that exactly describes the cost optimal solution of this NP-hard problem. 相似文献
13.
14.
针对时延约束下低代价组播树的构建方法,提出了一种基于关键节点的时延约束低代价组播路由算法.该算法对已有的动态时延优化的链路选择函数进行改进,并加入关键节点和关键次数的概念.在首次选择目的节点时,重点考虑关键节点和关键次数因素,降低了选择低代价链路的时间复杂性,再利用改进后的链路选择函数依次选择节点加入树中,进而产生满足要求的组播树.实验仿真结果表明,该算法不仅能正确构建出时延约束低代价组播树,且与其他算法相比,构成组播树所需平均时间更少. 相似文献
15.
Efficient routing of messages is a key to the performance of multicomputers. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. While multicast communication is highly demanded in many applications, most of the existing multicomputers do not directly support this service; rather it is indirectly supported by multiple one-to-one or broadcast communications, which result in more network traffic and a waste of system resources. The authors study routing evaluation criteria for multicast communication under different switching technologies. Multicast communication in multicomputers is formulated as a graph theoretical problem. Depending on the evaluation criteria and switching technologies, they study three optimal multicast communication problems, which are equivalent to the finding of the following three subgraphs: optimal multicast path, optimal multicast cycle, and minimal Steiner tree, where the interconnection of a multicomputer defines a host graph. They show that all these optimization problems are NP-complete for the popular 2D-mesh and hypercube host graphs. Heuristic multicast algorithms for these routing problems are proposed 相似文献
16.
Mohsen Heydarian 《The Journal of supercomputing》2014,68(1):214-244
Developing new mathematical frameworks such as distributed dynamic routing algorithms for constructing optimal incremental paths from a node to another node is an important challenge in data communication networks. These new algorithms can model network resources optimally and increase network performances. A bundle of single routes in a current communication path, which starts from a source node and ends to a destination node, can consist of several successive nodes and links. The Incremental term emphasizes that the number of routes (links and nodes) in a current path can change so that achieving more data rate and optimal efficiency in the network. In this paper, our problem is to add/omit some routes consisting of some nodes and links to/from the current unicast path dynamically and optimally. We call this problem the Optimal Dynamic Distributed Unicast Routing (ODDUR) problem and it is a NP-complete problem. This problem can be formulated as a new type of Linear Programming Problem (LPP) for finding a minimum cost multichannel unicast path, which this path will minimize end-to-end delay and bandwidth consumption along the routes from the source node to the destination node. In this paper, at first a new mathematical framework will be constructed and then this framework will propose the new optimal dynamic distributed unicast routing algorithm for solving our LPP problem. This algorithm will compute an optimal solution for our LPP based on the simplex method and postoptimality computations and will reduce computations and consumed time. Simulation results will show that our new algorithm is more efficient than other available algorithms in terms of utilization of bandwidths and data rate. 相似文献
17.
《Performance Evaluation》1999,35(1-2):49-74
Multicast network traffic is information with one source node, but many destination nodes. Rather than setting up individual connections between the source node and each destination node, or broadcasting the information to the entire network, multicasting efficiently exploits link capacity by allowing the source node to transmit a small number of copies of the information to mutually-exclusive groups of destination nodes. Multicasting is an important topic in the fields of networking (video and audio conferencing, video on demand, local-area network interconnection) and computer architecture (cache coherency, multiprocessor message passing). In this paper, we derive approximate expressions for the minimum cost (in terms of link utilization) of shortest-path multicast traffic in arbitrary tree networks. Our results provide a theoretical best-case scenario for link utilization of multicast distribution in tree topologies overlaid onto arbitrary graphs. In real networks such as the Internet MBONE, multicast distribution paths are often tree-like, but contain some cycles for purposes of fault tolerance. We find that even for richly-connected graphs such as the shufflenet and the hypercube, our expression provides a good prediction of the cost (in terms of link utilization) of multicast communication. Thus, this theoretical result has two applications: (1) a lower bound on the link capacity required for multicasting in random tree topologies, and (2) an approximation of the cost of multicasting in regular LAN and MAN topologies. 相似文献
18.
针对现有协议组播树开销难以达到最低的不足,提出了一种新的基于自适应阈值参数的组播路由算法.在初始化阶段对目的节点进行最佳合并分区,初始化完成后则在当前源节点处计算对应各目的节点路径有效因子α的值,自适应地选择阈值参数P对α进行评估,根据评估结果选择当前源节点的下一跳转发节点,直到数据包发送到所有目的节点.仿真结果表明,该算法降低了构建组播树的通信开销,并具有较低的算法复杂度. 相似文献
19.
Zhe Liang Wanpracha Art Chaovalitwongse Meeyoung Cha Sue B. Moon 《Computers & Operations Research》2010,37(10):1731-1739
This paper presents a redundant multicast routing problem in multilayer networks that arises from large-scale distribution of realtime multicast data (e.g., Internet TV, videocasting, online games, stock quotes). Since these multicast services commonly operate in multilayer networks, the communications paths need to be robust against a single router or link failure as well as multiple such failures due to shared risk link groups (SRLGs). The main challenge of this multicast is to ensure the service availability and reliability using a path protection scheme, which is to find a redundant path that is SRLG-disjoint (diverse) from each working path. The objective of this problem is, therefore, to find two redundant multicast trees, each from one of the two redundant sources to every destination, at a minimum total communication cost whereas two paths from the two sources to every destination are guaranteed to be SRLG-diverse (i.e., links in the same risk group are disjoint). In this paper, we present two new mathematical programming models, edge-based and path-based, for the redundant multicast routing problem with SRLG-diverse constraints. Because the number of paths in path-based model grows exponentially with the network size, it is impossible to enumerate all possible paths in real life networks. We develop three approaches (probabilistic, non-dominated and nearly non-dominated) to generate potentially good paths that may be included in the path-based model. This study is motivated by emerging applications of internet-protocol TV service, and we evaluate the proposed approaches using real life network topologies. Our empirical results suggest that both models perform very well, and the nearly non-dominated path approach outperforms all other path generation approaches. 相似文献
20.
《Computer Communications》2001,24(7-8):685-692
We present an heuristic genetic algorithm for the quality of service (QoS) multicast routing that depends on: (1) bounded end-to-end delay and link bandwidth along the paths from the source to each destination, and (2) minimum cost of the multicast tree, where the link delay and the link cost are independent metrics. The problem of computing such a constrained multicast tree is NP-complete. We show by experiments that our proposed genetic algorithm is efficient and effective. 相似文献