Yb. Zhang et al., AN APPROACH FOR CLUSTER-BASED MULTICAST ROUTING IN LARGE-SCALE NETWORKS, IEICE transactions on communications, E81B(5), 1998, pp. 1029-1040
This paper addresses the optimum routing problem of multipoint connect
ion in large-scale networks. A number of algorithms for routing of mul
tipoint connection have been studied so far, most of them, however, as
sume the availability of complete network information. Herein, we stud
y the problem under the condition that only partial information is ava
ilable to routing nodes and that routing decision is carried out in a
distributed cooperative manner. We consider the network being partitio
ned into clusters and propose a cluster-based routing approach for mul
tipoint connection. Some basic principles for network clustering are d
iscussed first. Next, the original multipoint routing problem is defin
ed and is divided into two types of subproblems. The global optimum mu
lticast tree then can be obtained asymptotically by solving the subpro
blems one after another iteratively. We propose an algorithm and evalu
ate it with computer simulations. By measuring the running time of the
algorithm and the optimality of resultant multicast tree, we show ana
lysis on the convergent property with varying network cluster sizes, m
ulticast 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 avai
lable to routing nodes.