多路由配置中备份拓扑存在的不足与改进算法研究

杨栩灼

摘要：本文介绍了多路由在配置中，由于备份拓朴数增加的时候会使得可用链路的增加，导致路由内存被占用过大的问题，提出改进关键节点的算法，减少路由跳数，起到优化的作用。通过对算法的综合评估认为改进后的算法具有可行性。

关键词：多路由配置；创建备份拓朴；改进算法

中图分类号：G424 文献标识码：A 文章编号：1009-3044（2018）06-0049-02

1多路由配置中备份拓扑存在的不足

因为多路由配置方法在现实使用过程中，假如传输的数据包没有通过故障链路，那么当其在故障状态下传输的数据包时其路由跳数是没有变化的。但是当相关数据传输过程中需要经过故障链路时，这时的路由跳数就会出现增加的现象。由于路由跳数的不断增加会使得流量加大、信道容易出现阻塞，相关数据报文也会出现延迟的现象。所以，一定需要想办法减少路由跳数的增加。此外，在具体的备份拓扑过程中，有一部分链路是受到相应的保护，因此，对于备份路由过程可用的链接数相对较少，这样会使得在恢复过程出现了有限可用链路的共享现象，很容易出现链路的超载。事实上，超载的链路是容易出现网络负荷的一个重要因素，同时也会降低用户体验。假如在增加备份拓扑的相关数目时，那么备份拓扑过程中，就会使得受保护的链路出现下降。这个时候，备份拓扑数的不断增加就会使得可用链路也会随之增加，那么路由的内存不断上升。因此，需要对原有方法进行优化。

2改进多路由配置中备份拓扑的算法

2.1关键节点的选取

在路由过程中备份拓扑链路的保护算法基本步骤：首先需要与关键点建立起相连的路径，并对其进行保护处理；其次是需要与普通节点相连的路径建立起保护的过程。当链路进行保护之后，需要对已生成的备份拓扑能否满足已有的拓扑创建規则，假如可以满足规则那么就继续进行，否则，程序就需要终止这个过程。这个算法的目的就是为了进一步增加关键节点的可用链路，从而可以更好地减少因选择最短路径而出现的跳数。

对于关键节点方面的选取，通常用两种方法。第一种方法就是选取出Top K个属于高介数值的节点位置（也即是Top K方法）。第二种方法就是通过使用一样的方法来选取Top K个节点，但是有必要考虑到节点的具体位置信息（也即是Non-adja-cent K方法），一般来说，如果选择出的某一个关键节点能够与现有关键节点相连接，那么就会放弃这个节点，再继续去寻找下一个更合适的点作为最新的关键节点。

2.2算法流程

说明：算法中的输入变量等于关键节点个数K，其中输出变量等于备份拓扑个数N。同时定义N等于1，算法总共由五个步骤组成，具体执行算法如下：

第一步：按照所定义好的关键点选取方法来对相关键节点的选取。

第二步：需要选取第K个关键节点，通常来说有这样的两种选取方法。

1）应用Top K选择方法：根据介数值的高低来对相关节点执行降序的排列，同时还需要选取前K个节点来作为具体的关键节点。

2）应用Non-adjacent K选择方法：这个关键节点不但拥有较大的介数值，并且有必要考虑关键节点在具体组网中体现的位置信息。假若关键节点是属于相邻的，那么其最大化可用的链路就会出现减少的可能。所以，假如当前所选的关键节点与之前所选取的关键节点是属于相邻的，那么就需要跳过当前的节点，此时就会选择下一个节点作当前的关键节点。

第三步：有必要与关键节点建立起具体的链路保护过程。使得能够与特定关键节点形成链路，以此来更好地保证各个备份拓扑中都可以通过最小的受保护链路数，具体如图1所示，从而可以达到保证各个关键节点在每个拓扑中都可以形成更多的可用链路。

这里将关键节点中保护链路在各个备份拓扑中占有的数量视为M，并将关键节点所拥有的最大出入度视为D，那么M>=ceil（D/N）+1。具体如图1所示，当出现的最大备份拓扑数是3时，以及关键节点为6时，其最大的出人度就等于3，那么各个备份拓扑中所受到保护的链路数最小值就等于1。

第四步：执行与之有关的普通节点的链路保护过程，并对各个链路实现保护。

第五步：判断最新生成的备份拓扑能否符合相关规则。如果能够满足，那么这次运行过程就结束。否则，就需要对N进行累加1，接着执行第一步。算法基本流程见图2。

2.3算法的实现

3改进算法后综合评估

事实上，关键节点在网络结构中选择是非常重要的，同时需要将关键节点的概念与备份拓扑结合起来。当在备份拓扑创建的最初阶段，需要通过关键节点评估的方法来选出具体的数目节点来作为最关键的节点，其他的节点视为普通节点。这个算法按照关键节点的出入度以及备份拓扑数的最大化关键节点来产生有关的链路等。为了可以更好准确的评估新的算法，这里提出了应用基于紧密度与介数值的综合评价方法：D（i）=C（i）B（i）。式中的D（i）是作为节点i的关键度，c（i）是作为节点i处于网络中心的程度，B（i）是指节点i对于邻节点所体现的重要程度。

对于关键节点的选取时，主要是将D（i）值高的节点根据顺序来作为关键节点。之后再应用Top K方法和Non-adjacent K方法来增加相关键节点的可用链路，以此来减少重路由所出现的跳数，从而达到优化算法的过程，改进后的算法具有可行性。

4结论

综上所述，本算法的重点是对关键节点的合理选取，关键节点的数目和关键节点的具体位置对于实验结果都会产生不同的影响，因此，需要做到在保障网络正常连通的情况下，选取合适的关键节点数目。通过对改进后的算法进行评估，认为改进后的算法具有可行性。