基于延遲和抖動感知的多播服務功能樹嵌入算法

劉 亮 陳 翔 桂曉菁 徐勇軍 杜婭榮 侯澤天 段 潔

①(重慶郵電大學通信與信息工程學院 重慶 400065)

②(重慶郵電大學自動化學院 重慶 400065)

1 引 言

在支持網絡功能虛擬化(Network Function Virtualization, NFV)的軟件定義網絡(Software Defined Networks, SDNs)中，為實現可靠、安全及可擴展傳輸等目的，用戶請求流通常需要依序遍歷由多個虛擬網絡功能(Virtual Network Functions, VNFs)組成的服務功能鏈(Service Function Chain, SFC)[1]。對于單播請求流， SFC可以直接沿著單播路由路徑依次選擇嵌入節點進行VNF部署，目前已有大量文獻對這一工作進行了研究，特別是文獻[2]利用拉格朗日對偶理論[3]設計松弛算法求解了具有多資源多QoS約束的單播SFC嵌入問題，具有典型的代表性。多播通過共享的多播樹進行多路復用，與單播相比，可以減少骨干網50%以上的帶寬消耗[4]。2022年至2028年，全球視頻流媒體市場預計將以21.0%的復合年增長率擴張[5]，這些視頻流大多以多播的形式向用戶提供服務。在SDN/NFV架構中具有SFC需求的多播請求流(Multicast Request flows, MRs)是將流量從源點轉發到多個目的節點，每個源-目的對之間需要根據SFC的要求依序遍歷多個VNFs實例，這將形成一個虛擬網絡功能轉發圖[6]。圖1為該文構建的一條多播流從源點s依序經過由防火墻(FW)、入侵檢測系統(IDS)、入侵阻止系統(IPS)組成的3條相同SFC后到達各個目的節點的示意。顯然這3條SFC共同組成了一顆多播服務功能樹(Service Function Tree,SFT)。聯合考慮網絡中各種資源及QoS約束條件，為多播請求流嵌入SFC是一個巨大的挑戰。

圖1 多播服務功能樹

目前，在SDN/NFV架構中，研究多播SFT嵌入的文獻比較少。文獻[7-9]研究了在已經放置了多個VNF實例環境中MRs的路由問題，但文獻[7]沒有考慮路由過程中VNF的動態部署，文獻[8]考慮了VNF的運行和動態部署成本，但沒有聯合考慮網絡中交換節點的轉發成本，并且，它們都以多播源-目的對之間的單條SFC進行嵌入。文獻[9]重點關注多播業務鏈的遷移調整，文獻[10]則基于預測的方式對多播流的SFC進行動態嵌入，上述工作沒有基于多播服務功能樹(SFT)對SFC進行靈活整體嵌入，會造成網絡資源分配不均衡。文獻[11,12]研究了SFT的動態編排和整體嵌入，但文獻[11]假設所有VNFs都部署在一個NFV功能節點中，文獻[12]則要求多播分發點只能在部署的最后一個VNF節點之后進行，限制了SFT嵌入的靈活性和可擴展性，從而降低了網絡資源的使用效率。

此外，對于視頻會議、多人游戲等實時性要求較高的多播應用，對時延和抖動有嚴格要求。文獻[13-17]研究了SFT的靈活嵌入和部署問題，但文獻[13,14]沒有考慮多播延遲和抖動約束，文獻[15-17]考慮了端到端的延遲約束，但沒有考慮多播目的節點之間的抖動約束，上述工作會影響多播用戶的服務體驗質量。文獻[18]考慮用戶的移動性及加入退出機制，研究了NFV網絡中多播SFC的嵌入，調整和擴展問題。文獻[19]是在無線Mesh網絡中，考慮無線信號干擾和資源受限的情況下，以最小化鏈路成本為目標研究多播服務功能樹的嵌入問題。上述工作同樣沒有考慮多播SFT時延和抖動約束，且和本文的研究場景不同。

綜上所述，當前還沒有相關工作聯合考慮多VNFs實例環境下VNF的動態放置、網絡資源約束及網絡負載均衡等因素，研究具有嚴格時延和抖動感知的SFT靈活嵌入和多播路由算法。因此，本文在已有研究基礎上，提出一種基于最優鏈路選擇函數進行深度優先搜索構建具有嚴格時延和抖動約束的多播SFT嵌入算法。具體內容為：

(1)聯合考慮VNF動態放置，多資源約束(包括SDN交換機的轉發表容量、鏈路的帶寬、功能節點的CPU容量)及網絡負載均衡因素正式定義并用ILP模型刻畫了延遲和抖動感知的動態SFT嵌入和路由問題(the Delay and Jitter Aware Dynamical SFT embedding and Routing Problem, DJADSRP)。(2)設計輔助邊權圖，將資源消耗及時延指標轉化為邊權圖中的權值降低問題復雜性，提出最優鏈路選擇函數構建SFT嵌入算法(SFT-EA)求解原問題。(3)將提出的SFT-EA算法與現有算法進行性能對比，結果表明SFT-EA不僅較優地解決了多資源及時延和抖動聯合約束下的多播SFT嵌入問題，且在流接受率、網絡吞吐量和負載平衡方面具有更好的性能。

2 系統模型

2.1 物理網絡

將SDN/NFV網絡表示為G=(N,L)，其中N,L分別表示節點和鏈路的集合。用u,v ∈N和＜u,v ＞∈L分別表示物理節點和物理鏈路，為方便起見，后文用uv ∈L表示物理鏈路。網絡中有兩種節點類型，一種是負責轉發數據的交換節點Ns ∈N，另一種是由一臺或多臺服務器組成的功能節點Nf ∈N，N=Ns ∪Nf。G中有一臺SDN控制器，為每條多播請求流執行動態的VNF放置和路由路徑選擇。圖2為網絡示例，其中節點v1,v3,v4為功能節點，其余為交換節點。

圖2 SDN/NFV網絡示例

圖3 輔助邊權圖的構造

用MRi表示第i條具有SFC請求的多播流。其中i為整數。當路由MRi時，在節點u上，流表容量和剩余流表項的比率用和表示。用和表示節點u上的CPU容量和剩余比率。物理鏈路uv∈L的帶寬容量、剩余帶寬比率、傳輸時延分別用表示。用η(u)表示節點u的鄰居節點集合。

2.2 虛擬網絡功能

網絡中可能的VNF類型用集合P表示。每種VNF類型p都有特定的部署成本、CPU需求、處理延遲，分別表示為Dp,。具有SFC要求的多播流請求MRi表示為

si和Di分別表示源節點和目的節點集，SCi={SCi(1),SCi(2),...,SCi(l)}表示MRi中每個源目的對必須升序遍歷的VNF 集合，即SFC，l=|SCi|為SFC的長度，即MRi中每個源目的對需要經過的VNF實例總數。其中分別表示帶寬需求、CPU需求、任意源目的對節點的最大容忍延遲和最大容忍抖動。

2.3 問題定義

在SDN/NFV中，延遲和抖動感知的多播服務功能樹動態嵌入和路由問題(DJA-DSRP) 是為MRi尋找或構建一顆多播樹SFT，滿足各鏈路帶寬，流表容量和CPU資源約束的同時，任何一條源目的節點對的端到端延遲和任意源目的對路徑之間的最大時延抖動分別不大于給定的閾值和，且多播樹的實現代價最小并可以自動保證網絡的負載均衡。

2.4 問題刻畫

2.4.1 物理網絡轉換

在實際網絡中，各功能節點允許部署的VNF類型可能不同。為了方便地表達這個約束并降低問題的復雜性，將通過枚舉的方式將原來的物理網絡轉換成一個擴展的偽網絡。即根據一種類型的VNFp的CPU需求和功能節點的CPU容量，列舉所有可以部署在每個功能節點Nf上的VNF。這些枚舉的VNF稱為偽VNF，它們的集合記作M。用m ∈M表示第m個VNF，用表示路由MRi時，第m個VNF上剩余CPU的比率。假如VNF m的類型為p時，定義函數τ(m)返回VNFm的類型

2.4.2 相對成本的定義

G中資源使用的一個重要特征是，邊際成本會隨著資源負載的增加而非線性膨脹。比如，與輕負載鏈路相比，重負載鏈路將花費更多的成本來處理傳入的網絡數據包[2]。為了描述這一特性且自動保證網絡資源負載均衡，利用相對成本來刻畫資源的使用成本并將鏈路帶寬、交換節點和VNF上CPU資源的相對代價分別定義為

其中，ωbw,ωft和ωcpu均為大于1的常數，和分別為鏈路上帶寬資源、交換節點上流表資源和VNF上CPU資源的剩余率。

2.4.3 ILP模型

確保在部署新的VNF實例m時不會違反CPU容量限制，則需滿足

值得注意的是，每個源目的對必須由SFT中的一個SFC服務。由于多播的多路復用特性，流在到達目的節點前可能經過相同的VNF 實例。因此，使用式(12)來保證面向每個目的節點的流只訪問SFT中同類型的VNF 1次。

此外，為確保MRi中任意源目的地對不違反最大時延抖動，需滿足

綜上，構建多播樹的成本計算為

優化問題為

3 啟發式優化算法

由于在網絡中嵌入多播服務功能樹是NP難的[13]，為降低問題求解復雜度，將功能節點中的CPU資源消耗和轉發節點中流表資源消耗轉化為邊上的權值進行表示。因此，本節將G轉化為輔助邊權圖，然后再將轉換為具有相對成本的VNF分裂多階段邊權圖，最后基于利用啟發式算法對問題進行求解，具體過程如下。

3.1 輔助邊權圖構建

3.2 多階段邊權圖構建

3.3 啟發式算法SFT-EA

基于以下思路設計服務功能樹嵌入算法(Service Function Tree Embedding Algorithm, SFTEA)來解決式(24)。定義ΔT ∈R+為實際多播樹Ti中源目的對路徑的最大延遲，即

顯然，

此外，如果u?∈Di，稱u?為目的節點；如果u?∈/Di，但∈Ti，則稱u?為中繼節點。

顯然，

根據式(27)、 式(28)可以得到

SFT-EA的主要思想是在ΔT的范圍內從小到大取值，將每一個值作為當前構造的多播樹中路徑的時延上限。算法首先初始化一棵只包含多播源節點的多播樹，然后逐個貪婪地加入中的節點。在節點加入的過程中，使用式(31)中定義的最佳鏈路選擇函數來選擇具有最小值的節點v?，并將該節點對應的邊添加到當前多播樹Ti中，然后，將v?作為當前節點，重復上述過程。如果找不到符合條件的節點v?，則回溯到當前節點的父節點并繼續上述過程。最后，若在ΔT時延范圍內找不到包含所有目的節點的多播樹，則多播樹構造失敗，結束算法。

SFT-EA算法的偽代碼如算法1：

定理1SFT-EA的時間復雜度為O(K|N|3)。

證明 執行SFT-EA時，枚舉VNF的時間復雜度為O(|Vf|)。計算G′中鏈路和節點的相對成本的復雜度為O(|Vs|+|M|+|L|)。最壞情況下，所有類型的VNF實例都可以部署在每個功能節點上，將執行|Vf|+(l-1)|Vf|2+|Vf||Di|次SP算法為G?生成鏈路，通常是Vf ＜＜Di，因此執行SP算法的次數約為|Vf||Di|。G′上SP的復雜度為O(|L|+|V|log|V|)，最多有2l|Vf|+1+Di個節點和(l-1)|Vf|2+l|Vf|+|Vf|+|Vf||Di|條鏈路，因此，建立G?的時間復雜度是：O(|Vf||Di|(|(l-1)|Vf|2+l|Vf|+|Vf|+|Vf||Di|||+|(2l|Vf|+1+Di)|log2|(2l|Vf|+1+Di)|))=O(|Vf|2|Di|2+|Di|2|Vf|log2|Di|)。KruskalMST計算TLDT的復雜度為O(V2)=O((2l|Vf|+1+Di)2)=O(Di2)，在算法中(第10～27行)，當沒有回溯時，時間復雜度為O(V2)，當有回溯時，時間復雜度為O(V3)。用于確定是否訪問了所有目的地節點的時間復雜度為O(Di)(第30～34行)，在最壞情況下，SFT-EA將迭代K次，路徑映射和資源更新的復雜度為O(1)。l的值很小。因此，SFT-EA的算法復雜度是O(K((|Vf|)+(|Vs|+|M|+|L|)+(|Vf|2|Di|2+|Di|2|Vf||log2|Di|)=O(K|Di|3)。在最壞的情況下，網絡中除源節點外的所有節點都是多播目的節點，所以，SFT-EA的復雜度為O(K|N|3)。 證畢

圖4中的紅色粗線給出了具有3個目的節點和3個VNF順序請求SFT的算法運行示例。

圖4 在圖 G?i 中解決DJA-DSPR

4 性能仿真分析

4.1 仿真設置

在Intel(R) Core(TM) i7-8550U CPU @ 1.80 GHz, 32.0 GB RAM的計算機上，用NetworkX3.1 Library[20]生成 Palmethone網絡[21]對提出的算法進行評估。網絡中，選擇按節點度降序排序的30%的節點作為功能節點?？紤]6種類型的VNFS[2]。Dp的取值為Uniform[0,10]×。每條鏈路的帶寬(Gbps)為Uniform[1,10]。交換節點的流量表容量設置為800個單元[2]，功能節點上的CPU容量設置為8000MIPS。(ms)設為Uniform[0.002,0.003]×，鏈路的延遲(ms)為Uniform[2,5][2]。wbw,wft,wcpu設置為2|V|[11]。

對于每條多播流，從目標網絡中隨機選擇源節點和目的節點。為了評估多播規模的影響，將|D|/|V|值設置為0.3，(Mbps)為Uniform[10,120][13]。(MIPS)為Uniform[0,10] ×，為Uniform [50,100]，(ms)為Uniform[30,50][2]。此外，將SFC的長度和SFT-EA的迭代最大次數K分別設置為4和10。取30次實驗結果的平均值作為結果輸出。

算法1 SFT-EA算法

4.2 對比算法

選用SDN/NFV網絡架構中與本文研究方向緊密相關且最新的對比算法進行仿真對比。

(1)STB[22]：用傳統經典的Steiner樹算法構造一個覆蓋多播所有目的節點的Steiner樹，并找到將源節點連接到該樹的最小代價路徑。然后沿著該路徑嵌入所需的SFC。STB只考慮鏈路和節點資源的成本；

(2)TSA[13]：通過考慮鏈路和節點資源成本得到SFC嵌入的初始方案，然后通過添加新的VNF實例逐步構建多播服務功能樹(SFT)，該算法不考慮流表成本及路徑抖動約束；

(3)HAJPR[16]：根據網絡中的關鍵NFV節點構造多徑多播樹，并且考慮物理資源和延遲約束，不考慮抖動約束，且沒有解決VNF的動態嵌入。

4.3 性能比較

圖5為平均流接受率的比較。SFT-EA的性能最好。當傳入MRs的數量為5 000時，它接受的MR比HAJPR多約6%，比TSA高約13%，比STB高約17%。在SFT-EA中，實現了VNF的動態放置和負載均衡，提供了更好的性能。HAJPR考慮多路徑路由，其性能優于TSA和STB。

圖5 平均流接受率

圖6展示了平均吞吐量的比較。當MR的數量為4 000時，SFT-EA的吞吐量比HAJPR高約5 Gbps，比TSA高約14 Gbps，比STB高約20 Gbps。性能和流接受率相符。

圖6 平均吞吐量

圖7展示了當4 000條MRs進入網絡時鏈路平均剩余帶寬的累積分布。從圖中可看出，STB和TSA有大約5%和3%的瓶頸鏈路。對于SFT-EA，剩余帶寬為6G和3G的鏈路分別約占71%和17%，因此，網絡中約有54%的鏈路剩余帶寬在3 Gbps到6 Gbps之間，對于HAJPR, TSA和STB，其剩余帶寬在3 Gbps到6 Gbps之間的鏈路分別約為51%、32%和27%。顯然，SFT-EA中使用指數函數來表示鏈路帶寬成本，使其對鏈路資源的利用比其他算法更加均衡。

圖7 剩余帶寬累積分布

圖8描述了4 000條MRs進入網絡時平均剩余流表條目的累積分布?？梢钥吹?，TSA和STB有大約3%和5%的交換節點瓶頸。從圖中剩余流表條目為400個單位看，STB大約有60%的交換機節點，其剩余流表條目小于400個單位，TSA為49%，HAJPR為35%，SFT-EA為30%， SFT-EA算法的性能優于其他算法。

圖8 剩余流表累積分布

圖9顯示了當4 000條MRs進入網絡時，功能節點上平均剩余CPU的累積分布。由于STB和TSA不能保證功能節點上CPU的均衡使用，分別有約4%和2%的瓶頸節點。對于SFT-EA，剩余CPU為1 600 MIP的功能節點大約占10%，剩余CPU為4 000 MIPS的功能節點大約占85%，因此，約75%的功能節點的剩余CPU在1 600～4 000 MIPS，而HAJPR,TSA和STB在這區間的剩余CPU分別約為63%、49%和45%。SFT-EA比其他算法更均衡。

圖9 剩余CPU的累積分布

圖10展示了不同長度SFC下流接受率的變化。由于MR消耗的網絡資源隨著SFC長度的增加而增加，因此，流接受率隨SFC長度的增加而降低。因STB和TSA無法平衡帶寬、流表和CPU資源的利用率，因此它們的性能較差。雖然HAJPR不考慮資源平衡，但由于采用多徑路由，且不考慮時延抖動約束，因此性能略高于SFT-EA。

圖10 平均流接受率隨SFC長度的變化

圖11顯示了不同比例功能節點下網絡的平均流接受率。功能節點的比例越高，可以動態部署VNF實例的節點就越多，MR可以選擇冗余的VNF實例來滿足其預定順序，因此，這些算法的平均流接受率就越高。同理，雖然HAJPR不考慮資源平衡，但由于采用多徑路由，且不考慮時延抖動約束，因此性能略高于SFT-EA。

圖11 不同功能節點數下的平均流接受率

圖12給出了多播目的節點數|D|∈[5,25]時，算法的運行時間比較，隨著多播目的節點數的增加，4種算法的執行時間都會增加。因SFT-EA需要考慮抖動約束，算法運行時間約高于HAJPR。

圖12 不同目的節點數下算法的執行時間

5 結束語

本文基于SDN/NFV架構，研究了延遲和抖動感知的多播服務功能樹嵌入和路由問題。首先將其建模為ILP模型。然后，利用節點分裂，將節點資源成本轉換為邊的思想，并設計了一個最優鏈路選擇函數和基于輔助邊權圖的SFT嵌入算法SFT-EA來解決該問題。最后通過實驗仿真對算法的性能進行了評價。結果表明，所提算法在吞吐量、流接受率和網絡負載均衡方面比現有算法有更好的性能，為虛擬網絡環境下具有延遲和抖動約束的多播流調度提供了有價值的參考。