基于多约束QoS路由算法综述

随着网络技术的不断发展,实时多媒体技术不断涌现。如何根据不同的服务提供不同的QoS保证,并保证网络资源的有效利用,便成为当前互联网的一个重要任务。对该问题的解决方法称为多约束最优路径（MCOP）问题,MCOP问题是一个NPC问题,求解MCOP问题的算法可分为精确、近似和启发式等算法。文章通过对目前所出现的算法按照精确算法和近似算法两大类进行分析,分析目前出现的算法的一些优缺点,并根据网路技术的发展趋势,对现行多约束路由算法在以后如何实现更加快速精确的路径计算提出几点展望。     

快速启发式多约束优化路径算法研究

针对QoS路由算法中多约束算法的不足,提出了一种新的多约束算法:快速启发式多约束优化路径算法(FH_MCOP)。与现有的路由算法相比,它有两个显著的不同:增加了一个λ快速计算机制,可以降低计算复杂度和加快计算速度,缩短算法响应时间;对MCOP算法进行了有效的改进,使计算结果达到优化。计算结果表明,FH_MCOP能针对多约束优化路径问题的特点降低计算量和提高计算速度。     

多约束最短链路分离路径精确算法

在通信的源和目的间寻找两条(主用和备用)链路分离的QoS路径是提供可靠QoS路由的重要途径.现有求解多约束链路分离路径对(multi-constrained link-disjoint path pair,简称MCLPP)的算法难以保证求得存在于任意网络中的可行解和最优解.为解决这一问题,分析了MCLPP问题最优解的性质,提出了精确算法的设计原则,在此基础上给出了求解MCLPP问题的精确算法(link-disjoint optimal multi-constrained paths algorithm,简称LIDOMPA算法),可对任意网络求解客观存在的多约束最短链路分离路径对.为了降低算法的复杂性,引入了候选最优解、紧缩的约束向量和结构化的路径支配3种关键方法,在保障算法精确性的同时,有效地降低了LIDOMPA的搜索空间.大量的实验结果表明,LIDOMPA的求解能力优于现有算法,同时可以实现较低的算法执行时间开销.     

多约束最短链路分离路径精确算法

在通信的源和目的间寻找两条(主用和备用)链路分离的QoS路径是提供可靠QoS路由的重要途径.现有求解多约束链路分离路径对(multi-constrained link-disjoint path pair,简称MCLPP)的算法难以保证求得存在于任意网络中的可行解和最优解.为解决这一问题,分析了MCLPP问题最优解的性质,提出了精确算法的设计原则,在此基础上给出了求解MCLPP问题的精确算法(link-disjoint optimal multi-constrained paths algorithm,简称LIDOMPA算法),可对任意网络求解客观存在的多约束最短链路分离路径对.为了降低算法的复杂性,引入了候选最优解、紧缩的约束向量和结构化的路径支配3种关键方法,在保障算法精确性的同时,有效地降低了LIDOMPA的搜索空间.大量的实验结果表明,LIDOMPA的求解能力优于现有算法,同时可以实现较低的算法执行时间开销.     

多约束QoS多播路由的模型和算法研究

随着高性能网络、移动网络及Internet的不断发展,具有QoS约束的多播路由技术已成为网络及分布式系统领域的一个重要研究课题。基于约束多播路由的目的在于鉴别一条路径满足QoS约束,然而,多加、乘约束的路由是一个NP-完全性问题。因此,快速的和精确的约束路由算法是少有的,甚至不存在。如此基于路由算法的需求导致众多的启发算法和一些少有的QoS算法的出现。文章描述了一种适用于研究QoS多播路由的网络模型,给出一个完全,简洁和公平地评价7个典型的基于多约束QoS多播路由算法,并且提供多约束路径算法的最坏情况下复杂性的比较。     

一种启发式算法在多受限QoS路由中的研究

随着互联网的广泛应用,网络服务质量(QoS)保证技术显得越来越重要,为了保证网络服务质量,希望根据多个QoS约束参数来选择可行路由。一般说来,多受限路径优化问题是一个NP完全问题,因此在多项式时间复杂度里不能解决该问题,针对这个问题,在启发式算法的基础上,提出一种改进扩展Bellman-Ford最短路径算法(MEBF),将NP完全问题简化为在多项式时间复杂度里能解决的问题。模拟的结果表明,该算法有良好的运行效率和QoS路由成功率。     

基于多个QoS约束的路径选择算法

寻找同时满足多个独立的QoS 约束的路径是一个NP 完全问题。提出一种解决多约束路径问题的有效算法———多约束最小跳路径算法( MHMCA) , 该算法首先利用Bellman-Ford 最短路径算法进行标记, 并删除图中的无用链路, 在简化后的图中使用基于堆栈的深度优先搜索算法寻找所有满足约束的最小跳可行路径。最坏情况下, 算法的时间复杂度为O( n3) 。仿真结果表明, 该算法寻找具有最小跳可行路径的成功率高, 接近于最优算法。     

基于改进蚁群算法的多约束QoS路由方法

高速多媒体网络路由问题是一个多QoS约束的NP一完全问题,提出一种改进蚁群路由算法对该问题进行求解。该算法采取了带记忆的后继节点选择方式,利用蚂蚁已走过的路径启发后继节点的选取;引入了基于目标函数的信息素更新机制,依据目标函数评价蚂蚁路径搜索行为,并根据蚂蚁的表现采取不同的信息素更新策略,提高了算法的寻优能力和收敛速度。仿真实验表明,该算法能快速得到较大程度满足业务QoS要求的路径。     

基于再励学习蚁群算法的多约束QoS路由方法

本文研究了多约束QoS路由问题,给出基于模糊评判的路由模型,实现了多QoS约束的综合优化;同时提出一种再励学习蚁群路由算法对该问题进行求解,算法通过对蚂蚁搜索路径进行评价产生再励信号,并根据再励信号采取了不同的信息素更新策略,提高了算法的寻优能力和收敛速度。仿真实验表明,该算法能快速得到较大程度满足业务QoS要求的路径。     

一种基于Agent的分布式QoS多播路由算法

针对QoS约束多播路由问题,提出了一种基于Agent的分布式QoS多播路由算法AQRA (Agent-based Distributed QoS Multicast Routing Algorithm).算法利用不同类型Agent之间的通信协作,寻求满足QoS约束要求的多播路由;在获得最优路径的同时可有效避免回路的产生,并且通过灵活的路由切换和锁定机制,保证了路由连接的成功建立.实验结果表明AQRA是一种正确、有效的QoS组播路由算法.     

大规模图上具有约束的多起点路径规划算法

路径规划查询是图数据上的一个基本问题,在众多的领域都有重要的应用价值。通常在实际问题中查询的路径是具有约束的,例如在外卖配送和共享出行问题中路径具有节点约束,其路径需要满足节点之间的先后关系约束。目前对于具有节点约束的路径查询问题,大多数的工作都在研究单起点的节点约束路径查询,但很难拓展到多起点节点约束问题中。因为具有节点约束的多起点路径查询问题是NP-hard的,所以该问题的大多数已有方法是使用贪心增量处理,但对于处理静态规则集拓展性不足。因此,提出了基于子路径的启发式算法和基于约束集拓展的精确算法,并在真实数据集上验证了算法的有效性。实验结果表明,启发式算法能够给出问题的精确解,而启发式算法能快速给出较好的近似解。     

基于分布式约束满足的多约束单路径路由问题求解

约束路由问题是IP网络的一个核心功能,由于求解多约束路由问题属于NP完全问题,所以大量的研究工作围绕此展开.基于分布式约束满足的思想,设计多约束单路径路由问题求解算法,分析表明该求解算法降低计算复杂度,提高算法的性能.在分布式条件下完成算法的实现,经实验表明,算法近似程度较好,求解速度快.     

率失真优化的无线多跳网络多路径选择算法

随着无线网络技术的发展,基于无线多跳网的视频通信在智能交通、灾难应急和军事指挥等多个领域得到越来越广泛的应用.但是,如何保证无线视频的传输质量,是亟待解决的一个关键问题.已有多路径视频传输研究忽略了信道变化和路径间干扰.针对该问题,提出一种基于率失真预测的多路径选择优化算法.该算法不仅分析了网络拥塞对传输质量的影响,而...     

DPA:一种动态环境下QoS单播路由算法

目前Internet网络环境下,网络参数的随时变化容易造成路由过期,从而使提供的QoS路由无效,为此提出了一种适合参数动态变化的单播QoS路由算法(DPA),该算法在路径代价随时间不断变化的情况下能够自主地选择最优路由节点,解决多约束QoS单播路由选择不精确的问题.实验表明,本路由算法自适应性和扩展性较好,同时在路由选择方面比传统的路由算法能够提供更好的QoS路由.     

基于模拟退火的服务质量路由算法

作为下一代互联网的核心问题之一,多约束的服务质量路由(QoSR)用来寻找一条同时满足多个约束条件的可行路径.然而,该问题具有NP完全的复杂度.将模拟退火引入多约束QoSR计算中,首先使用非线性能量函数将多个QoS度量转化成单一能量,然后基于模拟退火的方式求解最小能量路径.首先概述了模拟退火的方法,分析了在QoSR中应用模拟退火所面临的关键问题以及解决方案,然后给出了SA_MCP算法及其复杂性分析.实验结果表明,该算法具有很高的性能,同时对网络规模和约束个数都具有很好的扩展性,对QoS约束的分布状况也不敏感.此外,只要大部分QoS约束存在可行路径,算法的实际运行时间约为O(k(m+nlogn)),即传统Dijkstra算法的k倍(k为约束个数).     

基于约束分析的RapidIO路由选择算法

针对RapidIO网络多约束服务质量路由问题,提出一种基于约束分析和K最短路径的路由选择算法。通过定义约束严苛度的概念对各个QoS约束度量参数进行评价,选取约束严苛度最高的约束度量作为评价标准;在此基础上采用K最优路径算法快速选择满足多约束的可行路径。仿真结果表明,该算法可以解决多约束路由选择问题,在时间上具有多项式复杂度,对于约束度量参数个数有很好的扩展性。     

多约束服务质量路由中的路径压缩算法

多约束服务质量路由是一种能够支持灵活的服务质量控制的有效方案.然而在多约束的环境下,从一个源节点到一个目的节点可能存在多条路径,因而必须相应地增大路由表容量.由于当前路由表的规模已相当庞大,尤其是在高速核心网中,因此,为了在QoS路由表中存储更少的路径信息,需要首先进行路径压缩.文章以解决最优路径压缩问题(OPR)为目标,力图在尽量减小路由表存储规模的同时使路由成功率最大化.为了实现这个目标,文中提出了两个基于贡献区域的算法:增量贡献算法和改进的增量贡献算法.这两个算法从一个大的多约束路径集合中依次计算出具有最大贡献区域的积的路径,最后得到一个小的结果路径集合.大量模拟实验表明,这两个算法能够以较低的运算复杂度获得令人满意的路由成功率.     

FallBack+--一种新的多QoS约束路由算法

FallBack(FB)算法是满足多QoS路径选择的基本算法，是Dijkstra算法的一种改进，在FB算法中，路径选择是按照算法设计者根据经验排序的多QoS为确定的，因此是经验的，所做选择的难以保证是最佳路径。另外FB算法主要以满足多QoS路径选择为目的，并未考虑网络资源的有效利用。本文对FB算法进一步扩充，提出了路径选择的FallBack^ 算法，它不仅满足多QoS约束，有效地利用网络通信资源，并有高的功效。     

基于软件定义网络的多约束QoS双路径路由优化方法

针对当前SDN架构存在路由算法复杂度高、QoS流满意度低和单链路故障等问题,提出了一种基于软件定义网络的多约束QoS双路径路由优化算法(SDN＿MCQDP)。利用控制器获得全局网络状态信息,生成基于目的节点的有向无环图。在多约束QoS路由选择阶段,通过拉格朗日松弛对偶算法将多约束问题转化为线性规划问题。使用反向链路删减得到满足多约束QoS的节点不相交的双路径冗余链路,使链路故障后的数据传输得到保障。从路由计算时间、链路利用率、QoS流满意度等方面对算法进行仿真实验。结果表明,与MODLARAC、QT、RMCDP＿RD、H＿MCOP算法比较,SDN＿MCQDP能够有效降低传输时延,减少路由计算时间,提高链路利用率,且在链路发生故障后仍能满足QoS需求。     

基于混合策略的QoS选播流路由优先算法

分析了QoS选播流交错服务问题的产生过程及其对网络资源的浪费,提出了一种基于混合策略的全局路由优化解决方法.在构建路由优化问题模型的基础上,得出了选播流路由端到端时延、服务器负载、网络流量、路径调整等多个优化目标和QoS约束的表达式.给出了GA、SA、TS三种算法有机结合形成的一种混合优化算法,并说明了运用该算法求解的关键步骤和实现过程.实验结果表明,本算法能够在满足QoS约束的前提下实现选播路由的多目标组合优化,与基于GA或者SA的求解算法相比具有更强的稳定性和更高的精确度.