Multi‐path routing scheme for non‐interactive multicast communications

This paper proposes a multicast routing algorithm that makes use of multiple node‐disjoint distribution trees for its routing from the source to the multicast group members. The specialty of this scheme is that the different packets of a message between a source and destinations are routed through node‐disjoint paths to provide reliable and secure multicast communication. In this proposed routing scheme the computation of the node‐disjoint path for packet routing is done either at a centralized route moderator or in a distributed fashion at all destinations in order to avoid single point failure. An effective provision is made to enable new members to join the existing multicast trees and to prune leaving members. The performance parameters of the proposed reliable and secure multi‐path routing scheme are studied under various network conditions using GloMoSim. Copyright © 2006 John Wiley & Sons, Ltd.     

Optimal and heuristic algorithms for all‐optical group multicast in resource‐constrained WDM networks

Given a sparse‐splitting wavelength‐division multiplexing network with no wavelength converter, we study a group multicast problem that is how to transmit a number of multicast streams from the video server to multiple destinations simultaneously. To avoid the situation that the wavelengths are used up by the first few requests, one wavelength is available for each multicast request. Hence, some of destinations may not be included in the multicast trees because of the lack of wavelengths. Our goal is to construct a number of light trees with conflict‐free wavelengths for multiple requests so that the number of served clients is maximized. This problem is named as the revenue‐maximized and delay‐constrained group multicast routing problem. We first determine a set of multicast trees with the maximum number of served clients, then followed by the wavelength assignment to allocate the minimum number of wavelengths to the resulting trees. In this study, we propose two Integer Linear Programming ILP‐based algorithms for determining the optimal solutions for the light‐tree construction problem and the wavelength assignment problem, respectively. For large‐scale networks, two heuristics are introduced to solve the light‐tree construction problem approximately. A set of simulations are also provided for comparing performances of our algorithms against the other published methods. Copyright © 2016 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.     

Multicast throughput for large scale cognitive networks

In this paper, we focus on the achievable throughput of cognitive networks consisting of the primary ad hoc network (PaN) and the secondary ad hoc network (SaN). We construct PaN and SaN by placing nodes according to Poisson point processes of density n and m respectively over a unit square region. We directly study the multicast throughput of cognitive network to unify that of unicast and broadcast sessions. In order to ensure the priority of primary users in meanings of throughput, we design a metric called throughput decrement ratio (TDR) to measure the ratio of the throughput of PaN in presence of SaN to that of PaN in absence of SaN. Endowing PaN with the right to determine the threshold of the TDR, we propose multicast schemes based on TDMA and multihop routing for the two networks respectively and derive their achievable multicast throughput depending on the given threshold. Specially, we show when PaN has sparser density than SaN, to be specific, n=o(\fracm (logm)²),n=o\left({\frac{m} {(\log m)^2}}\right), and if PaN only cares about the order of its throughput, SaN can simultaneously achieve the same order of the aggregated multicast throughput as it were a stand-alone network in absence of PaN.     

Multicast wavelength assignment with sparse wavelength converters to maximize the network capacity using ILP formulation in WDM mesh networks

In general, multicast routing and wavelength assignment (MC-RWA) can be subdivided in routing and wavelength assignment issues in wavelength-division multiplexing (WDM) mesh networks. Previous studies on WDM multicast have mainly focused on WDM multicast routing. The multicast wavelength assignment problem is studied in this paper. A unicast routing path can be established by a lightpath in an all-optical network. However, in the multicasting case, a multicast routing tree can be established by a single light-tree or several lightpaths, or a combination of several light-trees and lightpaths. We propose a wavelength assignment algorithm for finding an optimal combination of lightpaths and light-trees to construct a newly required multicast session. First of all, two cost functions are given to evaluate the establishing cost for each feasible wavelength, and then find a set of wavelengths that covers all destinations with the minimal cost using Integer Linear Programming (ILP) formulation. We focus on maximizing the total number of users served in a multicast session and the network capacity. The simulation results show that the proposed algorithm can improve system resource utilization and reduce the blocking probability compared with the First-Fit algorithm.This research was partially supported by the Grant of National Science Council, R.O.C. (NSC 94-2745-E-155-007-URD).     

Online Multicasting for Network Capacity Maximization in Energy-Constrained Ad Hoc Networks

In this paper, we present new algorithms for online multicast routing in ad hoc networks where nodes are energy-constrained. The objective is to maximize the total amount of multicast message data routed successfully over the network without any knowledge of future multicast request arrivals and generation rates. Specifically, we first propose an online algorithm for the problem based on an exponential function of energy utilization at each node. The competitive ratio of the proposed algorithm is analyzed if admission control of multicast requests is permitted. We then provide another online algorithm for the problem, which is based on minimizing transmission energy consumption for each multicast request and guaranteeing that the local network lifetime is no less than gamma times of the optimum, where gamma is constant with 0 < gammaleq 1. We finally conduct extensive experiments by simulations to analyze the performance of the proposed algorithms, in terms of network capacity, network lifetime, and transmission energy consumption for each multicast request. The experimental results clearly indicate that, for online multicast routing in ad hoc wireless networks, the network capacity is proportional to the network lifetime if the transmission energy consumption for each multicast request is at the same time minimized. This is in contrast to the implication by Kar et al. that the network lifetime is proportional to the network capacity when they considered the online unicast routing by devising an algorithm based on the exponential function of energy utilization at each node.     

A general packet replication scheme for multicasting withapplication to shuffle-exchange networks

Multicasting in broadband packet switches and metropolitan networks can be achieved by first replicating the packets and then routing them to their destinations. This paper studies a simple but general replication scheme that can be applied to arbitrary interconnection-network topologies. The replication process of a packet adapts itself according to the network topology and the traffic condition. Hot spots of replication activities are diffused by this scheme which automatically migrates the replication efforts to less active network regions. The scheme can potentially be used in networks (e.g., the Manhattan-street network) in which multicasting was thought to be inherently difficult. This paper, however, focuses on the shuffle-exchange copy network for a detailed study of the replication algorithm and its implementation at the logic-diagram level. It is found that the performance of the algorithm improves with the increase in network dimensions. Cascading the copy network with a point-to-point switch makes a multicast switch. A novel strategy for reducing the memory size of its routing tables is proposed     

Quota-Based Multicast Routing in Delay-Tolerant Networks

Delay-Tolerant Networks (DTNs) are special types of network environments that are subject to delays and disruptions. Most research efforts on the DTN routing problem are focused on unicast routing but not multicast routing. Moreover existing DTN multicasting approaches are not efficient and flexible. In this paper, we propose a new multicast routing approach which can not only achieve a high delivery rate but also adapt to network conditions. Most importantly, our proposed approach need not maintain group membership. In other words, any interested users can freely join and leave any multicast groups, and this feature suitably fits into DTN environments.     

Dynamic group multicast routing with bandwidth reservations

Multicasting refers to the transmission of data from a source node to multiple destination nodes in a network. Group multicasting is a generalization of multicasting whereby every member of a group is allowed to multicast messages to other members that belong to the same group. The routing problem in this case involves the construction of a set of low cost multicast trees with bandwidth requirements, one for each member of the group for multicasting messages to other members of the group. In this paper, we examine this routing problem with an additional requirement that member nodes are allowed to join and leave the multicasting group anytime during a session. We call this problem, the dynamic group multicast routing problem (DGMRP). In this paper, we proposed three heuristic algorithms to generate a set of low cost multicast trees with dynamic group membership. Results from our empirical study shows that the one of the proposed algorithms, called Maximum bandwidth bottleneck path selection algorithm (MBBPS), achieves better utilization of bandwidth resources as compared with the other two algorithms which are based on a greedy approach. In addition MBBPS performs better in terms of cost when the bandwidth is not sufficient in the network. Copyright © 2002 John Wiley & Sons, Ltd.     

Scaling Group Communication Services with Self-adaptive and Utility-driven Message Routing

Group communication services typically generate large multicast data streams. Delivering such massive data streams to the end system nodes at the edge of the Internet has been a challenging problem in terms of high stress on the network links and high demand on network resources and routing node capacities. Most of existing research has been dedicated on geo-distance based routing with various optimizations to alleviate the performance impact on geo-distance based routing due to unpredictable network dynamics. Most representative techniques are targeted at reducing the delivery path length or optimizing routing path by utilizing network locality. In this paper, we identify the inefficiency of geo-distance based routing protocols in many existing multicast overlay networks in terms of both resource utilization and group communication efficiency. To address this issue, we develop a utility-based routing scheme (UDR) that can provide efficient group communication services in a decentralized geographical overlay network. Our approach makes three unique contributions. First, we introduce a utility function to refine the geo-distance based routing in such a way that the routing path selection can carefully incorporate both geo-distance based metric and the network latency. Second, we enhance our utility driven routing scheme with self-adaptive capability by considering the nodes?? state and network density. Thus, nodes in the multicast network can dynamically accommodate the changes of network conditions based solely on their local knowledge about the network. Third, we devise a suite of optimization techniques to minimize the maintenance cost and computational complexity of our self-adaptive and utility-drive routing scheme. We evaluate our approach through extensive experiments based on a realistic network topology model and show that the UDR method is highly scalable and it effectively enhances the multicast delivery efficiency for large scale group communication services compared to existing geo-distance based routing protocols.     

QM2RP: A QoS-Based Mobile Multicast Routing Protocol Using Multi-Objective Genetic Algorithm

With the increasing demand for real-time services in next generation wireless networks, quality-of-service (QoS) based routing offers significant challenges. Multimedia applications, such as video conferencing or real-time streaming of stock quotes, require strict QoS guarantee on bandwidth and delay parameters while communicating among multiple hosts. These applications give rise to the need for efficient multicast routing protocols, which will be able to determine multicast routes that satisfy different QoS constraints simultaneously. However, designing such protocols for optimizing multiple objectives, is computationally intractable. Precisely, discovering optimal multicast routes is an NP-hard problem when the network state information is inaccurate – a common scenario in wireless networks. Based on the multi-objective genetic algorithm (MOGA), in this paper we propose a QoS-based mobile multicast routing protocol (QM²RP) that determines near-optimal routes on demand. Our protocol attempts to optimize multiple QoS parameters, namely end-to-end delay, bandwidth requirements, and residual bandwidth utilization. Furthermore, it is fast and efficient in tackling dynamic multicast group membership information arising due to user mobility in wireless cellular networks. Simulation results demonstrate that the proposed protocol is capable of discovering a set of QoS-based, near-optimal multicast routes within a few iterations, even with imprecise network information. Among these routes one can choose the best possible one depending on the specified QoS requirements. The protocol is also scalable and yields lower multicast call-blocking rates for dynamic multicast group size in large networks.     

MPLS security: an approach for unicast and multicast environments

Multi-Protocol Label Switching (MPLS) network architecture does not protect the confidentiality of data transmitted. This paper proposes a mechanism to enhance the security in MPLS networks by using multi-path routing combined with a modified (k, n) threshold secret sharing scheme. An Internet Protocol (IP) packet entering MPLS ingress router can be partitioned into n shadow (share) packets, which are then assigned to maximally node disjoint paths across the MPLS network. The egress router at the end will be able to reconstruct the original IP packet if it receives any k share packets. The attacker must therefore tap at least k paths to be able to reconstruct the original IP packet that is being transmitted, while receiving k???1 or less of share packets makes it hard or even impossible to reconstruct the original IP packet. In this paper, we consider the multicast case in addition to the unicast. To our best knowledge, no work has been published for MPLS multicast security. We have implemented our model and measured its time complexity on variable packets size.     

A ring-based multicast routing topology with QoS support in wireless mesh networks

Wireless mesh networking (WMN) is an emerging technology for future broadband wireless access. The proliferation of the mobile computing devices that are equipped with cameras and ad hoc communication mode creates the possibility of exchanging real-time data between mobile users in wireless mesh networks. In this paper, we argue for a ring-based multicast routing topology with support from infrastructure nodes for group communications in WMNs. We study the performance of multicast communication over a ring routing topology when 802.11 with RTS/CTS scheme is used at the MAC layer to enable reliable multicast services in WMNs. We propose an algorithm to enhance the IP multicast routing on the ring topology. We show that when mesh routers on a ring topology support group communications by employing our proposed algorithms, a significant performance enhancement is realized. We analytically compute the end-to-end delay on a ring multicast routing topology. Our results show that the end-to-end delay is reduced about 33 %, and the capacity of multicast network (i.e., maximum group size that the ring can serve with QoS guarantees) is increased about 50 % as compared to conventional schemes. We also use our analytical results to develop heuristic algorithms for constructing an efficient ring-based multicast routing topology with QoS guarantees. The proposed algorithms take into account all possible traffic interference when constructing the multicast ring topology. Thus, the constructed ring topology provides QoS guarantees for the multicast traffic and minimizes the cost of group communications in WMNs.     

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     

Multicast capacity of optical ring network with hotspot traffic: The bi-directional WDM packet ring

Packet-switching WDM ring networks with a hotspot transporting unicast, multicast, and broadcast traffic are important components of high-speed metropolitan area networks. For an arbitrary multicast fanout traffic model with uniform, hotspot destination, and hotspot source packet traffic, we analyze the maximum achievable long-run average packet throughput, which we refer to as multicast capacity, of bi-directional shortest path routed WDM rings. We identify three segments that can experience the maximum utilization, and thus, limit the multicast capacity. We characterize the segment utilization probabilities through bounds and approximations, which we verify through simulations. We discover that shortest path routing can lead to utilization probabilities above one half for moderate to large portions of hotspot source multi- and broadcast traffic, and consequently multicast capacities of less than two simultaneous packet transmissions. We outline a one-copy routing strategy that guarantees a multicast capacity of at least two simultaneous packet transmissions for arbitrary hotspot source traffic.     

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.     

Solve the Tree Setup Problem and Minimize Control Overhead for High-Density Members in Delay-Bounded Distributed Multicast Networks

The multicast routing is one of the important techniques for achieving multicast applications in wireless networks, e.g., real-time video multicasting in Vehicular Ad-hoc NETwork (VANET). The main objective of a delay-bounded multicast algorithm is to determine the least-cost multicast tree while satisfying the delay-bounded requirement for multicasting voice/video transmission. Several multicast algorithms have been proposed, some disadvantages have not yet solved, including: (1) yielding a large numbers of control messages, (2) yielding dangling nodes, (3) exhibiting the cycle-free problem, (4) increasing the tree setup time, (5) suffering from the tree setup-break problem, etc. Thus, this paper proposes an adaptive distributed multicast routing (ADMR) algorithm to guarantee cycle-free, to overcome the tree setup-break and the dangling nodes problems while achieving the least-cost delay-bounded multicast tree for high density member multicast networks. Numerical results demonstrate that ADMR significantly outperforms the compared algorithms in the number of control messages and the setup convergence time. Finally, the worst case time complexity and the number of messages of ADMR are analyzed, which requires O(n · (m?+?c)) time and O(2m?+?2c) messages, respectively. The analyzed results of ADMR are lower than that of the compared algorithms.     

Dynamic Multicast Session Provisioning in WDM Optical Networks with Sparse Splitting Capability

In this work, we study dynamic provisioning of multicast sessions in a wavelength-routed sparse splitting capable WDM network with an arbitrary mesh topology where the network consists of nodes with full, partial, or no wavelength conversion capabilities and a node can be a tap-and-continue (TaC) node or a splitting and delivery (SaD) node. The objectives are to minimize the network resources in terms of wavelength-links used by each session and to reduce the multicast session blocking probability. The problem is to route the multicast session from each source to the members of every multicast session, and to assign an appropriate wavelength to each link used by the session. We propose an efficient online algorithm for dynamic multicast session provisioning. To evaluate the proposed algorithm, we apply the integer linear programming (ILP) optimization tool on a per multicast session basis to solve off-line the optimal routing and wavelength assignment given a multicast session and the current network topology as well as its residual network resource information. We formulate the per session multicast routing and wavelength assignment problem as an ILP. With this ILP formulation, the multicast session blocking probability or success probability can then be estimated based on solving a series of ILPs off-line. We have evaluated the effectiveness of the proposed online algorithm via simulation in terms of session blocking probability and network resources used by a session. Simulation results indicate that our proposed computationally efficient online algorithm performs well even when a fraction of the nodes are SaD nodes.     

Analysis of tree‐based multicast routing in wireless sensor networks with varying network metrics

Wireless ad hoc and sensor networks are emerging with advances in electronic device technology, wireless communications and mobile computing with flexible and adaptable features. Routing protocols act as an interface between the lower and higher layers of the network protocol stack. Depending on the size of target nodes, routing techniques are classified into unicast, multicast and broadcast protocols. In this article, we give analysis and performance evaluation of tree‐based multicast routing in wireless sensor networks with varying network metrics. Geographic multicast routing (GMR) and its variations are used extensively in sensor networks. Multicast routing protocols considered in the analytical model are GMR, distributed GMR, demand scalable GMR, hierarchical GMR, destination clustering GMR and sink‐initiated GMR. Simulations are given with comparative analysis based on varying network metrics such as multicast group size, number of sink nodes, average multicast latency, number of clusters, packet delivery ratio, energy cost ratio and link failure rate. Analytical results indicate that wireless sensor network multicast routing protocols operate on the node structure (such as hierarchical, clustered, distributed, dense and sparse networks) and application specific parameters. Simulations indicate that hierarchical GMR is used for generic multicast applications and that destination clustering GMR and demand scalable GMR are used for distributed multicast applications. Copyright © 2012 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.