基于图模型的算力网络表征与路由方法

本发明属于网络通信，尤其涉及一种算力网络表征与路由方法，可用于算力路由。

背景技术：

1、作为计算与网络深度协同的新型网络架构，算力网络通过无所不在的网络连接分布式计算节点，保证网络能够按需、实时调度不同位置的计算资源，满足新的业务场景对通信、计算的需求，进一步提升用户体验，其理论与技术也一直是学术研究的重点内容。随着算力网络框架的不断完善，算力路由作为重要组成部分，计算与网络资源一体化表征与路由技术被视作一种有效的路由方案，通过感知用户需求，综合考虑网络的实时状况和算力节点资源状态，将用户计算任务路由到最佳的目标节点，从而保证端到端总时延最短。

2、xueying han在ieee发表的文章《utility-optimized resource allocation incomputing-aware networks》中提出了一种算力网络中基于效用函数的计算与网络资源调度与路由方法，该方法通过设计效用函数，将可用带宽资源映射为用户的满意度，计算资源转为容量约束，以最大化用户满意度为优化目标，将算力网络中计算网络资源联合调度与路由问题转化为了效用值最优化问题。但该方法通过先找带宽满足业务需求的路径，后找计算容量满足的计算节点，本质上是一个两阶段的方法，难以找到端到端总时延最短路径，并且在小规模网络中，该方法的求解时间已经达到秒级，而通常时延敏感类业务的时延要求都在毫秒级，因而难以满足时敏业务的端到端低时延需求，也难以扩展到大规模网络。

3、hongqing ding在science direct发表的文章《optimal routing andheterogeneous resource allocation for computing-aware networks》中提出了一种算力网络中路由和异质资源分配模型，该模型以最小化操作成本为优化目标，将计算资源与网络资源统一转化为操作成本，并以计算资源和网络资源容量受限为约束，将算力网络中路由规划与资源分配问题建模为了操作成本最小化的整数线性规划问题。由于整数线性规划问题是np-hard问题，求解复杂度高。因此在大规模网络中，又设计了一种启发式算法，通过采用深度搜索优先和分支定界法，来遍历网络中所有可行的路径和计算中心，最后选择成本最小的组合作为最优解。但该方法通过先找到满足符合业务计算需求的计算节点候选集，然后通过深度搜索优先多次遍历经过候选集中计算节点的路径，最后在所有结果中选择代价最小的方案作为最优解，本质上还是先找到满足业务计算需求的计算节点，然后再找穿过该计算中心的可行路径。由于该启发式方法求解复杂度与算力网络的规模以及网络中计算节点的数量有关，因而同样在大规模网络中难以快速找到最优解。

技术实现思路

1、本发明的目的在于针对上述现有技术的不足，提出一种基于图模型的算力网络表征与路由方法，以联合调度计算与网络资源，快速找到端到端总时延最短路径。

2、本发明的技术方案是：通过复制基于图表征的算力网络，将源节点和目的节点分别挂载到两个不连通的子图，引入计算边连通子图，将节点的计算资源转化为计算边上的链路容量，从而得到算力网络扩展图模型，最后在扩展图中采用最短路径算法寻找时延最短路径，其实现步骤包括如下：

3、(1)构建算力网络快照图模型：

4、(1a)根据快照图由节点和边构成的结构形式，将快照图中的节点对应算力网络中的计算节点或转发节点，每个计算节点上都标注有权重；将快照图中的边对应算力网络中的链路；

5、(1b)将可连通的节点通过边进行连接，构成算力网络快照图模型；

6、(2)构建算力网络扩展图模型：

7、(2a)复制快照图模型得到两张快照图，并对第一张快照图中所有指向目的节点的边和目的节点进行删除处理：

8、(2b)根据节点属性引入有向计算边：

9、若节点为计算节点，在两个快照图对应计算节点之间引入一条计算边，该计算边的头为第一张处理后的算力网络快照图中所述节点，其尾为第二张算力网络快照图中与所述节点对应的复制节点，并删除该计算边上权重标注为算力网络快照图模型中计算节点的权重，构成算力网络扩展图模型；

10、若节点为转发节点，则不需要引入计算边；

11、(3)通过dijkstra算法在扩展图中找到权重最小的路径。

12、进一步，所述步骤(1)中构建的算力网络快照图模型，包括：

13、计算节点，用于转发节点和执行计算任务；

14、转发节点，用于转发业务数据；

15、边，用于表示节点间的连通关系；

16、边的权重，用于表示沿当前链路通信的时延，其包括传输时延、传播时延、处理时延、排队时延；

17、计算节点的权重，用于表示当前计算节点执行计算任务所需的计算时延。

18、进一步，所述步骤(3)中通过dijkstra算法在扩展图中找到权重最小的路径，实现如下：

19、(3a)初始化：在扩展图中设置源节点的权重为0，所有其它节点的权重为无穷大；

20、(3b)创建一个优先队列，将源节点加入队列；

21、(3c)从优先队列中选择当前权重最小的节点，设为当前节点；

22、(3d)对于当前节点的每一个邻接节点，计算其从源节点经过当前节点到该邻接节点的权重，并将该权重与当前记录的权重进行比较：

23、若该权重小于当前记录的权重，则更新邻接节点的权重，并将其前驱节点设置为当前节点，执行步骤(3e)；

24、若该权重大于或等于当前记录的权重，则邻接节点不作处理；

25、(3e)将处理过的邻接节点及其更新后的权重加入优先队列,从优先队列中移除(3c)中的当前节点；

26、(3f)判断优先队列是否需要再次更新：

27、若优先队列为空或队列包含目的节点，则执行步骤(3g)；

28、若优先队列非空且不包含目的节点，则返回步骤(3c)；

29、(3g)从目的节点开始，沿着前驱节点回溯到源节点，重构出最短路径，即为所求权重最短路径。

30、本发明与现有技术相比具有如下优点：

31、第一，本发明通过将源节点和目的节点分别挂载到两个不连通的子图，引入计算边连通子图，将节点的计算资源转化为计算边上的链路容量，从而构建了可联合调度计算与网络资源的扩展图模型，为采用图的经典算法找路提供了基础，相比于传统的两阶段方法，可找到端到端总时延最短的路径；

32、第二，本发明由于构建的扩展图的规模有界，即复制了一次快照图模型，其节点数至多为快照图模型的2倍，其链路数至多为快照图模型的2倍加上计算节点数，因而不会使其随着网络中计算节点的增加而迅速扩大。

33、第三，本发明由于采用基于图的路径搜索算法即dijkstra算法在扩展图中寻找权重最短的路径，不仅求解复杂度低，且能够保障求解结果的最优性，可适用于大规模算力网络。

技术特征：

1.一种基于图模型的算力网络表征与路由方法，其特征在于，包括如下步骤：

2.根据权利要求1所述的方法，其特征在于，步骤(1)中构建的算力网络快照图模型，包括：

3.根据权利要求2所述的方法，其特征在于，用于转发节点的计算节点，是指具有转发节点功能的节点，包括可接收来自源节点或其他节点的数据，并根据路由表或转发规则能将数据转发到与所述转发节点连通的下一个节点或目的节点。

4.根据权利要求2所述的方法，其特征在于，用于执行计算任务的计算节点，包括能对数据进行整合、提取、内容分析及实时渲染等任何计算任务的节点。

5.根据权利要求2所述的方法，其特征在于，用于转发业务数据的转发节点，是指能处理路径选择和数据流量管理、能通过mac地址表来转发业务数据、能够进行协议转换的节点。

6.根据权利要求1所述的方法，其特征在于，步骤(3)通过用dijkstra算法在扩展图中找到权重最短的路径，实现如下：

技术总结
本发明公开了一种基于图模型的算力网络表征与路由方法，主要解决现有算力网络计算资源与网络资源独立调度，求解复杂度高的问题。其实现方案为：1)根据快照图的结构形式，用算力网络中的节点和链路分别对应快照图中的节点和边，并将可连通的节点通过边连接，构成算力网络快照图模型；2)复制快照图模型得到两张快照图，删除第一张快照图中所有指向目的节点的边和目的节点，并在两个快照图对应的计算节点之间引入一条由两张复制快照图组成的计算边，构成算力网络扩展图模型；3)利用最短路径算法在扩展图中找到权重最小的路径。本发明求解复杂度高低，能快速找到一条从源节点到目的节点的总时延最短路径，可用于算力网络最优计算中心的选择和路由快速决策。

技术研发人员：李红艳,刘飞,王鹏,马英红,史可懿,张建国,郭宗焕
受保护的技术使用者：西安电子科技大学
技术研发日：
技术公布日：2024/9/23