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

王澤南，張嬌，汪碩，黃韜，F.Richard Yu

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

1 引言

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

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

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

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

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

2 網絡演算基本概念

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

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

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

網絡演算能夠計算多個網絡節點串聯后端到端的服務曲線，而服務鏈則由多個VNF 節點串聯組成。這意味著，當得到服務鏈中每個VNF 的服務曲線后，網絡演算能夠計算服務鏈的端到端服務曲線，從而計算數據包經過服務鏈的時延上限。因此，網絡演算在本文問題場景中具有良好的適用性。

3 問題描述

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

3.1 系統模型

1) 底層網絡基礎設施

2) 網絡業務請求

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

3) 服務鏈部署示例

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

3.2 數學建模

本節將基于上述系統模型，對DSC 的部署問題進行數學建模。

1) DSC 部署問題的優化目標

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

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

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

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

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

4) VNF 映射限制

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

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

6) 虛擬鏈路映射限制

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

7) 端到端時延限制

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

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

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

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

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

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

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

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

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

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

5 服務鏈部署算法

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

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

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

5.1 算法概述

算法1JRRA 算法主流程

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

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

5.2 服務鏈路由與節點映射

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

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

算法2JRRA 服務鏈路由算法

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

5.3 VNF 節點資源分配

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

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

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

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

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

6 實驗分析

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

6.1 實驗設置

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

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

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

6.2 實驗結果

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

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

1) 服務鏈長度的影響

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

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

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

3) 業務時延要求的影響

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

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

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

7 結束語

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

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