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

0 引言

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

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

1 研究現(xiàn)狀及研究意義

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

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

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

表1 服務質(zhì)量項目及含義

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

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

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

2 流量控制算法建模

2.1 QoS流分類

通過監(jiān)控流表項中流表優(yōu)先級、ToS 服務類型字段，獲得QoS 數(shù)據(jù)包的業(yè)務類別、優(yōu)先級、延遲時間等控制參數(shù)。將業(yè)務流按照SLO進行劃分，分類如下。

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

類型2：傳輸時延目標。如實時傳輸?shù)囊粢曨l流，超過某一時延，將會產(chǎn)生用戶可感知的明顯卡頓，影響用戶體驗。

類型3：傳輸丟包率目標。如對丟包率容忍度低的網(wǎng)絡(luò)檢索、網(wǎng)絡(luò)游戲等交互類業(yè)務，超過一定丟包率將影響數(shù)據(jù)交互和用戶體驗。

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

2.2 控制算法模型

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

2.3 控制算法建模

圖1 算法流程圖

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

算法規(guī)則：采用分層思想，將網(wǎng)絡(luò)拓撲每一個業(yè)務流的傳輸作為賦權(quán)拓撲圖G分層的支撐子圖。檢測周期T內(nèi)獲得的網(wǎng)絡(luò)鏈路參數(shù)，建立網(wǎng)絡(luò)相鄰節(jié)點權(quán)值［bij，dij，lij］矩陣：

其中，不相鄰節(jié)點間的權(quán)值為：wij=［0，∞，1］，表示不相鄰節(jié)點間直連鏈路帶寬為0，時延為無窮大，丟包率為100%。確定了相鄰節(jié)點權(quán)值矩陣就確定了網(wǎng)絡(luò)拓撲連接及網(wǎng)絡(luò)參數(shù)。

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

其中，i、j為鏈路est的任意相鄰中間節(jié)點vi到vj編號。由目標函數(shù)，可以實現(xiàn)路由鏈路的計算。

由于QoS業(yè)務流的服務質(zhì)量是以業(yè)務流的優(yōu)先級進行先占排序計算路由的，在衡量算法是否達到保障QoS 的SLO，就要體現(xiàn)出流量優(yōu)先級的評價作用。按照完成用戶SLO的情況程度，對其進行評價，評價值設(shè)為Dest，定義為QoS 業(yè)務流優(yōu)先級加權(quán)的SLO 完成結(jié)果的期望值。當網(wǎng)絡(luò)的路由分配滿足QoS 業(yè)務流的SLO時，計完成目標值設(shè)為Cst，p，則有：

主要算法描述：

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

輸出：QoS流路由，Dest值。

a）收集并建立網(wǎng)絡(luò)拓撲：G（V，E，W）。

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

c）根據(jù)源、目的節(jié)點地址，用避圈法得到所有無環(huán)路徑Pst=Kruskal（vs，vt）。

d）根據(jù)SLO 約束優(yōu)先級順序，結(jié)合約束條件（1）、（2）、（3）逐條循環(huán)計算符合SLO 矢量值（Ov，Od，Ol）的所有Pst，剔除不符路徑。

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

3 仿真和結(jié)果分析

3.1 仿真環(huán)境

實驗采用的拓撲如圖2 所示，鏈路標示為節(jié)點直連鏈路的網(wǎng)絡(luò)指標參數(shù)。使用Mininet軟件生成拓撲，F(xiàn)loodlight 作為控制器，Iperf 來生成數(shù)據(jù)流，Wireshark抓包分析。

3.2 仿真及結(jié)果分析

在網(wǎng)絡(luò)中通過Iperf產(chǎn)生32組定義了1-8優(yōu)先級3類QoS 數(shù)據(jù)流，隨機依次發(fā)送，為簡便計算，將所有數(shù)據(jù)流的SLO 值統(tǒng)一設(shè)置為（25，100，0.18），在此SLO 下計算所提算法最終評價值Dest，并與QoS-aware routing算法［9］和LARAC QoS 算法［10］測試結(jié)果進行了對比，如圖3所示。

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

4 結(jié)束語

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

圖2 實驗拓撲

圖3 仿真測試結(jié)果