SDN中基于用戶服務(wù)等級目標(biāo)的流量控制算法

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

0 引言

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

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

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

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

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

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

表1 服務(wù)質(zhì)量項(xiàng)目及含義

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

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

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

2 流量控制算法建模

2.1 QoS流分類

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

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

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

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

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

2.2 控制算法模型

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

2.3 控制算法建模

圖1 算法流程圖

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

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

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

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

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

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

主要算法描述：

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

輸出：QoS流路由，Dest值。

a）收集并建立網(wǎng)絡(luò)拓?fù)洌篏（V，E，W）。

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

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

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

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

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

3.1 仿真環(huán)境

實(shí)驗(yàn)采用的拓?fù)淙鐖D2 所示，鏈路標(biāo)示為節(jié)點(diǎn)直連鏈路的網(wǎng)絡(luò)指標(biāo)參數(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ù)流，隨機(jī)依次發(fā)送，為簡便計(jì)算，將所有數(shù)據(jù)流的SLO 值統(tǒng)一設(shè)置為（25，100，0.18），在此SLO 下計(jì)算所提算法最終評價(jià)值Dest，并與QoS-aware routing算法［9］和LARAC QoS 算法［10］測試結(jié)果進(jìn)行了對比，如圖3所示。

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

4 結(jié)束語

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

圖2 實(shí)驗(yàn)拓?fù)?/p>

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