一种基于智能查找算法的链路负载均衡方法

摘要

本发明提供一种基于智能查找算法的链路负载均衡方法，在修改了linux内核源码的基础上重新编写了路由模块，通过编译内核，形成的一种新的链路负载均衡技术。该技术可以提高网络选路的效率，特别是在多种线路运营商的情况下，可以通过智能选择线路，然后选择特定的路由进行数据路由。与传统的链路负载均衡相比，本发明能够快速分辨访问需要走的线路，并通过定制路由表，本发明提出的思想方法：(1)改进的二分查找算法，在IP数据库中快速辨别访问目的地址所属的线路。(2)自主的IP数据库结构创建。(3)开发了基于直接寻路思想linux内核功能模块。

主权项

一种基于智能查找算法的链路负载均衡方法,其特征在于为了提高数据查找效率，智能查找算法是在改进了折半查找算法的基础上，加入了分段的因子，该因子是通过多次检索总结出的一个经验值，通过经验值指导该段的IP应在分几段的情况下查找的最快，改进的算法是多个折半算法同时查找，因而效率提升了n倍，将数据查找分二段进行，然后在每个段中分别进行同步查找多个进程并行操作，在存放IP段的数据的二维数组中先分段再查找，时间复杂度在O((1/2)ⁿ)数量级上，将初始范围分为N段，在每一个段中分别进行二分查找，所需时间为原来的1/N；智能查找算法匹配规则如下：通过学习上N次的经验值得出本次应该将数据记录分成几段，即通过记忆多次的经验值来智能判断这一次应该分成的段数，将多次分段数结合时间值进行BP神经网络的优化，收敛最快最接近目标值的样本作为候选值，然后取候选值的平均值，利用BP神经网络作为分段的工具，限制优化学习的次数，只进行时间允许范围内的计算次数；内存数据结构是具有HASH功能和定时器功能的链表结构，每个节点存放了一个数据单元，数据链表初始化以后装填数据，然后按照hash算法将数据变量排序形成一个动态的数组，以供二分算法分段查找，存放数据的节点如下所示：在数据库中检索IP所属的线路，具体查找过程如下：(1)首先转换目标ip数据格式，将数据库中数据记录随机分成N段；(2)在每段中进行二分查找，根据数据库文件的存储格式，比较目的ip所属于的ip范围；(3)如果找不到返回默认线路。