基于Openflow的路由算法設計

林亞飛 劉惠臨

（安徽理工大學計算機科學與工程學院，安徽 淮南 232001）

1 引言

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

2 路由框架探討

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

3 路由算法設計

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

圖1 OpenFlow網(wǎng)絡結構示意圖

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

具體步驟如下：

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

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

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

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

圖2 Dijkstra算法圖

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

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

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

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

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

4.2.1 存儲結構定義

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

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

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

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

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

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

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

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

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

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

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

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

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

優(yōu)化后的算法采用面向對象的方法類型的存儲結構，占用的空間與算法無關，而是與算法執(zhí)行時需要的空間有關，所以降低了空間復雜度；對象的存儲位置和對象的關鍵屬性之間建立了特定的對應關系，每個對象只與唯一的一個存儲位置相對應，在查找時，只需要根據(jù)對象的關鍵屬性K計算F（K）便可得到要查找的對象，從而降低數(shù)據(jù)查找所花費的時間。算法優(yōu)化前后對比如表1所示。

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

5 總結

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

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

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

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

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

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

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

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