SDN中基于用戶服務等級目標的流量控制算法

陽 凱，林海濤（海軍工程大學電子工程學院，湖北武漢 430000）

0 引言

傳統IP 網絡配置管理存在的主要問題是監控粒度太粗，交換機和路由器的配置能力太弱，不能實施各種網絡業務的快速部署。從監控粒度來說，SDN 交換機可以在全部協議層次上進行流的區分和計數，具備對每流計數和監控的能力。SDN 控制器擁有全網所有交換設備的流表項配置能力，不僅能完成傳統網管系統做不到的路由表的配置，還可以實施各種網絡業務的配置和部署［1］。傳統IP網絡通過多策略路由表和多轉發表實現了對報文路由方式的控制，能夠實現流量的分類和傳遞，但是無法在不同端口、不同路徑上實現同一種業務的流量分配。SDN架構將交換機的控制功能和轉發功能分離開來，分成集中控制平面和數據轉發平面，可對不同交換機和路由器的流表進行修改，控制每一條數據流的流向，根據需求實現特殊的數據流量控制功能［2］。

在SDN 系統里，有獨立的中央控制器和上層應用層，轉發層只是作為最底層的數據轉發，業務編排在控制器中完成。在控制器完成具體動作過程中，SDN的流量控制算法起了決定性的作用。相對于傳統方式，SDN 為流量工程的開展提供了更好的基礎［3］。目前尚且沒有一種萬能SDN 流量控制算法能夠滿足所有QoS 業務目標的需求，自適應路由算法也只能在局部框架內進行自動調整。在不同QoS需求的網絡中針對QoS 等級目標來選擇控制算法或者算法組合，是解決此問題的有效方法。因此，為解決此問題，提出了基于用戶業服務等級目標的流量控制算法。

1 研究現狀及研究意義

傳統IP 網絡采用盡力而為的轉發模型，其特點是盡最大可能發送報文，對時延、可靠性等性能不提供有效保障［4］。因此，需要能根據網絡可用資源和數據流的QoS 需求來決定如何建立和維護路由。QoS 路由主要解決思路是，如何找到一條能夠同時滿足多個約束條件且具有最小代價的路徑滿足服務質量的需求，即解決性能約束和最優化問題。服務質量是一系列從用戶感知角度來描述系統提供服務的性能特征的參數，反映了用戶對服務的滿意程度。這些參數包括業務可用性、時延、丟包率、吞吐量等［2］。從網絡用戶體現統計結果來看，用戶關心的技術指標主要有帶寬、連通性、流量參數和網絡性能參數等［5］。

與傳統IP 網絡一致，SDN 中QoS 業務路由協議也分為3個部分，首先根據用戶應用體驗和需求，關聯網絡參數建立服務等級指標（SLI）體系，依據服務等級協定（SLA）來實施服務質量控制，以達到用戶需要的服務等級目標（SLO）。在實際的網絡保障中，管理人員需要關注的是SLI 和目標SLO，根據目標和指標選擇路由策略和算法。如表1 所示，SDN 服務質量主要包括SLI、SLO、SLA 3部分。

近年來，業界對于保障IP 網絡的QoS 數據業務提出了一系列理論和解決方案，然而傳統的互聯網架構仍然提供的是盡力而為的轉發服務，難以提供有效服務類別的保障。在QoS 技術發展歷程中，IETF 提出了幾種模型，如經典的集成服務模型IntServ 和綜合服務IntServ，但是都沒有得到全球化的成功應用，部分原因是這些架構是建立在分散的逐跳路由算法之上，而不是在全局視圖下的統一調度。利用快速標記交換，MPLS提供了一種可靠的改善QoS性能的解決方案，但是它是靜態的，不具備實時配置和適應能力。

表1 服務質量項目及含義

目前，給予QoS的路由算法積累了很多研究成果，Hedera［6］提出了一種基于模擬退火（SA）的算法，通過當前網絡狀態將流路由到不同的路徑。這項工作比傳統的ECMP（Equal Cost Multi-Path）［7］具有更好的多路徑性能。Long［8］提出了一種動態重路由算法，當SDN 控制器檢測到網絡擁塞時，使用單跳或多跳算法將流重新路由到其他路徑。與傳統的輪詢調度（RR）算法相比，該方法可以提高網絡利用率。上面提到的相關工作僅考慮一個約束，即鏈路帶寬。但是，用戶可能有多個QoS要求，為了解決這個問題，可以記錄每個應用程序的QoS 要求，并分配路由路徑來滿足QoS要求，Chienhung［9］提出了一種基于模擬退火的QoS 感知路由算法，該算法能夠在成本函數中自適應地調整延遲、丟失率和帶寬要求的權重，以根據QoS要求找到最佳擬合路徑。LARAC［10］提出了一種LARAC QoS 感知路由算法，該算法使用基于拉格朗日松弛的聚合成本方法，找到了近似的最優路徑。MINA［11］提出了一種用于物聯網的QoS 感知流量調度算法，使用遺傳算法迭代地計算滿足QoS 要求的最佳擬合路徑。然而，成本函數中的靜態權重和局部最優值難以兼具最優是MINA 的主要問題。但是由于控制器的計算能力存在瓶頸，在大型SDN 網絡中利用啟發式算法進行迭代計算路由，計算量將急劇增加，即使動態地調整多個權重優化得到綜合QoS 最優路徑，得到的也是對關鍵參數平均化后的優化路徑，與業務流的QoS 仍會存在一定偏差。

實際網絡中，服務需求不同的多種業務流均同時在網絡中傳輸，單一的路由算法往往顧此失彼，無法兼顧所有業務流的SLO。自適應算法和感知流量算法往往預先給定了加權計算模型，最終得到的路由可能是某一評價體系下的綜合最優，并不一定符合用戶的業務目標需求。同樣，類似于遺傳算法的全局最優算法得到的擬合路徑也都是在預定變量約束模式下的網絡最優，都沒有結合SLO來計算路徑。

本文所提算法充分利用SDN 全局視圖功能，掌握全網節點和鏈路的帶寬、速率、時延等重要SLI，根據用戶SLO 要求和優先級將QoS 流進行分類，建立約束模型來針對性地計算路由，因流施策，為業務流分配達到SLO要求的路由。

2 流量控制算法建模

2.1 QoS流分類

通過監控流表項中流表優先級、ToS 服務類型字段，獲得QoS 數據包的業務類別、優先級、延遲時間等控制參數。將業務流按照SLO進行劃分，分類如下。

類型1：傳輸速率目標。如高優先級的需要限時傳遞的大數據業務，要求在指定的速率限值以上完成業務傳輸，若低于傳輸速率，將影響完成時間。

類型2：傳輸時延目標。如實時傳輸的音視頻流，超過某一時延，將會產生用戶可感知的明顯卡頓，影響用戶體驗。

類型3：傳輸丟包率目標。如對丟包率容忍度低的網絡檢索、網絡游戲等交互類業務，超過一定丟包率將影響數據交互和用戶體驗。

用戶的QoS業務流SLO可能是1種，也可能有2種甚至多種，而大規模SDN 網絡中往往會發生參數路徑竟合的現象，符合的SLO 種類越多，竟合的路徑越少。按照用戶SLO 的重要性順序進行計算，可以找到篩選出符合用戶全部SLO 的路徑。由于網絡業務服務目標類型和種類繁多，僅從業務流的速率、時延、丟包率3個目標值進行討論。

2.2 控制算法模型

如圖1所示，所提算法的控制層接納控制機制為：首先在準入過程中，權衡異構網絡各自當前的負載狀況，對入流按照優先級大小排序，從端到端鏈路資源角度考慮是否能滿足業務需求，并不損害已有優先級業務的QoS 流。其次，實時地依據網絡負載狀況設置業務的接入門限，以確定不同類業務服務質量與對網絡影響的最佳協調點。而后，根據SLO 分類的QoS 策略匹配路由算法，并根據網絡監控參數執行算法計算得到最佳路由，而后映射生成流表項，下發到轉發節點。資源預留機制為：優先級由高到低，盡力而為地保證QoS流的預留網絡資源。無優先級業務不預留資源，在剩余網絡資源中以最短路徑路由算法盡力而為地轉發。

2.3 控制算法建模

圖1 算法流程圖

由于節點端口上下行鏈路帶寬和時延不同，將拓撲建模為無多重邊的簡單有向圖G（V，E），其中，V是SDN 網絡中交換機節點的集合，E為鏈路集合，包含鏈路指標參數（帶寬、時延、丟包率）。給定G中的2 個頂點vi、vj。設P是G中從vi到vj的鏈路est=［vs，vt］的集合，［est］∈Pst。每一條相鄰直連鏈路都可以用帶寬bij、時延dij、丟包率lij描述形成相應拓撲圖，直連鏈路權值為w（eij）=wij=［bij，dij，lij］。鏈路指標參數均為一個拓撲更新周期T內的統計值，假定周期內網絡拓撲參數保持不變，數據流量性能穩定。設Ov為業務流速率目標，Od為業務流時延目標、Ol為業務流丟包率目標。

算法規則：采用分層思想，將網絡拓撲每一個業務流的傳輸作為賦權拓撲圖G分層的支撐子圖。檢測周期T內獲得的網絡鏈路參數，建立網絡相鄰節點權值［bij，dij，lij］矩陣：

其中，不相鄰節點間的權值為：wij=［0，∞，1］，表示不相鄰節點間直連鏈路帶寬為0，時延為無窮大，丟包率為100%。確定了相鄰節點權值矩陣就確定了網絡拓撲連接及網絡參數。

通過避圈法計算獲得所有從vs發往vt業務流鏈路est的集合Pst，需滿足約束：鏈路最小帶寬滿足流量傳輸速度需求，鏈路累計時延不超過最大目標時延，鏈路累積丟包率不超過目標丟包率。由此建立目標方程：

其中，i、j為鏈路est的任意相鄰中間節點vi到vj編號。由目標函數，可以實現路由鏈路的計算。

由于QoS業務流的服務質量是以業務流的優先級進行先占排序計算路由的，在衡量算法是否達到保障QoS 的SLO，就要體現出流量優先級的評價作用。按照完成用戶SLO的情況程度，對其進行評價，評價值設為Dest，定義為QoS 業務流優先級加權的SLO 完成結果的期望值。當網絡的路由分配滿足QoS 業務流的SLO時，計完成目標值設為Cst，p，則有：

主要算法描述：

輸入：各QoS流的SLO矢量值（Ov，Od，Ol）。

輸出：QoS流路由，Dest值。

a）收集并建立網絡拓撲：G（V，E，W）。

b）根據流的服務類型字段將流量進行分類，從G中抽出相應服務參數的權值拓撲G（V，E，bij）、G（V，E，dij）、G（V，E，lij）。

c）根據源、目的節點地址，用避圈法得到所有無環路徑Pst=Kruskal（vs，vt）。

d）根據SLO 約束優先級順序，結合約束條件（1）、（2）、（3）逐條循環計算符合SLO 矢量值（Ov，Od，Ol）的所有Pst，剔除不符路徑。

e）對每條QoS 業務流，存在滿足SLO 業務路徑，則分配路由，令Cst，p為1，否則為0。更新網絡拓撲參數，跳轉至b）進行下一業務流的計算。所有流計算完則跳轉至f）。

3 仿真和結果分析

3.1 仿真環境

實驗采用的拓撲如圖2 所示，鏈路標示為節點直連鏈路的網絡指標參數。使用Mininet軟件生成拓撲，Floodlight 作為控制器，Iperf 來生成數據流，Wireshark抓包分析。

3.2 仿真及結果分析

在網絡中通過Iperf產生32組定義了1-8優先級3類QoS 數據流，隨機依次發送，為簡便計算，將所有數據流的SLO 值統一設置為（25，100，0.18），在此SLO 下計算所提算法最終評價值Dest，并與QoS-aware routing算法［9］和LARAC QoS 算法［10］測試結果進行了對比，如圖3所示。

從仿真測試結果可以看出，所提算法基本達到了設計目標，SLO 目標完成評價優于QoS-aware routing算法和LARAC QoS 算法。由于該算法是在符合目標約束條件下的所有通行鏈路中篩選出可行解，現有網絡資源依次用來保障業務流的QoS 需求，可在有限網絡資源中盡最大可能地為各業務流匹配路徑。而QoS-aware routing 算法是通過調整服務指標參數權重來自適應擬合路徑，改變了鏈路指標參數的相對值，影響了實際符合路徑的選擇。LARAC QoS 感知路由算法使用拉格朗日松弛模型，通過適當選取權系數來整調成本函數校正量，近似擬合路徑，在寬約束條件下能得到較好的近似松弛結果，但是由于取權系數的影響，實際計算結果和符合路徑仍會出現偏差。

4 結束語

用戶的業務流服務質量體驗是網絡服務保障的重點，從流的服務質量目標倒推合理路徑是本算法的主要思路。根據SLO 分類進行路徑約束的計算，算法復雜度低，執行速度快，準確性高，達到了用戶QoS 業務流要求目標，適合大型復雜網絡的QoS數據流應用。與已有的2 種QoS 算法相比，準確性完成度更高，更能貼合用戶的業務需求。在設計指定規模下的網絡時，其網絡容量和服務能力可以利用此算法進行計算。但是，所提算法僅僅是針對用戶SLO需求進行設計，在網絡均衡負載、資源利用率和吞吐量上缺乏設計，容易造成資源浪費和成本提升。下一步可在SLO可行解域內結合負載均衡算法進行鏈路配置，達到兼顧提高網絡資源利用率和吞吐量的目的。

圖2 實驗拓撲

圖3 仿真測試結果