基于链路共享的多源选播路由算法

计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (16): 103-106.

基于链路共享的多源选播路由算法

张宏滨1，谭学功1，2，李宁1

1.中山大学信息科学与技术学院，广州 510006
2.暨南大学华文学院，广州 510610

出版日期:2013-08-15 发布日期:2013-08-15

Multisource manycast routing algorithm based on link share

ZHANG Hongbin1, TAN Xuegong1，2, LI Ning1

1.School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510006, China
2.College of Chinese Language and Culture, Jinan University, Guangzhou 510610, China

Online:2013-08-15 Published:2013-08-15

摘要/Abstract

摘要： 选播（manycast）作为一种新型的通信模式，吸引了研究人员越来越大的兴趣。MSPT（Manycast Shortest Path Tree）算法是一种应用广泛的选播路由算法。但是，它没有考虑整体网络资源的利用；DDMC（Destination-Driven for Manycast）算法较好地解决了单源点选播最小生成树问题，但应用场景只是针对“一个对多个中的任意个”。针对“多个对多个中的任意个”的多源选播路由问题，在DDMC算法的基础上作了一些改进。仿真实验结果表明，改进的选播路由算法MBLS（Manycast Based-Link-Share）基于链路共享机制，在空间复杂度和时间复杂度相同的情况下，在选播森林每源点成本上优于MSPT算法。

关键词: 选播, 网络路由, 多点到多点网络

Abstract: As a new kind of communication method, manycast is attracting increasing interest from researchers. Manycast Shortest Path Tree（MSPT） is a widely-used manycast routing algorithm. However, MSPT does not consider overall network resource utilization. DDMC（Destination-Driven for Manycast） can solve the minimal spanning tree problem for single source manycast, but it just considers “one-to-some-of-many” situation. Improvements have been made to solve “many-to-some-of-many” multisource manycast routing problem on the basis of DDMC. Simulation results show that the modified algorithm MBLS（Manycast Based-Link-Share） outperforms MSPT in per-source manycast forest cost under the condition of the same space complexity and time complexity.

Key words: manycast, network routing, multipoint-to-multipoint networks

张宏滨1，谭学功1，2，李宁1. 基于链路共享的多源选播路由算法[J]. 计算机工程与应用, 2013, 49(16): 103-106.

ZHANG Hongbin1, TAN Xuegong1，2, LI Ning1. Multisource manycast routing algorithm based on link share[J]. Computer Engineering and Applications, 2013, 49(16): 103-106.

[1]	史蕊，白晨希. 混沌遗传算法在时延约束选播路由中的应用[J]. 计算机工程与应用, 2013, 49(10): 96-99.
[2]	张园园1，张英2，余镇危1. 基于克隆策略的QoS选播路由算法[J]. 计算机工程与应用, 2011, 47(35): 11-13.
[3]	胡琼琼，雷秀娟，张兰. 改进的蚁群算法在QoS网络路由中的应用[J]. 计算机工程与应用, 2011, 47(13): 212-215.
[4]	肖猛¹,李陶深^1,2. 蚁群算法在时延约束选播路由问题中的应用[J]. 计算机工程与应用, 2008, 44(24): 121-123.
[5]	陈燕宋玲李陶深. 一种有效的实时选播流连接建立算法[J]. 计算机工程与应用, 2007, 43(3期): 115-115.