分布式SDN控制平面下可靠的控制流傳輸路徑選擇

孫敏銘，張 棟

(福州大學數學與計算機科學學院，福建 福州 350108)

0 引言

軟件定義網絡(software-defined networking，SDN)作為一種新型網絡架構，將控制平面與數據平面相分離，成為網絡發展的重要趨勢之一[1].SDN控制平面負責做出適當決策以滿足多變的網絡需求；SDN數據平面根據控制平面下發的流表轉發數據包.集中控制的特性使SDN比傳統網絡更加靈活高效地管理網絡,但由于單控制器的SDN網絡存在諸多負載限制，若干研究提出以分布式多控制器的SDN控制平面架構來提升網絡魯棒性.

分布式SDN控制平面[2-3]及控制器放置問題(controller placement problem，CPP)[4]已經有系列研究，但較少考慮分布式控制平面下控制器與交換機間的控制流傳輸路徑選擇.現有研究通常默認交換機到控制器的最短路徑作為控制流的傳輸路徑，而忽略傳輸路徑的可靠性對SDN性能的影響[5].特別是在In-Band控制平面下，控制流傳輸路徑的可靠性非常重要，網絡故障將導致大量交換機的控制流無法被正常轉發，進而影響SDN網絡正常運行.

現有的控制流路徑研究主要分為兩類： 一是基于交換機本地的切換機制，二是在基于全局拓撲的控制流路徑選擇.第一類研究專注于在單個SDN交換機上實現各類機制來選擇控制流路徑,這類機制僅考慮本地環境，可能導致控制流環路甚至網絡級聯故障.第二類研究則是根據物理拓撲，為網絡中每個交換機選擇控制流的傳輸路徑.文獻[6]提出構造以控制器為根的生成樹用于轉發控制流，樹中的其他節點是網絡中的交換機節點，樹的枝干用于傳輸交換機節點的控制流.在此基礎上，文獻[7]提出在分布式SDN控制平面中為每個控制器構造生成樹.然而，該方法是基于靜態的控制域劃分，每個生成樹在相應的控制域內單獨計算，使算法無法找到最優的生成樹.本研究針對上述問題，詳盡地分析了分布式SDN控制平面下的控制流傳輸保護機制，并提出一種動態構造多生成樹的算法.在該算法中，根據控制流傳輸的可靠性要求為每個控制器構造生成樹并劃分控制域，以避免靜態控制域導致的控制流傳輸可靠性下降.

本研究將分布式SDN控制平面構造可靠的生成樹問題定義為控制森林構造問題(control forest construction problem,CFCP),即對給定的網絡及控制器放置，為每個交換機選擇控制流的路徑以提升傳輸的可靠性及容錯性.同時，針對CFCP提出了控制流路徑選擇算法(control traffic paths selection,CTPS)，該算法基于廣度優先搜索，從控制器節點出發，為每個交換機節點搜索適當的父節點，并在搜索結束后進行啟發式的調整以獲得近似最優解.實驗結果表明,CTPS能夠有效提高控制流傳輸的可靠性.

1 控制流路徑相關問題概述

近年來，隨著SDN的流行，SDN控制流路徑的選擇受到廣泛關注.文獻[8]設計了帶寬感知的控制流本地重路由機制，在原轉發端口帶寬剩余不足的情況下選擇剩余帶寬最多的本地端口轉發控制流.文獻[9]提出在In-Band控制平面中使用MPTCP，同時選擇多條不相交的路徑來轉發控制流，提升控制流傳輸的容錯性.文獻[10]設計了一種動態的控制平面，能夠在控制器或某個控制流路徑負載過大時，為控制流重新分配傳輸路徑.然而，該機制需要較大的通信與計算開銷，從而影響網絡的響應時間.文獻[6]提出基于快速故障恢復的生成樹，當某個交換機故障時，其子交換機節點可利用預配置的非樹鏈路來進行快速重路由，確保其父節點故障時能快速恢復下游交換機節點的控制流，提高控制流傳輸的可靠性.文獻[11]建立了生成樹構造問題的整數線性規劃模型(integer linear programming,ILP).在此基礎上，文獻[12]提出了啟發式的DDOT算法，該算法通過啟發式修改樹中交換機節點的位置來尋找最優的生成樹.但是，該算法仍然只針對單個控制器.與單生成樹構造不同，文獻[7]提出多生成樹構造算法GSA，該算法基于每個控制域中的最小生成樹.然而，GSA算法僅將分布式控制平面劃分為若干個控制域，在每個控制域中構造生成樹，沒有考慮域間鄰居節點及鏈路對可靠性的影響.

2 控制森林問題模型

可靠的控制流傳輸路徑選擇問題目標在于盡可能為每個交換機節點選擇一條可靠的路徑來傳輸控制流，以保證在底層網絡故障時，交換機能夠重路由控制流來保持與控制平面的連接.

2.1 單生成樹

圖1 單控制器的生成樹Fig.1 A spanning tree rooted at single controller

(1)

(2)

其中: 變量yij=1表示節點i被節點j簡單保護或兄弟保護,否則yij=0; 變量sij=1表示節點i與節點j是兄弟節點,否則sij=0.

由于生成樹的存在，當節點A被保護時，其子孫節點的控制流不會因節點A的父節點故障而受影響.當發生故障時，節點A能快速重路由自身及子孫節點的控制流到其他節點，比如圖1中的S8能夠將控制流重路由到S7，從而保護控制流傳輸不會中斷.另一方面，當節點A不是被保護節點時，無論其子孫節點是否被保護，都將因節點A的父節點的故障而失去與控制器的連接.因此，將一個節點i的權重wi定義為以節點i為根的子樹中的節點數量，表示為：

(3)

2.2 控制森林

分布式SDN控制平面需要多個生成樹來轉發各個控制域的控制流，將這樣的多個生成樹的集合稱為控制森林F=(Vf,Ef).其中,Vf表示SDN網絡中數據平面的交換機節點的集合，Ef表示控制森林中邊的集合.另外，用集合R表示控制器放置節點的集合，即R?V.使用mir=1表示交換機節點i由放置在節點r控制器管理，即交換機節點i是以r為根的生成樹中的一個節點；否則，mir=0.

如圖2所示，控制器C1和C2是控制森林中的兩個控制器.在圖2(a)中S7連接到控制器C1,若S7的父節點S8故障，S7因缺少非樹鏈路重路由控制流導致其將與C1失去連接，即S7是一個不被保護的節點.而在圖2(b)中，S7連接到C2，因此能夠被S3保護.

圖2 控制森林Fig.2 Control forest

(4)

(5)

(6)

在保護機制的基礎上，通過定義控制森林的權重來衡量分布式SDN控制平面下的控制流傳輸可靠性.對于給定的控制森林F的權重w(F)定義為：

(7)

其中:pi可以根據下式計算：

(8)

因此，根據上述的定義，控制森林構造問題的目標函數為：

minw(F)

(9)

約束條件為：

(10)

(11)

(12)

(13)

約束(10)表示每個交換機節點只能被一臺控制器管理；約束(11)表示控制森林中一共有N-C；約束(12)表示除根節點外,其余所有節點均有一個父節點；約束(13)表示控制器的負載不能超過其上限.

3 控制森林構造算法

本研究提出的CTPS算法分為3個階段： 初始森林構造、負載調整以及可靠性調整.初始森林構造階段根據網絡底層拓撲構造初始的生成樹；負載調整階段將調整樹結構以確保每個控制器的負載不會超過上限；最后可靠性調整階段啟發式修改森林中節點的父節點，尋找更優的控制森林.與現有的生成森林構建算法GSA[7]不同，CTPS在構造初始森林及可靠性調整時不止考慮域內節點，而是考慮所有的鄰居節點.同時，由于CTPS不是基于靜態的控制域劃分，因此，加入負載調整階段以確保初始森林的控制器不會過載.

3.1 初始森林構建

CTPS算法的初始森林構建階段基于廣度搜索,該階段如算法1所示，從根節點開始，每輪搜索均會將隊列中節點的鄰居加入相應的隊列并設為其子節點.同時，為避免出現某個節點沒有非樹鏈路可用的情況，在連接節點到森林時考慮了父節點的連接情況： 若節點A只剩下一條非樹鏈路，則不會將A設置為任何節點的父節點.廣度搜索結束后再將未加入森林的節點根據其鄰居節點情況加入控制森林.

算法1 初始森林構造輸入: 網絡拓撲圖G=(V, E); 控制器放置位置Θ;輸出: 初始森林F; 1) 為每個根節點r創建一個隊列, 將r壓入隊列; 2) 依次將每個隊列中的節點壓出, 檢查每個壓出的節點i的所有鄰居節點j:

算法1 初始森林構造 如果j還未加入森林, 且i存在兩條以上的非樹鏈路, 則將i置為j的父節點, 將j壓入i的原隊列, 否則, 不操作; 3) 重復2), 直到所有隊列為空; 4) 隨機選擇一個未加入森林的節點i, 選擇i的鄰居中樹高最小的節點j作為i父節點, 5) 對于剩余未加入森林的節點: 如果節點i有一個被保護的鄰居節點j, 則將j置為i父節點; 否則, 不操作; 6) 重復4)～5), 直到所有節點均加入森林; 7) 返回初始森林F

3.2 負載調整

考慮到控制器的負載問題，算法需要調整森林的結構防止控制平面過載.首先檢查森林中是否有生成樹的節點過多，超過控制器的負載限制；若存在，按樹中節點到根的距離降序排列節點，并嘗試將該樹中的節點加入其他生成樹，直到所有控制器管理的交換機均沒超過Lr.按降序排序節點是為盡可能調整少量節點來避免其他控制器超負載.該階段如算法2所示:

算法2 負載調整 Ⅰ) 將temp_F中所有節點按照節點到控制器的距離降序排序; Ⅱ) 如果控制器r管理的節點超出了Lr, 則按序處理r管理的節點, ?i∈{mir=1}: 如果節點i有一個鄰居節點j由控制器r1管理且Lrr1i=1, 那么將j置為i的父節點, 否則, 處理序列中下一個節點; Ⅲ) 重復Ⅱ), 直到所有控制器的負載都沒有超過Lr;Ⅴ) 返回temp_F

3.3 可靠性調整

在可靠性調整階段，CTPS算法根據當前的權重修改森林中節點的父節點.首先,按照節點到控制器的距離升序排序節點；之后，對每一個節點進行啟發式調整；最后，選擇其中最優的控制森林.該階段如算法3所示，在算法3中Γ(F1)>Γ(F)表示森林F1權重小于F權重，或兩個權重相等且森林F1的平均高度小于F；Fcurrent表示修改后的控制森林.

算法3 可靠性調整① 將temp_F中所有節點按照節點到控制器的距離升序排序; ② 對序列中的所有節點, ?i∈VF: 如果存在一個i的非父非子孫鄰居節點j, 使得當i成為j子節點后, 滿足Γ(Fcurrent)>Γ(F), 則置j為i的父節點; ③ 重復②直到w(temp_F)不再減少; ④ 返回當前控制森林F

4 實驗與結果

4.1 實驗參數設置

本研究采用2個真實的物理拓撲[13]進行實驗： AboveNet和PionierL3.其中,AboveNet有23個節點，31條邊；PionierL3有38個節點，53條邊.將提出的CTPS算法與文獻[7]的GSA比較,實驗中的控制器位置則是根據最小平均時延及最小最大時延放置[14]，即CTPS與GSA分別以兩種控制器放置位置為輸入構造控制森林.

4.2 實驗結果

圖3～4是兩種算法在兩種放置方法下，控制器從3個增加到6個時的森林權重的統計結果，其中，控制器負載上限Lr設置為網絡中的節點數.從實驗結果可知，隨著控制器數量的增加，w(F)下降.對于節點數量較少的AboveNet，當控制器的數量為5個時，CTPS算法構造的控制森林中只有一個葉節點未被保護，w(F)=1；而GSA算法構造的森林在兩種放置的場景下w(F)分別是3和5，并且GSA算法需要6個控制器才能將權重下降到1.這是因為CTPS算法根據w(F)為每個節點選擇控制器，而不是根據就近原則來選擇；CTPS算法會將一些無法被保護的節點的子孫節點移到其他控制樹，可以大量減少其數量，即減少節點的權重，從而降低w(F)，提高可靠性.

圖3 AboveNet中可靠性對比 Fig.3 Reliability comparison in AboveNet

圖4 PionierL3中可靠性對比Fig.4 Reliability comparison in PionierL3

圖5～6是兩種算法在兩種放置方法下，控制器從3個增加到6個時的控制流傳輸路徑平均長度的統計結果，其中，控制器負載上限Lr設置為網絡中的節點數.在控制器數量為3個時，CTPS生成的控制森林的平均長度比GSA的平均長度分別高出了6.25%及13.41%左右，這是由于CTPS算法可以將子孫節點連接到更遠的控制器來提升可靠性.并且，平均長度的差距會隨著控制器數量的增加而減少.

圖5 AbvoeNet中平均路徑長度對比Fig.5 Average path length comparison in AboveNet

圖6 PionierL3中平均路徑長度對比Fig.6 Average path length comparison in PionierL3

圖7 AbvoeNet中可靠性隨負載變化的對比Fig.7 Reliability comparison with load in AboveNet

圖7是AboveNet中兩種算法在兩種放置方法下，Lr分別為14，16，18，20，22個交換機時控制森林w(F)的統計結果.顯然，隨著Lr的增加，兩種算法生成的森林的w(F)均有一定程度的下降.然而，實驗結果表明，CTPS算法對控制器的負載更加敏感,當Lr上升到22個時，w(F)下降到了原先的31%，而GSA只下降了50%左右.甚至，在基于最小平均時延的控制器放置方案下，GSA的效果只提升14.29%.這種差距是由于GSA算法基于靜態的控制域分配，無法調整節點所在的生成樹，使得一些權重較大的節點因為找不到滿足負載約束的保護控制器而無法被保護造成的.

5 結語

本研究分析了分布式SDN控制平面下控制流傳輸路徑可靠性問題.首先分析了分布式環境下控制流傳輸的保護機制并提出了CTPS算法，該算法基于可靠性為每個節點選擇控制屏并規劃控制流的傳輸路徑.實驗表明，在控制器放置相同時，CTPS算法構造的控制森林能夠提供更可靠的控制流傳輸.同時，CTPS算法能夠更有效地利用控制器的負載來保護不同控制域中的交換機的控制流，以應對分布式控制平面中的控制器故障.