On Minimum Cost Multicast Routing based on Cost Prediction

Moonseong Kim, Matt W. Mutka, Dae-Jun Hwang, and Hyunseung Choo

Journal of Communications and Networks, vol. 11, no. 5, pp. 501-509, Oct. 2009 (SCI, IF: 0.224)

Abstract

We have designed an algorithm for a problem in multicast communication. The problem is to construct a multicast tree while minimizing its cost, which is known to be NP-complete. Our algorithm, which employs new concepts defined as potential cost and spanning cost, generates a multicast tree more efficiently than the well-known heuristic called Takahashi and Matsuyama (TM) [1] in terms of tree cost. The time complexity of our algorithm is O(kn2) for an n-node network with k members in the multicast group and is comparable to the TM. Our empirical performance evaluation comparing the proposed algorithm with TM shows that the enhancement is up to 1.25%∼4.23% for each best case.

 

Keyword

Minimal Steiner trees, minimum cost trees, multicast communications, multicast routing algorithm, Takahashi and Matsuyama (TM) algorithm.

 

View Full Text