一种基于优先级的带宽时延路由算法

2018-09-20 11:29李军旺
无线互联科技 2018年15期

李军旺

摘要:针对王勇智算法在负荷较重时,低等级业务丟包率较高的不足,文章改进了其剪枝条件,引入节点时延和优先级约束,提出一种基于优先级的带宽时延约束路由算法P-BDCBR。从仿真结果来看,改进的算法在重负荷时,在丢包率以及吞吐量等方面较原算法有一定的优越性。

关键词:节点时延;优先级;带宽时延约束

1 问题的提出

在高速多媒体网络中,时延是一个很重要的QoS度量参数,时延过大,会造成用户在视觉和听觉上的不适应,甚至无法播放。针对高速多媒体网络中的时延约束,国内外研究者很多,也提出了一些较好的算法,如Wang等[1]提出的基于带宽与时延约束的路由算法,Juttner等提出的基于时延约束、代价最小的路由算法,王勇智基于节点负荷率提出的Wang-Crowcroft改进算法。

至今提出的各种算法,它们针对的具体问题与所采用的策略是不相同的,已经证明当相加型或相乘型约束大于或等于两个时,其最优路径的求解是NP完全问题,在多项式时间内没有精确的解,故大多采用启发式算法[2]。对于时延约束类的路径求解问题,一般将带宽作为先决条件,剪去不满足要求的链路,然后用最短路径算法求解时延问题。这类算法最关键的问题是剪枝,通过剪去不滿足QoS要求的链路来简化寻找路径的拓扑结构,以降低算法的计算复杂度。

2 —种基于优先级的带宽时延改进算法

2.1 王勇智算法分析

王勇智针对Wang-Crowcroft算法的不足,提出了一种基于节点负荷率的带宽时延约束路由算法。该算法在Wang-Crowcroft算法的基础上加入节点负荷率的约束条件,以链路时延和节点负荷率为度量,剪去不合要求的链路,再用Dijkstra算法计算最短路径。该算法的优点是可以在一定程度上降低高带宽链路的拥塞度,其缺点是开销大以及未考虑对不同优先级的业务进行区别处理,在负荷较重时,传统尽力而为业务的丢包率可能较高。

2.2 算法的改进思路与描述

针对王勇智算法在负荷较重时,低等级业务丢包率较高的不足,本文改进了其剪枝条件,引入节点时延和优先级约束。当节点负荷较大,超过门阀值时,不是简单的剪枝,而是根据业务的优先级,将高优先级的业务映射到其他链路,而低优先级的业务仍按原链路传输。基于以上考虑,将MPLS的约束路由机制与业务优先级相结合,提出一种基于优先级的带宽时延约束路由算法P-BDCBR。

2.2.1 节点时延的定义

其中,Dn表示节点的时延;T表示节点在轻负荷时的转发处理时间;Ek(n)表示优先级为k的业务在节点缓存中的相对缓存占用率,其在数值上等于所占缓存与总缓存的比。

假设在MPLS网络中某个节点中同时有M个优先级的业务流,这些业务流在缓存区中按其优先级的高低排队,当一优先级为k的业务流到达时,该业务流只能排在优先级为k-1的业务流之前而排在优先级为k+l的业务流之后。因此,当有新的业务流到达时,只需计算比其优先级高的业务占用的缓存区就可以了。显然,即使是在网络状态相同的情况下,Ek(n)也会因为业务优先级的不同而有所不同,保证了不同优先级业务占用的资源。设有m个优先级的业务,则有:

Em(n)≥Em-1(n)……≥Ek(n)……≥E1(n)。

这样,既保证了高优先级业务能得到优先服务,又可以在一定程度上降低低优先级业务的丢包率。

2.2.2 分组丟弃策略

采用优先级与RED算法相结合的丢弃策略[3],在MPLS网络每个节点内部,用MD算法来决定分组的丢弃与否,而丢弃哪个分组由优先级来决定。

2.2.3 算法的改进思路与描述

采用源路由策略,当一个业务流到达MPLS网络时,采用改进的剪枝策略,剪去带宽与链路时延不符合要求的链路,然后计算节点的时延值。随着流过节点的流量的增加,节点的负荷会越来越重,节点的时延也会相应有所提高,当达到门阀值时,对于高优先级的业务,则将该节点剪去,将高优先级业务映射到其他节点,然后用Dijkstra算法计算最小代价路径;对于低优先级的业务,由于其肯定没有达到时延的门阀值,所以仍按原路径发送。这样可在均衡流量的同时,在一定程度上降低了低优先级业务的丢包率。

3 算法的仿真实验及比较分析

采用ns-allinone-2.30版本,在MNS_v2.0扩展包的基础上添加MPLS流量工程模块,修改部分底层C++源代码与ns-mpls-cr.tcl文件。实验在Windows+Cygwin环境下进行。本次实验只验证BE类流在高优先级的EF类流加入的时候在两种算法下的表现。主要从丢包率和请求的吞吐量(Throughput)两个方面进行对比分析,仿真结果如图1一2所示。

从图1一2可以看出:在0.5?5 s的时间段内,BE流的吞吐量比较平稳,丢包率也比较低,两种算法性能表现相似。这是因为此时网络的整体负荷较小,性能稳定。

5?8 s的时间段内,BE流吞吐量下降,丢包率有所升高。两种算法相比,P-BDCBR算法的变化幅度相对明显。这是因为随着EF类流的加入,网络中的流量不断增多,网络整体性能下降,但由于此时网络的整体负荷不是很大,性能还可以。对于王勇智算法由于没有考虑优先级,业务流在竞争时是“平等”的,而对于P-BDCBR算法,由于EF类流的优先级较高,争抢资源时有优势,故对BE类流有一定影响,吞吐量下降明显些,丢包率高些。

8?15 s的时间段内,BE流吞吐量进一步下降,丢包率进一步升高,到15 s左右达到极限值。两种算法相比,P-BDCBR算法下BE流的变化幅度比5?8 s时更明显些。这是因为随着网络中的流量进一步增加,网络负荷越来越重、性能下降,此时EF流由于优先级较高抢占了较多资源,对BE流的影响更加明显。

15?30 s的时间段内,BE流的吞吐量增加、丢包率下降,两种算法相比,差别较大,P-BDCBR算法明显要优异些。这是因为在15 s左右,节点时延达到门阀值,P-BDCBR算法的EF流被映射到备用链路,网络的负荷迅速减轻。而王勇智算法的EF流、BE流同时被映射到备用链路,仍存在相互抢夺资源的情况。

4 结语

P-DBCBR算法在原算法的基础上,改进了它的剪枝策略,加入了优先级约束,将优先级与流量有机地结合起来。当节点的负荷较重时,既保证了高优先级业务的“优先性”,又在一定程度上降低了低优先级业务的丢包率,提高了网络的吞吐量,减少了拥塞。从仿真结果来看,改进的算法在重负荷时,在丢包率以及吞吐量等方面较原算法有一定的优越性。

[参考文献]

[1]WANG Z, CROWCROFT J.QoS Routing for supporting resource reservation[J].IEEE Journal on Selected Areas in Communications,1996(7):1288-1294.

[2]尹国定,于战科,倪明放.多约束QoS路由的一种启发式算法[J].计算机工程与科学,2004(2):53-55.

[3]金明哗,黄永明,李乐民.一种新的IP分组丟弃策略PRDP[J].电子与信息学报,2002(8):1073-1079.