网络通讯中的QoS组播路由算法研究

论文摘要

组播路由算法属于网络优化的范畴,它是计算机网络的应用和发展中的核心问题。组播路由算法对于减小计算机网络的流量和减轻服务器的负担都有着非常大的意义。随着人们对网络服务质量的要求(quality of service,简写为QoS)越来越高,在求组播树的过程中就需要加入越来越多的限制条件,这也使得我们所求解的问题成为NP完全问题。对于此类问题,我们只能设计出不同的策略来尽可能快的求解出尽可能逼近最优解的结果。本文的前两章,主要讨论了组播路由算法研究过程中要用到的一些基本知识,包括图论中的一些基本概念和算法,主要为第三章和第四章的研究工作做准备。在第三章和第四章中,介绍了本文所取得的主要结果,可概括如下:1. 在第三章中,首先对Dijkstra算法进行了修正以适用于我们研究的主题,然后在虚拟网图中运用我们所制订的策略,即按照带宽要求由大到小为节点排序,按照顺序利用修正的Dijkstra算法为图中的每个节点寻找到可行的路。在此算法中,并不能保证每一个节点最后都有可行路,但根据计算机网络的工作原理,可以将这些节点并入下一次任务。2. 在第四章中,我们提出了一种基于最小树算法的组播路由算法。首先构造一棵树,使得所有的向服务器发送了请求的节点都被包含在树中。然后对树中的节点逐个进行检查,看组播树为其提供的路是否满足该节点的要求。对于那些不满足要求的节点,我们利用推广的Dijkstra算法为其寻找新的符合其要求的最小费用路,直到所有的节点都满足约束。

论文目录

• 摘要
• Abstract
• 1绪论
• 1.1计算机网络在信息时代的作用
• 1.2网络协议在计算机网络中不可替代的作用
• 1.3路由算法
• 1.3.1路由算法简介及优化准则
• 1.3.2QoS组播路由算法产生的背景
• 1.3.3组播路由算法
• 1.3.4组播路由算法分类
• 1.4目前研究现状及取得的成果
• 1.4.1Steiner树问题
• 1.4.2近年来一些好的QoS组播路由算法
• 2基本理论和算法
• 2.1有向图与有向网络的基本概念
• 2.2无向图与无向网络的基本概念
• 2.3组合优化和计算复杂度
• 2.3.1组合优化问题
• 2.3.2计算复杂度
• 2.4最小树及其算法
• 2.4.1树和最小树
• 2.4.2求最小树的算法
• 2.5Dijkstra算法
• 3对一类overlay层QoS组播路由问题的模型的改进
• 3.1引言
• 3.2原数学模型
• 3.3改进后的数学模型
• 3.4算法
• 3.4.1Modified Dijkstra算法
• 3.4.2MMD算法
• 3.5算法分析
• 4一种基于最小树的QoS组播路由算法
• 4.1预备知识
• 4.2数学模型的建立
• 4.3组播算法
• 4.4算法分析
• 结论
• 参考文献
• 附录AMMD算法的C语言实现
• 索引
• 攻读硕士学位期间发表学术论文情况
• 致谢
• 大连理工大学学位论文版权使用授权书