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

葉葉

摘要 本文提出基于K-Dijkstra算法的SDN負(fù)載均衡方法。首先利用控制器評估當(dāng)前網(wǎng)絡(luò)負(fù)載情況，其次基于已知的K條備選鏈路，利用K-Dijkstra算法分析符合現(xiàn)有網(wǎng)絡(luò)環(huán)境的鏈路;由于過載鏈路中存在部分流量擁塞的情況，所以需要進(jìn)行遷移，最終實(shí)現(xiàn)均衡化鏈路負(fù)載。

【關(guān)鍵詞】SDNK-Dijkstra 算法 負(fù)載均衡

隨著云計(jì)算、大數(shù)據(jù)的興起。在IT服務(wù)發(fā)展領(lǐng)域中數(shù)據(jù)中心扮演著至關(guān)重要的角色，是承載網(wǎng)絡(luò)負(fù)荷的基礎(chǔ)設(shè)施。要想確保網(wǎng)絡(luò)服務(wù)質(zhì)量，關(guān)鍵在于均衡化網(wǎng)絡(luò)負(fù)載。從數(shù)據(jù)中心發(fā)展的層面分析，當(dāng)務(wù)之急是解決網(wǎng)絡(luò)中存在的流量擁塞問題，在此基礎(chǔ)上優(yōu)化網(wǎng)絡(luò)資源，改善網(wǎng)絡(luò)性能。

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

1SDN介紹

1.1 SDN定義

Software Defined Network，簡稱SDN，即軟件定義網(wǎng)絡(luò)。SDN是近年來最流行的網(wǎng)絡(luò)分層架構(gòu)。此類架構(gòu)從上至下可細(xì)分為三層：其一是應(yīng)用層;其二是控制層;其三是數(shù)據(jù)層。由控制層完成傳統(tǒng)網(wǎng)絡(luò)中交換機(jī)、路由器的轉(zhuǎn)移權(quán)限的操作，集中化網(wǎng)絡(luò)功能。應(yīng)用層是管理層進(jìn)行網(wǎng)絡(luò)監(jiān)管的切入點(diǎn)。數(shù)據(jù)層的作用是執(zhí)行控制層下發(fā)的決策，其中的路由器、交換機(jī)的功能僅局限于轉(zhuǎn)發(fā)，應(yīng)用層包含可編程接口，有助于減少系統(tǒng)工作壓力，優(yōu)化系統(tǒng)性能，實(shí)現(xiàn)靈活操作。

1.2 SDN特點(diǎn)

1.2.1轉(zhuǎn)控分離

網(wǎng)元的控制平面在控制器上，負(fù)責(zé)協(xié)議計(jì)算，產(chǎn)生流表;而轉(zhuǎn)發(fā)平面只在網(wǎng)絡(luò)設(shè)備上。

1.2.2集中控制

設(shè)備網(wǎng)元通過控制器集中管理和下發(fā)流表，這樣就不需要對設(shè)備進(jìn)行逐一操作，具有簡化操作的作用，實(shí)際操作中僅需要對控制器進(jìn)行配置即可。

1.2.3開放接口

第三方應(yīng)用只需要通過控制器提供的開放接口，通過編程方式定義一個新的網(wǎng)絡(luò)功能，然后在控制器上運(yùn)行即可。

1.3 0pen Flow協(xié)議介紹

靈活、規(guī)范、穩(wěn)定性強(qiáng)的Open Flow協(xié)議是底層交換設(shè)備、控制器接口的重要協(xié)議，同時SDN領(lǐng)域普遍將該協(xié)議定義為南向接口標(biāo)準(zhǔn)。該技術(shù)的核心思想是支持分離SDN控制，同時協(xié)議還是控制器與底層交換設(shè)備實(shí)現(xiàn)通信的重要載體。網(wǎng)絡(luò)管理者及廣大用戶依托Open Flow協(xié)議，可結(jié)合實(shí)際需求制定相應(yīng)的轉(zhuǎn)發(fā)策略，而非僅依賴傳統(tǒng)硬件設(shè)備。如此一來，即可全面提升網(wǎng)絡(luò)資源分配管理的靈活性。

在SDN架構(gòu)中Open Flow控制器是最為核心的部件，該控制器可控制、管理整個網(wǎng)絡(luò)，是SDN的關(guān)鍵要素之一。

2負(fù)載均衡的意義

在現(xiàn)有網(wǎng)絡(luò)結(jié)構(gòu)上負(fù)載均衡負(fù)責(zé)向各服務(wù)器平均分配主機(jī)請求，避免部分鏈路擁塞或空閑的情況。簡而言之即有助于平衡各類鏈路的請求，縮短服務(wù)延長，提高服務(wù)吞吐量。

負(fù)載均衡調(diào)度算法，可具體分為如下兩類，其分類依據(jù)即負(fù)載調(diào)度策略。

（1）靜態(tài)負(fù)載均衡算法：立足網(wǎng)絡(luò)現(xiàn)狀，預(yù)設(shè)固定調(diào)度策略，并作為調(diào)度執(zhí)行，而無需實(shí)時參考網(wǎng)絡(luò)現(xiàn)狀。此種算法無需立足網(wǎng)絡(luò)現(xiàn)狀實(shí)時變動，可有效縮短執(zhí)行時間，節(jié)省成本。但是該算法的負(fù)載均衡效率差，不具有靈活性。

（2）動態(tài)負(fù)載均衡算法：可實(shí)現(xiàn)實(shí)時分析服務(wù)器、網(wǎng)絡(luò)現(xiàn)狀，在此基礎(chǔ)上結(jié)合負(fù)載信息，動態(tài)的向服務(wù)器平均分配請求。該算法具有靈活性高的特點(diǎn)，所以可及時獲取網(wǎng)絡(luò)現(xiàn)狀，并動態(tài)的實(shí)現(xiàn)調(diào)度負(fù)載，因此，解決了靜態(tài)負(fù)載均衡算法靈活性差，不能夠動態(tài)結(jié)合網(wǎng)絡(luò)現(xiàn)狀部署方案的缺點(diǎn)。

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

3K-Dijkstr算法

3.1 K-Dijkstr算法基本思想

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

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

應(yīng)用層軟件可滿足管理員結(jié)合具體要求設(shè)置當(dāng)前網(wǎng)絡(luò)跳數(shù)、丟包率、網(wǎng)絡(luò)延遲等相關(guān)參數(shù)及占比。如經(jīng)計(jì)算的w值越小，則說明對應(yīng)的路徑負(fù)載、優(yōu)先級良好。結(jié)合己刪除邊計(jì)算尋找下一個可替代的最短路徑，以小到大的順序排序總權(quán)重值w，由控制器下發(fā)轉(zhuǎn)發(fā)策略，向優(yōu)先級較高調(diào)度流量，緩解鏈路擁堵塞的情況，均衡負(fù)載。

3.2 K-Dijkstr算法描述

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

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

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

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

（5）將所有ka之后路徑S遍歷的所有節(jié)點(diǎn)記為kc，同時需要執(zhí)行相關(guān)操作：

首先將kc加入節(jié)點(diǎn)集合P中;

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

最后計(jì)算s到kc兩者間的最短路徑。假設(shè)擴(kuò)展節(jié)點(diǎn)kc-1，存在于路徑S中，且在kc-1存上，并形成kc-1與kc，該弧度具有連接兩者的作用，對應(yīng)的權(quán)值剛好為?。╧c-1，kc）相等：

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

擴(kuò)展節(jié)點(diǎn)：具體指在上次節(jié)點(diǎn)集合中引入新節(jié)點(diǎn)。

前驅(qū)節(jié)點(diǎn)：顧名思義即某一節(jié)點(diǎn)的前一節(jié)點(diǎn)（同一最短路徑）。

算法流程圖如圖1所示。

4小結(jié)

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

參考文獻(xiàn)

[1]武澤慧，魏強(qiáng)，王清賢，基于Open Flow的SDN網(wǎng)絡(luò)攻防方法[J]，計(jì)算機(jī)科學(xué)，2017， 44 （06）：121-132.

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

[3]黃小曼.SDN網(wǎng)絡(luò)控制器負(fù)載均衡技術(shù)研究與實(shí)現(xiàn)[D].南京：南京郵電大學(xué)，2015.

[4]胡延楠，軟件定義網(wǎng)絡(luò)關(guān)鍵技術(shù)及相關(guān)問題的研究[D].北京：北京郵電大學(xué)，2015.

[5]吳舢，一種基于SDN的網(wǎng)絡(luò)負(fù)載均衡方案的設(shè)計(jì)與實(shí)現(xiàn)[D].上海：復(fù)旦大學(xué)，2014.