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

孫敏銘，張 棟

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

0 引言

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

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

現(xiàn)有的控制流路徑研究主要分為兩類： 一是基于交換機本地的切換機制，二是在基于全局拓撲的控制流路徑選擇.第一類研究專注于在單個SDN交換機上實現(xiàn)各類機制來選擇控制流路徑,這類機制僅考慮本地環(huán)境，可能導(dǎo)致控制流環(huán)路甚至網(wǎng)絡(luò)級聯(lián)故障.第二類研究則是根據(jù)物理拓撲，為網(wǎng)絡(luò)中每個交換機選擇控制流的傳輸路徑.文獻[6]提出構(gòu)造以控制器為根的生成樹用于轉(zhuǎn)發(fā)控制流，樹中的其他節(jié)點是網(wǎng)絡(luò)中的交換機節(jié)點，樹的枝干用于傳輸交換機節(jié)點的控制流.在此基礎(chǔ)上，文獻[7]提出在分布式SDN控制平面中為每個控制器構(gòu)造生成樹.然而，該方法是基于靜態(tài)的控制域劃分，每個生成樹在相應(yīng)的控制域內(nèi)單獨計算，使算法無法找到最優(yōu)的生成樹.本研究針對上述問題，詳盡地分析了分布式SDN控制平面下的控制流傳輸保護機制，并提出一種動態(tài)構(gòu)造多生成樹的算法.在該算法中，根據(jù)控制流傳輸?shù)目煽啃砸鬄槊總€控制器構(gòu)造生成樹并劃分控制域，以避免靜態(tài)控制域?qū)е碌目刂屏鱾鬏斂煽啃韵陆?

本研究將分布式SDN控制平面構(gòu)造可靠的生成樹問題定義為控制森林構(gòu)造問題(control forest construction problem,CFCP),即對給定的網(wǎng)絡(luò)及控制器放置，為每個交換機選擇控制流的路徑以提升傳輸?shù)目煽啃约叭蒎e性.同時，針對CFCP提出了控制流路徑選擇算法(control traffic paths selection,CTPS)，該算法基于廣度優(yōu)先搜索，從控制器節(jié)點出發(fā)，為每個交換機節(jié)點搜索適當(dāng)?shù)母腹?jié)點，并在搜索結(jié)束后進行啟發(fā)式的調(diào)整以獲得近似最優(yōu)解.實驗結(jié)果表明,CTPS能夠有效提高控制流傳輸?shù)目煽啃?

1 控制流路徑相關(guān)問題概述

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

2 控制森林問題模型

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

2.1 單生成樹

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

(1)

(2)

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

由于生成樹的存在，當(dāng)節(jié)點A被保護時，其子孫節(jié)點的控制流不會因節(jié)點A的父節(jié)點故障而受影響.當(dāng)發(fā)生故障時，節(jié)點A能快速重路由自身及子孫節(jié)點的控制流到其他節(jié)點，比如圖1中的S8能夠?qū)⒖刂屏髦芈酚傻絊7，從而保護控制流傳輸不會中斷.另一方面，當(dāng)節(jié)點A不是被保護節(jié)點時，無論其子孫節(jié)點是否被保護，都將因節(jié)點A的父節(jié)點的故障而失去與控制器的連接.因此，將一個節(jié)點i的權(quán)重wi定義為以節(jié)點i為根的子樹中的節(jié)點數(shù)量，表示為：

(3)

2.2 控制森林

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

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

圖2 控制森林Fig.2 Control forest

(4)

(5)

(6)

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

(7)

其中:pi可以根據(jù)下式計算：

(8)

因此，根據(jù)上述的定義，控制森林構(gòu)造問題的目標函數(shù)為：

minw(F)

(9)

約束條件為：

(10)

(11)

(12)

(13)

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

3 控制森林構(gòu)造算法

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

3.1 初始森林構(gòu)建

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

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

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

3.2 負載調(diào)整

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

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

3.3 可靠性調(diào)整

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

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

4 實驗與結(jié)果

4.1 實驗參數(shù)設(shè)置

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

4.2 實驗結(jié)果

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

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

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

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

圖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)的統(tǒng)計結(jié)果.顯然，隨著Lr的增加，兩種算法生成的森林的w(F)均有一定程度的下降.然而，實驗結(jié)果表明，CTPS算法對控制器的負載更加敏感,當(dāng)Lr上升到22個時，w(F)下降到了原先的31%，而GSA只下降了50%左右.甚至，在基于最小平均時延的控制器放置方案下，GSA的效果只提升14.29%.這種差距是由于GSA算法基于靜態(tài)的控制域分配，無法調(diào)整節(jié)點所在的生成樹，使得一些權(quán)重較大的節(jié)點因為找不到滿足負載約束的保護控制器而無法被保護造成的.

5 結(jié)語

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