SDN驅(qū)動的網(wǎng)絡流量負載均衡路由優(yōu)化算法

閔曉飛, 李 靖, 張朝輝

(西安電子科技大學數(shù)學與統(tǒng)計學院, 陜西 西安 710126)

0 引 言

5G網(wǎng)絡是新一代移動通信網(wǎng)絡,其主要目標是在提升網(wǎng)絡數(shù)據(jù)流傳輸效率的同時優(yōu)化網(wǎng)絡資源分配效率、減少網(wǎng)絡運營支出成本(operating expenditure, OPEX)等[1]。5G網(wǎng)絡主要由3部分組成:無線接入網(wǎng)(radio access network, RAN)、核心網(wǎng)(core network, CN)以及軟件定義網(wǎng)絡(software-defined networking, SDN)[2]。作為5G通信網(wǎng)絡拓撲系統(tǒng)的重要組成部分,SDN分離了網(wǎng)絡的數(shù)據(jù)層和控制層[3-8],使得跨異構設備和網(wǎng)絡去配置服務質(zhì)量(quality of service, QoS)變得可行,并且可以通過控制網(wǎng)絡中的流量負載機制完成不同網(wǎng)絡資源的分配優(yōu)化,實現(xiàn)了從設備可編程到網(wǎng)絡可編程的轉(zhuǎn)變,為研發(fā)網(wǎng)絡新應用和未來互聯(lián)網(wǎng)技術提供了一種新的解決方案。

傳統(tǒng)的網(wǎng)絡資源分配問題大多側重于任務卸載和網(wǎng)絡開銷之間的權衡,以保證網(wǎng)絡QoS或最小化網(wǎng)絡開銷為目標[9-10]。文獻[11]針對用戶資源申請與網(wǎng)絡可用資源最優(yōu)配置問題,建立了基于SDN的資源分配多目標優(yōu)化模型,滿足了不同用戶的QoS需求。文獻[12]提出了一種SDN控制器上的強化學習方案,旨在最小化網(wǎng)絡鏈路的最大利用率,從而減少網(wǎng)絡服務中斷干擾。文獻[13]提出了一種基于接收器的擁塞控制方案—RecFlow,該方案利用OpenFlow提供的路徑可見性來解決數(shù)據(jù)中心傳輸問題。文獻[14]通過評估SDN,利用散列函數(shù)來調(diào)度數(shù)據(jù)流,對擁塞較少的路徑進行優(yōu)先排序,優(yōu)化了數(shù)據(jù)傳輸效率。

文獻[15]提出了一種基于SDN的復雜多路徑數(shù)據(jù)傳輸優(yōu)化策略—HiQoS,該策略通過改進Dijkstra算法優(yōu)化了數(shù)據(jù)多路徑轉(zhuǎn)發(fā)效率。文獻[16]利用類似的方法,選擇具有最大帶寬和可用性的路徑,提出了一種自適應多路徑供應方案。在文獻[17]中,Al-Najjar等初步探討了在靜態(tài)鏈路情況下如何更好地使用SDN控制多宿主終端主機中的網(wǎng)絡流。文獻[18]采用不同的流量負載均衡算法進一步在動態(tài)鏈路容量的網(wǎng)絡場景中擴展了這一貢獻。

現(xiàn)代優(yōu)化算法是一種操作性強且優(yōu)化率高的求解方式,近年來在網(wǎng)絡資源分配問題中被廣泛應用。在文獻[19]中,Zhang等提出了一種基于模糊邏輯的資源分配(fuzzy logic-based resource allocation, FUZZRA)算法,該算法能夠充分利用物理層資源,在不造成明顯干擾的情況下最大限度地重復利用有限的資源。文獻[20]提出了一種基于最小代價路徑的交換機遷移算法,根據(jù)流量負載預測矩陣確定遷出控制器和目標控制器集合。

文獻[21]基于SDN集中管理和控制的特點,在網(wǎng)絡正常運行情況下,結合遺傳算法中交叉和變異的思想,使用改進的粒子群優(yōu)化算法合理優(yōu)化網(wǎng)絡資源分配;對于流量過載的緊急情況,提出了一種基于軟件定義廣域網(wǎng)(software defined wide area network, SD-WAN)的定期調(diào)度方法,以解決通信中的“潮汐效應”問題。此外,還有很多算法將遺傳算法和其他智能優(yōu)化算法進行了融合,詳見文獻[22-24],這些算法都取得了非常優(yōu)異的效果。

SDN控制的QoS感知多路徑傳輸控制協(xié)議 (multipath transmission control protocol, MPTCP)問題是資源分配中常見的目標優(yōu)化問題。文獻[25]設計了一種名為延遲均衡快速(delay-equalized FAST, DEFT)的MPTCP擁塞控制算法,該算法包括一種適用于5G網(wǎng)絡的窗口控制方案和延遲均衡方案,在吞吐量和端到端延遲方面具備非常優(yōu)越的性能。Wang等[26]探索了在虛擬網(wǎng)絡中調(diào)度MPTCP流的多路徑轉(zhuǎn)發(fā)問題。但是,MPTCP將一個流拆分為多個子流轉(zhuǎn)發(fā)到多個路徑中,這對于移動用戶而言處理起來很復雜。

通過提高網(wǎng)絡流量遷移效率來完成資源分配優(yōu)化也是常見的研究手段。文獻[27]提出了一種基于模糊多目標粒子群算法的動態(tài)切換遷移策略,該方案綜合考慮了網(wǎng)絡流量遷移的OPEX、效率與均衡性,但算法的運算量和數(shù)據(jù)的存儲量都很大,魯棒性較低。為了解決控制層的流量負載均衡問題,Kim等[28]提出了一種遞進和聲搜索(progre-ssive-harmony search, P-HS)啟發(fā)式算法,該算法有效解決了分布式SDN環(huán)境中的資源動態(tài)控制、供應問題,最大程度減少了交換機與控制器之間的通信時延。

文獻[29]從用戶和網(wǎng)絡運營商的角度探討了執(zhí)行計劃(execution plans, EPs)的有效實施,并針對流量分配過程制定了3種不同的啟發(fā)式算法。此外,還提出了評估標準,以研究鏈路帶寬和運營商成本約束下EPs的效率。文獻[30]提出了一種用于支持SDN的邊緣網(wǎng)絡中動態(tài)任務調(diào)度和分配的深度強化學習方法,實現(xiàn)了網(wǎng)絡低延遲,同時節(jié)省了能耗。文獻[31]提出了一種端到端服務鏈編排系統(tǒng),該系統(tǒng)可以基于網(wǎng)絡的當前負載迅速調(diào)整已建立的服務鏈路徑,以解決可靠性問題。

隨著5G時代的到來,組網(wǎng)規(guī)模和用戶數(shù)量急劇增加,這就導致部署網(wǎng)絡功能設備的開銷越來越大,同時也出現(xiàn)了5G網(wǎng)絡底層設備運行管理困難、失效率高等問題。Bagaa等引入QoS感知的網(wǎng)絡配置和多路徑轉(zhuǎn)發(fā)協(xié)議,通過考慮用戶的移動環(huán)境以及QoS需求提出了一種啟發(fā)式路徑重計算(heuristic paths re-computation, HPR)算法[2]。該算法在滿足合理計算時間的前提下,降低了網(wǎng)絡OPEX,使得運營商在支持SDN的網(wǎng)絡中,能夠在考慮移動性的情況下有效地分配網(wǎng)絡資源、減少甚至消除過度供應。然而,文獻[2]并沒有考慮網(wǎng)絡整體流量負載均衡和資源利用率聯(lián)合的問題,無法直接用于新的5G虛擬網(wǎng)絡范式。

為了在滿足用戶多樣性服務需求的同時確保網(wǎng)絡QoS,本文提出了兩種由SDN驅(qū)動的路由優(yōu)化算法:負載均衡廣度優(yōu)先搜索(load balancing scheme with breadth-first-search, LBB)路徑優(yōu)化算法以及基于深度優(yōu)先搜索的迭代深度搜索(iterative deepening search with depth-first-search, IDDFS)路徑優(yōu)化算法。LBB算法首先將用戶接入的所有eNodeB節(jié)點看作一個超級源節(jié)點并進行數(shù)據(jù)的接入,在保證滿足用戶服務請求的同時滿足網(wǎng)絡QoS,然后在傳統(tǒng)廣度優(yōu)先搜索(breadth-first-search, BFS)算法的基礎上設定了一個動態(tài)流量負載均衡控制閾值。當網(wǎng)絡檢測到鏈路流量負載均衡參數(shù)超過實時動態(tài)流量閾值時,再次優(yōu)化路徑分配,在保證OPEX的同時提高了網(wǎng)絡資源的利用率。而IDDFS算法在每次數(shù)據(jù)傳輸路徑搜索中對搜索深度進行限制,在當前限制的深度下以最大帶寬優(yōu)先搜索目標節(jié)點,如果搜索不到目標節(jié)點,則增加深度重新進行搜索,直至找到目標節(jié)點。

IDDFS算法通過迭代去找尋可行解,如果在尋路的兩點之間不存在可行解,算法在搜索最優(yōu)路徑時會沒有方向地一直增加深度,陷入循環(huán),影響算法執(zhí)行效率。而在LBB算法中,一旦搜索不到目標節(jié)點,算法會立即終止此次搜索,不再進行迭代,保證算法后續(xù)的運行,在滿足合理計算時間的前提下實現(xiàn)負載均衡;而相較于LBB算法,IDDFS算法在保證負載均衡的同時有效地縮減了空間開銷。

1 網(wǎng)絡模型與系統(tǒng)建模

1.1 網(wǎng)絡模型

本文將5G網(wǎng)絡抽象為一個帶權有向圖G(V,E,W),其中E代表網(wǎng)絡中邊的集合,W表示帶寬集合,V=C∪O∪R∪S代表網(wǎng)絡中節(jié)點的集合,C、O、R、S分別代表用戶集、開放式虛擬交換機(open virtual switch,OVS)的集合、建立的超級源節(jié)點以及超級匯點(終端服務器)。E中邊(u,v)的權值wu,v代表節(jié)點u和節(jié)點v之間的帶寬容量。詳細的符號對照表如表1所示。

表1 符號對照表

網(wǎng)絡拓撲示意圖如圖1所示,假設每個用戶c與網(wǎng)絡接入通信節(jié)點eNodeB間的通信方式是無線(虛線)的;不同OVS之間的通信是有線(實線)的;對于用戶和服務器之間的通信方式,客戶端和接入點eNodeB之間的第一跳是無線接口,而通向服務器的其余網(wǎng)絡鏈路是有線的。

圖1 網(wǎng)絡拓撲示意圖Fig.1 Network topology skematic diagram

1.2 問題的數(shù)學建模

(1)

(2)

(3)

?i∈C∪O,?j∈η(i)∩(O∪S):

Ti,j≤wi,j×xi,j

(4)

(5)

式(2)表示每個用戶只能連接到一個相應的OVS來接收和傳輸數(shù)據(jù)流量;式(3)表示鏈路中每一跳轉(zhuǎn)發(fā)的數(shù)據(jù)流量等于用戶申請的數(shù)據(jù)流量,并且輸入流量等于輸出流量;式(4)表示實際轉(zhuǎn)發(fā)的流量不能超過兩個節(jié)點之間的鏈路帶寬上限;式(5)表示客戶端和服務器之間的數(shù)據(jù)傳輸路徑不存在任何環(huán)路。

由于上述的數(shù)學模型是一個NP難問題,因此本文將通過兩個近似優(yōu)化算法LBB以及IDDFS對該模型進行求解。

2 LBB優(yōu)化算法

文獻[2]基于Dijkstra算法提出了改進的HPR算法,在較短的時間內(nèi)實現(xiàn)了用戶和服務器之間的最優(yōu)路徑分配。然而該算法一旦選擇了接入點,數(shù)據(jù)傳輸路徑會一直被使用到與該接入點相連的鏈路帶寬不滿足用戶申請的帶寬要求時才停止,導致網(wǎng)絡中的其他節(jié)點一直處于休眠狀態(tài),造成了休眠狀態(tài)節(jié)點資源的浪費,降低了資源分配效率。

為了避免局部流量負載過大,同時提高節(jié)點資源利用率,并且盡可能地減少網(wǎng)絡OPEX,LBB算法在實現(xiàn)過程中加入了一個動態(tài)流量負載均衡閾值,具體路徑優(yōu)化過程如算法1所示。

算法 1 LBB算法輸入:G(V,E,W),C,S輸出:Φ,Pc,sBegin(1) Φ=?(2) For c∈C V1=V E1=E(3) For o∈η(c)∩O If wc,o<λt V1=V1o End if End for(4) For(u,v)∈E1If wu,v<λt E1=E1(u,v)End ifEnd for(5) While true do If ?o∈O∩V1-{c}∧|η(o)|≤1 V1=V1o Else Break End ifEnd while(6) MATOLIST(V1,E1)BFS(R,S,V1,E1,W)Source=R(7) If c==1 Pc,s= BFS(R,S,V1,E1,W) ElseWhile Source !=S If σ<φ Source=Next Pc,s=Pc,s∪Source Else E1wSource,next BFS(Source,S,V1,E1,W) Φ=Φ∪(Pc,s∩O) End if End while End if(8) For(u,v)∈Pc,s wu,v=wu,v-λt End for End forEnd

定義流量負載均衡參數(shù)公式

(6)

根據(jù)實驗,本文選取流量負載均衡參數(shù)的中位數(shù)φ為動態(tài)流量負載均衡控制閾值。算法開始時,初始化Φ為空集,然后執(zhí)行一個循環(huán),以計算并存儲用戶和終端服務器之間的數(shù)據(jù)傳輸路徑。在算法內(nèi)部循環(huán)中,為了避免路徑拓撲中的V和E在計算新路徑時被覆蓋而丟失路徑信息,將兩個臨時變量集合V1和E1分別初始化為V和E。算法1中的步驟(3)～步驟(5)移除了不滿足轉(zhuǎn)發(fā)條件的鏈路和節(jié)點。

接下來,步驟(6)和步驟(7)執(zhí)行尋找用戶c和終端服務器S之間的路徑進程,從超級源點R進行BFS,若此時是第一個用戶,則直接存儲其路徑,否則將Source記作接入點;如果Source到下一個節(jié)點的鏈路流量負載參數(shù)小于φ,則把下一個節(jié)點標記為Source,否則暫時屏蔽此路徑;從Source重新進行BFS,直至搜索到S,則輸出最終使用的OVS集合,并更新權值進行下一輪搜索。

圖2分別給出了HPR算法和LBB算法實現(xiàn)過程的網(wǎng)絡拓撲示例。假設一個移動網(wǎng)絡由4個eNodeB、1組編號為1到8的OVS節(jié)點和2個服務器(Sever)組成。網(wǎng)絡初始配置如圖2(a)、圖2(d)所示,刪除所有已用資源得到當前拓撲圖G,其中不滿足用戶申請帶寬要求的鏈路用紅色表示。如圖2(b)所示,在HPR算法中,當用戶1申請接入網(wǎng)絡時,由于此時沒有接入點eNodeB,則按照定義的權值使用Dijkstra算法進行尋路,得到最終路徑上使用的虛擬節(jié)點是OVS 1和OVS 4,將OVS 1選為接入點。如圖2(c)所示,當用戶2接入網(wǎng)絡時,由于此時基站eNodeB1和OVS 1之間的帶寬仍然滿足條件,因此仍然選擇OVS 1作為接入點,繼續(xù)使用Dijkstra算法進行尋路,最終激活了OVS 1、OVS 4,以進行數(shù)據(jù)傳輸。

圖2 HPR算法和LBB算法拓撲示例Fig.2 Topology examples of HPR algorithm and LBB algorithm

LBB算法在保證網(wǎng)絡QoS的前提下將所有的eNodeB節(jié)點映射為一個超級源點,對接入節(jié)點的資源進行統(tǒng)一分配控制,超級源點可以動態(tài)地選擇與OVS 1、OVS 2、OVS 3建立數(shù)據(jù)傳輸鏈路。在圖2(e)中,當用戶1申請接入網(wǎng)絡時,選擇OVS 1作為接入點直接進行BFS,此時網(wǎng)絡激活OVS 1和OVS 4。如圖2(f)所示,當用戶2申請接入網(wǎng)絡時,仍然選擇OVS 1作為接入點。當選取OVS 4作為下一個節(jié)點時,監(jiān)測到流量負載參數(shù)大于實時動態(tài)閾值φ,則回溯到OVS 1,從OVS 1重新進行BFS搜索到OVS 7,激活了OVS 1、 OVS 4、OVS 7,以進行數(shù)據(jù)傳輸。

3 IDDFS優(yōu)化算法

LBB算法旨在通過鏈路動態(tài)控制閾值和搜索回溯的方法優(yōu)化路徑配置,使網(wǎng)絡鏈路流量處于均衡的狀態(tài)。在BFS實現(xiàn)的過程中,每一步都需要存儲當前節(jié)點所連接的所有節(jié)點以及路徑信息。然而,隨著網(wǎng)絡拓撲規(guī)模的擴大,這會造成非常大的空間開銷,這種以空間換取時間的方法會影響算法的有效性。為了降低算法的空間開銷,進一步提出了一種IDDFS優(yōu)化算法。在IDDFS算法中,每次搜索都對搜索深度進行限制,并在搜索過程中選擇可用帶寬最大的鏈路,如果在當前限制深度下搜索不到目標節(jié)點,則增加一層深度重新進行搜索,直至找到目標節(jié)點。由于搜索深度是從小到大遞增的,因此可以保證所得解深度最小,且縮減了空間開銷。

IDDFS算法的具體路徑優(yōu)化過程如算法2所示,初始化后與算法1相同,執(zhí)行步驟(3)～步驟(5),對虛擬網(wǎng)絡拓撲進行優(yōu)化處理。在步驟(6)中,從給定的最小深度mindepth開始,按照帶寬大小進行深度優(yōu)先搜索,如找到目標節(jié)點(即服務器S),則輸出搜索路徑,否則加一跳深度繼續(xù)搜索下一層,直至搜索到S。

End if End for(4) For(u,v)∈E1If wu,v<λt E1=E1(u,v) End if End for(5) While true do If ?o∈O∩V1-{c}∧|η(o)|≤1 V1=V1o Else Break End if End while(6) For(i=mindepth;; i++) Pc,s= DFS(R,S,V1,E1,W) If Pc,s[last]==S Break End if End for

圖3給出了LBB算法和IDDFS算法的網(wǎng)絡拓撲實現(xiàn)過程示例圖。如圖3(a)所示,在LBB算法中,當用戶1申請接入10 Mbps的帶寬時,直接進行BFS搜索。在搜索過程中,OVS 1、OVS 2、OVS 3、OVS 4、OVS 5、OVS 7、OVS 6、OVS 9按層次存儲在堆棧中。最后,激活的節(jié)點是OVS 1、OVS 4。而在IDDFS算法中,每次搜索之前都會設置一個最小搜索深度。如在圖3(c)中,如果設置最小搜索深度為2,選擇OVS 1和OVS 7存儲在堆棧中,但是不能找到目標結點(即服務器節(jié)點 9),則需要將最小搜索深度增加1,再次進行DFS搜索,此時存儲的虛擬節(jié)點為OVS 1、OVS 7、OVS 9,最終激活了OVS 1、OVS 7進行數(shù)據(jù)傳輸。雖然兩個算法激活的OVS數(shù)量都是兩個,但IDDFS算法在尋路過程中需要的堆棧存儲空間比LBB算法少得多。

圖3 LBB算法和IDDFS算法拓撲示例Fig.3 Topology examples of LBB algorithm and IDDFS algorithm

4 仿真實驗

為了驗證所提算法的有效性,本文通過多次重復實驗,將LBB算法、IDDFS算法、HPR算法與經(jīng)典的Dijkstra算法從激活的OVS數(shù)與網(wǎng)絡吞吐量兩個指標進行仿真比較。網(wǎng)絡吞吐量的計算方式為WC×h,其中WC為接入用戶申請的帶寬,h為最終選擇路徑的跳數(shù)。實驗的仿真環(huán)境為Win10 64位系統(tǒng)、CPU處理器Intel Core i5-4300U 2.50 GHz,內(nèi)存4.00 GB,仿真軟件Matlab2020b、Visual Studio 2022。具體實驗方案為:① 固定OVS個數(shù),改變接入用戶的數(shù)量;② 固定用戶數(shù),改變網(wǎng)絡中OVS的數(shù)量。

4.1 動態(tài)流量負載均衡控制閾值對資源利用率的影響

在第2節(jié)中,本文給出了流量負載均衡參數(shù)σ(t)的定義,其代表第t個用戶接入網(wǎng)絡時活躍鏈路利用率的標準差。σ(t)值越小,代表網(wǎng)絡負載越均衡;反之,其值越大,表示鏈路負載差別越大,即負載不均衡。在LBB算法中,本文通過實驗驗證了閾值為中位數(shù)時算法性能最優(yōu)。如圖4所示,該實驗給出了接入用戶個數(shù)從10到100時不同閾值對LBB算法性能的影響。

圖4 不同閾值對LBB算法的影響Fig.4 Impact of different thresholds on LBB algorithm

在仿真實驗中,固定網(wǎng)絡中的OVS數(shù)量為25,網(wǎng)絡拓撲中的鏈路帶寬上限在[100,180]Mb區(qū)間服從隨機分布,接入帶寬區(qū)間為[10,30]M。實驗模擬了多個用戶申請不同接入帶寬大小時資源利用率在兩種不同閾值下的性能對比:① 選用每個用戶接入時當前負載均衡參數(shù)σ(t)為閾值;② 將σ(t)與前(t-1)個負載均衡參數(shù)放在一起,取中位數(shù)φ作為閾值。

由圖4可以看出,當接入用戶數(shù)從10增加到100時,選擇中位數(shù)φ作為動態(tài)流量負載均衡控制閾值時算法優(yōu)于選擇σ(t)作為閾值時激活的OVS數(shù),平均OVS利用率分別為31.4%和25.5%,前者平均利用率高出后者約6%。因此,本文選擇中位數(shù)φ作為動態(tài)流量負載均衡控制閾值。

4.2 固定OVS個數(shù)及改變接入用戶數(shù)對不同解決方案的影響

圖5給出了接入用戶個數(shù)從10到100對HPR算法、LBB算法、IDDFS算法以及Dijkstra算法性能的影響。在仿真實驗中,固定網(wǎng)絡中的OVS數(shù)量為25,網(wǎng)絡拓撲中的鏈路帶寬上限在[100,180]Mb區(qū)間服從隨機分布,接入帶寬區(qū)間為[10,30]Mb,實驗模擬了多個用戶申請不同大小的接入帶寬時的性能。

圖5 接入用戶數(shù)對不同解決方案的影響Fig.5 Impact of number of clients on different solutions

從圖5(a)可以看出,隨著接入用戶數(shù)量從10增加至100,Dijkstra算法激活的OVS數(shù)量從2增加至18,HPR算法從2增加至16,LBB算法從6增加至22,而IDDFS算法從7增加至23。LBB算法以及IDDFS算法的OVS使用數(shù)量始終多于HPR算法和Dijkstra算法,這是因為Dijkstra算法基于貪心思想在每次尋路時永遠選擇跳數(shù)最少的鏈路,而HPR算法則是傾向于復用已經(jīng)激活的鏈路和OVS。一旦選擇了接入點eNodeB,數(shù)據(jù)傳輸路徑會一直被使用直至與該接入點相連的鏈路帶寬不滿足用戶申請的帶寬要求,才會重新配置網(wǎng)絡,而LBB算法和IDDFS算法則是根據(jù)鏈路帶寬的負載能力去進行路徑選擇,有效地提高了節(jié)點資源的利用率。在接入用戶數(shù)量為70時,IDDFS算法首先進入穩(wěn)定狀態(tài),此時不需要激活新的OVS。而當用戶數(shù)大于80時,拓撲中的活躍鏈路帶寬接近上限,此時IDDFS算法會選擇新的OVS進行深度優(yōu)先搜索,進一步優(yōu)化了節(jié)點資源利用率。

從圖5(b)可以看出,IDDFS算法的網(wǎng)絡吞吐率最高。尤其在接入用戶數(shù)超過70時,IDDFS的網(wǎng)絡吞吐量優(yōu)化率更高,這說明在大規(guī)模通信網(wǎng)絡中,IDDFS算法具有更好的QoS。另外從圖5可以看出,隨著接入用戶數(shù)的增加,Dijkstra算法的網(wǎng)絡吞吐量近似線性增加,這是因為在尋路過程中,Dijkstra算法選擇跳數(shù)最少的路徑,而這樣的路徑在拓撲中存在多條。對比圖5(a)可以看到,雖然Dijkstra算法激活的OVS數(shù)比HPR算法多,但是其吞吐量卻是最低的,即便激活了新的OVS,Dijkstra算法在后續(xù)中繼節(jié)點的選擇中依然傾向于那些已經(jīng)激活且可以實現(xiàn)更小跳數(shù)的OVS,而LBB算法和IDDFS算法則通過及時激活其余休眠OVS,有效解決了前期用戶占用帶寬以及網(wǎng)絡帶寬占用率傾斜所導致的流量負載不均衡問題,避免了節(jié)點資源的浪費。

4.3 固定用戶數(shù)及改變網(wǎng)絡中的OVS數(shù)量對不同解決方案的影響

圖6給出了不同OVS數(shù)量對4種算法性能的影響。在圖6(a)和圖6(b)中,網(wǎng)絡拓撲中的接入用戶數(shù)固定為25;在圖6(c)和圖6(d)中,網(wǎng)絡拓撲中的接入用戶數(shù)固定為50。

圖6 不同的OVS數(shù)量對不同解決方案的影響Fig.6 Impact of number of OVSs on different solutions

由圖6(a)可以看出,當固定用戶數(shù)量為25時,隨著OVS數(shù)量的增多,Dijkstra算法激活的OVS數(shù)從8增加至18,HPR算法從7增加至16,LBB算法也從8增加至18,IDDFS算法從10增加至20。

從圖6(b)可以看出,當OVS數(shù)量超過30時,其網(wǎng)絡吞吐量增加速率達到最快,此時吞吐量增加率達到33.7%。LBB算法和IDDFS算法在OVS使用數(shù)以及網(wǎng)絡吞吐量兩項關鍵性能指標上均明顯優(yōu)于HPR算法和Dijkstra算法,這是因為HPR算法優(yōu)先選擇其先前已經(jīng)激活的OVS構建數(shù)據(jù)通信路徑,Dijkstra算法則是優(yōu)先選擇跳數(shù)最少的鏈路,造成了許多可用鏈路的浪費。這兩種算法都容易造成部分路徑的擁塞,從而導致數(shù)據(jù)的損失。LBB算法和IDDFS算法通過將網(wǎng)絡中的數(shù)據(jù)流量均勻地分配到網(wǎng)絡中的其他鏈路,有效地減少了路徑擁塞的概率,提高了網(wǎng)絡的吞吐量。

從圖6(c)可以看出,當固定的用戶數(shù)量為50時,Dijkstra算法激活的OVS數(shù)從7增加至18,HPR算法從7增加至16,LBB算法從10增加至23,IDDFS算法從15增加至35,IDDFS算法的資源利用率最大。

從圖6(d)可以看出,Dijkstra算法的網(wǎng)絡吞吐量從400 Mb增加至1 250 Mb,HPR算法的網(wǎng)絡吞吐量從580 Mb增加至1 530 Mb,LBB算法的網(wǎng)絡吞吐量從810 Mb增加至2 570 Mb,IDDFS算法的網(wǎng)絡吞吐量從1 230 Mb增加至3 580 Mb。

表2給出了接入用戶數(shù)為25時網(wǎng)絡中OVS的平均使用數(shù)、最大利用率和平均利用率;表3給出了接入用戶數(shù)為50時網(wǎng)絡中OVS的平均使用數(shù)、最大利用率和平均利用率。圖6以及表2、表3反映了當網(wǎng)絡規(guī)模增大(當接入用戶數(shù)從25增加至50)時,IDDFS算法的資源利用率以及網(wǎng)絡吞吐量相較于其余3種算法的優(yōu)化效果更加明顯,IDDFS算法更適用于大規(guī)模通信網(wǎng)絡的數(shù)據(jù)傳輸。

表2 OVS激活情況(接入用戶25個)

表3 OVS激活情況(接入用戶50個)

5 結 論

本文針對5G網(wǎng)絡中支持SDN架構的資源分配優(yōu)化問題,利用SDN架構的特點及優(yōu)勢,考慮網(wǎng)絡流量負載均衡,改進了HPR算法。其中,LBB算法通過對虛擬網(wǎng)絡設置動態(tài)流量負載均衡控制閾值的方式實時優(yōu)化了網(wǎng)絡鏈路的拓撲結構,而IDDFS算法通過限制每次搜索的深度,減少甚至避免了不必要的搜索,縮減了空間開銷。LBB算法和IDDFS算法充分考慮了流量負載均衡問題,提升了網(wǎng)絡路徑的傳輸效率以及網(wǎng)絡總吞吐量,提高了網(wǎng)絡資源利用率,優(yōu)化了網(wǎng)絡資源配置效率。仿真結果驗證了本文所提兩種算法在數(shù)據(jù)轉(zhuǎn)發(fā)方面的優(yōu)異性能。