日益增多的网络应用,使得因特网正从尽力而为的网络,进化到对不同网络应用提供不同等级服务质量的网络。因而,网络学术界对网络能否提供QoS能力非常关注,并提出了包括IntServ,DiffServ,MPLS等在内的几个支持QoS的网络模型。然而,目前因特网提供QoS的能力仍然不能满足不同应用的要求,其中重要原因之一是缺乏既有效又实用的解决手段,因而对支持QoS的网络的研究是计算机网络的一个研究热点。 QoS路由(QoSR)是支持QoS的网络体系结构中的重要组成部分。设计有效的QoS路由算法是QoS路由面临的关键问题之一,旨在利用QoS路由协议提供的网络状态信息,为不同网络应用寻找满足QoS需求的可行路径。论文针对QoS路由算法设计问题进行了深入研究,并提出了有效的QoS路由算法。 在QoS路由算法研究过程中,形成了三类重要子问题:约束最短路径问题(RSP);多约束路径问题(MCP);多约束优化路径问题(MCOP)。论文研究发现,这三类子问题都可以通过转化为一个特殊的多目标优化问题而获得解决,考虑到Pareto最优是多目标优化问题中的重要概念,论文首次把Pareto最优的相关概念引入到QoS路由中,并根据这些重要概念,研究了QoS度量空间划分问题,建立了基于Pareto最优的QoS度量空间区分框架POPF。在POPF中,QoS度量空间被划分成三个部分:可行区域、不可行区域以及NP完全区域,这些区域具有明确的实际意义。论文着重讨论了两可加约束QoS路由问题Pareto层的分布特性,对其中Pareto最优点的分布进行了深入的研究。指出Pareto最优点的数目和分布都对QoS度量空间划分产生影响,并给出了一种计算Pareto最优点的方法。POPF不但为在QoS路由中运用Pareto最优概念提供了理论基础,而且从算法采用的搜索方式,到算法的终止条件,甚至路由请求的生成方式等方面,都对QoS路由算法的设计和评估具有一定的指导作用。 论文首先提出了用来解决两可加约束的QoS路由算法。算法充分利用了POPF中的重要结论,因此具有良好的前瞻特性,避免了大量冗余计算。然后,论文定义了基于法线测量的非线性路径长度方程NM_LEN,并基于NM_LEN提出了解决MCP问题的NM_MCP算法。NM_MCP算法分为两个阶段:预计算阶段和在线计算阶段。在预计算阶段,算法具有较小的执行周期,在一定程度上减小了不精确网络状态信息对算法的影响。另一方面,即使需要在线计算,NM_MCP算法也只调用一次Dijkstra算法。由于预计算阶段采用线性搜索方法,而在线计算阶段则采用非线性搜索方法,因而NM_MCP算法成功结合了预计算和在线计算,线性搜索和非线性搜索的优点。仿真实验表明,与