基于SDN 的多目標路徑優(yōu)化算法研究

潘曉君

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

0 引言

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

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

1 多目標路由優(yōu)化框架

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

由于多目標路徑優(yōu)化算法會依據(jù)鏈路資源信息進行路由決策，因此在設計路由策略時，要求控制器能夠?qū)崟r獲取網(wǎng)絡中的相關資源信息，包括網(wǎng)絡拓撲結構信息、網(wǎng)絡鏈路資源信息、交換機節(jié)點個數(shù)等.

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

圖1 多目標路徑優(yōu)化框架

2 多目標路徑優(yōu)化算法設計

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

圖2 多目標路徑優(yōu)化算法流程

2.1 鏈路資源信息概述

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

具體參數(shù)介紹說明如下：

（1）網(wǎng)絡鏈路帶寬biq：鏈路帶寬為網(wǎng)絡拓撲初始化值；

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

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

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

（4）鏈路時延dlq：在SDN 網(wǎng)絡中，控制器發(fā)送地址為mac地址的廣播數(shù)據(jù)包；

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

路徑剩余帶寬的表達式為

路徑剩余帶寬的表達式為

路徑總時延為

路徑總丟包率為

2.2 多目標函數(shù)的約束

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

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

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

3 實驗環(huán)境與結果分析

3.1 實驗環(huán)境

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

實驗環(huán)境所用參數(shù)如表1所示.

表1 實驗環(huán)境參數(shù)表

3.2 實驗結果與分析

3.2.1 吞吐量

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

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

圖3 吞吐量比較

3.2.2 鏈路利用率

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

圖4 鏈路利用率比較

3.2.3 平均時延

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

圖5 平均時延比較

3.2.4 丟包率

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

圖6 丟包率比較

4 結語

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