林亞飛 劉惠臨

（安徽理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001）

1 引言

軟件定義網(wǎng)絡(luò)(Software-Defined Networking,簡稱SDN)架構(gòu)中數(shù)據(jù)層與控制層相互分離，交換機(jī)的控制策略由控制器負(fù)責(zé)，數(shù)據(jù)層僅需根據(jù)控制器下發(fā)的控制策略進(jìn)行數(shù)據(jù)包的轉(zhuǎn)發(fā)。OpenFlow允許一個交換機(jī)同時與多個控制器相連，當(dāng)主控制器出現(xiàn)故障時，可通過一定的選舉規(guī)則選舉出一個新的主控制器，使得網(wǎng)絡(luò)正常運(yùn)行。

2 路由框架探討

SDN網(wǎng)絡(luò)能夠可以解決傳統(tǒng)的網(wǎng)絡(luò)架構(gòu)所面臨的問題，如OTT業(yè)務(wù)沖擊、網(wǎng)絡(luò)架構(gòu)不靈活、信息重復(fù)傳輸率高等，同時對網(wǎng)絡(luò)的信息資源和網(wǎng)絡(luò)資源的使用靈活高效，且與目前的互聯(lián)網(wǎng)兼容。隨著互聯(lián)網(wǎng)功能要求和業(yè)務(wù)需求的增加，網(wǎng)絡(luò)中間設(shè)備承擔(dān)了更多的職責(zé)，使得封裝在設(shè)備內(nèi)部的網(wǎng)絡(luò)協(xié)議越來越復(fù)雜,設(shè)備成本也急劇增加。而在OpenFlow網(wǎng)絡(luò)中，為了提高對流的控制能力，OpenFlow交換機(jī)提供了從物理層的物理接口到傳輸層的邏輯端口之間的全部參數(shù)，并據(jù)此進(jìn)行數(shù)據(jù)包的轉(zhuǎn)發(fā)。我們對網(wǎng)絡(luò)數(shù)據(jù)流量采用集中式?jīng)Q策的方式。一個OpenFlow控制器通過控制多臺Open-Flow交換機(jī)來共同完成對流的轉(zhuǎn)發(fā)。OpenFlow主控制器能夠獲取整個網(wǎng)絡(luò)的鏈路狀況、網(wǎng)絡(luò)拓?fù)?、網(wǎng)絡(luò)流量等信息，實(shí)現(xiàn)精確的控制和優(yōu)化整個網(wǎng)絡(luò)的運(yùn)行狀況。從而，傳統(tǒng)網(wǎng)絡(luò)架構(gòu)中存在的一些路由協(xié)議問題在這種集中式控制的架構(gòu)下能夠得到很好的解決。

3 路由算法設(shè)計

交由OpenFlow交換機(jī)處理的數(shù)據(jù)包有三種∶⑴Open-Flow網(wǎng)段內(nèi)傳輸?shù)臄?shù)據(jù)包；⑵來自于傳統(tǒng)路由器的數(shù)據(jù)包；⑶OpenFlow網(wǎng)段間轉(zhuǎn)發(fā)的數(shù)據(jù)包。第三種情況下,要應(yīng)用OpenFlow路由組件對數(shù)據(jù)包進(jìn)行路由查詢和轉(zhuǎn)發(fā)。如圖1為Openflow網(wǎng)絡(luò)結(jié)構(gòu)示意圖。

圖1 OpenFlow網(wǎng)絡(luò)結(jié)構(gòu)示意圖

對數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)時，我們需選取最優(yōu)路徑來節(jié)省時間，提高工作效率。Dijkstra算法是從一個頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，能夠解決有向圖中的最短路徑問題。計算時以起始點(diǎn)為中心向按路徑由小至大擴(kuò)展直到終點(diǎn)。具體思想為：設(shè)G=(V,E)是一個帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成已知最短路徑的頂點(diǎn)集合（A）和未知最短路徑的頂點(diǎn)集合（B），按最短路徑從小到大的順序依次把B中的頂點(diǎn)加入A中。在加入過程中，要保證從原點(diǎn)v到已知頂點(diǎn)（A）的最短路徑長度不得大于從原點(diǎn)v到任一未知頂點(diǎn)（B）的最短路徑長度。

具體步驟如下：

（1）初始時，A集合中只有原點(diǎn)，即A＝{s}，s的距離為0。B包含除v外的所有頂點(diǎn)，b的距離有兩種情況：一種情況是b與v有邊，b的距離為該邊的權(quán)值；另一種情況是b不是v的出邊鄰接點(diǎn)，b的距離為∞。

（2）從B中選取與v距離最短的頂點(diǎn)n，把n加入A中(此時n的最短路徑長度已知即該頂點(diǎn)到v的距離）。

（3）以n作為新的中間節(jié)點(diǎn)，更新B中各頂點(diǎn)的距離；若經(jīng)過節(jié)點(diǎn)n的距離值比未經(jīng)過n時的距離值小，則更新頂點(diǎn)b的距離值(為n的距離+邊上權(quán)值)。

（4）重復(fù)步驟（2）和（3）直到A中包含全部節(jié)點(diǎn)。

圖2 Dijkstra算法圖

Dijkstra算法采用對節(jié)點(diǎn)的多次遍歷的方法來求得最短路徑的最優(yōu)解，要遍歷節(jié)點(diǎn)的數(shù)目較多，搜索速度慢，算法執(zhí)行效率低，因此我們需要進(jìn)一步優(yōu)化最短路徑算法。

4 路由算法優(yōu)化

4.1 算法優(yōu)化思想

本文通過改進(jìn)算法的數(shù)據(jù)存儲結(jié)構(gòu)來優(yōu)化經(jīng)典的Dijkstra算法，采用java中提供的Hashtable類（散列類）存儲節(jié)點(diǎn)信息。在搜索之前對所有節(jié)點(diǎn)的Hashtable對象進(jìn)行排序，這樣在每次搜索最小權(quán)值的節(jié)點(diǎn)時不用對所有節(jié)點(diǎn)進(jìn)行掃描。將每次搜索到的最小權(quán)值節(jié)點(diǎn)作為下次搜索的起點(diǎn)，每搜索一次對堆棧結(jié)構(gòu)進(jìn)行一次維護(hù)從而避免重復(fù)訪問同一個節(jié)點(diǎn)。

4.2 算法優(yōu)化實(shí)現(xiàn)

4.2.1 存儲結(jié)構(gòu)定義

pVector：用于存儲集合V-S中的節(jié)點(diǎn)(按節(jié)點(diǎn)直接前驅(qū)節(jié)點(diǎn)的編號順序存放)。

stVector：用于存儲最短路徑節(jié)點(diǎn)列表。

stHash：用于存儲從起點(diǎn)s到終點(diǎn)v的所有最短路徑。

nVector：用于存儲與原點(diǎn)相鄰但還沒有被訪問過的節(jié)點(diǎn)列表。

gHash：用于存儲出度大于零的節(jié)點(diǎn)。

bHash：用于存儲與gHash中每個節(jié)點(diǎn)元素相對應(yīng)的相鄰節(jié)點(diǎn)列表。

4.2.2 算法實(shí)現(xiàn)步驟

（1）初始化：將起點(diǎn)S到終點(diǎn)V的最短路徑d設(shè)為所允許的最大值，起點(diǎn)S到其它所有節(jié)點(diǎn)的最短距離D設(shè)為所允許的最大值，起點(diǎn)的節(jié)點(diǎn)編號k，所有節(jié)點(diǎn)的權(quán)值H[k,i]均置為0，并將該節(jié)點(diǎn)壓入stHash和gHash棧（pVector中的節(jié)點(diǎn)按直接前趨節(jié)點(diǎn)編號為索引進(jìn)行排序）。

（2）最短距離節(jié)點(diǎn)搜索：取出gHash棧頂元素i，搜索與之相通的節(jié)點(diǎn)中權(quán)值最小的弧，并將k放入最短路徑點(diǎn)列表stVector中，直到gHash?？?。

（3）最短路徑修改∶當(dāng)p為目標(biāo)節(jié)點(diǎn)時，即搜索到了一條最短路徑，將這條最短路徑的節(jié)點(diǎn)列表stVector加入最短路徑列表stHash中，若d＞D[p]，則修改最短路徑為d=D[p]，記s為該stVector所對應(yīng)的關(guān)鍵字key，令p=k，轉(zhuǎn)步驟（5）；當(dāng)p為非目標(biāo)節(jié)點(diǎn)時，轉(zhuǎn)步驟（4）。

（4）更新搜索起點(diǎn)s’：搜索與p相鄰的節(jié)點(diǎn)，若p出度大于零，則將p壓入棧gHash，其相鄰結(jié)點(diǎn)列表nVector壓入棧bHash，轉(zhuǎn)步驟（2）。

（5）對p的出度做減一運(yùn)算，若減一后出度仍大于零，壓入棧gHash，轉(zhuǎn)步驟（2）。

4.3 算法優(yōu)化分析

優(yōu)化后的算法采用面向?qū)ο蟮姆椒愋偷拇鎯Y(jié)構(gòu)，占用的空間與算法無關(guān)，而是與算法執(zhí)行時需要的空間有關(guān)，所以降低了空間復(fù)雜度；對象的存儲位置和對象的關(guān)鍵屬性之間建立了特定的對應(yīng)關(guān)系，每個對象只與唯一的一個存儲位置相對應(yīng)，在查找時，只需要根據(jù)對象的關(guān)鍵屬性K計算F（K）便可得到要查找的對象，從而降低數(shù)據(jù)查找所花費(fèi)的時間。算法優(yōu)化前后對比如表1所示。

表1 算法優(yōu)化分析

5 總結(jié)

本文對基于OpenFlow控制器的SDN網(wǎng)絡(luò)框架結(jié)構(gòu)進(jìn)行了探討，在數(shù)據(jù)轉(zhuǎn)發(fā)過程中采用優(yōu)化了的Dijkstra算法。SDN網(wǎng)絡(luò)架構(gòu)能夠解決部分傳統(tǒng)網(wǎng)絡(luò)架構(gòu)所面臨的問題，但同時也面臨新的難題。本文是在虛擬機(jī)搭建起來的環(huán)境下模擬SDN網(wǎng)絡(luò)，實(shí)現(xiàn)了數(shù)據(jù)轉(zhuǎn)發(fā)等基本功能，這與真實(shí)的網(wǎng)絡(luò)部署之間存在較大的差距，我們尚未能預(yù)測到在對真實(shí)的大規(guī)模網(wǎng)絡(luò)進(jìn)行布置時將面臨的問題，這有待我們進(jìn)一步研究與實(shí)踐。

[1]張燦，林昭文，馬嚴(yán).OpenFlow網(wǎng)絡(luò)環(huán)境中的路由技術(shù)研究[J].新型工業(yè)化，2014，4(2)：57-61.

[2]侯長逸.OpenFlow網(wǎng)絡(luò)軟件路由研究[J].蘭州大學(xué)學(xué)報（自然科學(xué)版），2013，(4)：261-262.

[3]高明.SDN的ForCES實(shí)現(xiàn)及服務(wù)部署研究[D].浙江：浙江大學(xué)，2014，(3)：4-10.

[4]左青云，陳鳴，趙廣松，等.基于OpenFlow的SDN技術(shù)研究[J].軟件學(xué)報，2013，(4)：1081-1087.

[5]王楠.OpenFlow網(wǎng)絡(luò)中路由機(jī)制的研究與實(shí)現(xiàn)[D].北京：北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，2012：27?28.

[6]蘇金樹，吳純青，胡曉峰，等.下一代互聯(lián)網(wǎng)體系結(jié)構(gòu)[J].中國計算機(jī)學(xué)會通訊，2010，3(6)：63?64.

[7]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，1997.