多条件QoS路由选择的一个动态规划算法  

A Dynamic Programming Approach for Multi-constrained QoS Routing Problem

作　　者：吴景岚[1] 朱文兴[2] 

机构地区：[1]闽江学院计算机科学系,福建福州350108 [2]福州大学数学与计算机学院,福建福州350108

出　　处：《莆田学院学报》2013年第5期59-62,共4页Journal of putian University

基　　金：国家自然科学基金资助项目(61070020)

摘　　要：研究具有可加性和可乘性参数约束的QoS路由选择问题,以丢失率约束为例,给出了把问题的可乘性参数约束变换为可加性约束的方法,据此给出具有丢失率约束最小时延问题的一个线性0-1规划模型。利用该变换,对一个简单的网络拓扑,给出了该问题的一个动态规划算法,算法具有拟多项式时间复杂性。The QoS routing problem with multiple addible and multiplicable constraints was considered in this paper. A method was proposed to transform multiplicable constraints such as loss rate constraint equivalently into addible constraints. By using this method, the minimization of time delay subject was modeled to a loss rate constraint over a simple network as a linear 0-1 programming problem, and a pseudo-polynomial time dynamic programming algorithm was presented.

关 键 词：QOS路由选择 动态规划算法 时延 线性0-1规划 丢失率 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]