[發明專利]一種基于SDN的路由路徑選擇方法、裝置及存儲介質

在審

• 申請號: 202310016324.3
• 申請日: 2023-01-06
• 公開（公告）號: CN116192746A
• 公開（公告）日: 2023-05-30
• 發明（設計）人: 郭建章;周偉;彭志婷;徐峰;卞國震;王俊;馬冬松
• 申請（專利權）人: 中電信數智科技有限公司
• 主分類號: H04L45/76
• 分類號: H04L45/76;H04L45/02;H04L45/12;H04L45/302;H04L45/74;H04L45/00
• 代理公司: 北京知匯林知識產權代理事務所(普通合伙) 11794
• 代理人: 王俊杰

1.一種基于SDN的路由路徑選擇方法，用于SDN應用程序，其特征在于，包括以下步驟：

S1，通過轉送自治系統網絡模型，獲取統計數據；

S2，根據最優路由路徑選擇算法，計算每個流到達時最佳QoS的路由路徑。

2.如權利要求1所述基于SDN的路由路徑選擇方法，其特征在于，所述S1中的轉送自治系統網絡模型具體指：由ONOSSDN控制器根據OpenFlow?SBI學習路由收集的統計數據，定期計算每個鏈路的剩余帶寬和IP包錯誤率的特征，生成所需的統計數據。

3.如權利要求1所述基于SDN的路由路徑選擇方法，其特征在于，所述S2中的最優路由路徑選擇算法的具體步驟包括：

S21，對整數線性規劃ILP進行預處理；

S22，采用分支定界法，刪除冗余變量約束和減小問題規模；

S23，將整數變量轉換為連續變量，其中是從i到j的鏈路；

S24，在求解最優松弛模型的基礎上，采用Gomory切割平面算法對松弛問題進行重復改進，直到達到整數解或找不到新的切割平面；

S25，得出路由路徑最優解。

4.如權利要求3所述基于SDN的路由路徑選擇方法，其特征在于，所述S21中的整數線性規劃是由SD-WAN網絡中轉自治系統的路由優化問題公式化得出。

5.如權利要求3所述基于SDN的路由路徑選擇方法，其特征在于：所述S21中預處理過程指從鏈路集合L中選擇并刪除一個問題q^l，并解出其松弛形式q^-l。

6.如權利要求3所述基于SDN的路由路徑選擇方法，其特征在于，所述S22中分支定界法處理的具體步驟包括：

步驟1，當各分支的最優目標函數中若分支小于下界，則剪掉這支，若分支大于下界，但不符合整數條件，則深入這支重新進行分支，定界；

步驟2，通過不斷縮小可行域，最終求到最優解。

7.如權利要求3所述基于SDN的路由路徑選擇方法，其特征在于，所述S24中的Gomory切割平面算法的具體步驟包括：

步驟1，將路由問題看作整數規劃問題，并表示為min{c^Tx:Ax＝b,x∈Zⁿ}，

其中，c^T指約束C的轉置矩陣，A、b分別為等式約束中的系數矩陣，x為基變量，Zⁿ是變量的取值集合；

步驟2，使用單純形法對線性松弛問題進行求解得到：

公式1：

其中，為基本變量，u為整數，取值為1到n，NB是非基變量的集合，為基向量，x_j為非基本變量，為非基向量；

步驟3，一般由此線性規劃得到的最優解一定不是整數，即存在某些值讓非基向量又由可以得到一個不等式成立：

公式2：

其中，和的范圍都為[0,1)，a_i是平面上的點；

步驟4，將公式2帶入到公式1中可以得到：

公式3：

步驟5，根據公式1和公式3可得到；

公式4：

步驟6，進一步驗證線性松弛問題的最優解中的非基變量部分滿足x_j＝0,j∈NB，此最優解不滿足上述約束公式4，故在原線性松弛問題中添加公式4作為約束以切割最優解，重新求解多出一個限制的線性規劃問題。

8.如權利要求3所述基于SDN的路由路徑選擇方法，其特征在于，所述S24中的改進具體指：在線性規劃中添加新的線性約束，消除分式解，同時確保已經生成的整數解不被消除。

9.一種基于SDN的路由路徑選擇裝置，其特征在于，包括獲取模塊和處理模塊：

獲取模塊：通過轉送自治系統網絡模型，獲取統計數據；

處理模塊：用于根據最優路由路徑選擇算法，計算每個流到達時最佳QoS的路由路徑。

10.一種計算機可讀存儲介質，用于存儲SDN應用程序，其特征在于，所述SDN應用程序被處理器執行時實現如權利要求1至8中任一項所述的基于SDN的路由路徑選擇方法。