摘要
该文提出了一种时延约束的多共享组播树构造算法,以解决多点到多点组播路由情况下单棵共享树无法满足时延约束的问题。该算法构造覆盖所有源节点和目的节点子集的多棵共享树以满足时延约束的要求,并通过减少共享树个数降低管理开销。该算法计算以每个节点为中心的共享树所能达到的目的节点的子集,将原问题转换为集合覆盖问题,并采用基于矩阵的启发式算法进行求解。仿真实验将该算法和同类算法进行比较,结果表明该算法在不增加管理开销和中心数的情况下,有效地减少了运行时间。
In many-to-many muhicast routing, a single shared multicast tree may not be able to satisfy the delay constraint. Under such circumstances, this paper proposes a delay-constrained multiple shared multicast trees construction algorithm. The algorithm constructs multiple shared muhicast trees including all source nodes and a subset of destination nodes to meet the requirement of the delay constraint, and minimizes the number of shared trees to reduce the management overhead. The algorithm computes the subset of those destinations that can be reached with a shared tree centered at each node, transforms the problem into a set-covering problem, and solves it by using a method based on matrix. Simulations demonstrate that this algorithm has the shortest run-time in all compared algorithms, without increasing management overhead and number of centers.
出处
《南京理工大学学报》
EI
CAS
CSCD
北大核心
2006年第2期127-131,141,共6页
Journal of Nanjing University of Science and Technology
基金
国家自然科学基金(60273035)
南京理工大学科研发展基金
关键词
多共享组播树
时延约束
多点到多点组播路由
QOS
multiple shared muhicast trees
delay-constraint
many-to-many muhicast routing
quality-of-service
