主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2018年第5期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
曹继军,苏金树.应用层组播的时延受限高稳定性生成树算法.软件学报,2010,21(12):3151-3164
应用层组播的时延受限高稳定性生成树算法
Delay-Bounded and High Stability Spanning Tree Algorithm for Application Layer Multicast
投稿时间:2008-07-18  修订日期:2009-03-31
DOI:
中文关键词:  应用层组播  稳定性  瞬态稳定度模型  生成树算法  启发式策略
英文关键词:application layer multicast (ALM)  stability  instantaneous stability degree model (ISDM)  spanning tree algorithm  heuristic policy
基金项目: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))
作者单位
曹继军  
苏金树  
摘要点击次数: 3771
全文下载次数: 3674
中文摘要:
      应用层组播树会因为单个成员节点的退出或失效而被迫调整其他多个成员节点在组播树中的位置,从而导致多个节点的组播连接被迫中断.该问题被称为应用层组播树的稳定性问题,它严重影响用户接收组播数据的连续性.首先分析了应用层组播树的稳定性问题,提出了瞬态稳定度模型(instantaneous stability degree model,简称ISDM).通过利用组播用户动态行为的统计学特性,提出了一种评估该模型中节点相对离开概率的实用方法.其次,由于实时传输是应用层组播技术的主要应用领域之一,进而基于ISDM模型提出了延迟受限最大瞬态稳定度组播生成树问题——DDSD(the degree-and delay-bounded maximum instantaneous stability degree ALM tree),并且证明了该问题属于NP-Hard问题.为了解决该问题,提出了DDSD-H近似算法,该算法共衍生出3种启发式策略.最后,通过仿真实验分析比较了所提算法在各种启发式策略下的有效性.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 
主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利