基于軟件定義網絡的分層路徑規劃策略

何杰挺,王子磊,奚宏生

(中國科學技術大學 自動化系,合肥 230027)

0 概述

隨著云計算技術的日趨成熟,流媒體業務也由傳統的內容分發網絡(Content Distribution Network,CDN)、對等網絡(Peer-to-peer Network,P2P)等模式向流媒體云模式轉變。流媒體云不僅具有云計算高度動態、靈活易擴展的特性,還主動將原位于網絡核心的服務內容外推至網絡邊緣,顯著減少了用戶服務請求時延和骨干網絡流量負載。目前,已有多種形式的流媒體云平臺被提出并投入使用[1-2]。

作為一種資源密集型的服務模式,如何對其系統內部的存儲、計算、網絡等資源進行合理分配,以提升系統整體服務能力,是流媒體云資源調度的重點。而沿用TCP/IP協議族的傳統流量工程(Traffic Engineering,TE)因缺乏必要的管控能力,導致不能在有限資源下向用戶提供更好服務[3]。軟件定義網絡(Software Defined Networking,SDN)能夠較好地解決該問題,因此,其一經提出便得到了業界的廣泛關注。控制平面與轉發平面相分離的設計模式,為網絡流量的行為控制帶來了眾多機遇和優勢[4]。

在有限網絡資源下,用戶請求模式的變動會導致資源使用率的失衡和系統整體服務能力的下降。如何對SDN中的資源進行合理優化,以提升系統的整體服務能力,業界對此進行了大量的研究。文獻[5]提出一種保障視頻流端到端服務質量的動態資源分配框架,并使用帶約束的最短路徑(Constrained Shortest Path,CSP)模型為業務流提供最佳路徑。文獻[6]針對可伸縮視頻編碼(Scalabel Video Coding,SVC)提出一種自適應路由策略,通過對不同層次視頻流路徑進行優化,達到系統整體最優。但是,上述路徑規劃策略都沒有充分利用用戶請求產生的應用層信息,僅采用網絡拓撲結構和鏈路使用率對業務流進行路徑優化,容易在最短路徑上產生擁塞和丟包。因此,利用單一網絡信息對業務流進行優化的策略,不僅沒有很好的優化效果,而且不易于系統的動態擴展。

為了提升系統的優化效果,本文提出一種適用于SDN的動態路徑優化策略,使用用戶請求的區域信息,將優化問題分治為多個區域內的子問題,通過對物理網絡資源的虛擬化處理為各個用戶區域提供獨立的邏輯網絡資源。當區域使用量產生波動時,對分配結果進行動態柔性調整,盡可能多地滿足各個區域的用戶需求。在子優化問題的求解中,充分利用當前流行度信息,當視頻流行度發生變化時,綜合考慮網絡資源使用率和服務現狀,并對分配結果進行動態調整。此外,在將數據流的具體轉發規則通過SDN中心控制器下發給各交換機時,如校園網絡[7]、企業網絡[8]和數據中心網絡[9-10]的控制方式會產生眾多的流表項,為緩解流表項和交換機存儲空間間的矛盾,本文提出一種結合隊列調度的執行機制:業務流數據包在包頭攜帶特定標簽,交換機根據標簽上的路徑信息選路,根據權重信息設定轉發速率。

1 邊緣云服務模型

本文處理的一種流媒體邊緣云(Streaming Media Edge Cloud,SMEC)服務系統模型如圖1所示。SMEC部署在網絡邊緣,通過基于SDN技術的承載網絡向周邊地區提供視頻服務。由支持OpenFlow協議的控制器和交換機組成視頻流承載網絡的主體。

圖1 基于SDN的SMEC服務架構

SMEC內部由多個流媒體服務器和業務管理服務器組成。其中,流媒體服務器上部署了相應的視頻資源;業務管理服務器用于處理用戶的服務請求,并將服務信息提供給OpenFlow控制器。眾多的客戶端從網絡邊緣接入,從相同交換機接入的客戶端被抽象成一個用戶區域。

針對接入SMEC系統的眾多視頻請求,需要在網絡中分配合適的承載路徑,系統中的整體請求可以看作各個用戶區域請求的疊加。不同區域間的服務請求除了共享系統網絡資源外,還具有一定的獨立性。通過網絡資源虛擬化的手段將物理網絡按照用戶區域劃分成多個獨立子網絡,可將原路徑優化問題分治為多個用戶區域內的子問題。為了更好地分治優化問題并動態適應各個分治區域請求的波動性,本文提出如圖2所示的分層優化方案:資源虛擬化為分治問題,產生網絡切片,運用路徑規劃求解各個分治子問題。

圖2 OpenFlow控制器分層策略示意圖

在上述模型下,本文的研究問題可以描述為:在網絡拓撲G已知的情況下,利用不同視頻的流行度信息,結合當前網絡的運行狀態,通過動態調整網絡中視頻流的承載鏈路和帶寬,使得網絡資源能夠承載更多的視頻流。

2 分層路徑規劃方案

2.1 方案描述

考慮到OpenFlow交換機中有限的流表空間,本文提出一種基于隊列調度的帶寬分配方案,該方案能有效減少流表空間的占用,適用于拓撲復雜、業務繁重的SMEC等系統。

2.2 資源虛擬化策略

對完整的物理網絡進行虛擬化分割,為上層路徑規劃提供數據源到目的地的連通性保證,并根據各子網的實際網絡使用情況重新調整分割方案,使網絡盡可能多地承載業務數據流。

為使對各子網的資源分配達到網絡層面的公平,本文采用將網絡中最小割鏈路擴展為完整路徑的方法,為每個獨立的子網Gk選取J(常數)條從SMEC到用戶區域的完整路徑,并對物理網絡按上述路徑進行帶寬資源預分配,分配閾值矩陣記為M=(mkj)K×J,其中,元素mkj表示子網Gk中第j條路徑分配的閾值帶寬。當新的視頻服務需求到達時,如果子網內的整體使用流量uk沒有超過預分配值,則直接提供服務。考慮到網絡流量的波動性,當預分配值不能滿足服務流量需求時,需要對分配矩陣M進行調整。

考慮到在SDN中,控制器需要通過下發流表的方式將決策信息告之相關的交換機,且虛擬子網的閾值改變也會觸發路徑規劃策略的執行,因此,在對矩陣M進行動態調整時,盡量使每次調整涉及的路徑較少,故給出如下優化目標:

(1)

綜上,以帶寬分配矩陣m*為決策變量,給出如下動態調整模型:

Subject to:

在該優化模型中,包含一個l0-范數的優化目標,然而l0-范數的非凸性使得優化模型無法通過凸優化的方式進行求解。在實際中,可用l0-范數的最優凸近似l1-范數替換l0-范數[13],再通過凸優化進行求解。

2.3 路徑規劃策略

2.3.1 靜態初始化過程

(2)

該目標即為在各視頻分配的有效帶寬之和最大。

subject to:

該模型是一個凸優化模型,可以通過凸優化的方式進行求解。

2.3.2 動態調整過程

在實際服務過程中,不可避免地存在視頻流行度發生變化的情況,這時需要對分配矩陣Fk進行重新調整。在保證有效分配帶寬盡可能大的同時,對視頻帶寬在不同路徑上的分配作出指導,使得路徑的負載趨于均衡,引入次優化目標:

(3)

subject to:

該模型是一個多目標凸優化模型,可使用分層序列法對其進行求解,首先針對第1個優化目標進行凸優化求解,得到最優值后將第1個優化目標轉換為新增最優值約束,再對第2個優化目標進行凸優化求解。

2.4 執行策略

在CDN中,交換機的轉發策略需要中心控制器統一下發。在交換機一側,用于存儲流表項的三態內容尋址存儲器(Ternary Content Addressable Memory,TCAM)因其高昂的造價而無法大規模應用[14]。隨著網絡拓撲和應用業務規模的增加,中心控制器的性能和交換機的流表內存容易成為CDN發展的瓶頸。

3 性能仿真與分析

3.1 仿真實驗設置

仿真所用網絡拓撲由波士頓大學的拓撲生成器BRITE[16]生成,各用戶區域使用的流量數據基于中國科學技術大學校園網絡多個互聯網服務供應商(Internet Server Provider,ISP)出口處的真實網絡使用量產生:每5 min測量一次校園網5個獨立ISP網絡出口的帶寬使用情況,選用連續20 d的測量數據,共(20×24×60)/5=5 760個數據點。使用真實網絡帶寬數據進行仿真實驗時,考慮到測量數據一定小于物理鏈路帶寬,因此,本文對真實數據進行了線性放大處理,并在放大實際數據量的同時,保留了原始數據良好的周期性和波動性。

(4)

其中,ψ為傾斜系數,本次實驗中ψ=0.7。

仿真中請求的到達過程符合參數為λ的泊松過程[18],會話時長符合文獻[19]分布,并設平均時長為50 min。其他子網仍使用采集的真實網絡流量數據作為背景流量。設定總仿真時長為500 min。

3.2 資源虛擬化動態調整

當網絡流量大于分配的資源閾值時,可以認為網絡中會產生擁塞、丟包等現象。選用仿真過程中產生擁塞的次數作為性能指標,分別測試并統計不同放大倍數下的策略性能。為更好地反映動態調整的效果,仿真實驗中加入了2組對照實驗:無動態調整策略和理論最大流限制策略,實驗結果如圖3所示。其中,理論最大流是指在給定網絡拓撲下,不考慮不同區域流量間的相互影響時各獨立區域所能達到的網絡最大流,該值即為網絡理論服務能力的上限。

圖3 3種方案擁塞總數統計

由圖3可以看出,本文提出的動態調整策略能夠對分配方案進行有效調整,大幅降低了擁塞次數,在滿負載前(放大倍數小于1.20),該策略幾乎不產生擁塞;當網絡滿載后(放大倍數大于等于1.20),該策略產生的擁塞數略高于理論最優情況,但明顯優于無調整的情況。綜上,本文提出的動態調整策略能夠顯著提升網絡服務能力。

3.3 路徑規劃

在上層路徑規劃過程中,因為考慮到各子網規劃問題的獨立性,所以僅在一個子網內部仿真視頻請求,其余子網均使用采集的真實流量數據作為背景流量。實驗時,背景流量和泊松過程產生的服務均具有波動性,資源虛擬化過程會動態執行并為各子網分配合適的資源。在選中子網內部,每100 min對視頻請求的流行度進行一次旋轉,用來模擬用戶區域流行度的變化情況。實驗分別從請求波動性、服務接受性能和遷移代價三方面對本文策略進行驗證。

首先驗證請求波動性對本文策略的影響。因為對用戶區域內的請求整體進行路徑規劃,所以單個用戶請求的突發性綜合表現為整個用戶區域內視頻流行度的變化。采用對視頻編號進行旋轉的方法[20]產生流行度的波動,旋轉因子π表示波動的大小。選取請求到達率λ=55使系統處于剛滿載狀態,多次實驗得出請求拒絕率和遷移比例,結果如表1所示。由表1可以看出,本文策略能夠較好應對視頻流行度的波動變化。

表1 旋轉因子對本文策略影響統計 %

為了說明本文策略中采用流行度信息和最低負載對服務接入的指導性,使用請求拒絕率和路徑遷移比例作為調整代價。在對比實驗方面,選用文獻[5-6]中的CSP算法。此外,隨機策略作為網絡技術中常用的手段,在實際應用中被廣泛采用,因此,再挑選“動態調整(Dynamic Adjust,DA)+隨機接入(Random Access,RA)”策略作為另一組對比實驗。DA+RA策略是指當流行度發生變化后,對矩陣Fk進行與本文類似的動態調整,優化接入系統的服務總量,但對每個服務采用隨機化的方式接入,不考慮其他信息。表2給出了本文策略、DA+RA策略與CSP策略的拒絕率統計情況。由表2可以看出,本文策略和DA+RA策略的請求拒絕率遠低于CSP策略,原因是CSP策略沒有利用應用層的請求信息,其根據網絡信息對路徑進行動態規劃,容易在物理網絡中形成瓶頸資源,影響系統的整體性能。

表2 不同策略拒絕率對比

為說明本文策略對遷移代價的優化,在不同請求到達率下對不同策略進行遷移比例統計,結果如表3所示。從表3的數據中可以看出,本文策略的遷移比例明顯低于CSP策略和DA+RA策略,原因是本文的接入指導策略能夠避免由隨機接入造成的盲目遷移,其通過有效減少視頻流的遷移次數降低了系統的整體服務代價,而CSP策略因對請求進行了大量的拒絕,導致遷移比例低于DA+RA策略。

表3 不同策略遷移比例對比

綜上,本文提出的分層策略充分利用視頻流行度信息和網絡負載狀態,能在有限的性能損失下為視頻流提供合適的路徑。

4 結束語

本文提出一種分層優化的路徑規劃策略,該策略的底層優化保證了路徑的連通性,對物理網絡進行虛擬化的子網劃分縮減了優化規模,充分利用視頻的流行度信息降低了視頻流遷移代價。考慮到實際應用中CDN的性能瓶頸,本文還提出一種基于隊列調度的執行策略,通過數據包頭部的標簽保證數據的正確轉發和帶寬分配。該策略能夠明顯減少控制流表的下發和存儲,使得其在大規模CDN上的應用成為可能。下一步將把網絡路徑規劃與SMEC內部視頻部署、SMEC自身部署相結合,通過對系統不同層面的資源進行綜合優化,以提升SMEC平臺的服務能力。

[1] JADHAV S,KAKADE V,KAMBLE S,et al.Media streaming applications using cloud[J].International Research Journal of Engineering and Technology,2016,3(5):2091-2096.

[2] 北京原力創新科技有限公司.云模式流媒體服務平臺:200910091537.2[P].2010-01-27.

[3] 高翔宇.一種POF控制器的實現與流量管理研究[D].合肥:中國科學技術大學,2016.

[4] AKYILDIZ I F,LEE A,WANG P,et al.A roadmap for traffic engineering in SDN-OpenFlow networks[J].Computer Networks,2014,71:1-30.

[5] XU C,CHEN B,FU P,et al.A dynamic resource allocation model for guaranteeing quality of service in software defined networking based cloud computing environment[C]//Proceedings of International Confe-rence on Cloud Computing and Security.Berlin,Germany:Springer,2015:206-217.

[6] YU T F,WANG K,HSU Y-H.Adaptive routing for video streaming with QoS support over SDN networks[C]//Proceedings of 2015 International Conference on Infor-mation Networking.Washington D.C.,USA:IEEE Press,2015:318-323.

[7] MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.OpenFlow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008,38(2):69-74.

[8] CASADO M,FREEDMAN M J,PETTIT J,et al.Rethinking enterprise network control[J].IEEE/ACM Transactions on Networking,2009,17(4):1270-1283.

[9] JAIN S,KUMAR A,MANDAL S,et al.B4:experience with a globally-deployed software defined WAN[C]//Proceedings of SIGCOMM’13.New York,USA:ACM Press,2013:3-14.

[10] HONG C Y,KANDULA S,MAHAJAN R,et al.Achieving high utilization with software-driven WAN[C]//Proceedings of SIGCOMM’13.New York,USA:ACM Press,2013:15-26.

[11] SCHWARZ H,MARPE D,WIEGAND T.Overview of the scalable video coding extension of the H.264/AVC standard[J].IEEE Transactions on Circuits and Systems for Video Technology,2007,17(9):1103-1120.

[12] NIU D,XU H,LI B,et al.Quality-assured cloud bandwidth auto-scaling for video-on-demand applications[C]//Proceedings of 2012 IEEE INFOCOM.Washington D.C.,USA:IEEE Press,2012:460-468.

[13] DONOHO D L.For most large underdetermined systems of linear equations the minimal L(1)-norm solution is also the sparsest solution[J].Communications on Pure and Applied Mathematics,2006,59(6):797-829.

[14] BRAUN W,MENTH M.Wildcard compression of inter-domain routing tables for OpenFlow-based software-defined networking[C]//Proceedings of the 3rd European Workshop on Software Defined Networks.Washington D.C.,USA:IEEE Press,2014:25-30.

[15] 尹德斌,謝劍英.一種新的加權公平隊列調度算法[J].計算機工程,2008,34(4):28-30.

[16] MEDINA A,LAKHINA A,MATTA I,et al.BRITE:an approach to universal topology generation[C]//Proceedings of the 9th International Symposium on Modeling,Analysis and Simulation of Computer and Telecommunication Systems.Washington D.C.,USA:IEEE Press,2001:346-353.

[17] QIU T,GE Z,LEE S,et al.Modeling channel popularity dynamics in a large IPTV system[C]//Proceedings of the 7th International Joint Conference on Measurement and Modeling of Computer Systems.New York,USA:ACM Press,2009:275-286.

[18] YU H,ZHENG D,ZHAO B Y,et al.Understanding user behavior in large-scale video-on-demand systems[C]//Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems.New York,USA:ACM Press,2006:333-344.

[19] CHEN L,ZHOU Y,CHIU D M.Smart streaming for online video services[J].IEEE Transactions on Multimedia,2015,17(4):485-497.

[20] WEI X,YANG J,XI H.A novel content updating policy based on dynamic storage balancing for clustered streaming media system[C]//Proceedings of IEEE International Conference on Control and Automation.Washington D.C.,USA:IEEE Press,2009:2031-2036.