一种域内路由选择优化方法及系统

1.一种域内路由选择优化方法，其特征在于，该方法包括：
步骤1)采集域内网络中所有路由器节点的本地路由表数据，通过路由表中路由表项之
间的索引关系构建路由回溯表，该路由回溯表由回溯表项组成，回溯表项中记录路由表项
的回溯路径；
步骤2)以所有路由回溯表组成的数据集作为事务数据集，利用Apriori算法从事务数
据集中逐级发现多级频繁项集，并从各级频繁项集中挖掘出对应级数的主干路由器节点，
所有主干路由器节点用于组建域内网络中分组转发的主干链路；
步骤3)除主干路由器节点以外的路由器节点作为普通路由器节点，采用设定的优先连
接规则为所有普通路由器节点确立强连接，该优先连接规则为：查找普通路由器节点的邻
居节点，按先后顺序优先选择主干路由器节点或分支路由器节点作为连接对象确立唯一的
强连接，所述的分支路由器节点为与主干路由器节点直接或间接相连的路由器节点；
步骤4)利用距离向量的路由路径算法在对本地路由表更新过程中，对于由不同邻居节
点发来的、具有相同目的地址和距离的路由表项，优先选择由强连接转发的路由表项更新
到本地。
2.根据权利要求1所述的域内路由选择优化方法，其特征在于，所述步骤1)中路由回溯
表构建的具体过程为：
步骤101)采集域内网络中所有路由器节点的本地路由表数据，路由器节点保存的本地
路由表基于RIP协议构建，路由表中的路由表项包括目的IP地址、下一跳IP地址和距离字段
值dm；
步骤102)提取当前路由表项Tm中的目的IP地址作为索引，从下一跳IP地址所在的路由
器节点的路由表中查找是否存在相同目的IP地址的路由表项Tm‑1，如果存在且距离字段值
为dm‑1，则执行步骤103)，否则删除当前路由表项；
步骤103)继续提取路由表项Tm‑1中的目的IP地址作为索引，重复执行步骤102)，直至遍
历到该目的IP地址所在的路由器节点后，将参与运算的所有路由器节点对应的IP地址按遍
历的先后排序，生成当前路由表项Tm所对应的回溯表项Bm，所述的回溯表项Bm包括由IP地址
组成的回溯路径和各IP地址在该回溯路径中的跳数。
3.根据权利要求1所述的域内路由选择优化方法，其特征在于，所述步骤2)中主干路由
器节点挖掘的具体过程为：
步骤201)由生成的每一回溯表项作为一项事务数据，将所有路由器节点的回溯表项组
成事务数据集；
步骤202)以回溯路径上的IP地址作为项，扫描事务数据集中各事务的所有项，累计每
个项的计数，由满足最小支持度计数的项组成频繁1项集的集合L1，并从频繁1项集的集合L1
选择计数最高的一项IP地址所在的路由器节点作为1级主干路由器节点；
步骤203)对频繁k‑1项集的集合Lk‑1中的元素按支持度计数降序排列，执行自连接
如果(li[1]＝lj[1])∧(li[2]＝lj[2])∧…∧(li[k‑2]＝lj[k‑2])∧(li[k‑1]
＜lj[k‑1])，表示频繁k‑1项集的集合Lk‑1中的子项集li和lj是可连接的，则连接子项集li和
lj产生候选k项集{li[1],li[2],…,li[k‑1],lj[k‑1]}，由上述自连接运算生成的所有候选k
项集组成集合Ck，其中k≥2；
步骤204)扫描事务数据集中各事务的所有项，累计包含Ck中每个候选k项集的事务计
数，由满足最小支持度计数的项集组成频繁k项集的集合Lk，对集合Lk中的元素按支持度计
数降序排列，按序提取同时包含1至k‑1级主干路由器节点IP地址的项集记为预选项集Pk，
k‑1 k‑1
从所有预选项集Pk中提取排序靠前的2 个普通路由器节点所对应的IP地址，并将该2 个
普通路由器节点作为k级主干路由器节点；
步骤205)对排序后的集合Lk重复执行步骤203)和步骤204)，以获得k+1级主干路由器节
点，并继续迭代运算直至无法再获得更高级数的主干路由器节点后，将挖掘出的各级主干
路由器节点组成主干路由集合，并按级数升序排列，其中主干路由器节点的级数与优先级
成反比。
4.根据权利要求1所述的域内路由选择优化方法，其特征在于，所述步骤3)中为普通路
由器节点确立强连接的具体过程为：
步骤301)利用路由回溯表提取当前普通路由器节点的所有邻居节点，按以下规则选择
连接对象：
如果邻居节点中存在一个主干路由器节点，则选择该主干路由器节点与当前普通路由
器节点的连接确立为强连接，并将当前普通路由器节点命名为x级第1分支路由器节点，其
中x表示连接的主干路由器节点级数，分支路由器节点的级数与优先级成反比；
如果邻居节点中存在至少两个主干路由器节点，则选择级数低的主干路由器节点与当
前普通路由器节点的连接确立为强连接，并将当前普通路由器节点命名为x级第1分支路由
器节点；
如果邻居节点中不存在主干路由器节点，则执行步骤302)；
步骤302)利用路由回溯表提取还未建立强连接的普通路由器节点的下n跳节点，n≥1，
按以下规则选择连接对象：
如果下n跳节点中存在一个x级第m分支路由器节点，则选择该分支路由器节点与当前
普通路由器节点的连接确立强连接，并将当前普通路由器节点命名为x级第n+m分支路由器
节点，其中m≥1；
如果邻居节点中存在至少两个分支路由器节点，则选择级数和分支计数低的分支路由
器节点与当前普通路由器节点的连接确立强连接，并将当前普通路由器节点命名为x级第n
+m分支路由器节点，其中x、m分别属于确立强连接的分支路由器节点的级数和分支计数属
性；
如果下n跳节点中不存在分支路由器节点，则执行步骤303)；
步骤303)利用路由回溯表提取还未建立强连接的普通路由器节点的下n+1跳节点，重
复执行步骤302)，直至所有普通路由器节点在域内网络中均确立有强连接。
5.根据权利要求1所述的域内路由选择优化方法，其特征在于，所述步骤4)中采用改进
的RIP协议执行相邻路由器节点之间的路由信息交换及更新操作，具体操作过程为：
接收邻居节点X发来的路由表，对于由邻居节点X到目的地址D的距离值为d1的路由表
项，如果本地路由表中不存在目的地址D，则将该路由表项添加到本地路由表中；
否则，将距离值d1与本地路由表中记录的到目的地址D的距离值d2进行比较，如果d1+1
＜d2，则将邻居节点X的路由表项更新到本地；
否则，如果d1+1＝d2，提取本地路由表中记录的到目的地址D的下一跳节点Y，比较邻居
节点X与下一跳节点Y的优先级，如果邻居节点X的优先级大于下一跳节点Y的优先级，则将
邻居节点X的路由表项更新到本地，如果邻居节点X的优先级不大于下一跳节点Y的优先级，
则不对本地路由表项更新；
否则，如果d1+1＞d2，则不对本地路由表项更新；
其中，普通路由器节点优先级＜分支路由器节点优先级＜主干路由器节点优先级，对
于相同级数的两个以上分支路由器节点：分支计数低的分支路由器节点优先级＞分支计数
高的分支路由器节点优先级。
6.根据权利要求1所述的域内路由选择优化方法，其特征在于，在执行k级主干路由器
节点挖掘过程中需要满足条件：选择的k级主干路由器节点与k‑1级主干路由器节点不相
邻。
7.根据权利要求1所述的域内路由选择优化方法，其特征在于，在主干路由器节点的选
k‑1
择过程中，如果存在多于2 个符合k级主干路由器节点选择条件的普通路由器节点，则进
一步统计符合条件的普通路由器节点在所有路由回溯表中出现的频次，并选择出现频次最
k‑1
高的前2 个普通路由器节点作为最终的k级主干路由器节点。
8.根据权利要求1所述的域内路由选择优化方法，其特征在于，在普通路由器节点确立
强连接的过程中，如果存在两个以上的、具有相同级数和分支计数的分支路由器节点时，则
进一步统计分支路由器节点在所有路由回溯表中出现的频次，并选择出现频次最高的分支
路由器节点与当前普通路由器节点的连接确立为强连接。
9.根据权利要求1所述的域内路由选择优化方法，其特征在于，所述的最小支持度计数
表示为：
其中，表示所有路由器节点在事务数据集中出现频次的均值。
10.一种域内路由选择优化系统，其特征在于，该系统包括路由优化服务器、路由采集
器和路由器节点；
所述的路由优化服务器与分布式部署于域内网络中的路由采集器连接，具体包括：
路由回溯表生成模块：接收路由采集器转发的各路由器节点的本地路由表数据，通过
路由表中路由表项之间的索引关系构建路由回溯表，该路由回溯表由回溯表项组成，回溯
表项中记录路由表项的回溯路径；
主干路由器节点挖掘模块：以所有路由回溯表组成的数据集作为事务数据集，利用
Apriori算法从事务数据集中逐级发现多级频繁项集，并从各级频繁项集中挖掘出对应级
数的主干路由器节点；
强连接定义模块：采用设定的优先连接规则为所有普通路由器节点确立强连接，该优
先连接规则为：查找普通路由器节点的邻居节点，按先后顺序优先选择主干路由器节点、分
支路由器节点作为连接对象确立唯一的强连接；
强连接信息发送模块：将与普通路由器节点确立为强连接的对方身份信息通过路由采
集器发送给指定的普通路由器节点，该身份信息包括路由器节点的IP地址、属于主干路由
器节点或分支路由器节点的等级属性；
所述的路由采集器用于采集临近路由器节点的本地路由表，并转发至路由优化服务
器，同时负责转发具有强连接关系的路由器节点身份信息，该路由采集器不参与域内网络
的路由信息交换和更新服务；
所述的路由器节点具体包括：
路由表发送模块：根据路由采集器发来的路由回溯请求消息，向对应的路由采集器回
传本地的路由表数据；
强连接信息接收模块：接收与本地具有强连接关系的对方身份信息，并保存至本地；
路由表接收模块：用于接收相邻路由器节点发来的路由表数据；
路由更新模块：基于改进的RIP协议，以具有强连接关系的连接对象作为路由更新的优
先选择方式完成本地的路由更新。

暂无

暂无