基于成本最优的IP路由算法

摘要：该文为解决IP网络中成本问题，提出了一种基于成本最优的IP路由算法。此算法是在给定网络初始拓扑情况下，通过优化网络的流量分布以达到全网花费的代价总和最小的目的。该文首先提出网络成本问题和数学模型，然后列出了算法框架，最后，对算法进行了仿真并得出了实验结果。

关键字：成本最优；路由算法；链路利用率

中图分类号：TP393 文献标识码：A 文章编号：1009-3044(2012)29-7003-03

1 问题描述

目前对网络规划的研究主要集中于负载均衡[1-2]，即最小化最大链路利用率问题。而对无网络供应商和客户来说，网络设备的成本代价永远是考虑的首要问题。面对客户大量业务需求，需要选择出合适的网络原件（路由器、插卡）满足业务的需求，这就需要我们队业务进行合适的规划布局，使得满足需求的同时应用的成本最低。对于现存网络来说，网络成本主要是节点成本和链路成本，节点成本主要包括路由器及路由器上应用的插卡数量，链路成本则是与节点距离相关，本文算法在设计时参考已设计的算法[3-6]，主要考虑节点成本，对链路成本通过设置权重来避免应用低利用率长链路。首先给出两个本文应用的定义：

定义2 平均链路利用率：网络中的链路平均利用率为所有链路(m,n)∈E带宽利用率的均值，即，其中表示链路数。

链路带宽利用率反映了链路上的带宽使用情况，也反映该链路的负载情况。当时，也就是链路(m,n)的负载比较重时，节点m和n间链路的已用带宽与请求的带宽接近，将来会很难再接纳其他经过该链路的业务请求，再接受其他业务时可能会导致拥塞丢包现象。是反映了全网链路利用率的情况，当较大时表示全网中链路负载较重。本文在考虑平均链路率的基础上设计了成本最优的算法。

3 算法实现

基于上述LP方程中的问题，本文设计了求最小成本的路由算法，本算法是基于IP路由算法的基础上增加了对成本优化的模块，由于IP路由算法是基于最短路径进行转发的，则算法的关键在于通过修改链路上的权重值，通过比较找到成本最优的解。

Step2：调用IP路由算法（最短路径算法）路由业务。路由业务之前，先将业务按带宽由大到小顺序排序，然后通过Dijkstra算法依次路由业务，并根据业务带宽选择或利用最适合的端口（如某个端口上剩余容量可以满足该业务，则无需增加新端口，否则，从候选端口中选择出一个满足带宽要求且费用最低的端口），流程图1所示。

Step3：调用流量优化算法降低最大链路利用率，使得全网负载均衡。流量优化算法流程图2所示。

首先将全网链路按利用率由大到小进行排序，然后增加利用率最高的链路的权重，则再调用IP路由算法重新路由业务直到链路上利用率降低。

Step4：代价优化。全网的代价取决于应用的端口数，优化的目的也是尽量应用合适的端口，使得在满足全网业务带宽的前提下，应用的端口代价最低。则优化过程中对利用率最低的链路增加其权重，使得该链路上的业务不再经过此链路，则可删除该链路对应的端口，达到降低全网代价的目的。

5 结束语

针对网络规划成本问题，本文提出了一种基于成本最优的路由算法，该算法在流量负载均衡的基础上，添加了代价成本模块。由于IP网络中路由是基于最短路径的，即取决于链路的权重，该算法通过设置链路的权重，尽量减少应用的硬件，以得到代价最优的路径。本文首先提出了网络成本最小问题，然后建立ILP方程，第三部分列出了算法的核心模块，最后，对算法进行了仿真。实验结果与ILP求解的结果对比证明，该算法可以实现成本最优的问题求解，能够规划出满足业务需求且代价较优的网络。

参考文献：

[1] Shi Yan,Liu Zengji,Qiu Zhiliang, et al.Load Balance Based Network Bandwidth Allocation for Delay Sensitive Services[C].Proceedings of the 19th International Conference on Advanced Information Networking and Applications (AINA’05)? 2005 IEEE,2005.

[2] Liu Xin,Chien A A.Traffic-based Load Balance for Scalable Network Emulation[C]. Proceedings of the ACM/IEEE SC2003 Conference,2003.

[3] Cheng Xiao-mei, Wang Sheng, Wang Xiong. Optimizing Link Weight in OSPF Routing Under Unknown Traffic Matrices[C].2009 IEEE 34th Conference on Local Computer Networks,2009.

[4] Fortz B,Thorup M.Internet traffic engineering by optimizing OSPF weights[C].Proceedings of INFOCOM, 2000:519-528.

[5] Ericsson M,Resende M G C,Pardalos P M.A genetic algorithm forthe weight setting problem in OSPF routing[J].Journal of CombinatorialOptimization, 2002,3(6):229-333.

[6] Buriol L, Resende M,Ribeiro C,et al.A hybrid geneticalgorithm for the weight setting problem in OSPF/IS-IS routing[J].Network, 2005,1(46):36-56.