Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.17 No.3, pp.507-524 (May 2001)

Constructing Delay-Bounded Mutlcast Trees in Computer Networks


Lih-Chau Wuu, Long Song Lin and Shing-Chyi Shiao
Institute of Electronic and Information Engineering
National YunLin University
Touliu Taiwan 640, R.O.C.

In this paper we propose a distributed protocol for constructing delay-bounded minimum-cost multicast trees in computer networks. The proposed protocol does not require knowledge of the complete network topology. Furthermore, it is unnecessary to know how many nodes are in the networks and which nodes are group members in advance. It is shown, through analysis and simulation on a class of random graphs, that our protocol only uses O(n) messages in the best case, where n is the number of nodes in the networks. Even in the worst case, our protocol uses O(d*n) messages that has lower message complexity than previous protocols, where d is the average nodal degree.

Keywords: multicast routing, Steiner tree, tree cost, delay bounded multicast, distributed algorithm

Full Text () Retrieve PDF document (200105_09.pdf)

Received December 9, 1998; revised February 23 & May 15, 1999; accepted August 4, 1999.
Communicated by Shing-Tsaan Huang.