MPLS网络中基于信息反馈的流量工程路径计算

徐 方，赵国涛

（1.湖北工程学院 现代教育技术中心，湖北 孝感432000；2.湖北工程学院 外国语学院，湖北 孝感432000）

随着互联网数据呈现指数级的增长，对网络的管理和控制显得越来越重要。显然，增加网络带宽并不能解决所有网络拥堵的问题。与此同时，越来越多的网络运营商非常有兴趣在他们的网络中提供差异化的服务。这些需求使得通过自动流量工程（Traffic Engineering，TE）获得网络的控制权变得日益重要。TE能减少拥塞，提高网络利用率，满足多样化的需求。

流量工程是MPLS网络中最重要的应用［1］。MPLS流量工程（MPLS－TE）可以通过协调网络资源的请求和当前可用资源来增加MPLS骨干网网络传输能力。由于流量工程的本质是将流量映射到物理拓扑结构，这意味着，在MPLS－TE的核心部分是路径计算的问题。

传统的尽力而为的IP网络一直青睐“最短路径”的算法，是因为要考虑所有负载条件下的效率和稳定性。但是随着人们对网络服务质量的进一步重视，除了计算源端到目的端的最小路径外，还非常有必要找到与最小路径不同的其他路径。这是因为最短路径变得高度拥塞，而其他可用路径却只有相对较低的利用率。此外，由于不同的数据流量有不同的QoS要求，一个单一的路径不能够满足所有源端到目的端流量的要求。

传统的路径计算算法，主要是通过优化静态指标（如链路成本／长度等）逐跳计算的算法。其中，新一代TE算法认为可以设置链路的动态权重，但这建立在已知将来带宽请求的基础上。MIRA［2］讨论了源路由方案，它使用另一个动态约束（在网络中可用的最大流量）确定关键链路，算法返回的路径试图避免那些不可靠的路径。

本文提出了一种使用静态和动态链路约束的源路由算法。该算法通过计算由首跳路径长度来改进MIRA，以便它不超过某一阈值T；然后通过最大流计算［3］找到一个最小拥塞路径。在MIRA的最大流计算中，应该注意到大型网络运行中计算密集型的问题。作为替代方案，建议从动态识别的关键链路中使用相关信息反馈的方式。

1 流量工程的路径计算

在本文中，QoS请求的形式为（A，B，Bw）：其中A为源节点，B为目的地节点，Bw为应用需要的最小带宽。使用TE路径计算算法，可以计算满足BwPA－B的路径。本文假设可以通过TE信令机制（如CR－LDP和RSVP［4］）在PA－B路径上为应用程序预留带宽资源。

1.1 约束路径上的最大开放流

MIRA启发式地提出要寻找一对节点之间的路径的方法，在其所有源节点到目地节点中寻找拥塞程度最小的可用流路径。下面给出了该算法的主要思想：

使用如下函数分配动态链路的权限w（i，j）：

● Assign＿Dynamic＿link＿weights（）：

图1 MIRA算法

图2 B＿MIRA算法

本文提出的第一个算法是对MIRA的改进，称之为B＿MIRA（Bounded－MIRA）。使用u（i，j）作为静态链路度量值。在这种新的路径计算方案中，同时考虑了动态分配的 w（i，j）和静态u（i，j）。在实验中，使用的静态度量值是链路的长度。B＿MIRA的特色是首先提出了使用基于静态链路度量u（i，j）的K 短路径［5］算法找到候选路径集，它将返回一个K路径集合，该集合是通过MIRA类计算找到在所有源－目的节点对中拥塞最小的最大流路径。因此，返回的路径是不会逊色于K－最短路径。

2.2 使用TE信息降低算法的复杂度

最大流计算的应用使得使用动态信息约束进行路径计算成为可能。使用有界的MIRA类型算法，可以找到长度约束的最低阻塞路径。然而，众所周知的最大流算法的复杂度O（n2），而最简单的最短路径算法的复杂度是O（nlogn）。最大流量计算的计算开销很大，尤其是当运行数以百万计的请求时。本文建议使用另一种动态约束——链路负载（link＿load），它不需要很大的计算开销。相反，可以依靠现有的流量工程基础设施提供链路负载信息。假设大多数网络运行链路状态的内部网关协议（IGP）计算路由。文献［6］通过使用动态TE信息简单的扩展的方法，如将预留链路带宽定期反馈到源节点。这些信息可以用于取代使用最大流计算获得的关键链路信息。链路负载的定义如下：

关键链路被定义为其运行负载超过阈值百分比U的链路，改进的算法使用下面的函数和参数。

●Identify＿CN（）：

●Assign＿Dynamic＿link＿Weight（）：

每一个链路被分配一个动态权重w（i，j），

●关键的路径P定义为：

本文所提出的最小关键K－最短路径算法（MCKS）的计算过程同时考虑了动态分配的链路权重w（i，j）和静态链路度量u（i，j）。MCKS和B＿MIRA的不同之处在于临界值的定义和计算复杂度的不同。MCKS算法如图3所示。

图3 MCKS算法

2 性能分析

下面对目前主流的路径计算算法进行比较实验，给出初步的比较结果。所有的实验运行在一个由20个节点随机组成的网络上，所有链路都是均衡分布，并随机分配权重。链接的传输能力变化是平缓的，从中度（12000单位的预留带宽）到高（48000单位的预留带宽）。所有链路的传输能力中和高的比例固定为3：1。对于每个网络，所有可能的源－目节点对属于一个固定的集合S。网络资源的请求的形式为（src，dest，Bw）。从S中随时挑选源节点和目的节点。

实验结果由一个包含20个节点组成的网络中进行。图4是对比 MIRA、B＿MIRA和 Min＿Dist得到的带宽请求被拒绝的情况。从图4上可以看出，高负载下的网络阻塞大约在请求数到20000才开始，Min＿Dist在带宽请求被拒绝的情况相对较多。随着负载的增加，MIRA和B＿MIRA两种算法的表现相差不大。

图4 服务请求数与带宽拥塞

图5 平均路径负载

路径的负载计算是在这条路径的所有链路负载中选择最大值。图5是在高负载条件下的平均路径负载对照结果，可以看出，MCKS路径的平均负载是最低的，B＿MIRA的平均负载低于MIRA。

3 结论

由上述实验结果可以看出，动态链接度量指标可以帮助网络保持最佳的网络负载水平，而结合使用静态约束（如链路长度）来描述路径特征能取得更好的效果，避免了在高负荷条件下使用过多的重要网络资源。本文研究表明，利用TE反馈信息，代替高开销的最大流计算，可以有效降低流量工程计算算法的复杂度，在高负载下能提供良好的性能。从这个角度来看，MCKS是一种高效的TE路径计算算法。

［1］唐治果，李乐民，虞红芳，等.针对MPLS网络流量工程的链路关键性路由算法［J］.电子与信息学报，2007，29（5）：1187－1190.

［2］Kodialam M，Lakshman T.Minimum Interference Routing with Applications to MPLS Traffic Engineering［C］／／Proceedings of IEEE INFOCOM’2009，2009.

［3］张静，邱学绍.网络最大流模型算法及其实现［J］.重庆大学学报：自然科学版，2006，29（5）：132－134.

［4］李效虎，张兴明，兰巨龙，等.MPLS流量工程中的RSVP和CR－LDP［J］.信息工程大学学报，2003，4（4）：50－53.

［5］Eppstein D.Finding the k shortest paths［J］.SIAM Journal on Computing，1998，28：652－673.