【作者】 唐厚俭；

【导师】 刘三阳；

【作者基本信息】 西安电子科技大学 ， 运筹学与控制论， 2001， 硕士

【摘要】 在计算机网络中，多播是目前研究最多、应用最广泛的连接方式。多播是指源节点将信息通过多播树传送到多个信宿（但非网络中的所有节点），它是点到点通信与广播通信的扩展。实现多播的一般方式是建立Steiner树。本文主要研究多播路由方法，即如何建立满足多播业务QoS要求的性能优异的多播树。 1）总结了现有的无约束多播路由树的建立方法，并分析了各种算法的计算时间复杂度、最坏情况下的性能比以及它们在不同网络中建立多播树的效率，同时给出了一种能更好解决最坏情况下性能比的多播路由算法——3Basic节点组合算法，使得多播路由算法的最坏性能比得到提高，同时还讨论了各种分布式多播算法。 2）本文介绍了带有度约束的多播路由问题，给出了一种基于最短路的带回路检测度约束分布式多播路由算法，使得处理度约束所需传递的信息量大大减少。同时还给出了一种非常健壮性的路由重构算法和该算法的一种低复杂度折衷算法——一层查询分布式算法，它的优点是时间复杂度低。 3）最后给出了算法的数值实验结果，并对算法的模拟与设计提出了一些有用的建议及实现方法。更多还原

【Abstract】 In computer networks, multicasting is a communication pattern that is widely usedand is studied by many researchers. Multicasting involves the message from a sourcenode are distributed to reach many, but not all, destinations, which is the extension ofpoint-to-point and broadcasting communications. Steiner Tree construction is acommonly used approach in solving the multicast route problem. This paper centers onhow to construct QoS constrained multicast routing trees with low cost.1.Summarize all existing heuristic algorithms for the Steiner tree problem, andanalyze their time complexities, worst-case performance ratio and efficiencies indifferent network models. A 3Basic-node combination multicast algorithm withmuch lower worst-case performance ratio is proposed, which can improve theworst-case performance. Moreover, all kinds of distributed multicastingalgorithms are studied.2.Deal with degree-constrained multicast routing problem. Three algorithms aregiven. The first one is a distributed algorithms using shortest-path-basedloop-detection, which can reduce the number of message required to deal with theloop appeared possibly when constructing the multicast route. The Second is avery robust route-reconstruction algorithm. Last, a one-layer query routingalgorithm is given, which has lower time-complexity than the algorithm proposedabove does.3.At last, the experimental results for all algorithms are given. Some useful adviseon the realization of the multicasting algorithms are proposed.更多还原