基于K最优路径的QoS路由预计算新算法  

Novel Precomputation Algorithms for QoS Routing Based on the K-optimal Paths

作　　者：齐小刚[1] 刘三阳[1] 

机构地区：[1]西安电子科技大学应用数学系,陕西西安710071

出　　处：《电子学报》2005年第10期1751-1756,共6页Acta Electronica Sinica

基　　金：国家自然科学基金(No.69972036);教育部跨世纪优秀人才培养基金(2002);陕西省自然科学基金(No.2004A02)

摘　　要：针对下一代高速网络中的多约束服务质量路由问题,首先提出了一种精确链路状态信息条件下的路由预计算算法MKPPA.在此基础上根据网络状态信息的动态性,通过引入“警戒点”对MKPPA进行了改进,提出了一种基于警戒点的修正预计算算法M-MKPPA,该算法能够适应网络链路信息的不精确性.最后通过理论分析表明MKPPA不仅能够解决加性度量参数受约束的QoS路由问题,而且能够解决加性与非加性度量参数混合受约束QoS路由问题,修正预计算算法M-MKPPA能够适应网络链路状态信息的动态特性.计算机仿真结果显示出MKPPA在求解QoS路由问题时,当计算次数不超过已有算法的计算次数时,不论是精确链路状态信息还是非精确链路状态信息条件下,均具有更高的路由计算成功率.To solve the problem of Quality-of-Service （QoS） muting in next generation high speed network,firstly a novel precomputation algorithm MKPPA for QoSR with accurate link-state information based on the K-optimal paths is proposed. Secondly a modified MKPPA,M_ MKPPA, is presented to adapt the inaccurate link-state information of the network by introducing an “alert point”. Finally the theoretical analysis indicates that the MKPPA is not only fit to the QoSR in which all constraint parameters are additive but also the QoSR in which some constraint parameters are additive and the others are non-additive, the M_ MKPPA can adapt the dynamical character of link-state information of the network. 3he extensive simulation results show that the proposed algorithms have the higher muting computation success ratio with either accurate link-state information or inaccurate link-state information of the network.

关 键 词：服务质量(QoS) 多约束 QOS路由 K最优路径 路由预计算 

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