劉彩霞 盧干強(qiáng) 湯紅波 王曉雷 趙 宇

?

一種基于Viterbi算法的虛擬網(wǎng)絡(luò)功能自適應(yīng)部署方法

劉彩霞 盧干強(qiáng)*湯紅波 王曉雷 趙 宇

(國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州 450002)(移動(dòng)互聯(lián)網(wǎng)安全技術(shù)國(guó)家工程實(shí)驗(yàn)室 北京 100876)

為了應(yīng)對(duì)移動(dòng)數(shù)據(jù)流量的爆炸性增長(zhǎng)，5G移動(dòng)通信網(wǎng)將引入新型的架構(gòu)設(shè)計(jì)。軟件定義網(wǎng)絡(luò)和網(wǎng)絡(luò)功能虛擬化是網(wǎng)絡(luò)轉(zhuǎn)型的關(guān)鍵技術(shù)，將驅(qū)動(dòng)移動(dòng)通信網(wǎng)絡(luò)架構(gòu)的創(chuàng)新，服務(wù)鏈虛擬網(wǎng)絡(luò)功能的部署是網(wǎng)絡(luò)虛擬化研究中亟待解決的問(wèn)題。該文針對(duì)已有部署方法未考慮服務(wù)鏈中虛擬網(wǎng)絡(luò)功能間順序約束和移動(dòng)業(yè)務(wù)特點(diǎn)的問(wèn)題，提出一種基于Viterbi算法的虛擬網(wǎng)絡(luò)功能自適應(yīng)部署方法。該方法實(shí)時(shí)感知底層節(jié)點(diǎn)的資源變化并動(dòng)態(tài)調(diào)整拓?fù)浣Y(jié)構(gòu)，采用隱馬爾科夫模型描述滿足資源約束的可用的底層網(wǎng)絡(luò)節(jié)點(diǎn)拓?fù)湫畔?，基于Viterbi算法在候選節(jié)點(diǎn)中選擇時(shí)延最短的服務(wù)路徑。實(shí)驗(yàn)表明，與其它的虛擬網(wǎng)絡(luò)功能部署方法相比，該方法降低了服務(wù)鏈的服務(wù)處理時(shí)間，并提高了服務(wù)鏈的請(qǐng)求接受率和底層資源的成本效率。

5G；網(wǎng)絡(luò)功能虛擬化；虛擬網(wǎng)絡(luò)功能部署；隱馬爾科夫模型；Viterbi算法；自適應(yīng)

1 引言

隨著移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展，智能終端和OTT業(yè)務(wù)正趨向主導(dǎo)地位，這大大增加了移動(dòng)數(shù)據(jù)業(yè)務(wù)的消費(fèi)需求。經(jīng)研究預(yù)測(cè)，2010~2020年間，移動(dòng)數(shù)據(jù)流量將增長(zhǎng)1000倍[1]。為了滿足業(yè)務(wù)流量的需求，運(yùn)營(yíng)商需要不斷加大基礎(chǔ)設(shè)施建設(shè)，擴(kuò)充網(wǎng)絡(luò)容量，因而網(wǎng)絡(luò)規(guī)模不斷膨脹，運(yùn)營(yíng)商的運(yùn)營(yíng)成本不斷提高。此外，隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展，移動(dòng)通信網(wǎng)被邊緣化和管道化的趨勢(shì)日益明顯，因而運(yùn)營(yíng)商的業(yè)務(wù)利潤(rùn)將逐漸下滑[2]。運(yùn)營(yíng)成本增加而收益逐漸降低的趨勢(shì)迫使運(yùn)營(yíng)商不得不進(jìn)行網(wǎng)絡(luò)轉(zhuǎn)型，采用諸如網(wǎng)絡(luò)功能虛擬化等技術(shù)來(lái)降低運(yùn)維成本，同時(shí)增加運(yùn)營(yíng)效益。5G提出將滿足超高流量密度、超高連接數(shù)密度、超高移動(dòng)性的需求。此外，包括5G在內(nèi)的未來(lái)移動(dòng)通信網(wǎng)將是多種異構(gòu)網(wǎng)絡(luò)融合互通且要求新業(yè)務(wù)的創(chuàng)新與部署更加靈活。因此，引入新型移動(dòng)通信網(wǎng)絡(luò)架構(gòu)勢(shì)在必行。

在信息通信技術(shù)(ICT)融合發(fā)展的背景下，以軟件定義網(wǎng)絡(luò)(SDN)和網(wǎng)絡(luò)功能虛擬化(NFV)為代表的新技術(shù)，將共同驅(qū)動(dòng)5G及未來(lái)移動(dòng)通信網(wǎng)的架構(gòu)創(chuàng)新，為解決移動(dòng)通信網(wǎng)發(fā)展中面臨的挑戰(zhàn)提供了途徑。SDN的核心是實(shí)現(xiàn)網(wǎng)絡(luò)控制平面和數(shù)據(jù)平面的分離，NFV的主要思想是實(shí)現(xiàn)網(wǎng)元功能與專屬硬件平臺(tái)的解耦，二者將增強(qiáng)網(wǎng)絡(luò)的靈活性和可擴(kuò)展性，促進(jìn)基礎(chǔ)設(shè)施資源的高效共享，大幅提高網(wǎng)絡(luò)建設(shè)的成本效率，從而降低網(wǎng)絡(luò)的CAPEX和OPEX，增大基礎(chǔ)設(shè)施收益[3]。

目前，移動(dòng)通信網(wǎng)的虛擬化研究處于起步階段，存在許多亟待研究的問(wèn)題。本文主要關(guān)注分組核心網(wǎng)(Evolved Packet Core, EPC)應(yīng)用場(chǎng)景下虛擬化網(wǎng)絡(luò)功能(VNF)的部署問(wèn)題。移動(dòng)通信對(duì)系統(tǒng)的服務(wù)時(shí)延要求較高，5G提出為用戶提供毫秒級(jí)的端到端時(shí)延。因此，如何在滿足資源約束的條件下保證業(yè)務(wù)請(qǐng)求承載量，并降低服務(wù)時(shí)延是VNF部署面臨的挑戰(zhàn)。SDN早在2006年被斯坦福大學(xué)Clean Slate課題提出，NFV于2012年被運(yùn)營(yíng)商聯(lián)盟提出，重在解決網(wǎng)絡(luò)的僵化問(wèn)題。隨著5G技術(shù)的提出，業(yè)界將SDN和NFV作為移動(dòng)通信網(wǎng)網(wǎng)絡(luò)架構(gòu)演進(jìn)的兩項(xiàng)重要技術(shù)，也是5G移動(dòng)通信網(wǎng)的核心技術(shù)。文獻(xiàn)[4]提出一種新型網(wǎng)絡(luò)架構(gòu)，實(shí)現(xiàn)了數(shù)據(jù)轉(zhuǎn)發(fā)和功能特征的分離，網(wǎng)絡(luò)只負(fù)責(zé)數(shù)據(jù)轉(zhuǎn)發(fā)，功能特征轉(zhuǎn)移到云平臺(tái)，可根據(jù)用戶的需求自動(dòng)化遷移或伸縮。文獻(xiàn)[5]提出一種基于SDN的可擴(kuò)展架構(gòu)，通過(guò)集中化的配置可以動(dòng)態(tài)地將不同類型的業(yè)務(wù)流轉(zhuǎn)發(fā)到任何中間件，允許用戶自由選擇網(wǎng)絡(luò)服務(wù)。文獻(xiàn)[6]提出應(yīng)用NFV技術(shù)管理5G網(wǎng)絡(luò)，并討論了5G虛擬化中VNF實(shí)例化等關(guān)鍵問(wèn)題。文獻(xiàn)[7]提出一種VNF資源分配模型，該模型將網(wǎng)絡(luò)的功能分解為不同的組件，實(shí)現(xiàn)功能虛擬化，并根據(jù)需要?jiǎng)討B(tài)重組提供功能服務(wù)，可以快速應(yīng)對(duì)資源請(qǐng)求變化，提高VNF的部署效率。文獻(xiàn)[8]針對(duì)高動(dòng)態(tài)網(wǎng)絡(luò)及其服務(wù)環(huán)境的管理問(wèn)題，提出一種VNF編排模型，通過(guò)監(jiān)控系統(tǒng)資源狀態(tài)，動(dòng)態(tài)編排VNF節(jié)點(diǎn)，實(shí)現(xiàn)虛擬網(wǎng)絡(luò)的自動(dòng)化部署及資源的自動(dòng)化分配。文獻(xiàn)[9]提出一種VNF功能鏈架構(gòu)，提出資源池概念，即同種類型的VNF部署在同一資源池，可以減少VNF間不必要的通信，但該模型對(duì)不同類型VNF之間的帶寬提出更高要求。為了有效地運(yùn)行虛擬化的網(wǎng)絡(luò)服務(wù)，文獻(xiàn)[10]提出了HSD和VSD兩種VNF部署方案，并分析了其在資源約束下的部署開(kāi)銷。目前，VNF部署問(wèn)題的研究處于概念驗(yàn)證階段，可參考的方法很少?，F(xiàn)有的方法更多地關(guān)注節(jié)點(diǎn)資源利用率且未考慮移動(dòng)業(yè)務(wù)的特點(diǎn)，傳統(tǒng)的虛擬網(wǎng)絡(luò)映射算法未考慮功能鏈中VNF間的順序約束，并不完全適用。因此，本文提出的VNF自適應(yīng)部署方法主要關(guān)注時(shí)延，以應(yīng)對(duì)5G低時(shí)延的性能要求。

2 網(wǎng)絡(luò)模型與問(wèn)題描述

5G及未來(lái)移動(dòng)通信網(wǎng)將是基于IT技術(shù)的集中化的云網(wǎng)絡(luò)，將打破網(wǎng)絡(luò)的封閉性。虛擬化技術(shù)是網(wǎng)絡(luò)高彈性和可重構(gòu)的基礎(chǔ)，是解決運(yùn)營(yíng)商網(wǎng)絡(luò)未來(lái)發(fā)展的關(guān)鍵技術(shù)，SDN和NFV將促進(jìn)運(yùn)營(yíng)商網(wǎng)絡(luò)的數(shù)字化轉(zhuǎn)型[11,12]。

2.1 移動(dòng)通信網(wǎng)絡(luò)虛擬化模型

如圖1所示，SDN將網(wǎng)絡(luò)實(shí)體中異構(gòu)的網(wǎng)元抽取分離，不同實(shí)體中同質(zhì)的網(wǎng)元集中化部署，實(shí)現(xiàn)了控制平面與數(shù)據(jù)平面的分離，在智能編排管理器的控制下，表現(xiàn)出高度的虛擬化和智能化特性。如圖2所示，NFV將網(wǎng)元功能與專屬硬件平臺(tái)解耦，網(wǎng)元功能從高昂的專屬硬件遷移到通用的服務(wù)器，實(shí)現(xiàn)了網(wǎng)元功能的軟件化、模塊化和IT承載，并通過(guò)VNF的虛擬化實(shí)例部署提供服務(wù)[13]。該架構(gòu)實(shí)現(xiàn)了網(wǎng)絡(luò)資源虛擬化，即對(duì)網(wǎng)絡(luò)進(jìn)行邏輯化的抽象和封裝，屏蔽復(fù)雜的物理細(xì)節(jié)；實(shí)現(xiàn)了網(wǎng)絡(luò)的集中化控制，可以支持多個(gè)網(wǎng)絡(luò)實(shí)體的協(xié)調(diào)和調(diào)度；實(shí)現(xiàn)了網(wǎng)絡(luò)的智能化，即自動(dòng)感知VNF請(qǐng)求及資源狀態(tài)，并隨著VNF的遷移或網(wǎng)絡(luò)位置的改變，自動(dòng)化配置網(wǎng)絡(luò)。網(wǎng)絡(luò)服務(wù)的實(shí)現(xiàn)需要一組有序的網(wǎng)元功能，如圖3所示。為了滿足不同的業(yè)務(wù)請(qǐng)求，運(yùn)營(yíng)商需要部署一系列有順序約束的網(wǎng)元功能集合，從而實(shí)現(xiàn)所需要的功能服務(wù)，該有序的功能集合被稱為“功能鏈”或“服務(wù)鏈”[14]。在虛擬化模型中，網(wǎng)絡(luò)可根據(jù)業(yè)務(wù)需求動(dòng)態(tài)實(shí)例化，促進(jìn)了底層資源的共享，業(yè)務(wù)的部署與編排更加智能化，增強(qiáng)了網(wǎng)絡(luò)的靈活性和可擴(kuò)展性。不同的部署方案會(huì)影響到網(wǎng)絡(luò)的服務(wù)質(zhì)量，因此，VNF部署是移動(dòng)通信網(wǎng)虛擬化的關(guān)鍵問(wèn)題之一。

2.2 服務(wù)鏈功能部署問(wèn)題描述

NFV可以根據(jù)需要?jiǎng)討B(tài)調(diào)配VNF，是顛覆性的網(wǎng)絡(luò)重構(gòu)技術(shù)。EPC網(wǎng)絡(luò)由多種網(wǎng)元功能組成，網(wǎng)絡(luò)服務(wù)基于功能鏈。在傳統(tǒng)的網(wǎng)絡(luò)架構(gòu)中，改變網(wǎng)元功能的連接方式或部署新功能比較復(fù)雜。NFV簡(jiǎn)化了網(wǎng)元功能的連接和部署方式，使服務(wù)更加靈活。在網(wǎng)絡(luò)虛擬化模型中，不同的VNF邏輯服務(wù)鏈，具有不同的功能表現(xiàn)，可根據(jù)部署策略在底層節(jié)點(diǎn)選擇部署位置與服務(wù)路徑。如圖4所示，VNF管理層根據(jù)服務(wù)請(qǐng)求，組合功能組件形成邏輯的VNF鏈；底層網(wǎng)絡(luò)是通用的硬件資源平臺(tái)，實(shí)際承載服務(wù)請(qǐng)求；虛擬化資源管理平臺(tái)根據(jù)服務(wù)鏈的請(qǐng)求信息和底層資源的狀態(tài)信息，實(shí)現(xiàn)服務(wù)鏈VNF在底層網(wǎng)絡(luò)中的部署。

圖1 移動(dòng)通信網(wǎng)絡(luò)虛擬化模型

圖3 網(wǎng)絡(luò)功能虛擬化示意圖

圖4 服務(wù)鏈功能部署模型

圖5 底層物理網(wǎng)絡(luò)拓?fù)鋱D

服務(wù)鏈功能的實(shí)例化流程，如圖6所示。首先，根據(jù)用戶的服務(wù)請(qǐng)求組合VNF功能模塊，形成邏輯功能鏈；其次，根據(jù)底層網(wǎng)絡(luò)的資源狀態(tài)信息，獲得當(dāng)前可部署位置邏輯視圖，并將功能鏈與底層網(wǎng)絡(luò)可用信息的邏輯視圖按照一定策略匹配。若服務(wù)功能鏈映射成功，則底層資源池為其分配相應(yīng)的資源實(shí)現(xiàn)服務(wù)鏈功能的實(shí)例化；然后，輸出服務(wù)鏈中VNF及鏈路的部署信息，并更新底層網(wǎng)絡(luò)的狀態(tài)信息，設(shè)置服務(wù)鏈的生存周期并實(shí)時(shí)監(jiān)測(cè)其生存狀態(tài)，基于服務(wù)鏈構(gòu)建的新業(yè)務(wù)即可向用戶提供相應(yīng)的服務(wù)。定義表示服務(wù)的起始時(shí)刻，表示當(dāng)前時(shí)刻，當(dāng)服務(wù)鏈的服務(wù)時(shí)間時(shí)，服務(wù)結(jié)束，收回為其分配的資源。定義二元變量表示服務(wù)鏈?zhǔn)欠癫渴鸪晒?，若服?wù)鏈部署成功，則；否則，。

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

虛擬化網(wǎng)絡(luò)功能部署主要是實(shí)現(xiàn)系統(tǒng)容量的優(yōu)化配置，實(shí)現(xiàn)資源的動(dòng)態(tài)共享。服務(wù)鏈功能部署面臨兩個(gè)挑戰(zhàn)：其一，如何區(qū)別服務(wù)請(qǐng)求的差異性，組合不同的VNF形成邏輯功能鏈并映射到底層網(wǎng)絡(luò)；其二，如何制定部署策略，實(shí)現(xiàn)VNF的優(yōu)化部署，滿足差異化的服務(wù)請(qǐng)求，并提高服務(wù)請(qǐng)求接受率和資源利用率。與互聯(lián)網(wǎng)相比，移動(dòng)通信網(wǎng)對(duì)服務(wù)的時(shí)延要求更高。因此，本文考慮在保證資源約束的前提下，將服務(wù)時(shí)延作為服務(wù)鏈VNF部署的優(yōu)化目標(biāo)，即根據(jù)服務(wù)鏈的順序約束，在底層物理網(wǎng)絡(luò)中尋找服務(wù)請(qǐng)求的時(shí)延最短服務(wù)路徑。

圖6 服務(wù)鏈功能實(shí)例化流程

本文中主要參數(shù)符號(hào)定義如表1所示。

表1主要參數(shù)符號(hào)定義

參數(shù)定義 服務(wù)節(jié)點(diǎn)的物理資源集合， 實(shí)例化的資源需求集合， VNF功能模塊集合 服務(wù)節(jié)點(diǎn)中資源的容量 f實(shí)例化對(duì)資源的需求數(shù)量 f功能模塊實(shí)例化的處理容量 物理網(wǎng)絡(luò)轉(zhuǎn)發(fā)節(jié)點(diǎn),之間物理鏈路的帶寬容量 物理網(wǎng)絡(luò)轉(zhuǎn)發(fā)節(jié)點(diǎn),之間物理鏈路的時(shí)延 服務(wù)鏈l中VNF功能節(jié)點(diǎn)之間的帶寬需求 服務(wù)鏈l的時(shí)延約束 服務(wù)鏈中功能f在服務(wù)節(jié)點(diǎn)n的處理時(shí)延 服務(wù)鏈l的生存周期

3 算法描述

底層網(wǎng)絡(luò)模型如圖5所示，由傳輸管道和云計(jì)算服務(wù)平臺(tái)組成。VNF部署算法分以下幾步：首先，根據(jù)服務(wù)請(qǐng)求組合邏輯功能；其次，根據(jù)邏輯功能鏈和當(dāng)前網(wǎng)絡(luò)狀態(tài)描述底層網(wǎng)絡(luò)中全部VNF可部署位置的邏輯視圖；然后，根據(jù)策略部署功能鏈，并輸出部署方案。

3.1 基于隱馬爾可夫模型的底層網(wǎng)絡(luò)描述

如圖5所示，在VNF部署問(wèn)題中，服務(wù)鏈的VNF組成及其上下文關(guān)系和VNF可部署的位置是可以觀測(cè)的，但服務(wù)鏈的具體服務(wù)路徑是無(wú)法觀測(cè)的。因此，服務(wù)鏈中VNF的部署問(wèn)題具有隱馬爾可夫特性，服務(wù)路徑是一條隱馬爾可夫鏈。

3.2基于Viterbi算法的服務(wù)鏈路徑選擇

Viterbi算法可用于尋找觀測(cè)事件的隱含狀態(tài)序列，適用于隱馬爾可夫模型。Viterbi算法的特點(diǎn)可以解決有向圖網(wǎng)絡(luò)中的路徑優(yōu)化問(wèn)題，可用于服務(wù)鏈中VNF的優(yōu)化部署。如圖8所示，VNF1和VNF2分別表示服務(wù)鏈中相鄰的上下文兩種功能。,,表示在時(shí)刻部署在節(jié)點(diǎn)的處理時(shí)延；表示在時(shí)刻部署在節(jié)點(diǎn)的處理時(shí)延，表示在時(shí)刻,分別部署在節(jié)點(diǎn),時(shí)，與節(jié)點(diǎn),關(guān)聯(lián)的轉(zhuǎn)發(fā)節(jié)點(diǎn)間的鏈路時(shí)延。定義維特比變量表示按照服務(wù)鏈的順序約束完成在節(jié)點(diǎn)部署時(shí)的最短時(shí)延。從流入節(jié)點(diǎn)開(kāi)始，在每層部署中計(jì)算層到層候選節(jié)點(diǎn)的最短時(shí)延，直至流出轉(zhuǎn)發(fā)節(jié)點(diǎn)。

圖7 服務(wù)鏈中VNF可部署位置的邏輯視圖

圖8 基于Viterbi算法的VNF部署

目標(biāo)函數(shù)：

約束條件：

3.3 服務(wù)鏈VNF的自動(dòng)化部署

基于Viterbi算法的VNF自動(dòng)化部署方法如表2所示。

3.4 復(fù)雜度分析

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

為了評(píng)估模型可行性及算法有效性，本文采用服務(wù)請(qǐng)求的處理時(shí)間、接受率、底層網(wǎng)絡(luò)的收益和平均利潤(rùn)成本比作為性能評(píng)價(jià)指標(biāo)，并與基于貪婪算法(Greedy)和禁忌搜索(Tabu Search)的方法比較[15]。

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)配置為Intel Core i7-4790 3.60 GHz CPU、8 GB內(nèi)存、Linux系統(tǒng)，參數(shù)設(shè)置如表3，表4所示，每對(duì)物理轉(zhuǎn)發(fā)節(jié)點(diǎn)之間等概率生成物理鏈路。為了評(píng)估算法的自適應(yīng)性，假設(shè)服務(wù)請(qǐng)求動(dòng)態(tài)到達(dá)，且服從強(qiáng)度為0~1000的泊松分布。每個(gè)服務(wù)請(qǐng)求由一個(gè)或多個(gè)VNF組成，數(shù)量服從2~5的均勻分布。

表2 基于Viterbi的VNF自動(dòng)化部署方法

4.2 性能分析

圖9表示不同請(qǐng)求強(qiáng)度下不同算法的請(qǐng)求接受率性能。從圖中可以看出，隨著請(qǐng)求強(qiáng)度的增大，請(qǐng)求接受率不斷降低，但不同算法的請(qǐng)求接受率的下降速度和幅度不同。在相同的資源環(huán)境和服務(wù)請(qǐng)求強(qiáng)度下，基于Viterbi算法的VNF部署方法的下降速度和幅度最小?；贕reedy的GFP和GLL算法以及基于TS的方法主要考慮節(jié)點(diǎn)的資源利用，沒(méi)有考慮鏈路資源的使用情況。隨著請(qǐng)求強(qiáng)度的增加，有限的鏈路資源限制的服務(wù)鏈的功能部署，使請(qǐng)求接受率大幅下降。而基于Viterbi算法的部署方法綜合考慮了底層節(jié)點(diǎn)和鏈路的資源狀態(tài)，且對(duì)VNF實(shí)行細(xì)粒度管理，增加了VNF部署和資源分配的靈活性。因此，基于Viterbi算法的VNF部署存在更優(yōu)的部署方案，可以接受更多的服務(wù)請(qǐng)求，請(qǐng)求接受率最高。雖然GFP和GLL都是基于Greedy的方法，但GFP以底層節(jié)點(diǎn)的處理能力作為選擇策略，造成服務(wù)請(qǐng)求在節(jié)點(diǎn)的處理等待時(shí)間較長(zhǎng)，而GLL以節(jié)點(diǎn)緩存的容量作為選擇策略，使服務(wù)請(qǐng)求到達(dá)后能夠及時(shí)處理，從而減少節(jié)點(diǎn)處理的排隊(duì)時(shí)間。因此，GLL的請(qǐng)求接受率高于GFP。雖然基于TS的部署方法也是主要考慮節(jié)點(diǎn)的資源使用，但TS通過(guò)反復(fù)迭代計(jì)算搜索更優(yōu)的部署方案，相比于GLL改善了服務(wù)請(qǐng)求接受率。

表3 底層網(wǎng)絡(luò)服務(wù)節(jié)點(diǎn)參數(shù)

表4 VNF 參數(shù)

圖10表示不同請(qǐng)求強(qiáng)度下不同算法的服務(wù)請(qǐng)求平均處理時(shí)間。從圖中可以看出，隨著請(qǐng)求強(qiáng)度的增大，服務(wù)請(qǐng)求的平均處理時(shí)間變大，但不同算法的處理時(shí)間的上升速度和幅度不同。在相同的條件下，基于Viterbi算法的部署方法處理時(shí)間上升速度和幅度最小。由于GFP和GLL主要考慮節(jié)點(diǎn)的資源使用，服務(wù)請(qǐng)求在節(jié)點(diǎn)的等候時(shí)間較長(zhǎng)。但GLL以節(jié)點(diǎn)的緩存容量作為選擇策略，可以減少服務(wù)請(qǐng)求的排隊(duì)時(shí)間。因此，GLL的服務(wù)處理時(shí)間性能優(yōu)于GFP?；赥S的部署方法通過(guò)搜索優(yōu)化的節(jié)點(diǎn)選擇方案，可以降低節(jié)點(diǎn)的服務(wù)處理時(shí)間。因此，TS的處理時(shí)間性能優(yōu)于GFP和GLL。但由于GFP, GLL和TS未充分考慮鏈路狀態(tài)，造成VNF承載節(jié)點(diǎn)間的服務(wù)路徑過(guò)長(zhǎng)，導(dǎo)致較高的鏈路傳輸時(shí)間開(kāi)銷?；赩iterbi的部署方法在滿足資源請(qǐng)求的可部署節(jié)點(diǎn)采用遞歸方法搜索時(shí)延最短路徑，不僅考慮了鏈路傳輸時(shí)間還考慮了節(jié)點(diǎn)處理時(shí)間，降低了服務(wù)處理時(shí)間的總開(kāi)銷。因此，該方法進(jìn)一步優(yōu)化了服務(wù)請(qǐng)求的處理時(shí)間，提高了服務(wù)處理速度。隨著請(qǐng)求到達(dá)強(qiáng)度的增加，該方法的性能優(yōu)勢(shì)更加明顯，在高業(yè)務(wù)強(qiáng)度下適應(yīng)性較強(qiáng)。由于移動(dòng)用戶對(duì)時(shí)延更敏感，該方法可以有效應(yīng)對(duì)5G熱點(diǎn)高容量、低時(shí)延高可靠的業(yè)務(wù)需求。

圖11表示不同請(qǐng)求強(qiáng)度下不同算法的平均利潤(rùn)。從圖中可以看出，隨著請(qǐng)求強(qiáng)度的增大，平均利潤(rùn)變大，但不同算法的平均利潤(rùn)上升的速度和幅度不同。在同等條件下，基于Viterbi部署的方法平均利潤(rùn)上升速度和幅度最大。圖12表示不同請(qǐng)求強(qiáng)度下不同算法的平均利潤(rùn)成本比。從圖中可以看出，隨著請(qǐng)求強(qiáng)度的增大，平均利潤(rùn)成本比變小，但不同算法的平均利潤(rùn)成本比下降的速度和幅度不同。與基于GFP, GLL和TS的方法相比，基于Viterbi的部署方法降低了服務(wù)時(shí)延，提高了服務(wù)請(qǐng)求的接受率，促進(jìn)了資源利用。因此，在相同的條件下，基于Viterbi算法的VNF部署方法的平均利潤(rùn)和平均利潤(rùn)成本比最高，能夠有效提高底層網(wǎng)絡(luò)的基礎(chǔ)設(shè)施收益。

5 結(jié)束語(yǔ)

SDN和NFV增強(qiáng)了運(yùn)營(yíng)商網(wǎng)絡(luò)的彈性，提升了管道的傳輸能力。本文主要研究了虛擬化環(huán)境下服務(wù)鏈VNF的部署問(wèn)題，針對(duì)傳統(tǒng)虛擬網(wǎng)絡(luò)映射算法的不足和5G業(yè)務(wù)更高的時(shí)延要求，提出基于Viterbi算法的VNF部署方法，并驗(yàn)證了方法的有效性。該方法根據(jù)服務(wù)請(qǐng)求選出滿足資源約束的VNF可部署位置，并根據(jù)鏈路時(shí)延和節(jié)點(diǎn)處理時(shí)延選出時(shí)延最短路徑。該模型能夠感知業(yè)務(wù)的變化，隨業(yè)務(wù)負(fù)載調(diào)整服務(wù)鏈間容量分配，解決了網(wǎng)絡(luò)間廣域資源的共享問(wèn)題，實(shí)現(xiàn)了資源的高效管理。與傳統(tǒng)的基于專屬硬件的固定服務(wù)路徑相比，提高了硬件資源的利用率；與傳統(tǒng)的虛擬網(wǎng)絡(luò)映射相比，考慮了不同VNF間的順序約束。實(shí)驗(yàn)表明，該方法降低了服務(wù)請(qǐng)求處理時(shí)間，并提高了服務(wù)請(qǐng)求接受率和成本效率，可實(shí)現(xiàn)網(wǎng)絡(luò)的優(yōu)化部署，增強(qiáng)用戶的服務(wù)體驗(yàn)，提高底層網(wǎng)絡(luò)的長(zhǎng)期受益。虛擬化技術(shù)降低了網(wǎng)絡(luò)的建設(shè)成本，實(shí)現(xiàn)了服務(wù)鏈VNF的靈活編排，提高了網(wǎng)絡(luò)服務(wù)的智能化運(yùn)維能力，增強(qiáng)了網(wǎng)絡(luò)對(duì)業(yè)務(wù)和環(huán)境的自適應(yīng)性。在后續(xù)研究中，將針對(duì)可靠性條件下VNF部署問(wèn)題進(jìn)行研究，以滿足移動(dòng)業(yè)務(wù)的高可靠性要求。

圖9 不同請(qǐng)求強(qiáng)度下的服務(wù)請(qǐng)求接受率???????圖10 不同請(qǐng)求強(qiáng)度下的服務(wù)請(qǐng)求處理時(shí)間

圖11 不同請(qǐng)求強(qiáng)度下的平均利潤(rùn)????????圖12 不同請(qǐng)求強(qiáng)度下的平均利潤(rùn)成本比

[1] Cisco Visual. Networking Index Global mobile data traffic forecast update, 2012-2017[OL]. http://www.cisco.com/en/ US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/ white paper c11-520862, 2013.

[2] Marketing Charts Staff. Mobile network operators face cost crunch[OL]. http://www.marketingcharts.com/wp/direct/ mobile-network operators-face-cost-crunch-17700/, 2011.

[3] HAWILO H, SHAMI A, MIRAHMADI M,. NVF: State of the art, challenges, and implementation in next generation mobile networks (vEPC)[J]., 2014, 28(6): 18-26. doi: 10.1109/MNET.2014.6963800.

[4] LI L E, LIAGHAT V, ZHAO H,. PACE: Policy-aware application cloud embedding[C]. IEEE International Conference on Computer Communication, Turin, 2013: 638-646. doi: 10.1109/INFCOM.2013.6566849.

[5] ZHANG Y, BEHESHTI N, BELIVEAU L,. Steering: A software-defined networking for inline service chaining[C]. IEEE International Conference on Network Protocols (ICNP), Rio de Janeiro, 2013: 1-10. doi: 10.1109/ICNP. 2013.6733615.

[6] GIANNOULAKIS I, KAFETZAKIS E, XYLOURIS G,. On the applications of efficient NFV management towards 5G networking[C]. IEEE International Conference on 5G for Ubiquitous Connectivity, Levi, 2014: 1-5. doi: 10.4108/ icst.5gu.2014.2581 33.

[7] MOENS H and DE TURCK F. VNF-P: a model for efficient placement of virtualized network functions[C]. IEEE International Conference on Network and Service Management, Rio de Janeiro, 2014: 418-423. doi: 10.1109/ CNSM.2014.7014205.

[8] CLAYMAN S, MAINI E, GALIS A,. The dynamic placement of virtual network functions[C]. IEEE International Conference on Network Operations and Management Symposium, Krakow, 2014: 1-9. doi: 10.1109/ NOMS.2014.6838412.

[9] XIA M, SHIRAZIPOUR M, ZHANG Y,. Network function placement for NFV chaining in packet/optical datacenters[J]., 2015, 33(8): 1565-1570. doi: 10.1109/JLT.2015.2388585.

[10] YOUSAF F Z, LOUREIRO P, ZDARSKY F,. Cost analysis of initial deployment strategies for virtualized mobile core network functions[J]., 2015, 53(12): 60-66. doi: 10.1109/MCOM.2015.7355586.

[11] MATIAS J, GARAY J, TOLEDO N,. Toward an SDN-enabled NFV architecture[J]., 2015, 53(4): 187-193. doi: 10.1109/MCOM. 2015. 7081093.

[12] AISSIOUI A, KSENTINI A, GUEROUI A M,. Toward elastic distributed SDN/NFV controller for 5G mobile cloud management systems[J]., 2015, 3: 2055-2064. doi: 10.1109/ACCESS.2015.2489930.

[13] BASTA A, KELLERER W, HOFFMANN M,. A virtual SDN-enabled LTE EPC architecture: A case study for S-/P-gateways functions[C]. IEEE International Conference on SDN for Future Networks and Services, Trento, 2013: 1-7. doi: 10.1109/SDN4FNS. 2013.670 2532.

[14] HAN Bo, GOPALAKRISHNAN V, JI Lusheng,. Network function virtualization: Challenges and opportunities for innovations[J]., 2015, 53(2): 90-97. doi: 10.1109/MCOM.2015. 7045396.

[15] MIJUMBI R, SERRAT J, GORRICHO J L,. Design and evaluation of algorithms for mapping and scheduling of virtual network functions[C]. IEEE Conference on Network Softwarization, London, 2015: 1-9. doi: 10.1109/NETSOFT. 2015.7116120.

Adaptive Deployment Method for Virtualized Network Function Based on Viterbi Algorithm

LIU Caixia LU Ganqiang TANG Hongbo WANG Xiaolei ZHAO Yu

(,450002,)(,100876,)

In order to deal with the explosive growth of mobile data traffic, a novel design of network architecture will be adopted in 5G. Software Defined Network (SDN) and Network Function Virtualization (NFV) are the key technologies for network transformation, which will drive the innovation of mobile communication network architecture. The deployment of Virtualized Network Function (VNF) in service chain is a critical issue in network virtualization. To overcome the ignorance of VNF sequence constraints in service chain and the characteristics of mobile business in existing literatures, an adaptive deployment method of VNF based on Viterbi algorithm is proposed. With real-time perception of the resources change of underlying nodes, the topology structure will be adjusted dynamically. Hidden Markov model is used to describe the topology information of available nodes with resources constraints in underlying network, and the service path with shortest delay is selected based on Viterbi algorithm in candidate service node. Experimental results show that the process time of service chain can be lower compared with existing algorithm. In addition, the acceptance rates of service chain requests and cost efficiency of underlying resources are also raised.

5G; Network Function Virtualization (NFV); Virtualized Network Function (VNF) deployment; Hidden Markov model; Viterbi algorithm; Self-adaption

TN915.81

A

1009-5896(2016)11-2922-09

10.11999/JEIT160045

2016-01-13；改回日期：2016-04-18；

2016-06-16

盧干強(qiáng) luganqiang@163.com

國(guó)家科技重大專項(xiàng)(2013ZX03006002)，國(guó)家863計(jì)劃(2014AA01A701)，國(guó)家自然科學(xué)基金(61521003)，科技部支撐計(jì)劃(2014BAH30B01)

The National Science and Technology Major Project of China (2013ZX03006002), The National 863 Program of China (2014AA01A701), The National Natural Science Foundation of China (61521003), The Ministry of Science and Technology Support Plan (2014BAH30B01)

劉彩霞： 女，1974年生，副教授，研究方向?yàn)橐苿?dòng)通信網(wǎng)絡(luò)、新型網(wǎng)絡(luò)體系結(jié)構(gòu).

盧干強(qiáng)： 男，1990年生，碩士生，研究方向?yàn)橐苿?dòng)通信網(wǎng)絡(luò)、網(wǎng)絡(luò)功能虛擬化.

湯紅波： 男，1968年生，教授，研究方向?yàn)橐苿?dòng)通信網(wǎng)絡(luò)、新型網(wǎng)絡(luò)體系結(jié)構(gòu).

王曉雷： 男，1982年生，博士生，研究方向?yàn)橐苿?dòng)通信網(wǎng)絡(luò)、軟件定義網(wǎng)絡(luò).

趙 宇： 男，1984年生，博士生，研究方向?yàn)橐苿?dòng)通信網(wǎng)絡(luò)、社交網(wǎng)絡(luò).