【作者】 李峰；

【导师】 曹阳；

【作者基本信息】 武汉大学 ， 通信与信息系统， 2004， 硕士

【摘要】 随着Internet的迅猛增长及具有实时要求的新兴业务(如VoIP，视频会议、多媒体远程教学、视频点播等)不断出现，用户对网络服务质量(QoS，Qualityof Service)的要求越来越高。 路由问题处于网络的核心地位，也是决定网络传输质量的主要因素之一。QoS路由(QoSR，QoS Routing)是QoS研究中的核心技术和热点问题。传统路由算法满足不了用户的QoS要求，而且在最短路径上容易产生拥塞。因此，需要采取一定的约束路由机制来平衡网络负载，提高传输效率。QoS路由的出现就能够有效地解决这些问题。多约束条件下的QoS路由问题是一个NP-完全问题，一般采用启发式算法寻找其次优解。网络链路状态信息的非精确性是客观存在的，因而研究非精确网络状态信息下的QoS路由算法十分必要。多路径路由算法在克服网络状态信息非精确性方面具有较好的性能，并能有效平衡网络负载。 现有的QoS路由算法有各种启发式算法、神经网络算法、遗传算法和蚂蚁算法等。这些算法往往存在约束条件单一，没有考虑网络负载平衡，也没有考虑与传统最短路径优先路由算法的共存问题等缺陷。 基于现有方法存在的局限性，本文研究了非精确网络状态信息下的多路径QoS路由算法，在改进原有算法的基础上，提出并实现了2种QoS路由算法：Minpath算法和KMulpath算法。Minpath算法基于改进的Bellman_Ford算法，通过剪裁策略减少了算法的搜索空间，寻找出满足带宽、时延和跳数约束的最小代价路由。KMulpath算法采用深度优先搜索策略，计算并预存K条满足带宽、时延和跳数约束的QoS路径。通过路径评价函数和对路径带宽利用率的比较，找出最优和次优路径。在最优路由失效时迅速转到备用的次优路由上去，极大地减少了重路由开销，能有效解决由于链路状态信息的非精确而引起的问题。 为了验证算法的有效性，用ns-2建立网络仿真场景，采用这两种QoS路由算法进行仿真试验。通过与传统算法性能的比较，可以看出这两种算法能平衡网络负载，提高网络资源利用率，具有较好的性能。 对QoS路由算法与传统最短路径路由算法的共存问题进行了初步探讨。在仿真中根据网络流量的变化自适应调整路由策略，动态选择是采用原来的最短路径路由还是QoS路由，从而解决了与传统路由算法的共存问题。实验结果表明KMulpath算法能与传统算法良好共存，同时提高了网络性能。更多还原

【Abstract】 As the fast growth of Internet and the continues emergence of newly services having real time demand such as Voice over IP, Video Conference, Multimedia long-distance Education and Video Programme, user’s demand on Quality of Service (QoS) becomes higher and higher.Routing is the kernel of network. It is also one of the main factors deciding QoS. QoS Routing (QoSR) is the core technique and hotspot in the research of QoS. Traditional routing algorithm can’t meet the user’s QoS need. At the same time, the shortest path can easily become congested, which leads to the network performance drops dramatically. So some constrained-routing mechanism must be taken to balance network load and improve transfer efficiency. The emergency of QoS routing can solve this problem efficiently. Multiple constrained QoS routing problem is a NP-complete problem. Currently, we search hypo-excellent paths using heuristic algorithm to solve this problem. The imprecision of network link-state information is objective, thus, the research of QoS routing algorithms under imprecise link-state information becomes necessarily. Multi-path routing algorithm can balance network load and have a preferable performance in coping with imprecise network link-state information.The existing algorithms of QoS routing include various heuristic algorithms, neural network-based algorithms, hybrid genetic algorithms, ant-algorithms and so on. These algorithms exist some defects as foliows:(1) the constrain condition of these algorithms is single (2) they dont take the network load balance into consideration (3) they don’t consider the coexistence of themselves with traditional shortest-path first algorithm.Aiming at solving these defects, we design and realize multi-path QoS routing algorithm under imprecise link-state information in this paper: Minpath algorithm and KMulpath algorithm. Based on unproved Bellman_Ford algorithm, Minpath algorithm can find the least cost path meeting bandwidtiu delay and hop constrains. Using deepest first search strategy, KMulpath algorithm can find and keep multiple QoS paths meeting QoS constrains in advance. Then, it can select the best and hypo-best path among these multiple QoS paths through path evaluation function and the comparison between bandwidth utilization of these paths. When the best route is invalid, route can be switched to the hypo-best path quickly. As a result, it can decrease reroute spending greatly and solve the problems caused by imprecise link-state information.To validate the efficiency of our algorithms, we create network simulate scenes and go along simulate experiment using these two QoS routing algorithms. By comparison with traditional shortest path first routing algorithm, it can be seen that these two algorithms can balance network load and heighten network resource utilization.Also we primarily probe into the coexistence problem of QoS routing algorithm with traditional shortest path first routing algorithm. In network simulation, our dynamical routing algorithm can adjust routing strategy adaptively according to changes of network stream , choose route dynamically and decide using whether the shortest path or the QoS path, solving the problem of the coexistence of QoS routing algorithm with traditional routing algorithm. The result of simulation experiment indicates that KMulpath algorithm can coexist with traditional shortest-path algorithm excellently and has a preferable network performance.更多还原