基于K-Dijkstra算法的SDN負載均衡策略研究

葉葉

摘要 本文提出基于K-Dijkstra算法的SDN負載均衡方法。首先利用控制器評估當前網絡負載情況，其次基于已知的K條備選鏈路，利用K-Dijkstra算法分析符合現有網絡環境的鏈路;由于過載鏈路中存在部分流量擁塞的情況，所以需要進行遷移，最終實現均衡化鏈路負載。

【關鍵詞】SDNK-Dijkstra 算法 負載均衡

隨著云計算、大數據的興起。在IT服務發展領域中數據中心扮演著至關重要的角色，是承載網絡負荷的基礎設施。要想確保網絡服務質量，關鍵在于均衡化網絡負載。從數據中心發展的層面分析，當務之急是解決網絡中存在的流量擁塞問題，在此基礎上優化網絡資源，改善網絡性能。

提高網絡帶寬，重新規劃網絡架構，是傳統的改善網絡性能、均衡化負載的基本方法。其常見的實現方法是使用負載均衡器，但是其復雜性高且費用高，同時其所有請求僅依賴于負載均衡器進行傳遞。均衡器一旦由于某種原因而突發故障，則降低網絡性能，甚至使網絡陷入癱瘓。眾所周知可編程性差、創新性不足是傳統網絡的主要瓶頸性問題，從數據中心網絡發展的角度來看，僅改善TCP/IP網絡架構很難真正發揮其應有的作用，基于此，而形成軟件定義網絡。

1SDN介紹

1.1 SDN定義

Software Defined Network，簡稱SDN，即軟件定義網絡。SDN是近年來最流行的網絡分層架構。此類架構從上至下可細分為三層：其一是應用層;其二是控制層;其三是數據層。由控制層完成傳統網絡中交換機、路由器的轉移權限的操作，集中化網絡功能。應用層是管理層進行網絡監管的切入點。數據層的作用是執行控制層下發的決策，其中的路由器、交換機的功能僅局限于轉發，應用層包含可編程接口，有助于減少系統工作壓力，優化系統性能，實現靈活操作。

1.2 SDN特點

1.2.1轉控分離

網元的控制平面在控制器上，負責協議計算，產生流表;而轉發平面只在網絡設備上。

1.2.2集中控制

設備網元通過控制器集中管理和下發流表，這樣就不需要對設備進行逐一操作，具有簡化操作的作用，實際操作中僅需要對控制器進行配置即可。

1.2.3開放接口

第三方應用只需要通過控制器提供的開放接口，通過編程方式定義一個新的網絡功能，然后在控制器上運行即可。

1.3 0pen Flow協議介紹

靈活、規范、穩定性強的Open Flow協議是底層交換設備、控制器接口的重要協議，同時SDN領域普遍將該協議定義為南向接口標準。該技術的核心思想是支持分離SDN控制，同時協議還是控制器與底層交換設備實現通信的重要載體。網絡管理者及廣大用戶依托Open Flow協議，可結合實際需求制定相應的轉發策略，而非僅依賴傳統硬件設備。如此一來，即可全面提升網絡資源分配管理的靈活性。

在SDN架構中Open Flow控制器是最為核心的部件，該控制器可控制、管理整個網絡，是SDN的關鍵要素之一。

2負載均衡的意義

在現有網絡結構上負載均衡負責向各服務器平均分配主機請求，避免部分鏈路擁塞或空閑的情況。簡而言之即有助于平衡各類鏈路的請求，縮短服務延長，提高服務吞吐量。

負載均衡調度算法，可具體分為如下兩類，其分類依據即負載調度策略。

（1）靜態負載均衡算法：立足網絡現狀，預設固定調度策略，并作為調度執行，而無需實時參考網絡現狀。此種算法無需立足網絡現狀實時變動，可有效縮短執行時間，節省成本。但是該算法的負載均衡效率差，不具有靈活性。

（2）動態負載均衡算法：可實現實時分析服務器、網絡現狀，在此基礎上結合負載信息，動態的向服務器平均分配請求。該算法具有靈活性高的特點，所以可及時獲取網絡現狀，并動態的實現調度負載，因此，解決了靜態負載均衡算法靈活性差，不能夠動態結合網絡現狀部署方案的缺點。

本文逐一分析了兩種算法的優劣勢。在此基礎上提出了SDN負載均衡方法。該算法的核心思想是K-Dijkstra算法，優化SDN架構，并改進該算法，在已獲得的短路徑中刪除某中一條邊，重新尋找新的替代邊，獲取其他路徑，通過控制器對轉發策略調度進行重新制度，避免部分鏈路被流量擁堵的情況，進一步實現負載均衡。下文將具體說明算法的基本思想及核心理念。

3K-Dijkstr算法

3.1 K-Dijkstr算法基本思想

確定有向圖最短徑并刪除其中某條邊，在此基礎上刪除其中某條邊，基于K條備選路路徑選擇一條可代替的路徑。通過公式（1）說明圖邊中的權重值w。 w=αχ+βγ+γγ（1）

其中α+β+γ=1，χ、γ、z分別用于表示其一平均延遲;其二平均丟包率;其三跳數。具體由流量監測模塊提供數值。給定初始權重值，即w =l/3（x+y+z），此后結合網絡情況可方便用戶、管理員結合需求改變并計算w值。假設所計算的值較w值小，對應的該值為有效值。如較w值大，則說明相關值為無效值，此時需要重新設計。

應用層軟件可滿足管理員結合具體要求設置當前網絡跳數、丟包率、網絡延遲等相關參數及占比。如經計算的w值越小，則說明對應的路徑負載、優先級良好。結合己刪除邊計算尋找下一個可替代的最短路徑，以小到大的順序排序總權重值w，由控制器下發轉發策略，向優先級較高調度流量，緩解鏈路擁堵塞的情況，均衡負載。

3.2 K-Dijkstr算法描述

（1）基于向圖G（N，A）采用該算法計算根節點為m的節點，并確定最短路徑，s為終點，用Sn，表示該條路徑，n=l;

（2）假設存在該路徑的候選路徑，且n

（3）在路徑S點中，確定首個節點后，進行遍歷操作從中確定首個入度較1大的節點，并記為ka，假設ka不存在于任何節點之中，換言之即節點中不存在ka的擴展節點，如符合條件，則直接進入（4）;如未符合條件，需找出ka后續首個不基于點集P的擴展節點，記為ka，則，繼續執行步驟（5）;

（4）生成ka，即ka的擴展節點，同時加入點集P中，kn所有前驅節點（除前一個節點ka-1外）連接至ka，此時不改變弧權重，在弧集A中添加該弧值，基于m、ka計算兩者的最短路徑，代表初始節點與擴展節點的距離，并記為ki=ka+1;

（5）將所有ka之后路徑S遍歷的所有節點記為kc，同時需要執行相關操作：

首先將kc加入節點集合P中;

基于路徑S分別連接kc的前驅節點至kc的?。ú话耙粋€節點kc-1），在弧集A中添加這些弧，并不改變權值。

最后計算s到kc兩者間的最短路徑。假設擴展節點kc-1，存在于路徑S中，且在kc-1存上，并形成kc-1與kc，該弧度具有連接兩者的作用，對應的權值剛好為?。╧c-1，kc）相等：

（6）計算第n條最短路徑，即m與t（n）的距離，即開始節點到結束節點的距離，同時n+l=n，具體執行上述第二個步驟。

擴展節點：具體指在上次節點集合中引入新節點。

前驅節點：顧名思義即某一節點的前一節點（同一最短路徑）。

算法流程圖如圖1所示。

4小結

本文基于SDN架構詳細研究并部署了均衡負載的方案，首先運用已有的控制器獲取并評估網絡負載;在此基礎上結合K-Dijkstra算法具體求解出相關算法，即最短路徑，在此基礎上進行優先級排序，其排序依據為路徑權重值大小，如經排序認為路徑的權重值較小，則說明對應的最短路徑具備較高的優先級;最后是轉發策略，本步驟的重點是把存在流量過多的過載鏈路中的流量遷移至最符合要求的鏈路之中，均衡負載。同時結合該算法計算向圖權重值，并利用三元函數組，滿足用戶在不同環境中的使用需求。綜上本文所提出的方法不僅可顯著優化網絡性能，同時減少網絡丟包率、網絡延遲等情況的發生。當然本文尚存不足之處，有待后續研究完善。

參考文獻

[1]武澤慧，魏強，王清賢，基于Open Flow的SDN網絡攻防方法[J]，計算機科學，2017， 44 （06）：121-132.

[2]竇煥娟，基于Open Flow的服務器集群負載均衡的研究[D].北京：華北電力大學，2016.

[3]黃小曼.SDN網絡控制器負載均衡技術研究與實現[D].南京：南京郵電大學，2015.

[4]胡延楠，軟件定義網絡關鍵技術及相關問題的研究[D].北京：北京郵電大學，2015.

[5]吳舢，一種基于SDN的網絡負載均衡方案的設計與實現[D].上海：復旦大學，2014.