面向软件定义网络的均衡分域方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN114124716A(43)申请公布日2022.03.01(21)申请号202010891071.0G06K9/62(2022.01)(22)申请日2020.08.30(71)申请人西南电子技术研究所(中国电子科技集团公司第十研究所)地址610036四川省成都市金牛区茶店子东街48号(72)发明人伍元胜(74)专利代理机构成飞(集团)公司专利中心51121代理人郭纯武(51)Int.Cl.H04L41/12(2022.01)H04L45/125(2022.01)H04L45/00(2022.01)G06F9/50(2006.01)权利要求书2页说明书8页附图3页(54)发明名称面向软件定义网络的均衡分域方法(57)摘要本发明公开的一种面向软件定义网络的均衡分域方法，旨在提供一种收敛快、效率高、能减小网络控制时延，提升网络性能的均衡分域方法，本发明通过下述技术方案实现：在给定网络拓扑、节点位置、预估的流量矩阵和单个域允许的最大规模后，执行基于K均值算法框架的初始分域阶段，使用宽度优先的图遍历初始化分布的域中心节点，反复进行距离优先的域增长和域中心节点更新；在初始分域结果的基础上执行基于商图的局部调优阶段，将分域结果中域边界节点在相邻域的移动进行的局部调优转换为商图，反复在分域结果转换得到的商图上寻找负权环或计算最小成本路径，直到商图中无负权环且分域结果达到绝对均衡为止，实现目标函数的优化和保证域规模的绝对均衡。CN114124716ACN114124716A权利要求书1/2页1.一种面向软件定义网络的均衡分域方法，具有如下技术特征：将面向软件定义网络的均衡分域分为两个阶段，阶段1：基于K均值聚类算法框架的初始分域阶段；阶段2：基于商图的局部调优阶段；在给定网络拓扑、节点位置、预估的流量矩阵和每个域允许的最大规模后，进行基于K均值算法框架的初始分域阶段，首先，根据网络节点数量和单个域允许的最大规模计算域的数量K,并从随机选择的一个节点出发，使用宽度优先的图遍历初始化K个分布较均匀的域中心节点，然后，反复进行距离优先的域增长和域中心节点更新，直到相邻两次迭代的分域结果完全相同为止，得到K个域节点连通、空间分布集中，具有凸包特性的初始分域结果；在初始分域结果的基础上进行基于商图的局部调优阶段，首先，将分域结果中域边界节点在相邻域的移动进行的局部调优过程建模为在图论中的商图上计算最小成本路径的过程，然后，反复在分域结果转换得到的商图上寻找负权环或计算最小成本路径，并在保证域节点连通性的条件下，根据负权环或最短路径执行同时对1个或多个域边界节点的移动，直到商图中无负权环且分域结果达到绝对均衡为止，从而实现目标函数的优化和保证域规模的绝对均衡。2.如权利要求1所述的面向软件定义网络的均衡分域方法，其特征在于：基于K均值算法框架的初始分域阶段，初始化域中心节点，首先根据网络的节点数和给定的单个域允许的最大规模计算域数量K，然后从随机选择的节点开始，使用宽度优先图遍历随机初始化K个在空间上分布相对均匀的域中心节点。3.如权利要求2所述的面向软件定义网络的均衡分域方法，其特征在于：在初始化中心节点后使用距离优先图遍历，以K个域中心节点为起点，遍历网络拓扑图进行距离优先的域增长。4.如权利要求3所述的面向软件定义网络的均衡分域方法，其特征在于：根据距离优先的域增长对初始化分域进行快速收敛性判断，如果新得到的K个域与上次的K个域完全相同，表明初始化分域已经收敛，则已得到初始的分域结果，退出阶段1并转基于商图的局部调优阶段；否则，更新域中心节点，计算每个域的所有节点位置的算术平均值，获取K个域的中心位置，然后选离中心位置最近的节点作为新的域中心节点，返回距离优先的域增长，继续进行收敛性判断。5.如权利要求1所述的面向软件定义网络的均衡分域方法，其特征在于：在分域结果收敛后进入部调优阶段，根据分域结果中域边界节点在相邻域间的移动构造商图；在商图中，如果域i有多个域边界节点与域j相邻，则v为移动成本最小域边界节点，每个节点表示1个域，每条有向边eij表示域i的域边界节点v移动到相邻的域j，边权值wij表示v从域i移动到域j的移动成本；为了保证域边界节点移动后域仍然是连通的，商图中的边对应的域边界节点不能是禁忌列表中的割节点。6.如权利要求1所述的面向软件定义网络的均衡分域方法，其特征在于：在负权环检测中，使用最短路快速算法SPFA在商图中进行负权环检测，判断是否找到负权环，如果找到负权环，先对负权环的每条边对应的域边界节点进行割节点检测，如果发现割节点，则将其加入禁忌队列，转入构造商图，继续进行负权环检测；如果没有发现割节点，执行负权环对应的域边界节点移动，并检查有节点移入或移出