Directional core selection approach and dynamic tree reorganization for delay and delay variation multicast routing

Multicast communication constrained by end‐to‐end and interdestination delay variation is known as delay and delay variation–bounded multicast. These constraints are salient for real‐time multicast communications. In this paper, we propose a directional core selection algorithm for core selection and delay variation–bounded multicast tree generation. Another algorithm, based on k‐shortest paths, is proposed to further decrease the interdestination delay variation of the trees generated by directional core selection. We also propose the dynamic version of both algorithms that respond to dynamic join and leave requests to the ongoing multicast session by reorganizing the tree and avoiding session disruption. Simulations show that the proposed algorithms surpass existing algorithms in end‐to‐end delay, interdestination delay variation, execution time, and failure probability.     

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

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

多信道广播组总延误端到端延迟变化路由问题

在高速分组交换环境中,提出了构造多信道广播树,且满足实时交互性应用端到端变化要求的总延误问题.多信道广播路由将寻找从源到包括所有多信道广播终端的一棵有根树.在多媒体应用中,关于路由问题有两种要求:最小总延误和延迟变化.在实践中链路延迟和终端延迟的概念是有区别的.重新定义延迟的概念,也就是端到端的路径延迟定义为截止延迟或界定延迟,延误成员数的延迟定义为松驰延迟.终端的松驰延迟具有的特征是沿着一棵树从源到任何一个终端的累积延迟可以超过松驰延迟的值.确定这样一棵约束树的问题是NP-完全的.由时间的复杂性和动态成员的灵活性,提出了一个有效的启发式算法.     

Algorithms for delay constrained group multicast routing

Multicast routing allows network sources to use network resources efficiently by sending only a single copy of data to all group members. In the delay constrained group multicast routing problem (DCGMRP), every group member is also a source, and has an individual minimal delay and bandwidth requirement. The routing algorithm must, for each member of the group, construct a source‐based routing tree spanning all the other member nodes without exceeding the capacities of the traversed links, while satisfying the stated delay constraints. Previous work adopted the direct, intuitive approach by first creating a source‐based multicast tree independently for each member node, and then iteratively locating network links whose capacity constraint are violated and eliminating the violation by rerouting the trees. In this paper, we investigate a number of efficient and effective algorithms, DCGM _ IA ⁺, DCGM _ GR and DCGM _ CP , for solving DCGMRP and compare their performance with previous proposals. Through extensive experiments, our proposals are shown to outperform previous algorithms in constructing group multicast trees with low costs and high success ratios. Copyright © 2005 John Wiley & Sons, Ltd.     

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

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

基于延时及带宽约束的组播路由算法

本文分析了网络中基于延时和带宽受限的组播路由优化问题,提出了一种新的启发式算法,并进行了实验和分析。文中构造的路由方案成功地解决了当网络中存在多组组播通信时的QoS路由选择问题。此方案不仅保证了组播业务所需的带宽、端到端延时、减小了丢包率,而且有效地控制了算法的复杂性并可适用于大规模的网络中。     

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

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

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.     

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.     

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

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

GPM: A generic and scalable P2P model that optimizes tree depth for multicast communications

Group communications (real‐time and non‐real‐time) refer to one‐to‐many or many‐to‐many communications. On the one hand, multicast is considered as an appropriate solution for supporting group communication‐oriented applications (we distinguish IP network multicast from application layer multicast). On the other hand, peer‐to‐peer model tends to be a good candidate for supporting today Internet applications (e.g. P2P IPTV, P2P VoIP, etc.). In this context, P2P has attracted significant interest in the recent years. This is mainly due to its properties that also make P2P well adapted to today social networks. In this paper, we propose GPM (Generic P2P Multicast): a novel generic and scalable approach, that optimizes multicast tree depth in P2P networks (structured and unstructured), and contributes to control the network overlay latency. For multicast tree construction, the approach we propose is based on a distributed algorithm using a specific data structures (adjacency and forwarding matrixes). GPM model inherits from P2P attributes such as scalability, flexibility and fault tolerance, while taking into consideration the respective characteristics of one‐to‐many and many‐to‐many type of applications. We also give a performance evaluation for validation and comparison purposes while considering some main existing application layer multicast protocols. Copyright © 2011 John Wiley & Sons, Ltd.     

Power aware scalable multicast routing protocol for MANETs

Multicasting is an effective way to provide group communication. In mobile ad hoc networks (MANETs), multicasting can support a wide variety of applications that are characterized by a close degree of collaboration. Since MANETs exhibit severe resource constraints such as battery power, limited bandwidth, dynamic network topology and lack of centralized administration, multicasting in MANETs become complex. The existing multicast routing protocols concentrate more on quality of service parameters like end‐to‐end delay, jitter, bandwidth and power. They do not stress on the scalability factor of the multicast. In this paper, we address the problem of multicast scalability and propose an efficient scalable multicast routing protocol called ‘Power Aware Scalable Multicast Routing Protocol (PASMRP)’ for MANETs. PASMRP uses the concept of class of service with three priority levels and local re‐routing to provide scalability. The protocol also ensures fair utilization of the resources among the nodes through re‐routing and hence the lifetime of the network is increased. The protocol has been simulated and the results show that PASMRP has better scalability and enhanced lifetime than the existing multicast routing protocols. Copyright © 2005 John Wiley & Sons, Ltd.     

A resource‐tuned QoS multicast routing protocol

This paper presents a novel framework for quality‐of‐service (QoS) multicast routing with resource allocation that represents QoS parameters, jitter delay, and reliability, as functions of adjustable network resources, bandwidth, and buffer, rather than static metrics. The particular functional form of QoS parameters depends on rate‐based service disciplines used in the routers. This allows intelligent tuning of QoS parameters as functions of allocated resources during the multicast tree search process, rather than decoupling the tree search from resource allocation. The proposed framework minimizes the network resource utilization while keeping jitter delay, reliability, and bandwidth bounded. This definition makes the proposed QoS multicast routing with resource allocation problem more general than the classical minimum Steiner tree problem. As an application of our general framework, we formulate the QoS multicast routing with resource allocation problem for a network consisting of generalized processor sharing nodes as a mixed‐integer quadratic program and find the optimal multicast tree with allocated resources to satisfy the QoS constraints. We then present a polynomial‐time greedy heuristic for the QoS multicast routing with resource allocation problem and compare its performance with the optimal solution of the mixed‐integer quadratic program. The simulation results reveal that the proposed heuristic finds near‐optimal QoS multicast trees along with important insights into the interdependency of QoS parameters and resources.     

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

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

Lifetime optimization for reliable broadcast and multicast in wireless ad hoc networks

In this paper, we consider the reliable broadcast and multicast lifetime maximization problems in energy‐constrained wireless ad hoc networks, such as wireless sensor networks for environment monitoring and wireless ad hoc networks consisting of laptops or PDAs with limited battery capacities. In packet loss‐free networks, the optimal solution of lifetime maximization problem can be easily obtained by tree‐based algorithms. In unreliable networks, we formulate them as min–max tree problems and prove them NP‐complete by a reduction from a well‐known minimum degree spanning tree problem. A link quality‐aware heuristic algorithm called Maximum Lifetime Reliable Broadcast Tree (MLRBT) is proposed to build a broadcast tree that maximizes the network lifetime. The reliable multicast lifetime maximization problem can be solved as well by pruning the broadcast tree produced by the MLRBT algorithm. The time complexity analysis of both algorithms is also provided. Simulation results show that the proposed algorithms can significantly increase the network lifetime compared with the traditional algorithms under various distributions of error probability on lossy wireless links. Copyright © 2012 John Wiley & Sons, Ltd.     

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

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

Multicast routing with end-to-end delay and delay variationconstraints

We study the problem or constructing multicast trees to meet the quality of service requirements of real-time interactive applications operating in high-speed packet-switched environments. In particular, we assume that multicast communication depends on: (1) bounded delay along the paths from the source to each destination and (2) bounded variation among the delays along these paths. We first establish that the problem of determining such a constrained tree is NP-complete. We then present a heuristic that demonstrates good average case behavior in terms of the maximum interdestination delay variation. The heuristic achieves its best performance under conditions typical of multicast scenarios in high speed networks. We also show that it is possible to dynamically reorganize the initial tree in response to changes in the destination set, in a way that is minimally disruptive to the multicast session     

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

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

适于低轨卫星IP网络的特定源组播算法

为了解决低轨卫星IP网络中现有特定源组播算法的信道资源浪费问题,本文提出了一套新的特定源组播算法,即基于核心群的特定源组播算法(CSSM)和加权的CSSM算法(w-CSSM).CSSM算法以源节点作为初始核心群,通过核心群和剩余组成员的最短路径方法逐步扩展直至整棵组播树构建完成,所得的树代价最小,从而大大提高了网络的带宽利用率和传输效率.在w-CSSM算法中,加权因子可以自适应调整以适度增大树代价、降低端到端传播时延,以支持某些有严格端到端时延要求的实时组播业务.通过与低轨卫星IP网络中典型特定源组播算法MRA的仿真比较,可以看出CSSM和w-CSSM算法的树代价性能比MRA有较大改善,不过端到端传播时延略高.     

Placing and maintaining a core node in wirelessad hoc networks

Wireless ad hoc networks are characterized by several performance metrics, such as bandwidth, transport, delay, power, etc. These networks are examined by constructing a tree network. A core node is usually chosen to be the median or center of the multicast tree network with a tendency to minimize a performance metric, such as delay or transport. In this paper, we present a new efficient strategy for constructing and maintaining a core node in a multicast tree for wireless ad hoc networks undergoing dynamic changes, based on local information. The new core (centdian) function is defined by a convex combination signifying total transport and delay metrics. We provide two bounds of O(d) and O(d+l) time for maintaining the centdian using local updates, where l is the hop count between the new center and the new centdian, and d is the diameter of the tree network. We also show an O(n log n) time solution for finding the centdian in the Euclidian complete network. Finally, an extensive simulation for the construction algorithm and the maintenance algorithm is presented along with an interesting observation. Copyright © 2009 John Wiley & Sons, Ltd.