端到端時(shí)延上限確定的服務(wù)鏈部署算法

王澤南，張嬌，汪碩，黃韜，F(xiàn).Richard Yu

（1.網(wǎng)絡(luò)通信與安全紫金山實(shí)驗(yàn)室，江蘇 南京 211111；2.北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100876；3.加拿大卡爾頓大學(xué)，渥太華 K1S 5B6）

1 引言

隨著5G 網(wǎng)絡(luò)的發(fā)展，遠(yuǎn)程醫(yī)療、自動(dòng)駕駛、AR/VR、工業(yè)自動(dòng)化等業(yè)務(wù)正在成為可能，并處于穩(wěn)步推進(jìn)的過(guò)程中。這些新業(yè)務(wù)對(duì)網(wǎng)絡(luò)端到端時(shí)延提出了更嚴(yán)苛的要求。例如，自動(dòng)駕駛需要網(wǎng)絡(luò)提供低于10 ms 的端到端時(shí)延，保證汽車能夠及時(shí)地執(zhí)行命令[1]。游戲玩家在體驗(yàn)AR/VR 游戲時(shí)，需要網(wǎng)絡(luò)提供低于20 ms 的端到端時(shí)延，以消除游戲圖像和動(dòng)作不匹配造成的眩暈[2]。因此，提供端到端嚴(yán)格的時(shí)延保障對(duì)這些業(yè)務(wù)至關(guān)重要。

當(dāng)今的網(wǎng)絡(luò)依賴于眾多的網(wǎng)絡(luò)功能設(shè)備，文獻(xiàn)[3]指出網(wǎng)絡(luò)中近半的設(shè)備均為網(wǎng)絡(luò)功能設(shè)備。隨著網(wǎng)絡(luò)功能虛擬化（NFV,network function virtualization）技術(shù)[4]的普及，可以預(yù)見(jiàn)越來(lái)越多的網(wǎng)絡(luò)功能設(shè)備將以虛擬網(wǎng)絡(luò)功能（VNF,virtual network function）的形式進(jìn)行部署。軟件定義網(wǎng)絡(luò)（SDN,software define network）[5]作為與NFV 互補(bǔ)的技術(shù)，可以實(shí)現(xiàn)流量在VNF 之間按順序進(jìn)行傳遞，從而實(shí)現(xiàn)VNF 按序串成鏈來(lái)提供網(wǎng)絡(luò)服務(wù)，這也稱為服務(wù)鏈。在面對(duì)時(shí)延敏感業(yè)務(wù)的服務(wù)鏈請(qǐng)求時(shí)，如何保障服務(wù)鏈端到端的時(shí)延吸引了學(xué)術(shù)界和工業(yè)界的關(guān)注。

現(xiàn)有許多文獻(xiàn)[6-9]研究了如何通過(guò)優(yōu)化服務(wù)鏈的部署來(lái)為服務(wù)鏈提供端到端的時(shí)延保障。但是這些工作都無(wú)法為服務(wù)鏈提供嚴(yán)格的時(shí)延保障。例如，文獻(xiàn)[6-7]在建模的過(guò)程中，認(rèn)為數(shù)據(jù)包通過(guò)VNF 節(jié)點(diǎn)的時(shí)延是固定的，這將對(duì)服務(wù)鏈的端到端時(shí)延建模帶來(lái)較大的誤差。由于VNF 節(jié)點(diǎn)分配的資源大小是可以變化的，而VNF 節(jié)點(diǎn)的數(shù)據(jù)包處理速率將隨著分配資源的大小而改變，從而影響數(shù)據(jù)包通過(guò)VNF 節(jié)點(diǎn)的時(shí)延。文獻(xiàn)[8-9]通過(guò)使用排隊(duì)論來(lái)避免這一問(wèn)題，然而，基于排隊(duì)論計(jì)算得到的時(shí)延為數(shù)據(jù)包平均時(shí)延，不能保證每一個(gè)數(shù)據(jù)包均能在該時(shí)延內(nèi)完成傳輸。顯然，這對(duì)一些時(shí)延敏感的業(yè)務(wù)是不可容忍的。

為了解決上述問(wèn)題，一些工作提出了基于網(wǎng)絡(luò)演算計(jì)算服務(wù)鏈的端到端時(shí)延。由于基于網(wǎng)絡(luò)演算得到的時(shí)延為時(shí)延上限，因此能保證全部的數(shù)據(jù)包在該時(shí)延內(nèi)完成傳輸。例如，文獻(xiàn)[10]率先將網(wǎng)絡(luò)演算應(yīng)用于計(jì)算服務(wù)鏈中單條業(yè)務(wù)流的端到端時(shí)延中。由于不同的服務(wù)鏈會(huì)共享網(wǎng)絡(luò)基礎(chǔ)設(shè)施，不同的業(yè)務(wù)流量之間會(huì)存在資源競(jìng)爭(zhēng)。因此，文獻(xiàn)[10]中的模型不能擴(kuò)展到多條服務(wù)鏈的場(chǎng)景。文獻(xiàn)[11]考慮了服務(wù)鏈之間的資源競(jìng)爭(zhēng)并基于隨機(jī)網(wǎng)絡(luò)演算推導(dǎo)了服務(wù)鏈的端到端時(shí)延，并將推導(dǎo)得到的結(jié)果在實(shí)驗(yàn)仿真中進(jìn)行了驗(yàn)證。然而，上述工作僅僅是基于網(wǎng)絡(luò)演算推導(dǎo)了服務(wù)鏈的端到端時(shí)延，并未進(jìn)一步將網(wǎng)絡(luò)演算與服務(wù)鏈的部署相結(jié)合。

本文將網(wǎng)絡(luò)演算應(yīng)用到服務(wù)鏈的部署問(wèn)題中，旨在保障部署后的服務(wù)鏈具有嚴(yán)格的端到端時(shí)延上界。嚴(yán)格的時(shí)延保障指經(jīng)過(guò)服務(wù)鏈的每一個(gè)數(shù)據(jù)包的時(shí)延都符合業(yè)務(wù)的需求。這種為業(yè)務(wù)流量提供嚴(yán)格時(shí)延保障的服務(wù)鏈稱為確定性服務(wù)鏈（DSC,deterministic service chain）。在DSC 的部署問(wèn)題中，DSC 的目標(biāo)是為接收的服務(wù)鏈請(qǐng)求提供嚴(yán)格的端到端時(shí)延保障的同時(shí)，提高接收的服務(wù)鏈的數(shù)量。首先對(duì)DSC 的部署問(wèn)題進(jìn)行建模，由于網(wǎng)絡(luò)演算在推導(dǎo)服務(wù)鏈時(shí)延的過(guò)程中引入了非線性約束，因此問(wèn)題最終被建模為混合整數(shù)非線性規(guī)劃。為了簡(jiǎn)化問(wèn)題的求解，DSC 問(wèn)題被分解為2 個(gè)子問(wèn)題，分別是服務(wù)鏈路由子問(wèn)題與VNF 節(jié)點(diǎn)資源分配子問(wèn)題，通過(guò)引入最大允許的VNF 總時(shí)延，實(shí)現(xiàn)對(duì)2 個(gè)子問(wèn)題的協(xié)同優(yōu)化。最后，通過(guò)實(shí)驗(yàn)驗(yàn)證了所提模型和算法的有效性，結(jié)果顯示所提算法能在提高接收的服務(wù)鏈數(shù)量的同時(shí)，嚴(yán)格保障接收的每一條服務(wù)鏈的端到端時(shí)延。

2 網(wǎng)絡(luò)演算基本概念

時(shí)延是網(wǎng)絡(luò)性能的一個(gè)重要指標(biāo)，目前存在多種不同的工具和方法對(duì)網(wǎng)絡(luò)端到端性能進(jìn)行建模和分析。其中最常見(jiàn)的工具是排隊(duì)理論，它將數(shù)據(jù)包的到達(dá)建模為泊松過(guò)程，并計(jì)算平均的時(shí)延和隊(duì)列長(zhǎng)度。然而，文獻(xiàn)[12]指出，網(wǎng)絡(luò)中的流量具有自相似性和突發(fā)性，因此泊松過(guò)程不能準(zhǔn)確地描述流量的到達(dá)特征。此外，排隊(duì)論得到的時(shí)延為平均時(shí)延，不能保證每個(gè)數(shù)據(jù)包都能在該時(shí)延內(nèi)完成傳輸。因此，另一種工具——網(wǎng)絡(luò)演算應(yīng)運(yùn)而生。

在網(wǎng)絡(luò)演算中，最基本且最關(guān)鍵的概念是到達(dá)曲線、服務(wù)曲線和服務(wù)曲線串聯(lián)。到達(dá)曲線描述流將要發(fā)送的最大數(shù)據(jù)量，服務(wù)曲線描述服務(wù)節(jié)點(diǎn)保證處理的最小數(shù)據(jù)量。如圖1 所示，假設(shè)業(yè)務(wù)到達(dá)流量經(jīng)過(guò)了令牌桶過(guò)濾器（TBF,token bucket filter），TBF 的發(fā)送速率為ρ，令牌桶的大小為σ，則經(jīng)過(guò)TBF 的流的到達(dá)曲線可表示為ρt+σ。業(yè)務(wù)流量被發(fā)送到節(jié)點(diǎn)進(jìn)行處理，假設(shè)該節(jié)點(diǎn)的服務(wù)曲線為γ(t?θ)，該服務(wù)曲線表示該節(jié)點(diǎn)的處理速率為γ，數(shù)據(jù)包在得到處理之前將等待θ時(shí)間[13]。基于到達(dá)曲線和服務(wù)曲線，可以得到2 個(gè)重要概念，分別是時(shí)延上限和隊(duì)列長(zhǎng)度上限。時(shí)延上限的值等于到達(dá)曲線與服務(wù)曲線的最大水平偏差，隊(duì)列長(zhǎng)度上限的值等于到達(dá)曲線和服務(wù)曲線的最大垂直偏差。如果用α(t) 和β(t) 分別表示到達(dá)曲線和服務(wù)曲線，則時(shí)延上限的表達(dá)式為式(1)，隊(duì)列長(zhǎng)度上限的表達(dá)式為式(2)。在這里，可以得到時(shí)延上限的值為σ/ +γ θ，隊(duì)列長(zhǎng)度的上限為ρ+θ σ。

上述為網(wǎng)絡(luò)演算在單個(gè)節(jié)點(diǎn)中的運(yùn)用，然而在網(wǎng)絡(luò)中，通常存在多個(gè)節(jié)點(diǎn)串聯(lián)的情況。此時(shí)，端到端的時(shí)延上限或隊(duì)列長(zhǎng)度上限不能簡(jiǎn)單地通過(guò)累加單個(gè)VNF 節(jié)點(diǎn)上的時(shí)延上限或隊(duì)列長(zhǎng)度上限來(lái)獲得。網(wǎng)絡(luò)演算理論給出了計(jì)算多節(jié)點(diǎn)串聯(lián)情況下的端到端服務(wù)曲線的方法。如圖2 所示，2 個(gè)獨(dú)立的節(jié)點(diǎn)分別對(duì)應(yīng)2 條服務(wù)曲線，假設(shè)這兩個(gè)節(jié)點(diǎn)的服務(wù)曲線分別為β1(t)=γ1(t?θ1)和β2(t)=γ2(t?θ2)。然后，串聯(lián)后的2 個(gè)節(jié)點(diǎn)的端到端服務(wù)曲線為β1(t)?β2(t)，其中符號(hào)?表示最小化卷積，其具體表達(dá)式如式(3)所示。在圖2 的情況中，2 個(gè)節(jié)點(diǎn)串聯(lián)后的端到端服務(wù)曲線是γ2(t?θ1?θ2)。

網(wǎng)絡(luò)演算能夠計(jì)算多個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)串聯(lián)后端到端的服務(wù)曲線，而服務(wù)鏈則由多個(gè)VNF 節(jié)點(diǎn)串聯(lián)組成。這意味著，當(dāng)?shù)玫椒?wù)鏈中每個(gè)VNF 的服務(wù)曲線后，網(wǎng)絡(luò)演算能夠計(jì)算服務(wù)鏈的端到端服務(wù)曲線，從而計(jì)算數(shù)據(jù)包經(jīng)過(guò)服務(wù)鏈的時(shí)延上限。因此，網(wǎng)絡(luò)演算在本文問(wèn)題場(chǎng)景中具有良好的適用性。

3 問(wèn)題描述

本節(jié)給出了DSC 部署問(wèn)題的系統(tǒng)模型和數(shù)學(xué)建模。DSC 的目標(biāo)是為每一個(gè)接收的網(wǎng)絡(luò)業(yè)務(wù)請(qǐng)求確定最佳的服務(wù)鏈部署方案，在保證服務(wù)鏈端到端時(shí)延嚴(yán)格滿足業(yè)務(wù)需求的同時(shí)，使接收的服務(wù)鏈總量最大。

3.1 系統(tǒng)模型

1) 底層網(wǎng)絡(luò)基礎(chǔ)設(shè)施

2) 網(wǎng)絡(luò)業(yè)務(wù)請(qǐng)求

在本文問(wèn)題中，假設(shè)全部的網(wǎng)絡(luò)業(yè)務(wù)請(qǐng)求同時(shí)全部到達(dá)（模型和算法也支持業(yè)務(wù)請(qǐng)求逐個(gè)到達(dá)的情況）。對(duì)于每一個(gè)網(wǎng)絡(luò)業(yè)務(wù)請(qǐng)求，網(wǎng)絡(luò)運(yùn)營(yíng)商需要決定是否對(duì)其接收。使用S={s1,s2,…,sK}表示全部網(wǎng)絡(luò)業(yè)務(wù)請(qǐng)求的集合，其中K為集合S中業(yè)務(wù)請(qǐng)求的數(shù)量。第k個(gè)網(wǎng)絡(luò)業(yè)務(wù)請(qǐng)求包含一條服務(wù)鏈。服務(wù)鏈由一組按序排列的VNF 節(jié)點(diǎn)Fk和一組虛擬鏈路Lk組成，為了便于說(shuō)明，分別用表示業(yè)務(wù)請(qǐng)求中的第i個(gè)VNF 節(jié)點(diǎn)和第j條虛擬鏈路。服務(wù)鏈中的每一個(gè)VNF 都有一種對(duì)應(yīng)的類型，=1表示的類型為ψh。此外，每一種類型的VNF 都會(huì)被分配一定的資源。業(yè)務(wù)請(qǐng)求除了包含的服務(wù)鏈，還會(huì)指定業(yè)務(wù)流量的起點(diǎn)和終點(diǎn)，分別表示為。業(yè)務(wù)流量由源點(diǎn)的用戶生成，在進(jìn)入網(wǎng)絡(luò)之前首先會(huì)經(jīng)過(guò)TBF 進(jìn)行整形。TBF 的參數(shù)包含ρk和σk，這意味著允許終端用戶一次性發(fā)送大小為σk的數(shù)據(jù)量，但平均的發(fā)送速率不能超過(guò)ρk。業(yè)務(wù)流量從入口節(jié)點(diǎn)開(kāi)始，依次按序經(jīng)過(guò)全部的VNF 節(jié)點(diǎn)，最終到達(dá)終點(diǎn)節(jié)點(diǎn)。所有數(shù)據(jù)包的端到端時(shí)延應(yīng)滿足業(yè)務(wù)的時(shí)延要求，記為Dk。

3) 服務(wù)鏈部署示例

以一個(gè)例子來(lái)介紹業(yè)務(wù)請(qǐng)求中服務(wù)鏈的部署。部署主要包括VNF 節(jié)點(diǎn)的映射、虛擬鏈路的映射以及VNF 節(jié)點(diǎn)的資源分配。部署示例如圖3 所示。假設(shè)業(yè)務(wù)請(qǐng)求中包含的服務(wù)鏈由3 個(gè)VNF 組成，源點(diǎn)為底層物理節(jié)點(diǎn)1，終點(diǎn)為底層物理節(jié)點(diǎn)4。為了便于表示服務(wù)鏈的源點(diǎn)和終點(diǎn)，構(gòu)造了一個(gè)偽頭部VNF和偽尾部VNF。這2 個(gè)偽VNF 提前映射到源點(diǎn)和終點(diǎn)。接下來(lái)，需要確定每個(gè)VNF 和虛擬鏈路的映射。在本例中，VNF1映射到底層物理節(jié)點(diǎn)2，而VNF2和VNF3都映射到物理節(jié)點(diǎn)3。業(yè)務(wù)流量通過(guò)最短路徑依次遍歷底層物理節(jié)點(diǎn)1、2、3、4。同時(shí)虛擬鏈路被映射到對(duì)應(yīng)的路徑上，特別是，VNF2和VNF3之間的虛擬鏈路并沒(méi)有映射到物理鏈路，而是映射到底層物理節(jié)點(diǎn)3 內(nèi)部的鏈路。當(dāng)服務(wù)鏈中的節(jié)點(diǎn)和鏈路的映射確定后，需要為VNF 所映射的VNF實(shí)例分配資源，即完成了一條服務(wù)鏈的部署。

3.2 數(shù)學(xué)建模

本節(jié)將基于上述系統(tǒng)模型，對(duì)DSC 的部署問(wèn)題進(jìn)行數(shù)學(xué)建模。

1) DSC 部署問(wèn)題的優(yōu)化目標(biāo)

DSC 部署問(wèn)題的優(yōu)化目標(biāo)是最大化接收的業(yè)務(wù)量，且保證服務(wù)鏈的端到端上限時(shí)延嚴(yán)格滿足業(yè)務(wù)的需求。接收的業(yè)務(wù)總量表示為式(4)，其中Wk表示是否接收業(yè)務(wù)請(qǐng)求sk。

2) 底層物理節(jié)點(diǎn)容量限制

在系統(tǒng)模型中，Rhn表示分配給節(jié)點(diǎn)上類型為ψh的VNF 的總資源量。式(5)保證了分配給一個(gè)底層物理節(jié)點(diǎn)上所有類型的VNF 的資源總量不能超過(guò)該底層物理節(jié)點(diǎn)的資源容量。

3) 底層物理鏈路容量限制

底層物理鏈路也有帶寬限制。首先，為了表示虛擬鏈路是如何映射到底層物理鏈路的，定義變量。如果業(yè)務(wù)請(qǐng)求sk中的第j條虛擬鏈路映射到之間的物理鏈路，則。此外，物理鏈路2 個(gè)方向的流量將共享帶寬。因此，式(6)保證了物理鏈路上的總流量滿足其帶寬限制。

4) VNF 映射限制

為了表示服務(wù)鏈中的VNF 是如何映射到底層物理節(jié)點(diǎn)的，定義變量表示業(yè)務(wù)sk中的第i個(gè)VNF 被映射到上。式(7)確保了接收的每一個(gè)請(qǐng)求中的每個(gè)VNF 都完成映射且僅被映射一次。

5) VNF 類型限制在系統(tǒng)模型中，假設(shè)每個(gè)底層物理節(jié)點(diǎn)支持部分的VNF 類型，例如，高性能防火墻需要FPGA硬件加速，則只有配備了FPGA 的物理節(jié)點(diǎn)才能支持該網(wǎng)絡(luò)功能。式(8)表示一個(gè)VNF 只能被映射到支持該VNF 類型的底層物理節(jié)點(diǎn)。

6) 虛擬鏈路映射限制

每條虛擬鏈路可以從2個(gè)不同的方向映射到一條物理鏈路。此外，每條虛擬鏈路可以映射到多條物理鏈路。因此，使用式(9)保證一條虛擬鏈路不會(huì)同時(shí)映射到物理鏈路的2 個(gè)方向上，以避免產(chǎn)生環(huán)路。此外，使用式(10)保證每個(gè)底層物理節(jié)點(diǎn)的輸出流量總量與輸入流量總量相等，如此，同一個(gè)業(yè)務(wù)請(qǐng)求中的虛擬鏈路最終可以形成端到端連續(xù)的路由路徑。

7) 端到端時(shí)延限制

最后一個(gè)限制條件是端到端時(shí)延的限制。Dk*表示部署后的服務(wù)鏈的端到端時(shí)延上限。Dk*的確切形式將在第4 節(jié)中詳細(xì)介紹。式(11)表示服務(wù)鏈的端到端時(shí)延應(yīng)嚴(yán)格滿足業(yè)務(wù)的時(shí)延要求。

4 服務(wù)鏈端到端時(shí)延上限計(jì)算

在問(wèn)題的數(shù)學(xué)建模中，服務(wù)鏈部署后的端到端時(shí)延暫時(shí)用Dk*表示。本節(jié)將應(yīng)用網(wǎng)絡(luò)演算推導(dǎo)Dk*的具體表達(dá)式。

根據(jù)第2 節(jié)給出的示例，需要計(jì)算服務(wù)鏈的端到端時(shí)延上限，則首先需要獲取業(yè)務(wù)流量的到達(dá)曲線以及服務(wù)鏈的端到端服務(wù)曲線。在系統(tǒng)模型中，業(yè)務(wù)流量在進(jìn)入網(wǎng)絡(luò)之前由TBF 進(jìn)行整形。因此，業(yè)務(wù)流量的到達(dá)曲線很容易得到。式(12)表示業(yè)務(wù)sk的到達(dá)曲線。

接下來(lái)，將推導(dǎo)業(yè)務(wù)sk的端到端服務(wù)曲線。業(yè)務(wù)流量在網(wǎng)絡(luò)中會(huì)經(jīng)過(guò)VNF 節(jié)點(diǎn)、物理交換機(jī)和物理鏈路，這些網(wǎng)元都有其各自的服務(wù)曲線。首先，研究VNF 節(jié)點(diǎn)的服務(wù)曲線。本文使用速率?時(shí)延服務(wù)曲線對(duì)VNF 節(jié)點(diǎn)進(jìn)行建模。由于分配給VNF 的資源是可變化的，因此VNF 服務(wù)曲線中的速率參數(shù)會(huì)隨之變化。為此，通過(guò)實(shí)驗(yàn)驗(yàn)證了VNF 節(jié)點(diǎn)的速率與分配的資源之間的關(guān)系。實(shí)驗(yàn)中開(kāi)發(fā)了2 種示例性質(zhì)的 VNF，分別為 VNF-Firewall 和VNF-NAT。調(diào)整分配給VNF 的CPU 資源的百分比并測(cè)量VNF的速率，例如當(dāng)分配的CPU資源為40%時(shí)，則意味著數(shù)據(jù)包處理進(jìn)程消耗了CPU 40%的時(shí)間片，結(jié)果如圖4 所示。從圖4 可以看出，VNF的速率與分配的資源量成正比。因此，分配的資源與速率的關(guān)系如式(13)所示，其中λhn是一個(gè)常數(shù)，可以通過(guò)實(shí)驗(yàn)獲得。最終，上類型為ψh的VNF 的總服務(wù)曲線如式(14)所示。

式(14)中的服務(wù)曲線代表的是整個(gè)VNF的服務(wù)曲線。然而，多個(gè)服務(wù)鏈可能共享同一個(gè)VNF 并競(jìng)爭(zhēng)資源。因此，對(duì)于每一條服務(wù)鏈，需要計(jì)算其在VNF 上獨(dú)立的服務(wù)曲線。基于單個(gè)VNF 上獨(dú)立的服務(wù)曲線，計(jì)算服務(wù)鏈端到端時(shí)延上限的一種簡(jiǎn)易方法是根據(jù)業(yè)務(wù)的到達(dá)曲線和VNF 上獨(dú)立的服務(wù)曲線計(jì)算服務(wù)鏈經(jīng)過(guò)每一個(gè)VNF 的時(shí)延上限，然后端到端的時(shí)延上限為每一個(gè)VNF 上的時(shí)延上限的累加。然而，由于“pay burst once”現(xiàn)象的存在，這種簡(jiǎn)易的方法會(huì)放大端到端的時(shí)延上限。因此，正確的方法是在考慮服務(wù)鏈之間競(jìng)爭(zhēng)的情況下，計(jì)算服務(wù)鏈端到端整體的服務(wù)曲線，并根據(jù)端到端整體的服務(wù)曲線和業(yè)務(wù)流量的到達(dá)曲線計(jì)算端到端時(shí)延上限。

為此，首先需要推導(dǎo)服務(wù)鏈經(jīng)過(guò)單個(gè)VNF 時(shí)獨(dú)立的服務(wù)曲線。根據(jù)文獻(xiàn)[14]可知sk所經(jīng)過(guò)的VNF 上交叉流量的到達(dá)曲線。式(15)表示底層物理節(jié)點(diǎn)上類型為ψh的VNF 上的總流量大小。基于式(15)，sk中第i個(gè)VNF所在的VNF 實(shí)例上的總流量大小可以表示為式(16)。為了簡(jiǎn)化的表達(dá)式，定義一個(gè)變量，其值如式(17)所示。然后，的值可以簡(jiǎn)化為式(18)，sk所經(jīng)過(guò)的VNF上交叉流量的到達(dá)曲線可以表示為式(19)。根據(jù)文獻(xiàn)[14]中第4.B 節(jié)中給出的理論，針對(duì)的獨(dú)立服務(wù)曲線仍然為rate-latency 的類型，其具體形式如式(20)所示，其中和的值分別如式(21)和式(22)所示。

在得到sk中單個(gè)VNF 獨(dú)立的服務(wù)曲線后，可以根據(jù)網(wǎng)絡(luò)演算理論輕松地得到sk端到端的服務(wù)曲線。根據(jù)網(wǎng)絡(luò)演算理論[15]，s k中多個(gè)串聯(lián)的VNF的服務(wù)曲線如式(23)所示。符號(hào)?表示極小化卷積。sk端到端的服務(wù)曲線仍然是rate-latency 類型，如果使用式(24)表示sk的端到端服務(wù)曲線，則γk和θk的值分別如式(25)和式(26)所示。最后，可以基于網(wǎng)絡(luò)演算理論得到sk中所有VNF 節(jié)點(diǎn)串聯(lián)后的端到端時(shí)延上限為式(27)。

由式(25)和式(26)可以觀察到，端到端服務(wù)曲線的速率參數(shù)取決于全部串聯(lián)的VNF 節(jié)點(diǎn)中的最小速率，而端到端服務(wù)曲線中的時(shí)延參數(shù)是全部串聯(lián)的VNF 節(jié)點(diǎn)的時(shí)延之和。這一觀察結(jié)果指導(dǎo)本文將更多的資源分配給瓶頸VNF 節(jié)點(diǎn)，以提高串聯(lián)的VNF 節(jié)點(diǎn)中最小的速率，從而提高端到端服務(wù)曲線的速率。此外，這對(duì)研究交換機(jī)和物理鏈路的時(shí)延也具有一定的指導(dǎo)意義。交換機(jī)的服務(wù)曲線認(rèn)為是rate-latency 類型，可以表示為γs(t?θs)。由于交換機(jī)的處理速率γs大于全部的VNF節(jié)點(diǎn)，因此在端到端服務(wù)曲線中考慮交換機(jī)并不會(huì)影響γk的值。因此，數(shù)據(jù)包每經(jīng)過(guò)一個(gè)交換機(jī)只會(huì)為數(shù)據(jù)包增加一個(gè)固定的時(shí)延值，即θs。服務(wù)鏈路由路徑中包含的交換機(jī)數(shù)量等于包含的物理鏈路的數(shù)量減1。因此，數(shù)據(jù)包經(jīng)過(guò)交換機(jī)產(chǎn)生的時(shí)延的值如式(28)所示。

對(duì)于物理鏈路，文獻(xiàn)[14]指出其服務(wù)曲線是一個(gè)脈沖函數(shù)，即速率為無(wú)限大，時(shí)延為一個(gè)固定值。這也符合常識(shí)的判斷，物理鏈路中的數(shù)據(jù)包不會(huì)產(chǎn)生排隊(duì)，數(shù)據(jù)包經(jīng)過(guò)物理鏈路的時(shí)延等于物理鏈路的傳輸時(shí)延。在系統(tǒng)模型中，使用′表示至的傳播時(shí)延。因此，數(shù)據(jù)包經(jīng)過(guò)物理鏈路產(chǎn)生的時(shí)延的值如式(29)所示。

5 服務(wù)鏈部署算法

本節(jié)介紹一種名為JRRA（joint routing and resource allocation）的啟發(fā)式算法來(lái)解決DSC 的部署問(wèn)題。JRRA 首先確定最優(yōu)服務(wù)鏈路由路徑，該路徑依次包含所有需要的VNF 節(jié)點(diǎn)，然后確定包含的VNF 節(jié)點(diǎn)的資源分配量。服務(wù)鏈路由路徑的選擇和VNF 節(jié)點(diǎn)的資源分配量將決定服務(wù)鏈的端到端時(shí)延。雖然已有許多相關(guān)文獻(xiàn)[16]研究了不同場(chǎng)景下的服務(wù)鏈優(yōu)化部署問(wèn)題，但是尚沒(méi)有算法能運(yùn)用于DSC 問(wèn)題，同時(shí)本問(wèn)題還存在3 個(gè)挑戰(zhàn)。

第一個(gè)挑戰(zhàn)來(lái)自服務(wù)鏈的路由。在不考慮VNF節(jié)點(diǎn)時(shí)延的情況下，需要找到端到端時(shí)延最小的路徑，同時(shí)，該路徑需要滿足一些額外的要求。第二個(gè)挑戰(zhàn)來(lái)自VNF 節(jié)點(diǎn)的資源分配。從式(25)、式(26)和式(27)可以看出，服務(wù)鏈中任一VNF 節(jié)點(diǎn)分配的資源量將影響數(shù)據(jù)包通過(guò)服務(wù)鏈的時(shí)延。因此，服務(wù)鏈中所有VNF 節(jié)點(diǎn)的資源分配應(yīng)該協(xié)同進(jìn)行考慮。此外，由于不同的服務(wù)鏈之間會(huì)共享VNF 節(jié)點(diǎn)，不同的服務(wù)鏈中共享的VNF 節(jié)點(diǎn)的資源分配也應(yīng)該協(xié)同進(jìn)行考慮。第三個(gè)挑戰(zhàn)來(lái)自服務(wù)鏈路由與VNF 節(jié)點(diǎn)分配的協(xié)同，由于兩者都將對(duì)服務(wù)鏈的端到端時(shí)延產(chǎn)生影響，因此需要將兩者協(xié)同進(jìn)行考慮。

JRRA 算法分為兩步。第一步，將服務(wù)鏈路由建模成了一個(gè)可解的線性規(guī)劃問(wèn)題，此外還提出了一種基于多層拓?fù)涞膯l(fā)式服務(wù)鏈路由方法來(lái)解決第一個(gè)挑戰(zhàn)。第二步，通過(guò)推導(dǎo)確定為每個(gè)VNF節(jié)點(diǎn)分配的資源量來(lái)解決第二個(gè)挑戰(zhàn)。通過(guò)引入最大允許的VNF 時(shí)延參數(shù)將第一步與第二步進(jìn)行協(xié)同來(lái)解決第三個(gè)挑戰(zhàn)。

5.1 算法概述

算法1JRRA 算法主流程

JRRA 算法的流程如算法1 所示，首先根據(jù)ρk/Jk的值（每單位服務(wù)鏈長(zhǎng)度的吞吐）降序排列所有業(yè)務(wù)請(qǐng)求，然后按序逐個(gè)部署業(yè)務(wù)請(qǐng)求。對(duì)于單個(gè)業(yè)務(wù)請(qǐng)求的部署，將按照?qǐng)D5 所示的示例進(jìn)行說(shuō)明。假設(shè)圖5 中的業(yè)務(wù)請(qǐng)求s k的帶寬要求為5 Mbit/s，業(yè)務(wù)從（節(jié)點(diǎn)A）開(kāi)始，到（節(jié)點(diǎn)F）結(jié)束，所需的VNF 類型依次為VNF1、VNF2和VNF3。首先去除剩余帶寬小于5 Mbit/s 的物理鏈路，構(gòu)造一個(gè)拓?fù)銰k（算法1 的第3 行），即節(jié)點(diǎn)A 和節(jié)點(diǎn)B之間的物理鏈路將被移除。拓?fù)銰k中剩余的每條鏈路的時(shí)延等于其原來(lái)的時(shí)延加上它所連接的交換機(jī)的轉(zhuǎn)發(fā)時(shí)延的一半，這是為了將節(jié)點(diǎn)時(shí)延轉(zhuǎn)移至鏈路時(shí)延。接下來(lái)的目標(biāo)是在Gk中為sk找到最短且可行路徑（FS-Path,feasible and shortest path）。FS-Path 應(yīng)滿足如下3 個(gè)要求。1) 從開(kāi)始，到結(jié)束。2) 路徑上所有物理鏈路的剩余帶寬都能夠承載業(yè)務(wù)。3) 端到端時(shí)延（僅包含交換機(jī)時(shí)延和鏈路傳輸時(shí)延，不包含VNF 節(jié)點(diǎn)時(shí)延）最小。如何找到FS-Path 的方法將在5.2 節(jié)中介紹，在這里使用一個(gè)函數(shù)FeasibleShortestPath()表示該方法（算法1的第5 行）。如果找不到FS-Path，sk將被拒絕。否則，將繼續(xù)在FS-Path 中為其包含的VNF 節(jié)點(diǎn)分配資源。

在VNF 節(jié)點(diǎn)資源分配的過(guò)程中，引入一個(gè)參數(shù)，名為最大允許VNF 節(jié)點(diǎn)時(shí)延的值等于業(yè)務(wù)的端到端時(shí)延需求Dk減去FS-Path 的總時(shí)延（算法1 的第7 行）。然后，分配給每個(gè)VNF節(jié)點(diǎn)資源可以根據(jù)推導(dǎo)得到，具體推導(dǎo)過(guò)程在5.3 節(jié)中描述，這里使用函數(shù)VNF_Resource()來(lái)替換它（算法1 的第8 行）。由于分配給每個(gè)VNF節(jié)點(diǎn)的資源數(shù)量在尋找服務(wù)鏈路由的過(guò)程中是不可預(yù)測(cè)的，因此無(wú)法確定底層物理節(jié)點(diǎn)是否能夠?yàn)閂NF 節(jié)點(diǎn)提供足夠的資源。因此，VNF 節(jié)點(diǎn)所需的資源可能存在不能被滿足的情況。為了處理這種情況，函數(shù)VNF_Resource()將返回資源不能被滿足的VNF 節(jié)點(diǎn)，這些VNF 節(jié)點(diǎn)包含在U-VNFs 集合中。U-VNFs 集合中的節(jié)點(diǎn)將從拓?fù)銰k中刪除。然后，在更新后的kG將重新尋找FS-Path（算法1 的第11 行）。如果所有VNF 節(jié)點(diǎn)所需要的資源都可以滿足，則業(yè)務(wù)請(qǐng)求sk將被接收。

5.2 服務(wù)鏈路由與節(jié)點(diǎn)映射

本節(jié)將介紹算法1中函數(shù)FeasibleShortestPath()的實(shí)現(xiàn)。根據(jù)FS-Path 的要求，可以通過(guò)求解以下ILP 模型來(lái)找到FS-Path。

然而，當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，基于ILP 的解決方案面臨計(jì)算時(shí)間長(zhǎng)的問(wèn)題。因此，本文也提出了一種高效的啟發(fā)式算法來(lái)確定FS-Path。經(jīng)典的Dijkstra算法[17]可以得到2 個(gè)節(jié)點(diǎn)之間的最小加權(quán)路徑，即時(shí)延最小的路徑。然而，Dijkstra 無(wú)法找到按序經(jīng)過(guò)所需的VNF 的最小加權(quán)路徑。文獻(xiàn)[18]中提出的基于多層拓?fù)涞姆?wù)鏈路由方法可以有效地解決這一問(wèn)題，但該方法不能保證路徑包含的物理鏈路的剩余帶寬能夠滿足業(yè)務(wù)的需求。雖然剩余帶寬小于業(yè)務(wù)帶寬需求的物理鏈路已經(jīng)在拓?fù)銰k中被提前移除，但業(yè)務(wù)流量可能會(huì)多次經(jīng)過(guò)同一條物理鏈路，從而導(dǎo)致物理鏈路的剩余帶寬出現(xiàn)不能夠滿足需求的情況。例如，在圖5 中，當(dāng)業(yè)務(wù)的路由路徑為A→C(VNF1)→E(VNF2)→C(VNF3)→E→F 時(shí)，端到端時(shí)延為10 ms，小于圖中標(biāo)注的路由路徑。但是，業(yè)務(wù)流量在節(jié)點(diǎn)C 和節(jié)點(diǎn)E 之間的物理鏈路上經(jīng)過(guò)了3 次，因此對(duì)該鏈路的帶寬要求為15 Mbit/s，然而該鏈路的剩余帶寬僅為8 Mbit/s。因此，本節(jié)提出了一個(gè)時(shí)延懲罰因子α（一個(gè)大于1 的常數(shù)），并將其應(yīng)用于文獻(xiàn)[18]所提方法中。當(dāng)文獻(xiàn)[18]中的方法找到的路由路徑包含剩余帶寬不足的物理鏈路時(shí)，將這些物理鏈路的時(shí)延乘以α。如此，這些物理鏈路在最小加權(quán)路徑的尋找過(guò)程中將逐漸不被優(yōu)先選擇。

算法2JRRA 服務(wù)鏈路由算法

算法2 給出了JRRA 算法中完整的服務(wù)鏈路由算法過(guò)程。首先，基于拓?fù)銰k構(gòu)造一個(gè)新的多層拓?fù)鋱D，如圖6 所示，其中層數(shù)等于服務(wù)鏈的長(zhǎng)度加1，每一層的拓?fù)渑cGk保持一致。層之間的連接取決于所需VNF 類型的位置。例如，節(jié)點(diǎn)B 和節(jié)點(diǎn)C 支持的類型為VNF1，則節(jié)點(diǎn)B1與節(jié)點(diǎn)B2相連，節(jié)點(diǎn)C1與節(jié)點(diǎn)C2相連。這確保了當(dāng)路由路徑從第1 層到達(dá)第2 層時(shí)，必定會(huì)經(jīng)過(guò)類型為VNF1的VNF。類似地，將其他相鄰的兩層之間進(jìn)行連接。每層中物理鏈路的時(shí)延與Gk保持一致，連接相鄰兩層的鏈路的時(shí)延設(shè)置為0。指定節(jié)點(diǎn)A1和節(jié)點(diǎn)F4分別作為服務(wù)鏈路由的起點(diǎn)和終點(diǎn)，運(yùn)用Dijkstra算法尋找到起點(diǎn)和終點(diǎn)之間的最小加權(quán)路徑S-Path（算法2 中第3 行），S-Path 將依次經(jīng)過(guò)第一層到達(dá)第四層，也就是說(shuō)，選擇的S-Path 也將依次包含所需的VNF。然后，將檢查得到的S-Path，以保證其中所包含的物理鏈路的剩余帶寬是足夠的（算法2中第10 行）。不合格的物理鏈路將加入U(xiǎn)-Links 集合，并將U-Links 集合中的鏈路的時(shí)延乘以α后再重新尋找S-Path（算法2 中第10～13 行）。最終，通過(guò)檢查的S-Path 即FS-Path。

5.3 VNF 節(jié)點(diǎn)資源分配

本節(jié)將介紹算法1 中的VNF_Resource()函數(shù)的實(shí)現(xiàn)。在推導(dǎo)VNF 的資源數(shù)量之前，已經(jīng)確定了最大允許的VNF 節(jié)點(diǎn)時(shí)延，即。接下來(lái)，將基于的值，以業(yè)務(wù)請(qǐng)求sk為例，推導(dǎo)出為sk所對(duì)應(yīng)的FS-Path包含的VNF節(jié)點(diǎn)分配的最優(yōu)資源量。分配的資源量應(yīng)滿足以下3 個(gè)要求。1) 端到端總的VNF 節(jié)點(diǎn)時(shí)延在sk之前接收部署的業(yè)務(wù)的端到端總VNF 節(jié)點(diǎn)時(shí)延不應(yīng)增加；3) VNF 節(jié)點(diǎn)的處理速率應(yīng)大于所承載的全部業(yè)務(wù)的帶寬需求。當(dāng)滿足上述3 個(gè)要求時(shí)，分配給VNF節(jié)點(diǎn)的最小資源量即最優(yōu)資源量。

接下來(lái)，以sk為例說(shuō)明如何推導(dǎo)出最優(yōu)的VNF資源分配方案。為了簡(jiǎn)化推導(dǎo)過(guò)程中使用到的表達(dá)式，首先定義了式(31)所示的變量。然后，式(21)和式(22)可以分別簡(jiǎn)化為式(32)和式(33)。其中表示分配給sk中第i個(gè)VNF 部署所在的VNF 實(shí)例的資源量。由于端到端的VNF總時(shí)延與分配給VNF的資源成反比，則當(dāng)端到端的總VNF 時(shí)延等于時(shí)，分配的資源量最小。因此，將式(33)中的值代入式(27)，可以得到式(34)。

由式(25)可知，服務(wù)鏈端到端服務(wù)曲線的速率由服務(wù)鏈中處理速率最小的VNF 決定，處理速率最小的VNF 將限制端到端服務(wù)曲線的速率，從而增加端到端的VNF 時(shí)延。因此，應(yīng)該提高處理速率最小的VNF 的處理速率，避免出現(xiàn)瓶頸。另一方面，如果某一VNF 的處理速率大于服務(wù)鏈端到端服務(wù)曲線的速率，這對(duì)于提高服務(wù)鏈整體處理速率沒(méi)有幫助，從而造成資源浪費(fèi)。綜上，服務(wù)鏈中的每一個(gè)VNF 的處理速率都將與服務(wù)鏈端到端的處理速率保持一致，因此，服務(wù)鏈中的每個(gè)VNF都應(yīng)該具有相同的速率，據(jù)此，可以得到式(35)。將式(35)中的的表達(dá)式代入式(34)，可以得到γk的值。然后，再將γk的值代入式(35)，可以得到的值。

然而，上述資源分配方案可能不能滿足第二個(gè)和第三個(gè)要求。以業(yè)務(wù)sk中第i個(gè)VNF 所在的VNF實(shí)例為例，另一個(gè)業(yè)務(wù)sk'中的VNF 可能在業(yè)務(wù)sk部署之前就已經(jīng)存在于該VNF 實(shí)例中。在部署sk時(shí)，需要重新確定分配給該VNF 實(shí)例的資源量，只需要保證γk′的值不降低，θk′的值不增加即可。應(yīng)保證不增加sk'對(duì)應(yīng)的VNF節(jié)點(diǎn)的總時(shí)延。為此，因此，可以得到式(36)和式(37)。至此，第二個(gè)要求已經(jīng)滿足。根據(jù)第三個(gè)要求，即VNF 節(jié)點(diǎn)的處理速率應(yīng)大于所承載的全部業(yè)務(wù)的帶寬需求，可以得到式(38)。最終，確定滿足3 個(gè)要求，即同時(shí)滿足式(35)、式(36)、式(37)和式(38)的最小VNF 節(jié)點(diǎn)資源分配量，即最優(yōu)的VNF 節(jié)點(diǎn)資源分配方案。

綜上，DSC 問(wèn)題的優(yōu)化目標(biāo)是幫助服務(wù)提供商最大化接收的業(yè)務(wù)量，即最大化式(4)的值，同時(shí)通過(guò)協(xié)同優(yōu)化服務(wù)鏈路由與VNF 節(jié)點(diǎn)資源分配，使通過(guò)服務(wù)鏈的數(shù)據(jù)包的最大時(shí)延小于業(yè)務(wù)的時(shí)延需求，即保證每一個(gè)數(shù)據(jù)包均能在指定時(shí)延內(nèi)完成傳輸。

6 實(shí)驗(yàn)分析

本節(jié)通過(guò)數(shù)值模擬來(lái)評(píng)估所提模型和算法的性能。首先介紹實(shí)驗(yàn)設(shè)置，然后從不同方面對(duì)算法的性能進(jìn)行評(píng)估，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行討論。

6.1 實(shí)驗(yàn)設(shè)置

為了獲得準(zhǔn)確的統(tǒng)計(jì)，每個(gè)數(shù)據(jù)點(diǎn)通過(guò)平均10 次獨(dú)立模擬的結(jié)果得到。基于Python 進(jìn)行數(shù)值模擬，利用Python 中的PySCIPOpt 套件[19]求解ILP 模型。此外，運(yùn)行數(shù)值模擬的計(jì)算機(jī)配備了主頻為3.40 GHz 的CPU 以及大小為16 GB 的內(nèi)存。實(shí)驗(yàn)在Internet Topology Zoo[20]提供的2 個(gè)真實(shí)的網(wǎng)絡(luò)拓?fù)渲羞M(jìn)行，其中網(wǎng)絡(luò)拓?fù)? 由42 個(gè)物理節(jié)點(diǎn)和66 條物理鏈路組成，而網(wǎng)絡(luò)拓?fù)? 由13 個(gè)物理節(jié)點(diǎn)和15 條物理鏈路組成。每個(gè)物理節(jié)點(diǎn)包含的CPU核數(shù)在[50,100]中隨機(jī)生成，此外，每個(gè)物理節(jié)點(diǎn)對(duì)VNF 類型的默認(rèn)支持率為70%，假如網(wǎng)絡(luò)中存在30 種不同類型的VNF，則每個(gè)物理節(jié)點(diǎn)將隨機(jī)支持其中的21 種VNF 類型。每條物理鏈路包含2 個(gè)參數(shù)，包括可用帶寬和傳播時(shí)延。每條物理鏈路的帶寬在[10,100]Gbit/s 中隨機(jī)生成，傳播時(shí)延在[1,5]ms中隨機(jī)生成。

為了生成業(yè)務(wù)請(qǐng)求，首先生成一組VNF 類型，包含30 種不同的VNF 類型。對(duì)于每一種VNF 類型，所需CPU 資源和處理速率之間的關(guān)系已經(jīng)在式(13)中進(jìn)行了討論。式(13)中的常數(shù)λhn在[0,1]中隨機(jī)產(chǎn)生，例如，λhn=0.5表示在物理節(jié)點(diǎn)上，類型為ψh的VNF 處理1 Gbit/s 的流量需要0.5 個(gè)CPU 核（占用1 個(gè)CPU 50%的運(yùn)行周期）。業(yè)務(wù)請(qǐng)求中的服務(wù)鏈包含的VNF 的數(shù)量從[2,7]中隨機(jī)選擇，每一個(gè)VNF 的類型將從VNF 類型的集合中隨機(jī)選擇。此外，每個(gè)業(yè)務(wù)請(qǐng)求的入口和出口節(jié)點(diǎn)從全部的物理節(jié)點(diǎn)中隨機(jī)選擇。每個(gè)業(yè)務(wù)請(qǐng)求的流量在進(jìn)入網(wǎng)絡(luò)前都將由TBF 進(jìn)行流量整形。每個(gè)業(yè)務(wù)請(qǐng)求中TBF 的rate 參數(shù)在[100,1 000]Mbit/s 中隨機(jī)生成，burst 參數(shù)在[1,10]Mbit/s 中隨機(jī)生成。最后，當(dāng)網(wǎng)絡(luò)拓?fù)? 作為實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)鋾r(shí)，共隨機(jī)生成2 000 個(gè)業(yè)務(wù)請(qǐng)求，而當(dāng)網(wǎng)絡(luò)拓?fù)? 作為實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)鋾r(shí)，共隨機(jī)生成500 個(gè)業(yè)務(wù)請(qǐng)求。如果算法能為業(yè)務(wù)請(qǐng)求找到一個(gè)可行的解決方案，則該請(qǐng)求將被接收，否則請(qǐng)求被拒絕。

本節(jié)對(duì)比了以下2 種算法。1) JRRA-MLT 算法。JRRA-MLT算法基于多層拓?fù)鋱D為業(yè)務(wù)尋找服務(wù)鏈的路由。2) JRRA-ILP 算法。JRRA-ILP 算法與JRRA-MLT算法的不同之處在于JRRA-ILP通過(guò)5.2節(jié)中的ILP 模型來(lái)尋找服務(wù)鏈的路由。JRRA-MLT和JRRA-ILP 算法均通過(guò)5.3 節(jié)中的方法確定VNF節(jié)點(diǎn)的資源分配量。

6.2 實(shí)驗(yàn)結(jié)果

DSC 部署問(wèn)題的目標(biāo)是幫助服務(wù)提供商最大化接收的業(yè)務(wù)量，即式(4)所示的值。因此，在實(shí)驗(yàn)中，使用接收的業(yè)務(wù)量作為算法的性能評(píng)估指標(biāo)，并測(cè)試了一些因素對(duì)算法性能的影響。

圖7 展示了采用不同的實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)涞那闆r下不同算法接收的業(yè)務(wù)量大小。從圖7 中可以看出，JRRA-ILP 算法的性能表現(xiàn)優(yōu)于JRRA-MLT 算法。這是因?yàn)榛贗LP 確定的服務(wù)鏈路由路徑具有更小的端到端時(shí)延，當(dāng)鏈路時(shí)延和交換機(jī)時(shí)延越小時(shí)，則對(duì)應(yīng)的最大允許的VNF 節(jié)點(diǎn)時(shí)延則變得更大，從而減少VNF 節(jié)點(diǎn)對(duì)資源的使用。由于VNF 節(jié)點(diǎn)資源使用的降低，在網(wǎng)絡(luò)中VNF 節(jié)點(diǎn)資源總量固定的情況下，所能服務(wù)的業(yè)務(wù)總量得到增加。此外，可以觀察到，在2 種網(wǎng)絡(luò)拓?fù)渲校琂RRA-MLT 算法的性能僅比JRRA-ILP 算法降低了10%左右，這證明了所設(shè)計(jì)的基于多層網(wǎng)絡(luò)拓?fù)涞姆?wù)鏈路由算法能有效地尋找到可行且端到端時(shí)延相對(duì)較小的服務(wù)鏈路由路徑。考慮到基于多層網(wǎng)絡(luò)拓?fù)涞姆?wù)鏈路由算法計(jì)算復(fù)雜度更低，該算法適用于大規(guī)模網(wǎng)絡(luò)拓?fù)洌⒛苋〉门c最優(yōu)結(jié)果近似的性能表現(xiàn)。

1) 服務(wù)鏈長(zhǎng)度的影響

首先評(píng)估了服務(wù)鏈長(zhǎng)度對(duì)算法性能的影響。本文測(cè)試了4 種不同范圍的服務(wù)鏈長(zhǎng)度，分別是(1,2]、[3,4]、[5,6]和[7,8)。評(píng)估結(jié)果展示在圖8 和圖9 中。可以觀察到，在2 種不同的實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)渲校S著服務(wù)鏈長(zhǎng)度的增加，接收的業(yè)務(wù)總量均減小，造成這一現(xiàn)象的原因有以下2 個(gè)。首先，服務(wù)鏈長(zhǎng)度的增加意味著服務(wù)鏈中包含的VNF 數(shù)量的增加，則接收相同大小的服務(wù)鏈將消耗更多的VNF 節(jié)點(diǎn)資源，因此，在物理節(jié)點(diǎn)資源總量一定的情況下，隨著服務(wù)鏈長(zhǎng)度的增加，接收的業(yè)務(wù)總量下降。第二個(gè)原因在于，隨著服務(wù)鏈長(zhǎng)度的增加，意味著服務(wù)鏈路由長(zhǎng)度的增加，即服務(wù)鏈所經(jīng)過(guò)的物理鏈路數(shù)量增加，這導(dǎo)致服務(wù)鏈端到端時(shí)延組成中的交換機(jī)時(shí)延和鏈路時(shí)延的占比提高，從而導(dǎo)致最大允許的VNF 節(jié)點(diǎn)時(shí)延降低。因此，服務(wù)鏈需要占用更多的VNF 節(jié)點(diǎn)資源來(lái)降低VNF 節(jié)點(diǎn)的時(shí)延。在這雙重原因疊加下，接收的業(yè)務(wù)總量迅速下降。

2) 物理節(jié)點(diǎn)對(duì)VNF 類型的支持率的影響

假設(shè)每個(gè)底層物理節(jié)點(diǎn)只能支持部分的VNF類型，將物理節(jié)點(diǎn)上支持的VNF 類型數(shù)量占網(wǎng)絡(luò)中VNF 類型的總數(shù)量定義為物理節(jié)點(diǎn)對(duì)VNF 類型的支持率，默認(rèn)情況下每個(gè)物理節(jié)點(diǎn)的VNF 類型支持率為70%。這里評(píng)估物理節(jié)點(diǎn)對(duì)VNF 類型的支持率對(duì)業(yè)務(wù)接收總量的影響。從圖10 和圖11 中可以看出，2 種算法接收的業(yè)務(wù)總量均隨著物理節(jié)點(diǎn)對(duì)VNF 類型的支持率的上升而增加。這可以通過(guò)多層網(wǎng)絡(luò)拓?fù)溥M(jìn)行解釋，當(dāng)物理節(jié)點(diǎn)對(duì)VNF 類型的支持率上升時(shí)，同一種類型的VNF 將在更多的物理節(jié)點(diǎn)上得到支持，這意味在服務(wù)鏈路由的過(guò)程中，多層網(wǎng)絡(luò)拓?fù)涞膶优c層之間的連接鏈路數(shù)將增加。如此，在源點(diǎn)和終點(diǎn)之間存在更多的可行路徑可供選擇，則找到端到端時(shí)延更小的服務(wù)鏈路由路徑的概率也越大。當(dāng)服務(wù)鏈路由路徑的端到端時(shí)延越小時(shí)，最大允許的VNF 節(jié)點(diǎn)時(shí)延將增加，服務(wù)鏈對(duì)VNF 節(jié)點(diǎn)資源的占用將降低，從而更多的業(yè)務(wù)請(qǐng)求可以被接收。

3) 業(yè)務(wù)時(shí)延要求的影響

接下來(lái)，進(jìn)一步研究業(yè)務(wù)時(shí)延要求的影響。默認(rèn)情況下，業(yè)務(wù)的時(shí)延要求在[20,100]ms 中隨機(jī)生成。在產(chǎn)生業(yè)務(wù)請(qǐng)求的過(guò)程中將時(shí)延的要求固定，探究設(shè)置不同業(yè)務(wù)時(shí)延需求時(shí)接收的業(yè)務(wù)總量的變化。圖12 和圖13 顯示，隨著業(yè)務(wù)時(shí)延要求的上升，接收的業(yè)務(wù)總量也會(huì)增加。這一點(diǎn)很容易解釋，根據(jù)算法1 第7 行，當(dāng)業(yè)務(wù)的時(shí)延要求較大時(shí)，在服務(wù)鏈路由路徑不變的情況下，最大允許VNF 節(jié)點(diǎn)時(shí)延變大。在上文也多次討論過(guò)了最大允許VNF節(jié)點(diǎn)時(shí)延變大將增大接收的業(yè)務(wù)總量。此外，觀察到在網(wǎng)絡(luò)拓?fù)? 中，當(dāng)業(yè)務(wù)時(shí)延要求設(shè)置為20 ms 時(shí)，接收的業(yè)務(wù)總量顯著下降。這是因?yàn)榫W(wǎng)絡(luò)拓?fù)? 的規(guī)模較大，當(dāng)業(yè)務(wù)時(shí)延要求設(shè)置為20 ms 時(shí)，部分業(yè)務(wù)因找不到可行的服務(wù)鏈路徑而被直接拒絕（算法2 中第7～8 行）。由于網(wǎng)絡(luò)拓?fù)? 的規(guī)模較小，這種情況并未發(fā)生。

4) 業(yè)務(wù)在線到達(dá)場(chǎng)景下算法性能

最后，評(píng)估業(yè)務(wù)在線到達(dá)場(chǎng)景下算法的性能表現(xiàn)。由于不能提前得知全部業(yè)務(wù)請(qǐng)求的信息，因此無(wú)法對(duì)業(yè)務(wù)請(qǐng)求進(jìn)行排序。每到達(dá)一個(gè)業(yè)務(wù)請(qǐng)求，運(yùn)行算法對(duì)業(yè)務(wù)進(jìn)行部署，若無(wú)法找到滿足業(yè)務(wù)時(shí)延的部署方案，則業(yè)務(wù)請(qǐng)求被拒絕。圖14 和圖15展示了隨著累計(jì)到達(dá)的業(yè)務(wù)請(qǐng)求數(shù)量的增加，接收的業(yè)務(wù)總量的變化。可以看到，在前期業(yè)務(wù)請(qǐng)求到達(dá)時(shí)，JRRA-ILP 和JRRA-MLT 算法均能為業(yè)務(wù)找到可行的部署方案而接收業(yè)務(wù)請(qǐng)求，從而2 種算法的性能表現(xiàn)一致。隨著接收的業(yè)務(wù)數(shù)量逐漸增加，由于JRRA-MLT 算法比JRRA-ILP 算法在接收同一個(gè)業(yè)務(wù)請(qǐng)求時(shí)將消耗更多的VNF 節(jié)點(diǎn)資源，從而導(dǎo)致JRRA-MLT 算法更早地耗盡了VNF 節(jié)點(diǎn)資源。例如，在網(wǎng)絡(luò)拓?fù)? 中，當(dāng)?shù)?00 個(gè)左右的業(yè)務(wù)請(qǐng)求到達(dá)時(shí)，JRRA-MLT 的業(yè)務(wù)接收率開(kāi)始下降，接收的業(yè)務(wù)總量開(kāi)始落后于JRRA-ILP。

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

遠(yuǎn)程醫(yī)療、自動(dòng)駕駛、工業(yè)自動(dòng)化等業(yè)務(wù)對(duì)網(wǎng)絡(luò)端到端時(shí)延的要求更加嚴(yán)格。本文研究了DSC的部署問(wèn)題，旨在為網(wǎng)絡(luò)業(yè)務(wù)中的服務(wù)鏈提供端到端時(shí)延嚴(yán)格保障的同時(shí)，最大化接收的業(yè)務(wù)總量。本文將網(wǎng)絡(luò)演算運(yùn)用于服務(wù)鏈的端到端時(shí)延計(jì)算中，實(shí)現(xiàn)為業(yè)務(wù)提供嚴(yán)格的端到端時(shí)延保障；將DSC 部署問(wèn)題建模為混合整數(shù)非線性規(guī)劃問(wèn)題，并將該問(wèn)題拆解為服務(wù)鏈路由子問(wèn)題和VNF 節(jié)點(diǎn)資源分配子問(wèn)題；將服務(wù)鏈路由子問(wèn)題建模為可解的線性規(guī)劃問(wèn)題，同時(shí)也提出了一種高效的啟發(fā)式法。此外，理論推導(dǎo)了VNF 節(jié)點(diǎn)的最佳資源分配值。最后，通過(guò)實(shí)驗(yàn)驗(yàn)證了所提算法的性能，結(jié)果顯示所提算法在性能表現(xiàn)上與最優(yōu)解接近。

本文研究成果在未來(lái)有望運(yùn)用于部署了虛擬網(wǎng)絡(luò)功能的5G 核心網(wǎng)中，為遠(yuǎn)程醫(yī)療等業(yè)務(wù)提供確定性時(shí)延保障。不過(guò)在實(shí)際生產(chǎn)環(huán)境中設(shè)計(jì)解決DSC 問(wèn)題時(shí)，需要進(jìn)一步考慮VNF 實(shí)例的不同類型的服務(wù)曲線以及不同的部署模型，這也是DSC問(wèn)題未來(lái)的研究方向。