亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于流量?jī)?yōu)化的可靠服務(wù)功能鏈部署方法

        2021-11-11 05:59:24孟相如康巧燕趙文文
        關(guān)鍵詞:物理評(píng)價(jià)方法

        陽(yáng) 勇, 孟相如, 康巧燕, 趙文文

        (空軍工程大學(xué)信息與導(dǎo)航學(xué)院, 陜西 西安 710077)

        0 引 言

        隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展,傳統(tǒng)網(wǎng)絡(luò)僵化的弊端逐漸凸顯,其軟件與硬件緊耦合的架構(gòu)越來越難以滿足用戶的需求[1-2]。在傳統(tǒng)網(wǎng)絡(luò)中,基于專有硬件的網(wǎng)絡(luò)功能導(dǎo)致諸多問題,比如網(wǎng)絡(luò)升級(jí)換代需要巨大開銷、可管理性差、可擴(kuò)展性差等[3-5]。網(wǎng)絡(luò)功能虛擬化(network function virtuali-zation,NFV)是解決上述問題的下一代網(wǎng)絡(luò)重要技術(shù)之一,其通過解耦硬件物理設(shè)備與運(yùn)行于其上的網(wǎng)絡(luò)功能,實(shí)現(xiàn)網(wǎng)絡(luò)功能的靈活部署、軟硬件的發(fā)展周期分離以及網(wǎng)絡(luò)功能的動(dòng)態(tài)擴(kuò)展[6-8]。利用NFV技術(shù),網(wǎng)絡(luò)功能可以當(dāng)成一個(gè)普通軟件的實(shí)例,根據(jù)需求動(dòng)態(tài)部署在網(wǎng)絡(luò)中不同位置而無需重新安裝新的硬件,在增加靈活性的同時(shí)極大地降低了運(yùn)營(yíng)商的成本[9-11]。

        在NFV環(huán)境的網(wǎng)絡(luò)中,服務(wù)功能鏈(service function chain,SFC)部署是實(shí)現(xiàn)網(wǎng)絡(luò)業(yè)務(wù)的基礎(chǔ),部署過程中的資源開銷很大程度上決定了運(yùn)營(yíng)商的成本,部署后的可靠性嚴(yán)重影響網(wǎng)絡(luò)功能的穩(wěn)定性,進(jìn)而影響對(duì)用戶的服務(wù)質(zhì)量(quality of service,QoS),因此SFC部署問題得到了許多學(xué)者的關(guān)注[12-29]。文獻(xiàn)[12]在虛擬網(wǎng)絡(luò)功能(virtual network function,VNF)部署階段,利用PageRank算法進(jìn)行節(jié)點(diǎn)排序,在保證端到端時(shí)延的同時(shí)提高了SFC的可靠性,但未考慮資源開銷的優(yōu)化。文獻(xiàn)[13-16]通過備份的方式提高SFC的可靠性,其中文獻(xiàn)[13]對(duì)VNF進(jìn)行聯(lián)合備份,將SFC部署問題構(gòu)建成整數(shù)線性規(guī)劃模型,在優(yōu)先滿足SFC可靠性的同時(shí)優(yōu)化了資源配置;文獻(xiàn)[14]對(duì)鏈路進(jìn)行備份,基于路徑分割對(duì)虛擬鏈路進(jìn)行多路徑映射,以保證鏈路的可靠性。但此類方法因?yàn)槿哂鄠浞菰黾恿诉\(yùn)營(yíng)商的成本。文獻(xiàn)[17-21]提出迭代算法進(jìn)行VNF部署,其中文獻(xiàn)[17]采用基于改進(jìn)遺傳模擬退火算法的VNF部署策略優(yōu)化了端到端時(shí)延;文獻(xiàn)[18]在對(duì)SFC構(gòu)建與部署進(jìn)行雙層編碼的基礎(chǔ)上,利用改進(jìn)遺傳粒子群算法優(yōu)化了請(qǐng)求接受率與資源開銷;文獻(xiàn)[19]提出改進(jìn)遺傳算法進(jìn)行VNF部署,并結(jié)合物理節(jié)點(diǎn)保護(hù)機(jī)制,提高了底層網(wǎng)絡(luò)資源利用率和SFC的生存性。但這此類方法都需通過反復(fù)迭代才能求解,難以實(shí)現(xiàn)VNF的快速部署。文獻(xiàn)[22]采用三階段遞進(jìn)的方式部署VNF,首先將VNF部署到可靠性最高的節(jié)點(diǎn)上,然后調(diào)整部署方案實(shí)現(xiàn)對(duì)負(fù)載的優(yōu)化,最后調(diào)整部署方案縮短大帶寬虛擬鏈路部署到底層網(wǎng)絡(luò)后的物理長(zhǎng)度,該方法提高了SFC的可靠性,但未考慮端到端時(shí)延。文獻(xiàn)[23-27]采用機(jī)器學(xué)習(xí)算法進(jìn)行VNF部署,對(duì)SFC的性能有較大優(yōu)化,但依賴足夠多的準(zhǔn)確數(shù)據(jù)對(duì)模型進(jìn)行訓(xùn)練。文獻(xiàn)[28]提出可以采用聚合的方式部署VNF,但未進(jìn)一步研究具體的聚合方法。文獻(xiàn)[29]根據(jù)功能約束與資源約束聚合VNF,未考慮VNF對(duì)鏈路流量的影響。

        針對(duì)上述問題,本文提出基于流量?jī)?yōu)化的可靠服務(wù)功能鏈部署(reliable service function chain deployment based on traffic optimization,TO-RSFCD)方法。首先根據(jù)虛擬鏈路的帶寬需求變化對(duì)VNF進(jìn)行聚合處理,使聚合的VNF部署到底層網(wǎng)絡(luò)后大帶寬虛擬鏈路上的流量成為服務(wù)器的內(nèi)部流量,達(dá)到降低鏈路開銷的目的。然后綜合考慮物理節(jié)點(diǎn)的可靠性、綜合時(shí)延以及拓?fù)鋵傩?利用離差最大化的多指標(biāo)決策算法對(duì)滿足資源需求的物理節(jié)點(diǎn)進(jìn)行評(píng)價(jià)并排序,評(píng)價(jià)過程中賦予對(duì)排序作用大的評(píng)價(jià)指標(biāo)更高權(quán)重。同時(shí)通過鏈路約束降低流量乒乓效應(yīng),依次將聚合后的VNF部署在排序最靠前的節(jié)點(diǎn)上。最后采用k-最短路徑算法完成虛擬鏈路的部署。實(shí)驗(yàn)表明,TO-RSFCD方法在保證SFC可靠性的基礎(chǔ)上,對(duì)映射成功率、平均收益開銷比、端到端時(shí)延以及帶寬開銷進(jìn)行了較大優(yōu)化。本文的主要貢獻(xiàn)有:

        (1) 根據(jù)虛擬鏈路的帶寬需求變化對(duì)VNF進(jìn)行聚合,使聚合的VNF部署到底層網(wǎng)絡(luò)后大帶寬需求鏈路上的流量變?yōu)榉?wù)器的內(nèi)部流量,優(yōu)化了資源開銷;

        (2) 提出節(jié)點(diǎn)綜合時(shí)延和拓?fù)渚徒戎笜?biāo),前者量化節(jié)點(diǎn)及其相鄰鏈路所產(chǎn)生的時(shí)延,后者量化節(jié)點(diǎn)與源、目的端點(diǎn)之間最短路徑的拓?fù)鋵傩?實(shí)現(xiàn)了算法對(duì)底層網(wǎng)絡(luò)的拓?fù)渑c時(shí)延感知;

        (3) 采用離差最大化多指標(biāo)決策算法對(duì)物理節(jié)點(diǎn)進(jìn)行評(píng)價(jià),對(duì)排序作用大的評(píng)價(jià)指標(biāo)賦予更高權(quán)重,實(shí)現(xiàn)了權(quán)重的自適應(yīng)設(shè)定;

        (4) VNF部署過程中設(shè)置鏈路約束條件,降低了流量的乒乓效應(yīng)。

        1 網(wǎng)絡(luò)模型及問題描述

        1.1 網(wǎng)絡(luò)模型

        物理網(wǎng)絡(luò)用一個(gè)加權(quán)無向圖G=(N,E)表示,其中N為物理節(jié)點(diǎn)的集合,E為物理鏈路的集合。每個(gè)物理節(jié)點(diǎn)上附著一至多個(gè)服務(wù)器,能夠用來實(shí)例化VNF。節(jié)點(diǎn)ns∈N的剩余可用計(jì)算資源為Cal(ns),可用存儲(chǔ)資源為Mem(ns),可用轉(zhuǎn)發(fā)資源為For(ns),實(shí)例化VNF后產(chǎn)生的時(shí)延為d(ns),可靠性為r(ns)。鏈路es∈E的剩余可用帶寬為b(ns),時(shí)延為d(es)。

        SFC請(qǐng)求用一個(gè)七元組(I,O,D,T,R,V,L)表示,其中I為源端點(diǎn),O為目的端點(diǎn),D為SFC的最大允許時(shí)延,T為SFC的生存時(shí)間,R為SFC的可靠性要求下限,V為組成SFC的VNF集合,L為組成SFC的虛擬鏈路集合。集合V={v1,v2,…,vn}中的元素vi表示SFC的第i個(gè)VNF,其計(jì)算資源需求為Cal(vi),存儲(chǔ)資源需求為Mem(vi),轉(zhuǎn)發(fā)資源需求為For(vi),帶寬改變因子為η(vi),其中帶寬改變因子定義為VNF流量的流出帶寬與流入帶寬之比。集合L={l0,l1,…,ln}中的元素li為vi到vi+1之間的虛擬鏈路。當(dāng)i=0時(shí),li為源端點(diǎn)I到v1之間的虛擬鏈路,當(dāng)i=n時(shí),li為vn到目的端點(diǎn)O之間的虛擬鏈路。用b(li)表示li的帶寬需求,則b(li)的計(jì)算公式為

        (1)

        1.2 優(yōu)化目標(biāo)

        用xi, j表示vi是否部署到物理節(jié)點(diǎn)nj上,yi, j表示li部署到底層網(wǎng)絡(luò)后是否經(jīng)過物理鏈路ej。令集合φ=(Cal, Mem, For),k∈φ表示計(jì)算、存儲(chǔ)、轉(zhuǎn)發(fā)資源中任意一種資源。則SFC部署到底層網(wǎng)絡(luò)后,資源開銷的計(jì)算公式為

        (2)

        式(2)的第一部分表示節(jié)點(diǎn)的計(jì)算、存儲(chǔ)與轉(zhuǎn)發(fā)資源開銷,第二部分表示鏈路的帶寬開銷。本文旨在保證SFC可靠性和時(shí)延要求的基礎(chǔ)上,對(duì)資源開銷進(jìn)行優(yōu)化,優(yōu)化目標(biāo)為

        Goal=min(Cost)

        (3)

        SFC的部署過程中約束條件如下:

        (4)

        (5)

        (6)

        (7)

        (8)

        (9)

        (10)

        式(4)表示每一個(gè)VNF都能在底層網(wǎng)絡(luò)部署,但只能部署到一個(gè)物理節(jié)點(diǎn)上。式(5)表示每一條虛擬鏈路都能在底層網(wǎng)絡(luò)部署,且能部署在一條或多條物理鏈路上。式(6)表示每一條物理鏈路被同一條SFC的虛擬鏈路最多部署一次,這是為了防止乒乓效應(yīng),其中乒乓效應(yīng)指流量在兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)間來回傳輸。式(7)表示VNF的任意一種資源需求都不能超過所部署節(jié)點(diǎn)的剩余可用資源。式(8)表示虛擬鏈路的帶寬需求不能超過所部署鏈路的剩余可用帶寬。式(9)表示SFC的時(shí)延不能超過所允許的最大時(shí)延,不等式的左邊第一部分表示節(jié)點(diǎn)產(chǎn)生的時(shí)延,第二部分表示鏈路時(shí)延。式(10)表示SFC必須滿足可靠性要求,不等式的左邊表示SFC的可靠性。本文只考慮服務(wù)器的可靠性,當(dāng)節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí),由于其上附著的服務(wù)器沒有被SFC使用,所以其可靠性不計(jì)入SFC的可靠性中。

        1.3 問題描述

        從資源開銷的組成部分分析,由于每個(gè)VNF只能部署在一個(gè)物理節(jié)點(diǎn)上,所以計(jì)算、存儲(chǔ)與轉(zhuǎn)發(fā)資源的開銷與需求相等,無法對(duì)其進(jìn)行優(yōu)化。而每一條虛擬鏈路能夠部署在一條或多條物理鏈路上,所以帶寬開銷必定大于或等于帶寬需求,能夠?qū)ζ溥M(jìn)行優(yōu)化。圖1是同一SFC在相同物理網(wǎng)絡(luò)拓?fù)湎碌?種不同部署方法,箭頭處數(shù)字代表初始帶寬,VNF處數(shù)字代表帶寬改變因子。

        圖1 不同VNF部署方法對(duì)比Fig.1 Comparison of different VNF deployment methods

        與方法1相比,方法2通過鏈路約束避免了流量在節(jié)點(diǎn)B與節(jié)點(diǎn)H之間來回傳輸(即乒乓效應(yīng)),方法3在避免乒乓效應(yīng)的基礎(chǔ)上,將某些VNF進(jìn)行了聚合部署。經(jīng)計(jì)算,方法1的帶寬開銷為583.84 M/s,方法2的帶寬開銷為497.44 M/s,方法3的帶寬開銷為367.84 M/s,方法2和方法3相較于方法1對(duì)帶寬開銷進(jìn)行了較大優(yōu)化。

        假設(shè)每個(gè)物理節(jié)點(diǎn)的可靠性為0.95,由于方法3中只在兩個(gè)節(jié)點(diǎn)上部署VNF,SFC的可靠性為0.952=0.902 5。而另外兩種方法在4個(gè)節(jié)點(diǎn)上部署VNF,SFC的可靠性為0.954=0.814 5。對(duì)比可見,方法3的SFC可靠性也得到了提高。因此,在部署SFC時(shí),以一定規(guī)則對(duì)VNF進(jìn)行聚合處理,并盡可能減少流量的乒乓效應(yīng),則能在提高SFC可靠性的同時(shí)達(dá)到優(yōu)化帶寬開銷的目的。

        2 基于流量?jī)?yōu)化的可靠服務(wù)功能鏈部署方法設(shè)計(jì)

        2.1 基于帶寬需求變化的VNF聚合算法

        NFV環(huán)境中存在3類VNF,第1類是帶寬改變因子大于1的VNF,比如數(shù)據(jù)加密、編碼等,經(jīng)此類VNF處理后,SFC的帶寬會(huì)增大。第2類是帶寬改變因子等于1的VNF,比如QoS監(jiān)視、入侵檢測(cè)等,經(jīng)此類VNF處理后,SFC的帶寬不會(huì)發(fā)生變化。第3類是帶寬改變因子小于1的VNF,比如防火墻、數(shù)據(jù)解密等,經(jīng)此類VNF處理后,SFC的帶寬會(huì)減小。為達(dá)到優(yōu)化帶寬開銷的目的,就必須在保證VNF編排順序不變的前提下,將帶寬改變因子小于1的VNF在物理網(wǎng)絡(luò)中靠前部署,帶寬改變因子大于1的VNF靠后部署。

        本算法的中心思想是針對(duì)所有帶寬改變因子大于1的VNF,將編排在其后但在下一個(gè)帶寬改變因子大于1的VNF之前的所有VNF與其進(jìn)行聚合,聚合的VNF將部署到同一個(gè)物理節(jié)點(diǎn)上,達(dá)到將帶寬改變因子小于1的VNF靠前部署的目的,并使大帶寬需求鏈路上的流量變?yōu)榉?wù)器的內(nèi)部流量,如圖2所示。

        圖2 基于帶寬需求變化的VNF聚合算法案例Fig.2 A case study of VNF polymerization algorithm based on bandwidth demand changes

        以SFC1為例,v1和v4是帶寬改變因子大于1的VNF,v2和v3編排在v1之后,v4之前,所以將v2和v3與v1進(jìn)行聚合。聚合的VNF將部署到同一個(gè)物理節(jié)點(diǎn)上,其中流入該物理節(jié)點(diǎn)流量的帶寬為SFC1的初始帶寬,流出該物理節(jié)點(diǎn)流量的帶寬為經(jīng)v1、v2和v3依次處理過的帶寬,是一個(gè)較小的值。而僅經(jīng)v1處理過的大帶寬流量成為了該物理節(jié)點(diǎn)上所附著服務(wù)器的內(nèi)部流量。SFC2和SFC3的聚合規(guī)則同理。算法的具體步驟如下所示。

        算法 1 基于帶寬需求變化的VNF聚合算法輸入: VNF集合V,V中元素所對(duì)應(yīng)的帶寬改變因子集合η輸出: 聚合后的VNF集合V′1 for V中每一個(gè)元素vi 2 if η(vi)>13 將vi的編排位置放入集合Temp中;4 end if5 end for6 if η(vi)≤17 將V中前Temp-1個(gè)VNF進(jìn)行聚合,并賦值給v′1; 8 for i=2: |Temp|9 將V中第Temp(i-1)到Temp(i)-1個(gè)VNF進(jìn)行聚合,并賦值給v′i;10 end for11 將V中第Temp(i)及之后的所有VNF進(jìn)行聚合,并賦值給v′ i+1;12 else13 for i=|Temp|-114 將V中第Temp(i)到Temp(i+1)-1個(gè)VNF進(jìn)行聚合,并賦值給v′i;15 end for16 將V中第Temp(i+1)及之后的所有VNF進(jìn)行聚合,并賦值給v′ i+1;17 end if18 return V′

        聚合后VNF的計(jì)算、存儲(chǔ)與轉(zhuǎn)發(fā)資源需求等于聚合前各VNF的同類資源需求之和,帶寬改變因子等于聚合前各VNF的帶寬改變因子之積。

        2.2 基于離差最大化的VNF部署算法

        對(duì)SFC中VNF進(jìn)行聚合處理后,再對(duì)聚合的VNF進(jìn)行部署。本算法的中心思想是在對(duì)底層網(wǎng)路進(jìn)行拓?fù)渑c時(shí)延感知的基礎(chǔ)上,利用離差最大化的多目標(biāo)決策算法對(duì)物理節(jié)點(diǎn)進(jìn)行評(píng)價(jià)并排序,每次按照編排順序部署聚合后的VNF時(shí),依據(jù)資源約束與鏈路約束篩選物理節(jié)點(diǎn),再?gòu)暮Y選出的物理節(jié)點(diǎn)中選擇排序靠前的部署VNF。對(duì)物理節(jié)點(diǎn)進(jìn)行評(píng)價(jià)的指標(biāo)有節(jié)點(diǎn)可靠性、節(jié)點(diǎn)綜合時(shí)延、節(jié)點(diǎn)拓?fù)渚徒群凸?jié)點(diǎn)源端距。

        節(jié)點(diǎn)可靠性采用固有可用度[30]進(jìn)行表示,其定義為

        (11)

        式中:MTBF表示節(jié)點(diǎn)的平均故障間隔;MTTR表示平均修復(fù)時(shí)間。節(jié)點(diǎn)可靠性越高,越有利于靠前排序。

        定義 1節(jié)點(diǎn)綜合時(shí)延是對(duì)節(jié)點(diǎn)及其相關(guān)聯(lián)鏈路所產(chǎn)生時(shí)延的綜合度量,能反映選取該節(jié)點(diǎn)部署VNF后對(duì)SFC時(shí)延的影響,是算法實(shí)現(xiàn)對(duì)底層網(wǎng)絡(luò)時(shí)延感知的關(guān)鍵指標(biāo),其計(jì)算公式為

        (12)

        式中:d(ns)表示節(jié)點(diǎn)ns所產(chǎn)生的時(shí)延,包括排隊(duì)時(shí)延、處理時(shí)延與發(fā)送時(shí)延;E(ns)表示與ns相關(guān)聯(lián)的物理鏈路集合,|E(ns)|表示集合E(ns)中元素的個(gè)數(shù);d(es)表示鏈路es所產(chǎn)生的時(shí)延,包括傳播時(shí)延;α與β為權(quán)重因子,本文中均設(shè)為1。節(jié)點(diǎn)的綜合時(shí)延越小,越有利于靠前排序。

        定義 2節(jié)點(diǎn)拓?fù)渚徒缺硎竟?jié)點(diǎn)與源目端點(diǎn)之間最短路徑的拓?fù)渚o密程度,能反映選取該節(jié)點(diǎn)部署VNF后對(duì)SFC物理長(zhǎng)度的影響,是算法實(shí)現(xiàn)對(duì)底層網(wǎng)絡(luò)拓?fù)涓兄年P(guān)鍵指標(biāo),其計(jì)算公式為

        (13)

        式中:TD(ns)表示ns的度數(shù),數(shù)值上等于|E(ns)|;hop(ns,I)表示ns與源端點(diǎn)之間的最短跳數(shù);hop(ns,O)表示ns與目的端點(diǎn)之間的最短跳數(shù)。采用節(jié)點(diǎn)拓?fù)渚徒茸鳛樵u(píng)價(jià)指標(biāo)能縮短SFC的物理長(zhǎng)度,節(jié)點(diǎn)的拓?fù)渚徒仍酱?越有利于靠前排序。

        節(jié)點(diǎn)源端距表示節(jié)點(diǎn)與源端點(diǎn)之間的最短跳數(shù),即hop(ns,I)。采用節(jié)點(diǎn)源端距作為評(píng)價(jià)指標(biāo)能實(shí)現(xiàn)帶寬改變因子小于1的VNF盡可能靠前部署,節(jié)點(diǎn)源端距越小,越有利于靠前排序。

        采用離差最大化的多指標(biāo)決策算法計(jì)算每個(gè)物理節(jié)點(diǎn)ns的評(píng)價(jià)度S(ns),并利用S(ns)對(duì)各物理節(jié)點(diǎn)進(jìn)行排序,然后依據(jù)VNF編排順序?qū)Ω鱒NF進(jìn)行部署。離差最大化的多指標(biāo)決策算法步驟如下。

        步驟 1根據(jù)評(píng)價(jià)指標(biāo)類型構(gòu)造規(guī)范化決策矩陣(Zij)m×n。假設(shè)有m個(gè)評(píng)價(jià)對(duì)象,表示不同的物理節(jié)點(diǎn),每個(gè)物理節(jié)點(diǎn)有n個(gè)評(píng)價(jià)指標(biāo),記第i個(gè)物理節(jié)點(diǎn)的第j個(gè)評(píng)價(jià)指標(biāo)值為aij。值越大越有利于節(jié)點(diǎn)靠前排序的評(píng)價(jià)指標(biāo)為效益型評(píng)價(jià)指標(biāo),如節(jié)點(diǎn)可靠性與拓?fù)渚徒?值越小越有利于節(jié)點(diǎn)靠前排序的評(píng)價(jià)指標(biāo)為成本型評(píng)價(jià)指標(biāo),如節(jié)點(diǎn)綜合時(shí)延與源端距。效益型評(píng)價(jià)指標(biāo)在決策矩陣中的值為

        (14)

        成本型評(píng)價(jià)指標(biāo)在決策矩陣中的值為

        (15)

        式中:max(a*j)表示第j個(gè)評(píng)價(jià)指標(biāo)的最大值;min(a*j)表示第j個(gè)評(píng)價(jià)指標(biāo)的最小值。

        步驟 2根據(jù)離差最大化方法計(jì)算各評(píng)價(jià)指標(biāo)的最優(yōu)加權(quán)向量W*。設(shè)評(píng)價(jià)指標(biāo)的加權(quán)向量為W=[w1,w2,…,wn],則在W作用下規(guī)范化決策矩陣為

        (16)

        如果某評(píng)價(jià)指標(biāo)的值對(duì)所有物理節(jié)點(diǎn)均無差異,則其對(duì)節(jié)點(diǎn)排序不起作用,應(yīng)將其權(quán)重設(shè)為0。反之若某評(píng)價(jià)指標(biāo)的值對(duì)所有物理節(jié)點(diǎn)有較大差異,則其對(duì)節(jié)點(diǎn)排序起重要作用,應(yīng)將其權(quán)重設(shè)為較大值。在當(dāng)前權(quán)重下,第i個(gè)物理節(jié)點(diǎn)的第j個(gè)評(píng)價(jià)指標(biāo)與其他物理節(jié)點(diǎn)的離差為dispij(w),計(jì)算方式為

        (17)

        第j個(gè)評(píng)價(jià)指標(biāo)的總離差為dispj(w),其表示就第j個(gè)評(píng)價(jià)指標(biāo)而言,所有物理節(jié)點(diǎn)與其他物理節(jié)點(diǎn)的總離差,計(jì)算方式為

        (18)

        據(jù)前面分析,加權(quán)向量W的選擇應(yīng)使所有評(píng)價(jià)指標(biāo)的總離差最大,因此構(gòu)造目標(biāo)函數(shù)為

        (19)

        其中,約束條件為

        (20)

        (21)

        步驟 3根據(jù)最優(yōu)加權(quán)向量作用下的決策矩陣計(jì)算各物理節(jié)點(diǎn)的綜合評(píng)價(jià)度S(ns)。最優(yōu)加權(quán)向量作用下的決策矩陣為

        (22)

        第i個(gè)物理節(jié)點(diǎn)的綜合評(píng)價(jià)度為

        (23)

        算法 2 基于離差最大化的VNF部署算法輸入: 經(jīng)VNF聚合處理后的SFC=(I,O,D,T,R,V′,L′),物理網(wǎng)絡(luò)G=(N,E)輸出: VNF_Embedding_List1 for N中每一個(gè)物理節(jié)點(diǎn)ns2 利用離差最大化多指標(biāo)決策算法計(jì)算綜合評(píng)價(jià)度S(ns);3 end for4 利用S(ns)對(duì)N中物理節(jié)點(diǎn)進(jìn)行排序;5 for V′中每一個(gè)v′i6 從N中篩選出滿足其計(jì)算、存儲(chǔ)與轉(zhuǎn)發(fā)資源需求的節(jié)點(diǎn)集合Ф(v′i);7 if Ф(v′i)為空8 return VNF_EMBEDDING_FAILED9 else10 從Ф(v′i)刪除滿足hop(ns, O)>hop(ns(vi-1′), O)的物理節(jié)點(diǎn);11 if Ф(v′i)為空12 return VNF_EMBEDDING_FAILED13 else14 將v′i部署到Ф(v′i)中排序最靠前的物理節(jié)點(diǎn)上,并將映射關(guān)系存入VNF_Embedding_List中;15 更新各物理節(jié)點(diǎn)剩余資源;16 end if17 end if18 end for19 計(jì)算SFC的可靠性;20 if SFC的可靠性不滿足可靠性要求下限R21 return VNF_EMBEDDING_FAILED22 else 23 return VNF_Embedding_List34 end if

        2.3 虛擬鏈路部署

        VNF部署完畢后,首先在物理拓?fù)渲袆h除不滿足帶寬需求的物理鏈路,然后利用k-最短路徑算法在剩余拓?fù)渲胁渴鹛摂M鏈路,最后根據(jù)VNF所部署物理節(jié)點(diǎn)產(chǎn)生的時(shí)延與虛擬鏈路所部署物理鏈路的時(shí)延計(jì)算出SFC的端到端時(shí)延,若該時(shí)延小于最大允許時(shí)延D,則SFC部署成功,否則部署失敗。

        在VNF部署階段,TO-RSFCD對(duì)物理節(jié)點(diǎn)進(jìn)行評(píng)價(jià)的時(shí)間復(fù)雜度為O(|N|);在鏈路部署階段,k-最短路徑算法的時(shí)間復(fù)雜度為O(k|N|(|E|+|N|lg|E|))。

        3 算法性能評(píng)估與分析

        為評(píng)估本文所提方法的性能,利用Matlab對(duì)其進(jìn)行仿真并與基于QoS保障的服務(wù)功能鏈動(dòng)態(tài)部署算法[12]、可靠感知與資源優(yōu)化的虛擬網(wǎng)絡(luò)功能部署方法[22]進(jìn)行對(duì)比。同時(shí),為驗(yàn)證VNF聚合部署的優(yōu)勢(shì),設(shè)置了一種本文所提方法的對(duì)照方法,該方法除不進(jìn)行VNF聚合外,所有過程皆與本文所提方法保持一致。

        3.1 方法評(píng)價(jià)指標(biāo)

        本文采用請(qǐng)求接受率、平均帶寬開銷、SFC平均可靠性、SFC平均端到端時(shí)延以及長(zhǎng)期平均收益開銷比來衡量算法的性能。

        (1) 請(qǐng)求接受率ωaccept定義為

        (24)

        式中:NUMsuc(T)表示T時(shí)間內(nèi)成功部署的SFC數(shù)目;NUMv(T)表示T時(shí)間內(nèi)到達(dá)的SFC請(qǐng)求總數(shù)目。

        (2) 平均帶寬開銷Bcost_ave定義為

        (25)

        式中:Bcostsg是成功部署的SFCg所消耗的帶寬。

        (3) SFCg的可靠性為

        (26)

        則SFC的平均可靠性定義為

        (27)

        (4) SFCg的端到端時(shí)延為

        (28)

        則SFC平均端到端時(shí)延定義為

        (29)

        (5) 在t時(shí)刻,成功部署一個(gè)SFCg的收益為

        (30)

        物理網(wǎng)絡(luò)的資源開銷為

        (31)

        式中:α,β,γ,χ分別表示收益和開銷中計(jì)算、存儲(chǔ)、轉(zhuǎn)發(fā)與帶寬資源的比重,本文中均設(shè)為1。則長(zhǎng)期平均收益開銷比定義為

        (32)

        3.2 仿真環(huán)境設(shè)置

        仿真環(huán)境中物理網(wǎng)絡(luò)是由100個(gè)節(jié)點(diǎn)和525條鏈路組成的連通圖,相當(dāng)于一個(gè)中型網(wǎng)絡(luò)拓?fù)?SFC請(qǐng)求服從到達(dá)率λ=0.05的泊松分布,生存時(shí)間服從μ=1 000的指數(shù)分布,仿真時(shí)間為50 000個(gè)單位。其余各項(xiàng)參數(shù)如表1所示。

        表1 仿真參數(shù)Table 1 Simulation parameters

        3.3 實(shí)驗(yàn)結(jié)果分析

        為避免隨機(jī)因素影響,仿真實(shí)驗(yàn)共進(jìn)行10次,取每次結(jié)果的平均值作為最終的實(shí)驗(yàn)結(jié)果,如圖3~圖8所示。

        圖3 重復(fù)映射鏈路條數(shù)Fig.3 Number of links that are mapped repeatedly

        從圖3可以發(fā)現(xiàn),本文所提方法與對(duì)照方法的鏈路重復(fù)映射條數(shù)小于另外兩種方法,即乒乓效應(yīng)低于另外兩種方法。這是因?yàn)樵诓渴疬^程中這兩種方法進(jìn)了鏈路約束,有效降低了同一條SFC上的不同虛擬鏈路映射到相同物理鏈路上。而另外兩種方法未考慮乒乓效應(yīng),所以鏈路重復(fù)映射條數(shù)較高。

        從圖4可以發(fā)現(xiàn),本文所提方法的收益開銷比保持在0.75以上,明顯優(yōu)于其他3種方法。這是因?yàn)楸疚乃岱椒ǜ鶕?jù)帶寬需求變化對(duì)VNF進(jìn)行聚合處理,并且在部署時(shí)利用鏈路約束降低了乒乓效應(yīng),有效降低了帶寬開銷,從而提升了長(zhǎng)期平均收益開銷比。本文對(duì)照方法未進(jìn)行VNF聚合,但在部署時(shí)利用鏈路約束降低了乒乓效應(yīng),所以其長(zhǎng)期收益開銷比大于另外兩種方法。文獻(xiàn)[12]和文獻(xiàn)[22]所提方法未進(jìn)行VNF聚合,也未考慮乒乓效應(yīng),所以長(zhǎng)期收益開銷比較低。

        圖4 長(zhǎng)期平均收益開銷比Fig.4 Long-term average revenue overhead ratio

        從圖5可以發(fā)現(xiàn),本文所提方法與對(duì)照方法的映射成功率都在0.95以上,優(yōu)于另外兩種方法,這是因?yàn)檫@兩種方法在進(jìn)行部署時(shí)考慮了物理節(jié)點(diǎn)的綜合時(shí)延、可靠性以及拓?fù)鋵傩?使得部署后的SFC能較好地滿足時(shí)延與可靠性約束,所以映射成功功率較高。而文獻(xiàn)[12]所提方法未考慮鏈路的時(shí)延,文獻(xiàn)[22]所提方法對(duì)節(jié)點(diǎn)和鏈路的時(shí)延均未作考慮,使得部署后的SFC未能很好滿足時(shí)延約束,所以映射成功率較低。

        圖5 映射成功率Fig.5 Mapping success rate

        從圖6可以發(fā)現(xiàn),本文所提方法的SFC平均可靠性最高,保持在0.91以上,這是因?yàn)檫M(jìn)行了VNF聚合后,多個(gè)VNF部署到同一個(gè)物理節(jié)點(diǎn)上,并采用離差最大化的多指標(biāo)決策方法賦予對(duì)排序作用大的評(píng)價(jià)指標(biāo)更高權(quán)重,有效地提高了SFC的可靠性。文獻(xiàn)[22]所提方法的SFC平均可靠性保持在0.9以上,僅次于本文所提方法,這是因?yàn)樵摲椒ㄔ诘谝浑A段將VNF都部署在可靠性最高的物理節(jié)點(diǎn)上,后兩個(gè)階段只是在此基礎(chǔ)上作調(diào)整,所以能保持較高的可靠性。本文對(duì)照方法在部署階段考慮了拓?fù)鋵傩?、?jié)點(diǎn)綜合時(shí)延與可靠性,文獻(xiàn)[12]所提方法考慮了拓?fù)鋵傩耘c節(jié)點(diǎn)可靠性,均未對(duì)VNF進(jìn)行聚合,所以其SFC可靠性較低,但由于本文對(duì)照方法采用離差最大化多指標(biāo)決策方法,所以在可靠性方面還有一定優(yōu)勢(shì)。

        圖6 SFC平均可靠性Fig.6 Average reliability of SFC

        從圖7可以發(fā)現(xiàn),本文所提方法與對(duì)照方法的SFC平均端到端時(shí)延低于另外兩種方法,分別保持在45 ms和50 ms左右,這是因?yàn)檫@兩種方法在部署階段既把物理節(jié)點(diǎn)綜合時(shí)延作為評(píng)價(jià)指標(biāo),還利用鏈路約束降低了乒乓效應(yīng),所以能獲得更低的節(jié)點(diǎn)與鏈路時(shí)延。而文獻(xiàn)[12]所提方法未考慮鏈路時(shí)延,文獻(xiàn)[22]所提方法對(duì)節(jié)點(diǎn)時(shí)延與鏈路時(shí)延均未考慮,所以SFC平均端到端時(shí)延較高。

        圖7 SFC平均端到端時(shí)延Fig.7 Average end to end delay of SFC

        圖8 平均帶寬開銷Fig.8 Average bandwidth overhead

        從圖8可以發(fā)現(xiàn),本文所提方法的帶寬開銷低于另外3種方法,保持在500 M/s左右,這是因?yàn)楸疚乃岱椒雀鶕?jù)帶寬需求對(duì)VNF進(jìn)行了聚合處理,在部署時(shí)還利用鏈路約束降低了乒乓效應(yīng),所以獲得了較低的帶寬開銷。而本文對(duì)照算法未進(jìn)行VNF聚合處理,但降低了乒乓效應(yīng),所以帶寬開銷僅高于本文所提方法。另外兩種方法未進(jìn)行VNF聚合,也未考慮乒乓效應(yīng),所以平均帶寬開銷較高。

        4 結(jié) 論

        針對(duì)NFV環(huán)境中服務(wù)功能鏈的部署問題,本文提出一種基于流量?jī)?yōu)化的可靠服務(wù)功能鏈部署方法。首先根據(jù)虛擬鏈路的帶寬需求變化對(duì)VNF進(jìn)行聚合處理,使大帶寬虛擬鏈路上的流量變?yōu)榉?wù)器的內(nèi)部流量,有效降低了帶寬開銷,提升了收益開銷比。然后綜合考慮節(jié)點(diǎn)可靠性、綜合時(shí)延以及拓?fù)鋵傩?使用離差最大化的多指標(biāo)決策算法對(duì)滿足聚合后VNF資源需求的物理節(jié)點(diǎn)進(jìn)行評(píng)價(jià),并利用鏈路約束降低乒乓效應(yīng),依次將VNF部署到評(píng)價(jià)度最高的節(jié)點(diǎn)上。最后采用k-最短路徑算法完成虛擬鏈路的部署。實(shí)驗(yàn)表明,該方法在保證SFC可靠性的基礎(chǔ)上,對(duì)長(zhǎng)期平均收益開銷比、映射成功率、端到端時(shí)延以及平均帶寬開銷有較大優(yōu)化。下一步將對(duì)流量預(yù)測(cè)進(jìn)行研究,進(jìn)一步提高NFV環(huán)境中網(wǎng)絡(luò)的性能。

        猜你喜歡
        物理評(píng)價(jià)方法
        只因是物理
        井岡教育(2022年2期)2022-10-14 03:11:44
        SBR改性瀝青的穩(wěn)定性評(píng)價(jià)
        石油瀝青(2021年4期)2021-10-14 08:50:44
        處處留心皆物理
        三腳插頭上的物理知識(shí)
        可能是方法不對(duì)
        用對(duì)方法才能瘦
        Coco薇(2016年2期)2016-03-22 02:42:52
        四大方法 教你不再“坐以待病”!
        Coco薇(2015年1期)2015-08-13 02:47:34
        捕魚
        我不是教物理的
        中學(xué)生(2015年2期)2015-03-01 03:43:33
        基于Moodle的學(xué)習(xí)評(píng)價(jià)
        67194熟妇人妻欧美日韩| 日韩人妻免费一区二区三区| 日本免费大片一区二区三区| 无码少妇丰满熟妇一区二区| 撕开奶罩揉吮奶头视频| 亚洲国产麻豆综合一区| 少妇久久高潮不断免费视频| 在线播放亚洲丝袜美腿| 日韩中文字幕免费视频| 国产人成精品免费视频| 插入中文字幕在线一区二区三区| 青青草视频网站在线观看| 91精品国产综合久久久蜜臀九色 | 午夜内射中出视频| 亚洲伊人久久大香线蕉影院| 极品视频一区二区三区在线观看| 亚洲女优中文字幕在线观看| 九九在线中文字幕无码| 少妇人妻偷人精品视频| 亚洲一区二区三区久久不卡| 日韩人妻无码精品二专区| 日日麻批视频免费播放器| 性色视频加勒比在线观看| 婷婷五月六月综合缴情| 国产美女一级做a爱视频| 偷拍一区二区三区黄片| 亚洲色图片区| 亚洲丁香五月激情综合| 日韩美女av二区三区四区| 少妇人妻av一区二区三区| 美女张开腿黄网站免费| 久久亚洲精品无码va大香大香| 色999欧美日韩| 激情综合网缴情五月天| 日本精品久久不卡一区二区| 99国产精品久久久蜜芽| 国产99re在线观看只有精品| 色佬易精品视频免费在线观看| 蜜臀av在线观看| 国产亚洲视频在线观看网址| 国产人成亚洲第一网站在线播放|