首页 | 本学科首页   官方微博 | 高级检索  
     

一种基于K最短路径的QoS路由选择算法
引用本文:齐小刚,刘三阳.一种基于K最短路径的QoS路由选择算法[J].吉林大学学报(工学版),2005,35(5):526-0530.
作者姓名:齐小刚  刘三阳
作者单位:西安电子科技大学,应用数学系,西安,710071
基金项目:国家自然科学基金资助项目(69972036);教育部跨世纪优秀人才培养基金(2002);陕西省自然科学基金资助项目(2004A02).
摘    要:针对多约束服务质量路由问题,提出了一种基于K最短路径路由选择算法QRBKP。该算法首先计算针对各约束度量参数的K最短路径,然后在所有的最短路径中选择满足多约束的QoS路由,其中最短路径数k根据各QoS约束自适应变化。基于此,本文提出了节点对之间的路由空间再分配技术和节点对内部的路由空间再分配技术,确保总的路由表空间不会超过设计路由空间。理论分析表明,QRBKP不仅能够解决加性度量参数受约束的QoS路由问题,而且能够解决加性与非加性度量参数混合受约束QoS路由问题。仿真结果表明:在求解QoS路由问题时,在相同的计算次数下,QRBKP算法比同类算法具有更高的路由计算成功率。

关 键 词:计算机系统结构  服务质量(QoS)  多约束  QoS路由  K最短路径  NP完全
文章编号:1671-5497(2005)05-0526-05
收稿时间:2005-02-27
修稿时间:2005年2月27日

Selection Algorithm for QoS Routing Based on K-shortest Paths
QI Xiao-gang,LIU San-yang.Selection Algorithm for QoS Routing Based on K-shortest Paths[J].Journal of Jilin University:Eng and Technol Ed,2005,35(5):526-0530.
Authors:QI Xiao-gang  LIU San-yang
Affiliation:Department of Applied Mathematics, Xidian University, Xi'an 710071, China
Abstract:Facing the problem of multiple constraint Quality of Service Routing(QoSR), a novel selection algorithm based on K shortest paths, QRBKP, was proposed. This algorithm calculated the K shortest paths first according to each constraint parameter. Then the QoSR satisfying multiple constraints was selected among all shortest paths with the value of k changing adaptively to the QoS constraints. Both intra-node-pair reassignment method and inter-node-pair reassignment method were proposed to assure the routing table space not out of the range of designed routing table space. Theoretical analysis shows QRBKP can solve QoSR not only with additive constraint parameters, but also with non-additive constraint parameters. Simulation results show that the routing computational success ratio of QRBKP is higher than that of current algorithms in solving QoSR under the same computational time.
Keywords:computer system structure  quality of service (QoS)  multiple constraints  QoS routing  (K-shortest path  NP complete)
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《吉林大学学报(工学版)》浏览原始摘要信息
点击此处可从《吉林大学学报(工学版)》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号