基于链路状态的多约束路由预计算算法

作为下一代高速网络的核心问题之一,多约束的服务质量路由(QoSR)至今尚无有效算法,为此基于线性能量函数设计了预计算算法MEFPA.该算法将每个QoS度量的重要性均匀分成若干个等级,从而在多维QoS度量空间中构造出多个均匀分布的线性能量函数;算法通过能量函数将QoS链路状态转化成单一能量值,再使用Dijkstra算法计算最小能量树,最终产生QoS路由表.文章分析了多约束下的线性能量函数对算法性能的影响,给出了判定多维空间中QoS约束的可行区域和不可行区域的方法,最后基于这些理论为多约束QoSR问题给出了预计算算法.广泛深入的实验结果表明,高可扩展性、高性能、易实现的预计算算法MEFPA是一种值得在下一代网络中考虑的路由算法.

Link State-Based Precomputation for Multi-Constrained Routing

As one of the most challenging problems in the upcoming next generation high speed networks,quality of service routing (QoSR) with multiple constraints has the NP complete complexity.A precomputation algorithm,MEFPA,was proposed.This algorithm divides the significance of each QoS weight into multiple degrees,and constructs a number of linear energy functions (LEFs) distributed uniformly in the multi dimensional QoS metric space.Using LEFs,it then converts different QoS weights to a single energy.At last,it uses Dijkstra's algorithm to create the least energy trees,based on which the QoS routing table is created.The performance of LEFs with constraints is analyzed,and the method is given to determine the feasible and unfeasible areas in the multi dimensional QoS metric space for a QoS constraint.Then MEFPA for the multi constrained QoS routing problem was introduce.Extensive simulations show that our easily implemented MEFPA is a promising precomputation algorithm to provide QoSR with high scalability and high performance in high speed networks.