基于图曲率的通信网络瓶颈度量与局部拓扑优化方法及系统
本技术涉及网络通信,具体地,涉及一种基于图曲率的通信网络瓶颈度量与局部拓扑优化方法及系统。
背景技术:
1、近年来,随着视频会议、云计算、大模型业务等应用持续增长,骨干网与数据中心网络中的流量呈现明显的动态性与非均匀性,网络拥塞风险显著增加。传统按静态或统一流量模式设计的通信网络难以持续适配此类时变需求。为保障低时延、高带宽与服务可靠性,业界普遍采用软件定义网络(software-defined network,sdn)、虚拟覆盖路由以及可重构光交换等技术,对网络拓扑进行动态调整。因此,如何在流量波动场景下实现高效拓扑重构,已成为通信网络规划中的关键问题。
2、在给定流量需求、链路状态与服务约束条件下,网络规划通常需要联合决策拓扑连接关系、链路容量及路由策略。现有研究多采用优化求解或学习求解方式,从全局解空间搜索网络拓扑,以降低一次性建网成本或提升整体性能。如专利“cn114884825b;一种网络规划方法、装置及电子设备”为典型的优化求解方法,通过混合整数规划联合优化拓扑、链路容量与路由,在全局解空间内寻优,以一次性建网成本最小为核心目标,并依托业务约束、多方案综合评估兼顾网络整体性能。该类方法在理论上可获得较优全局结果,但在网络频繁升级场景下往往需要对原拓扑进行较大幅度重构,容易带来较高的重配置成本与工程实施开销,难以满足在既有网络基础上实施渐进式、低扰动拓扑演进的工程需求。
3、进一步地,网络规划问题可建模为混合整数规划(mixed integer programming,mip)问题,优化变量与约束规模会随网络规模快速增长。无论是商业求解器还是现有启发式方法,在大规模、时变流量场景中均可能面临求解效率、可扩展性或稳定性不足的问题。尤其在需要快速响应拥塞变化时,若无法在有限计算时间内完成有效决策,将影响网络重构的实时性。
4、局部拓扑优化被认为是降低重配置成本、提升在线可用性的可行方向,但其核心难点在于:一是如何准确识别拥塞瓶颈链路,二是如何确定最有效的局部拓扑调整操作。现有瓶颈识别方法通常依赖特定网络模型或先验流量信息,泛化能力受限;而已有曲率类度量多面向无向图或无权图,难以直接适用于具有方向性与容量差异特征的通信网络有向加权图。因而,亟需一种面向通信网络特性的流量传输瓶颈度量方法,以支撑低成本、可解释且高效率的局部拓扑优化。
技术实现思路
1、针对现有技术中的缺陷/之一,本技术的目的是提供一种基于图曲率的通信网络瓶颈度量与局部拓扑优化方法及系统。
2、本技术的第一方面,提供一种基于图曲率的通信网络瓶颈度量与局部拓扑优化方法,包括:
3、将待优化的通信网络拓扑建模为有向加权图;
4、根据所述有向加权图和曲率计算方式,确定所述有向加权图中的每一有向边的曲率,并将最小曲率对应的有向边确定为最拥塞链路;
5、遍历所述最拥塞链路的节点对应的节点邻域集合,确定与所述最拥塞链路的节点组成新的3-环集合和4-环集合的邻域连接方案;
6、遍历所述邻域连接方案,采用所述曲率计算方式,确定优化后的最拥塞链路的曲率;
7、根据所述最拥塞链路的曲率和优化后的最拥塞链路的曲率,确定曲率变化值;
8、根据所述曲率变化值和成本约束条件,局部优化所述待优化的通信网络拓扑,确定经过优化的通信网络拓扑。
9、可选地,所述将待优化的通信网络拓扑建模为有向加权图,包括:
10、将所述待优化的通信网络的站点作为所述有向加权图的节点;
11、将所述待优化的通信网络的站点和站点之间的流量传输通信链路作为所述有向加权图的节点和节点之间的有向边,所述有向边的方向表征流量传输方向,所述有向边的权重表征流量传输通信链路的链路容量。
12、可选地,所述曲率计算方式为:
13、根据预设的节点距离阈值,定义每一节点的节点邻域集合,所述节点邻域集合包括单跳开出邻集和单跳闭出邻集;
14、将每一节点的出边权重之和确定为每一节点的节点权重;
15、根据所述每一节点的节点权重、所述有向边的权重以及所述节点邻域集合中的节点集合,确定每一有向边的曲率,所述节点集合包括3-环集合、4-环集合以及非3-环集合、4-环集合的节点集合。
16、可选地,所述根据所述有向加权图和曲率计算方式,确定所述有向加权图中的每一有向边的曲率,包括:
17、;
18、;
19、;
20、;
21、;
22、;
23、;
24、其中,表示节点到节点的有向边的曲率,表示节点到节点的有向边的权重,表示节点的节点权重,表示节点到节点的有向边对应的通信链路容量,表示节点的单跳开出邻集,表示节点的单跳开出邻集,表示节点到节点的有向边的节点邻域集合中的3-环集合,表示节点到节点的有向边的节点邻域集合中的4-环集合,表示节点到节点的有向边的节点邻域集合中的非3-环集合、非4-环集合的节点集合,表示单射函数集合。
25、可选地,所述根据所述最拥塞链路的曲率和优化后的最拥塞链路的曲率,确定曲率变化值,包括:
26、
27、其中,表示所述最拥塞链路在节点对、建立连接后的曲率变化值,表示优化后的最拥塞链路的曲率,表示所述最拥塞链路的曲率。
28、可选地,所述预设的成本约束为优化后的通信网络拓扑的成本增量不大于预设的成本阈值。
29、可选地,所述根据所述曲率变化值和成本约束条件,局部优化所述待优化的通信网络拓扑,确定经过优化的通信网络拓扑,包括:
30、根据所述曲率变化值,采用
softmax函数构建概率分布;
31、根据所述概率分布,进行加权随机抽样,确定实际连接链路;
32、根据所述成本约束条件,返回所述根据所述有向加权图和曲率计算方式,确定所述有向加权图中的每一有向边的曲率,并将最小曲率对应的有向边确定为最拥塞链路的步骤,重复确定新的实际连接链路,直至所述新的实际连接链路不再满足所述成本约束条件;
33、根据所述新的实际连接链路,局部调整所述待优化的通信网络拓扑,确定经过优化的通信网络拓扑。
34、本技术第二方面,提供一种基于图曲率的通信网络瓶颈度量与局部拓扑优化系统,包括:
35、有向加权图建模模块,用于将待优化的通信网络拓扑建模为有向加权图;
36、最拥塞链路确定模块,用于根据所述有向加权图和曲率计算方式,确定所述有向加权图中的每一有向边的曲率,并将最小曲率对应的有向边确定为最拥塞链路;
37、新链路探索模块,用于遍历所述最拥塞链路的节点对应的节点邻域集合,确定与所述最拥塞链路的节点组成新的3-环集合和4-环集合的邻域连接方案;
38、新链路曲率确定模块,用于遍历所述邻域连接方案,采用所述曲率计算方式,确定优化后的最拥塞链路的曲率;
39、曲率变化值确定模块,用于根据所述最拥塞链路的曲率和优化后的最拥塞链路的曲率,确定曲率变化值;
40、局部拓扑优化模块,用于根据所述曲率变化值和成本约束条件,局部优化所述待优化的通信网络拓扑,确定经过优化的通信网络拓扑。
41、本技术的第三方面,提供一种非临时性计算机可读存储介质,其上存储有计算机程序,该程序被处理器执行时实现本技术第一方面提供的任一项所述方法的步骤。
42、本技术的第四方面,提供一种电子设备,包括:
43、存储器,其上存储有计算机程序;
44、处理器,用于执行所述存储器中的所述计算机程序,以实现本技术第一方面提供的任一项所述方法的步骤。
45、本技术的基于图曲率的通信网络瓶颈度量与局部拓扑优化方法,将待优化的通信网络拓扑建模为有向加权图,并根据曲率计算方式,同时表征通信链路的容量差异和流量传输方向特性;遍历最拥塞链路的节点对应的节点邻域集合,构建新的3-环集合和4-环集合的邻域连接方案,并遍历邻域连接方案,确定最拥塞链路的优化前后的曲率变化值,从而量化评估候选方案的拥塞缓解效果以提高新增链路选择的针对性,还根据曲率变化值和成本约束条件针对瓶颈局部进行优化,从而有效避免全局重构导致的高昂链路调整与计算开销。
46、由附加特征带来的其他技术效果将在相应的实施例中进一步阐述。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com