论文部分内容阅读
世界上许多事物以及它们之间的联系都可以用图形直观的表示。这时人们往往用结点表示事物,用边表示它们之间的联系。这种由结点和边构成的图形就是图论研究的对象。计算机网络通俗的讲就是大量分散但又互联的自主计算机所构成的系统。计算机网络与图论的研究对象具有天然的相似性,图论的研究成果可以在计算机网络的研究中得到应用和发展。 为了有效地支持多播通信,路由(路径)选择是一个需要讨论的关键问题。路由选择负责对源与目的结点间的多条可行路径根据某种目标加以选择、例如网络资源消耗最低化就是路由选择的重要目标。解决多播路由的流行方法涉及到“树”的构造,如果能构造出合理的多播树,就可以在满足业务需要的前提下,尽量少占用网络资源。 本篇论文在现代图论研究的基础上,由简单到复杂,逐步深入,对多播生成树问题尽可能的作出一个整体的,全面的探索和研究。结合国内外关于多播生成树算法的最新研究成果,在充分考虑到网络动态性的前题下,利用了最大限度地使用原有的计算结果,避免重复计算、以存储空间换取计算时间两种策略,得到一系列计算效率非常高的多播生成树算法,形成一条比较完整的技术路线,对多个研究方向的多播生成树问题均提出了高效率的解决方案。 本篇论文对多播生成树问题进行了比较全面的讨论,涉及内容包括单约束的单树多播、单约束的成组多播等多个方面,所提出的动态最短路径树算法DMDT(Dynamic Minimum Distance Tree),最小代价多播生成树算法FMPH(Fast Minimum Path Cost Heuristic)动态最小代价多播生成树算法DMPH(Dynamic Minimum Path Cost Heuristic),成组多播快速路由算法FGMRA(Fast Group Multicast Routing Arithmetic),都取得了显著的效果,是目前同类问题中比较好的解决方案,达到了预期的目的。