基于MPLS流量工程的多路径约束负载均衡方法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于MPLS流量工程的多路径约束负载均衡方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：对多协议标签交换（MPLS）流量工程负载均衡问题，提出了两种多路径基于约束的负载均衡方法，在LSP建立初期就融入负载均衡思想。在通常的CSPF算法中，对于一个大带宽约束很可能无法找到可行路径，文中所提方法在没有单一路径满足带宽约束时，能将带宽约束划分为两个或多个子约束，并为每一子约束找到约束路径。实验结果表明，所提方法能增加路径建立的成功率，提高网络资源利用率，达到流量均衡。

关键词：多协议标签交换；流量工程；负载均衡；约束路由；区分服务

中图分类号：TP393.07

文献标识码：A

0引言

在网络上实施流量工程（Traffic Engineering，TE），提高网络资源的利用率和网络的整体性能已成为当前网络研究的重要课题。TE是提高网络性能、优化网络资源的重要手段，也是满足网络用户各种服务质量（Quality of Svervie, QoS）请求的有力保证。mpls作为一种先进的转发机制为TE的实施提供了便利，负载均衡（Load Balancing，LB）是其中的重要功能。

目前已有学者提出了一些负载均衡方法：MPLSOMP（Optimized MultiPath） 是根据各条路径上的流量来均衡负载的，它对负载的分担是由每条路径经过hash计算后的数值大小来决定的；由Widjaja和Elwalid提出的MATE（MPLS Adaptive Traffic Engineering），主要目标是在源、目的端LSR之间的多条LSP上均衡负载，从而避免网络拥塞。在MATE中，入口LSR定期发送探测包到出口LSR，再由出口LSR回送到入口LSR，入口LSR利用回送的探测包中的信息就能计算出LSP的特征从而在它们之间均衡负载；基于CRC16的Hash负载均衡算法 也只是从数量上进行流量分割，没有考虑QoS要求；文献[6]中提出了三种负载均衡算法,分别是基于拓扑、基于资源的静态负载均衡算法和动态负载均衡算法，这些算法也没有考虑QoS要求及业务的优先级。

多路径路由算法（MLR）是流量工程中的一个能够最大限度进行流量均衡的方法，能够达到最优的流量性能。由于在分组网络中延迟、抖动、带宽的相关性，对延迟、抖动的约束可以映射到对带宽和跳数的约束，本文试图从保证QoS和均衡网络负载的需求出发，以带宽和跳数为度量值，提出两种DiffServ策略下带优先级的基于多路径约束路由的负载均衡方法，在建立LSP时就融入负载均衡的思想，充分考虑了现实需求。

1多路径负载均衡方法

1.1优化目标

用G=（N，E）描述网络拓扑，N为节点集合，E是网络链路的集合。对于一个给定带宽要求，最优路径应该具有最小的端到端耗费。记m为所需路径的数目，Bi为路径i的使用带宽，Cij是路径i所包含的链路j传输数据包的每单位比特耗费，ni是路径i所包含链路的数目，xik表示路径i是否经由链路k，hi为路径i的跳数限制。则一条最优路径应最小化成本函数C:オ

其中， bk是链路k的剩余带宽， BWc是带宽约束。上述问题的解可通过如下过程找到：首先，计算出源、目的端间最小耗费路径，将路径带宽（路径上所有链路的最小带宽）分配给该路径；其次，计算剪除无可用带宽的链路后的最短路径，将路径带宽分配给它；继续这样的过程直到我们将整个带宽约束分配到连续的最短路径上。但是这种算法可能导致有大量的LSP来满足整个约束，这增加了计算和信令时间，并且在大量并行LSP之间分割流量也是非常困难的，因此，在相同条件下使LSP的数目尽可能小是一个很关键的问题。

1.2等带宽多路径约束负载均衡方法

这种方法的基本思想是将带宽要求划分成等带宽（Equal Bandwidth，EB）的多个子要求，对每一个子要求，通过CSPF算法找到一条最短路径，即在建立LSP时就考虑负载均衡。它首先试着寻找一条路径带宽大于或等于BWc的单一路径，这可通过Dijkstra或BellmanFord算法来实现，如果寻找失败，则计算两条满足子要求BWc/2的路径，如还是失败则计算满足BWc/3子要求的路径…如此计算直到找到带宽和等于或大于BWc的多条路径。下面给出算法描述：

其中，Q[m]为流量矩阵，d(Q[i])表示路径i上的带宽花的流量。オ

在相同带宽约束下，和单一路径路由算法(SLR)相比，EBMCM方法提高了路径建立的成功率。但是能否再减少LSP的数目呢？看图1所示的简单例子，在源、目的节点间有4条路径，其路径带宽分别是5Mbps，3Mbps，2Mbps和2Mbps。假如我们使用EBMCM方法为带宽约束为7Mbps的业务流建立路径，需要4条满足7/4Mbps的子要求路径，但是我们将约束进行不等分配的话比如4Mbps和3Mbps，只需要前两条路径就可以满足7Mbps的要求。

1.3最大路径带宽优先多路径约束负载均衡方法

为了满足带宽要求，该方法试着寻找最小数目的路径。首先，计算一条满足约束的单一路径，如果没有这样的路径，计算源、目的端之间最大带宽路径，将该路径上所有链路的最小带宽Е1分配给它，然后计算另一条满足剩余带宽要求（BWc-Δ1）的约束路经，如找到则完成，否则继续计算一条当前最大带宽路径，将它所包含链路的最小带宽Δ2分配给它…如此计算直到将BWc完全分配给找到的路径。

1.4在路径间负载均衡

如果能找到一条满足约束的单一路径就没有必要负载均衡，但如果我们通过上述算法找到多条路径，则应该最优地将流量分割映射到各条路径上。通常，我们通过链路i的利用率ρi来表示拥塞程度，定义如下：

其中，Ci是链路i的容量，χi是使用带宽，bi是i的可用带宽。当ρi接近于1时，链路变得拥塞，包丢失率和时延急剧增加，所以本文方法中负载均衡的基本思想是在分配流量后各路径的最小带宽链路的利用率保持相等。

记N为找到路径的总数目，Δi是第i条路径pi的带宽，ai是分配给pi流量，假设所有链路容量相等，则负载均衡方法简化描述如下：オ

在实际网络中，为了保证服务质量限制最大链路利用率ρmax小于1，在调整可用带宽Δi确保ρi不会超过ρmax后，我们可以根据式（5）～（7）计算出ai。オ

1.5DiffServ策略

DiffServ域由边界节点和核心节点组成，各自完成不同的功能。边界节点将业务流分成少量的类或聚集(Behavior Aggregation, BA)，它由IP分组头标的DSCP(区分服务码)来标识。内部节点根据每个BA相关的PHB(Perhop Behavior)来转发分组。PHB是BA的外部表现,可分解成调度特性和丢弃优先级。为了保证高优先级业务的QoS，同时又防止高优先级占据所有的输出带宽,可以采用加权公平排队策略（WFQ）来调度。WFQ为不同权重的流提供不同的优先级，分为基于序列号计算的WFQ和基于流或类的WFQ，前者模拟每次传输一个字节的广义处理器共享服务器，后者为每个流使用一个子队列，通过表排序来实现。

基于以上分析，可得到最大路径带宽优先多路径约束方法（MBFMCM）的总体流程如图2所示。其基本思想是对到达的业务流首先按QoS要求进行简单分类放入不同的队列，经过WFQ调度后通过多路径约束方法将不同队列上的业务映射到LSP上。EBMCM方法的流程只需进行相应变化即可。

2仿真

在这个部分，我们使用OPNET Modeler，对提出的两种负载均衡方法进行了仿真分析。网络拓扑如图3所示，为计算方便，设链路的容量都为30Mbps，可用带宽在1Mbps到30Mbps之间随机地产生，选择节点A、L为源、目的端。

在以上设定条件下仿真结果如图4~图6所示。由图4可见，路径建立成功率随着带宽约束的增加而下降。MLR的成功率比SLR要大，随着路径数目的增加成功率也随之增加，并且MBFMCM方法的成功率高于EBMCM方法。

图5给出了路径建立成功率随链路数目增加的变化曲线。可以看出随着链路数目的增加，成功率也增加。当有大量网络连接时找到合适路径的可能性增大了。图6给出了网络中负载分布（各链路利用率）情况，显示了路由的有效性，流量分布比较均衡，达到了均衡负载的目的。

3结语

本文提出了两种多路径基于约束的负载均衡方法，对网络流量进行均衡，得出以下结论：通过对带宽分割，增加了路径建立的成功率；引入了DiffServ策略，保证了业务流的QoS要求；基于Dijkstra算法的路由算法，可以保证所得最短路径是最优解；在建立LSP初期就融入负载均衡思想，使网络资源得到充分利用。