Patent ID: 7693074

Claim:
A multicast communication path calculation method performed by a multicast path calculation apparatus for obtaining multicast paths from a given source node to a plurality of destination nodes in a network including a plurality of nodes, the method comprising: receiving, by the multicast path calculation apparatus, a distance graph including topology and cost of the network; establishing, by the multicast path calculation apparatus, a first distance subgraph in which the source node is deleted from the received distance graph; selecting, by the multicast path calculation apparatus, the destination nodes from the first distance subgraph, obtaining a second distance subgraph in which each edge is a shortest path between two of the destination nodes, and establishing a first minimal spanning tree of the second distance subgraph; establishing, by the multicast path calculation apparatus, a subgraph of the first minimal spanning tree by including intermediate nodes in each of the edges of the first minimal spanning tree, and establishing a second minimal spanning tree of the subgraph; deleting, by the multicast path calculation apparatus, unnecessary edges from the second minimal spanning tree so that a tree including the destination nodes is established; assuming, by the multicast path calculation apparatus, that nodes that form the tree are candidate nodes of a rendezvous point node, obtaining, for each of the candidate nodes, a difference between the maximum distance and the minimum distance among distances between the candidate node and each of the destination nodes, and selecting, as the rendezvous point node, the candidate node for which the difference is smallest; and obtaining, by the multicast path calculation apparatus, the multicast paths by connecting the tree and the source node at the rendezvous point node, and outputting the multicast paths.