Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (33): 150-154.

• 网络、通信与安全 • Previous Articles     Next Articles

Dynamic RP relocation algorithm in PIM-SM multicast

ZHANG Min,WANG Hua,MA Jun   

  1. School of Computer Science and Technology,Shandong University,Ji’nan 250061,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-11-21 Published:2007-11-21
  • Contact: ZHANG Min

PIM-SM组播中的RP动态重定位

张 民,王 华,马 军   

  1. 山东大学 计算机科学与技术学院,济南 250061
  • 通讯作者: 张 民

Abstract: The prime problem to construct a shared multicast tree is to determine the position of the shared root,that is,the center selection problem.This is an NP-Complete problem.The positioning of center and the dynamic change of group members directly affects the structure of the multicast tree and the performance of multicast accordingly.Then it is required to adjust the position of the center and rebuild a multicast tree,which is a problem of center migration.How to avoid data loss and reduce the replication of multicast data in the process of center migration needs to be solved.In dynamic networks,the selection and migration of the center are two problems mutually independent and inseparable.They are also two steps indispensable to relocate RP.This paper proposes an RP selection algorithm based on tabu search and a new RP migration algorithm is then put forward.Simulation results show that good performance is achieved in multicast cost,delay from end to end and registration delay,and there is no loss and redundancy of multicast data in the process of migration.

Key words: NPC problem, PIM-SM, group-based, dynamic relocation, tabu search

摘要: 构建共享组播树的首要问题是要决定共享根的位置,即中心选择问题,这是一个NPC问题。中心的定位及组成员的动态变化直接影响到组播树的结构,进而影响到组播的性能,故需要适时地调整中心的位置和重建组播树,即中心的迁移问题,如何在中心迁移过程中避免丢失数据和减少组播数据的冗余是需要解决的问题。在动态网络中,中心的选择与迁移是两个相互独立而又密不可分的问题,是重定位RP不可少的两个步骤,论文提出一种基于禁忌搜索的RP选择算法,继而提出一种新的RP迁移算法。仿真结果表明该算法在组播费用、端到端延迟和注册延迟方面都达到了较好的性能,且在迁移的过程中没有组播数据的丢失和冗余。

关键词: 非多项式完全问题, 稀疏模式协议独立组播, 基于组, 动态重定位, 禁忌搜索