MPLS网络中QoS路径安排研究

孙尚 王万龙

（中国人民解放军66061 部队 北京市 100144）

1 引言

近几年，互联网(Internet)的迅速发展及使用人数的递增，带宽不足将是往后互联网所面临到的一个重要问题，带宽的竞争和冲突严重危害了整体网络的传输性能。由于标签交换技术的发展，许多优点因素证明其将发展为未来网络技术的主流，尤其多重协议标签交换技术(MultiprotocolLabel Switch, 简称MPLS)，它整合了目前各种交换式路由器技术的优点，其结合了非同步传送模式(Asynchronous Transfer Mode, 简称ATM)的快速化、简单传输的优点，以及传统IP 的普遍性(ubiquity)、延展性(scalability)及弹性度(flexibility)优点。本文重点研究MPLS 网络标签交换技术中的路由路径安排，并可以使得有足够的带宽分给不同类型服务，从而达到服务所需。

2 算法设计

2.1 LSP路由安排算法

本节将介绍如何安排有服务质量需求的数据的路由选择方式，下面列举两项：Best-fit shortest path algorithm (BSP)和Worstshortest path algorithm (WSP)。

2.1.1 Best-fit shortest path algorithm (BSP)

Best-fit shortest path algorithm 是 由Dijkstra’s shortest path algorithm 演变而来，将最短路径距离权重考虑成连接带宽权重，来计算安排某一来源端(source)到目的端(destination)之间标签交换路径，LSP(s, d)，而此LSP(s, d)路径所选择的路径，是为欲配置的LSP 路径所连接带宽剩余总和为最小者。

（1）相关符号定义与注解：

G(N, L, C)：图形G 具有N 个节点及L 个连接

N：网络节点数的集合

L：任两节点间连接(Link)的集合

C：网络所有连接带宽权重的集合

s：欲安排LSP 起点(来源端)

t：欲安排LSP 终点(目的端)

b：欲安排LSP 所需带宽权重

S：N 集合中的部分集合

Du：s 点到u 点的带宽权重

duv：u 点到v 点之间连接的带宽权重

duv*：u 点到v 点之间连接减去b 后的带宽权重

G’：G(N, L)所有连接减去b 所行成的网络图形

图1：网络带宽安排范例

图2：弹性带宽配置

（2）BSP 实行步骤简述：

Step 1：网络所有连接带宽减去要配置给此LSP (s, d)的带宽b；即G’(N, L, C-b)。

Step 2：在G’(N, L, C-b)中，利用Dijkstra’s algorithm 计算安排一最短路径给 LSP(s,d)，此路径所选择经过的所有连接带宽剩余总和为最小者；

Step3：更新网络状态，将原G 减去LSP (s, d)所分配的带宽，即得网络所剩余带宽；然后回Step 1，安排下一条LSP。

2.1.2 Worst-shortest path algorithm (WSP)

Worst-shortest path algorithm 所计算路由方式和Best-fit shortest pathalgorithm 相似，两者最大差异在于前者所选LSP 路径其各Link所剩余资源为较多者，后者反之。

（1）相关符号定义与注解：

Du

hop：s 点到u 点的带宽权重

hop：为s 点到u 点所经的hop 数

duv：u 点到v 点之间连接的带宽权重

duv#：u 点到v 点之间连接减去b 后的带宽权重

（2）WSP 实行步骤简述：

Step1：网络所有Links 带宽减去要配置给(s, d)的带宽b；即G’(N, L, C-b)。

Step2：在G’(N, L, C-b)中,计算安排一经过hop 数为最少的路径给LSP(s, d)，此路径所选择经过的所有连接带宽总和，在其他相同hop 数的路径当中，其带宽剩余总和值为最大者。

Step3：更新网络状态，将原G 减去LSP (s, d)所分配的带宽，即得网络所剩余带宽；然后回Step 1，安排下一条LSP。

2.1.3 BSP 与WSP 的研究

BSP 算法所选择LSP 是所有连接剩余带宽和为最小者，此意思是说由利用BSP 算法所选择的路径将会是最接近其带宽需求的LSP。主要采用此方式的原因是考虑保留较大的剩余带宽给未来需求带宽较大的LSP 使用。例如图1 的网络拓扑有三条LSP(S1, D1, 4Mb)、LSP(S2, D2, 3Mb) 以及LSP(S3, D3, 2Mb) 需建 立。假如三条LSP 建立需求顺序为LSP(S3, D3,2Mb)-＞LSP(S2, D2, 3Mb)-＞LSP(S1, D1, 4Mb)，以最短路径选择的话，S3 到D3 将先选R3-R4-R9-R11、S2 到D2 将选R2-R4-R6-R9-R10、S1 到D1 将被拒绝。

但假如采用BSP 方式选路S3 到D3 将选择更其带宽需求最接近 的R3-R4-R5-R7-R8-R9-R11(2Mb)、S2 到D2 选R2-R4-R6-R9-R10(3Mb)、S1 到D1 选R1-R4-R9-R12(4Mb)。在这种情形下，采用BSP 算法选择路径可达较佳状况。

但是BSP 缺点是由于是选择最接近其带宽需求的路径，所以没有考虑到连接资源消耗的问题，如图1 中LSP(S3, D3, 2Mb)所选的路径将经过六个连接，然而其需求带宽应用为2Mb，便使用了整体网络12Mb 的带宽。

WSP 算法选路原则是计算安排经过hop 数为最少且所经连接带宽剩余总和值为最大的路径。WSP 选择路径的考虑因素是为了企图达到网络负载平衡，也就是说，WSP 选择路径方式主要希望将网络数据流尽量分布于网络之中，其采用“经过hop 数为最少”的原因是考虑连接资源消耗的问题。但是其缺点为可能造成往后较大带宽容量需求的LSP 无法配置情形发生。同样以图1 为例，三条LSP 建立需求顺序为LSP(S3, D3, 2Mb)-＞LSP(S2, D2, 3Mb)-＞ LSP(S1, D1,4Mb)，采用WSP 方式选路却可能发生跟最短路由方式相同的情形，S3 到D3 将先选R3-R4-R9-R11、S2 到D2 将选R2-R4-R6-R9-R10、而S1 到D1 将被拒绝。

由于BSP 和WSP 算法，各有其所考虑因素及其缺点，故本论文将其分别应用于不同服务数据流当中，测试两者使用在LSP 路由安排机制上情形，并将在往后章节作一研究其模拟结果。

2.2 伸缩限制带宽的方法

为了让网络中连接带宽得以有效率地分配，本节提出伸缩限制带宽(Elastic Constrained Bandwidth，ECB)的配置方式。此配置方式的主要目的是为避免或缓解高优先权路径，因过于集中某些连接，而造成这些连接无法弹性利用，及促使其他低优先权重据的需求，可能因此无法传送而需等待。在伸缩限制带宽的配置方式中，本研究中订定一弹性参数Ef来作为调节高优先权及低优先权路径在使用连接时的使用率。我们将Ef的大小设置为介于0～1 之间。当网络高优先权重据在作路径安排动作时，网络连接带宽将根据弹性限制参数(Ef)而受到某程度的使用限制，致使高优先权路径得以选择其他连接，避免集中情形产生。对低优先权类型服务，则考虑其业务特性，让低优先权类型数据可有弹性弥补网络安排的LSP 的带宽过多于实际传送数据量使用的带宽时，而造成的资源浪费，而大胆地将连接带宽多分配比率给低优先权类型使用，以寻求改善。如采用伸缩限制带宽方式来分配路径，假设Ef值为0.25，则表示在高优先权重据使用连接带宽时，将保留总连接带宽的25%，作弹性调整。而低优先权重据使用连接带宽时，将有以多于连接带宽25%的带宽，来作其弹性调整。例如图2 所示，假设(S1,D1)、(S2, D2)之间，各有两不同服务类型数据(GS 及CLS)需要传送，传送顺序为高优先权重据(GS)优先，GS 类型所需带宽为3Mb、CLS 类型为4Mb。假设所欲配置的LSP(S1, D1 ,3Mb ,GS)经由R1-R3-R4-R6-R7路径传送时，根据伸缩限制带宽方式选路的话，R3-R4-R6 路段将只剩余1.5Mb(6×0.25-3=1.5)的带宽来提供GS 类型数据流。所以另一LSP(S2, D2, 3Mb, GS)则将选择另一路径R2-R3-R5-R6-R8。如此依据伸缩限制带宽方式选路，可避免其两条GS 类型LSP 同时经过相同路段(R3-R4-R6)且占尽其所有资源。然而，在CLS 类型LSP 安排上，虽然连接带宽无法达到其所需带宽，但根据弹性参数作其连接的弹性调整，即整条连接将可分配7.5Mb (6+6×0.25=7.5)带宽，故两CLS 类型LSP 将也可以得到路径分配。由此方式将两高优先权重路径分开，保留连接资源，对于将来使用亦可简易调整或增大其所需带宽，而减去作重新选路计算的动作。对于超额分配给低优先权服务的方式，则是主要考虑网络整体资源能够达到充分利用。

3 结语

本文考虑不同服务类型数据的优先次序，来做路径选择安排的比较，并得以保障高等级服务应用的实现，且加入伸缩限制带宽的配置方式，不仅可以提供大部分高优先权服务的应用，而且对于其他低优先权服务也可以获得实现，且同时能够保障或达到使用者所要求服务的最低需求，换句话说，在高优先等级服务得以保障的同时，也希望较低优先等级服务能得到其所需求的最低保障带宽。