应用于网络流量控制的路由选择算法分析

季保启

菏泽家政职业学院，山东菏泽 274300

1 传统的路由选择算法

传统的路由选择算法通常可分为两类：静态路由选择算法与动态路由选择算法。

1.1 静态路由选择算法

静态路由选择算法是指对网络信息既不进行利用也不进行测量，按某种固定规律进行计算的路由选择的算法。

1.1.1 随机路径选择算法

随机路径选择算法是指在数据传输过程中，当数据包到达某一节点后，则在该节点上，通过完全随机法和轮选法两种随机方法，选择出一条输出路径进行转发。随机路径选择算法实现过程简单，但由于计算过程中有可能将其收到的数据包通过原来的路径折回，从而使数据包在网络中无限循环传达，而最终无法到达目的节点，因此具有一定的局限性。

1.1.2 扩散路径算法

扩散路径算法是指当某一个网络节点从某条线路收到一个分组后，再向其除了该条线路以外的所有线路发送收到的分组，最先到达的目的节点的一个或者若干组，耗时最短，必定为最短路径，在此过程中所有可能的分组都被尝试过。但此种方法会产生很多的相同分组，甚至可能产生无限多个分组。

1.1.3 最短路径选择法

最短路径选择算法是指用一个无向图来表示网络，认定无向图的每条边即为一条链路，在链路上用测度的数据进行标识，例如节点之间的距离，带宽，平均吞吐量等。然后通过计算，得出从本节点到其他节点的最优路径，同时将计算结果进行记录。当某一节点收到一个数据包需要转发时，可在数据包的计算结果中进行目的地址查找，找出最优链路进行转发[2]。

1.2 动态路由选择算法

动态路由选择算法根据网络当前的状态信息来进行节点网络策略的选择，又称自适应路由选择算法。

1.2.1 距离矢量算法

距离矢量算法中每个路由器都对应一张路由表，它以每个路由器为索引，在表中已详细列出了已知的路由器到每个目标路由器的最短距离及其所使用的线路，在执行过程中，相邻节点通过交换信息来更新表中的内容。距离矢量算法一般将距离用所通过的节点数或链路数表示，在一定周期时间内，每个节点将自己的距离矢量发送给相邻节点。若某个节点在给定的时间范围内，没有接到邻接点的距离矢量表，则可认定该邻接点的距离为∞，表示不可达到。在收到邻接点对应的距离矢量表后，节点根据优化原则，同步更新自己的距离矢量表。

1.2.2 链路选择算法

链路选择算法通过发现邻居节点、测量邻接点延迟、创建链路状态分组、发布链路状态分组、计算新的路由这五步进行实现。链路选择算法应用广泛，可应用于大型网络。

2 路由选择算法的改进

2.1 改进的路由选择算法的基本思想

由于源节点和目的节点并不相同，可能出现多个数据包流量所选择的最佳路径为同一链路的现象，这就使得某一链路被过分使用，而其他链路被闲置。流量淘汰算法即是当出现情况时，按照流量淘汰算法进行淘汰，将不适宜的流量进行转移，使其选择到其他闲置链路上，从而降低同一链路的使用率，最大程度的避免网络拥塞[3]。

2.2 改进的路由选择算法的模型

已知每段链路带宽为H，每段链路最大数据流量为qi， 若流量G选择了该段链路则会得到效益fiai，其中表示该流量被选择；ai=0表示该流量被淘汰。算法建立的数学描述如下：

2.3 算法的实现

此算法由于设置了过滤条件，可以使得可行解通过过滤条件直接过滤，而不用进行其他约束条件的判断，这种计算过程减少了运算次数，同时，每次得到的过滤条件的判断值是可以动态改变的，从而减少了计算量。

3 结论

与传统的路由选择算法相比，改进后得到的应用于流量控制的路由选择算法经，可较好的解决流量在选择数据传输时选择同一链路而产生的网络拥塞问题，链路的使用率得到均衡，大大提高了网络的吞吐量，对于缓解流量在数据传输过程中的数据包丢失情况有显著效果。改进的路由选择算法对于提高网络的数据传输速率，减少网络费用具有重要的意义。

[1]方敏，孙劲光，杨勇.基于流量控制的路由选择算法[J].辽宁工程技术大学学报，2002，21（6）：767-769.

[2]陶滔，马淑萍，罗江琴.网络路由信息安全应用研究-基于流量预测的路由选择新算法[J].中国安全科学学报，2003，13（5）：62-64.

[3]钱程.路由选择算法分析[J].信息科技，2010，21（5）：87-89.