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

第2 0 卷 第 5 期  2 0 1 3 年 1 0月   莆 田 学 院 学 报  J o u r n a l  o f  P u t   i a n  Un i v e r s i t y   中图 分 类 号 : T P 3 0 1 . 6   VO 1 . 2 0  No . 5   Oc t .2 0 1 3   文章编号 : 1 6 7 2 . 4 1 4 3 ( 2 0 1 3 ) 0 5 . 0 0 5 9 . 0 4   文献标识码 : A   Q o S   一 个 动 态 规 划 算 法   吴景岚  , 朱文兴 z   ( 1 . 闽江学院 计算机科 学 系,福 建 福 州 3 5 0 1 0 8 ; 2 . 福州大学 数学与计算机 学院,福建 福 州 3 5 0 1 0 8 )   摘  要 : 研究具有可加性和可乘性参数约束的Q o S 路由选择问题, 以丢失率约束为例, 给出了把问题的可乘性  参数约束 变换为可加性约束的方法 , 据此给 出具有 丢失率约束最小时延 问题的一个线性 O - 1 规划模型 。利 用该  变换 , 对一个简单 的网络拓扑 , 给 出了该 问题的一个动态规划算法 , 算法具有拟 多项式时间复杂性。   关 键词 : Q o S 路 由选择 ; 动态规 划算法; 时延 ; 线性 0 - 1 规划; 丢 失率  A Dyn a mi c  Pr o g r a mmi ng  A p pr o a c h f o r   Mu l t i - c o n s t r a i n e d  Qo S  Ro u t i n g  P r o b l e m  W U J i n g — l a n   . ZHU W e n - x i n g  ̄   ( 1 . De p a r t me n t   o f   C o mp u t e r   S c i e n c e , Mi n j i a n g   U n i v e r s i t y , F u z h o u   F u j i a n   3 5 0   1   0 8 , C h i n a ;   2 . C o l l e g e   o f Ma t h e ma t i c s   a n d   C o mp u t e r   S c i e n c e , F u z h o u   U n i v e r s i y, t F u z h o u   F u j i a n   3 5 0 1 0 8 , C h i n a )   Ab s t r a c t : T h e   Qo S   r o u t i n g   p r o b l e m  wi t h   mu l t i p l e   a d d i b l e   a n d   mu l t i p l i c a b l e   c o n s t r a i n t s   w a s   c o n s i d e r e d   i n   hi t s  p a p e r .   A  me t h o d   wa s   p r o p o s e d   t o  t r a n s f o r m mu l t i p l i c a b l e  c o n s t r a i n t s  s u c h  a s  l o s s  r a t e  c o n s t r a i n t   e q u i v a l e n t l y   i n t o   a d d i b l e   c o n s r t a i n t s .  B y   u s i n g   t h i s   me t h o d , t h e  mi n i mi z a t i o n   o f   t i me   d e l a y   s u b j e c t   wa s   mo d e l e d   t o  a  l o s s  r a t e  c o n s t r a i n t  o v e r  a  s i mp l e  n e t wo r k  a s  a  l i n e a r  0 - 1  p r o g r a mmi n g  p r o b l e m,   a n d  a   p s e u d o — p o l y n o mi a l   t i me   d na y mi c   p r o g r a mm i n g   a l g o r i t h m  wa s   p r e s e n t e d .   Ke y   wo r d s : Q o S   r o u t i n g ; d y n a mi c   p r o g r a mmi n g ; d e l a y ;l i n e a r   0 - 1   p r o ra g mmi n g ; l o s s   r a t e   0 引 言  目前 的网络 为 了支 持 各种 Qo S需 求 ,在 进行  路 由选 择 时 所 考 虑 的路 由参 数 主 要 有 网 络 路 由  的跳数 和 时延 , 网络带 宽 , 时延 抖动 及 丢失 率 等 参  数『 l _ 3 ] 。这 些参 数 可 以分 为 以 下三 类 :1 ) 可加 性 参  造 近似算法[ 2 - 5 】 , 而考虑多参数条件约束的完全性  算法 则少 见嘲 。 文[ 2 , 6 ] 指 出满 足带 宽要求 的链 路可  以预先找 出 , 故只须 考虑 可加 性 和可乘性 参数 。 文  [ 6 ] 指 出 网络 中的服 务通 常要 求在 丢 失率 不超 过一  个 限定值 的前 提下 求最 小 时延 ,并

相关文档

一种基于多条件约束的QoS路由选择优化算法
多条件约束的QoS路由选择简化算法研究
基于动态最短路径策略的多QoS路由算法
电脑版