一种基于GPU的广域网信息传输调度方法和系统

本发明涉及通信，特别是涉及一种基于gpu的广域网信息传输调度方法和系统。

背景技术：

1、现代全球规模的在线服务，如搜索、社交网络和电子商务，需要在广域网(wan)上传输海量数据。然而，构建和维护wan的成本极高，因此网络运营商必须最有效地利用wan带宽，以容纳尽可能多的流量并尽快完成数据传输。

2、传统的流量管理解决方案存在分布式协议效率低下的问题，主要是因为路由器等设备缺乏对网络拓扑和流量需求的全局视图，从而无法做出良好的网络全局路由决策。然而，软件定义网络(sdn)的发展使网络运营商能够构建集中式控制系统，该系统能够获取全局拓扑和流量信息，并以集中的方式动态配置网络中的所有路由器和光学层中的光学设备，这种集中控制不仅提高了路由决策的效率，还增强了网络管理的灵活性和可扩展性。

3、该集中控制系统在动态配置网络层中设备过程中，会接收到一系列到达的传输请求，其中每个请求都有一个源、一个目的地、一个传输大小，因此需要设计一种能够优化数据包传输过程的信息传输调度问题的方法，在每个时刻决定要传输哪些数据包，确保数据在有效的时间内传输到目的地。

技术实现思路

1、发明目的：本发明的目的是提供一种基于gpu的广域网信息传输调度方法和系统，通过对各数据包传输顺序的调度，在最小完成时间实现所有数据包的有效传输。

2、技术方案：为实现上述目的，本发明所述的一种基于gpu的广域网信息传输调度方法，包括以下步骤：

3、步骤1：构建信号传输图，图中节点表示设备，两节点构成的边表示数据包传输路径；

4、步骤2：基于边的编号，对所有边进行初始化排序，生成一组初始随机序列；

5、步骤3：基于高斯分布生成的权重序列对初始随机序列重新排序，生成一组关于各边编号的初始解序列；

6、步骤4：将初始解序列输入到gpu中，利用邻域算子对初始解序列中元素位置进行变换，生成多组元素分布不同的初始解序列，构成解序列集；

7、步骤5：基于解序列集的计算规模在gpu中设置线程分配策略，进一步计算执行解序列集中每一个初始解序列所需要的时间；

8、步骤6：利用规约算法评价每个线程块计算出的结果，找出最优解，所述最优解为按照某个初始解序列执行各数据包的传输顺序，实现所有数据包传输的最小完成时间；

9、步骤7：通过多次迭代步骤2-6，输出迭代后的最优解对应的初始解序列，即为实现所有数据包传输的最优调度顺序。

10、其中，所述信号传输图构建过程为：假设有m个设备和n待传输的数据包，则信号传输图中有m个节点和n条边，其中节点vi可同时传输的数据包个数表示为p(vi)，i＝1,2,...,m，边ej对应的数据包传输时间表示为l(ej),j＝1,2,...,n，且

11、其中，步骤2所述的初始化排序方法为：基于已进行编号n条边构成边的集合e＝{e1,..,ej...,en}，(j＝1,2,...,n)为边的编号，生成一组1到n范围内的随机数序列x＝[x1,x2,...,xn]，作为集合e的初始随机序列，即初始随机序列中的随机数与集合e中的边随机对应，使得每个边都对应一个随机数。

12、其中，步骤3所述的基于权重对随机初始解序列重新排序的方法为：先基于高斯分布随机生成一组数量为n个的权重序列aσk，a＝a1,a2,...,an，a为一组均值为0随机高斯分布向量，σk为方差；

13、将权重序列和初始随机序列对应序列号的序列值相加，得到一组新的随机序列x'，作为优先级序列，x'＝[x1',x2',...,xn']＝x+aσk；将优先级序列中按序列值从大到小排序，获得关于集合e中各边编号的初始解序列，即初始解序列中第一位序号表示的优先级序列中序列值最大的边对应的编号，最后一位序号表示优先级序列中序列值最小的边对应的编号。

14、其中，步骤4所述的元素表示边的编号，利用邻域算子对初始解序列中元素位置进行变换的方法为：在当前线程的序号的位置开始移动指定的元素，从而生成一个新的解序列；重复移动过程，从而生成多组元素分布不同的初始解序列，构成解序列集。

15、其中，步骤5所述的线程分配策略包括：

16、定义线程数和线程块大小：

17、

18、其中numblock为线程块数，threadperblock为每个线程块中的线程数，edge_num＝n为信息传输图中的边数；

19、数组定义和内存分配：数组order存在全局内存中，便于所有的线程访问，表示输入单个线程的初始顺序，大小为edge_num；数组limit_nodes为每个端口限制值，大小为node_num；数组files为边的属性，包含leftnode左端口、rightnode右端口以及length数据包传输时长，数据类型均为integer；端口表示节点，端口限制值表示节点可同时传输的数据包个数；数组output用于存储每个线程块内最优解值，大小为numblock；数组thread_per_time用于存储一个线程块内所有线程计算出来的解值，大小为threadperblock。

20、其中，基于所述线程分配策略，线程计算执行解序列集中每一个初始解序列的时间的方法为：线程计算执行解序列集中每一个初始解序列的时间的方法为：将解序列集输入到线程块中，所有线程块中的每一个线程对应一个初始解序列，所有线程同步执行计算，计算执行该初始解序列时所需要的时间：

21、

22、其中，s(e)为每个数据包传输的起始时间，l(e)为每个数据包需要传输的时长；e＝{e1,..,ej...,en}，(j＝1,2,...,n)为边的编号。

23、在该线程块中，每个线程计算出的结果存储在thread_per_time中，其中thread_per_time[0]存储的是该线程块的最优结算结果；每个线程块中thread_per_time[0]存储的最优结算结果进一步存入到数组output中。

24、其中，步骤6所述利用规约算法评价每个线程块计算出来的结果，找出最优解的方法为：基于数组output存储的所有线程块的最优计算结果，对比相同线程位置的计算的结果，找出每对比较中的最小值存入靠前线程的位置，重复迭代对比过程，每次迭代减少参与比较的元素数量，直到剩下一个元素，即为最优解。

25、其中，步骤7所述通过多次迭代步骤2-6，输出迭代后的最优解的方法为：设定迭代策略包括达到设定迭代次数后停止，输出最优解或经过多次迭代后，最优解未发生变化后停止，输出最优解。

26、本发明所述的一种基于gpu的广域网信息传输调度系统，包括：

27、信号传输图构建模块：构建信号传输图，图中节点表示设备，两节点构成的边表示数据包传输路径；

28、初始随机序列生成模块：基于边的编号，对所有边进行初始化排序，生成一组初始随机序列；

29、初始解序列生成模块：基于高斯分布生成的权重序列对初始随机序列重新排序，生成一组关于各边编号的初始解序列；

30、解序列集构建模块：利用邻域算子对初始解序列中元素位置进行变换，生成多组元素分布不同的初始解序列，构成解序列集；

31、解序列集求解模块：将解序列集输入到gpu中，基于解序列集的计算规模在gpu中设置线程分配策略，进一步计算执行解序列集中每一个初始解序列所需要的时间；

32、最优解生成模块：利用规约算法评价每个线程块计算出的结果，找出最优解，所述最优解为按照某个初始解序列执行各数据包的传输顺序，实现所有数据包传输的最小完成时间；

33、最优解迭代模块：通过多次迭代步骤2-6，输出迭代后的最优解对应的初始解序列，即为实现所有数据包传输的最优调度顺序。

34、有益效果：本发明具有如下优点：1、本发明基于设备和待传输的数据包构建信号传输图，通过图形化方式清晰地建模了设备和数据包之间的关系，为后续的传输调度问题的求解提供了直观、结构化的基础，有助于优化路径规划和提高整体传输效率；

35、2、基于信号传输图对所有边进行初始化排序，再利用高斯分布生成的权重序列对初始随机序列重新排序，为后续的优化调度提供了一个起点，使得复杂的优化问题可以从某个具体的解开始迭代和优化，从而提高了找到最优解的可能性；

36、3、通过引入邻域算子对初始解序列进行变换，增加了搜索解空间的可能性，同时有利于利用gpu的高并行处理能力，提高广域网信息传输调度的计算效率和性能，也为解决更大规模问题提供了有效手段；

37、4、针对解序列集的计算规模在gpu上设置了线程分配策略，以及利用规约算法评估每个线程块计算出的结果，可以快速确定哪个初始解序列能够实现所有数据包传输的最小完成时间，从而确保找到的是最优的数据包传输调度顺序，从而进一步减少了计算所需的时间，提高了整个信息传输调度的效率。

技术特征：

1.一种基于gpu的广域网信息传输调度方法，其特征在于，包括以下步骤：

2.根据权利要求1所述的基于gpu的广域网信息传输调度方法，其特征在于，所述信号传输图构建过程为：假设有m个设备和n待传输的数据包，则信号传输图中有m个节点和n条边，其中节点vi可同时传输的数据包个数表示为p(vi)，i＝1,2,...,m，边ej对应的数据包传输时间表示为l(ej),j＝1,2,...,n，且

3.根据权利要求1所述的基于gpu的广域网信息传输调度方法，其特征在于，步骤2所述的初始化排序方法为：基于已进行编号n条边构成边的集合e＝{e1,..,ej...,en}，(j＝1,2,...,n)为边的编号，生成一组1到n范围内的随机数序列x＝[x1,x2,...,xn]，作为集合e的初始随机序列，即初始随机序列中的随机数与集合e中的边随机对应，使得每个边都对应一个随机数。

4.根据权利要求1所述的基于gpu的广域网信息传输调度方法，其特征在于，步骤3所述的基于权重对随机初始解序列重新排序的方法为：先基于高斯分布随机生成一组数量为n个的权重序列aσk，a＝a1,a2,...,an，a为一组均值为0随机高斯分布向量，σk为方差；

5.根据权利要求1所述的基于gpu的广域网信息传输调度方法，其特征在于，步骤4所述的元素表示边的编号，利用邻域算子对初始解序列中元素位置进行变换的方法为：在当前线程的序号的位置开始移动指定的元素，从而生成一个新的解序列；重复移动过程，从而生成多组元素分布不完全相同的初始解序列，构成解序列集。

6.根据权利要求1所述的基于gpu的广域网信息传输调度方法，其特征在于，步骤5所述的线程分配策略包括：

7.根据权利要求6所述的基于gpu的广域网信息传输调度方法，其特征在于，基于所述线程分配策略，线程计算执行解序列集中每一个初始解序列的时间的方法为：将解序列集输入到线程块中，所有线程块中的每一个线程对应一个初始解序列，所有线程同步执行计算，计算执行该初始解序列时所需要的时间：

8.根据权利要求7所述的基于gpu的广域网信息传输调度方法，其特征在于，步骤6所述利用规约算法评价每个线程块计算出来的结果，找出最优解的方法为：基于数组output存储的所有线程块的最优计算结果，对比相同线程位置的计算的结果，找出每对比较中的最小值存入靠前线程的位置，重复迭代对比过程，每次迭代减少参与比较的元素数量，直到剩下一个元素，即为最优解。

9.根据权利要求7所述的基于gpu的广域网信息传输调度方法，其特征在于，步骤7所述通过多次迭代步骤2-6，输出迭代后的最优解的方法为：设定迭代策略包括达到设定迭代次数后停止，输出最优解或经过多次迭代后，最优解未发生变化后停止，输出最优解。

10.一种基于gpu的广域网信息传输调度系统，其特征在于，包括：

技术总结
本发明公开了一种基于GPU的广域网信息传输调度方法和系统，包括构建信号传输图，基于图中边的编号，对所有边进行初始化排序，生成一组初始随机序列；基于高斯分布生成的权重序列对初始随机序列重新排序，生成一组关于各边编号的初始解序列；将初始解序列输入到GPU中，利用邻域算子对初始解序列中元素位置进行变换，生成多组元素分布不同的初始解序列，构成解序列集；对解序列集进行求解；利用规约算法评价每个线程块计算出的结果，找出最优解；通过多次求解过程，输出迭代后的最优解对应的初始解序列，即为实现所有数据包传输的最优调度顺序。本发明通过对各数据包传输顺序的调度，能够在最小完成时间实现所有数据包的有效传输。

技术研发人员：张晓岩,姚志琦,高家全,王凤娟,毛亚平
受保护的技术使用者：南京师范大学
技术研发日：
技术公布日：2024/9/23