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

Link State-Based Precomputation for Multi-Constrained Routing

作　　者：崔勇[1] 吴建平[1] 徐恪[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《电子学报》2003年第8期1173-1177,共5页Acta Electronica Sinica

基　　金：国家"八六三"项目 (No 2 0 0 2AA1 0 30 67);国家自然科学基金 (No 6972 50 0 3No 90 1 0 4 0 0 2No .60 2 0 30 2 5)

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

关 键 词：线性能量函数 QOS路由 预计算算法 多约束 可扩展性 

分 类 号：TP393.01[自动化与计算机技术—计算机应用技术]