关键词: 计算机系统结构, 服务质量（QoS）, 多约束, QoS路由, K最短路径, NP完全

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.

Key words: computer system structure, quality of service (QoS), multiple constraints, QoS routing, Kshortest path, NP complete