The Steiner tree problem is a nondeterministic-polynomial-time-complete problem, so heuristic polynomial-time algorithms have been proposed for finding multicast trees. However, these polynomial-time algorithms' tree-cost optimality rates are not sufficient to obtain effective multicast trees, so intelligence algorithms, such as the genetic algorithm and artificial fish swarm algorithm, were proposed to improve previously proposed polynomial-time algorithms. However, these intelligence algorithms are time-consuming, even though they can reach quasi-optimal multicast trees. This paper proposes the multi-agent branch-based multicast (BBMC) algorithm, which can maintain the fast speed of polynomial-time algorithms while matching the tree-cost optimality of intelligence algorithms. The advantage of the proposed multi-agent BBMC algorithm is its covering of discarded effective branch candidates to seek the optimal multicast tree. By saving these branch candidates, the algorithm incurs tree-costs that are as small as those of intelligence algorithms, and by saving only a limited number of effective candidates, the algorithm is much faster than intelligence algorithms.

Information Centric Networking (ICN) is a promising architecture as an alternative paradigm to traditional IP networking. The innovative concepts, such as named data, name-based routing, and in-network caching bring lots of benefits to Wireless Sensor Networks (WSNs). Simple and robust communication model of ICN, based on interest/data messages exchange, is appealing to be deployed in WSNs. However, ICN architectures are designed for power supplied network devices rather than resource-constrained sensor nodes. Introducing ICN-liked architecture to WSNs needs to rethink the naming scheme and forwarding strategy to meet the requirements of energy efficiency and failure recovery. This paper presents a light weight data centric routing mechanism (GRMR) for interest dissemination and data delivery in location-aware WSNs. A simple naming scheme gives assistance for routing decision by individual nodes. Greedy routing engaging with regional multicast mechanism provides an efficient data centric routing approach. The performance is analytically evaluated and simulated in NS-2. The results indicate that GRMR achieves significant energy efficiency under investigated scenarios.

There is a well known Steiner tree algorithm called minimum-cost paths heuristic (MPH), which is used for many multicast network operations and is considered a benchmark for other Steiner tree algorithms. MPH's average case time complexity is O(m(l+nlog n)), where m is the number of end nodes, n is the number of nodes, and l is the number of links in the network, because MPH has to run Dijkstra's algorithm as many times as the number of end nodes. The author recently proposed a Steiner tree algorithm called branch-based multi-cast (BBMC), which produces exactly the same multicast tree as MPH in a constant processing time irrespective of the number of multicast end nodes. However, the theoretical result for the average case time complexity of BBMC was expressed as O(log m(l+nlog n)) and could not accurately reflect the above experimental result. This paper proves that the average case time complexity of BBMC can be shortened to O(l+nlog n), which is independent of the number of end nodes, when there is an upper limit of the node degree, which is the number of links connected to a node. In addition, a new parameter β is applied to BBMC, so that the multicast tree created by BBMC has less links on it. Even though the tree costs increase due to this parameter, the tree cost increase rates are much smaller than the link decrease rates.

Multicast routing with Quality-of-Service (QoS) guarantees is the key to efficient content distribution and sharing. Developing QoS-aware multicast routing algorithm is an important open topic. This paper investigates QoS-aware multicast routing problem with K constraints where K > 2. The contributions made in this paper include a heuristic that employs the concept of nonlinear combination to extend the existing well-known algorithm for fast computation of a QoS multicast tree, and a Fully Polynomial Time Approximation Scheme (FPTAS) to approximate a multicast routing tree with QoS guarantees. The theoretical analyses and simulations conducted on both algorithms show that the algorithms developed in this paper are general and flexible, thus are applicable to the various networking systems.

To provide scalability against group size, Global Location Search based Hierarchical Geographic Multicast Protocols (GLS-HGMPs) have recently been proposed for wireless sensor networks. To reduce the communication overhead imposed by the global location search and prevent the multicast data detour imposed by the hierarchical geographic multicasting in GLS-HGMPs, this letter proposes Local Location Search based Progressive Geographic Multicast Protocol (LLS-PGMP). Simulation results show that LLS-PGMP is superior to GLS-HGMPs.

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.

Multicasting is an efficient communication tool for use in multi-point applications such as conferencing and information distribution. In ad hoc networks, node mobility causes frequent changes of network topology, and re-construction of the multicast tree in an efficient and effective manner becomes a critical issues. In case of link breakage, most of the multicast tree construction protocols available presently require either a total re-build of the tree or to reconnect a disjoined node back to the multicast tree via the shortest path which may disrupt the optimising factors, such as energy consumption, delay or cost, used in the building of the original tree. In this paper, we introduce a computationally efficient recovery algorithm which will also minimise the power consumption on the tree.

In this paper, we consider the problem of multicasting a message in k-ary n-cubes under the store-and-forward model. The objective of the problem is to minimize the size of the resultant multicast tree by keeping the distance to each destination over the tree the same as the distance in the original graph. In the following, we first propose an algorithm that grows a multicast tree in a greedy manner, in the sense that for each intermediate vertex of the tree, the outgoing edges of the vertex are selected in a non-increasing order of the number of destinations that can use the edge in a shortest path to the destination. We then evaluate the goodness of the algorithm in terms of the worst case ratio of the size of the generated tree to the size of an optimal tree. It is proved that for any k 5 and n 6, the performnance ratio of the greedy algorithm is c kn - o(n) for some constant 1/12 c 1/2.

The ATM multicast Tree (AMT) is the Mbone of video/audio conferencing and other multicasting applications in ATM (Asynchronous Transfer Mode) networks. However, real problems such as temporarily moving switches, changing optic fiber connections and/or tangible/intangible failures of ATM networks will cause many service disruptions. Thus we must carefully consider the system's SQOS (Survivable QOS) when we construct the system. A point-to-point self-healing scheme utilizing a conventional pre-planned backup mechanism is proposed to protect the AMT from failure. This scheme uses point-to-point pre-planned backup Root-to-Leaf Routes (RLR) as the root-to-leaf structure of an AMT. Though AMT protection via preplanned backup RLR requires no search time, duplicate paths may cause redundant bandwidth consumption. This paper also proposes a closest-node method, which can locate the minimum-length route structure during the initial design and also rebuild the AMT in the event of a network failure. To enhance the survivability of the system, we introduce two near optimal re-routing algorithms, a most-decent search algorithm, and also a predictive-decent search algorithm in order to find the minimum lost flow requirement. These near optimal schemes use search technique to guide the local optimal lost flow to the most-decent lost flow direction. The predictive way is an especially economical technique to reduce the calculation complexity of lost flow function. For the evaluation of the feasibility and performance of the new schemes, we simulate AMT restoration and the simulation results show the closest-node scheme provides superior AMT restoration compared to a system with a preplanned point-to-point backup scheme. In addition, the predictive-decent search algorithm is faster than the most-decent search one.

In the future broadband networks, multicast services such as video conferencing and distance learning will become increasingly important. To support these multimedia services, one solution is to form an AMT(ATM Multicast Tree)to connect all the conferencing members. In this paper, based on AMT survivability requirements, we investigate the self-healing of an AMT. Self-healing on AMT is a new challenge of survivability of multimedia services. The pre-assign way is a method we usually considered on protection. If we construct a disjoint backup tree, the low building probability and complicated loading on constructing is the first problem. Second, if only one link or node failed on an AMT, we need to reroute links and reserve bandwidth on whole backup tree. Moreover, since the AMT usually transmits video images, the restoration rate will be decreased because even only one branch of backup tree does not endure the required bandwidth. These enhance us to restore the AMT by dynamic restoration scheme. Two proposed dynamic restoration schemes are developed to provide prioritized restoration from a link or node failure. In the first scheme, we apply a link-based restoration scheme on the AMT. The restoration is based on the failed links of network and does not take whole AMT into account. In the second scheme, without changing the multicast services to the members, we allow reconfiguration of the AMT during the restoration phase. Reconfiguration of the AMT is based on a tree-based restoration concept. By computer simulations, we verify the characteristics of the proposed schemes and the results show that the second scheme outperforms the first.