一種基于QoS和動態負載均衡的路由策略

孫 杰，李 莉，沈蘇彬

(南京郵電大學 計算機學院、軟件學院，江蘇 南京 210003)

一種基于QoS和動態負載均衡的路由策略

孫 杰，李 莉，沈蘇彬

(南京郵電大學 計算機學院、軟件學院，江蘇 南京 210003)

為了提高SDN網絡負載均衡調度的針對性和準確性，設計了SAS(Scheduling According to Stickiness )算法。該算法提出了鏈路粘值的概念，用鏈路粘值預估調度對流性能影響的大小，通過優先調度粘值低的流來減小調度對流性能的影響，達到優化調度的目的。在重路由過程中，該算法兼顧了流的QoS需求，并用近似算法進行多QoS約束的最優路徑選擇。基于Floodlight開源控制平臺設計和實現了相應的原型系統，并根據負載均衡效果和負載均衡生成流的QoS兩個測試目標，設計和實現了測試的方案。實驗測試結果表明，在不同QoS需求的數據流競爭網絡資源、導致網絡負載偏離均衡狀態的情況下，相較DLB、LABERIO機制，提出的技術方案在提高帶寬利用率的同時可以兼顧分組流的QoS需求，并且可以降低對流性能的影響。

軟件定義網絡；路由策略；動態負載均衡；鏈路粘值

0 引 言

隨著大量的網絡設備和服務的出現，SDN(Software-Defined Networking)[1]網絡也慢慢成為一個新的研究熱點。與傳統的分布式IP網絡的不同之處在于它對控制平面與轉發平面的分離。SDN網絡是一種不需要控制邏輯和數據轉發功能緊耦合在網絡設備上，控制器利用控制-轉發接口[2]對數據平面的交換機進行集中式控制的新型網絡體系結構。SDN交換機以提取并解析分組頭域，逐級與流表項進行匹配，按照其中指定的動作進行處理和轉發的通信模式，可以靈活地實現節點的數據傳輸。新型網絡業務被廣泛應用，網絡業務類型不斷增加，網絡擁堵越來越嚴重。實現負載均衡可以優化利用網絡資源，提高網絡資源的使用率。研究SDN網絡負載均衡解決方案具有很大的實用價值。

已有一些經典的SDN網絡負載均衡解決方案。比如，文獻[3]中提出的負載均衡模型,考慮到網絡擁塞和服務器負載，使用平均響應時間和網絡最新狀態，為網絡應用的請求合理分配。文獻[4]中提出了一種支持多服務的OpenFlow負載均衡,對于不同的服務有不同的控制器用于處理，不同的控制器的負載均衡算法選擇可以是不同的。文獻[5]中提出了基于通配符匹配的負載均衡算法，以發起請求的客戶端IP地址作為通配符前綴，接著用規則集來控制交換機，從而減少控制器進行干預的次數，降低了平均請求延遲。

文中認為不同類型的流其QoS受調度的影響程度不盡相同。網絡中的數據流有時延敏感的小數據流和吞吐量敏感的大數據流[6]。在網絡負載不均衡程度超過一定值時，在同樣都能起到均衡負載的情況下，調度前一種對QoS的影響要遠大于后一種，所以應該選擇后者調度。文中提出的調度策略不僅考慮到傳統流的分類，而且考慮到調度可能對流的QoS性能指標產生的影響大小，因此更有針對性。這里將所引入的流的適合調度值借用了一個物理學中的概念-鏈路粘值(stickness)來表述，并使用改進的動態負載均衡算法更新鏈路粘值。

算法通過北向接口完成對流鏈路粘度的初始區分，這個過程其實是獲取業務對流鏈路粘度的需求過程。在改進的動態負載均衡算法更新下，多次被調度的流的鏈路粘值會不斷增大，對調度的拒絕程度越來越高。這時，即使是初始的鏈路粘值很高的流，也會被合理地調度到。在動態重路由的過程中，算法兼顧了流的QoS需求，為流尋找一條有足夠資源、能滿足QoS要求的可行路徑。對于這種具有NP難度的多目標選路問題，文中選擇了一種現有的帶多約束的最優路徑算法-Iwata[7]，作為一個具體的計算方案。帶著這樣的目的，理論上便可以在滿足流QoS需求的同時，保證動態負載均衡調度的針對性和準確性。

1 相關技術分析

相較于傳統網絡中的負載均衡策略，在SDN網絡中主流的支持負載均衡機制都基于SDN控制器的全局視野。SDN控制器對網絡狀態進行檢測，利用根據鏈路負載的實時狀態對影響負載均衡的最大流進行調度的負載均衡策略。該策略的代表算法為LABERIO[8]。SDN控制器查詢鏈路負載的狀態作為動態負載均衡的選路依據，每次都使用貪心策略選取當前空閑帶寬最大的鏈路。該策略的代表算法為DLB[9]。

在算法LABERIO中，考慮到僅僅依靠SDN網絡的初始路由計算，即使在剛開始滿足負載均衡的需求，也會隨著網絡的變化變得不再滿足，并不能保證傳輸數據過程中的網絡動態負載均衡。為此，需要對SDN網絡的狀態進行周期更新，實時監控網絡負載均衡程度，對負載過重的鏈路上的流量進行調度，以使網絡實現動態負載均衡。對負載過重的鏈路上的流量進行調度時，優先對網絡中負載均衡影響最大的流進行調度。但是這種算法忽略了流對QoS的要求，可能會使有些流因為調度而導致時延過大。算法對那些時延敏感的流并不合適。

在算法DLB中，將流作為更小的單元，采用了深度優先的算法，開始從源節點向上傳輸到高層次的節點直到第一層節點，然后繼續往下轉發目的節點。在每一跳DLB算法用貪心策略來選擇更大的空閑帶寬的鏈路。DLB算法在SDN網絡有著比傳統負載均衡算法更好的性能。但貪心路由決策沒考慮整個網絡的負載分布，由算法選出的源節點到目的節點的路徑可能并不合適。

上述介紹的機制都是基于SDN網絡的動態重路由機制[8]并已驗證其有效性。同樣是通過動態的重路由機制解決SDN網絡中的負載均衡問題,文中采用的算法更多關注了調度對流的性能所造成的影響。顯而易見，參照測算出的重路由對流產生的影響信息，盡量選擇影響小的流進行重路由，比僅在初始設定流的優先級更有針對性和準確性。SAS算法中用鏈路粘值作為流拒絕重路由程度的量化的值。動態地測算流的鏈路粘值，并按照鏈路粘值來對流進行調度，能較好地解決SDN網絡中的動態負載均衡問題。

2 問題分析與方案設計

2.1 動態負載均衡的路由方案

在介紹基于QoS和動態負載均衡的路由方案之前，這里先定義一個負載均衡參數ε(t)，用來描述在t時刻全網負載均衡的程度。ε(t)值越趨近于0表示全網鏈路的負載越均衡，ε(t)值越大表示全網的負載越不均衡。ε(t)值的計算如式(1)所示。

(1)

(2)

(3)

其中，Bt表示在t時刻鏈路l:[il,jl,CAPl]上已傳輸的總byte。每條鏈路上的Bt值都可以通過SDN數據統計機制來獲取。

這里需要設置一個負載均衡閾值ε*。ε*值的設置依據是不同ε*值會導致不同網絡吞吐量，研究吞吐量與ε*的變化關系并選取使得網絡吞吐量最大的ε值作為ε*。當ε(t)在t時刻大于ε*(即網絡負載不均衡程度超出預設值時)，觸發聯合路由方案啟動負載均衡調度。控制器將找到占據在最擁堵鏈路上且鏈路粘值最小的流，將其移動到其他可用的路徑上。這里的可用路徑需要滿足兩個條件：路徑是包含首尾節點的通路；路徑上的所有鏈路可以滿足流f所屬類型c的QoS需求(即滿足式(5))。在計算出所有可用路徑的集合后，選擇其中負載最小的路徑作為流f的替換路徑。如果沒有可替換的路徑表明流f對當前鏈路的依賴程度(即粘值)高出了預期，則為流f增加一個定值s作為新的sf再重新執行啟動負載均衡的調度。基于QoS和動態負載均衡的路由方案步驟的具體描述如下：

步驟1：控制器不斷檢測網絡的負載均衡狀態，每隔ns計算一次網絡的負載均衡參數ε(t)值。如果ε(t)大于閾值ε*,執行步驟2，否則繼續執行步驟1。

步驟2：找出負載最大的鏈路，即loadij(t)值最大的鏈路l:[il,jl,CAPl]。執行步驟3。

步驟3：找出鏈路l:[il,jl,CAPl]承載的所有流中鏈路粘值sf最小的流f。執行步驟4。

步驟4：找出所有流f的可用替代路徑pf集合。路徑pf的首節點為ni、尾節點為nj(即為ni→nm→nj序列)，pf滿足式(2)。如果pf集合不為空則執行步驟5，否則執行步驟7。

步驟5：選擇pf集合中負載最小的路徑min(pf)(如果有多個負載最小的路徑，則選擇其中剩余帶寬最大的路徑)作為流f的替代路徑。執行步驟6。

步驟6：刪除鏈路l:[il,jl,CAPl]上f的表項。安裝min(pf)上f的流表項，建立并關聯相應計量表項。執行步驟7。

步驟7：更新流f的鏈路粘值sf。如果流f遷移成功，執行2.3中的流f鏈路粘值更新策略，未成功則sf加上一個常數值s作為新的sf。繼續執行步驟1。至此，聯合路由選擇的一個周期結束。

基于QoS和動態負載均衡的路由算法依據網絡當前的負載均衡狀態對過載鏈路進行動態的流調度，通過數據流的鏈路粘值來描述數據流對流調度的拒絕程度，進而得到應當對哪條流進行調度。因此算法的時間復雜度直接取決于鏈路個數nl和數據流的個數nf，為O(nl*nf)。

2.2 基于QoS約束的選路策略

在SDN網絡這種基于流的網絡架構中，可以區分并保證每一個業務流的服務質量，完成最細粒度的服務質量保證。而SDN網絡擁有的網絡全局視野更能夠滿足業務流對鏈路的需求。邊界交換機將數據流分類后，要為數據流分配能夠滿足數據流相應需求的路徑。數據流f可以用源節點sf、目的節點df、服務類別cf這三個屬性來表示(f:[sf,df,cf],sf∈N,df∈N,cf∈C)。其中，C代表所有服務類別的集合。服務類別包含的參數包括數據速率rc、丟包率pc、時延tc和用來為動態負載路由算法服務的初始鏈路粘度sc(c:[rc,pc,tc,sc])。這里借用了粘值(Stickiness)的物理學概念。物理學中的粘值[10]是指流體的內摩擦表現出的宏觀屬性，這里的粘值表示服務類別c的數據流f對當前的鏈路的依賴性或者稱為數據流對重路由的排斥程度。這個變量的定義將在2.3小節加以具體描述。

(4)

路由選擇需要考慮鏈路能否滿足數據流所屬類型的QoS值。當網絡中增加一個新流f(流所屬類別的屬性為rnew,pnew,tnew和snew)。流f流經的所有鏈路l都需要滿足式(5)～(7)。

(5)

(6)

(7)

其中，fl表示在鏈路l上承載所有的流集合；nf表示流f流經的所有的交換機集合；CAPl表示鏈路l的最大容量;pfsrc，pfdst分別表示在流f轉發路徑的起始交換機fsrc和目的交換機fdst上已接收到的流f包的總數。

常規的網絡時延包含處理時延、排隊時延、傳輸時延、傳播時延。這里的tl不僅僅包含鏈路時延，文獻[12]將傳輸時延和傳播時延合起來作為鏈路時延(例如ns2仿真器)。這里的tl不僅包含傳輸時延和傳播時延，還包含了跟控制器的交互。因此，在式(7)中大于號右邊減去了節點ni和控制器交互的時延dc_ni。

為了方便計算tl，文中提出了用于SDN交換機的服務質量監測機制，即一種基于OpenFlow協議實現的鏈路時延測算機制。在LLDP(LinkLayerDiscoveryProtocol[13]，鏈路層發現協議)分組基礎上進行改進，采用鏈路時延監測分組(LinkDelayDiscoveryPacket,LDDP)來監測鏈路l從鏈路源節點nlsrc(nlsrc∈N)接受到分組到鏈路l目的節點nldst(nldst∈N)接受到分組的時延。LLDP是IEEE定義的一種鏈路層協議，被大部分網絡設備所支持，一些OpenFlow控制器利用該協議實現網絡拓撲的發現功能。

而LDDP分組通過控制器發出分組到鏈路l的端節點。LDDP分組內容包括鏈路l的源節點mac地址maclsrc、鏈路l的源節點端口portlsrc、控制器在nlsrc處理此LDDP分組時的時刻tlsrc(LDDP:[maclsrc,portlsrc,tlsrc])。LDDP分組發出后其中的動作字段為轉發到節點的指定端口。LDDP分組從節點nlsrc的端口轉發出去，對端節點nldst將會收到傳入的LDDP分組，但它并不能識別這個LDDP分組，只當普通數據報文處理，此LDDP分組將被交換機封裝成Packet-In消息發送到控制器中。控制器將LDDP分組中的maclsrc和tlsrc消息記錄下來，根據maclsrc和當前節點mac標記出鏈路l，根據當前系統時刻tldst、l源節點處理時刻tlsrc即可求出鏈路l的時延t1，其值如式(8)所示。

tl=tldst-tlsrc

(8)

文中對控制器c與節點ni間的時延dc_ni(包括控制器處理發送OpenFlow請求到控制器接收OpenFlow響應之間的時延)的計算，這里的OpenFlow請求和響應，文中使用的是特征請求消息和特性響應消息。在控制器向將節點ni發送特征請求消息時記錄下當前時刻tc_ni，當控制器接收到相應節點的特性響應消息時記錄下時刻tni_c。如此，dc_ni的值通過式(9)得出。將式(8)和式(9)帶入式(7)，即可完成對路徑是否滿足流時延要求的判斷。

(9)

因此，在進行重路由之前需要先選取全網所有滿足式(5)～(7)的鏈路。選出的鏈路信息用來為動態負載均衡重路由選取提供拓撲結構。

當新的流需要進行重路由時，它需要的路徑不僅要滿足2.1節的替換路徑的要求，還需要滿足式(5)～(7)對鏈路的要求。這種多目標的選路策略是有NP難度的，因此文中采用了一種現有的帶多約束條件的QoS路由算法-Iwata[7]，作為一種具體的計算方案。Iwata算法先以一個QoS度量為關鍵字來計算最短路徑，然后檢測該路徑是否滿足其他QoS度量；如不滿足，則選取另一QoS度量來計算最短路徑，同樣檢測該路徑是否滿足剩余的QoS度量；如此反復直到找到一條滿足所有QoS度量的可行路徑。

2.3 分組流的鏈路粘值更新策略

為了使得網絡達到動態負載均衡狀態，需要解決兩個問題：網絡鏈路過載發生的檢測和檢測到過載發生后的處理。這兩個問題已在2.1小節解答了。一旦鏈路發生過載，應對鏈路上的哪個流重路由，使網絡狀態恢復負載均衡。需要對不同的流進行區分，不同的流可以簡單分為對吞吐量敏感的流和對延時敏感的流。考慮到延時敏感流傳輸時間相對較短，改變其路徑很可能會增加延遲和開銷，因此應遷移非延時敏感流[14]。利用概念粘值，鏈路粘值sf表示數據流f對遷移的拒絕程度。而前面提到的不同的流(吞吐量敏感的流和對延時敏感的流)對更改路徑的成本高低，都可以簡單地用對遷移的拒絕程度高或低即鏈路粘值sf來表示。計算鏈路粘值如式(10)所示。

(10)

其中，sfl表示f最近一次sf值；ufl表示最近一次遷移對數據流的影響值。

通過式(10)可以看出，如果數據流f從未遷移過，它會有一個初始值sc。這個值路由模塊執行時為數據流區分的服務類型c所包含的屬性sc。這個sc其實就是控制器根據分類機制為數據流f設置的初始粘值。考慮到網絡的動態性，那些被遷移的流的鏈路粘值只有根據遷移對流的影響值來動態更新，才能保證sf的準確性。并且式中sf的計算過程實際為一個迭代過程，每一次遷移的影響值都會被考慮在內。這樣就保證了一些初始粘值較小或者每次的遷移影響值較小的流，不會被頻繁調度，保證了流調度的合理性。式(10)中影響值ufl可以通過對SDN數據統計信息的計算來完成。ufl的值如式(11)所示。

ufl=α*dfl+β*bfl

(11)

其中，dfl表示最近一次遷移流f丟包率的變化程度；bfl表示最近一次遷移流f傳輸帶寬的變化程度；α和β分別表示dfl、bfl在影響值ufl中所占的比例。

dfl，bfl分別通過式(12)和式(13)計算獲得。

(12)

(13)

其中，pt1表示t1時刻流f的總丟包數；bt1表示t1時刻流f的已傳輸的總byte。

控制器在流遷移前隔ms讀取一次鏈路的統計信息，在流遷移后隔ns讀取一次鏈路的統計信息。兩次統計信息的比值準確反映了鏈路遷移對流f的丟包率和帶寬影響。

控制器記錄并更新每條流的最新的鏈路粘值。當SDN網絡發生過載時，控制器對比過載鏈路上所承載的流的鏈路粘值并決定對哪條流進行流調度。關于根據鏈路粘值進行流調度以及調度后的路由策略已在2.1小節說明了。

由上可知，SAS是一種基于QoS和動態負載均衡的路由策略，所以在實驗部分需要使用不同類別流傳輸對動態負載均衡的實現進行功能測試，使用不同的傳輸速率對使用SAS機制后的帶寬、丟包率、抖動變化進行性能分析。

3 實驗搭建及性能分析

實驗對SAS算法系統軟件進行測試，測試環境如圖1所示。在源末主機上部署iperf發包工具，模擬端到端的不同業務流的傳輸環境。在兩種業務流傳輸情況下分別執行LABERIO、DLB以及文中的SAS系統，統計各機制運行過程中帶寬、丟包率、抖動等性能指標來進行比較。

3.1 實驗環境搭建

搭建SDN實驗網絡。首先在一臺DELL服務器上部署最新版本floodlight控制器，作為控制層設備。其次，由于目前OpenFlow物理交換機價格昂貴，文中選用一款開源的OpenFlow軟件交換機OVS安裝在三臺DELL臺式機上作為數據層轉發設備。交換機和控制器的主機系統均為32位Ubuntu 12.04，而通信的主機節點均為Windows7系統。

圖1 測試網絡拓撲圖

實驗中，三臺OVS軟件換機分別與控制器相連受控制器控制。文中將控制器IP地址設置為192.168.0.150，交換器控制端口IP地址分別設置為192.168.0.151，192.168.0.152和192.168.0.153。將通信主機與三臺交換機中的任意一臺相連，通信主機分別運行數據傳輸的客戶端和服務器端(文中是用iperf發包工具)用于發送和請求數據分組。設置負載均衡閾值ε*為1%，粘值增量常數s為1。

3.2 實驗性能評估指標

文中使用平均帶寬利用率、平均丟包率和平均抖動等性能指標對負載均衡算法的性能進行評估。

(1)平均帶寬利用率。

指定帶寬arf是指由客戶機發送流的帶寬，而實際帶寬rrf是指服務器實際獲取的流帶寬。由于傳輸期間可能發生網絡擁塞將導致分組丟失，從而服務器接收的實際帶寬小于或等于由客戶機發送的指定帶寬。平均帶寬利用率α是指每條流實際獲得的帶寬與其所指定帶寬的比值的平均值。

(14)

平均帶寬利用率反映了網絡的均衡程度，利用率越高說明網絡的負載越均衡。

(2)平均丟包率百分比。

由SDN統計機制獲得每條流的丟包信息，丟包數與傳輸指定的數目的比值就是這條流的丟包率。平均丟包率百分比β是指所有流的丟包率的平均值，如式(7)所示。平均丟包率百分比越大說明網絡擁塞程度越高，流的QoS傳輸效果越差。

(15)

(3)平均抖動。

根據iperf客戶端工具輸出的測試報告，得到每個流的抖動jf。平均丟包率百分比γ是指所有流的抖動的平均值。平均抖動越大則說明流的QoS傳輸效果越差。

(16)

3.3 實驗結果分析

圖2是在不同業務流傳輸時，三項機制的平均帶寬利用率比較。

圖2 多業務流時不同機制對平均帶寬利用率的影響

從圖中可以看到，隨著流量負荷增加，三種算法的平均帶寬利用率在逐步下降。SAS算法在平均帶寬利用率上表現一般。甚至在高流量負荷時，比LABERIO表現要差。尤其在客戶端發送速率增加至6 Mbps后，利用率平均低了3%左右。因為在重負荷之下，LABERIO算法這種優先對網絡中占用帶寬最多的流進行調度的機制，雖然忽略了流對QoS的要求，但負載均衡效果更好。在重負荷之下DBL算法的單跳最優策略更容易引發網絡的局部擁塞，增大了報文的丟包率，降低了數據流的帶寬利用率，而SAS算法在考慮全局路徑負載情況后做出的選路降低了發生擁塞的概率，相比于DBL有更高的帶寬利用率。

隨著數據傳輸速率的增加，網絡動態的調整，重新尋找滿足流QoS要求的可行路徑。相較于DLB、LABERIO機制，SAS算法使用了測算流QoS變化的負載均衡改進策略，優勢在于提高了流的負載均衡調度的針對性和準確性。

SAS通過改進的動態負載均衡算法，按鏈路粘值為流進行調度。鏈路粘值考慮到了丟包率的影響，優先調度對丟包率影響較小的流。由于SAS是多目標的計算綜合最優結果的算法，SAS相比LABERIO這種單純考慮負載均衡效果的算法，SAS會在負載均衡調度時考慮到調度對流丟包率的影響，優先調度丟包率影響較小的流而不是對負載均衡影響最大的流，因此會產生更低的網絡丟包率。作為代價，SAS算法在平均帶寬利用率上表現一般，甚至在高流量負荷時，比LABERIO表現要差。

圖3給出了3種算法的平均丟包率的實驗結果。

圖3 多業務流時不同機制對平均丟包率的影響

從平均丟包率隨流量負荷變化而變化的情況看，SAS平均丟包率最低，LABERIO平均丟包率低于DLB。整體上LABERIO好于DLB，這歸功于全局選路降低了擁塞出現的概率，減少了需經過擁塞路徑才能遞交的報文。SAS丟包率的變化趨勢跟其他算法一致，在具體數值上小了幾個百分點。當客戶端發送速率達到9 Mbps時，三種算法的平均丟包率都超過了50%，這也說明當網絡流量負荷較高時，網絡中各鏈路都較為擁堵，報文在交換機中丟包率會更高。SAS算法在平均丟包率上表現相對較好，但在高流量負荷時丟包率同樣很高。跟現有方案相比，SAS在丟包率表現上有一定程度的改進。

圖4給出了三種算法平均抖動的實驗結果。

圖4 多業務流時不同機制對平均抖動的影響

從整個曲線上看,SAS處在最下方，LABERIO處在DLB的下方。SAS在平均抖動上性能要優于LABERIO和DLB。曲線開始的一段時間內，抖動呈上升趨勢，這是因為數據流剛剛開始產生，網絡中同時傳輸的數據流還未達到最大值，只有部分鏈路上有流量經過。當傳輸的數據流達到4 Mpbs時，抖動也基本達到峰值，這之后的變化幅度相對更小。

從圖4中的抖動變化能夠看出LABERIO平均抖動性能優于DLB，相對于DLB流量分布更為均勻，網絡中的流量分配更為均衡。而LABERIO是對網絡中影響負載均衡的最大流進行調度，當調度到時延敏感的數據流時，肯定會出現流的抖動波動較大的現象。SAS按流調度對流受調度影響的歷史信息進行流調度，優先對受調度影響較小的流。因此，會產生更低的平均抖動。在具體數值上，LABERIO和DLB雖然比文中方案在數值上高了零點幾毫秒，但數據的變化趨勢相似，SAS的表現相對較好。跟現有方案相比，SAS在抖動表現上有一定程度的改進。

4 結束語

文中從調度會對流QoS產生影響的角度，盡可能利用流的調度受影響的歷史信息，提出了一種基于QoS和動態負載均衡的路由策略SAS。在floodlight控制器平臺上編寫實現SAS算法并與DLB、LABERIO進行對比。統計各項性能指標可以看出，SAS算法按照流的鏈路粘值進行調度，可以保證在滿足不同業務流QoS需求的同時，有效提高帶寬利用率，產生較低的抖動和丟包率，提高SDN網絡路由轉發的效率。

[1] Open Networking Foundation.Software-defined networking:the new norm for networks[EB/OL].2012.https://www.opennetworking.org/sdn-resources/sdn-library/whitepapers.

[2] 沈蘇彬.軟件定義聯網的建模與分析[J].南京郵電大學學報:自然科學版,2014,34(3):1-9.

[3] 張園園.利用openflow技術實現網絡負載均衡[D/OL].[2010-12-09].http://www.paper.edu.cn/releasepaper/content/201012-258.

[4] Handigol N,Seetharaman S,Flajslik M,et al.Plug-n-Serve:load-balancing web traffic using OpenFlow[J].ACM Sigcomm Demo,2009,4(5):6.

[5] Koerner M, Kao O. Multiple service load-balancing with OpenFlow[C]//IEEE international conference on high performance switching & routing.[s.l.]:IEEE,2012:210-214.

[6] Benson T,Akella A,Maltz D A.Network traffic characteristics of data centers in the wild[C]//Proceedings of the 10th ACM SIGCOMM conference on Internet measurement.[s.l.]:ACM,2010:267-280.

[7] Fujita N,Iwata A.Adaptive and efficient multiple path pre-computation for QoS routing protocols[C]//Global telecommunications conference.[s.l.]:IEEE,2001:2215-2219.

[8] Long H,Shen Y,Guo M,et al.LABERIO:dynamic load-balanced routing in OpenFlow-enabled networks[C]//IEEE 27th international conference on advanced information networking and applications.[s.l.]:IEEE,2013:290-297.

[9] Li Y,Pan D.OpenFlow based load balancing for Fat-Tree networks with multipath support[C]//Proceedings of 12th IEEE international conference on communications.Budapest,Hungary:IEEE,2013:1-5.

[10] Kovtun P K,Son D T,Starinets A O.Viscosity in strongly interacting quantum field theories from black hole physics[J].Physical Review Letters,2005,94(11):111601.

[11] Open Networking Foundation.OpenFlow switch specification,version1.3[EB/OL].2012.https://www.opennetworking.org/images/stories/downloads/specification/openflow-spec-v1.3.0.pdf.

[12] Issariyakul T, Hossain E. Introduction to network simulator NS2[M].[s.l.]:Springer-Verlag,2012.

[13] Surhone L M,Tennoe M T,Henssonow S F,et al.Link layer discovery protocol[M].[s.l.]:Betascript Publishing,2010.

[14] 樊自甫,伍春玲,王金紅.基于SDN架構的數據中心網絡路由算法需求分析[J].電信科學,2015,31(2):36-45.

A Routing Strategy Based on QoS and Dynamic Load Balancing

SUN Jie，LI Li，SHEN Su-bin

(School of Computer Science & Technology,School of Software，Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

In order to improve pertinence and accuracy of network load balancing scheduling for SDN (Software-Defined Networking),a SAS algorithm is designed.This algorithm puts forward the concept of link stickiness,and applies link stickiness to estimate the impacts of scheduling on flow performance,by preferentially scheduling flow with low stickiness to reduce the impacts of scheduling on flow performance,so as to achieve the purpose of optimized scheduling.In the process of re-routing,it takes QoS needs of flow into consideration,and applies approximation algorithm to calculate the optimal route under multi-QoS constraints.Then a prototype system is designed and implemented based on Floodlight,an open control platform.Aiming at two test targets,including the load_balancing effect and its generated flows’ QoS,the test approach is designed and implemented.Experimental test results show that in case of different QoS requirement flows competing for limited network resources and resulting in network load deviations from the balance state,compared with DLB and LABERIO,the technology approach proposed can improve the bandwidth utilization while fulfilling the requirements of QoS on flow,and reduce the influence on flow’s performance.

Software-Defined Networking;routing strategy;dynamic load balancing;link stickness

2016-01-18

2016-05-10

時間：2016-10-24

江蘇省未來網絡前瞻性研究資助項目(BY2013095-1-08)

孫 杰(1990-),男，碩士研究生，研究方向為計算機應用技術；沈蘇彬，博士生導師，研究方向為計算網絡、下一代電信網及網絡安全。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1113.028.html

TP392

A

1673-629X(2016)11-0188-07

10.3969/j.issn.1673-629X.2016.11.041