文档介绍：基于成本最优IP路由算法
摘要：该文为解决IP网络中成本问题，提出了一种基于 成本最优的IP路由算法。此算法是在给定网络初始拓扑情况 下,通过优化网络的流量分布以达到全网花费的代价总和最 小的目的。该文首先提出网络成本问题和数学模型，然后列 出了算法框架，最后，对算法进行了仿真并得出了实验结果。
关键字：成本最优；路由算法；链路利用率
中图分类号：TP393文献标识码：A文章编号：
1009-3044(2012)29-7003-03
1问题描述
目前对网络规划的研究主要集中于负载均衡[仁2],即最 小化最大链路利用率问题。而对无网络供应商和客户来说， 网络设备的成本代价永远是考虑的首要问题。面对客户大量 业务需求，需要选择出合适的网络原件(路由器、插卡)满 足业务的需求，这就需要我们队业务进行合适的规划布局， 使得满足需求的同时应用的成本最低。对于现存网络来说， 网络成本主要是节点成本和链路成本，节点成本主要包括路 由器及路由器上应用的插卡数量，链路成本则是与节点距离 相关，本文算法在设计时参考已设计的算法[3-6],主要考虑
节点成本，对链路成本通过设置权重来避免应用低利用率长 链路。首先给出两个本文应用的定义：
定义2平均链路利用率：网络中的链路平均利用率为所 有链路(m,n)eE带宽利用率的均值，即，其中表示链路数。
链路带宽利用率反映了链路上的带宽使用情况，也反映 该链路的负载情况。当时，也就是链路(m,n)的负载比较重时, 节点m和n间链路的已用带宽与请求的带宽接近，将来会很 难再接纳其他经过该链路的业务请求，再接受其他业务时可 能会导致拥塞丢包现象。是反映了全网链路利用率的情况， 当较大时表示全网中链路负载较重。本文在考虑平均链路率 的基础上设计了成本最优的算法。
3算法实现
基于上述LP方程中的问题，本文设计了求最小成本的路 由算法，本算法是基于IP路由算法的基础上增加了对成本优 化的模块，由于IP路由算法是基于最短路径进行转发的，则 算法的关键在于通过修改链路上的权重值，通过比较找到成 本最优的解。
Step2 :调用IP路由算法(最短路径算法)路由业务。 路由业务之前，先将业务按带宽由大到小顺序排序，然后通 过Dijkstra算法依次路由业务，并根据业务带宽选择或利用 最适合的端口(如某个端口上剩余容量可以满足该业务，则
无需增加新端口，否则，从候选端口中选择出一个满足带宽 要求且费用最低的端口)，流程图1所示。
Step3 :调用流量优化算法降低最大链路利用率，使得全 网负载均衡。流量优化算法流程图2所示。
首先将全网链路按利用率由大到小进行排序，然后增加 利用率最高的链路的权重则再调用IP路由算法重新路由业 务直到链路上利用率降低。
Step4 :代价优化。全网的代价取决于应用的端口数，优 化的目的也是尽量应用合适的端口，使得在满足全网业务带 宽的前提下，应用的端口代价最低。则优化过程中对利用率 最低的链路增加其权重，使得该链路上的业务不再经过此链 路，则可删除该链路对应的端口，达到降低全网代价的目的。
5结束语
针对网络规划成本问题，本文提出了一种基于成本最优 的路由算法，该算法在流量负载均衡的基础上，添加了代价 成本模块。由于IP网络中路由是基于最短路径的，即取决于 链路的