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.     

基于最短路径树的节点删除动态路由算法

提出一种基于最短路径树的节点删除动态路由算法。算法建立一个最短路径树更新集合,该集合包括被删除节点的断裂子树所有节点和其它节点连接的边,利用子树的结构信息,对子树节点的直系子孙节点和祖先节点进行更新,采用Dijkstra算法对其它子树节点进行更新。实验结果表明,该算法能有效减少节点更新计算次数。     

On properties of multicast routing trees

In the last several years we witnessed the proliferation of multimedia applications on the Internet. One of the unavoidable techniques to support this type of communication is multicasting. However, even a decade after its initial proposal, multicast is still not widely deployed. One of the reasons is the lack of a solid business model. If the gain and the cost of multicast could be predicted, network operators might be encouraged to deploy multicast on a larger scale. In this paper we propose analytical expressions that could be used to estimate the gain of network‐layer multicast. We show that the theoretical model matches extensive simulation and Internet measurement results remarkably well. Furthermore, we examine the reliability of traceroute data and of traceroutes‐based conclusions. We investigate the node degree distributions in the Internet maps obtained from CAIDA and RIPE and we show the divergency of our results with those obtained by other researchers. We further focus on the analysis of multicast trees based on traceroute data. Only few results have been available on the node degree distribution of multicast routing trees which provided contradictory conclusions. Our results seem to indicate that the node degrees follow power laws only for a large number of multicast users. Copyright © 2005 John Wiley & Sons, Ltd.     

GPSPA: a new adaptive algorithm for maintaining shortest path routing trees in stochastic networks

This paper presents a new efficient solution to the Dynamic Shortest Path Routing Problem, using the principles of Generalized Pursuit Learning. It proposes an efficient algorithm for maintaining shortest path routing trees in networks that undergo stochastic updates in their structure. It involves finding the shortest path in a stochastic network, where there are continuous probabilistically based updates in link‐costs. In vast, rapidly changing telecommunications (wired or wireless) networks, where links go up and down continuously and rapidly, and where there are simultaneous random updates in link costs, the existing algorithms are inefficient. In such cases, shortest paths need to be computed within a very short time (often in the order of microseconds) by scanning and processing the minimal number of nodes and links. The proposed algorithm, referred to as the Generalized Pursuit Shortest Path Algorithm (GPSPA), will be very useful in this regard, because after convergence, it seems to be the best algorithm to‐date for this purpose. Indeed, it has the advantage that it can be used to find the shortest path within the ‘statistical’ average network, which converges irrespective of whether there are new changes in link‐costs or not. Existing algorithms are not characterized by such a behaviour inasmuch as they would recalculate the affected shortest paths after each link‐cost update. The algorithm has been rigorously evaluated experimentally, and it has been found to be a few orders of magnitude superior to the algorithms available in the literature. Copyright © 2004 John Wiley & Sons, Ltd.     

加权的基于多播节点的多播路由算法

在许多多播应用中,降低多播树网络费用非常重要.本文提出了加权的基于多播节点的多播路由算法（WDDMC算法）.由于改变了DDMC（Destination-Driven routing for low-cost Multicast ）算法中的指示函数,适当降低了多播节点作为中间节点的优先级,提高非多播节点作为中间节点的优先级,从而使得多播树更接近最小Steiner树.在随机网络上的仿真结果表明,WDDMC算法的多播树网络费用优于DDMC算法.该算法的复杂度与DDMC算法完全相同.     

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

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

Enabling scalable multicast protocols using dynamic overlap tree path

The scalability of a multicast protocol is a very critical issue when it is implemented on a global scale. The number of forwarding states that are maintained at each multicast router explodes when the number of multicast groups grows exponentially as in the case of global Internet. In this paper we describe a technique, called dynamic overlap tree path (DOTP), to reduce the forwarding states that need to be maintained in multicast routers and hence improve the scalability of existing multicast protocols. This technique, which can be incorporated in both the dense and sparse modes of multicast protocols, dynamically finds overlapped unbranched tree paths and merges their corresponding forwarding states to reduce the storage requirement in multicast routers. It does not introduce any additional control‐message overheads through the reduction process. OPNET simulation results show that the overall average forwarding‐state table size of the simulated networks can be reduced by about 30 per cent on the average. Copyright © 2001 John Wiley & Sons, Ltd.     

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多播路由算法

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

A protocol for scalable loop-free multicast routing

In network multimedia applications such as multiparty teleconferencing, users often need to send the same information to several (but not necessarily all) other users. To manage such one-to-many or many-to-many communication efficiently in wide-area internetworks, it is imperative to support and perform multicast routing. Multicast routing sends a single copy of a message from a source to multiple receivers over a communication link that is shared by the paths to the receivers. Loop-freedom is an especially important consideration in multicasting because applications using multicasting tend to be multimedia and bandwidth intensive, and loops in multicast routing duplicate looping packets. We present and verify a new multicast routing protocol, called multicast Internet protocol (MIP), which offers a simple and flexible approach to constructing both group-shared and shortest-paths multicast trees. MIP can be sender-initiated or receiver-initiated or both; therefore, it can be tailored to the particular nature of an application's group dynamics and size. MIP is independent of the underlying unicast routing algorithms used. MIP is robust and adapts under dynamic network conditions (topology or link cost changes) to maintain loop-free multicast routing. Under stable network conditions, MIP has no maintenance or control message overhead. We prove that MIP is loop-free at every instant, and that it is deadlock-free and obtains multicast routing trees within a finite time after the occurrence of an arbitrary sequence of topology or unicast changes     

GMNF-DVMRP: an enhanced version of distance vector multicast routing protocol

In this paper we propose an enhancement to the Distance Vector Multicast Routing Protocol (DVMRP), called ‘Group Membership Near First DVMRP’ (GMNF-DVMRP), to decrease the network cost (NC) of the multicast tree formed by DVMRP. A simulation is implemented to compare our enhanced version and the original DVMRP. We find that our method saves about 5%–7% of NC of the multicast tree formed by DVMRP. © 1998 John Wiley & Sons, Ltd.     

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

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

多媒体通信的成组多点广播路由算法

多点广播是一源点传送信息到多个目的节点,成组多点广播是一组节点内部互相进行多点广播。成组多点广播的路由算法是为组内的每一个节点建立一棵路由树,用于点到多点的广播通信。本文提出一种新的成组广播路由算法,它比传统的成组广播路由算法在性能上有了一定的提高,同时更为简洁。     

Tree-based differential evolution algorithm for QoS multicast routing

Differential evolution(DE)algorithm has attracted more and more attention due to its fast optimization performance and good stability.When DE algorithm is applied into multi-constrained multicast routing optimization problem,a common solution to such problem is to merge the paths into a tree after finding paths from the source node to each destination node.This method maybe obtains the better result,but it can consume a lot of computational time.To solve the problem,a tree-based DE algorithm is introduced in this paper.The central operations of the algorithm are realized with tree structure.This method saves the time of finding paths and integrating them to construct a multicast tree.The experiments show that the proposed algorithm can achieve higher success rate than several common algorithms with much smaller running time for different networks.     

A Distributed Multicast Routing Scheme for Multi-Layered Satellite IP Networks

In this paper, a distributed multicast routing scheme is introduced for multi-layered satellite IP networks, which include GEO, MEO, and LEO layers. This scheme aims to minimize the total cost of multicast trees in the satellite network. Multicast trees are constructed and maintained in the dynamic satellite network topology in a distributed manner. Simulation results are provided to evaluate the performance of the new scheme in terms of end-to-end delay and multicast tree cost.     

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.     

Lightweight PIM—a new multicast routing protocol

Multicast holds out great promise to significantly reduce network load between the sender and a group of receivers by delivering a single data stream to many recipients. Protocol‐Independent Multicast (PIM) Sparse Mode and its variant PIM Source‐Specific Multicast (PIM SSM) are the most widely used IP multicast protocols. Protocols offer low latency data delivery capabilities with relatively high reliability and are characterized by large signaling overhead. This article presents a new multicast protocol, called Lightweight PIM (LPIM), tackling the main problem hindering widespread usage of IP multicast protocols, which is a large volume of signaling traffic. Given the existing usability of the PIM family protocols, a decision was made to base the new LPIM protocol on PIM SSM. The improvements used in LPIM lead to a considerable reduction of state data and signaling messages required by LPIM as compared with PIM SSM. Similar to its predecessor, LPIM is capable of handling large groups, although with significantly lower overhead. Copyright © 2012 John Wiley & Sons, Ltd.     

基于贪婪算法的WDM网络组播路由算法的研究

文章首先用贪婪算法找出在现有网络结构中完成任务所需的波长数较少的波长集,然后依据其上每条链路的权值,用最短路径算法生成一棵组播树,使其跳数和阻塞率较低,以保证网络能够在使用较少波长资源的情况下,快速、有效地传送数据.     

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

提出了一种适合目的节点动态加入的、时延受限低代价多播路由的启发式算法DLHMA算法。该算法基于MPH算法的基本思想进行扩展,在满足时延限制条件和多播树代价增加最小的基础上,逐步将目的节点添加到多播树上。最后,证明了算法的正确性,分析了算法的动态性,并进行了仿真实验。结果表明,该算法可以实现新加目的节点的动态加入,并保证所获得多播树的低代价。     

An efficient mesh‐based multicast routing protocol in mobile ad hoc networks

Mesh‐based multicast routing protocols for mobile ad hoc networks (MANETs) build multiple paths from senders to receivers to deliver packets even in the presence of links breaking. This redundancy results in high reliability/robustness but may significantly increase packet overhead. This paper proposes a mesh‐based multicast protocol, called centered protocol for unified multicasting through announcements (CPUMA), that achieves comparable reliability as existing mesh‐based multicast protocols, however, with significantly much less data overhead. In CPUMA, a distributed core‐selection and maintenance algorithm is used to find the source‐centric center of a shared mesh. We leverage data packets to center the core of each multicast group shared mesh instead of using GPS or any pre‐assignment of cores to groups (the case of existing protocols). The proposed centering scheme allows reducing data packet overhead and creating forwarding paths toward the nearest mesh member instead of the core to reduce latency. We show, via simulations, that CPUMA outperforms existing multicast protocols in terms of data packet overhead, and latency while maintaining a constant or better packet delivery ratio, at the cost of a small increase in control overhead in a few scenarios. Copyright © 2010 John Wiley & Sons, Ltd.