【作者】 石莎；

【导师】 刘三阳；

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

【摘要】 Internet高速网络中实时和多媒体应用业务的迅速发展,要求通信网络能提供高效的服务质量(QoS)支持,但是传统的“尽力而为”网络机制并不能满足QoS通信的要求.近几年的研究表明网络路由算法对实现网络质量服务具有非常重要的作用,因此QoS路由算法日益成为网络研究的核心问题之一。本文首先介绍了QoS路由算法的发展背景和研究现状,随后对目前可用于解决QoS路由算法问题的思想方法做了较详细的分析和归纳;对传统Dijkstra最短路算法编程实现之后,从三个方面对传统算法加以改进.最后建立了一种QoS路由数学模型和综合评价指标,并给出了适合该模型和综合评价指标的QoS路由Dijkstra最短路改进算法.具体研究工作如下:(1)分析当前QoS路由算法的发展现状和需求,讨论其网络模型和算法机制;然后从思想、具体步骤、示例和优缺点等方面较详细地分析和归纳了目前可用于解决QoS路由问题的八种思想方法;(2)从最短路生成树和最小生成树两个方面对传统Dijkstra最短路算法进行编程;从数据结构、搜索方向和路由信息的数据存储三个方面提出了改进思想,并比较其优缺点;(3)建立了一种QoS路由数学模型和综合评价指标,基于该模型和综合评价指标,给出了针对带宽、时延、丢包率、成本和时延抖动及负载分布的QoS路由Dijkstra最短路改进算法;更多还原

【Abstract】 With the fast development of real-time and multimedia applications in high-speed Internet, the high-efficient quality-of-service support is required in the communication network. But the traditional "best-effort" network mechanism can not guarantee the QoS communication. Recent research shows that the algorithm of network routing plays an important part in providing quality-of-service guarantees, so the QoS-based routing algorithm becomes one of the nuclear network problems.First, this dissertation introduces the background of the QoS-routing technology and it’s present research condition; the methods that can be used to solve the problems of QoS-routing algorithm are analysed and concluded in detail; then the theory foundation is established for the network routing algorithms with QoS constraints, the traditional Dijkstra’s shortest path algorithm is realized from two different aspects; and three improved methods are proposed for the Dijkstra algorithm; at last, the model and Synthetical evaluation system of QoS-Routing are established, and the improved methods of Dijkstra’s shortest path algorithm for meeting the requirements are given and validated. The main works are listed as follow:(1) Analyzing the current development actuality and requirement of QoS-Routing; Discussing its network model and QoS-Routing algorithm mechanism; Respecting their ideas, detailed steps,demonstrations and relative merits, the existing QoS-Routing research methods are classified and summarized ;(2) The Dijkstra’s shortest path algorithm are realized from two aspects;According to the data structure, search directions and data storage of routing information, three improved Dijkstra algorithms are given;(3) Put forward a QoS routing algorithm model and the synthetical evaluation system DQT; based on the model and the system, the improved Dijkstra algorithm is proposed regarding to bandwidth, time, ratio of loss-packet,cost, time dithering and load distributing.更多还原