面向多業(yè)務(wù)需求的NFV和SDN融合的資源優(yōu)化算法

朱曉榮，張倩

?

面向多業(yè)務(wù)需求的NFV和SDN融合的資源優(yōu)化算法

朱曉榮，張倩

（南京郵電大學(xué)通信與信息工程學(xué)院，江蘇 南京 210003）

物聯(lián)網(wǎng)的多種業(yè)務(wù)需要靈活的網(wǎng)絡(luò)部署來保障其服務(wù)質(zhì)量。針對(duì)物聯(lián)網(wǎng)服務(wù)功能鏈部署問題，將網(wǎng)絡(luò)功能虛擬化（NFV, network function virtualization）與軟件定義網(wǎng)絡(luò)（SDN, software defined networking）相結(jié)合，綜合考慮轉(zhuǎn)發(fā)成本以及流量平衡情況，給出了虛擬網(wǎng)絡(luò)功能放置與服務(wù)功能鏈路由的聯(lián)合優(yōu)化模型，該優(yōu)化模型是NP-Hard問題。為了求解該問題，提出兩種啟發(fā)式算法：一種是先路由后放置（FRTP, first routing then placing）的服務(wù)鏈部署算法，另一種是基于節(jié)點(diǎn)優(yōu)先級(jí)的先放置后路由（PFBR, placing followed by routing）的服務(wù)鏈部署算法。仿真結(jié)果表明，與其他算法相比，提出的FRTP和PFBR算法能顯著平衡網(wǎng)絡(luò)中的流量負(fù)載，改善鏈路擁塞情況，從而提高服務(wù)功能鏈請(qǐng)求接受率。

物聯(lián)網(wǎng)；虛擬網(wǎng)絡(luò)功能；服務(wù)功能鏈部署；節(jié)點(diǎn)優(yōu)先級(jí)；負(fù)載均衡

1 引言

隨著物聯(lián)網(wǎng)的發(fā)展，各種各樣的業(yè)務(wù)對(duì)網(wǎng)絡(luò)的需求日益多樣化[1]。例如，車聯(lián)網(wǎng)中的通信對(duì)時(shí)間的敏感度高；工業(yè)制造中要求低分組丟失率和低時(shí)延；而移動(dòng)視頻監(jiān)控網(wǎng)絡(luò)可以容忍適度的誤碼率和時(shí)延，但需要高帶寬?，F(xiàn)有的專用硬件網(wǎng)絡(luò)系統(tǒng)架構(gòu)面臨著諸多嚴(yán)重缺陷，例如，網(wǎng)絡(luò)體系架構(gòu)僵硬、網(wǎng)絡(luò)升級(jí)維護(hù)困難、功能平面劃分不合理等，難以應(yīng)對(duì)日新月異的物聯(lián)網(wǎng)業(yè)務(wù)需求。

SDN通過數(shù)據(jù)平面與控制平面的分離，并借助開放的接口，為形式各異的網(wǎng)絡(luò)應(yīng)用提供靈活的承載服務(wù)。NFV使用虛擬化技術(shù)以消除對(duì)專用硬件的依賴[2]，并使很多不同的網(wǎng)絡(luò)設(shè)備類型合并到行業(yè)標(biāo)準(zhǔn)高容量服務(wù)器、交換機(jī)及存儲(chǔ)器上，通過靈活的部署策略來提高網(wǎng)絡(luò)基礎(chǔ)設(shè)施的資源利用率和服務(wù)質(zhì)量[3]。

雖然SDN和NFV技術(shù)的應(yīng)用有望滿足物聯(lián)網(wǎng)多樣化的業(yè)務(wù)對(duì)網(wǎng)絡(luò)靈活組網(wǎng)的需求，但是NFV技術(shù)對(duì)網(wǎng)絡(luò)服務(wù)重新抽象和細(xì)粒度分解，使其組成成分更加復(fù)雜，關(guān)鍵的挑戰(zhàn)在于服務(wù)功能鏈（SFC, service function chain）的部署。由于巨大的服務(wù)規(guī)模以及高動(dòng)態(tài)的網(wǎng)絡(luò)負(fù)載，物聯(lián)網(wǎng)復(fù)雜業(yè)務(wù)驅(qū)動(dòng)的動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)構(gòu)建機(jī)制無論對(duì)當(dāng)前還是未來都是一個(gè)挑戰(zhàn)。

Wang等在文獻(xiàn)[4]中，針對(duì)NFV資源分配問題，提出一種綜合的成本模型，在滿足用戶需求的基礎(chǔ)上實(shí)現(xiàn)最低成本的資源分配目標(biāo)。Hendrik Moens和Filip De Turck考慮了物理網(wǎng)絡(luò)功能（PNF, physical network function）和虛擬網(wǎng)絡(luò)功能（VNF, virtualized network function）共存的場景，決定網(wǎng)絡(luò)中功能的正確放置位置，可以較為充分地利用物理和虛擬資源[5]，以實(shí)現(xiàn)服務(wù)功能鏈部署的擴(kuò)展性和靈活性。Kanizo等[6]用圖論來解決NFV的資源分配問題，將虛擬網(wǎng)絡(luò)功能和服務(wù)器（具有多個(gè)虛擬機(jī)）看作二分圖中兩個(gè)互不相交的子集，側(cè)重于解決節(jié)點(diǎn)功能失效時(shí)，由支持該功能的服務(wù)器進(jìn)行恢復(fù)，從而使故障功能恢復(fù)的可能性最大。

Mohammadkhan等[7]將關(guān)注點(diǎn)聚焦于網(wǎng)絡(luò)功能的放置以及業(yè)務(wù)流路由的均衡問題。為了給特定的服務(wù)功能鏈分配資源，Leivadeas等[8]在放置VNF和為功能鏈選路的同時(shí)，用加權(quán)系數(shù)對(duì)資源利用率和帶寬利用率進(jìn)行權(quán)衡，以實(shí)現(xiàn)網(wǎng)絡(luò)中負(fù)載平衡，從而有效提高資源利用率。Lopez等[9]提出了一個(gè)根據(jù)網(wǎng)絡(luò)拓?fù)浞胖锰摂M網(wǎng)絡(luò)功能并構(gòu)建功能鏈的方案，并給出了幾種啟發(fā)式算法，但更加側(cè)重于功能放置構(gòu)建服務(wù)功能鏈的方法。

Seliuchenko等[10]提出擴(kuò)展的多商品流模型（multi-commodity flow model），使用服務(wù)質(zhì)量標(biāo)準(zhǔn)來平衡負(fù)載，業(yè)務(wù)流的路由問題可以根據(jù)分類進(jìn)一步細(xì)化。Pham等[11]對(duì)NFV多徑路由的負(fù)載平衡問題進(jìn)行了分析，研究了基于NFV的網(wǎng)絡(luò)系統(tǒng)用戶需求的變化，提高響應(yīng)能力，從而優(yōu)化網(wǎng)絡(luò)性能。

Nam等[12]將NFV服務(wù)功能鏈引入無線接入網(wǎng)，使移動(dòng)邊緣計(jì)算（MEC, mobile edge computing）功能可以分配給附近的基站，從而使業(yè)務(wù)接入用戶設(shè)備獲得更低的時(shí)延體驗(yàn)。為了實(shí)現(xiàn)NFV的全部潛力，NFV擴(kuò)展到無線接入部分[13]，其缺點(diǎn)在于每個(gè)SFC需求的功能只能部署一次，而且每個(gè)功能需要放置在不同的節(jié)點(diǎn)上，這在一定程度上會(huì)引入鏈路時(shí)延。

Bari等[14]定位在企業(yè)網(wǎng)絡(luò)，致力于降低部署網(wǎng)絡(luò)功能的總成本。為了實(shí)現(xiàn)服務(wù)鏈部署，Sun等[15]考慮在服務(wù)鏈之間共享虛擬網(wǎng)絡(luò)功能，并在相同的節(jié)點(diǎn)中，部署相鄰的虛擬網(wǎng)絡(luò)功能以避免帶寬消耗。Hirwe等[16]針對(duì)VNF的放置影響交換機(jī)負(fù)載和帶寬利用效率等問題，提出一種高效的算法——LightChain，以消除乒乓流量。針對(duì)多個(gè)服務(wù)功能鏈的VNF共享，Savi等[17]考慮到升級(jí)成本和上下文轉(zhuǎn)移成本的影響，以最小化NFV激活節(jié)點(diǎn)作為優(yōu)化目標(biāo)。Beck等[18]考慮的是物理網(wǎng)絡(luò)的節(jié)點(diǎn)與鏈路出現(xiàn)故障時(shí)，如何進(jìn)行資源合理分配的問題。如果某些節(jié)點(diǎn)失效，則需要將部署在該節(jié)點(diǎn)處的網(wǎng)絡(luò)功能進(jìn)行合理的遷移或由備份的VNF實(shí)現(xiàn)，以保障彈性和擴(kuò)展性。

針對(duì)VNF鏈如何最佳地協(xié)調(diào)分配到網(wǎng)絡(luò)基礎(chǔ)設(shè)施上，Beck等[19]提出一種啟發(fā)式方法—— CoordVNF，旨在合理的運(yùn)行時(shí)間內(nèi)最大限度地降低帶寬利用率。Liu等[20]試圖確定放置中間件的最佳位置，以便優(yōu)化服務(wù)鏈性能，并提出兩種啟發(fā)式算法——貪婪算法和模擬退火算法來獲得次優(yōu)解，結(jié)果表明，其可以減少22％的端到端時(shí)延，平均節(jié)省38％的帶寬消耗。Bouet等[21]出于對(duì)網(wǎng)絡(luò)安全的考慮，將vDPI（virtual deep packet inspection）部署在網(wǎng)絡(luò)中，以成本最小化為目標(biāo)建立模型，結(jié)果證明提出的基于中心的貪婪算法很好地趨近最優(yōu)解。Mijumbi等[22]針對(duì)VNF部署問題，側(cè)重于提出虛擬網(wǎng)絡(luò)功能的映射與調(diào)度算法，其提出的3種貪婪算法以及基于禁忌搜索的啟發(fā)式算法中，后者表現(xiàn)出稍許的優(yōu)勢(shì)。

雖然目前已有很多文獻(xiàn)對(duì)NFV資源分配和SDN路由策略進(jìn)行了研究，但是仍存在著很多不足。例如，大多數(shù)文獻(xiàn)中構(gòu)成功能鏈的VNF，其占用資源單一，幾乎沒有考慮同時(shí)需要計(jì)算、存儲(chǔ)等多維資源需求的場景。另外，有些文獻(xiàn)僅從NFV資源分配或SDN路由策略某一個(gè)方面重點(diǎn)考慮，容易陷入局部最優(yōu)解，如何協(xié)調(diào)二者之間的關(guān)系，值得深入研究。

在這種背景下，本文研究動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)的NFV和SDN融合的資源優(yōu)化算法，根據(jù)網(wǎng)絡(luò)狀態(tài)的動(dòng)態(tài)變化、業(yè)務(wù)特性提出聯(lián)合優(yōu)化模型，確定業(yè)務(wù)驅(qū)動(dòng)的最優(yōu)傳輸性能的資源優(yōu)化方法，從而有效保障用戶QoS，并實(shí)現(xiàn)網(wǎng)絡(luò)性能優(yōu)化。為了方便求解優(yōu)化模型，本文根據(jù)VNF放置與業(yè)務(wù)流選路的順序提出了兩種啟發(fā)式算法——FRTP算法和PFBR算法。FRTP算法側(cè)重從用戶角度出發(fā)，使大量的數(shù)據(jù)分組在數(shù)據(jù)平面快速轉(zhuǎn)發(fā)，提高用戶體驗(yàn)；基于節(jié)點(diǎn)優(yōu)先級(jí)的PFBR算法，能有效地平衡網(wǎng)絡(luò)中的流量負(fù)載，提高服務(wù)鏈請(qǐng)求接受率。

2 系統(tǒng)模型

NFV技術(shù)將用戶的請(qǐng)求轉(zhuǎn)化為VNF構(gòu)成的服務(wù)功能鏈，SDN將流量管理與流量轉(zhuǎn)發(fā)分離，實(shí)現(xiàn)集中控制。在控制平面，SDN控制器管理網(wǎng)絡(luò)資源并控制全局網(wǎng)絡(luò)流量?；诰W(wǎng)絡(luò)狀態(tài)信息，控制器可相對(duì)于服務(wù)功能鏈的QoS需求，確定通信路徑，從而做出靈活的流量控制決策，經(jīng)由OpenFlow南向API，數(shù)據(jù)平面硬件用于轉(zhuǎn)發(fā)數(shù)據(jù)分組，優(yōu)化整個(gè)網(wǎng)絡(luò)的運(yùn)行。本文將服務(wù)功能鏈部署問題分為兩個(gè)階段。根據(jù)服務(wù)功能鏈的源節(jié)點(diǎn)、目的節(jié)點(diǎn)以及VNF次序，將服務(wù)功能鏈所需的一系列VNF放置在網(wǎng)絡(luò)上的NFV節(jié)點(diǎn)，以滿足用戶定制的網(wǎng)絡(luò)服務(wù)需求；SDN控制器根據(jù)服務(wù)功能鏈的需求，為其選擇一條最佳路徑，直至構(gòu)成一條完整的端到端路徑。

圖1給出了一條服務(wù)功能鏈的資源分配與鏈路映射示意，該條服務(wù)功能鏈共有5個(gè)虛擬網(wǎng)絡(luò)功能， SDN控制器以及VNF管理編排器（MANO, management and orchestration）依據(jù)SFC請(qǐng)求以及當(dāng)前網(wǎng)絡(luò)狀態(tài)，實(shí)時(shí)地將服務(wù)功能鏈所需的VNF分配在物理節(jié)點(diǎn)1、物理節(jié)點(diǎn)2、物理節(jié)點(diǎn)2、物理節(jié)點(diǎn)5、物理節(jié)點(diǎn)3處，另一方面，SDN控制器為該條服務(wù)功能鏈規(guī)劃的路徑為(s,1)→(1,2)→(2,3)→(3,5)→(5,4)→(4,3)→(3,)。

圖1 服務(wù)功能鏈資源分配與鏈路映射示意

3 NFV和SDN融合的資源優(yōu)化模型

本文提出的NFV和SDN融合的資源優(yōu)化模型分別如式(4)~式(12)所示。

4 算法描述

眾所周知，NP-Hard問題難以在多項(xiàng)式時(shí)間內(nèi)求解，因此，本文根據(jù)VNF放置與業(yè)務(wù)流選路的順序提出了兩種啟發(fā)式算法求解NFV和SDN融合的資源優(yōu)化模型。一種是對(duì)SFC先進(jìn)行靈活的路由決策，然后在該路徑上依次順序地放置所需的VNF，稱為先路由后放置的服務(wù)鏈部署算法；另一種則剛好相反，先將服務(wù)功能鏈所需的VNF放置在優(yōu)先級(jí)最高的節(jié)點(diǎn)上，繼而遍歷源節(jié)點(diǎn)、該節(jié)點(diǎn)以及目的節(jié)點(diǎn)，形成一條完整的路徑，稱為先放置后路由的服務(wù)鏈部署算法。

4.1 先路由后放置的服務(wù)鏈部署算法

算法1 先路由后放置的服務(wù)鏈部署算法

步驟1 根據(jù)該階段所有服務(wù)功能鏈的速率需求降序排序，標(biāo)注優(yōu)先級(jí)，向SDN控制器請(qǐng)求更新所有節(jié)點(diǎn)的可用資源以及網(wǎng)絡(luò)鏈路的剩余帶寬。

步驟3 為該條服務(wù)功能鏈選擇從源節(jié)點(diǎn)至目的節(jié)點(diǎn)的最短路徑作為最佳路徑。

步驟4 為該條服務(wù)功能鏈選擇從源節(jié)點(diǎn)至目的節(jié)點(diǎn)的前條最短路徑中剩余帶寬最大的一條作為最佳路徑。

步驟5 判斷該條最佳路徑的最小鏈路剩余帶寬是否大于速率需求，若是，轉(zhuǎn)向步驟6；否則，轉(zhuǎn)向步驟8。

步驟7 對(duì)選擇的路徑依次經(jīng)過的節(jié)點(diǎn)順序地放置VNF，直至放置完成，結(jié)束。

步驟8 繼續(xù)搜索從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的次佳路徑，重復(fù)步驟5~步驟7，若均不滿足，則結(jié)束，即拒絕該條服務(wù)功能鏈。

步驟9 重復(fù)步驟2~步驟8，直至所有的服務(wù)功能鏈均被部署或拒絕。

4.2 先放置后路由的服務(wù)鏈部署算法

算法2 先放置后路由的服務(wù)功能鏈部署算法

步驟1 根據(jù)該階段所有服務(wù)功能鏈的速率需求降序排序，標(biāo)注優(yōu)先級(jí)，并依次為服務(wù)功能鏈進(jìn)行VNF的放置。

步驟2 對(duì)物理網(wǎng)絡(luò)中能夠承載虛擬網(wǎng)絡(luò)功能的節(jié)點(diǎn)進(jìn)行優(yōu)先級(jí)降序排序，排序的標(biāo)準(zhǔn)由式(14)所示，節(jié)點(diǎn)的優(yōu)先級(jí)由該節(jié)點(diǎn)的可用資源以及選擇該節(jié)點(diǎn)引入的跳數(shù)共同決定。

步驟3 對(duì)于每條服務(wù)功能鏈，其每一跳的放置依據(jù)為選擇優(yōu)先級(jí)最大的節(jié)點(diǎn)作為當(dāng)前的最佳位置，判斷當(dāng)前選中的節(jié)點(diǎn)是否有足夠的資源承載VNF，即是否滿足資源需求式(13)，若滿足，轉(zhuǎn)向步驟4；否則轉(zhuǎn)向步驟5。

步驟4 將該條服務(wù)鏈所需的VNF貪婪地放置在該節(jié)點(diǎn)上，動(dòng)態(tài)更新節(jié)點(diǎn)的可用資源。

步驟5 繼續(xù)搜索節(jié)點(diǎn)優(yōu)先級(jí)次高的節(jié)點(diǎn)作為當(dāng)前最佳節(jié)點(diǎn)，直到能夠放置VNF，否則視為拒絕該服務(wù)功能鏈。

步驟7 在該條服務(wù)功能鏈的源節(jié)點(diǎn)、VNF的放置節(jié)點(diǎn)以及目的節(jié)點(diǎn)之間的每一跳，都采用最短路徑，形成首尾相連的完整路徑。

步驟8 判斷選擇的路徑的最小鏈路剩余帶寬是否大于速率需求，若大于，則該條服務(wù)功能鏈部署成功；否則轉(zhuǎn)步驟9。

步驟9 在該條服務(wù)功能鏈的源節(jié)點(diǎn)、VNF的放置節(jié)點(diǎn)以及目的節(jié)點(diǎn)之間的每一跳，對(duì)其進(jìn)行條最短路徑搜索，得到剩余帶寬最大的路徑。

步驟10 判斷選擇的路徑鏈路可用帶寬是否大于SFC速率需求，若大于，則該條服務(wù)功能鏈部署成功；否則視為拒絕該服務(wù)功能鏈。

步驟11 重復(fù)步驟2~步驟10，直至所有的服務(wù)功能鏈均被部署或拒絕。

4.3 算法復(fù)雜度分析

5 實(shí)驗(yàn)結(jié)果及性能分析

為了對(duì)本文提出的FRTP和PFBR算法進(jìn)行評(píng)估，將提出的啟發(fā)式算法重點(diǎn)在總轉(zhuǎn)發(fā)成本、負(fù)載均衡度、平均運(yùn)行時(shí)間以及服務(wù)功能鏈請(qǐng)求接受率等方面與基于最短路徑的服務(wù)功能鏈部署算法（其中VNF放置策略與FRTP算法相同）以及NAaP算法和AaP算法[15]進(jìn)行對(duì)比。NAaP算法和AaP算法在路由階段均優(yōu)先采用最短路徑，進(jìn)行VNF的放置時(shí)采用貪心算法，二者的區(qū)別在于后者將源節(jié)點(diǎn)與目的節(jié)點(diǎn)相同的SFC進(jìn)行融合，其中，帶寬需求疊加，相同的VNF可以共享。

表1 6節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)涞乃惴ńY(jié)果

5.1 實(shí)驗(yàn)環(huán)境和參數(shù)設(shè)置

由于本文提出的服務(wù)功能鏈部署算法，可以分為兩個(gè)階段，既包含VNF放置階段的算法，也包括服務(wù)鏈路由的算法。其中，VNF放置階段的算法運(yùn)行在Matlab 2015a環(huán)境中；FRTP和PFBR算法中的服務(wù)功能鏈路由算法部分寫入Ryu控制器（SDN控制器），利用Mininet仿真工具生成網(wǎng)絡(luò)拓?fù)洌赨buntu系統(tǒng)里進(jìn)行驗(yàn)證。

網(wǎng)絡(luò)中的節(jié)點(diǎn)具有承載VNF的能力，節(jié)點(diǎn)數(shù)量越多，其具有的VNF所需的各類資源越多，服務(wù)功能鏈部署成功的概率越大，請(qǐng)求被接受的越多。因此，本文在設(shè)置仿真實(shí)驗(yàn)時(shí)，將服務(wù)功能鏈數(shù)量與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量進(jìn)行相應(yīng)的調(diào)節(jié)。

本文實(shí)驗(yàn)在初始階段采用6個(gè)節(jié)點(diǎn)、8條鏈路的拓?fù)洌總€(gè)節(jié)點(diǎn)具有3種資源類型，資源總量服從均值為100、方差為31.8的均勻分布，鏈路帶寬為200 unit。SFC的數(shù)量為50~100，VNF種類共有7種，服務(wù)功能鏈所需的VNF為2~4種，對(duì)3種類型的資源需求均為0.2~1 unit，服務(wù)功能鏈的速率需求為1~5 unit，各種算法的對(duì)比結(jié)果如表1所示。然后，將網(wǎng)絡(luò)規(guī)模擴(kuò)展為20~100節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)，VNF的種類共有9種，每條服務(wù)功能鏈所需的VNF為3~6種，SFC數(shù)量由200條逐漸增加到1 000條。

5.2 性能分析

在較小網(wǎng)絡(luò)規(guī)模下，服務(wù)功能鏈的數(shù)量由50遞增至100，由表1可知，F(xiàn)RTP算法和PFBR算法在總帶寬成本以及流量負(fù)載均衡這兩個(gè)方面“勢(shì)均力敵”，并未表現(xiàn)出太多的差異。FRTP算法和PFBR算法與基于最短路徑的算法以及NAaP算法和AaP算法相比，總轉(zhuǎn)發(fā)成本略高一些，而負(fù)載均衡度得到了降低，這是由于后者總是優(yōu)先以最短路徑進(jìn)行業(yè)務(wù)流的轉(zhuǎn)發(fā)，因此，總轉(zhuǎn)發(fā)成本相對(duì)較低，相應(yīng)地，負(fù)載均衡度會(huì)急劇升高。FRTP算法的時(shí)間開銷略高于PFBR算法，其原因在于，在網(wǎng)絡(luò)規(guī)模較小的情況下，F(xiàn)RTP算法先確定轉(zhuǎn)發(fā)路徑，繼而依次順序（相對(duì)平均地）將VNF放置在選定的路徑經(jīng)過的節(jié)點(diǎn)上，其主要復(fù)雜度在于對(duì)每一條SFC中的VNF所需資源與節(jié)點(diǎn)資源總量進(jìn)行比對(duì)；而PFBR算法由于對(duì)服務(wù)功能鏈選擇優(yōu)先級(jí)最大的節(jié)點(diǎn)進(jìn)行VNF貪婪的放置方法，因此，在網(wǎng)絡(luò)規(guī)模較小時(shí)，運(yùn)行時(shí)間更短一些。但是，與最短路徑算法、NAaP算法、AaP算法相比，本文提出的兩種算法由于復(fù)雜度更高，平均運(yùn)行時(shí)間相對(duì)更長。AaP算法由于對(duì)SFC進(jìn)行融合，相比逐條部署SFC，算法復(fù)雜度更低，其部署速度更快。

圖2顯示了網(wǎng)絡(luò)拓?fù)涔?jié)點(diǎn)數(shù)目為50時(shí)的隨機(jī)網(wǎng)絡(luò)中服務(wù)功能鏈數(shù)量與轉(zhuǎn)發(fā)成本的關(guān)系。總體而言，轉(zhuǎn)發(fā)成本隨著服務(wù)功能鏈數(shù)量的增大而增大，F(xiàn)RTP算法的轉(zhuǎn)發(fā)成本低于PFBR算法，由于總轉(zhuǎn)發(fā)成本與選擇的路徑長度呈正相關(guān)，因此，二者的轉(zhuǎn)發(fā)成本均高于最短路徑算法、NAaP算法、AaP算法。

圖2 總轉(zhuǎn)發(fā)成本與SFC數(shù)量的關(guān)系

但僅考慮如何降低轉(zhuǎn)發(fā)成本是非常片面的，容易造成網(wǎng)絡(luò)中流量負(fù)載分布不均，有些鏈路異常擁塞，而有些鏈路非?？臻e的情況。圖3展示了隨著SFC數(shù)量的增加網(wǎng)絡(luò)中負(fù)載均衡度的變化。FRTP算法的負(fù)載均衡效果稍微遜色于PFBR算法，但這兩種算法與最短路徑算法、NAaP算法、AaP算法相比，在負(fù)載均衡方面表現(xiàn)出更強(qiáng)的優(yōu)勢(shì)。

圖3 網(wǎng)絡(luò)中負(fù)載均衡度與SFC數(shù)量的關(guān)系

在網(wǎng)絡(luò)規(guī)模逐漸增大時(shí)，服務(wù)功能鏈的數(shù)量固定為500條，總轉(zhuǎn)發(fā)成本并未隨著節(jié)點(diǎn)的增大而呈現(xiàn)較大差異，這是由于生成的隨機(jī)網(wǎng)絡(luò)的平均距離大致相同，選擇的路徑長度也差別不大，因此，F(xiàn)RTP算法、PFBR算法的總轉(zhuǎn)發(fā)成本相差不大。但是，網(wǎng)絡(luò)中負(fù)載均衡度卻有著較為明顯的差別，圖4描述了在網(wǎng)絡(luò)規(guī)模逐漸增大時(shí)負(fù)載均衡度的變化趨勢(shì)。整體而言，PFBR算法的負(fù)載均衡效果優(yōu)于FRTP算法，而最短路徑算法、NAaP算法、AaP算法明顯劣于本文提出的兩種算法，由此可見，F(xiàn)RTP算法、PFBR算法在路由階段的優(yōu)化起到了至關(guān)重要的作用。

圖4 網(wǎng)絡(luò)中負(fù)載均衡度與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的關(guān)系

當(dāng)網(wǎng)絡(luò)拓?fù)涔潭?0個(gè)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)時(shí)，算法的平均運(yùn)行時(shí)間隨著服務(wù)功能鏈數(shù)量的增大而增大，如圖5所示?；谧疃搪窂降乃惴ㄅcNAaP算法、AaP算法的時(shí)間開銷相差不大，而本文提出的算法尋求帶寬剩余量較多的空閑鏈路以平衡流量負(fù)載，其代價(jià)是更長的時(shí)間開銷。FRTP算法的時(shí)間開銷低于PFBR算法，與網(wǎng)絡(luò)規(guī)模較小時(shí)的結(jié)論看似相反，實(shí)際由于FRTP算法的服務(wù)鏈部署算法選擇的路徑長度幾乎不可能超過節(jié)點(diǎn)的數(shù)量，因此，PFBR的服務(wù)鏈部署算法在對(duì)每一條SFC計(jì)算節(jié)點(diǎn)優(yōu)先級(jí)時(shí)需花費(fèi)更多的時(shí)間。圖6描述了網(wǎng)絡(luò)規(guī)模逐漸增大時(shí)，各算法的時(shí)間開銷，與SFC數(shù)量增多時(shí)的結(jié)論無異。

圖5 算法時(shí)間開銷與SFC數(shù)量的關(guān)系

圖6 算法時(shí)間開銷與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的關(guān)系

本文實(shí)驗(yàn)還設(shè)置了一組仿真，在節(jié)點(diǎn)為20的隨機(jī)網(wǎng)絡(luò)中，將鏈路帶寬上限設(shè)為100 unit，服務(wù)功能鏈的速率需求約為4~10 unit，驗(yàn)證不同服務(wù)請(qǐng)求的接收率。圖7展示了在不同服務(wù)功能鏈請(qǐng)求強(qiáng)度下，各種算法的服務(wù)功能鏈請(qǐng)求接受率。AaP算法比最短路徑算法、NAaP算法的接受率略高，這是由于在帶寬和節(jié)點(diǎn)資源一定的情況下，AaP算法能夠通過在多條SFC之間共享相同的VNF，從而降低由于節(jié)點(diǎn)資源不足以承載VNF導(dǎo)致服務(wù)鏈部署失敗的概率。與最短路徑算法、NAaP算法、AaP算法相比，本文提出的服務(wù)鏈部署算法表現(xiàn)出了顯著的優(yōu)勢(shì)。其中，由于PFBR算法相比FRTP算法能夠較好地平衡網(wǎng)絡(luò)中的資源流量負(fù)載，因此，網(wǎng)絡(luò)的資源能夠得到更加充分的利用，服務(wù)功能鏈請(qǐng)求接受率相比其他算法有明顯的提高。

圖7 不同服務(wù)功能鏈請(qǐng)求強(qiáng)度與接受率的關(guān)系

綜上，本文提出的FRTP算法、PFBR算法與最短路徑算法、NAaP算法、AaP算法相比，在犧牲一部分轉(zhuǎn)發(fā)成本的基礎(chǔ)上，獲取了更多的鏈路可用資源，能更有效地平衡網(wǎng)絡(luò)中的流量負(fù)載，且提升服務(wù)功能鏈請(qǐng)求接受率。但FRTP算法與PFBR算法相比，更側(cè)重于降低總轉(zhuǎn)發(fā)成本，使大量的數(shù)據(jù)流在網(wǎng)絡(luò)中快速轉(zhuǎn)發(fā)，在一定程度上可降低服務(wù)功能鏈響應(yīng)速度，提高用戶體驗(yàn)，其也可以作為在線算法，實(shí)時(shí)地部署服務(wù)功能鏈。另一方面，基于PFBR的服務(wù)鏈部署算法在中、大規(guī)模網(wǎng)絡(luò)以及SFC數(shù)量較多時(shí)可以更加有效地平衡網(wǎng)絡(luò)中的負(fù)載，從而提高網(wǎng)絡(luò)中整體的鏈路利用率，提升服務(wù)功能鏈請(qǐng)求接受率，其優(yōu)勢(shì)用于離線算法中更為明顯。

6 結(jié)束語

本文主要研究了物聯(lián)網(wǎng)環(huán)境下服務(wù)功能鏈的部署問題，根據(jù)網(wǎng)絡(luò)狀態(tài)的動(dòng)態(tài)變化、業(yè)務(wù)特性，提出NFV和SDN融合的虛擬網(wǎng)絡(luò)功能放置與服務(wù)鏈路由的聯(lián)合優(yōu)化模型。為了方便求解優(yōu)化模型，本文提出了兩種啟發(fā)式算法，經(jīng)仿真驗(yàn)證，與其他算法相比，F(xiàn)RTP和PFBR算法能顯著平衡網(wǎng)絡(luò)中的流量負(fù)載，提高請(qǐng)求接受率。就本文提出的算法而言，F(xiàn)RTP算法作為在線算法，在實(shí)時(shí)部署服務(wù)功能鏈方面，能夠使大量的數(shù)據(jù)分組在數(shù)據(jù)平面快速轉(zhuǎn)發(fā)，提高用戶體驗(yàn)；而PFBR算法可作為離線算法，雖然其在降低總轉(zhuǎn)發(fā)成本方面略顯遜色，但在負(fù)載均衡方面優(yōu)勢(shì)凸顯，使服務(wù)功能鏈請(qǐng)求接受率得到顯著提高。兩種算法的有益結(jié)合能夠更好地部署服務(wù)功能鏈。在大規(guī)模網(wǎng)絡(luò)和業(yè)務(wù)請(qǐng)求非常多的場景中，本文提出的兩種算法雖能有效平衡網(wǎng)絡(luò)流量負(fù)載，但時(shí)間開銷增加很快。因此，在今后的工作中，期望研究更優(yōu)化的啟發(fā)式算法，在兼顧負(fù)載平衡的同時(shí)，盡可能地降低時(shí)間開銷。

[1] BIZANIS N, KUIPERS F A. SDN and virtualization solutions for the Internet of Things: a survey[J]. IEEE Access, 2016, 4(99): 5591-5606.

[2] MECHTRI M, GHRIBI C, SOUALAH O, et al. NFV orchestration framework addressing SFC challenges[J]. IEEE Communications Magazine, 2017, 55(6):16-23.

[3] 袁泉, 湯紅波, 黃開枝, 等. 基于Q-learning算法的vEPC虛擬網(wǎng)絡(luò)功能部署方法[J]. 通信學(xué)報(bào), 2017, 38(8): 172-182.

YUAN Q, TANG H B, HUANG K Z, et al. Deployment method for vEPC virtualized network function via Q-learning[J]. Journal on Communications, 2017, 38(8): 172-182.

[4] WANG L H, LU Z M, WEN X M, et al. Joint optimization of service function chaining and resource allocation in network function virtualization[J]. IEEE Access, 2016, 4: 8084-8094.

[5] MOENS H, TURCK F D. Customizable function chains: managing service chain variability in Hybrid NFV networks[J]. IEEE Transactions on Network and Service Management, 2016, 13(4): 711-724.

[6] KANIZO Y, ROTTENSTREICH O, SEGALL I, et al. Optimizing virtual backup allocation for middleboxes[J]. IEEE Journals & Magazines, 2017, 25(5): 2759-2772.

[7] MOHAMMADKHAN A, GHAPANI S, LIU G, et al. Virtual function placement and traffic steering in flexible and dynamic software defined networks[C]//The 21st IEEE International Workshop on Local and Metropolitan Area Networks. 2015: 1-6.

[8] LEIVADEAS A, FALKNER M, LAMBADARIS I, et al. Resource management and orchestration for a dynamic service chain steering model[C]//2016 IEEE Global Communications Conference (GLOBECOM). 2016.

[9] LOPEZ M A, MATTOS D M F, DUARTE O C M B. Evaluating allocation heuristics for an efficient virtual Network Function chaining[C]//2016 7th International Conference on the Network of the Future (NOF). 2016.

[10] SELIUCHENKO M, LAVRIV O, PANCHENKO O, et al. Enhanced multi-commodity flow model for QoS-aware routing in SDN[C]//2016 International Conference Radio Electronics & Info Communications (UkrMiCo). 2016.

[11] PHAM T M, PHAM L M. Load balancing using multipath routing in network functions virtualization[C]//2016 IEEE RIVF International Conference on Computing & Communication Technologies, Research, Innovation, and Vision for the Future (RIVF).2016: 85-90.

[12] NAM Y, SONG S, CHUNG J M. Clustered NFV service chaining optimization in mobile edge clouds[J]. IEEE Communications Letters, 2017, 21(2): 350-353.

[13] RIGGIO R, BRADAI A, HARUTYUNYAN D, et al. Schedulingwireless virtual networks functions[J]. IEEE Transactions on Network and Service Management, 2016, 13(2): 240-252.

[14] BARI M F, CHOWDHURY S R, AHAMED R, et al. Orchestrating virtualized network functions[J]. IEEE Transactions on Network and Service Management, 2016, 13(4): 725-739.

[15] SUN Q Y, LU P, LU W, et al. Forecast-assisted NFV service chain deployment based on affiliation-aware vNF placement[C]//2016 IEEE Global Communications Conference (GLOBECOM). 2016.

[16] HIRWE A, KATAOKA K. LightChain: A lightweight optimization of VNF placement for service chaining in NFV[C]//2016 IEEE NetSoft Conference and Workshops (NetSoft). 2016, 33-37.

[17] SAVI M, TOMATORE M, VERTICALE G. Impact of processing costs on service chain placement in network functions virtualization[C]//2015 IEEE Conference on Network Function Virtualization and Software Defined Network (NFV-SDN). 2015: 191-197.

[18] BECK M T, BOTERO J F, SAMELIN K. Resilient allocation of service function chains[C]//2016 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN). 2016: 128 - 133.

[19] BECK M T, BOTERO J F. Coordinated allocation of service function chains[C]//2015 IEEE Global Communications Conference (GLOBECOM). 2015: 1-7.

[20] LIU J, LI Y, ZHANG Y, et, al. Improve service chaining performance with optimized middlebox placement[J]. IEEE Transactions on Services Computing, 2017, 10(4): 560-573.

[21] BOUET M, LEGUAY J, CONAN V. Cost-based placement of vDPI functions in NFV infrastructures[C]//The 2015 1st IEEE Conference on Network Softwarization (NetSoft). 2015: 1-9.

[22] MIJUMBI R, SERRAT J, GORRICHO J L, et al. Design and evaluation of algorithms for mapping and scheduling of virtual network functions[C]//The 2015 1st IEEE Conference on Network Softwarization (NetSoft). 2015: 1-9.

[23] GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. New York: W H Freeman & Company. 1979.

Resource optimization algorithm of combination of NFV and SDN for application of multiple services

ZHU Xiaorong, ZHANG Qian

College of Communications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

Various services of internet of things (IoT) require flexible network deployment to guarantee different quality of service (QoS). Aiming at the problem of IoT service function chain deployment, network function virtualization (NFV) and software defined networking (SDN) were combined to optimize resources. Considering forwarding cost and traffic load balance, a joint optimization model of virtual network function placement and service function chain routing was given and was proved to be NP-Hard. In order to solve this model, two heuristic algorithms were proposed. One was the service chain deployment algorithm of first routing then placing (FRTP) and the other was the placing followed by routing (PFBR) based on node priority. Simulation results demonstrate that FRTP and PFBR algorithm can significantly balance network traffic load while alleviating congestion and improving the acceptance ratio of the chain requests compared with other algorithms.

internet of things, VNF, service function chain deployment, node priority, load balance

TN915.81

A

10.11959/j.issn.1000?436x.2018235

朱曉榮（1977–），女，山東臨沂人，南京郵電大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)?G通信系統(tǒng)、異構(gòu)網(wǎng)絡(luò)、物聯(lián)網(wǎng)等關(guān)鍵技術(shù)及系統(tǒng)研發(fā)。

張倩（1994–），女，江蘇徐州人，南京郵電大學(xué)碩士生，主要研究方向?yàn)榫W(wǎng)絡(luò)功能虛擬化、軟件定義網(wǎng)絡(luò)等。

2018?01?29；

2018?05?10

朱曉榮，xrzhu@njupt.edu.cn

國家自然科學(xué)基金資助項(xiàng)目（No.61871237）；江蘇省高校自然科學(xué)研究重大項(xiàng)目基金資助項(xiàng)目（No.16KJA510005）；江蘇省研究生科研與實(shí)踐創(chuàng)新計(jì)劃基金資助項(xiàng)目（No.KYCX17_0767）

The National Natural Science Foundation of China (No.61871237), The Natural Science Foundation of the Higher Education Institutions of Jiangsu Province (No.16KJA510005), Postgraduate Research & Practice Innovation Program of Jiangsu Province (No. KYCX17_0767)