基于受限时延和时延抖动的最小代价组播树算法研究  

Algorithm research of minimum cost multicast tree based on bound delay and delay variation

作　　者：樊秀梅[1] 陈常嘉[1] 

机构地区：[1]北方交通大学电子信息工程学院,北京100044

出　　处：《铁道学报》2000年第4期54-59,共6页Journal of the China Railway Society

摘　　要：随着高速分组交换网络和因特网的高速发展 ,越来越多的应用 (如视听电视会议、远程教学、资源发现、计算机协同工作等 )需要多媒体信息的传输和多点连接 ,这就需要研究如何构造有效组播通信树的问题。本文首先给出基于受限时延和时延抖动的最小代价组播树问题的网络模型及其数学描述 ,并确定寻求这样的受限树是NPC问题。然后提出一个启发式算法来求解该问题 ,并分析了算法的复杂度。最后 ,显示了目的地动态变化时 。With the development of high speed packet switched network and internet, the more and more applications need the transmission of multimedia information and multi point connection. This need to research the problem how to construct feasible multicast tree. This paper first discusses the minimum cost multicast network model and its mathematical model based on bound delay and delay variation, and then provides a heuristic algorithm to solve the problem and shows the time complexity analysis. Finally, this paper also shows that it is possible to dynamically reorganize the initial tree in response to changes in the destination set ,in a way this is minimally disruptive to the multicast session.

关 键 词：最短路径树 受限组播树 斯坦利树 组播路由树 

分 类 号：TN919.1[电子电信—通信与信息系统]