| 摘要: |
| 提出基于主干树的最小代价组播路由算法,该算法首先在网络中找出K个代价最小的结点,然后以这K个结点形成一棵树,并称这棵为主干树,然后将不在主干树上的成员结点加入到树上,最后剪去非成员的叶结点。该算法的时间复杂度O(n3)。该算法所构造的组播树代价略低于MPH算法和KMB算法。 |
| 关键词: 最小代价组播树 组播路由 主干树 服务质量 |
| DOI： |
| 投稿时间：2003-12-25修订日期：2004-04-01 |
| 基金项目:广西"新世纪十百千人才工程"专项资金(桂人字2001213号);广西教育厅科技项目(桂教科研[2001]401号) |
|
| The Minimum Cost Multicast Routing Algorithm Based on Main Frame Tree |
|
Liu Wenbin, Li Taoshen
|
| (Coll of Comp & Elec Info, Guangxi Univ, Nanning, Guangxi, 530004, China) |
| Abstract: |
| The minimum cost multicast routing algorithm based main frame tree is presented.The steps of the algorithm are,to find the K nodes with minimum cost in the network firstly,and make a trunk using these nodes;the member nodes which are not in the trunk are put in the trunk,and finally,the non member nodes(leaves nodes) in the trunk are deleted. The time consumption of the algorithm is O(n3). The multicast tree cost of the algorithm is a bit less than those of algorithms of KMB and MPH. |
| Key words: minimum cost multicast tree multicast routing main frame tree service quality |
