On Minimum Cost Multicast Routing Based on Cost Prediction

作     者：Kim, Moonseong Mutka, Matt W. Hwang, Dae-Jun Choo, Hyunseung 

作者机构：Sungkyunkwan Univ Sch Informat & Commun Engn Suwon 440746 South Korea Michigan State Univ Dept Comp Sci & Engn E Lansing MI 48824 USA 

出 版 物：《JOURNAL OF COMMUNICATIONS AND NETWORKS》 (通讯与网络杂志)

年 卷 期：2009年第11卷第5期

页      面：500-508页

核心收录：

学科分类：0810[工学-信息与通信工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：ITRC [IITA-2009-(C1090-0902-0046)] KOSEF [R31-2008-000-10062-0] 

主　　题：Minimal Steiner trees minimum cost trees multicast communications multicast routing algorithm Takahashi and Matsuyama (TM) algorithm 

摘      要：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(kn(2)) 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%similar to 4.23% for each best case.