[發明專利]時間敏感流的路由調度方法、裝置、電子設備及介質

有效

• 申請號: 202110350933.3
• 申請日: 2021-03-31
• 公開（公告）號: CN113032938B
• 公開（公告）日: 2022-07-08
• 發明（設計）人: 鄭偉;李聰;章晨宇;王正英;路兆銘;溫向明
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06F30/18
• 分類號: G06F30/18;G06F30/27;G06K9/62;G06N20/00;G06F111/02;G06F111/04;G06F119/12
• 代理公司: 北京智信四方知識產權代理有限公司 11519
• 代理人: 黃健;葛啟宏

本公開實施例公開了一種時間敏感流的路由調度方法、裝置、電子設備及介質。所述方法包括：利用譜聚類算法聚類K個時間敏感流得到N個簇；根據簇內時間敏感流的相似度對簇排序；基于配置的時間敏感流的全局網路拓撲結構確定簇內每個時間敏感流在所述全局網路拓撲結構上路由調度的約束條件；利用優化器求解得到時間敏感流的輸出鏈路信息以及在該輸出鏈路上的開始傳輸時間信息。該技術方案通過對時間敏感流分簇，并根據簇的順序進行路由調度，并通過對每個簇內時間敏感流確定約束條件，進而將調度問題轉化為線性規劃問題進行求解，簡化了時間敏感流的路由調度問題，提高了計算效率，從而可以適應于動態業務需求。

技術領域

本公開涉及網絡通信技術領域，具體涉及一種時間敏感流的路由調度方法、裝置、電子設備及介質。

背景技術

時間敏感網絡(TSN：Time Sensitive Networking)消除了標準以太網中由于流“擁堵”導致的不確定性，為標準以太網增加了確定性和可靠性；允許時間緊迫和盡力而為流在同一網絡上共存，從而節省了成本并保留了向后兼容性。在IEEE802.1Qbv中定義了對計劃流調度的增強機制，即網絡部署之前，根據實時流的時序參數和網絡結構生成靜態調度表，交換機根據預先計算的門控列表(GCL：Gate Control List)對實時流進行調度以實現確定性、低延遲和低抖動通信。盡管該協議能夠解決確定性和低時延的問題，但是卻沒有解決GCL的計算問題。在TSN中由GCL合成引起的調度問題是NP-hard的，由于調度問題的復雜性，通常離線計算端口的GCL來進行調度，這種計算方式在網絡配置發生變化時無法快速的響應，不適用于時間敏感網絡動態變化的流量調度場景。

發明內容

為了解決相關技術中的問題，本公開實施例提供一種時間敏感流的路由調度方法、裝置、電子設備及介質。

第一方面，本公開實施例中提供了一種時間敏感流的路由調度方法。

具體地，所述時間敏感流的路由調度方法，包括：

利用譜聚類算法聚類K個時間敏感流得到N個簇，其中，K個時間敏感流兩兩間的相似度根據時間敏感流的屬性特征計算得到，所述屬性特征包括：基于源節點及目的節點確定的路由路徑數量、傳輸時長以及流量周期；

根據簇內時間敏感流的相似度對簇排序，并按照簇的排序對K個時間敏感流進行路由調度；

基于配置的時間敏感流的全局網路拓撲結構確定簇內每個時間敏感流在所述全局網路拓撲結構上路由調度的約束條件；

使用線性規劃問題處理方式，利用優化器求解得到時間敏感流的輸出鏈路信息以及在該輸出鏈路上的開始傳輸時間信息；其中，所述線性規劃問題的優化目標為最小化時間敏感流的端到端時延和路由數目；

根據所述輸出鏈路信息以及在該輸出鏈路上的開始傳輸時間信息配置所述全局網路拓撲結構中的交換機節點。

可選地，所述基于配置的時間敏感流的全局網路拓撲結構確定簇內每個時間敏感流在所述全局網路拓撲結構上路由調度的約束條件，包括：

裁剪時間敏感流的全局網路拓撲結構中的冗余鏈路，得到簡化網絡；

基于所述簡化網絡確定簇內每個時間敏感流在所述全局網路拓撲結構上路由調度的約束條件。

可選地，所述約束條件至少包括：沖突避免約束、時延約束、實時性約束以及鏈路傳輸約束。

可選地，所述時間敏感流兩兩間的相似度為：

其中，R_i和R_j分別表示了時間敏感流i和j使用的路徑集合，||表示路徑集合中元素的個數，t_i和t_j分別表示了時間敏感流i和j的傳輸時長，P_i和P_j分別表示了時間敏感流i和j的流量周期。