面向VoIP的QoS路由算法研究综述【完整版】.docx

《面向VoIP的QoS路由算法研究综述【完整版】.docx》由会员分享，可在线阅读，更多相关《面向VoIP的QoS路由算法研究综述【完整版】.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、面向VoIP的QoS路由算法研究综述【完整版】(文档可以直接使用，也可根据实际需要修订后使用,可编辑放心下载）面向VoIP的QoS路由算法研究综述段虎1，蔡铁21.深圳大学信息工程学院，广东 深圳 518060；2.深圳信息职业技术学院信息技术研究所，广东 深圳 518029摘 要：效劳质量路由(quality-of-service routing,简称QoSR)是提高网络实时(音频、视频)传输效劳质量的核心技术。本文在介绍网络QoS根本数学模型的根底上,详细分析了面向VoIP的QoS路由算法参数和多约束多播路由算法融合这两个重要问 题,并分别对这两个问题的典型算法进行分析和比拟，最后得出了该

2、领域中需要进一步研究的关键问题。关键词: VoIP；效劳质量路由；NP完全问题；多播路由算法；中文分类号：TP393文献标识码：A文章编号：1672-6332202102-0023-06SMCMRA算法15 等。第二类是两种智能型算法互相融合的算法(简称智能型算法).，如GAACO_QoS算 法16 、FangJunfeng提出的算法17 等。第三类是非智 能型算法和智能型算法互相融合的算法(简称混合 型算法)，如NOPARA算法18 、CEACA算法9 等。当前Internet只提供尽力发送(best-effort)效劳,根本无法满足大规模的实时数据视频、音频等传 输应用的要求。QoSR对实

3、现网络效劳质量起到了 非常关键的作用，同时QoSR也是平衡网络负载和 充分利用网络资源的重要保证。面向VoIP的QoSR 对于实时传输的效劳质量极其重要,其关键问题包 括参数选择和路由两个主要内容。AlaF.Khalifeh和 AliH.El-Mousa对面向VoIP路由算法的参数进行了分 类1 ：1)单纯用跳数hop-count做为路由参数， 如Dijkstra算法2 、Bellman算法3 。2延迟为主要 参数的花费函数值做为路由参数，如Lorenz算法4、Orda等设计的算法5 、LARAC算法6 。3用标准 跳数hop-normalized做为路由参数，如ARGA算 法7 ，Z.Wan

4、g和J.Crowcroft设计的算法8 ，CEACA算法9 。从路由方式来说，多播技术是网络支持多媒 体业务的关键技术之一。因此，本文主要针对的 是多约束多播QoS路由问题。过去经典的多约束多 播路由方法多为启发式算法,如蚁群算法10 、遗传 算法11 、H_MCOP12 、极限粒度和极限路径启发算 法(LPH)13 、模拟退火算法14 等。根据是否参加智 能计算的思想,目前主流的多约束多播路由算法可 以分为三类：一类是两种非智能型算法互相融合 的算法(简称非智能型算法),如CMCMRA算法15 、1 QoS路由问题效劳质量路由是未来互联网络的一个核心功能，其主要目标包括两个：1为每个接受的Q

5、oS业 务流提供效劳质量保证；2到达网络全局资源的 最正确利用。目前的研究成果说明，在一定区域内部 通过合理地配置基于链路状态的QoSR协议,为支持 QoS所引入的开销是完全可能接受的,然而QoSR领域 仍然面临着挑战19 。QoSR问题难于解决的原因：1目标节点对数 据流的QoS需求一般是多方面的。例如，语音通信 对效劳质量有严格的要求。因此，必须提供可扩展 的解决方案，以满足不断扩展的网络规模和效劳细 分需求。2寻找一条满足两个独立加性QoS约束的 路径的路由问题就是NPC(NP-Complete)问题，具有 NPC(NP-Complete)的计算复杂度20 。3为了提高 可扩展性所使用的

6、层次化模型，产生了多种参数如 何聚集的问题21 。多约束QoS问题的目标即是找到一条路径 收稿日期 2021-04-02基金工程 深圳市科技方案资助工程SZKJ0601作者简介 段虎1980-，男汉，湖南长沙人，硕士研究生，E-mail:duanhu1980163 p(s, d ) ，使它满足以下条件:2时延抖动DelayJitter1时延约束: delay(e) D ， D 表示时延约束；时延的变化，即时延抖动主要由网络引起，如2本钱约束: cos t (e) C ， C 表示本钱约束；果端到端的传输路径中经过的中间节点(路由器、3丢包率约束: loss(e) L ， L 表示丢包率约交换机

7、等)越多，带来的时延抖动越大。 束；3丢包率Packet Loss4带宽约束: bandwidth( p) B ， B 表示带宽约承载语音帧的包在到达接收端的过程中被丢 束。弃。丢包率对语言效劳质量的影响很大。对于多约束路由问题，由于各个目标之间缺少面向VoIP的QoS路由算法的研究过程中应该重点 统一的度量尺度，往往不能使每个指标的要求到达考虑到这三个参数，来提高整个路由算法的效率。最优。所以，通常是尽可能兼顾多个目标，求其满2.2 面向VoIP的QoS路由算法参数意解。将每条路径上的多约束函数整合成一个搜索在具体的路由算法开展过程中，路由算法中出m函数 y( p) = wi f i ( p

8、) ，以此作为目标函数来进行路现的参数或者参数组合主要有三类：i =1径选择，求得满足约束条件的最短路径。由此可以1单纯用跳数hop-count做为路由参数。构造出多约束QoS问题的数学模型：算法会选择跳数最少的路径做为最正确路径，如果有 几条链路跳数相同，那么选择要求最小带宽的那条链 路做为最正确链路。最初提出的QoSR算法，如Dijkstra1算法2 和Bellman-Ford算法3 都是这种类型。f i ( p) = f i (e)ep2延迟为主要参数的花费函数值做为路由参s.t. f i (e) i , i = 1,2,.m f ( p) , i = 1,2,.m 数。选择函数值最小的

9、链路做为最正确路由。运用这 ii种参数，在负载较低的情况下可以得到比拟好的效2果，但是当负载比拟高时，选择路由的效果将急剧1 e X 是满足多约束条件的所有链路之集；下降。2 wi 表示该业务对时延、本钱、延时抖动等延迟受限的最小花费问题(DCLC)是指，对于 约束的加权系数；任意 0 ，存在一个多项式时间的算法能够找到3分别表示一个业务在某一链一条路径,在满足延迟受限的同时,其花费不超过最路 e 的时延函数、本钱函数、延时抖动函数；小花费的 1 + 倍。由于这些算法的计算复杂度与4为单个链路上的约束临界 有关，因此被称为伪多项式算法。例如，Lorenz值；算法4 、Orda等人设计的通过量化

10、花费函数的预计5 = 1 , 2 ,. m 为路径上的约束临界值。算算法5 。AlparJuttner提出基于合成代价的拉格朗62 面向VoIP的QoS参数问题研究日松弛算法 (Lagrange Relaxation based AggregateCostLARAC )。LARAC算法基于启发式最小化代价2.1 面向VoIP的效劳质量QoS参数函数：在VoIP和视频流等实时性比拟高的业务方面，c = cos t + * delay3路由算法中对参数的选择是非常重要的。经过研究这里 是代表延迟和代价相关的权值。发现，VoIP应用的效劳质量主要受到三个性能参数3用标准跳数hop-normalize

11、d做为路由参的影响：端到端时延End-to-EndDelay、时延数。标准跳数参数是延迟和非延迟参数组成的新的抖动DelayJitter、丢包率Packet Loss。参数的值或者函数。这个参数是标准化跳数方面1端到端时延End-to-EndDelay的链接花费。标准跳数参数可以更准确的反映流端到端时延是影响交互式语音通信质量的最重量负载和整个网络的拥塞情况。用标准跳数hop-要因素之一。是指承载语音信息的包从发射系统到normalized做为路由参数，可以分为两类：接收系统所经历的时延。端到端的时延包括编解码a将两个或者两个以上的加性参数按照算术时延，打包与解包时延，以及网络传送时延。规那么

12、，组合成一个值。24深圳信息职业技术学院学报第6卷基于遗传算法的自适应路由算法AdaptiveCMCMRA算法和SMCMRA算法15 都属于此类算法。 Routing method basedon Genetic Algorithm ARGA提下面针对CMCMRA和SMCMRA算法重点进行介绍。 出了两个参数约束的路由问题7 ，应用的参数是延HuangLin和ZhangYu-Lin提出了CMCMRA和 迟DT和传输成功率(TSR)。基于遗传算法的自SMCMRA算法15 。这两种算法是将CBT概念23 和 适应路由算法ARGA提出一个新的参数 T,T的SPH概念24-25 分别与H_MCOP算法

13、26 结合起来。 值是这样定义的：CBT算法是一种动态的算法，可以动态将结点参加 链路，或从链路中删除一个结点。改良的SPH算法4可以支持分布式性能。 N是指路径的连接数。CMCMRA算法步骤： 显然，当T值很小的时候，延迟DT的值也1首先在网络中选择一个结点做为核心结 会很小，传输的成功率会很大。使用T值，可以使点。 两个参数的路由问题转化为一个参数的路由问题，2分别应用H_MCOP算法找到从核心结点到 并使两个参数都得到优化。模拟仿真结果显示，两源结点和所有目标结点的路径。 个参数的QoS路由算法优于一个参数的QoS路由算3显然路径结构是由源结点和所有目标结点 法。组成的多播树。计算多播树

14、的代价，每一个核心结Z.Wang和J.Crowcroft使用Dijkstra最短路径树算 点建立一棵多播树，最后可以得到 n ( n 是网络的法实现了带宽延迟受限的源路由求解8 。提出将参规模)棵多播树。数延迟、带宽、和丢包率混合起来的的参数T,做为4寻找到代价最小并且满足多约束的多播 选择路径的值，T的值是这样定义的：树。T =B( p)SMCMRA算法步骤：(D( p) * L( p)51应用H_MCOP算法找到网络中任意两个结P是指整个路径。点之间的路径。b)将两个或者以上的加性参数按照一定规那么构2分别找到从源结点到所有目标结点的路 成一个搜索函数。径。寻找所有路径当中代价最小的路径。

15、把路径HuaWang等提出基于交叉熵算法的分布式蚁(包括结点和边)储存在树 T1 中，把路径中的结点存群算法A Distributed Ant Colony Algorithm Basedon储在结点集 V1 ,其他目标结点(与树 T1 没有关系的结Cross-Entropy CEACA)来寻找满足多约束路由的最点)那么存储到结点集 U 。佳路径9 。将交叉熵的代价函数改为前面提到的多3同样用H_MCOP算法分别找到从结点集 U约束路由算法的搜索函数：m 中的结点到树 Ti 的路径，并且计算 Ti 的代价。因为L( k ) = y( k ) = wi f i ( k ) 6i =1U 是结点集

16、，可以找到一些局部的 Ti 树。找出这 k 是指可行路径中的某一条。些局部树中代价最小并且满足多约束的局部树 T ，在这里运用了延迟(delay)、本钱cost、丢i同时更新U = U u 。包率loss、带宽bindwidth四个参数来构成4重复第二步，直到所有的目标结点都包括搜索函数，寻找最优的路径：在多播树中。最后得出的是最正确的满足多约束的多L( k ) = wd delay( k ) + wc cos t ( k ) +播树。3.2 智能型算法wl loss( k ) + wb bandwidth( k ) 7该类算法是新的研究热点，多种群退火遗传算法30173 面向VoIP的多约束

17、多播路由算法(MPAGA) 、FangJunfeng提出的算法 和GAACO_QoS算法16 相继被提出。下面对GAACO_QoS算法重点3.1 非智能型算法进行介绍。该类算法应用广泛，当前提出的E-LARAC算法GAACO_QoS的根本思想是将遗传算法和蚁群28 、FPTAS-SMCP算法29 、FPTAS-FMCP算法29、算法融合,利用遗传算法优化解生成信息素初值,利25段虎，蔡铁：面向VoIP的QoS路由算法研究综述第2期用蚁群算法获取最优解16 。算法主要可以分为四个 C k C局部：P =i i id Di Ti i = Di Ti 1011预处理局部分为两步：a)为了简化问题,将

18、Ci 是自适应修正因数，其值在 0,1 之间。 ：节点上的特性叠加到链路上,只考虑链路而不考虑选取0.2到0.5之间的值。节点的特性；b)分析链路的多个约束,先过滤掉图NOPARA算法主要有两个主要步骤：G = V , E 中不满足带宽约束的链路(假设经过预处1) 用Dijkstra算法找出原结点与目标结点之间 理后的网络拓扑图是连通的)。累积代价最优的N条路径。2充分利用遗传算法的全局搜索能力以及快 2) 区分N条路径的流量。区分的标准是端到端延 速性、随机性等特点,生成假设干组优化解,进而转换 迟的大小，它是通过使增强学习信号最优化得到的。 成蚁群算法的信息素初值,为蚁群算法局部求取最 3

19、.4 算法的分析和比拟优路由做好准备。利用蚁群算法的正反应机制和高表1 多播效劳质量路由算法的比拟效收敛的特点求取满足约束的最优路由。Tab.1 Comparison of multicast QoSR algorithms3判断遗传算法和蚁群算法融合的适当时AlgorithmProblemtosolveRoutingstrategy ComputationBasedalgo- Heuristicclass complexityrithm机。结合QoS路由的特殊性,设计了适用于路由问题CMCMRA15 TwoDistributedO( n lg(n) + m) * mn ) H_MCOP He

20、uristic的融合方法。具体操作是，定义遗传算法控制函multi-constrained routingCBT数：SMCMRA15 TwoDistributedO( n lg(n) + m) * n2 ) H_MCOP Heuristic multi-constrained routingSPHGAACO_QoS16 MultipleDistributed* AntColony Heuristic8path-constrained routingGA18 MultipleDistributedDijkstras Non其中：，为遗传算法第 l 次迭代NOPARApath-constraine

21、d routing* AntColony -Heuristic后得到的群体费用的平均值,1 l N G ； N G 为遗传CEACA9 MultipleDistributedAntColony Heuristic path-constrained routing* CE算法的迭代次数； p 为常数。通过 l +1 值的变化来CGn 为节点数, m 为边数,“*表示计算复杂程度 动态地控制遗传算法和蚁群算法的融合时机。3.3 混合型算法不确定。非智能型算法CMCMRA和SMCMRA的时间复 该类算法综合了前面两类算法优点，当前 2的FanYiming等提出的算法 31 、CEACA算法9 、杂度

22、分别为 O( n lg(n) + m) * mn ) 和 O( n lg(n) + m) * n ) 。QoSMR-QGA算法32 、NOPARA算法18 是此类算法非智能型算法的优点是算法本身比拟简单、实用、时间复杂度确定，当前网络中实际运用的算法都是 典型代表。下面对NOPARA算法重点进行介绍。NOPARA(N-best Optimal Paths Ant Routing)算法18这种类型的算法。智能型算法那么具有健壮性、并行 性、灵活性，空间复杂度比拟小等优点，但是随着通过改编和整合算法中概率函数的自适应修正因网络的规模不同，算法的收敛速度是不确定的，其 数，扩展了NOQRA算法。它同

23、时用到了AntNet和论文27 推荐的探测和增强模型，这个模型是基于群时间复杂度也很难确定。这类算法在大规模求解过程中，在时间上的花费是很大的。混合型算法结合 智能的理念。这个模型主要是通过整合随机的根据了前面两种融合算法的优点，可以把算法的时间复 方案的探索过程(前向蚁群)和回退过程(后向蚁群)结杂度控制在一定的范围之内，同时还具有健壮性和 合而成。NOQRA算法概率函数的数学公式是： 1 1 k 1 1 并行性等特点。因此，如何将非智能算法思想和智Pi = D * T D * T 能算法思想更好的融合，是当前算法研究的一个重 i i i =1 i i 9点和热点问题。Di 是包从源节点到目

24、的结点的时间。 Ti ：下一跳路由器的队列延迟。 和 ：两个正整数4 总结 = 2 、 = 1 在NOPARA算法中，探索过程(前向蚁群)阶本文对面向VoIP的QoS路由算法参数和多约束段，前面的公式的根底上进行改良参加了自适应修多播路由算法融合这两个问题进行了深入的探讨。正因数，提出了下面的公式：VoIP应用的效劳质量主要受到三个性能参数的影26深圳信息职业技术学院学报第6卷27段虎，蔡铁：面向VoIP的QoS路由算法研究综述第2期响：端到端时延、时延抖动、丢包率。在同等条件下用标准跳数做为路由参数的参数类型比其他两种 参数类型可以得到更好的效劳质量。算法融合思想 是当前算法研究的一个重要方

25、向。因此，对于面向VoIP应用的效劳采用标准跳数做为路由参数，整合端到端时延、时延抖动、丢包率这三个参数，运用 混合型算法，可以使算法得到更高的效率和更优的 效劳质量。参考文献(References)1 Ala F. Khalifeh, Ali H. El-Mousa. QoS Routing of VoIP using a Modified Widest-Shortest Routing AlgorithmC ,2007IEEE.116-123.2 Dijkstra.A note on two problems in connexion with graphsJ. Numerical Mat

26、hematics. 1959,1:269-271. 3 Bellman.Dynamic ProgrammingJ . Princeton, Princeton University Press, 1957.4 Lorenz, Orda, Raz, et al. Efficient QoS partition and routing of unicast and multicastC .Proceedings of the 8th InternationalWorkshop on Quality of Service (IWQoS 2000), IEEE Communications Socie

27、ty, 2000. 75-83.5 Orda. QoS routing: the precomputation perspectiveC . Proceedings of the IEEE INFOCOM 2000. IEEE Communication Society,2000. 128-136.6 A. Juttner, B. Szviatovszki, I. Mecs and Z. Rajko.Lagrange Relaxation Based Method for the QoS Routing ProblemC . ProceedingsIEEE INFOCOM, April 200

28、1.7 Leonard Barolli, Akio Koyama, Kazunori Matsumoto,Takuo Suganuma, Norio Shiratori .A Genetic Algorithm Based Routing MethodUsing Two QoS ParametersC . Proceedings of the 13th International Workshop on Database and Expert Systems Applications(DEXA02), 2002 IEEE.8 Z. Wang, J. Crowcroft.Quality of s

29、ervice routing for supporting multimedia applicationsJ . IEEE Journal on selected areas inCommunications, Sep.1996, Vol 14: 1228-1234.9 Hua Wang, Gang Wang, Jun Ma and Zhao Shi. A Distributed Ant Colony Algorithm Based on Cross-Entropy for Multi-ConstraintsQoS RoutingC . ICACT2007,pp.1809-1813.10 Hu

30、a Wang, Zhao Shi, Jun Ma, Gang Wang.The Tree-Based Ant Colony Algorithm for Multi-Constraints Multicast RoutingC.ICACT 2007, 1544-1547.11 Fan Yiming, Yu Jianjun, Fang Zhimin. An Improved Genetic Algorithm for QOS Multicast RoutingC . Proceedings ofIWSDA07,2007. 133-137.12 T Korkmaz,M Krunz.Multi-con

31、strained optimal path seleetiion pathC .Proceedings of the INFOCOM 2001 conference,IEEE,2001,volume(2):834-843.13 Yuan Liu. Heuristic algorithms for multiconstmined quality-of-service RoutingJ . IEEE/ACM transactions on Networking.2002. l0(2):244-256.14 Xingwei Wang, Hui Cheng, Jiannong Cao. A Simul

32、ated-annealing-based QoS Multicasting AlgorithmC . Proceedings ofICCT2003,469-473.15 Huang Lin, Zhang Yu-Lin, Ren Yong-Hong.Two multi-constrained multicast QoS routing algorithmsC . Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distri

33、buted Computing, 2007IEEE,pp495-500.16 Liu ping,Gao Fei,Yang Yun.Qos routing algorithm based on the combination of genetic algorithm and ant colony algorithmJ.Application Research of Computer,2007,24(9):224-227.17 Fang Junfeng,Feng Guojian.A multicast Routing Algorithm Based on a New Optimization Al

34、gorithmJ puter Engineering andApplication ,2005.122-13018 Farid Baguenine, Abdelhamid Mellouk.N-Best Optimal Path Ant Routing Algorithm for State-Dependent N Best Quality of serviceRoutes in IP NetworksC .32nd IEEE Conference on Local Computer Networks, 2007 IEEE.747-754.19 Ariel Orda.QoS Routing: C

35、hallenges and Solution ApproachesC . Proceedings of the 2nd Intl Conf. on Quality of Service inHeterogeneous Wired/Wireless Networks (QShine05) ,2005 IEEE.20 Garey,Johnson puters and intractability: a guide to the theory of NP-completenessJ . 1979.21 Hao, Zegura. On scalable QoS routing: performance

36、 evaluation of topology aggregationC . Proceedings of the IEEE INFOCOM2000,IEEE Communication Society, 2000.147-156.22 Guoliang Xue, Senior Member, IEEE, and S. Kami Makki, Member, IEEE. Multiconstrained QoS Routing:A Norm ApproachJ.Published by the IEEE Computer Society, IEEE Transections on Comput

37、ers, June 2007. 859-863. 23 A.Ballardie. Core based tree(CBT) multicast routing architectureC .Internet RFC2201,Sept 1996.24 Pi-Rong Sheu,Shan-Tai Chen. A fast and efficient heuristicalgorithm for the delay and delay variation bounded multicast tree28深圳信息职业技术学院学报第6卷problemJ . Computer Communications

38、,2002,(25):825-833.25 T.L.Huang,D.T.Lee. An iterative distributed algorithm formulti-constraint multicast routingJ . Computer Communications,2006,(29):3647-3661.26 Turgay Korkmaz,Marwan Krunz. Multi-Constrained OptimalPath SelectionC .IEEE INFOCOM, 2001.834-843.27 M. Dorigo, t A Mobile Agents Approa

39、ch to Adaptive RoutingC . Technical Report, IRIDIA- Free BrusselsUniversity,Belgium, 1997.28 Himanshu Agrawal, Melanie Grah and Mark Gregory. Optimization of QoS RoutingC . 6th IEEE/ACIS International Conference onComputer and Information Science (ICIS 2007).29 Guoliang Xue, Arunabha Sen, Weiyi Zhan

40、g. Finding a Path Subject to ManyAdditive QoS ConstraintsJ . IEEE/ACM Transactions on Networking,2007, 15( 1):201-211.30 Yang De-hong,Qu Zhong,He Jiang-ping.Method for multicast routing based on genetic algorithmJ puter Engineering andDesign,2005,26(10):2730-2733.31 Fan Yiming, Yu Jianjun, Fang Zhim

41、in.An Improved Genetic Algorithm for QOS Multicast RoutingC . Proceedings of IWSDA07,2007 IEEE.133-137.32 Chen Niansheng, Li Layuan, Ke Zongwu. QoS Multicast Routing Algorithm Based on QGAC . 2007 IFIP International Conference on Network and Parallel Computing Workshops,IEEE 2007.683-688.VoIP-orient

42、ed OoS routing algorithmsDUAN Hu1, CAI Tie2(1.College of Information Engineering, Shenzhen University, Shenzhen 518029, P.R.China;2. Research of Information Technology, Shenzhen Institute of Information Technology Shenzhen 518029, P.R.China)Abstract: Quality-of-service routing (QoSR) is a key issue

43、for enhance the quality-of-service of the networkreal-time(audio,video)transmit.Based on the network QoS basic mathematic model is introduced in this paper. The VoIP-Oriented QoSR metrics and combination of multi-constraints multicast routing algorithm are the important subjets,which are analyzed in detail.And the typical algorithms of these two subjets are classified and compared.At last,key issues are proposed to be further studied in the QoSR field.Keywords:VoIP；QoS routing；NP-complete problem；multicast routing algorithms责任编辑：高潮