基于最優(yōu)加權(quán)圖匹配的服務(wù)功能鏈部署方法

李丹，蘭巨龍，王鵬，胡宇翔

?

基于最優(yōu)加權(quán)圖匹配的服務(wù)功能鏈部署方法

李丹，蘭巨龍，王鵬，胡宇翔

（國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450000）

服務(wù)功能鏈技術(shù)通過(guò)對(duì)虛擬網(wǎng)絡(luò)功能的編排來(lái)支持靈活的網(wǎng)絡(luò)服務(wù)請(qǐng)求。針對(duì)資源有限網(wǎng)絡(luò)中的服務(wù)功能鏈部署問(wèn)題，提出了一種基于優(yōu)加權(quán)圖匹配的服務(wù)功能鏈部署方法，把服務(wù)功能鏈組合為功能拓?fù)鋱D，利用鄰接矩陣特征向量分解算法獲取功能拓?fù)渑c物理拓?fù)涞募訖?quán)圖匹配方式，并通過(guò)爬山算法對(duì)匹配結(jié)果進(jìn)一步優(yōu)化。仿真結(jié)果表明，所提方法在降低服務(wù)功能鏈部署所需帶寬的同時(shí)，優(yōu)化了節(jié)點(diǎn)負(fù)載和鏈路帶寬的均衡度，可以支持更多的服務(wù)請(qǐng)求，且復(fù)雜度低，具有較高的時(shí)效性。

服務(wù)功能鏈；加權(quán)圖匹配；特征向量分解；爬山算法

1 引言

互聯(lián)網(wǎng)的高速發(fā)展和廣泛應(yīng)用，對(duì)網(wǎng)絡(luò)中的新功能和新服務(wù)提出了更高的要求。網(wǎng)絡(luò)功能虛擬化技術(shù)（NFV，network function virtualization）[1]通過(guò)分離邏輯功能與物理資源，將多樣化的網(wǎng)絡(luò)功能和服務(wù)從底層物理資源中抽象出來(lái)，改變了傳統(tǒng)網(wǎng)絡(luò)功能的設(shè)計(jì)和部署方式，可以更加靈活、高效地利用網(wǎng)絡(luò)資源。NFV技術(shù)將傳統(tǒng)網(wǎng)絡(luò)中部署在特定硬件設(shè)備上的功能虛擬化為虛擬網(wǎng)絡(luò)功能，可以根據(jù)需要靈活部署在任意一個(gè)通用功能平臺(tái)。在NFV的基礎(chǔ)上，服務(wù)功能鏈技術(shù)（SFC，service function chaining）[2]將不同的網(wǎng)絡(luò)功能按照一定的順序連接起來(lái)，支持某種具體的服務(wù)請(qǐng)求，實(shí)現(xiàn)網(wǎng)絡(luò)服務(wù)的個(gè)性化定制。要將虛擬的服務(wù)功能鏈與實(shí)際的網(wǎng)絡(luò)拓?fù)浣Y(jié)合起來(lái)，需要將這些功能部署在網(wǎng)絡(luò)中的節(jié)點(diǎn)上，并選擇路徑使數(shù)據(jù)依次經(jīng)過(guò)提供這些功能的節(jié)點(diǎn)。軟件定義網(wǎng)絡(luò)（SDN, software defined networking）[3]將控制平面和數(shù)據(jù)平面分離，在控制平面集中計(jì)算最優(yōu)的功能部署位置和數(shù)據(jù)傳輸路徑，使服務(wù)功能鏈的動(dòng)態(tài)配置和部署成為可能。

為了在網(wǎng)絡(luò)中提供多樣化的服務(wù)，需要部署大量功能順序不同的服務(wù)功能鏈，但是由于網(wǎng)絡(luò)中的節(jié)點(diǎn)處理能力和鏈路帶寬有限，如何在資源有限的條件下盡可能多地部署服務(wù)功能鏈?zhǔn)潜疚难芯康闹饕獑?wèn)題。目前，針對(duì)服務(wù)功能鏈的部署問(wèn)題已經(jīng)有了一些相關(guān)研究，文獻(xiàn)[4]建立了基于SDN架構(gòu)的服務(wù)功能鏈部署模型，通過(guò)統(tǒng)一控制機(jī)制來(lái)確保功能部署和數(shù)據(jù)傳輸?shù)臏?zhǔn)確性，并舉例說(shuō)明了該架構(gòu)可以支持的優(yōu)化目標(biāo)，但是沒(méi)有給出具體的部署算法。文獻(xiàn)[5-6]以優(yōu)化數(shù)據(jù)傳輸和處理時(shí)延為目標(biāo)，給出了服務(wù)功能鏈部署的問(wèn)題模型以及優(yōu)化求解算法。文獻(xiàn)[7-8]從時(shí)延、分組丟失率、中繼節(jié)點(diǎn)數(shù)等方面建立了多參數(shù)混合優(yōu)化模型，來(lái)提高服務(wù)功能鏈的綜合服務(wù)性能。文獻(xiàn)[9-10]通過(guò)遺傳算法來(lái)適應(yīng)服務(wù)功能鏈對(duì)服務(wù)質(zhì)量的動(dòng)態(tài)需求，在網(wǎng)絡(luò)環(huán)境變化時(shí)仍能提供較好的服務(wù)質(zhì)量。

以上算法主要針對(duì)服務(wù)性能進(jìn)行優(yōu)化，而沒(méi)有考慮網(wǎng)絡(luò)資源的限制。文獻(xiàn)[11]以整個(gè)網(wǎng)絡(luò)的帶寬資源需求為優(yōu)化目標(biāo)，研究了虛擬網(wǎng)絡(luò)功能的優(yōu)化部署問(wèn)題。文獻(xiàn)[12]針對(duì)同時(shí)優(yōu)化帶寬需求和數(shù)據(jù)傳輸處理時(shí)延的問(wèn)題，設(shè)計(jì)了一種啟發(fā)式搜索算法。文獻(xiàn)[13-14]研究了在數(shù)據(jù)中心網(wǎng)絡(luò)中部署服務(wù)功能鏈的網(wǎng)絡(luò)流量均衡算法。文獻(xiàn)[15]研究了一種功能合并部署算法，該算法統(tǒng)計(jì)各個(gè)功能之間的帶寬需求，將帶寬需求較大的功能合并部署在同一節(jié)點(diǎn)上來(lái)降低路徑帶寬。但是這些文獻(xiàn)側(cè)重于對(duì)帶寬資源的優(yōu)化利用，而缺少對(duì)節(jié)點(diǎn)處理能力和鏈路帶寬的綜合考慮。針對(duì)節(jié)點(diǎn)處理能力和帶寬資源有限的情況，文獻(xiàn)[16-17]通過(guò)啟發(fā)式算法來(lái)實(shí)現(xiàn)降低鏈路帶寬需求和減少功能部署開銷之間的平衡。文獻(xiàn)[18]將網(wǎng)絡(luò)中所有節(jié)點(diǎn)的剩余處理能力、存儲(chǔ)空間和帶寬加權(quán)組合為節(jié)點(diǎn)剩余資源，把服務(wù)功能鏈部署在滿足約束條件且剩余資源總和最大的路徑上，但是該算法需要遍歷所有部署方式，計(jì)算復(fù)雜度較高。文獻(xiàn)[19]將服務(wù)功能鏈分解為多層有向圖的組合，通過(guò)維特比算法求解每一層的節(jié)點(diǎn)選擇，但該算法在選擇節(jié)點(diǎn)的過(guò)程中會(huì)優(yōu)先將功能部署在相同節(jié)點(diǎn)中，容易導(dǎo)致部分節(jié)點(diǎn)負(fù)載過(guò)重而無(wú)法支持新的服務(wù)請(qǐng)求。文獻(xiàn)[20]將服務(wù)功能鏈的部署問(wèn)題轉(zhuǎn)化為功能拓?fù)浜臀锢硗負(fù)涞募訖?quán)圖匹配問(wèn)題，將節(jié)點(diǎn)處理能力和鏈路帶寬作為參數(shù)來(lái)選擇符合要求的節(jié)點(diǎn)匹配方式，該算法可以快速生成符合傳輸需求的部署方式，但是會(huì)將帶寬需求較大的虛擬鏈路映射為跳數(shù)較多的物理傳輸路徑，造成大量帶寬損耗，且?guī)捄拓?fù)載均衡效果較差。文獻(xiàn)[21]提出了一種最優(yōu)加權(quán)圖匹配算法，該算法利用特征向量分解算法實(shí)現(xiàn)2幅同構(gòu)加權(quán)圖的快速匹配，可以較大概率實(shí)現(xiàn)最優(yōu)匹配，即使得到的不是最優(yōu)解，所得結(jié)果仍然可以通過(guò)爬山算法修正為最優(yōu)解，但是該方法對(duì)待匹配的加權(quán)圖有一定的要求，無(wú)法直接解決服務(wù)功能鏈部署問(wèn)題。

基于以上分析，本文提出了一種基于最優(yōu)加權(quán)圖匹配的服務(wù)功能鏈部署方法，把相鄰的服務(wù)功能鏈組合為功能拓?fù)鋱D，將功能鏈的部署問(wèn)題轉(zhuǎn)化為功能拓?fù)渑c物理拓?fù)涞募訖?quán)圖匹配問(wèn)題，通過(guò)對(duì)加權(quán)圖鄰接矩陣的擴(kuò)充和元素替換來(lái)滿足文獻(xiàn)[21]的同構(gòu)條件，采用鄰接矩陣特征向量分解算法和爬山優(yōu)化算法得到功能和鏈路的最優(yōu)匹配。與其他算法相比，本文方法的創(chuàng)新點(diǎn)體現(xiàn)在以下3個(gè)方面：1)可以實(shí)現(xiàn)多條服務(wù)功能鏈的同時(shí)部署，降低計(jì)算復(fù)雜度，具有較高的時(shí)效性；2)通過(guò)合理的元素替換，均衡鏈路匹配過(guò)程中路徑帶寬和傳輸跳數(shù)的關(guān)系，避免帶寬浪費(fèi)，節(jié)省網(wǎng)絡(luò)資源；3) 計(jì)算節(jié)點(diǎn)和鏈路資源的最優(yōu)匹配，能夠同時(shí)均衡全網(wǎng)的節(jié)點(diǎn)負(fù)載和鏈路帶寬資源，可以支持更多的服務(wù)請(qǐng)求。

2 服務(wù)功能鏈部署與加權(quán)圖匹配問(wèn)題

2.1 服務(wù)功能鏈部署問(wèn)題

本文將服務(wù)功能鏈的部署問(wèn)題建模為一個(gè)多約束優(yōu)化問(wèn)題，如式(1)~式(3)所示。

2.2 加權(quán)圖匹配問(wèn)題

根據(jù)定義1，最優(yōu)加權(quán)圖匹配問(wèn)題可表示為式(4)。

其中，()表示匈牙利算法。

利用特征向量分解算法進(jìn)行加權(quán)圖匹配需要一定的前提條件，為了利用文獻(xiàn)[21]的算法對(duì)服務(wù)功能鏈和物理拓?fù)溥M(jìn)行匹配，需要在算法中解決以下3個(gè)問(wèn)題。

1) 在加權(quán)圖匹配問(wèn)題中，2幅圖的頂點(diǎn)和邊的數(shù)目相同，但是通常情況下服務(wù)功能鏈中的功能數(shù)少于物理拓?fù)渲械墓?jié)點(diǎn)數(shù)。

2) 在加權(quán)圖匹配問(wèn)題中，2幅圖的鏈路是一一對(duì)應(yīng)進(jìn)行匹配的，而在服務(wù)功能鏈的部署過(guò)程中，2個(gè)相鄰功能間的虛擬鏈路既可以映射為一條物理鏈路，也可以映射為多條物理鏈路。

3) 特征向量分解算法要求待匹配的2個(gè)圖近似同構(gòu)，但是服務(wù)功能鏈與物理拓?fù)漤旤c(diǎn)數(shù)不同，鏈路權(quán)值不相關(guān)，不滿足同構(gòu)條件。

3 方法設(shè)計(jì)

3.1 服務(wù)功能鏈組合

本文方法利用最優(yōu)加權(quán)圖匹配算法計(jì)算功能和鏈路的映射關(guān)系，支持多條服務(wù)功能鏈的同時(shí)部署，首先需要將服務(wù)功能鏈組合為功能拓?fù)鋱D。以圖1所示的2條服務(wù)功能鏈為例，將2條功能鏈中的相同功能合并，圖中的功能權(quán)值表示該功能需要的節(jié)點(diǎn)處理能力，鏈路權(quán)值表示其連接的功能間傳輸路徑所需帶寬，需要注意的是，2條功能鏈重疊部分的權(quán)值應(yīng)為二者之和。

圖1 服務(wù)功能鏈組合為功能拓?fù)?/p>

3.2 鄰接矩陣擴(kuò)充

圖2 待匹配的功能拓?fù)渑c物理拓?fù)?/p>

3.3 矩陣元素替換

在服務(wù)功能鏈的部署過(guò)程中，相鄰功能既可以匹配到相鄰節(jié)點(diǎn)，也可以匹配到非相鄰節(jié)點(diǎn)。為了在鏈路映射的過(guò)程中滿足以上要求，需要對(duì)物理拓?fù)溧徑泳仃囍斜硎炬溌穾挼木仃囋剡M(jìn)行替換，為每一對(duì)節(jié)點(diǎn)選擇一條最優(yōu)路徑并更新匹配權(quán)值。在文獻(xiàn)[20]中，按照最小帶寬最大原則為非相鄰節(jié)點(diǎn)計(jì)算路徑并以該帶寬作為新的鏈路匹配權(quán)值，雖然該方法支持相鄰功能與非相鄰節(jié)點(diǎn)的匹配，但是存在以下2個(gè)問(wèn)題：1) 沒(méi)有更新相鄰節(jié)點(diǎn)間的路徑帶寬，導(dǎo)致相鄰節(jié)點(diǎn)間直連帶寬較小時(shí)無(wú)法進(jìn)行鏈路匹配；2) 最小帶寬最大路徑很可能需要經(jīng)過(guò)多次轉(zhuǎn)發(fā)，路徑較長(zhǎng)，匹配帶寬需求較高的虛擬鏈路后會(huì)造成大量的帶寬損耗。為此，算法1為任意一對(duì)節(jié)點(diǎn)計(jì)算一條路徑，使該路徑的最小帶寬與傳輸跳數(shù)的比值最大，并把該比值更新為鏈路匹配權(quán)值，從而均衡路徑帶寬和傳輸跳數(shù)的關(guān)系，避免帶寬浪費(fèi)。

算法1 物理拓?fù)滏溌窓?quán)值更新算法

1) for any nodesandindo //：源節(jié)點(diǎn)，：目的節(jié)點(diǎn)

2)(1)=,=, hop()=0, label()=0 if1, label()=10 000 //：已確定節(jié)點(diǎn)集合，：轉(zhuǎn)接點(diǎn)，hop：各節(jié)點(diǎn)到源節(jié)點(diǎn)跳數(shù)，label：各節(jié)點(diǎn)權(quán)值

3） whileis not indo

4) for=1 toandis not indo

6) if label()

7) label()=, hop()=hop()+1,()=

8) end if

9) end for

10)=node with maximum label

11) putinto

12) end

13) path(1)=,=//path：節(jié)點(diǎn)和之間的傳輸路徑，：前序節(jié)點(diǎn)

14) whileis not in path do

15)=()

16) putinto path

17) end

18) end for

特征向量分解算法要求待匹配的2個(gè)加權(quán)圖近似同構(gòu)，因此需要進(jìn)一步對(duì)功能拓?fù)涞泥徑泳仃囋剡M(jìn)行替換，使其與更新后的物理拓?fù)鋱D同構(gòu)。替換方法如下。首先，將各功能和各節(jié)點(diǎn)分別按照處理能力由大到小的順序排列，把功能拓?fù)溧徑泳仃囍斜硎咎幚砟芰π枨蟮脑匾佬蛱鎿Q為各節(jié)點(diǎn)的剩余處理能力，“0”元素則隨機(jī)替換為較小的節(jié)點(diǎn)處理能力，實(shí)現(xiàn)2個(gè)加權(quán)圖的頂點(diǎn)同構(gòu)。然后，用同樣的辦法將功能拓?fù)溧徑泳仃囍斜硎編捫枨蟮脑剡M(jìn)行替換，實(shí)現(xiàn)2個(gè)加權(quán)圖的邊同構(gòu)，滿足文獻(xiàn)[21]的算法要求。這種替換方法的目的是，在構(gòu)建同構(gòu)加權(quán)圖的過(guò)程中，盡可能將處理能力需求較高的功能和帶寬需求較高的鏈路匹配到剩余資源較多的節(jié)點(diǎn)和路徑上。圖2中功能拓?fù)涞泥徑泳仃囋靥鎿Q過(guò)程如式(9)所示，加號(hào)兩邊分別是非“0”元素和“0”元素的替換矩陣。

3.4 特征值分解與匈牙利算法

利用匈牙利算法對(duì)該效率矩陣進(jìn)行求解，得到最優(yōu)映射函數(shù)如式(11)所示。

3.5 爬山優(yōu)化算法

算法2 映射函數(shù)修正爬山算法

1) flag=1 //flag：判斷修正過(guò)程是否結(jié)束標(biāo)志

2) while flag=1 do

3) flag=0,=||1T?2|| //：映射函數(shù)作用后2個(gè)圖差值

4) for=1 todo

5) for=1 todo

6)=

7) exchange columnand columnof//：交換一對(duì)頂點(diǎn)后的映射函數(shù)

8)=||1T?2|| //：新的映射函數(shù)作用后2個(gè)圖差值

9) if there is no negative number in1T?2and

10)=,=, flag=1

11) end if

12) end for

13) end for

14) end

3.6 方法流程說(shuō)明與復(fù)雜度分析

圖3 本文方法流程示意

4 性能仿真與分析

為了對(duì)本文提出的服務(wù)功能鏈部署方法性能進(jìn)行驗(yàn)證，在2.80 GHz CPU，4 GB內(nèi)存的PC機(jī)上通過(guò)Matlab軟件進(jìn)行了仿真實(shí)驗(yàn)并對(duì)實(shí)驗(yàn)結(jié)果處理分析。仿真場(chǎng)景設(shè)計(jì)為，由20個(gè)節(jié)點(diǎn)構(gòu)成隨機(jī)網(wǎng)絡(luò)拓?fù)浒凑誛axman-Salam模型[23]生成，每個(gè)節(jié)點(diǎn)能夠提供的處理能力為50 MHz，每條鏈路的總帶寬為50 Mbit/s。網(wǎng)絡(luò)可以提供8種功能，每個(gè)需要部署的服務(wù)功能鏈由任意順序排列的2~8個(gè)互不相同的功能組成，每個(gè)功能需要的處理能力在0~2 MHz之間，每條服務(wù)功能鏈所需帶寬在0~5 Mbit/s之間，每個(gè)功能拓?fù)鋱D由2條服務(wù)功能鏈合并生成。為了提高算法評(píng)估的精確性，采用蒙特卡洛方法，在每個(gè)測(cè)試場(chǎng)景下進(jìn)行了100組仿真測(cè)試，取平均值作為測(cè)試結(jié)果。

本文將平均服務(wù)請(qǐng)求處理時(shí)間、節(jié)點(diǎn)負(fù)載均衡度、鏈路帶寬均衡度、平均鏈路剩余帶寬和網(wǎng)絡(luò)能夠支持的最大服務(wù)請(qǐng)求數(shù)作為方法性能的評(píng)價(jià)指標(biāo)，其中節(jié)點(diǎn)負(fù)載均衡度是指節(jié)點(diǎn)剩余處理能力的均方差，鏈路帶寬均衡度是指鏈路剩余帶寬的均方差，并將本文方法與文獻(xiàn)[20]中同樣采用圖匹配策略的特征值分解算法和文獻(xiàn)[19]中的多層圖算法進(jìn)行比較。特征值分解算法將非相鄰節(jié)點(diǎn)間的最大路徑帶寬更新為鏈路權(quán)值，根據(jù)鄰接矩陣的特征向量計(jì)算效率矩陣，最后采用啟發(fā)式算法依次為每個(gè)功能選擇符合限制條件的匹配方式。多層圖算法將服務(wù)功能鏈分解為多層有向圖，通過(guò)維特比算法計(jì)算每一層的節(jié)點(diǎn)選擇代價(jià)，最后回溯搜索最優(yōu)的節(jié)點(diǎn)和鏈路匹配方式。

圖4顯示了各算法對(duì)服務(wù)請(qǐng)求的平均處理時(shí)間和服務(wù)功能鏈長(zhǎng)度的關(guān)系。從圖中可以看出，多層圖算法的平均處理時(shí)間和服務(wù)功能鏈的長(zhǎng)度近似成正比關(guān)系，這是因?yàn)樵撍惴ǖ姆謱訑?shù)由服務(wù)功能鏈中的功能個(gè)數(shù)決定，分層數(shù)越多需要的計(jì)算時(shí)間越長(zhǎng)。由于本文方法和特征值分解算法的計(jì)算復(fù)雜度僅與物理拓?fù)涞墓?jié)點(diǎn)數(shù)相關(guān)，因此平均處理時(shí)間不會(huì)隨著服務(wù)功能鏈長(zhǎng)度的增加而變化，特征值分解算法的處理時(shí)間略小于本文方法，是因?yàn)楸疚姆椒ㄔ黾恿擞成浜瘮?shù)的修正過(guò)程。

圖4 平均服務(wù)請(qǐng)求處理時(shí)間

圖5和圖6分別給出了服務(wù)功能鏈長(zhǎng)度為5時(shí)，各算法對(duì)節(jié)點(diǎn)負(fù)載和鏈路帶寬的均衡性能。由于多層圖算法優(yōu)先將功能部署在相同節(jié)點(diǎn)上，沒(méi)有考慮對(duì)節(jié)點(diǎn)負(fù)載和鏈路帶寬的均衡，因此節(jié)點(diǎn)剩余處理能力和鏈路剩余帶寬的均方差最高。特征值分解算法根據(jù)節(jié)點(diǎn)和鏈路的剩余網(wǎng)絡(luò)資源對(duì)服務(wù)功能鏈進(jìn)行匹配，但是該算法得到的不是最優(yōu)匹配，因此帶寬和負(fù)載的均衡性能介于多層圖算法和本文方法之間。由于本文方法在匹配過(guò)程中對(duì)鄰接矩陣進(jìn)行了同構(gòu)化處理，可以較大概率實(shí)現(xiàn)最優(yōu)匹配，負(fù)載均衡度和帶寬均衡度都明顯優(yōu)于其他算法，且本文算法通過(guò)爬山算法修正映射函數(shù)，進(jìn)一步優(yōu)化了對(duì)負(fù)載和帶寬的均衡效果。

圖5 節(jié)點(diǎn)負(fù)載均衡性能

圖7給出了服務(wù)功能鏈長(zhǎng)度為5時(shí)，平均鏈路剩余帶寬隨著服務(wù)請(qǐng)求增加的變化情況。雖然多層圖算法的剩余帶寬明顯高于其他2種算法，但是由于該算法將功能集中部署在相同節(jié)點(diǎn)，使得部分節(jié)點(diǎn)因剩余處理能力不足而無(wú)法支持新功能的部署，當(dāng)服務(wù)請(qǐng)求數(shù)大于40后，新的服務(wù)請(qǐng)求難以找到符合限制條件的部署方式。與特征值分解算法相比，本文方法采用帶寬與跳數(shù)的比值來(lái)更新物理拓?fù)溧徑泳仃囋?，避免為跳?shù)較多的路徑匹配帶寬需求較高的虛擬鏈路，因此部署服務(wù)功能鏈需要的帶寬更小。圖8給出了3種算法能夠支持的最大服務(wù)請(qǐng)求數(shù)與服務(wù)功能鏈長(zhǎng)度的關(guān)系?？梢钥闯?，本文方法由于降低了帶寬損耗，且負(fù)載均衡度和帶寬均衡度高，因此能夠提供的服務(wù)請(qǐng)求數(shù)明顯多于特征值分解和多層圖算法，且服務(wù)功能鏈越長(zhǎng)，本文方法的優(yōu)勢(shì)越明顯，這是因?yàn)檩^長(zhǎng)的服務(wù)功能鏈對(duì)負(fù)載和帶寬的均衡性能要求更高。

圖6 鏈路帶寬均衡性能

圖7 平均鏈路剩余帶寬

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

針對(duì)資源有限的網(wǎng)絡(luò)中的服務(wù)功能鏈部署問(wèn)題，本文提出了一種基于最優(yōu)加權(quán)圖匹配的服務(wù)功能鏈部署方法，把多條服務(wù)功能鏈組合為功能拓?fù)鋱D，通過(guò)鄰接矩陣的擴(kuò)充和元素替換實(shí)現(xiàn)功能拓?fù)鋱D與物理拓?fù)鋱D的同構(gòu)，采用鄰接矩陣特征向量分解算法快速獲取最優(yōu)加權(quán)圖匹配方式，并通過(guò)爬山算法對(duì)匹配結(jié)果進(jìn)一步優(yōu)化。該方法可以支持多條服務(wù)功能鏈的同時(shí)部署，計(jì)算復(fù)雜度低，具有較高的時(shí)效性。與其他算法相比，該方法降低了服務(wù)功能鏈部署所需的鏈路帶寬，對(duì)節(jié)點(diǎn)負(fù)載和鏈路帶寬資源的均衡性能更好，可以在相同的網(wǎng)絡(luò)資源條件下支持更多的服務(wù)請(qǐng)求。下一步研究考慮搭建服務(wù)功能鏈部署原型系統(tǒng)，將本方法在真實(shí)環(huán)境中進(jìn)行驗(yàn)證。

圖8 最大服務(wù)請(qǐng)求數(shù)

[1] MIJUMBI R, SERRAT J, GORRICHO J L, et al. Network function virtualization: state-of-the-art and research challenges[J]. IEEE Communications Surveys & Tutorials, 2017, 18(1):236-262.

[2] QUINN P, GUICHARD J. Service function chaining: creating a service plane via network service headers[J]. Computer, 2014, 47(11):38-44.

[3] NUNES B A A, MENDONCA M, NGUYEN X N, et al. A survey of software-defined networking: past, present, and future of programmable networks[J]. IEEE Communications Surveys & Tutorials, 2014, 16(3):1617-1634.

[4] LI Y, ZHENG F, CHEN M, et al. A unified control and optimization framework for dynamical service chaining in software-defined NFV system[J]. Wireless Communications IEEE, 2015, 22(6):15-23.

[5] LEE G, KIM M, CHOO S, et al. Optimal flow distribution in service function chaining[C]// The, International Conference on Future Internet. ACM, 2015:17-20.

[6] MARTINI B, PAGANELLI F, CAPPANERA P, et al. Latency-aware composition of virtual functions in 5G[C]// Network Softwarization. IEEE, 2015:1-6.

[7] MEHRAGHDAM S, KELLER M, KARL H. Specifying and placing chains of virtual network functions[C]// IEEE International Conference on Cloud NETWORKING. IEEE, 2014:7-13.

[8] LEIVADEAS A, FALKNER M, LAMBADARIS I, et al. Resource management and orchestration for a dynamic service chain steering model[C]// Global Communications Conference. IEEE, 2017:1-6.

[9] RANKOTHGE W, MA J, LE F, et al. Towards making network function virtualization a cloud computing service[C]// IFIP/IEEE International Symposium on Integrated Network Management. IEEE, 2015:89-97.

[10] OTOKURA M, LEIBNITZ K, KOIZUMI Y, et al. Application of evolutionary mechanism to dynamic Virtual Network Function Placement[C]// IEEE International Conference on Network Protocols. IEEE, 2016:1-6.

[11] SAHHAF S, TAVERNIER W, ROST M, et al. Network service chaining with optimized network function embedding supporting service decompositions[J]. Computer Networks the International Journal of Computer & Telecommunications Networking, 2015, 93(P3):492-505.

[12] CHUA F C, WARD J, ZHANG Y, et al. Stringer: balancing latency and resource usage in service function chain provisioning[J]. IEEE Internet Computing, 2016, 20(6):22-31.

[13] KLINKOWSKI M, WALKOWIAK K. On advantages of elastic optical networks for provisioning of cloud computing Traffic[J]. IEEE Network, 2013, 27(27):44-51.

[14] ZHANG L, ZHU Z. Spectrum-efficient anycast in elastic optical inter-datacenter networks [J]. Optical Switching & Networking, 2014, 14(4):250-259.

[15] YANG K, ZHANG H, HONG P. Energy-aware service function placement for service function chaining in data centers[C]// Global Communications Conference. IEEE, 2017:1-6.

[16] FANG W, ZENG M, LIU X, et al. Joint Spectrum and it resource allocation for efficient VNF service chaining in inter-datacenter elastic optical networks[J]. IEEE Communications Letters, 2016, 20(8):1539-1542.

[17] KUO T W, LIOU B H, LIN C J, et al. Deploying chains of virtual network functions: On the relation between link and server usage[C]// IEEE International Conference on Computer Communications. IEEE, 2016:1-9.

[18] XIE L, JIANG Y, WANG B, et al. An approach for network function combination based on least busy placement algorithm[J]. China Communications, 2016, 13(S1):167-176.

[19] BARI F, CHOWDHURY S R, AHMED R, et al. Orchestrating virtualized network functions[J]. IEEE Transactions on Network & Service Management, 2016, PP(99):1-1.

[20] MECHTRI M, GHRIBI C, ZEGHLACHE D. A scalable algorithm for the placement of service function chains[J]. IEEE Transactions on Network & Service Management , 2016 , 13 (3) :533-546

[21] UMEYAMA S. An eigendecomposition approach to weighted graph matching problems[J]. Pattern Analysis & Machine Intelligence IEEE Transactions on, 1988, 10(5):695-703.

[22] PAPADIMITRIOU C H, STEIGLITZ K. Combinatorial optimization: algorithms and complexity[J]. IEEE Transactions on Acoustics Speech & Signal Processing, 1982, 32(6):1258-1259.

[23] SALAMA H F. Multicast routing for real-time communication of high-speed networks[D]. Raleigh: North Carolina State University, 1996.

Service function chain deployment algorithm based on optimal weighted graph matching

LI Dan, LAN Julong, WANG Peng, HU Yuxiang

National Digital Switching System Engineering & Technology Research Center, Zhengzhou 450000, China

Service function chain can support flexible network service requirement by linking virtual network functions. Aiming at the problem of service function chain deployment in a resource-constrained network, an algorithm for service function chain deployment based on optimal weighted graph matching was proposed. The service function chains was composed into graphs of functional topography, and the optimal matching results between graphs of functional topology and physical topology was obtained using eigendecomposition approach, and furtherly the matching results by hill-climbing method was optimized. Simulation results show that, the proposed algorithm can reduce the required bandwidth to deploy service function chains, balance the load of nodes and bandwidth of links, and support more service requests. What is more, the algorithm has a lower computation complexity and higher time efficience.

service function chain, weighted graph matching, eigendecomposition approach, hill-climbing method

TP393

A

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

2018?05?31；

2019?02?21

國(guó)家高技術(shù)研究發(fā)展計(jì)劃（“863計(jì)劃”）基金資助項(xiàng)目（No.2015AA016102）；國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61521003，No.61702547）

The National High Technology Research and Development Program of China (863 Program) (No.2015AA016102), The National Natural Science Foundation of China (No.61521003, No.61702547)

李丹（1989?），男，遼寧沈陽(yáng)人，博士，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心助理研究員，主要研究方向?yàn)樾滦途W(wǎng)絡(luò)體系結(jié)構(gòu)、路由交換技術(shù)。

蘭巨龍（1962?），男，河南鄭州人，博士，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心教授、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)體系結(jié)構(gòu)、信息安全。

王鵬（1985?），男，河南周口人，博士，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心助理研究員，主要研究方向?yàn)樾滦途W(wǎng)絡(luò)體系結(jié)構(gòu)、路由技術(shù)。

胡宇翔（1982?），男，河南周口人，博士，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心副研究員、碩士生導(dǎo)師，主要研究方向?yàn)樾滦途W(wǎng)絡(luò)體系結(jié)構(gòu)、網(wǎng)絡(luò)安全。