This paper presents an artificial fish swarm algorithm (AFSA) to solve the multicast routing problem, which is abstracted as a Steiner tree problem in graphs. AFSA adopts a 0-1 encoding scheme to represent the artificial fish (AF), which are then subgraphs in the original graph. For evaluating each AF individual, we decode the subgraph into a Steiner tree. Based on the adopted representation of the AF, we design three AF behaviors: randomly moving, preying, and following. These behaviors are organized by a strategy that guides AF individuals to perform certain behaviors according to certain conditions and circumstances. In order to investigate the performance of our algorithm, we implement exhaustive simulation experiments. The results from the experiments indicate that the proposed algorithm outperforms other intelligence algorithms and can obtain the least-cost multicast routing tree in most cases.

While the problem of multicast routing and wavelength assignment (MC-RWA) in optical wavelength division multiplexing (WDM) networks has been investigated, relatively few researchers have considered network survivability for multicasting. This paper provides an optimization framework to solve the MC-RWA problem in a multi-fiber WDM network that can recover from a single-link failure with shared protection. Using the light-tree (LT) concept to support multicast sessions, we consider two protection strategies that try to reduce service disruptions after a link failure. The first strategy, called light-tree reconfiguration (LTR) protection, computes a new multicast LT for each session affected by the failure. The second strategy, called optical branch reconfiguration (OBR) protection, tries to restore a logical connection between two adjacent multicast members disconnected by the failure. To solve the MC-RWA problem optimally, we propose an integer linear programming (ILP) formulation that minimizes the total number of fibers required for both working and backup traffic. The ILP formulation takes into account joint routing of working and backup traffic, the wavelength continuity constraint, and the limited splitting degree of multicast-capable optical cross-connects (MC-OXCs). After showing some numerical results for optimal solutions, we propose heuristic algorithms that reduce the computational complexity and make the problem solvable for large networks. Numerical results suggest that the proposed heuristic yields efficient solutions compared to optimal solutions obtained from exact optimization.

Multicast communication over mobile ad hoc networks has become popular. However, dependable and scalable multicast routing is required for mobile ad hoc networks even though network size and node mobility continue to increase. Therefore, this paper proposes a new hierarchical multicast routing scheme for such ad hoc networks. The proposed scheme introduces the inter-cluster group mesh structure based on our previous autonomous clustering proposal. In the proposed scheme, data packets are delivered from the source node to the multicast members through multiple routes over the inter-cluster group mesh structure. Simulations show that the proposed scheme is scalable with regard to network size and strong against node mobility; it can provide dependable multicast communication on large mobile ad hoc networks.

We consider the capacitated multi-source multicast tree routing problem (CMMTR) in an undirected graph G=(V,E) with a vertex set V, an edge set E and an edge weight w(e) ≥ 0, e ∈ E. We are given a source set S ⊆ V with a weight g(e) ≥ 0, e ∈ S, a terminal set M ⊆ V-S with a demand function q : M → R+, and a real number κ > 0, where g(s) means the cost for opening a vertex s ∈ S as a source in a multicast tree. Then the CMMTR asks to find a subset S′⊆ S, a partition {Z1,Z2,...,Zl} of M, and a set of subtrees T1,T2,...,Tl of G such that, for each i, ∑t∈Ziq(t) ≤ κ and Ti spans Zi∪{s} for some s ∈ S′. The objective is to minimize the sum of the opening cost of S′and the constructing cost of {Ti}, i.e., ∑s∈S′g(s)+w(Ti), where w(Ti) denotes the sum of weights of all edges in Ti. In this paper, we propose a (2ρUFL+ρST)-approximation algorithm to the CMMTR, where ρUFL and ρST are any approximation ratios achievable for the uncapacitated facility location and the Steiner tree problems, respectively. When all terminals have unit demands, we give a ((3/2)ρUFL+(4/3)ρST)-approximation algorithm.

Mobile IP is a solution to support mobile nodes but it does not handle NEtwork MObility (NEMO). The NEMO Basic Support (NBS) [1] ensures session continuity for all the nodes in a MObile NETwork (MONET). Since the protocol is based on Mobile IP, it inherits from Mobile IP the same fundamental problem such as tunnel convergence, when it is used to support the multicast for NEMO. In this paper, we propose the multicast Route Optimization (RO) scheme in NEMO environments. We suppose that the Mobile Router (MR) has a multicast function and the Nested Mobile Router Information (NeMRI). The NeMRI is used to record a list of the CoAs of all the MRs located below. And it obtains information whether the MRs desire multicast services. Also, we adopt any RO scheme to handle pinball routing. Therefore, we achieve optimal routes for multicasting in NEMO. We also develop analytic models to evaluate the performance of our scheme. We show much lower multicast tree delay and cost in NEMO compared with other techniques such as Bi-directional Tunneling (BT), Remote Subscription (RS), and Mobile Multicast (MoM) based on the NBS protocol.

With the proliferation of multimedia group applications, the construction of multicast trees satisfying the Quality of Service (QoS) requirements is becoming a problem of the prime importance. An essential factor of these real-time application is to optimize the Delay- and delay Variation-Bounded Multicast Tree (DVBMT) problem. This problem is to satisfy the minimum delay variation and the end-to-end delay within an upper bound. The DVBMT problem is known as NP-complete problem. The representative algorithms for the problem are DVMA, DDVCA, and so on. In this paper, we show that the proposed algorithm outperforms any other algorithm. The efficiency of our algorithm is verified through the performance evaluation and the enhancement is up to about 13.5% in terms of the multicast delay variation. The time complexity of our algorithm is O(mn2) which is comparable to well known DDVCA.

QMNF is a QoS-aware multicast routing protocol using N-hop dominating flooding and built upon a layered routing architecture. In this architecture, QMNF invites the N-hop flooding component and the shortest path routing table from OSPF by open signaling interfaces, floods the path-probing packets, and employs a two-pass resource reservation scheme to avoid unnecessary resource reservation. The QMNF is QoS-aware, loop-free, flexible and scalable, and improves network resource utilization. In our simulation, the performance of QMNF is compared with that of traditional flooding protocol with the shortest path resources reservation, a traditional flooding protocol with the widest path resources reservation, PIM and QMBF. The simulation results confirm that QMNF has a high success rate and good resource utilization, and it can distribute traffic in a network evenly.

This paper discusses multicast routing in ad hoc networks. In multicast routing, a node delivers the same message to the other nodes within a multicast group along with a multicast tree. Since nodes are moving around in ad hoc networks, the links between the nodes change frequently. However, the multicast tree must be maintained to deliver the messages regardless of the link changes. This paper gives a description of an autonomous clustering-based hierarchical multicast routing protocol in ad hoc networks. Since the autonomous clustering scheme is adaptive to the node movement, the proposed multicast routing can maintain the multicast tree in despite of link changes. This paper shows the effectiveness of autonomous clustering-based hierarchical multicast routing from the point of view of adaptability to link changes and scalability to multicast members.

We consider the multicast routing problem for large-scale wavelength division multiplexing (WDM) optical networks where transmission requests are established by point-to-multipoint connections. To realize multicast routing in WDM optical networks, some nodes need to have light (optical) splitting capability. A node with splitting capability can forward an incoming message to more than one output link. We consider the problem of minimizing the number of split-capable nodes in the network for a given set of multicast requests. The number of wavelengths is fixed and given a priori. We propose a genetic algorithm that exploits the combination of alternative shortest paths for the given multicast requests in order to minimize the number of required split-capable nodes. This algorithm is examined for two realistic networks constructed based on the locations of major cities in Ibaraki Prefecture and those in Kanto District in Japan. Our experimental results show that the proposed algorithm can reduce more than 10% of split-capable nodes compared with other routing algorithms whereby the optimization for the split-capable node placement is not taken into account.

In this paper, we consider the problem of multicast routing and wavelength assignment (MC-RWA) in multi-fiber all-optical WDM networks. Two main network design system comprehensively investigated here are mesh and multi-ring designs. Given the multicast traffic demands, we present new ILP formulations to solve the MC-RWA problem with an objective to determine the minimal number of fibers needed to support the multicast requests. Unlike previous studies, our ILP formulations are not only capable of finding the optimal multicast routing and wavelength assignment pattern to the light-trees, but also finding the optimal light-tree structures simultaneously. Since broadcast and unicast communications are special cases of multicast communications, our ILP models are actually the generalized RWA mathematical models of optical WDM networks. In addition to proposing the ILP models, this paper takes two main issues affecting the network capacity requirement into account, that is, the splitting degree level of optical splitters and techniques of wavelength assignment to the light-trees. Three multicast wavelength assignment techniques studied in this paper are Light-Tree (LT), Virtual Light-Tree (VLT) and Partial Virtual Light-Tree (PVLT) techniques. Due to the NP-completeness of the MC-RWA problem, the ILP formulations can reasonably cope with small and moderate networks. To work with large networks, this paper presents alternative MC-RWA ILP-based heuristic algorithms for the PVLT and LT networks and develops lower bound techniques to characterize the performance of our algorithms. Using existing large backbone networks, numerical results are reported to analyze such aspects as multiple fiber systems, the benefits of using optical splitters and wavelength converters, and the capacity difference between the mesh and multi-ring designs. Finally, this paper provides an analysis of the influence of network connectivity on the network implementation under the constraints of mesh and multi-ring design schemes.

Cluster computation has been used in the applications that demand performance, reliability, and availability, such as cluster server groups, large-scale scientific computations, distributed databases, distributed media-on-demand servers and search engines etc. In those applications, multicast can play the vital roles for the information dissemination among groups of servers and users. This paper proposes a set of novel efficient fault-tolerant multicast routing algorithms on hypercube interconnection of cluster computers using multicast shared tree approach. We present some new algorithms for selecting an optimal core (root) and constructing the shared tree so as to minimize the average delay for multicast messages. Simulation results indicate that our algorithms are efficient in the senses of short end-to-end average delay, load balance and less resource utilizations over hypercube cluster interconnection networks.

Group multicasting is a generalization of multicasting whereby every member of a group is allowed to multicast messages to other members that belongs to the same group. The group multicast routing problem (GMRP) is that of finding a set of multicast trees with bandwidth requirements, each rooted at a member of the group, for multicasting messages to other members of the group. An optimal solution to GMRP is a set of trees, one for each member of the group, that incurs the least overall cost. This problem is known to be NP-complete and hence heuristic algorithms are likely to be the only viable approach for computing near optimal solutions in practice. In this paper, we derive a lower bound on the cost of an optimal solution to GMRP by using Lagrangean Relaxation and Subgradient Optimization. This lower bound is used to evaluate the two existing heuristic algorithms in terms of their ability to find close-to-optimal solutions.

In this paper we addresses the problem of finding feasible solutions for the Group Multicast Routing Problem (GMRP). This problem is a generalization of the multicast routing problem whereby every member of the group is allowed to multicast messages to other members from the same group. The routing problem involves the construction of a set of low cost multicast trees with bandwidth requirements for all the group members in the network. We first prove that the problem of finding feasible solutions to GMRP is NP-complete. Following that we propose a new heuristic algorithm for constructing feasible solutions for GMRP. Simulation results show that our proposed algorithm is able to achieve good performance in terms of its ability of finding feasible solutions whenever one exist.

In this paper we describe a multicast routing algorithm, which builds upon mobile multicast agents of an ad-hoc network. Mobile multicast agents (MMAs) form a virtual backbone of an ad-hoc network and they provide multicast tree discovery, multicast tree maintenance and datagram delivery. First, we construct a cluster-spine hierarchy structure for an ad-hoc network. Second, we propose a multicast routing algorithm, which is inspired by Ad-hoc On-Demand Distance Vector (AODV) routing protocol. The results show that the MMA multicast algorithm can simplify the multicast tree discovery, reduce control overhead of the network, and increase the total network throughput, in comparison with general AODV multicast operation. We also overcome the deficiency of CBRP multicast routing, which places much burden on cluster heads.

Emerging multimedia technologies introduce the prevalent multicast transmission, and the multicast tree is determined using the time-invariant network parameters. This paper addresses the time-varying multicast tree problem and presents path selection heuristics for multicast routing to determine an alternative path for real-time applications. A network is partitioned into the optimal region, the disjoint region, and the edge cutset if a branch of the multicast tree meets the un-guaranteed QoS condition. The path selection heuristics operate during the multicast session phase to efficiently select an alternative routing path containing an edge in the edge cutset to connect the multicast tree again. The source-based heuristics PS-SPT finds the path for minimal source-to-destination delay and the sharing-based heuristics PS-DDMC for minimal total cost. These path selection heuristics can efficiently provide solutions to keep the multicast transmission reliable. Simulation results also show that the proposed heuristics can provide effective good solutions for real-time multicast transmission. PS-SPT can select a path with optimal source-to-destination delay and PS-DDMC can select a path with optimal total cost.

This paper proposes a managed IP multicast platform that enables IP multicast services to be used for business. Nowadays, many business applications have switched from traditional network platforms to the IP platform. Among these applications, one-to-many or many-to -many types of applications are especially essential to business users. These applications may use IP Multicasting for transmitting data to many users. However, for business applications, it is difficult to use the present IP Multicast services, because they lack many requirements for business usage. The requirements are address management, authentication, time management, and guaranteed throughput. To satisfy the business users, we made the design of a managed IP multicast platform that will meet these requirements. Our platform, which separates the routing control layer and the packet forwarding layer, is called GMN-CL (Connection Technologies for Global Mega-media Network). The routing control layer manages routing information and controls network routing centrally, so it can understand the whole network situation and perform efficient routing. The packet forwarding layer can concentrate completely on forwarding, so the forwarding speed and copying speed is higher than when using routers. We have implemented our design of a managed IP multicast platform over GMN-CL. This paper reports the system design, implementation, and evaluation.

We investigate a state dependent multicast routing scheme, called Least Load Multicast Routing (LLMR), for single rate loss networks. The algorithm is based on Least Load Routing (LLR) concept and the approach is to select the least loaded links for establishing connections. An analytical model for LLMR is developed. The accuracy of the analytical model is compared with the simulation results and is found to be very good. We also develop a simplified analytical model for fully symmetrical networks, which is also verified by comparing with simulation results.

In this paper, a new multicast routing method for layered streams is proposed. This method is an extension of the weighted greedy algorithm (WGA) and uses two kinds of weight values to refine the link distance. It can cope with dynamic change in the group members without multicast tree re-construction. The method is compatible with the RSVP and can be utilized in existing shared tree type routing protocols such as CBT and PIM sparse mode. The network resources can be utilized efficiently; furthermore, the loss rate of member's requests to receive more layers can be reduced by this routing method when a sufficient number of nodes have the packet filtering function and a sufficient number of hops is permitted.

The main issues of the next generation Internet are high performance multicast, security and QoS (Quality of Service). The network layer multicast is accepted as a powerful solution to reduce communication overhead in networks as well as hosts. Although a lot of multicast routing protocols have been developed and have worked for the current Internet, they have drawbacks in scalability, reliability and network load balancing. In this paper, we propose an enhanced multicast routing protocol called DCBT (Decentralized Core based Tree), which includes some features of CBT (Core Based Tree), PIM-SM (Protocol Independent Multicast-Sparse Mode) and BGMP (Border Gateway Multicast Protocol). Fundamentally DCBT differs from those in that it covers not only intra-region but also inter-region multicast. RNs (Regional networks) have their intra-region shared trees, which are interconnected by an inter-region shared tree for a multicast group. New two concepts are introduced: the one is RBTS (Region Based Tree Switching) to achieve network load balancing and the other is to redefine TOS (Type Of Service) byte to make special multicast routing decision. In addition, the effect of core location is given by changing its position within an RN. Finally we provide the performance evaluation of DCBT by OPNET network simulator over a real scale network model.

This paper studies the routing algorithms for multi-destination connections where each destination may require different amount of data streams. This asymmetric feature can arise mostly in a large and/or heterogeneous network environment. There are mainly two reasons for this. One is that terminal equipments may have different capabilities. The other is that users may have various interests in the same set of information. We first define the asymmetric multicast problem and describe an original routing method for this type of multicast. The method is then employed in the presented routing algorithms, which can be run in multi-cluster environment. The multi-cluster architecture is considered to be effective for running routing in the networks, where a variety of operating methods might be applied in different clusters but global network performance is required. Our algorithms are designed based on some classical Steiner tree heuristics. The basic goal of our algorithms is to make routing decisions for the asymmetric multicast connections with minimum-cost purpose. In addition, we also consider delay constraint requirements in the multicast connections and propose correspondent algorithms. We compare the performance between SPT (Shortest Path Tree)-based algorithms and the presented algorithms by simulations. We show that performance difference exists among the different types of the algorithms.