【作者】 江昊；

【导师】 晏蒲柳；

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

【摘要】 随着计算机技术和通信技术的飞速发展，Internet以其便捷、价廉的优势，吸引着越来越多的用户和新业务加入其中，目前网络承载的业务包括数据、语音、视频等多种业务，为实现多种业务共存，多种应用共存，服务质量(QoS)控制机制是必需的。Internet已逐步由单一的数据传输网向多媒体综合传输网演进。但目前Internet中的传输模式“尽力而为”(Best-Effort)服务，无法满足多媒体应用和各种用户对网络传输质量的要求。因此，以提高网络资源利用效率、为用户提供高质量服务作为目标的QoS(Quality of Service)研究是当前Internet领域的热点之一。因为路由直接关系到网络的性能，所以搜索满足约束并优化网络资源利用的QoS路由是全网和局部网络的QoS控制的核心问题之一。本文重点研究了目前QoS路由研究中的几个热点难点问题，具有重要的理论意义和使用价值。本文的主要工作如下： (1)本文研究了QoS路由的一个重要问题---多约束最优路径问题(Multi-constrained Optimal Path，MCOP)。多约束最优路径问题，又称多约束最小代价路径问题，是QoS路由中一个很重要的问题，它涉及网络使用的计费，用户的付费，网络的优化等。本文提出了新的多约束最优路径选择算法---LBPSA(Lagrange Branch-and-Bound Path Selection Algorithm)，LBPSA利用拉格朗日松弛搜索出多约束最小代价路径的上界和下界，然后使用分枝界定反向搜索，得到多约束最小代价路径的成功率更高，而且复杂度相对较低。为提高搜索的成功率，本文提出了一种新的拉格朗日乘子在网络结构中的迭代方法，并利用拉格朗日乘子迭代的结果和属性确定了多约束最小代价QoS路径的边界，提出了反向分枝界定搜索方法以得到多约束最小代价QoS路径。实验结果表明LBPSA在搜索多约束最小代价路径的成功率比目前公认性能较好的H_MCOP算法更有效，而且算法复杂度也较低。 (2)本文研究了目前QoS路由的一个难点问题----多业务流共存的问题。本文从路由的角度提出了一种新的算法——综合度量路由算法，该算法在保证QoS流的延迟、带宽要求和“尽力而为”流的带宽要求同时，合理选择路由，利用资源，在相同条件下，比现有的最短路径路由算法能容纳更多的QoS流，而且不会消耗过多的网络带宽资源。 (3)在现有的基于探测法的分布式QoS路由算法的基础上，本文充分利用了探测法分布式的特点，借鉴蚂蚁路由算法的思想提出了一个基于探测法的QoS路由算法一MLP以(Multi一p毗Limited Prob访g助uting Algorithm)。在MLpRA中，本文提出最短路径优先探测的方法减少探测包的发送，同时提出“待完成路径”的思想搜索出更多的可行路径。在返回包返回的过程中提出在中间节点保留路径选择“痕迹”的方法，同时也记录其他请求留下的“痕迹”，通过分析比较选择最优路径，减少拥塞和流量溢出。更多还原

【Abstract】 Following the fast growth of the Internet in recent years, more and more multimedia application carry out in the Internet. Future networks are expected to support various applications, specially multimedia application such as VoIP, VoD. To satisfy different QoS (Quality-of-Service) requirements, some mechanisms need to be employed. But because the Internet nowadays based on IPv4 only provides the best-effort service, and no QoS guarantees provided. QoS guarantee for the next-generation Internet is a challenging problem, and QoS guarantee is also a hot-topic in Internet research. Among QoS guarantee mechanism, QoS routing is one of the key issues. QoS routing has two objectives: (1) find a feasible path for QoS traffic to provide the QoS guarantee; (2) maximizing the utilization of the whole network.In this thesis, we research some problems in QoS routing. The main contributions of this thesis are as follows:(1) To obtain multi-constrained QoS path with minimal cost, a least-cost QoS path selection algorithm-LBPSA(Lagrange Branch-and-Bound Path Selection Algorithm) is presented. This algorithm uses Lagrangian relaxation to obtain the lower bound and the upper bound of the least cost of multi-constrained QoS path. And finds the multi-constrained QoS path with least cost by branch-and-bound method. In solving the Lagrangian multiplier problem, it introduced a new iteration method. Through recursion from destination to source based on branch-and-bound scheme, the least-cost multi-constrained path is obtained. The proposed algorithm has a pseudo polynomial running time. The simulation shows that the algorithm can find the path with high success ratio and low complexity. The success ratio is higher than the H_MCOP that is the main algorithm of MCOP.(2) The second objective of QoS routing is maximizing the utilization of the networks. To QoS traffic, it means that the networks admit more QoS flows that have different QoS requests, including best-effort flows. It is multiple flows coexistence problem. We propose a novel method to this problem- the synthesis metrics routing algorithm (SMRA). SMRA synthesize the QoS delay constrain and the bandwidth request of the QoS flow to form the metrics. Based on the synthesis metrics, SMRA use the shortest path algorithm to search pathfor the QoS flows and best-effort flows. The simulation shows that the networks with SMRA can admit more QoS flows that have different delay request. And the load of the whole networks increase very little.(3) The probing method is a good distributed QoS routing. We propose a new routing algorithm based on probing- MLPRA(Multi-path Limited Probing Routing Algorithm). In MLPRA, we propose two methods- shortest path first probing and saving incomplete path, to search more feasible QoS paths by using limited probing. In the acknowledge procedure, the ack deposit the "pheromone" and get the "pheromone" deposited by the other acks. In simulation, MLPRA can search more feasible paths than DRA, the other probing QoS routing algorithm, and use little probing packets. Through "pheromone’", the congestion probability of MLPRA is little than widest-shortest routing algorithm and shortest-widest routing algorithm.更多还原