【作者】 易红春；

【导师】 陈蜀宇；

【作者基本信息】 重庆大学 ， 计算机系统结构， 2003， 硕士

【摘要】 随着当前Internet的发展和各种多媒体应用的出现，组播技术得到大量应用。组播指将同一信息从源结点传送到网络中多个结点（不一定是网络中所有结点）。实现组播的一般方式是建立组播树, 组播树的优点在于：首先，信息以并行方式沿着树枝发送到不同的组播终点，从而降低了信息传递的时延；其次，信息的复制只在树的分支处进行，因此网络中需要传送的复制信息量最少，能够节约网络带宽资源，降低网络负载，减少拥塞。因此组播成为目前研究最多、应用最广的网络信息传输方式。组播路由算法主要用来建立一棵性能良好的组播树，并使它能够满足各种业务的服务质量需求。本文首先对网络路由选择技术，包括单播路由、组播路由和基于遗传算法的组播路由选择技术进行了分析总结，指出简单性、通用性、外延性、层次型路由和不精确状态信息下的路由是未来服务质量组播路由的研究重点。然后分析了组播和组播路由选择技术的原理，组播路由算法通常采用启发式技术，要么太复杂难以求解，要么太费时不能实际应用，而遗传算法简单高效，非常适用于组播路由选择。随后介绍了遗传算法的基本思想和运行过程以及遗传算法的数学基础，并对遗传算法的基本要素设计技术和改进策略进行了分析总结。在此基础上，将多种群并行技术和退火技术相结合，以克服现有基于遗传算法的组播路由算法过早收敛和后期搜索速度较慢的缺陷，且使用树状编码方法，提出求解带宽、时延、时延抖动和分组丢失率约束的代价最小组播树的多种群并行退火遗传组播路由算法。从理论和实验上验证了算法的正确性，并分析了算法的最坏时间复杂度和空间复杂度，其最坏时间复杂度为(max(e+n㏒+k ,n2))，最坏空间复杂度为( kn2)，它们均为多项式解，表明算法也是有效的。更多还原

【Abstract】 With the development of Internet and the advent of various multimedia applications, multicasting technology is widely applied. Multicast routing constructs paths along with data packets from a source are distributed to reach many, but not all, destinations in a communication network. Tree construction is a commonly used approach in solving the multicast routing problem. One advantage of multicast tree is that data are distributed to different multicasting destinations along the branches in parallel, which reduces the delay. The other is that message need only be replicated at forking nodes, which minimizes the data replication, spares the network bandwidth, reduces the network load and lessens the congestion. Thus multicasting is mostly researched and utilized at present. Multicast routing algorithms are used to compute multicast trees that satisfy quality of service requirement.Firstly, this paper analyses and summarizes the routing technology, including unicast routing, multicast routing and multicast routing based on genetic algorithm, presents the research of quality of service multicast routing will be focused on simplicity, generality, extensibility, hierarchical routing and routing with imprecise state information.Then, the paper analyses the principle of multicast and multicast routing technology. Commonly multicast routing algorithms use heuristic technology, either too complex to solve problems, or too time-consuming to be applied, and genetic algorithm is simple and effective, suitable for multicast routing. Subsequently the paper introduces the basic idea, the process and the mathematical fundament of genetic algorithm, analyses and summarizes the basic element design technology and the improvement methods of genetic algorithm.On the above, to overcome the pre-maturity and low speed of search in the late phase of multicast routing algorithm based on genetic algorithm, the author gives the multi-population parallel annealing genetic multicast routing algorithm to solve the bandwidth, delay, delay jitter and packet loss constrained least-cost multicast routing problem, which combines the<WP=6>multi-population parallel technology and annealing technology, adopts tree-like coding approach. In addition, the author verifies the correction of the algorithm theoretically and experimentally, and analyzes the time complexity and the space complexity, points out the worst time complexity is (max(e+n㏒+k ,n2)) and the worst space complexity is (kn2), which are polynomial solutions and indicate the algorithm is effective.更多还原