端到端時延上限確定的服務鏈部署算法

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

3 問題描述

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

3.1 系統(tǒng)模型

1) 底層網(wǎng)絡基礎設施

2) 網(wǎng)絡業(yè)務請求

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

3) 服務鏈部署示例

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

3.2 數(shù)學建模

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

1) DSC 部署問題的優(yōu)化目標

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

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

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

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

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

4) VNF 映射限制

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

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

6) 虛擬鏈路映射限制

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

7) 端到端時延限制

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

4 服務鏈端到端時延上限計算

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

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

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

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

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

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

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

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

5 服務鏈部署算法

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

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

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

5.1 算法概述

算法1JRRA 算法主流程

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

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

5.2 服務鏈路由與節(jié)點映射

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

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

算法2JRRA 服務鏈路由算法

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

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

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

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

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

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

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

6 實驗分析

本節(jié)通過數(shù)值模擬來評估所提模型和算法的性能。首先介紹實驗設置，然后從不同方面對算法的性能進行評估，并對實驗結果進行討論。

6.1 實驗設置

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

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

本節(jié)對比了以下2 種算法。1) JRRA-MLT 算法。JRRA-MLT算法基于多層拓撲圖為業(yè)務尋找服務鏈的路由。2) JRRA-ILP 算法。JRRA-ILP 算法與JRRA-MLT算法的不同之處在于JRRA-ILP通過5.2節(jié)中的ILP 模型來尋找服務鏈的路由。JRRA-MLT和JRRA-ILP 算法均通過5.3 節(jié)中的方法確定VNF節(jié)點的資源分配量。

6.2 實驗結果

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

圖7 展示了采用不同的實驗網(wǎng)絡拓撲的情況下不同算法接收的業(yè)務量大小。從圖7 中可以看出，JRRA-ILP 算法的性能表現(xiàn)優(yōu)于JRRA-MLT 算法。這是因為基于ILP 確定的服務鏈路由路徑具有更小的端到端時延，當鏈路時延和交換機時延越小時，則對應的最大允許的VNF 節(jié)點時延則變得更大，從而減少VNF 節(jié)點對資源的使用。由于VNF 節(jié)點資源使用的降低，在網(wǎng)絡中VNF 節(jié)點資源總量固定的情況下，所能服務的業(yè)務總量得到增加。此外，可以觀察到，在2 種網(wǎng)絡拓撲中，JRRA-MLT 算法的性能僅比JRRA-ILP 算法降低了10%左右，這證明了所設計的基于多層網(wǎng)絡拓撲的服務鏈路由算法能有效地尋找到可行且端到端時延相對較小的服務鏈路由路徑。考慮到基于多層網(wǎng)絡拓撲的服務鏈路由算法計算復雜度更低，該算法適用于大規(guī)模網(wǎng)絡拓撲，并能取得與最優(yōu)結果近似的性能表現(xiàn)。

1) 服務鏈長度的影響

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

2) 物理節(jié)點對VNF 類型的支持率的影響

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

3) 業(yè)務時延要求的影響

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

4) 業(yè)務在線到達場景下算法性能

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

7 結束語

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

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