 |
|
|
|
 |
 |
 |
|
 |
|
 |
|
|
| 曹佳,鲁士文.应用层组播的最小延迟生成树算法.软件学报,2005,16(10):1766-1773 |
| 应用层组播的最小延迟生成树算法 |
| A Minimum Delay Spanning Tree Algorithm for the Application-Layer Multicast |
| 投稿时间：2004-07-16 修订日期：2005-03-11 |
| DOI： |
| 中文关键词: 应用层组播 最小延迟生成树 NP-hard 实时传输 |
| 英文关键词:application-layer multicast minimum delay spanning tree NP-hard real time transmission |
| 基金项目:Supported by the National High-Tech Research and Development Plan of China under Grant No.2002AA742052(国家高技术研究发展计划(863)) |
|
| 摘要点击次数: 3782 |
| 全文下载次数: 4881 |
| 中文摘要: |
| 实时传输是应用层组播技术的一个主要应用领域,对网络延迟有严格的限制.保证低延迟组播成功的关键在于构建高效的应用层组播树,研究构建最小延迟应用层组播树的算法.首先分析影响延迟的3个因素:链路的传输时间、结点的发送/转发时间和结点度,然后把求解应用层组播树的问题抽象成对边和点都带权的有向图求解"度约束最小延迟生成树"的问题,同时证明这个问题属于NP-hard,并且提出了两类启发式近似算法:基于度的算法和基于最大延迟路径的算法.最后通过模拟实验说明了所提出算法的有效性. |
| 英文摘要: |
| Real time transmission, which is delay sensitive, is an important aspect of application-layer multicast. It is crucial to build an efficient multicast tree to guarantee the lower delay. This research is focused on the algorithms of the minimum-delay spanning tree for the application-layer multicast. Firstly, it is stated that the total delay is affected by communication delay, processing delay and the degree of nodes. Then the network is modeled into the node-and-edge-weighted directed graph with the limited degree of nodes. In this model the problem is shown to be NP-hard. Therefore, two kinds of heuristic algorithms are proposed, which are based on the maximum degree and the maximal length path respectively. Finally, the simulation demonstrates that the proposed algorithms are valid. |
|
HTML 下载PDF全文 查看/发表评论 下载PDF阅读器 |
|
|
|
|
|
|
 |
|
|
|
|
 |
|
 |
|
 |
|
