###
DOI:
Journal of Software:2010.21(12):3151-3164

应用层组播的时延受限高稳定性生成树算法
曹继军,苏金树
()
Delay-Bounded and High Stability Spanning Tree Algorithm for Application Layer Multicast
CAO Ji-Jun,SU Jin-Shu
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 4256   Download 3977
Received:July 18, 2008    Revised:March 31, 2009
> 中文摘要: 应用层组播树会因为单个成员节点的退出或失效而被迫调整其他多个成员节点在组播树中的位置,从而导致多个节点的组播连接被迫中断.该问题被称为应用层组播树的稳定性问题,它严重影响用户接收组播数据的连续性.首先分析了应用层组播树的稳定性问题,提出了瞬态稳定度模型(instantaneous stability degree model,简称ISDM).通过利用组播用户动态行为的统计学特性,提出了一种评估该模型中节点相对离开概率的实用方法.其次,由于实时传输是应用层组播技术的主要应用领域之一,进而基于ISDM模型提出了延迟受限最大瞬态稳定度组播生成树问题——DDSD(the degree-and delay-bounded maximum instantaneous stability degree ALM tree),并且证明了该问题属于NP-Hard问题.为了解决该问题,提出了DDSD-H近似算法,该算法共衍生出3种启发式策略.最后,通过仿真实验分析比较了所提算法在各种启发式策略下的有效性.
Abstract:In application layer multicast (ALM) tree, when a parent node quits or fails, all its descendent nodes must adjust their positions, which causes the interruptions of multicast connections. This problem is called stability problem of ALM trees, and it may affect the continuity of multicast data transmission and then degrade user experience seriously. This paper first analyzes the stability problem of ALM trees and proposes the instantaneous stability degree model (ISDM). An approach which takes advantage of the statistical properties of members’ join-leave behaviors is proposed to estimate the relative leave probability of member nodes in ISDM. Then, real-time transmission is one of the important aspects of ALM and one major objective of the ALM-based real-time transmissions is to determine multicast tree so as to guarantee the lower delay. This paper proposes the DDSD (the degree-and delay-bounded maximum instantaneous stability degree ALM tree) problem based on the ISDM. The DDSD problem is proved to be NP-Hard and an approximation algorithm (i.e. DDSD-H) is proposed to solve it. In addition, three heuristic policies are presented for the algorithm. Finally, the simulation results demonstrate the validity of the proposed algorithms and the comparison in the performance of the three heuristic policies is made.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant No.906004006 (国家自然科学基金); the National Basic Research Program of China under Grant No.2009CB320503 (国家重点基础研究发展计划(973)) Supported by the National Natural Science Foundation of China under Grant No.906004006 (国家自然科学基金); the National Basic Research Program of China under Grant No.2009CB320503 (国家重点基础研究发展计划(973))
Foundation items:
Author NameAffiliation
CAO Ji-Jun  
SU Jin-Shu  
Reference text:

曹继军,苏金树.应用层组播的时延受限高稳定性生成树算法.软件学报,2010,21(12):3151-3164

CAO Ji-Jun,SU Jin-Shu.Delay-Bounded and High Stability Spanning Tree Algorithm for Application Layer Multicast.Journal of Software,2010,21(12):3151-3164