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.     

Agent Driven Delay and Power Constrained Multicast Routing in Mobile Ad Hoc Networks by Using ANFIS

Group communication applications in Mobile Ad hoc NETworks (MANETs) require stringent bounds on Quality of Service (QoS) parameters. In this paper, we propose an agent driven QoS mesh based multicast routing scheme in MANET that satisfies the user requirements with good reasoning by using adaptive neuro-fuzzy inference system (ANFIS). Four types of agents are used in the scheme: Multicast administer, ANFIS, Route inventing and Guard agents. The proposed scheme operates in following steps. (1) ANFIS agent at the source node optimizes membership functions of QoS parameters according to the user QoS requirement. It also computes QoS factor for different combinations of parameter values from optimized membership functions. (2) Route inventing mobile agent carries the QoS requirement, set of parameter values and their corresponding QoS factors to reach multicast receivers through intermediate nodes by using selective flooding and agent cloning. Multicast administer agent (MAA) at the intermediate node decides its QoS satisfiability. (3) Route inventing mobile agents trace back the traversed path by marking QoS nodes. They facilitate MAA at the source node to construct QoS mesh between source and destinations. (4) MAA at the source node selects a shortest path to reach each of the multicast receivers from the constructed QoS mesh, and (5) Guard mobile agent is employed for the link/node failures and management of the group. Our proposed scheme performs better than fuzzy based, and autonomic QoS multicast routing schemes.     

A practical network coding and routing scheme based on maximum flow combination

Network coding is a novel field of information theory and coding theory. It is a breakthrough over the traditional store‐and‐forward routing methods by allowing coding of two or more packets together. From an information flow aspect, multiple flows could be overlapped in a routing scheme. Hence the theoretical upper bound of multicast capacity could be achieved by network coding. In this project, a complete routing and coding scheme is constructed to realize the maximum multicast transportation task. In order to implement the scheme, the paths of multiple max‐flows are determined. Edges are divided into overlapped and normal type based on the merged max‐flows. The transmitting data are represented using packets in a specific format. Multicast, forward and coding operations are defined to transmit data at the nodes. The nodes are classified according to the type of operation. A dynamic coding and routing algorithm is proposed to route packets gradually from source node to destinations in topological sorting order by the three operations on the path of merged max‐flows. We show that the use of simple XOR operations can satisfy most of the network topologies. The running time of the algorithm presented here is less than 1 second for most of the benchmark and random datasets. Copyright © 2012 John Wiley & Sons, Ltd.     

Queue‐based multiple path load balancing routing protocol for MANETs

Congestion in the network is the main cause for packet drop and increased end‐to‐end transmission delay of packet between source and destination nodes. Congestion occurs because of the simultaneous contention for network resources. It is very important to efficiently utilize the available resources so that a load can be distributed efficiently throughout the network. Otherwise, the resources of heavily loaded nodes may be depleted very soon, which ultimately affects network performances. In this paper, we have proposed a new routing protocol named queue‐based multiple path load balancing routing protocol. This protocol discovers several node‐disjoint paths from source to destination nodes. It also finds minimum queue length with respect to individual paths, sorts the node‐disjoint paths based on queue length, and distributes the packets through these paths based on the minimum queue length. Simulation results show that the proposed routing protocol distributes the load efficiently and achieves better network performances in terms of packet delivery ratio, end‐to‐end delay, and routing overhead. Copyright © 2016 John Wiley & Sons, Ltd.     

QoS multicast routing by using multiple paths/trees in wireless ad hoc networks

In this paper, we investigate the issues of QoS multicast routing in wireless ad hoc networks. Due to limited bandwidth of a wireless node, a QoS multicast call could often be blocked if there does not exist a single multicast tree that has the requested bandwidth, even though there is enough bandwidth in the system to support the call. In this paper, we propose a new multicast routing scheme by using multiple paths or multiple trees to meet the bandwidth requirement of a call. Three multicast routing strategies are studied, SPT (shortest path tree) based multiple-paths (SPTM), least cost tree based multiple-paths (LCTM) and multiple least cost trees (MLCT). The final routing tree(s) can meet the user’s QoS requirements such that the delay from the source to any destination node shall not exceed the required bound and the aggregate bandwidth of the paths or trees shall meet the bandwidth requirement of the call. Extensive simulations have been conducted to evaluate the performance of our three multicast routing strategies. The simulation results show that the new scheme improves the call success ratio and makes a better use of network resources.     

Restricted dynamic Steiner trees for scalable multicast in datagramnetworks

The paper addresses the issue of minimizing the number of nodes involved in routing over a multicast tree and in the maintenance of such a tree in a datagram network. It presents a scheme where the tree routing and maintenance burden is laid only upon the source node and the destination nodes associated with the multicast tree. The main concept behind this scheme is to view each multicast tree as a collection of unicast paths and to locate only the multicast source and destination nodes on the junctions of their multicast tree. The paper shows that despite this restriction, the cost of the created multicast trees is not necessarily higher than the cost of the trees created by other algorithms that do not impose the restriction and therefore require all nodes along the data path of a tree to participate in routing over the tree and in the maintenance of the tree     

An integrated routing and admission control mechanism for real‐time multicast connection establishment

There are two major difficulties in real‐time multicast connection setup. One is the design of an efficient distributed routing algorithm which optimizes the network cost of routing trees under the real‐time constraints. The other is the integration of routing with admission control into one single phase of operations. This paper presents a real‐time multicast connection setup mechanism, which integrates multicast routing with real‐time admission control. The proposed mechanism performs the real‐time admission tests on a cost optimal tree (COT) and a shortest path tree (SPT) in parallel, aiming at optimizing network cost of the routing tree under real‐time constraints. It has the following important features: (1) it is fully distributed; (2) it achieves sub‐optimal network cost of routing trees; (3) it takes less time and less network messages for a connection setup. Copyright © 2001 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.     

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.     

A scalable multicast routing protocol for building shortest path trees

Scalability is a great concern in the design of multicast routing protocols for the global Internet. Building shortest path trees (SPT) is currently one of the most widely used approaches to supporting multicast routing because of the simplicity and low per‐destination cost of such trees. However, the construction of an SPT typically involves high protocol overhead, which leads to the scalability problem as the number of concurrent multicast sessions increases. In this paper, we present a destination‐initiated shortest path tree (DSPT) routing protocol. The design objective is to effectively reduce the protocol overhead associated with SPT constructions for providing scalable multicast. To achieve this objective, we introduce destination‐initiated joining operations in constructing SPTs. With DSPT, each router receiving a request to join a specific multicast group makes a local decision on selecting its parent node through which it connects to the existing tree. A source‐rooted SPT is built as a result of such collaborative operations at nodes. DSPT requires only limited routing information at routers. Analytical results demonstrate that DSPT scales well with respect to computation, storage and communication overhead when the number of concurrent multicast requests is large. Simulation experiments are also conducted to verify the correctness of the theoretically deduced analytical results. Copyright © 2006 John Wiley & Sons, Ltd.     

Secure multicast routing protocols in mobile ad‐hoc networks

A mobile ad‐hoc network (MANET) is a collection of autonomous nodes that communicate with each other by forming a multi‐hop radio network. Routing protocols in MANETs define how routes between source and destination nodes are established and maintained. Multicast routing provides a bandwidth‐efficient means for supporting group‐oriented applications. The increasing demand for such applications coupled with the inherent characteristics of MANETs (e.g., lack of infrastructure and node mobility) have made secure multicast routing a crucial yet challenging issue. Recently, several multicast routing protocols (MRP) have been proposed in MANETs. Depending on whether security is built‐in or added, MRP can be classified into two types: secure and security‐enhanced routing protocols, respectively. This paper presents a survey on secure and security‐enhanced MRP along with their security techniques and the types of attacks they can confront. A detailed comparison for the capability of the various routing protocols against some known attacks is also presented and analyzed. Copyright © 2013 John Wiley & Sons, Ltd.     

Agent‐based secure routing for underwater acoustic sensor networks

The underwater networks have severe security implications and are vulnerable to various types of attacks such as selective forwarding, wormhole, and sinkhole. Neighbor discovery, a fundamental requirement for routing is vulnerable to wormhole attack, which enables false neighbor acceptance, thereby degrading the routing performance. The proposed agent‐based secured routing scheme enhances the quality of service by discovering the wormhole resilient secure neighbors and route the information through the secure path. This scheme uses 4 agencies, namely, security, routing, underwater gateway, and vehicle, which are embedded with static and mobile agents. (1) Agents in security agency of a node discover secured neighbors by using the direction of arrival estimation and authentication, (2) agents in routing agency of a node establish secured routes from source to surface gateway, (3) agents in Underwater Gateway Agency communicate with Autonomous Underwater Vehicles (AUVs) and underwater nodes for key distribution, and (4) vehicle traversing agency in AUV coordinates with Underwater Gateway Agency for changing AUVs traversal to cover the isolated network area. The proposed scheme depicts the improved performance compared to basic neighbor discovery and channel aware routing protocol in terms of failure detection, energy consumption, and overheads.     

A distributed algorithm of delay-bounded multicast routing formultimedia applications in wide area networks

Multicast routing is to find a tree which is rooted from a source node and contains all multicast destinations. There are two requirements of multicast routing in many multimedia applications: optimal network cost and bounded delay. The network cost of a tree is defined as the sum of the cost of all links in the tree. The bounded delay of a routing tree refers to the feature that the accumulated delay from the source to any destination along the tree shall not exceed a prespecified bound. This paper presents a distributed heuristic algorithm which generates routing trees having a suboptimal network cost under the delay bound constraint. The proposed algorithm is fully distributed, efficient in terms of the number of messages and convergence time, and flexible in dynamic membership changes. A large amount of simulations have been done to show the network cost of the routing trees generated by our algorithm is similar to, or even better than, other existing algorithms     

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.     

Message trust‐based secure multipath routing protocol for opportunistic networks

Opportunistic networks (OppNets) are composed of wireless nodes opportunistically communicating with each other. These networks are designed to operate in a challenging environment characterized by high delay, intermittent connectivity, and no guarantee of fixed path between the sender and the destination nodes. One of the most vital issues in designing and maintaining practical networks over a time period is the security of the messages flowing in OppNets. This paper proposes a new method called message trust‐based secure multipath routing protocol (MT‐SMRP) for opportunistic networks. Various routing protocols such as ProPHet, Epidemic, and HiBOp, to name a few, have been proposed for OppNets, but none of these have applied a secure multipath routing technique. The proposed MT‐SMRP scheme relays the message to the destination through the disjoint paths, each applying a soft‐encryption technique to prevent message fabrication attacks. Simulations are conducted using the Haggle Infocom'06 real mobility data traces, showing that when time‐to‐live is varied, (1) the proposed MT‐SMRP scheme outperforms D‐MUST by 18.10%, 7.55%, 3.275%, respectively, in terms of delivery probability, messages dropped, and average latency; (2) it also outperforms SHBPR by 21.30%, 7.44%, and 4.85%, respectively, in terms of delivery probability, messages dropped, and average latency. Under similar performance metrics, the performance of MT‐SMRP is also shown to be better than that of D‐MUST and SHBPR when the buffer size (respondents. the message generation interval) is varied.     

Morphing distribution trees—On the evolution of multicast states under mobility and an adaptive routing scheme for mobile SSM sources

Source Specific Multicast (SSM) promises a wider dissemination of group distribution services than Any Source Multicast, as it relies on simpler routing strategies with reduced demands on the infrastructure. However, SSM is designed for á priori known and changeless addresses of multicast sources and thus withstands any easy extension to mobility. Up until now only few approaches arose from the Internet research community, leaving SSM source mobility as a major open problem. The purpose of this paper is twofold. At first we analyze characteristic properties of multicast shortest path trees evolving under source mobility. Analytically and by stochastic simulations we derive measures on the complexity of SSM routing under source mobility. At second we introduce a straightforward extension to multicast routing for transforming (morphing) source specific delivery trees into optimal trees rooted at a relocated source. All packet forwarding is done free of tunneling. Multicast service disruption and signaling overhead for the algorithms remain close to minimal. Further on we evaluate the proposed scheme using both, analytical estimates and stochastic simulations based on a variety of real-world Internet topology data. Detailed comparisons are drawn to bi-directional tunneling, as well as to proposals on concurrent distribution trees.     

Multi‐constrained Shortest Disjoint Paths for Reliable QoS Routing

Finding link‐disjoint or node‐disjoint paths under multiple constraints is an effective way to improve network QoS ability, reliability, and so on. However, existing algorithms for such scheme cannot ensure a feasible solution for arbitrary networks. We propose design principles of an algorithm to fill this gap, which we arrive at by analyzing the properties of optimal solutions for the multi‐constrained link‐disjoint path pair problem. Based on this, we propose the link‐disjoint optimal multi‐constrained paths algorithm (LIDOMPA), to find the shortest link‐disjoint path pair for any network. Three concepts, namely, the candidate optimal solution, the contractive constraint vector, and structure‐aware non‐dominance, are introduced to reduce its search space without loss of exactness. Extensive simulations show that LIDOMPA outperforms existing schemes and achieves acceptable complexity. Moreover, LIDOMPA is extended to the node‐disjoint optimal multi‐constrained paths algorithm (NODOMPA) for the multi‐constrained node‐disjoint path pair problem.     

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.     

A novel efficient multicast routing algorithm in sparse splitting optical networks

The advances in wavelength-division multiplexing (WDM) technology are expected to facilitate bandwidth-intensive multicast applications through light splitting. Due to complexity and cost constraints, light splitting (or optical multicast) nodes are sparsely configured in a practical WDM network. In this article, we investigate the multicast routing problem under the sparse light-splitting constraint. An efficient sparse splitting constrained multicast routing algorithm called Multicast Capable Node First Heuristic (MCNFH) is proposed. The key idea of MCNFH is to include the shortest path, that includes most of the multicast capable nodes, for configuring the multicast tree. Simulations and comparisons are used to demonstrate the performance of MCNFH. Simulation results and analysis show that MCNFH builds multicast trees with the least wavelength channel cost and with the smallest number of wavelengths used per link. In addition, MCNFH requires only one transmitter at the source node.     

Two algorithms for multi‐constrained optimal multicast routing

Multimedia applications, such as video‐conferencing and video‐on‐demand, often require quality of service (QoS) guarantees from the network, typically in the form of minimum bandwidth, maximum delay, jitter and packet loss constraints, among others. The problem of multicast routing subject to various forms of QoS constraints has been studied extensively. However, most previous efforts have focused on special situations where a single or a pair of constraints is considered. In general, routing under multiple constraints, even in the unicast case is an NP‐complete problem. We present in this paper two practical and efficient algorithms, called multi‐constrained QoS dependent multicast routing (M_QDMR) and (multicasting routing with multi‐constrained optimal path selection (M_MCOP)), for QoS‐based multicast routing under multiple constraints with cost optimization. We provide proof in the paper that our algorithms are correct. Furthermore, through extensive simulations, we illustrate the effectiveness and efficiency of our proposals and demonstrate their significant performance improvement in creating multicast trees with lower cost and higher success probability. Copyright © 2003 John Wiley & Sons, Ltd.