一种时延和时延抖动受约束的启发式多播路由算法

多播路由算法在组播应用中是至关重要的,对视频会议等交互式实时组播业务来说,不仅要考虑时延约束,而且要考虑时延抖动约束。本文提出了一种基于最短时延路径的时延和时延抖动约束的启发式算法,仿真结果表明该算法复杂度较低,而且性能也较好,在算法复杂度和性能之间达到了很好的折中。     

一种基于带宽和时延约束的分布式组播路由算法

针对已有分布式组播路由算法在寻找QoS路由时的低成功率问题,本文提出了一种新的基于带宽和时延约束的分布式组播路由算法-QDMR(QoS-based Distributed Multicast Routing).在为新组播成员搜索连接到组播树的可行路径时,QDMR算法使用RBMF(Reverse Best Metric Forwarding)转发算法代替RPF(Reverse Path Forwarding)转发算法,从而优先搜索满足带宽和时延约束要求的路径,然后才考虑代价的优化.模拟分析表明,QDMR提高了路由搜索的成功率,并且降低了协议开销.     

基于可用带宽满足时延和时延差别 约束的实时多播路由算法

实时多播路由中具有可加性的代价(Cost)不能确切反映网络本质特性,尤其不能反映路径带宽的凹性(Concave).已有基于代价的算法不能很好适应多播应用,需要新的模型和算法.本文采用可用带宽代替代价作为主要度量,并满足实时多播中二个重要约束度量:时延和时延差别.同时基于此三个度量,本文提出二种新的具有多项式复杂性的实时多播路由算法并比较其性能.新算法通过分析得到每路径时延和二约束之间的关系,有效降低涉及时延和时延差别此类问题的复杂性.新算法采用度量反映实时多播本质特性而具有实际推广性.     

有时延及时延差别约束的最小代价组播路由问题

本文把有时延、时延差别约束的组播路由问题提到优化的层次上,提出了有时延、时延差别约束的最小代价组播路由优化问题,并证明此问题是NP－complete问题。继而提出了一种基于动态罚函数法的启发式遗传算法以及解该问题,并分析了算法的复杂度。仿真表明,本文算法是有效的、稳定的。在满足两种约束的情况下,能够使网络代价优化。     

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

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

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

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

一种时延受限的低代价移动IP组播路由算法

基于固定和移动IP混合网络，针对时延敏感的实时通信业务，建立了网络模型，提出了有时延约束的低代价组播路由问题，给出了一种分布启发式组播路由算法，证明了算法的正确性，分析了算法的复杂度。仿真结果表明，算法是有效的、稳定的。     

基于蚂蚁算法的时延受限分布式多播路由研究

本文探讨了在高速包交换计算机网络中,具有端到端时延限制的多播路由问题。提出了一种新颖的基于蚂蚁算法的多播路由优化算法,该算法是完全分布式的。仿真实验表明,用该算法产生的多播路由树的费用比已存在的主要算法更好,并且适应于多播成员数的变化。     

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

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

一种基于克隆策略的多播路由算法

该文针对网络计算中的NPcomplet问题一带时延约束的多播路由问题,提出了一种基于克隆策略的路由算法．仿真实验表明,与基于遗传算法的多播路由算法相比,该算法具有更快的收敛速度和更好的全局寻优能力,而且算法稳定、灵活,操作简单．     

Ad Hoc网络中基于粒子群优化的QoS多播路由研究

针对Ad Hoc网络中带QoS约束的多播路由问题，提出了一种新的结合MAODV多播路由发现方法和粒．子群优化算法的QoS多播路由发现算法。仿真试验显示该算法较好地改进了端到端传输的代价、延时和带宽利用率，能够找到一棵消耗趋于最小、状态稳定的多播路由树。     

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

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

组播路由调度的神经网络方法

本文探讨了在高速包交换计算机网络中，具有端到端时延及时延抖动限制的组播路由问题。首先给出了此类问题的网络模型及其数学描述，然后提出了基于Ｈｏｐｆｉｅｌｄ神经网络的组播路由优化算法。实验表明，本算法能根据组播应用对时延的要求，快速、有效地构造最优组播树，有较强的实时性。     

Minimizing Cost and Delay in Shared Multicast Trees

Existing tree construction mechanisms are classified into source‐based trees and center‐based trees. The source‐based trees produce a source‐rooted tree with a low delay. However, for the applications with multiple senders, the management overheads for routing tables and resource reservations are too high. The center‐based trees are easy to implement and manage, but a priori configuration of candidate center nodes is required, and the optimization nature such as tree cost and delay is not considered. In this paper, we propose a new multicast tree building algorithm. The proposed algorithm basically builds a non‐center based shared tree. In particular, any center node is not pre‐configured. In the proposed algorithm, a multicast node among current tree nodes is suitably assigned to each incoming user. Such a node is selected in a fashion that tree cost and the maximum end‐to‐end delay on the tree are jointly minimized. The existing and proposed algorithms are compared by experiments. In the simulation results, it is shown that the proposed algorithm approximately provides the cost saving of 30 % and the delay saving of 10 %, compared to the existing approaches. In conclusion, we see that the cost and delay aspects for multicast trees can be improved at the cost of additional computations.     

QoS multicast routing with delay constraints

Proliferation of group-based real-time applications, such as online games and video conferencing has motivated research into QoS multicast routing. These types of applications require consideration of both source-to-destination delay (i.e., packet delay from the source to all destinations) and inter-destination delay variation (i.e., the difference in packet delay from the source to different destinations) constraints. In this paper, we formulate a new combined problem for delay partitioning and multicast routing with source-to-destination delay and inter-destination delay variation constraints in a QoS framework, where a delay dependent cost function is associated with each network link. After identifying the problem asnp-complete, we introduce a Genetic Algorithm (ga) based algorithm that computes a source-based multicast tree which satisfies both constraints with near-optimal cost. We compare differentga schemes using different selection operators and find that the combination of Steady Statega and Remainder Stochastic Sampling selection operator works best for our problem. Simulation results also show that ourga heuristic consistently perfornis better than several other simple heuristics.     

An iterative algorithm for delay-constrained minimum-costmulticasting

The bounded shortest multicast algorithm (BSMA) is presented for constructing minimum-cost multicast trees with delay constraints. The BSMA can handle asymmetric link characteristics and variable delay bounds on destinations, specified as real values, and minimizes the total cost of a multicast routing tree. Instead of the single-pass tree construction approach used in most previous heuristics, the new algorithm is based on a feasible-search optimization strategy that starts with the minimum-delay multicast tree and monotonically decreases the cost by iterative improvement of the delay-bounded multicast tree. The BSMA's expected time complexity is analyzed, and simulation results are provided showing that BSMA can achieve near-optimal cost reduction with fast execution     

QoS-driven multicast routing in sparse-splitting optical networks

This paper investigates the quality-of-service (QoS)-driven multicast routing problem in a sparse-splitting optical network. The main objective is to minimize the total cost of wavelength channels utilized by the light-tree while satisfying required QoS parameters. In this paper, both the optical-layer constraints (e.g., optical signal power) and application-layer requirements (e.g., end-to-end delay and inter-destination delay variation) are considered as the QoS parameters. First, integer linear programming (ILP) formulations to solve the optimal multicast routing problem with the given QoS parameters are presented. Solving the ILP formulations for large-scale networks can easily overwhelm the capabilities of state-of-the-art computing facilities, and hence, a heuristic algorithm is proposed to construct a feasible light-tree that satisfies the required QoS parameters in large-scale networks. Simulation results demonstrate the performance of the proposed heuristic algorithm in terms of the cost of utilized wavelength channels.     

A new delay‐constrained algorithm for multicast routing tree construction

New multimedia applications provide guaranteed end‐to‐end quality of service (QoS) and have stringent constraints on delay, delay‐jitter, bandwidth, cost, etc. The main task of QoS routing is to find a route in the network, with sufficient resources to satisfy the constraints. Most multicast routing algorithms are not fast enough for large‐scale networks and where the source node uses global cost information to construct a multicast tree. We propose a fast and simple heuristic algorithm (EPDT) for delay‐constrained routing problem for multicast tree construction. This algorithm uses a greedy strategy based on shortest‐path and minimal spanning trees. It combines the minimum cost and the minimum radius objectives by combining respectively optimal Prim's and Dijkstra's algorithms. It biases routes through destinations. Besides, it uses cost information only from neighbouring nodes as it proceeds, which makes it more practical, from an implementation point of view. Copyright © 2004 John Wiley & Sons, Ltd.