多播路由算法和容错多播的研究

【作者】 丁建；

【导师】 刘凤玉；

【作者基本信息】 南京理工大学 ， 计算机应用， 2004， 硕士

【摘要】 因特网上的多播通信的核心在于多播树的生成，这需要高效的多播树生成算法和协议，本文介绍了多种多播路由算法和路由协议，并对它们的优点与不足进行了比较分析。在本文中，探讨了平衡延迟和带宽消耗的算法，提出了改进的最短路径树算法(ASPT)。ASPT算法在路径长度增加程度可控的程度下最小化带宽消耗，模拟试验表明此算法能够在路径长度有限增加的情况下在很大程度上减少了带宽消耗。另外在RS算法基础上提出受限搜索RS(RSRS)算法，可以在很大程度上的减少建立多播树所花费的时间，同时保证生成的多播树最优。现在关于多播路由的研究大多着眼于多播树的生成，一旦多播树出现故障，就需要对故障点以下的所有多播接收节点进行重新路由甚至对整个多播树进行重新构造，这一方面降低了服务质量，另一方面有些多播应用不允许长时间的中断，对此本文提出了一种多播容错方案，采用在分枝节点之间建立备份路径的措施，可以在很大程度上减少额外的代价，能够在最快的时间内恢复多播树的故障，并使得恢复后的多播树形状基本上没有改变。更多还原

【Abstract】 The core of multicast communication researches on the Internet is how to generate optimized multicast tree. Efficient multicast routing algorithms and protocols are needed. This dissertation introduced many kinds of routing algorithms and protocols, also with the algorithm performance analyses together. In this dissertation, algorithms for generating multicast trees with a trade-off in delay and bandwidth consumption are investigated. The Ameliorated Shortest Path Tree (ASPT) is proposed. The ASPT algorithm minimizes bandwidth consumption. Simulation experiment demonstrates that ASPT algorithm reduces bandwidth consumption greatly with path length increasing a little. In addition, The Restricted Search RS algorithm (RSRS) is proposed based on RS algorithm. It can reduce the time complexity of RS algorithm, at the same time, it guarantee the multicast tree is optimization. Nowadays most of researches on the multicast routing are how to generate multicast tree. In case of multicast tree failure, there need to re-route all of nodes behind the failure point so much as re-build the whole tree, this will deteriorate Quality-of-Service, on the other hand, it is insufferable in some multicast applications. We proposed a Fault-Tolerant multicast scheme to resolve this problem. Our scheme creates backup paths crosswise in the ramose node. It can reduce additional cost greatly and recover the failure of multicast tree rapidly. At the same time, the multicast tree has tiny change.更多还原