Delay-Bounded and High Stability Spanning Tree Algorithm for Application Layer Multicast
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 18,2008
  • Revised:March 31,2009
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063