SDN驅動的網絡流量負載均衡路由優化算法

閔曉飛, 李 靖, 張朝輝

(西安電子科技大學數學與統計學院, 陜西 西安 710126)

0 引 言

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

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

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

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

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

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

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

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

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

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

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

1 網絡模型與系統建模

1.1 網絡模型

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

表1 符號對照表

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

圖1 網絡拓撲示意圖Fig.1 Network topology skematic diagram

1.2 問題的數學建模

(1)

(2)

(3)

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

Ti,j≤wi,j×xi,j

(4)

(5)

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

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

2 LBB優化算法

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

為了避免局部流量負載過大,同時提高節點資源利用率,并且盡可能地減少網絡OPEX,LBB算法在實現過程中加入了一個動態流量負載均衡閾值,具體路徑優化過程如算法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

定義流量負載均衡參數公式

(6)

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

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

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

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

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

3 IDDFS優化算法

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

IDDFS算法的具體路徑優化過程如算法2所示,初始化后與算法1相同,執行步驟(3)～步驟(5),對虛擬網絡拓撲進行優化處理。在步驟(6)中,從給定的最小深度mindepth開始,按照帶寬大小進行深度優先搜索,如找到目標節點(即服務器S),則輸出搜索路徑,否則加一跳深度繼續搜索下一層,直至搜索到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算法的網絡拓撲實現過程示例圖。如圖3(a)所示,在LBB算法中,當用戶1申請接入10 Mbps的帶寬時,直接進行BFS搜索。在搜索過程中,OVS 1、OVS 2、OVS 3、OVS 4、OVS 5、OVS 7、OVS 6、OVS 9按層次存儲在堆棧中。最后,激活的節點是OVS 1、OVS 4。而在IDDFS算法中,每次搜索之前都會設置一個最小搜索深度。如在圖3(c)中,如果設置最小搜索深度為2,選擇OVS 1和OVS 7存儲在堆棧中,但是不能找到目標結點(即服務器節點 9),則需要將最小搜索深度增加1,再次進行DFS搜索,此時存儲的虛擬節點為OVS 1、OVS 7、OVS 9,最終激活了OVS 1、OVS 7進行數據傳輸。雖然兩個算法激活的OVS數量都是兩個,但IDDFS算法在尋路過程中需要的堆棧存儲空間比LBB算法少得多。

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

4 仿真實驗

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

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

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

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

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

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

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

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

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

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

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

4.3 固定用戶數及改變網絡中的OVS數量對不同解決方案的影響

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

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

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

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

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

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

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

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

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

5 結 論

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