最小延迟的应用层多播树算法研究  

Study of Application-layer Multicast Algorithms Based on Minimum Delay

作　　者：郑心炜[1] 余胜生[2] 

机构地区：[1]广东商学院信息学院电子商务教研室,广东广州510320 [2]华中科技大学计算机学院信息存储系统教育部重点实验室,湖北武汉430074

出　　处：《小型微型计算机系统》2010年第2期198-201,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60673001)资助

摘　　要：在构建高效的应用层多播树过程中,许多端系统需要时间处理发送和转发数据,因此求解"最小延迟生成树"的问题必须考虑节点的处理延迟.本文分析了两类应用层多播路由模型:基于优化延迟的MRDL模型和基于负载平衡的LRRB模型,并证明都是NP难问题,且提出相应的两类启发式近似算法:MRDL-H算法和LRRB-H算法.最后通过模拟实验说明了所提出算法的高效性、健壮性.In the constructing an efficient application-level multicast tree,many end systems need some time to send and transmit data,so the process delay must be considered in resolving the problem of ＂minimum delay spanning tree＂.This thesis has proposed two application-level multicast router models：MRDL model based on optimum delay and LRRB model based on load balance.At the same time,they have been proved to be NP-hard problems.This thesis has proposed the corresponding heuristic algorithms：MRDL-H algorithm and LRRB-H algorithm.The simulation results have proved these algorithms can transmit the media stream efficiently and robustly.

关 键 词：应用层多播 最小延迟生成树 路由算法 NP-HARD 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]