基于SDN 的多目標路徑優化算法研究

潘曉君

(安徽工商職業學院信息工程學院，安徽合肥 231131)

0 引言

軟件定義網絡（Software Defined Networking，SDN）[1]通過分離控制平面與數據平面，將控制權移到軟件控制器中，把復雜性操作從硬件中移開，致使硬件只需關注轉發流量，更加趨于簡單化，使得傳統網絡在滿足當今復雜需求方面的局限性問題能夠得到很好解決.

隨著網絡中應用程序的不斷更替，程序的業務需求也越來越趨于多元化，這就要求集中控制平面需要在較短時間內完成對不同數據流量需求的路徑計算.因此，針對SDN 網絡中快速有效的路徑優化方案的研究就顯得尤為重要.

1 多目標路由優化框架

多目標優化問題的通常解決方法是找到一組稱為Pareto 最優集的最優折中解[2].Pareto 最優集是對于每個不同目標都具有獨立支配能力的解，且不會被其它解所支配.在SDN中，當網絡的交換機收到一條新的數據流時，會首先檢查自身已有的數據流表，對該數據流進行逐項匹配.若沒有匹配項，就將數據流以Packet_in 消息的形式發往控制器，控制器對數據流的處理方式會依據最短路徑算法進行運算，并將運算結果以Packet_out 消息的形式下發到路徑中的所有交換機中[3].但這種路由策略沒有將網絡拓撲中相關的鏈路資源（如網絡鏈路剩余帶寬、鏈路時延、鏈路丟包率）考慮其中，在網絡中數據流量較大時，這種路由方法較容易形成網絡的擁塞[4].

由于多目標路徑優化算法會依據鏈路資源信息進行路由決策，因此在設計路由策略時，要求控制器能夠實時獲取網絡中的相關資源信息，包括網絡拓撲結構信息、網絡鏈路資源信息、交換機節點個數等.

多目標路徑優化框架如圖1所示，控制器利用Hello、Packet_in、Packet_out、Flow Stats 等模塊與交換機進行數據交互.

圖1 多目標路徑優化框架

2 多目標路徑優化算法設計

多目標路徑優化算法流程如圖2所示，主要包括種群數量、初始化鏈路資源、多目標函數確定、選擇操作、交叉及變異操作.下面將對流程圖中的每個操作內容做詳細介紹.

圖2 多目標路徑優化算法流程

2.1 鏈路資源信息概述

將收集到的鏈路信息及網絡拓撲信息轉換成一個具有m個節點h條連接的無向圖G(V，E)[5-6].其中V表示網絡中節點，E為被檢測到的鏈路，且有|V|=m，|E|=h.對于備選路徑，遺傳算法中的染色體則可以表示為一個三維組合(X，Link，Y)，其中X代表的是源主機，Y代表的是目的主機，Link則為從源主機到目的主機間的不重復路徑的鏈路集合，即Link={l1,l2,…,lt}(1 ≤t≤h).

具體參數介紹說明如下：

（1）網絡鏈路帶寬biq：鏈路帶寬為網絡拓撲初始化值；

（2）網絡鏈路剩余帶寬alq：當網絡數據流確定其轉發的路徑后，控制器則會下發轉發流表至交換機，交換機節點間的鏈路剩余帶寬是由網絡中的監控模塊進行計算得出，一般情況下，鏈路的剩余帶寬越大，則此條鏈路被選中的概率越高；

掌握公司設備技術狀況及配置情況，負責設備按拆施工，根據生產實際情況制定維修計劃，對設備實施維修，確保生產能力和產品質量要求，做好設備事故分析，做好處理和上報工作，負責建立設備技術資料檔案，完善各種設備資料，定期對設備開展大檢查，排查不安全因素和隱患，并提出整改意見，參與設備更新、改型等工作。

（3）網絡鏈路帶寬利用率ulq：表示被選路徑發生擁塞的可能性，它由鏈路總帶寬及鏈路剩余帶寬共同表示，其表達式為

（4）鏈路時延dlq：在SDN 網絡中，控制器發送地址為mac地址的廣播數據包；

（5）鏈路丟包率plle：該參數在網絡資源信息初始化時設置，依據每條鏈路上的資源信息可計算得出對于一條被選路徑上的總資源信息.

路徑剩余帶寬的表達式為

路徑剩余帶寬的表達式為

路徑總時延為

路徑總丟包率為

2.2 多目標函數的約束

要實現多目標路徑的優化功能，首先是要進行多目標函數的確立.確定多目標函數，主要考慮被選路徑上的總時延、剩余總帶寬、總丟包率等參數.依據式（1）、（3）、（4）可確定多目標路徑優化算法中的目標函數分別為

這里Link為被選路徑，適應度函數值越大，則被選路徑越容易產生其后代，所以采用的目標函數為路徑既要鏈路上剩余帶寬較大、又要確保鏈路時延及數據丟包率較小.

多目標優化算法中需要確定網絡擁擠度算子，這需要對上面三個目標函數進行歸一化操作，這里面使用消除量綱影響最簡易的操作即離差標準化[7].具體運算公式如下：

3 實驗環境與結果分析

3.1 實驗環境

為驗證本文提出的多目標路徑優化算法的性能，這里在SDN 上進行仿真實驗.在軟件定義網絡中，多目標路徑優化算法中的網絡信息主要包括節點與鏈路資源信息.為實現多目標路徑優化，該算法中的network_monitor（網絡監聽）模塊需要每經過一定的單位時間t1進行一次監聽.如果監聽到網絡中數據流所需帶寬超過目前路徑中的鏈路帶寬閾值或數據鏈路利用率較高時，network_configu?ration（網絡配置）模塊便開始進行一次新的多目標路徑優化操作.首先利用鏈路發現協議來識別網絡中的所有轉發路徑，通過染色體編碼方案生成初始種群，然后運用多目標函數來尋找第一代子代個體，接著進行非支配選擇、交叉與變異操作產生新的子代，并將上一代與這一代合并來獲取最優個體.為了維護網絡狀態的多目標最佳路徑，反復使用算法進行重路由.

實驗環境所用參數如表1所示.

表1 實驗環境參數表

3.2 實驗結果與分析

3.2.1 吞吐量

為了反應多目標路徑優化算法的性能，將該算法與最短路徑算法[8]在網絡數據吞吐量、數據鏈路利用率、平均時延及數據丟包率等參數進行比較.

本文的多目標路徑優化算法與最短路徑算法數據轉發后的鏈路吞吐量對如圖3所示.當客戶端發送速率逐步增大時，可以有效的降低網絡發送擁塞的概率，網絡丟包的情況也隨之減少，進而提高了數據鏈路的吞吐量.

圖3 吞吐量比較

3.2.2 鏈路利用率

平均鏈路利用率對比結果如圖4所示，最短路徑算法根據路徑中交換機節點數最少進行選路，導致客戶端發送速率逐漸增大時其鏈路利用率依然較小且變化不大.與最短路徑相比，多目標路徑優化算法平均鏈路利用率有所提高.

圖4 鏈路利用率比較

3.2.3 平均時延

隨著客戶端數據發送速率的不斷增大，兩種路由算法的平均時延的變化如圖5所示.相對于最短路徑算法，本文的多目標路徑優化算法的時延增幅明顯小于它.最短路徑算法由于沒有考慮鏈路剩余帶寬大小與數據流所需帶寬大小之間的關系，從而導致流量發送速率較大時的轉發時延變化較大，網絡發送擁塞的概率增大.

圖5 平均時延比較

3.2.4 丟包率

圖6 顯示的為多目標路徑優化算法與最短路徑算法在不同發送速率下的數據丟包率的情況.最短路徑算法在數據流量較小時，它的網絡丟包率較小，但當數據流量較大時，若將所有流量按最短路徑進行轉發，非常容易形成數據鏈路資源的短缺，進而導致網絡的擁塞，網絡數據的丟包率也隨之加快.

圖6 丟包率比較

4 結語

由于SDN 網絡是基于跳數的最短路徑轉發策略，當有大數據流量情況下，這種策略非常的不靈活，極易形成網絡的擁塞，進而影響網絡的服務質量.依據SDN 網絡的結構特點，在控制器中添加多目標路由優化模塊，通過多目標路由優化算法選出最佳的轉發路徑.實驗結果表明，與傳統的最短路徑路由算法相比，本文提出的多目標路由優化算法在數據吞吐量、通信鏈路利用率、鏈路時延以及數據丟包率等性能方面均具有較好的提升，使網絡發生擁塞的概率大幅降低，為SDN 網絡的進一步研究，提供了一定的技術支持.