(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202110350933.3 (22)申请日 2021.03.31 (65)同一申请的已公布的文献号 申请公布号 CN 113032938 A (43)申请公布日 2021.06.25 (66)本国优先权数据 202110327597.0 2021.0 3.26 CN (73)专利权人 北京邮电大 学 地址 100876 北京市海淀区西土城路10号 (72)发明人 郑伟　李聪　章晨宇　王正英　 路兆铭　温向明　 (74)专利代理 机构 北京智信四方知识产权代理 有限公司 1 1519 专利代理师 黄健　葛啟宏 (51)Int.Cl. G06F 30/18(2020.01) G06F 30/27(2020.01) G06K 9/62(2022.01) G06N 20/00(2019.01)G06F 111/02(2020.01) G06F 111/04(2020.01) G06F 119/12(2020.01) (56)对比文件 CN 111740924 A,2020.10.02 CN 112511462 A,2021.0 3.16 US 202013 6894 A1,2020.04.3 0 LAN/MAN Standards Com mittee.802.1Qbv - IEEE Standard for L ocal and metropolitan area netw orks -- Bridges and Bridged Netw orks - Amendment 25: Enhancements for Sc heduled Traf fic. 《IEEE Internati onal Standard》 .IE EE,2018, 张弛等.时间敏感网络关键技 术与标准 化现 状. 《自动化仪表》 .2020,(第0 3期),全文. 姜旭艳等.S SA:一种面向CQF模型的TSN资源 调度算法. 《东北 大学学报(自然科 学版)》 .2020, (第06期),全文. 审查员 赵宇 (54)发明名称 时间敏感流的路由调度方法、 装置、 电子设 备及介质 (57)摘要 本公开实施例公开了一种时间敏感流的路 由调度方法、 装置、 电子设备及介质。 所述方法包 括： 利用谱聚类算法聚类K个时间敏感流得到N个 簇； 根据簇内时间敏感流的相似度对簇排序； 基 于配置的时间敏感流的全局网路拓扑结构确定 簇内每个时间敏感流在所述全局网路拓扑结构 上路由调度的约束条件； 利用优化器求解得到时 间敏感流的输出链路信息以及在该输出链路上 的开始传输时间信息。 该技术方案通过对时间敏 感流分簇， 并根据簇的顺序进行路由调度， 并通 过对每个簇内时间敏感流确定约束条件， 进而将 调度问题 转化为线性规划问题进行求解， 简化了 时间敏感流的路由调度问题， 提高了计算效率，从而可以适应 于动态业 务需求。 权利要求书2页 说明书9页 附图4页 CN 113032938 B 2022.07.08 CN 113032938 B 1.时间敏感流的路由调度方法， 其特 征在于， 包括： 利用谱聚类算法聚类K个时间敏感流得到N个簇， 其中， K个时间敏感流两两间的相似度 根据时间敏感流的属 性特征计算得到， 所述属 性特征包括： 基于源节点及目的节点确定的 路由路径数量、 传输时长以及流 量周期； 根据簇内时间敏感流的相似度对簇排序， 并按照簇的排序对K个时间敏感流进行路由 调度； 基于配置的时间敏感流的全局网路拓扑结构确定簇内每个时间敏感流在所述全局网 路拓扑结构上路由调度的约束条件； 使用线性规划问题 处理方式， 利用优化器求解得到时间敏感流的输出链路信 息以及在 该输出链路上 的开始传输时间信息； 其中， 所述线性规划问题的优化 目标为最小化时间敏 感流的端到端时延和路由数目； 根据所述输出链路信息以及在该输出链路上的开始传输时间信息配置所述全局网路 拓扑结构中的交换机节点。 2.根据权利要求1所述的方法， 其特征在于， 所述基于配置的时间敏感流的全局网路拓 扑结构确定 簇内每个时间敏感流在所述全局网路拓扑 结构上路由调度的约束条件， 包括： 裁剪时间敏感流的全局网路拓扑 结构中的冗余链路， 得到简化网络； 基于所述简化网络确定簇内每个时间敏感流在所述全局网路拓扑结构上路由调度的 约束条件。 3.根据权利要求1或2所述的方法， 其特征在于， 所述约束条件至少包括： 冲突避免约 束、 时延约束、 实时性约束以及链路传输约束。 4.根据权利要求3所述的方法， 其特 征在于， 所述时间敏感流两 两间的相似度为： 其中， Ri和Rj分别表示了时间敏感流i和j使用的路径集合， ||表示路径集合中元素的个 数， ti和tj分别表示了时间敏感流i和j的传输时长， Pi和Pj分别表示了时间敏感流i和j的流 量周期。 5.根据权利要求1、 2或4所述的方法， 其特 征在于， 聚类得到的N个簇的数量 为： 其中， n为每个簇内时间敏感流的数量， 5 ≤n≤10。 6.根据权利要求5所述的方法， 其特征在于， 所述根据所述输出链路信 息以及在该输出 链路上的开始传输时间信息配置所述全局网路拓扑 结构中的交换机节点， 包括： 根据输出链路信息确定门控列表的对应端口； 以及 根据输出链路上的开始传输时间信息确定所述门控列表开启门的时间。 7.时间敏感流的路由调度装置， 其特 征在于， 包括： 计算模块， 被配置为利用谱聚类算法聚类K个时间敏感流得到N个簇， 其中， K个时间敏 感流两两间的相似度根据时间敏感流的属 性特征计算得到， 所述属 性特征包括： 基于源节权　利　要　求　书 1/2 页 2 CN 113032938 B 2点及目的节点确定的路由路径数量、 传输时长以及流 量周期； 排序模块， 被配置为根据簇内时间敏感流的相似度对簇排序， 并按照簇的排序对K个时 间敏感流进行路由调度； 确定模块， 被配置为基于配置的时间敏感流的全局网路拓扑结构确定簇内每个时间敏 感流在所述全局网路拓扑 结构上路由调度的约束条件； 求解模块， 被配置为使用线性规划问题处理方式， 利用优化器求解得到时间敏感流的 输出链路信息以及在该输出链路上 的开始传输时间信息； 其中， 所述线性规划问题的优化 目标为最小化时间敏感流的端到端时延和路由数目； 配置模块， 被配置为根据所述输出链路信 息以及在该输出链路上的开始传输时间信 息 配置所述全局网路拓扑 结构中的交换机节点。 8.一种电子设备， 其特征在于， 包括存储器和 处理器； 其中， 所述存储器用于存储一条 或多条计算机指令， 其中， 所述一条或多条计算机指令被所述处理器执行以实现权利要求 1‑6任一项所述的方法步骤。 9.一种可读存储介质， 其上存储有计算机指令， 其特征在于， 该计算机指令被处理器执 行时实现权利要求1 ‑6任一项所述的方法步骤。权　利　要　求　书 2/2 页 3 CN 113032938 B 3