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

李军旺

摘要：针对王勇智算法在负荷较重时，低等级业务丟包率较高的不足，文章改进了其剪枝条件，引入节点时延和优先级约束，提出一种基于优先级的带宽时延约束路由算法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.