孫敏銘，張 棟

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

0 引言

軟件定義網(wǎng)絡(luò)(software-defined networking，SDN)作為一種新型網(wǎng)絡(luò)架構(gòu)，將控制平面與數(shù)據(jù)平面相分離，成為網(wǎng)絡(luò)發(fā)展的重要趨勢之一[1].SDN控制平面負(fù)責(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ò)存在諸多負(fù)載限制，若干研究提出以分布式多控制器的SDN控制平面架構(gòu)來提升網(wǎng)絡(luò)魯棒性.

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

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

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

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

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

2 控制森林問題模型

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

2.1 單生成樹

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

(1)

(2)

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

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

(3)

2.2 控制森林

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

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

圖2 控制森林Fig.2 Control forest

(4)

(5)

(6)

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

(7)

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

(8)

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

minw(F)

(9)

約束條件為：

(10)

(11)

(12)

(13)

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

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

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

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

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

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

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

3.2 負(fù)載調(diào)整

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

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

3.3 可靠性調(diào)整

在可靠性調(diào)整階段，CTPS算法根據(jù)當(dāng)前的權(quán)重修改森林中節(jié)點(diǎn)的父節(jié)點(diǎn).首先,按照節(jié)點(diǎn)到控制器的距離升序排序節(jié)點(diǎn)；之后，對每一個節(jié)點(diǎn)進(jìn)行啟發(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é)點(diǎn)按照節(jié)點(diǎn)到控制器的距離升序排序; ② 對序列中的所有節(jié)點(diǎn), ?i∈VF: 如果存在一個i的非父非子孫鄰居節(jié)點(diǎn)j, 使得當(dāng)i成為j子節(jié)點(diǎn)后, 滿足Γ(Fcurrent)>Γ(F), 則置j為i的父節(jié)點(diǎn); ③ 重復(fù)②直到w(temp_F)不再減少; ④ 返回當(dāng)前控制森林F

4 實(shí)驗(yàn)與結(jié)果

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

4.2 實(shí)驗(yàn)結(jié)果

圖3～4是兩種算法在兩種放置方法下，控制器從3個增加到6個時的森林權(quán)重的統(tǒng)計(jì)結(jié)果，其中，控制器負(fù)載上限Lr設(shè)置為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù).從實(shí)驗(yàn)結(jié)果可知，隨著控制器數(shù)量的增加，w(F)下降.對于節(jié)點(diǎn)數(shù)量較少的AboveNet，當(dāng)控制器的數(shù)量為5個時，CTPS算法構(gòu)造的控制森林中只有一個葉節(jié)點(diǎn)未被保護(hù)，w(F)=1；而GSA算法構(gòu)造的森林在兩種放置的場景下w(F)分別是3和5，并且GSA算法需要6個控制器才能將權(quán)重下降到1.這是因?yàn)镃TPS算法根據(jù)w(F)為每個節(jié)點(diǎn)選擇控制器，而不是根據(jù)就近原則來選擇；CTPS算法會將一些無法被保護(hù)的節(jié)點(diǎn)的子孫節(jié)點(diǎn)移到其他控制樹，可以大量減少其數(shù)量，即減少節(jié)點(diǎn)的權(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)計(jì)結(jié)果，其中，控制器負(fù)載上限Lr設(shè)置為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù).在控制器數(shù)量為3個時，CTPS生成的控制森林的平均長度比GSA的平均長度分別高出了6.25%及13.41%左右，這是由于CTPS算法可以將子孫節(jié)點(diǎn)連接到更遠(yuǎn)的控制器來提升可靠性.并且，平均長度的差距會隨著控制器數(shù)量的增加而減少.

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

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

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

圖7是AboveNet中兩種算法在兩種放置方法下，Lr分別為14，16，18，20，22個交換機(jī)時控制森林w(F)的統(tǒng)計(jì)結(jié)果.顯然，隨著Lr的增加，兩種算法生成的森林的w(F)均有一定程度的下降.然而，實(shí)驗(yàn)結(jié)果表明，CTPS算法對控制器的負(fù)載更加敏感,當(dāng)Lr上升到22個時，w(F)下降到了原先的31%，而GSA只下降了50%左右.甚至，在基于最小平均時延的控制器放置方案下，GSA的效果只提升14.29%.這種差距是由于GSA算法基于靜態(tài)的控制域分配，無法調(diào)整節(jié)點(diǎn)所在的生成樹，使得一些權(quán)重較大的節(jié)點(diǎn)因?yàn)檎也坏綕M足負(fù)載約束的保護(hù)控制器而無法被保護(hù)造成的.

5 結(jié)語

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