This paper addresses the optimum routing problem of multipoint connection in large-scale networks. A number of algorithms for routing of multipoint connection have been studied so far, most of them, however, assume the availability of complete network information. Herein, we study the problem under the condition that only partial information is available to routing nodes and that routing decision is carried out in a distributed cooperative manner. We consider the network being partitioned into clusters and propose a cluster-based routing approach for multipoint connection. Some basic principles for network clustering are discussed first. Next, the original multipoint routing problem is defined and is divided into two types of subproblems. The global optimum multicast tree then can be obtained asymptotically by solving the subproblems one after another iteratively. We propose an algorithm and evaluate it with computer simulations. By measuring the running time of the algorithm and the optimality of resultant multicast tree, we show analysis on the convergent property with varying network cluster sizes, multicast group sizes and network sizes. The presented approach has two main characteristics, 1) it can yield asymptotical optimum solutions for the routing of multipoint connection, and 2) the routing decisions can be made in the environment where only partial information is available to routing nodes.

In this paper, we propose a new multicast routing algorithm for constructing the delay-constrained minimal spanning tree in the VP-based ATM networks, in which we consider the efficiency even in the case where the destination dynamically joins/departs the multicast connection. For constructing the delay-constrained spanning tree, we first generate a reduced network consisting of only VCX nodes from a given ATM network, originally consisting of VPX/VCX nodes. Then, we obtain the delay-constrained spanning tree with a minimal tree cost on the reduced network by using our proposed heuristic algorithm. Through numerical examples, we show that our dynamic multicast routing algorithm can provide an efficient usage of network resources when the membership nodes frequently changes during the lifetime of a multicast connection, while the existing multicast routing algorithm may be useful for constructing the multicast tree with a static nature of destination nodes. We also demonstrate that more cost-saving can be expected in dense networks when applying our proposed algorithm.