多源多播服務功能鏈優化部署算法

收稿日期：2021-11-15；修回日期：2022-01-05

基金項目：國家自然科學基金資助項目（61907036，51905457）；南充市市校合作項目（19SXHZ0018）

作者簡介：任誠（1981-），女（通信作者），四川南充人，副教授，碩導，博士，主要研究方向為智慧網絡、機器視覺（rencheng@swpu.edu.cn）；陳緒祥（1994-），男，四川達州人，碩士研究生，主要研究方向為網絡資源優化、機器學習；唐斌文（1972-），男，四川南充人，副教授，主要研究方向為電路與系統；王宇（1988-），女，新疆烏魯木齊人，副教授，碩導，博士，主要研究方向為仿生機器人、人工智能；李豪（1996-），男，四川德陽人，碩士研究生，主要研究方向為網絡資源部署、機器學習.

摘 要：在軟件定義網絡和網絡功能虛擬化環境下，針對多播中的服務功能鏈（SFC）部署，探究了多源多播中的聯合虛擬網絡功能（VNF）部署和流量路由問題，目的是最小化節點資源消耗和鏈路資源消耗總成本。同時考慮到節點、鏈路及帶寬延遲限制，建立了整數線性規劃模型，并提出一種名為多源多播樹優化的啟發式算法。該算法旨在為所有用戶找到最近的源節點，獲得多個源、目節點組，為每個組構造一棵多播服務功能樹，然后優化多播服務功能樹。實驗仿真結果表明，與其他啟發式算法相比，該算法有效地降低了總成本、鏈路利用率及時延。

關鍵詞：軟件定義網絡； 網絡功能虛擬化； 服務功能鏈； 多源多播； 時延

中圖分類號：TP301.6"" 文獻標志碼：A

文章編號：1001-3695（2022）06-036-1814-06

doi：10.19734/j.issn.1001-3695.2021.11.0615

Multi-source multicast service function chain optimization deployment algorithm

Ren Cheng1，2， Chen Xuxiang1， Tang Binwen3， Wang Yu1， Li Hao1

（1.School of Electrical Engineering amp; Information， Southwest Petroleum University， Chengdu 610500， China; 2.School of Information amp; Communication Engineering， University of Electronic Science amp; Technology of China， Chengdu 611731， China; 3.School of Information， Southwest Petroleum University， Nanchong Sichuan 637001， China）

Abstract：In the software defined network and network function virtualization environment， for the deployment of service function chain in multicast， this paper explored the deployment of joint virtual network function and traffic routing in multi-source multicast. The purpose was to minimize the total node resource consumption and link resource consumption cost. At the same time， considering the node， link and bandwidth delay constraints， it established an integer linear programming model and proposed a heuristic algorithm called multi-source multicast tree optimization. The algorithm aimed to find the nearest source node for all users， obtained multiple source and destination node groups， constructed a multicast service function tree for each group， and then optimized the multicast service function tree. Experimental simulation results show that compared with other heuristic algorithms， this algorithm effectively reduces the total cost， link utilization and delay.

Key words：software defined network（SDN）; network function virtualization（NFV）; service function chain; multi-source multicast; delay

0 引言

近年來，隨著互聯網技術的廣泛應用，網絡功能虛擬化（NFV）和軟件定義網絡（SDN）的出現使得通信網絡的管理和設計方式發生了根本性的變化。通過NFV技術，將網絡功能（network function，NF）軟件部署到通用服務器上，取代了傳統硬件網絡中的中間盒設備，將網絡功能與硬件設備解耦，從而降低部署成本，使網絡具有可擴展性和靈活性［1］。其中，這種軟件化的網絡中間盒，如防火墻（firewall）、網絡地址轉換（NAT）、入侵檢測系統（IDS）或路由器等，都被稱為虛擬網絡功能（virtua-lized network function，VNF） ［2］。NFV在SDN技術的支持下，網絡資源能夠實現按需分配和靈活調控，從源到目的節點的請求流，依次被一定順序的不同網絡功能處理，從而形成一條服務功能鏈（service function chain，SFC）［3］。如何靈活嵌入SFC，對網絡的延遲、建設成本和運維開銷都有很大的影響。

單播僅是一個源和一個目的地之間的通信，而多播是將相同的數據從源傳遞到一組目的地的通信［4］。如今，多播在網絡技術中的需求大幅增長，如網上視頻會議、媒體廣播、多人游戲、分布式交互模擬等都是多播性質服務。據估計，82%的消費者的互聯網流量將歸因于視頻流媒體［5］，這清楚地顯示了從點對點（單播）通信到點對多點和多點對多點通信（多播）的趨勢轉變。目前為止，單播服務的VNF部署和流量路由問題已經得到了廣泛的研究［6］，關于多播服務的聯合VNF部署和多播路由的工作相對較少［7］。與單播通信相比，多播通信模式可以避免單播路徑的重復傳輸，從而顯著降低網絡中的帶寬利用率。

相比單播SFC的嵌入，在多播網絡中嵌入SFC更具挑戰性。在多播服務中，如果僅使用一對一單播服務中的VNF部署和路由策略，VNF的部署和路由路徑將會重復，這將導致巨額的服務成本；若SFC嵌入位置離源近而離目的地遠，這將會構造一棵大的服務功能樹，從而導致更高的鏈路成本；若將VNF功能實例部署在多個NFV節點中，可能會降低鏈路配置成本，但會增加功能配置成本。因此，需要平衡鏈路成本和VNF部署成本。另一個主要的挑戰是，在節點和鏈路資源有限的同一個基層網絡中，如何嵌入多個多播請求以最小化總成本。

文獻［8］設計了一種最小成本多播服務功能樹（MC-MSFT）的算法，提出分級的路徑分割技術，構建多播SFC樹及優化請求資源分配問題，但并沒有考慮SFC的特定順序。文獻［9］提出了一種基于斯坦納樹的方法，目的是最小化VNF部署和路由的成本。文獻［10］研究了多播服務的聯合VNF放置和拓撲路由，提出一種具有近似因子為2的算法，并假設在網絡拓撲中部署VNF后，多播復制點才會發生，這使得路由的靈活性降低。文獻［11］研究SDN中啟用NFV的多播技術，目的是最大化網絡吞吐量，假設用于實現每個請求的服務鏈的服務器數量不大于一個常數，提出了兩種在線近似算法，該算法將所有VNF部署在同一個服務器節點中，可能會造成更多的鏈路配置成本。文獻［12］以降低流量傳輸成本為目標，在多播任務網絡中嵌入最優服務功能樹，提出了一個兩階段算法（TSA），該模型支持在分散的網絡節點上放置一個多播樹的VNF。文獻［13］考慮單服務和多服務場景，以最小的配置成本和最大化總吞吐量為優化目標，研究了聯合多路徑多播路由和VNF放置。文獻［14］研究了多播VNF部署和路由優化問題，將所有VNF放置在單個服務器中。文獻［15］提出一種基于多服務路徑（MSC-M）的多播服務鏈VNF-PR模型，即使服務請求不同，該模型也允許將攜帶相同數據的部分路徑合并為一條路徑。文獻［16］將NFV啟用的多播服務鏈的最優嵌入問題表述為一個混合二進制線性程序，然后為在合理的時間內解決這個問題，使用了基于懲罰的連續上界最小化算法。

關于多源多播的研究，文獻［17］提出服務覆蓋森林（SOF），以最小化森林中所有分配的VNF和所有多播樹的總成本，設計出一種近似算法來解決該問題，但該方法僅考慮每個NFV節點放置一個VNF。文獻［18］設計了一個多源多播樹構造（MMTC）的啟發式算法，雖然考慮了帶寬和延遲的限制，但該算法旨在為所有目的地用戶找到一條公共鏈路，嵌入服務功能鏈（SFC），但在大型網絡中，由于目的地之間的鏈路成本，該方法不能保證成本最優。文獻［19］提出一個NFV多源多播資源優化模型，利用DW（Dantzig-Wolfe）分解模型，將其分解為一個主問題和幾個定價問題來優化問題，但優化目標僅是最大化請求接受率，并沒有考慮到成本優化問題。

綜上，當前研究的多數工作是限制所有目的地共享同一條SFC，這使得效率低下，且當目的地在地理上分散時，會造成一個巨大的鏈路成本；如果將所有類型的網絡功能實例部署在一個NFV節點中，會增加路由成本，一個有效的解決方案是復制或部署功能實例在多個NFV節點中，以減少由于靈活路由導致的鏈路成本。在多播的NFV中，多源多播（多點對多點）通信的研究很少，本文目標是在多播網絡中嵌入SFC，在多播請求時延約束下，最小化整體的節點和鏈路資源消耗成本。

本文研究了多個服務請求的多源多播資源優化問題。首先，針對VNF部署規則、傳輸資源約束及時延，從數學上表述和定義了聯合多播VNF部署及路由問題，設計了整數線性規劃（integer linear programming，ILP）模型。其次，考慮到嵌入SFC的ILP優化是NP難問題，為降低復雜性及運行時間，設計了一種多源多播樹優化啟發式算法來分解此模型，該算法充分利用多個源，根據源、目節點間的最短路徑距離，為每個目的節點找到一個最優的源，得到多個源、目節點組；通過復制NF實例，在每個源、目節點組中構造多播服務功能樹。然后，聯合優化VNF部署成本和路由成本，去除冗余節點及鏈路，優化多播樹，得到最優解，這使得在網絡VNF的放置和路由過程中有更高的靈活性、更高的效率和更低的成本。

1 網絡模型

1.1 基層網絡

本文將軟件定義物理基層網絡表示為無向圖G=（V，L），V表示網絡節點集合，V=Vs∪Vd∪Vm∪Vw。其中：Vs表示源節點集合，用于發出流量;Vd表示目的節點集合；Vm表示連接有計算服務器的節點集合，這些服務器節點作為NFV節點，可以部署各種網絡功能，節點計算資源總容量表示為Cu，只要節點資源容量足夠大，每個節點可以部署一個或多個 VNF；Vw表示普通交換機節點集合，交換機僅用于復制或轉發流量，因此它的節點容量為0。其余參數符號如表1所示。

1.2 服務功能鏈

假設F表示所有VNF類型的集合，fj∈F定義為一種特定的VNF，從F中選擇一些fj，按照特定順序連接，可以組成一條服務功能鏈SFC，即SFC fck=（f1，f2，…，f|k|），圖1為多播服務功能鏈的示例，從源s1發出的數據包必須依次經過服務功能鏈到達目的節點d1、d2。假設每個Vm支持F中的所有類型的VNF，并且可以運行多個VNF。第k個多播服務請求rk∈R表示為rk={sk，dk，fck，tk}，其余參數符號如表1所示。

1.3 相關變量

在第k個多播請求中，對流向目的節點d∈dk的數據流量，若經過VNF fj到VNF fj+1路徑中的鏈路lu，v，則ξk，dfj，u，v=1，否則為0；對第k個多播請求，用χkfj，u，v表示鏈路lu，v是否在多播服務功能樹中從VNF fj到VNF fj+1的路徑上，如果在VNF fj到VNF fj+1的路徑上，χkfj，u，v=1，否則為0。對第k個多播請求的目的節點d∈dk，VNF實例fj新部署在服務器節點u上，θk，dfj，u=1，否則為0；同理，若請求集R中的VNF fj新部署在NFV節點u上，λfj，u=1，否則為0。

2 整數線性規劃模型

針對多個服務請求的多源多播資源優化問題，本文設計了多源多播整數線性規劃（multi-source multicast integer linear programming，MSMILP）模型，該模型綜合考慮了網絡中節點資源、鏈路資源、路由流量關系及多播時延需求等情況，找到服務功能鏈的最優嵌入位置，最小化網絡中的節點計算資源和鏈路帶寬資源消耗成本，其優化目標函數表示為

min{α1∑u∈Vm∑fj∈Fλfj，uσfj，u+α2∑rk∈R∑u，v∈V∑d∈dk∑fj∈fck′ξk，dfj，u，vbk}（1）

其中：第一部分表示所有NFV的節點計算資源消耗成本；第二部分是所有多播請求通過鏈路的帶寬消耗成本；αi（i=1，2）為兩部分的平衡因子。目標公式約束如下：

對于每個NFV節點，分配給VNF的可用資源應不超過其節點容量，應滿足式（2）節點資源約束。式（3）表示每條鏈路的使用資源不超過其鏈路容量。

∑fj∈Fλfj，uδfj≤Cu u∈Vm（2）

∑rk∈R∑u，v∈V∑fj∈fc′kχkfj，u，vbk≤Cu，v u，v∈V（3）

將f0作為fck′中源節點的網絡功能，除源節點外，其他節點都不能獲取f0的服務，對每個目的節點d，多個源節點中僅有一個源節點能獲得f0的服務，則有式（4）。式（5）表示一個fj僅能部署在一個NFV節點上，不能被多個NFV節點共享。

∑u∈skθk，df0，u=1 rk∈R，d∈dk（4）

∑u∈Vmθk，dfj，u=1 rk∈R，fj∈fc′k，d∈dk（5）

網絡中的多播請求流量必須遵循流量守恒，即每個節點中流出的流量等于流入的流量，且需保證SFC的順序要求，則有

∑v∈Nuξk，dfj，u，v－∑v∈Nuξk，dfj，v，u=θk，dfj，u－θk，dfj+1，urk∈R，fj∈fc′k，d∈dk，u∈V（6）

此外，多播請求流量還需滿足約束式（7），對目的節點d∈dk，如果ξk，dfj，u，v=1，則χkfj，u，v=1。

ξk，dfj，u，v≤χkfj，u，v rk∈R，fj∈fc′k，d∈dk（7）

考慮到多播請求的服務質量（quality of service，QoS），式（8）保證每個請求需滿足端到端的時延約束，式（9）表示每個多播請求中所有目的地之間的時延誤差不超過πk。

∑u，v∈V∑fj∈fc′kξk，dfj，u，vu，v≤tk d∈dk，rk∈R（8）

|∑u，v∈V∑fj∈fc′kξk，dmfj，u，vu，v－∑u，v∈V∑fj∈fc′kξk，dnfj，u，vu，v|≤πkdm，dn∈dk，rk∈R（9）

3 啟發式算法描述與分析

雖然多源多播資源優化問題可以通過第2章中的ILP公式進行最優求解，但其有較高的復雜性。因此，本文設計了一種兩階段的多源多播樹優化（multi-source multicast tree optimization，MSMTO）啟發式算法，該算法主要分為兩步：

a）構造多播服務功能樹階段，首先在單個多播請求中，為每個目的節點選擇一個合適的源節點，將源節點相同的目的節點分成一組；其次為每組源、目節點嵌入SFC，構造一棵最小成本的斯坦納樹，獲得每個多播請求的多播服務功能樹。算法1描述了此過程。

b）優化多播樹階段，算法2聯合優化VNF部署成本和鏈路成本，將每個多播請求在第一階段得到的多播樹進行優化，最終得到所有多播請求的最小成本服務功能樹。

3.1 構造多播樹

3.1.1 為每個目的節點尋找最優源

算法1為每個多播請求rk構造多播樹。

算法1 多播服務功能樹建立算法

輸入：底層網絡G=（V，L）；多播請求集R；rk={sk，dk，fck，tk}。

輸出：R所有的最小成本多播樹。

1 將rk∈Rn按流量需求，從小到大排序，得到Rn；

2 for rk∈Rn

3" 目的節點集Mkm，源節點集Ok；

4" 在G中，為每個源sm∈sk和dk構造最小生成樹Tm；

5" 在Tm中分別計算sm到所有dk的最短距離，將離目的節點di∈dk近的源sm作為di的源；

6" 將含有相同源sm∈sk的所有目的節點di∈dk添加至Mkm中，同時將源sm添加至Ok中；

7" for sm∈Ok

8"" 令s0=sm；

9"" for h∈fck

10""" 獲得能夠新部署VNF h且離s0成本C1最小的節點u=Vm和已經部署VNF h且離s0成本C2最小的節點v=Vm；

11""" if 式（10）條件成立then

12"""" 由式（11）獲得部署VNF h的節點nh；

13"""" 令s0=nh；

14""" else

15"""" 選擇C1、C2中最小值的節點位置nh；

16"""" 令s0=nh；

17" end for

18" 依次連接源節點sm到fck［－1］的節點位置；

19" 在G中，包含fck［－1］的節點位置和Mkm構造斯坦納樹Hkm；

20 end for

21 end for

22 return R所有的最小成本多播樹

算法第1～6行給出了為每個目的節點尋找最優源的詳細描述。為方便理解，構造如圖2（a）的物理基層網絡G=（V1，L1），網絡中三角形表示源節點，圓圈表示NFV節點，五邊形為普通交換機節點，正方形表示表目的節點。在基層網絡G中，首先，包含源節點s1與所有目的節點di（i=1，2，3）構造一棵最小生成樹T1，如圖2（b）所示，包含源節點s2和所有目的節點di（i=1，2，3）構造一棵最小生成樹T2，如圖2（c）所示，分別計算T1中s1到di（i=1，2，3）的最短路徑距離，T2中s2到di（i=1，2，3）的最短路徑距離，若di離s1近，則認為s1為di的源節點，否則，分別計算T1中s1到di（i=1，2，3）的最短路徑距離，T2中s2到di（i=1，2，3）的最短路徑距離，若di離s1近，則認為s1為di的源節點，否則，s2為di的源節點。找到每個目的節點的源節點后，將含有相同源的目的節點分成一組，將相應源存入集合Ok中、目節點存入集合Mkm中。然后，為每組源、目節點構造多播服務功能樹，值得注意，每個目的節點僅屬于一棵多播樹。

3.1.2 為多播請求構造服務功能樹

算法1第7～18行為每棵多播樹嵌入最優SFC過程。首先，沿著成本最小的路徑，找到合適的NFV節點依次放置SFC的VNF實例，假設每個VNF實例可以被多條SFC共享。第7～10行，描述了為SFC選擇最優的NFV節點，當為每個VNF h選擇部署節點時，分兩種情況：a）選擇距離上一NFV節點s0的成本C1最小的節點u∈Vm，且節點u中沒有部署VNF h或已經部署的VNF h中沒有剩余的流處理資源，這時需重新部署VNF h，其成本C1=Ps0，u+Chd，u，其中Ps0，u是s0到節點u的最短路徑成本、Chd，u表示VNF h在節點u上的部署成本；b）選擇距離上一NFV節點s0的成本C2最小的節點v∈Vm，如果節點v中已經部署有VNF h，且VNF h中剩余的流處理資源足夠，則無須重新部署VNF h，直接使用已有的VNF h，這時VNF h在節點u上的部署成本為0，只有s0到節點v的最短路徑成本Ps0，v，其成本C2=Ps0，v。第11～17行，如果C1+C2的值滿足下列條件：

C1+C2≥min{C1+Pu，v，C2+Pu，v}（10）

其中：Pu，v表示節點u到節點v的最短路徑成本，這時VNF h的節點位置選擇為nh。

nh=argminu，v{C1+Pu，v，C2+Pu，v}（11）

若式（10）不成立，直接選擇C1、C2中最小值的節點位置。第18行，依次連接源節點sm到fck中最后一個VNF的節點位置，即獲得SFC的最優嵌入位置。第19行，在G中包含最后一個VNF節點位置與相應目的節點集Mkm，構造一棵斯坦納樹Hkm，即獲得得到一棵成本最小的多播服務功能樹Tkm。

3.2 多播服務功能樹優化

算法2為多播服務功能樹優化的過程。

算法2 服務功能多播樹優化算法

輸入：底層網絡G=（V，L）;多播請求集R;rk={sk，dk，fck，tk}。

輸出：R的所有多播服務功能樹。

1 運行算法1，獲得每個多播請求服務功能樹Tkm、源節點集Ok；

2 for rk∈R

3" for sm∈Ok

4"" for sj∈Ok，m≠j

5""" 令n=|fck|；

6""" while n≥1

7"""" if 式（14）條件成立then

8"""" if式（15） 獲得的源節點se為源sm then

9""""" 刪除多播樹Tkj中sj到其第n個VNF的路徑、VNF實例及相應節點，從Ok中移除sj；

10"""""" 連接Tkm中第n個VNF與Tkj中第n個VNF的節點；

11""""" else

12"""""" 刪除多播樹Tkm中sm到其第n個VNF的路徑、VNF實例及相應節點，從Ok中移除sm；

13"""""" 連接Tkm中第n個VNF與Tkj中第n個VNF的節點；

14"""""" n=n－1；

15""" end while

16"" end for

17" end for

18 end for

19 return R的所有多播服務功能樹

由算法1獲得了每個多播請求的源節點集Ok和多播服務功能樹，算法2第1～7行為確定多播樹Tkm和Tkj的優化位置。首先，計算多播樹Tkm中的成本C3，即

C3=Mnsm+∑q=1，…，nHqkm（12）

其中：Mnsm表示在多播樹Tkm中，源sm到服務功能鏈fck的第n個VNF的鏈路成本；Hqkm為多播樹Tkm中，fck的第q個VNF的部署成本；令C4為另一顆多播樹Tkj中相應的成本之和，即

C4=Mnsj+∑q=1，…，nHqkj（13）

值得注意的是，兩棵多播樹間優化時，應首先從最后一個VNF依次往前檢查是否可優化，且需滿足下列條件：

C3+C4≥min{C3+P（Tnkm，Tnkj），C4+P（Tnkm，Tnkj）}（14）

其中：P（Tnkm，Tnkj）表示多播服務功能樹Tkm的第n個VNF到多播服務功能樹Tkj的第n個VNF的路徑成本。第8行，若式（14）成立，則允許優化多播樹Tkm和Tkj，優化后新的源節點se選取規則如下：

se=argminsm，sj{C3+P（Tqkm，Tqkj），C4+P（Tqkm，Tqkj）}（15）

第8～10行，若式（15）獲得的源節點se為多播樹Tkm中的源節點sm，則刪除多播樹Tkj中sj到其第n個VNF的路徑、VNF實例及相應節點，連接Tkm中第n個VNF與Tkj中第n個VNF的節點位置，獲得一棵優化后完整的多播樹。第11～13行，若式（15）獲得的源節點se為多播樹Tkj中的源節點sj，去除Tkm中相應路徑、VNF實例及節點，獲得相應多播樹。

圖3為優化多播樹的一個例子，若圖3（a）為第一階段獲得的兩棵多播服務功能樹Tk1和Tk2，SFC fc2=（f1，f2，f3），首先檢查最后一個VNF f3是否滿足優化條件，若不滿足式（14），則認為兩棵多播樹不能在VNF f3處優化，這時依次往前尋找滿足條件的VNF。如果VNF f2滿足條件式（14），假如這時由式（15）得到的源節點為多播樹Tk1中的s1，則刪除Tk2中s2到VNF f2的路徑、VNF實例及節點，僅保留節點8及之后的路徑，并將節點8連接至Tk1中的節點2，這時Tk2中的目的節點與Tk1共享VNF f1和f2，獲得的多播服務功能樹如圖3（b）所示。

3.3 時延保證

通過算法1和2獲得每個多播請求的一棵或多棵多播服務功能樹后，需計算每個多播請求的時延，確定是否滿足時延需求tk；且每個多播請求的所有用戶之間的時延誤差不能超過一個確定值πk，否則該請求將被拒絕。

3.4 算法時間復雜性理論分析

首先，算法1第3～6行，為每個目的節點尋找合適的源節點，得到相應的源、目節點組，在這個過程中需要構造一棵最小生成樹，時間復雜度為O（（1+|dk|）2）。然后，為其構建多播服務功能樹時，需在原始網絡G中構造一棵斯坦納樹來找到最優的路由路徑，其時間復雜度為O（（1+|dk|）×|V|2）［20］。第7～19行，在最壞的情況下，時間復雜度為O（Ok×（1+|dk|）×|V|2），所以，算法1的時間復雜度為O（|Rn|×|Ok|×（1+|dk|）×|V|2）。其次，算法2的時間復雜度為O（|R|×|Ok|×||Ok|－1|×|n|），因此，啟發式算法總時間復雜度為算法1和2的總和。

4 仿真實驗與性能分析

4.1 實驗環境和參數設置

本實驗在Windows系統的PC機上運行，CPU型號為Intel Core i7 3.0 Ghz、內存為32 GB。網絡拓撲為合成網絡和現實世界的網絡Europe［21］，合成網絡有19個節點，24條鏈路，記為H， Europe網絡包含33個節點，48條鏈路，記為Q。評估了多播請求數量、目的節點數量、SFC的長度（VNF的數量）和源節點數量的變化，對總成本、鏈路利用率和總時延的影響。在同一參數下，所有指標通過10輪訓練得出平均結果。其余參數設置如下：

式（1）優化目標中的平衡因子αi（i=1，2）均設置為1，假設每個節點總資源容量為3 000 Mbps，鏈路容量設置為［1 000，2 000］" Mbps的隨機分布，鏈路和節點資源的單位成本均為1，部署1個VNF需要的資源為100 Mbps。假設網絡服務中的每一個服務器節點支持多個VNF實例，且支持所有類型的VNF；集合F中包含七種類型的VNF，每種VNF的部署成本分別為{10，20，30，40，30，20，10}。每條SFC的排列順序、VNF數量隨機生成，所有源節點、目的節點均隨機生成。每條流的大小服從均值為20，標準差為4的正態分布，每條邊的時延從［15，50］隨機選擇，每個多播請求的總時延需求滿足均值為400，標準差為8的正態分布。

4.2 仿真結果分析

為評估算法性能，將本文提出的MSMILP、多源多播樹優化算法MSMTO與服務覆蓋森林部署算法（SOFDA）［17］、多源多播樹構建（MMTC）算法［18］進行比較，此外，將設計的另一種多源多播算法作為對照算法，該算法在多個源節點中隨機選擇一個源節點，且遵循算法1的VNF部署規則，然后構造一棵斯坦納樹的方式，記為MSMTO-R。

4.2.1 總成本變化

為觀察多播請求總成本的變化，實驗中依次改變了目的節點數量、源節點數量、SFC長度及多播請求數量。當目的節點數量在［2，7］變化，源節點數量在［1，6］變化，服務功鏈長度在［2，7］變化，多播請求數量在［10，40］變化時，多播請求的其余參數分別如表2中的序號第1～4列（后文所有多播請求參數設置均參照表2）。

圖4為在兩種拓撲圖H、Q中，總成本的仿真結果，由圖4（a）（b）可以看出，當目的節點數量增加時，五種算法的總成本有不斷增加的趨勢，這是因為隨著目的節點數量的增加，需要的鏈路和VNF實例數也相應增加。然而，隨著源節點數的增加，MSMILP和MSMTO算法成本有下降的趨勢，而MMTC和MSMTO-R保持穩定，因為本文算法充分利用多個源節點的優勢，為每個目的地找到一個最近的源，獲得最佳路由路徑，從而成本有所下降；MMTC和MSMTO-R所有目的節點僅使用一個源節點，因此，總成本不隨源節點數量的變化而改變。

圖4（c）（d）表明了總成本隨服務功能鏈和多播請求數量的增加而逐漸增加，且本文MSMTO算法優于對照算法，主要原因是在于，一方面，它將所有目的節點分成多個組，為每組找到一個最優的源節點，通過復制VNF實例，構建了多棵多播樹，在構造多播樹及優化多播樹的過程中都綜合考慮了節點和鏈路成本優化，最終得到一棵最優多播樹。而MMTC僅考慮鏈路資源優化，而不是聯合優化所有資源分配，SOFDA僅考慮每個NFV節點放置一個VNF實例，會增加VNF部署成本。另一方面，當新嵌入服務功能鏈時，如果網絡拓撲中已經部署有某種VNF，且該VNF的剩余處理資源足夠，那么會直接使用該VNF，而不會重復部署一個新的VNF，這極大降低了VNF的部署成本。

4.2.2 鏈路利用率和時延變化

在網絡撲圖H和Q中，平均鏈路利用率及每個多播請求的平均總時延隨目的節點數量和源節點數量增加時，變化趨勢如圖5（a）～（d）所示，當目的節點數量增加時，多播樹中使用的鏈路增多，因此，五種算法的鏈路利用率和平均時延都相應增加；當源節點數量增加時，MSMILP和MSMTO算法的鏈路利用率和時延有下降的趨勢，而MMTC、SOFDA和MSMTO-R則趨于穩定，這是因為MSMILP和MSMTO充分利用多個源節點的優勢，為每個用戶找到最近的一個源節點，避免構造更大的多播樹，從而減少了鏈路的使用。圖5（e）（f）隨著服務功能鏈長度的增加，五種算法的鏈路利用率有輕微的上升，其中SOFDA算法相對較高且明顯，因為它僅考慮每個NFV節點部署一個VNF實例，VNF實例數增加時，鏈路使用增加。此外，鏈路利用率隨多播請求數的增加而增加，由于VNF的實例數增多，鏈路資源使用也相應增加。

5 結束語

本文探討了在多源多播中嵌入服務功能鏈的資源優化問題，為平衡節點和鏈路之間的總成本，同時考慮到節點資源、鏈路資源的利用率及時延，利用整數線性規劃定義和優化了多個服務請求的模型。由于ILP方法的復雜性，本文設計了一種低復雜度的兩階段啟發式算法，該算法充分利用多個源，將源節點和目的用戶分成多個源、目節點組，為每個組構造一棵多播服務功能樹，然后，再優化其多播服務功能樹。最后，分析了啟發式算法的復雜性，并通過仿真實驗評估了該算法。實驗結果表明，該方法在總成本、鏈路利用率及時延方面，優于現有算法。任何軟件故障都會影響多播服務的穩定性，因此，下一步將研究SFC的可靠性，以及考慮多播請求的接受率。

參考文獻：

[1]祖家琛，胡谷雨，嚴佳潔，等.網絡功能虛擬化下服務功能鏈的資源管理研究綜述［J］.計算機研究與發展，2021，58（1）：137-152.（Zu Jiachen， Hu Guyu， Yan Jiajie， et al. Resource management of service function chain in NFV enabled network［J］.Journal of Computer Research and Development，2021，58（1）：137-152.）

［2]金明，李琳琳，張文瑾，等.基于深度強化學習的服務功能鏈映射算法［J］.計算機應用研究，2020，37（11）：3456-3460，3466.（Jin Ming， Li Linlin， Zhang Wenjin， et al. SFC mapping algorithm based on deep reinforcement learning［J］.Application Research of Computers，2020，37（11）：3456-3460，3466.）

［3]Bhamare D， Jain R， Samaka M， et al. A survey on service function chaining［J］.Journal of Network and Computer Applications，2016，75：138-155.

［4]Huang L H， Hsu H C， Shen S H， et al. Multicast traffic engineering for software-defined networks［C］//Proc of the 35th Annual IEEE International Conference on Computer Communications.Piscataway，NJ：IEEE Press，2016：1-9.

［5]Liu Lu， Hu Han， Luo Yong， et al. When wireless video streaming meets AI： a deep learning approach［J］.IEEE Wireless Communications，2020，27（2）：127-133.

［6]Zhang Ning， Yang Peng， Zhang Shan， et al. Software defined networking enabled wireless network virtualization： challenges and solutions［J］.IEEE Network，2017，31（5）：42-49.

［7]Alhussein O， Do P T， Li Junling， et al. Joint VNF placement and multicast traffic routing in 5G core networks［C］//Proc of IEEE Global Communications Conference.Piscataway，NJ：IEEE Press，2018：1-6.

［8]Guler E， Devaraju S， Luo Guangchun， et al. Multicast-aware service function tree embedding［C］//Proc of the 20th International Confe-rence on High Performance Switching and Routing.Piscataway，NJ：IEEE Press，2019：1-6.

［9]Cheng Yulun， Yang Longxiang. VNF deployment and routing for NFV-enabled multicast： a Steiner tree-based approach［C］//Proc of the 9th International Conference on Wireless Communications and Signal Processing.Piscataway，NJ：IEEE Press，2017：1-4.

［10]Zhang Saiqian， Tizghadam A， Park B， et al. Joint NFV placement and routing for multicast service on SDN［C］//Proc of IEEE/IFIP Network Operations and Management Symposium.Piscataway，NJ：IEEE Press，2016：333-341.

［11]Xu Zichuan， Liang Weifa， Huang Meitian， et al. Efficient NFV-enabled multicasting in SDNs［J］.IEEE Trans on Communications，2019，67（3）：2052-2070.

［12]Ren Bangbang， Guo Deke， Shen Yulong， et al. Embedding service function tree with minimum cost for NFV-enabled multicast［J］.IEEE Journal on Selected Areas in Communications，2019，37（5）：1085-1097.

［13]Alhussein O， Do P T， Ye Qiang， et al. A virtual network customization framework for multicast services in NFV-enabled core networks［J］.IEEE Journal on Selected Areas in Communications，2020，38（6）：1025-1039.

［14]Zhang Saiqian， Zhang Qi， Bannazadeh H， et al. Routing algorithms for network function virtualization enabled multicast topology on SDN［J］.IEEE Trans on Network and Service Management，2015，12（4）：580-594.

［15]Kiji N， Sato T， Shinkuma R， et al. Virtual network function placement and routing for multicast service chaining using merged paths［J］.Optical Switching and Networking，2020，36：100554.

［16]Asgarian M， Mirjalily G， Luo Zhiquan. Embedding multicast service function chains in NFV-enabled networks［J］.IEEE Communications Letters，2021，25（4）：1264-1268.

［17]Kuo J J， Shen S H， Yang Minghong， et al. Service overlay forest embedding for software-defined cloud networks［C］//Proc of the 37th International Conference on Distributed Computing Systems.Piscataway，NJ：IEEE Press，2017：720-730.

［18]Xie Kun， Zhou Xuhui， Semong T， et al. Multi-source multicast routing with QoS constraints in network function virtualization［C］//Proc of IEEE International Conference on Communications.Piscataway，NJ：IEEE Press，2019：1-6.

［19]Muhammad A， Sorkhoh I， Qu Long， et al. Delay-sensitive multi-source multicast resource optimization in NFV-enabled networks：a column generation approach［J］.IEEE Trans on Network and Service Management，2021，18（1）：286-300.

［20]Kou L， Markowsky G， Berman L. A fast algorithm for Steiner trees［J］.Acta Informatica，1981，15（2）：141-145.

［21]The University of ADELAIDE. The Internet topology zoo［EB/OL］.（2012-07-18）.http：//www.topology-zoo.org/dataset.html.