【作者】 陈兴华；

【导师】 郑连伟；

【作者基本信息】 东北大学 ， 运筹学与控制论， 2008， 硕士

【摘要】 当前许多多媒体业务都要求网络具有多播(multicast)能力,例如：音频、视频会议、交互式仿真、网络游戏、分布式数据库等。多播技术,将同样的数据从一个源节点同时传输给大量的目的节点,从而大大节省了网络带宽,减少了数据冗余,在一定程度上解决了多媒体通信中的带宽瓶颈问题,将成为未来的一项重要技术。多播路由算法的目标是寻找一棵连接源节点和多个目的节点的多播树,同时满足各种服务质量需求。在实时交互性多播应用中,时延和时延抖动等服务质量因素尤为重要。为此,论文主要研究满足QoS约束中时延和时延抖动约束的多播路由问题。论文首先研究时延约束下的多播路由问题,该问题的目标是创建一棵覆盖源节点和目的节点的代价最小树,且满足端到端时延要求。这个问题被证明是NP完全问题。我们在研究已有算法的基础上,提出两个新的启发式算法。一种算法充分考虑链路共享对网络费用和链路时延的影响,提出了关键节点的概念。使得算法可以在满足时延约束的情况下,找到费用最小的多播树。另一种算法提出了节点优先函数和链路选择函数的概念,在构造满足时延约束低代价的树时运用了单播策略。分析的结论是这两种算法都是低复杂度、低费用并符合时延约束的多播路由算法。然后,论文分析限制时延抖动对某些多播应用的重要意义,并就时延和时延抖动约束的多播路由问题提出了一种新的链路选择函数。基于这个函数我们提出了一个时延和时延抖动约束的启发式Steiner树算法,通过仿真表明,该算法在时延抖动方面有较好的性能。更多还原

【Abstract】 Recently, many of the multi-media applications require networks to provide multicast. These applications, for instance, can be audio、video conference、distributed simulation、network game、distributed database and so on. Multicast technology, which transmits the same data from a source to a large number of destination nodes simultaneously, in order to save a great deal of bandwidth and reduce data redundancy in the network, can resolve the problem of bandwidth bottlenecks of the multimedia communications in a certain extent, and will become an important technology in the future.The main purpose of multicast routing algorithms is to construct a tree rooted at the source and spanning all destinations, while the quality of service (QoS) will be satisfied. Delay and delay variation are two QoS metrics that directly related to real-time interactive applications. In this thesis we further study the problem of delay and delay variation bounded multicast routing.The first part considers the delay constraint multicast routing problem. This problem refers to constructing minimum-cost spanning trees constrained by delay, which is known to be NP-Complete problem. On the basis of some related work in this area, we present two new heuristic algorithms. One of the algorithms considers the influence that the links to the cost of the tree and the delay of the links, we present the concept of key nodes, the algorithm can find the low-cost multicast tree under the delay constraint. In the other algorithm we introduce node priority function and link choice function, and use the politics of unicast routing algorithm for generating low-cost tree while satisfying the delay constraint. The conclusion is that these two algorithms are of low time complexity and low-cost under delay constraint. In the second part, we discuss the significant of delay variation in some multicast applications. We also present a heuristic algorithm for multicast routing problem with delay and delay variation constraints. Based on the function we give a delay and delay variation bounded heuristic Steiner tree constructing algorithm. It’s shown that, in terms of delay variation, the heuristic algorithm demonstrates good average case behavior through simulations.更多还原