1 引言

　　动态路由算法是mpls流量工程中最关键的技术之一[1，2]，建立有带宽保证的路由问题已经有大量的前期工作，其中代表性的路由算法主要有最小跳算法(min-hop aigorithm，mha)、最宽最短路径算法(widestshortest path，wsp)[3]、最短最宽路径算法(shortestest widest palh，swp)[4,5]、以及最小干扰路径算法(minimuminterference routing algorithm，mira)[6，7]等。

　　mha算法采用的是基于目的地最短路径路由,就是在网络源节点与目的节点之间查找一条具有最小跳数的可达路径。此算法会导致多条最短路径都选用同一条链路而发生拥塞。wsp与swp算法基本相似,wsp算法是在多条跳数最小的侯选路径中选择一条可用带宽最多的一条路径：swp是在多条可用带宽最大的路径中选择一条跳数最小的路径进行路由。这两种算法属于贪婪算法，并且对同一节点对产生多条最小跳或是最大带宽的几率并不是很大，因此算法的效果并不理想。比较复杂的影响力最大的算法包括最小干扰路由算法(mira)，主要思想是在为当前源、目的结点对选择lsp时尽量减少对未来节点对建立链接请求的影响,从而优化网络性能。但是从mira算法对关键链路的定义来看,此算法只定义了属于某节点对的最小割的链路为关键链路,并没有考虑非关键链路对未来建立链路请求的影响，并且算法复杂度高。

2 系统模型及算法描述

2．1 网络模型描述

　　网络路由算法研究通常借助图论描述网络模型,网络的拓扑结构以无向加权连通图g=(v,e，b)表示，v(｜v｜=n)表示路由节点集合：n表示节点数目，e(｜e｜=m）表示链路集合，m表示链路数目；b表示网络中链路容量的集合。用l表示可能产生建立lsp请求的进出路由器对的集合。需要建立lsp链接请求r(s。d，b)表示，s和d分别表示业务流的入口和出口节点。b表示需要链接的业务流(s,d)的需求带宽,r1表示链路i的剩余带宽。

2．2 算法描述

　　此前大多数有带宽保证的路由算法基本只考虑链路剩余带宽而没有考虑链路的带宽利用率,以至于其他条件都相同的情况下,带宽相同的两条链路同等对待,而实际上这两条链路的负载相差很大，因此建立链路之后对网络的影响截然不同。

　　定义：链路带宽利用率a1：对任意节点对(s，d)，接受请求带宽为b的链路请求之后的链路带宽利用率为：

　　链路带宽利用率反应链路当前的负载情况，也可反应建立lsp请求后的链路负载情况，a1的值越小说明建立链接对以后的lsp链接请求的影响越小，当a1 值接近为1时说明链路的负载非常重，接入新的链路请求的动态成本非常高。

　　mbgra算法的核心思想是先计算各个链路的权重值，而后用最短路由算法查找权重最小的路径。此算法在计算链路权值时分为离线阶段和在线阶段。离线阶段计算的链路初始权值w(l)是静态的，在网络拓扑一定的条件下不发生变化，只有当网络拓扑发生变化时才需要重新计算。

2.2.1 离线阶段

　　对任意给定的网络拓扑结构，对任意lsp请求i(s,d,b)，首先计算(s,d)∈l的结点对之间的网络最大流为fsd。由于网络最大流路径的选择不唯一，因此我们计算出网络最大流的所有可能组合，对任意的链路的使用无疑将改变网络最大流，因此用fsd1表示在离线状态下节点对(s,d)∈l之间的网络最大流中通过链路l的流量,我们定义此链路对(s，d)∈l之间的网络最大流的贡献量为,此值反映了链路l对将要建立的(s,d)∈l之间的链路请求的相对重要程度。计算单个链路i相对结点对(s，d)∈l的链路权值为：

　　其中，fsd代表路由节点对(s，d)之间的网络最大流，fsd1表示路由出入节点(s，d)∈e之间的网络最大流中通过链路i的部分，n表示在路由结点对(s，d)之间的网络最大流路由数目．m表示这n种网络路由数目中通过链路i的次数。计算链路i的初始权值w(i)为：

2.2.2 在线阶段

　　对于给定的网络拓扑,在离线阶段已经计算出单条链路的初始权值w(i)，定义单条链路的及时权值为：

在我们的研究过程中发现，链路带宽利用率al对链路权值的影响并没有预想的那样大，因此我们给al开方来定义链路的及时权值。此定义链路权值不仅定量分析了单个链路对网络最大流的贡献量，并且考虑了单条链路的负载情况,因此mbgra算法在选择路由路径的过程中可以更好的优化网络资源，建立更加合理的路由路径。

　　对到达的任意lsp链接请求r(s,d,b)表示，s和d分别表示业务流的入口和出口节点，b表示需要链接的业务流(s，d)的需求带宽，利用式(4)计算每条具体链路的链路权值,采用diikstra's算法选择权值最小的路径建立lsp链接,并更新剩余网络带宽参数。

2.3 算法