			Home About us Contact

Multicast Routing (multicast + routing)

Distribution by Scientific Domains

Information Science and Computing	60%

Selected Abstracts

Distributed end-host multicast algorithms for the Knowledge Grid

CONCURRENCY AND COMPUTATION: PRACTICE & EXPERIENCE, Issue 15 2007
Wanqing Tu
Abstract The Knowledge Grid built on top of the peer-to-peer (P2P) network has been studied to implement scalable, available and sematic-based querying. In order to improve the efficiency and scalability of querying, this paper studies the problem of multicasting queries in the Knowledge Grid. An m -dimensional irregular mesh is a popular overlay topology of P2P networks. We present a set of novel distributed algorithms on top of an m -dimensional irregular mesh overlay for the short delay and low network resource consumption end-host multicast services. Our end-host multicast fully utilizes the advantages of an m -dimensional mesh to construct a two-layer architecture. Compared to previous approaches, the novelty and contribution here are: (1) cluster formation that partitions the group members into clusters in the lower layer where cluster consists of a small number of members; (2) cluster core selection that searches a core with the minimum sum of overlay hops to all other cluster members for each cluster; (3) weighted shortest path tree construction that guarantees the minimum number of shortest paths to be occupied by the multicast traffic; (4) distributed multicast routing that directs the multicast messages to be efficiently distributed along the two-layer multicast architecture in parallel, without a global control; the routing scheme enables the packets to be transmitted to the remote end hosts within short delays through some common shortest paths; and (5) multicast path maintenance that restores the normal communication once the membership alteration appears. Simulation results show that our end-host multicast can distributively achieve a shorter delay and lower network resource consumption multicast services as compared with some well-known end-host multicast systems. Copyright © 2006 John Wiley & Sons, Ltd. [source]

Tightest constraint first: An efficient delay sensitive multicast routing algorithm

INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 7 2005
Gang FengArticle first published online: 1 APR 200
Abstract As a key issue in multicast routing with quality of service (QoS) support, constrained minimum Steiner tree (CMST) problem has been a research focus for more than a decade, and tens of heuristics have been developed to solve this NP-complete problem. Among all the previously proposed algorithms, the bounded shortest path algorithm (BSMA) (IEEE INFOCOM'95 1995; 1:377,385) have been proved to be capable of producing a multicast tree that has on average the lowest cost. However, such an excellent cost performance is accompanied with an extremely high time complexity. Recently, Feng et al. presented an alternative implementation of BSMA, which makes use of the latest research results on the delay-constrained least cost (DCLC) routing problem. Simulations indicate that, in comparison with the original implementation, the alternative implementation has a much lower time complexity with virtually identical cost performance, and it also runs much faster than many renowned heuristics such as KPP (IEEE/ACM Trans. Networking 1993; 1(3):286,292) and CAO (The design and evaluation of routing algorithms for real-time channels. Technical Report ICSI TR-94-024, International Computer Science Institute, University of California at Berkeley, June 1994). In this paper, we propose a brand new heuristic TCF, which is based on an idea called ,tightest constraint first.' TCF runs a DCLC heuristic only once for each destination and therefore has a provably low time complexity. We further propose an iterative heuristic ITCF, which uses TCF to obtain an initial tree and then gradually refines it. Extensive simulations demonstrate that, in the average sense, TCF can achieve a cost performance comparable to or better than that of BSMA, the cost performance of ITCF is even better than that of TCF, TCF runs approximately twice as fast as ITCF, and ITCF runs 2,4 times as fast as the best implementation of BSMA. Copyright © 2005 John Wiley & Sons, Ltd. [source]

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

INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 3 2001
Xiaohua Jia
Abstract 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. [source]

A dynamic multicast routing satisfying multiple QoS constraints

INTERNATIONAL JOURNAL OF NETWORK MANAGEMENT, Issue 5 2003
Debasish Chakraborty
In this paper we propose a QoS-based routing algorithm for dynamic multicasting. The complexity of the problem can be reduced to a simple shortest path problem by applying a Weighted Fair Queuing (WFQ) service discipline. Using a modified Bellman,Ford algorithm, the proposed routing builds a multicast tree, where a node is added to the existing multicast tree without re-routing and satisfying QoS constraints.,With user defined life-time of connection this heuristic algorthm builds multicast tree which is near optimum over the whole duration of session. Simulation results show that tree costs are nearly as good as other dynamic multicast routings that does not consider QoS. Copyright © 2003 John Wiley & Sons, Ltd. [source]