【作者】 李雪莲；

【导师】 刘三阳；

【作者基本信息】 西安电子科技大学 ， 应用数学， 2004， 硕士

【摘要】 随着计算机网络的迅速发展，网络功能日益强大。网络中的通信由单一的两点间的通信向多点间的通信发展，因此对多播和群播（是多播的一种推广）技术的研究也成为网络通信领域中的一个重要研究课题。多播是一个源节点将同一信息传送到多个目的节点(但不是所有节点)的通信方式。本文主要研究多播和群播路由算法，即建立满足各种业务服务质量需求的多播树。目前多播路由算法的研究大多都针对无约束多播路由问题、时延受限及有带宽预留机制的多播路由问题。本论文首先介绍了有关多播的相关知识；接着对有多个约束的多播路由问题进行了研究，并且给出了一种满足 QoS 约束可靠的适应性多播路由算法。利用该算法，可以避免在有些节点或边失效(或不满足某种可靠性要求)的情况下依旧选择这些节点和边的可能，有效地减少了信息传送，缩短了传输时延。这是以往多播（multicast）算法中很少考虑的情况。数值实验表明，这种算法是快速而有效的，算法的时间复杂度为Ο(mD logn)。此外，本论文还研究了有带宽预留机制的群播路由问题，给出了两种有带宽约束的群播路由算法和一种带有多个约束的群播路由算法。前两种群播路由算法对 GTM 算法进行了改进，使得两种算法所获得的 GMRP 问题解的总费用几乎总是低于或等于由 GTM 算法所获得解的总费用且时间复杂度不变, 均为Ο(p3n2)。并用仿真实验对其有效性进行了证明。对于带有多个约束的群播路由算法，由于其采用改进了的成本函数，算法的时间复杂度并没有增加，也为Ο(p3n2)。同时还提出了一种满足延迟约束的多播最小生成树算法（时间复杂度为Ο(pn2) ）。更多还原

【Abstract】 With fast development of computer networks, the functions of networks arestrengthened increasingly and developed from simple transmission to many real-timeapplications. Multicast and group multicast are the key of supporting these multimediaapplications. Multicast routing is a network-layer function that constructs paths alongwhich data pachets from a source are distributed to reach many, but not all, destinationsin a communication network, A fundamental issue in multicast communication is how todetermine an efficient message route (multicast routing). Tree construction is acommonly used approach in solving the multicast and group multicast routing problem.This paper centers on the algorithms to construct low cost multicast routing trees withQoS requirements. Now, researches on multicast routing algorithm mainly focus on multicastingalgorithm without constraints, delay-constrained and bandwidth reserved multicastrouting. In this thesis, firstly, the theory on multicast is introduced. Secondly, a researchis made on algorithm satisfying multiple constraints and an adaptive and reliablealgorithm satisfying QoS for multicast is proposed. It overcomes the shortcoming of theexistent algorithms. As a result, it effectively reduces the transmission of informationand the delay of propagation. Its time complexity is Ο(m D logn) . Thirdly, the groupmulticast routing problem with bandwidth constrained is studied, three heuristicalgorithms for group multicast routing are presented. The former two group multicastalgorithms are the improvement of GTM algorithm. Simulation results show that ouralgorithms performed better in terms of cost compared with GTM algorithm and havethe same time complexity Ο(p3n2) . At the same time, a fast heuristic algorithm ofmimimum cost tree with delay constraint are presented, its time complexity is Ο(pn2) .更多还原