[發明專利]一種降低管理負載開銷的SDN多控制器部署方法

在審

• 申請號: 201410291267.0
• 申請日: 2014-07-24
• 公開（公告）號: CN104065509A
• 公開（公告）日: 2014-09-24
• 發明（設計）人: 李克秋;陸駿;齊恒;喻海生
• 申請（專利權）人: 大連理工大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 李寶元;梅洪玉

1.一種降低管理負載開銷的SDN多控制器部署方法，其特征在于以下步驟：

(一)分析網絡拓撲結構

a.分析網絡的拓撲結構，將多控制器部署問題抽象化為一個圖論問題，即將整個網絡抽象為一個無向圖；

b.提出一種新的度量，用來反映控制器管理負載，管理負載主要包括控制器處理請求的代價和安裝規則的代價等，并以此作為決策變量；

(二)構建相關數學模型

控制器的管理負載作為決策變量；由決策變量和所要達到目的之間的函數關系確定目標函數；根據決策變量以及最終目標確定將最小化管理負載作為目標函數；由決策變量所受的限制條件確定決策變量所要滿足的約束條件；將滿足一定閥值的網絡延遲以及有限的控制器的處理能力作為約束條件；

將多控制器部署問題抽象化為一個圖論問題，然后在給定的k個控制器中選擇控制器，并將這些控制器與圖中的交換機相連接；假設整個網絡抽象為拓撲圖G，S為網絡中交換機的集合，C為網絡中控制器的集合，設定單位時間內從網絡中交換機i轉發到控制器的流數為f_i，設流在交換機i與控制器j之間的最短路徑上的傳播代價為d_ij，那么由此得到該優化問題的目標函數為minΣ_i∈SΣ_j∈Cf_ix_ijd_ij，其中x_ij表示交換機i與控制器j是否相連接；對于該多控制器部署優化問題，目標就是在k個控制器中選取合適數量的控制器，從而使得網絡中使用的控制器的管理負載最小；

設定一個閥值為δ，要求對于和，都有x_ijd_ij≤δ即要求網絡延遲的值不大于該閥值；引入控制器能力描述，定義U＝<u_i,u₂,…u_|C|>為控制器單位時間內的處理能力向量，那么u_j就是控制器j單位時間內所能處理的最大請求數量，得對于，要求滿足Σ_i∈Sx_ijf_i≤y_ju_j，其中y_j表示控制器j是否連入網絡中并處于激活狀態；

(三)近似算法的選取及求解

a.根據0-1整數規劃的線性規劃的松弛，把每個變量必須為0或1的約束，替換為較弱的每個變量屬于區間[0,1]的約束；把NP難的最優化問題轉化為一個相關的多項式時間可解的問題，然后對松弛后的線性規劃進行求解；

b.針對松弛后的線性規劃，求得其對偶規劃maxΣ_i∈Sα_i-γδ-bk，γ、b為任意常數且滿足γ,b≥0；選取近似度達到3的近似算法對該對偶規劃求解；

c.由對偶規劃可得，圖中每個交換機的對偶變量α_i不斷增長直到當該交換機與某個控制器相連時保持不變；初始狀態，每一個交換機處于未連接狀態；對偶變量α_i增長，當圖中某些邊(i,j)達到α_i＝f_id_ij+γd_ij+af_i時，算法申明該邊是“不可行邊”；當對偶變量β_ij滿足β_ij>0時，申明該邊是“可行邊”；同樣地，當邊(i,j)是可行邊時，申明交換機i是連接的，控制器j處于激活狀態；對于控制器j，如果滿足Σ_i∈Sβ_ij＝b-au_j，則申明該控制器暫時處于激活狀態；同時，所有與該控制器之間存在不可行邊的交換機變為連接的，申明該控制器為這些交換機的“偽控制器”；接下來，令C_t表示暫時處于激活狀態的控制器的集合，包含所有可行邊的子圖G₁以及滿足交換機與控制器之間邊數之多為2的子圖G₂；最終目標就是尋找最大的獨立集合，滿足，為G₂的子圖，使得在集合中的所有控制器都處于激活狀態。