一种多约束最优路径宽度优先松弛算法

在分析单播QoS路由问题的基础上,提出了宽度优先松弛算法BFRA,其核心思想是基于改进的宽度优先搜索策略,采用特殊的松弛算法分别前向(从源节点)和后向(从目标节点)搜索网络拓扑.前向搜索预先计算路径的综合度量、约束等参数,收集路径信息;后向搜索则采用Cost-measurement策略对路径进行选择和筛选,不断搜索到新的可行路径,并选取最优路径.讨论了在路径振荡时BFRA选取次优路径,为其他QoS流的接入预留了资源.理论分析表明BFRA保存的状态信息较少,时间复杂度为线性,仿真结果表明,BFRA发现最优路径的成功率较高.

Breadth First Relax Algorithm for Multi-Constrained Optimal Path

Based on analysis of unique cast QoS routing,the paper proposes BFRA(Breadth First Relax Algorithm).And it's main idea based on improved BFS is adopting special relax policy,and searching the network topology seperately from forwardness(source node) and backward(destination node).Forward search pre-computs integrated metric,constrains and other parameters of path,gathering path info;backward search chooses and filters pathes adopting Cost-measurement policy,and chooses the optimal path on finding new pathes.And the paper points that BFRA chooses hypo-optimal path on the condition of path surge,and retains the resources for other QoS request.The theory analysis indicates that BFRA needs less status info reserved and it's time complexity is linearity.The experiments indicate that BFRA's SR of finding the optimal path is higher.