面向流量工程优化的约束路由算法分析

钟华

摘 要 流量工程的网络优化价值较高，可以解决在互联网中由传送机制与最短路径路由算法所导致的拥塞现象，优化网络资源。本文介绍的是面向多路径流量工程的约束路由算法，它以多路径路由算法来将网络资源利用率最大化，使流量请求通过多条不同路径实现传输，实现了负载均衡分布的最终目的。

【关键词】流量工程优化 约束路由算法 多路径 优化

面向流量工程优化的约束路由算法有许多，例如在线单路径流量工程约束路由算法、预计算型单路径流量工程约束路由算法、多路径流量工程约束路由算法等等。其中多路径路由可以最大化优化网络资源的利用率，使流量请求在多条不同路径中实现数据传输。它不但降低了路由路径的拥塞概率，也提升了数据路由数据传输的稳定安全性。多路径流量工程约束路由算法包含两种，一种是最小化路径数目及干涉的多路径选择算法，另一种是基于流量分配的最小干涉多路径算法，本文主要介绍前者。

1 面向多路径流量工程优化的约束路由算法

1.1 算法概述

经实践研究验证表明，以负载均衡为优化目标的约束路由算法能有效提升网络资源的可利用效率，因此多数多路径流量工程优化的约束路由算法也把主要关注点放在了负载均衡上。但事实证明，目前面向最小化路径数目及干涉的多路径选择算法研究并不多且不成熟，所以本文希望简要研究一下这种算法，证明面向最小干涉优化可以提高网络资源利用请求成功率，避免请求相互干扰和阻塞这一说法。

1.2 优化目标

多路径路由的优化准则就是以最小代价化函数为主，设路径数为m，Bi作为路径i所分配的贷款，而Cij作为沿路径i的链路j传输以bit数据为单位的代价，ni为路径i上所存在的链路数目，所以最优化的多路径路由最小化代价函数就应该为：

并要求同时满足：

基于上述的一般化准则，在实际计算中可能涉及到的常见优化目标就包括了负载均衡、最短路径、最小化多路径数目以及最小干涉等。

另外就是负载均衡，它的优化原则是对网络吞吐量的提升。在多路径路由优化算法中，ECMP路由算法算是比较经典和简单的一种负载均衡算法。它的简单之处就在于它可以在多条路径之间平均分配流量，并常用负载均衡优化措施来实现对最大链路利用率的最小化。

2 最小化路径数目及干涉的多路径选择算法解读

2.1 算法目标

多路径最小干涉路由算法的目标就是降低路由出入口对彼此之间的干扰，提升请求接纳成功率。本文所提出的就是一种基于最小干涉多路径的启发式优化算法，在路由的实际构造算法中提高性能，因此算法中考虑了最小化路径数目、干涉最小化、负载均衡等等优化目标。以下为启发式链路权值函数算式：

在此算式中，表示路由出入口对（s，d）的重要性系数，而表示（s，d）之间所能够达到的最大流量时链路l上的流量。在该算法中，它的主要倾向是选择合适的链路，而r（l）表示链路中可用的实际带宽，它表示能够承载未来请求的能力，如果链路的可用带宽小，就要避免拥有如此链路的路由。

2.2 具体算法流程

根据以上算法目标给出算法的具体流程，首先要明确的是算法的伪代码，基于多路径最小干涉算法，首先输入坐标点G=（V，E），它所对应的出入口对集合为P，为此建立路径请求为（s，d，BW）。然后基于s到d的多条路径进行输出，并定义它的子路径贷款之和应该为BW。

算法的实施过程如下：首先对所有出入口计算最大流量；然后进行链路权重计算；第三步设置初值i=1，则有Flag=False；最后一步要考虑i值，如果i≤K（最大流量值），那么原图中应该删除剩余带宽小于BW/i的链路，并绘制导出图。最后开始循环并重置标志Flag=True，导出最小加权路径j。结果若能成功导出链路带宽，则要从导出图中删除已有的路径i以及它的瓶颈链路。如果未能成功导出链路带宽，则要根据可行路径原则来设置标志使得Flag=False，最后退出循环j，并按照i条路径构建从s到d的标签式交换路径。

2.3 多路径最小干涉路由算法的复杂度分析

对多路径最小干涉路由算法的复杂度分析要分4步进行。首先第一步利用最高标签来预留推进算法，并为每个出入口计算其最大流量需要，如果有p个出入口对，则有。

第二、三步分别为提取并设置常数时间。

最后一步根据链路需要结合常数时间执行共需，所以该算法的总体复杂度实际上就应该为：。

2.4 算法模拟实验

为了证明最小化路径数目及干涉的多路径选择算法的优化性能，本文采用网络拓扑实验，在5个出入口对中记录拓扑值，并请求在{10，20，30，40}中随机产生静态LSP，当LSP被建立后才宣告实验结束，可以在5个出入口对之间产生约800以上的流量请求。

如图1，实验中出入口对于最大流总量之间的关系是随着时间的改变而不断变化的，这就说明在最小路径数目及最小干涉多路徑算法中，最大流量减小速度<最小路径数目，所以该算法对高效预留网络容量是很有效果的。

另外，在350个左右的网络请求下传统算法的资源消耗<最小路径数目等代价的多路径算法。而在350个请求后，传统算法>最小路径数目等代价多路径算法。考虑到两种算法存在吞吐量差异，所以综合来看最小路径数目等代价多路径算法在带宽占用方面相对更高效。

而在网络多线路全部链路带宽利用率方面，则当其标准差越小则证明所有链路的负载水平越接近。反之则表明负载均衡效果不甚理想。根据实验结果，本算法的链路带宽标准差是一直低于最小路径数目等代价多路径算法的，这就说明了该算法在负载均衡效果方面是要好于最小路径数目等代价多路径算法的。

3 总结

本文主要介绍的是最小化路径数目及干涉算法，它主要实现了两大优化目标，那就是最小化路径数目最小干涉。前者能够节省链路带宽资源，也能使得标签空间与负载均衡处于优化状态。而后者则尽量避免了不同出入口对之间所产生的路由干涉。该算法谈不是绝对的最佳算法，因为在实际应用中还要根据具体的链路带宽与网络拓扑情况来进行相应算法及参数的设置。

参考文献

[1]程小梅.IP网络流量工程优化算法研究[D].电子科技大学，2010.19-21.

[2]王新华，孙义欣，苑芳兵等.基于流量工程的动态路由算法研究[J].山东师范大学学报（自然科学版），2009，24（1）：36-39.

[3]孟兆炜.面向流量工程优化的约束路由算法研究[D].国防科学技术大学，2007，75-80.

作者单位

四川职业技术学院 四川省遂宁市 629000