基于Openflow的路由算法設計

林亞飛 劉惠臨

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

1 引言

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

2 路由框架探討

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

3 路由算法設計

交由OpenFlow交換機處理的數據包有三種∶⑴Open-Flow網段內傳輸的數據包；⑵來自于傳統路由器的數據包；⑶OpenFlow網段間轉發的數據包。第三種情況下,要應用OpenFlow路由組件對數據包進行路由查詢和轉發。如圖1為Openflow網絡結構示意圖。

圖1 OpenFlow網絡結構示意圖

對數據包進行轉發時，我們需選取最優路徑來節省時間，提高工作效率。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作為新的中間節點，更新B中各頂點的距離；若經過節點n的距離值比未經過n時的距離值小，則更新頂點b的距離值(為n的距離+邊上權值)。

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

圖2 Dijkstra算法圖

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

4 路由算法優化

4.1 算法優化思想

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

4.2 算法優化實現

4.2.1 存儲結構定義

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

stVector：用于存儲最短路徑節點列表。

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

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

gHash：用于存儲出度大于零的節點。

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

4.2.2 算法實現步驟

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

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

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

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

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

4.3 算法優化分析

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

表1 算法優化分析

5 總結

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

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

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

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

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

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

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

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