基于VNF實例共享的服務功能鏈部署算法

摘 要：針對服務功能鏈（SFC）部署過程中存在虛擬網絡功能（VNF）實例部署成本和轉發路徑成本難以權衡的問題，提出了基于VNF實例共享的SFC部署算法。首先針對多鏈SFC建立VNF和虛擬鏈路映射模型，并預估路徑部署長度上限，保證SFC時延需求；其次，在路徑部署長度限制范圍內，盡可能使VNF實例共享最大化，以平衡鏈路轉發成本和VNF部署成本，最終得到SFC部署策略。與已有的SPH（shortest path heuristic）和GUS（greedy on used server）部署算法相比，所提算法所得的總運營成本分別降低6.6%和12.15%，且當SFC數量增多時，該算法的服務接受率可達89.33%。仿真實驗結果表明，提出算法可以在保證用戶服務質量的同時有效降低SFC部署成本。

關鍵詞：服務功能鏈；虛擬網絡功能；VNF實例共享；成本優化

中圖分類號：TP393.01 文獻標志碼：A

文章編號：1001-3695（2023）06-033-1806-06

doi：10.19734/j.issn.1001-3695.2022.11.0564

Service function chain placement algorithm based on VNF instance sharing

Wang Yuantao，Shu Zhaogang，Zhong Yiwen，Qiu Caiyu，Tian Jialin

（College of Computer amp; Information Sciences，Fujian Agriculture amp; Forestry University，Fuzhou 350002，China）

Abstract：This paper proposed an SFC（service function chaining） placement algorithm based on VNF（virtual network function） instance sharing to address the problem of difficult tradeoff between the deployment cost of VNF instances and forwarding cost in the process of SFC placement.Firstly，for multi-link SFC，it constructed the VNF and virtual link mapping model，and estimated the upper bound of the path deployment length to ensure the SFC delay.Secondly，within the limit of the path length，it maximized the number of the reused VNF instance as much as possible to balance the forwarding cost and the deployment cost of VNF.Finally，it obtained the SFC placement strategy.Compared with the existing SPH（shortest path heuristic） and GUS（greedy on used server） placement algorithms，the total operating expense of the proposed algorithm is 6.6% and 12.15% lower，and when the number of SFC increases，the service acceptance rate of this algorithm can reach 89.33%.The simulation experimental results show that this algorithm can effectively reduce the SFC placement cost while ensuring the quality of service.

Key words：service function chain；virtual network function；VNF instance sharing；cost optimization

0 引言

在傳統網絡中，物理設備是一個承擔著不同網元功能的黑盒子，其配置的靈活性較低。當前5G/6G網絡需要為垂直行業靈活地提供各種類型的網絡服務，而傳統的網絡管理架構顯得力不從心。隨著軟件定義網絡（software defined networking，SDN）［1］和網絡功能虛擬化（network function virtualization，NFV）技術的出現，大大緩解了這一問題。SDN和NVF可以將網絡功能靈活地部署在云服務的虛擬機上［2］，以實現低成本和靈活的網絡管理［3］。以上管理模式中，虛擬機中的網絡功能稱為虛擬網絡功能（virtual network function，VNF），而服務功能鏈（service function chain，SFC）是由多個VNF按一定順序連接的VNF實例集合（如防火墻、WAN優化器、負載平衡器和網絡地址轉換器），從而形成一個VNF轉發圖（virtual network function-forwarding graph，VNF-FG）［4］。因此，當用戶請求網絡服務時，網絡服務提供商可以為該用戶在虛擬機上部署對應的SFC；當服務結束后，則可以將虛擬機資源進行釋放，既增加了管理的靈活性，又降低了運營成本。

雖然SFC方案有效降低了網絡服務提供商的運營成本，但VNF的部署和編排［5］仍然有很多問題需要解決。主要體現在：在保證用戶網絡的服務質量（quality of service，QoS）的前提下（如滿足時延、帶寬需求），如何選擇VNF的部署位置和共享方案以進一步優化運營成本。運營成本包括部署VNF實例的成本和鏈路轉發成本兩部分。目前大部分研究只考慮VNF實例成本，或只考慮鏈路轉發成本，且在研究VNF實例共享方案時只考慮了SFC為單鏈的場景。因此，如何綜合考慮以上約束條件和多鏈場景，并兼顧QoS需求，進一步優化運營成本，是當前研究的一大挑戰，也是本文的主要研究目標。

對于用戶的時延需求，文獻［6］將兩個VNF之間的跳數作為傳輸延遲；文獻［7］將物理鏈路端到端傳輸延遲的總和視為請求的延遲；文獻［8］通過將VNF實例集中在更少的物理節點上，從而使請求流通過更少的物理鏈路以降低傳輸時延；文獻［9］提出一種基于深度強化學習的SFC映射算法，降低網絡平均時延和部署失敗率；文獻［10］通過避免物理鏈路上的流量過載情況來降低請求延遲。然而，以上研究只考慮了SFC為單鏈的情況，很少有研究考慮其他類型的VNF-FG。文獻［11］考慮了多播網絡服務的VNF放置，但是其中VNF-FG是僅具有一個源端和幾個目的端的特例，且沒有考慮延遲的需求。本文將為每個請求考慮基于VNF-FG部署的通用模型，并在VNF-FG映射到實際物理網絡時考慮用戶的延遲需求。

在有關增大經濟效益或降低成本作為優化目標的研究中，文獻［12］建立基于馬爾可夫決策的隨機優化模型，優化SFC部署成本和端到端時延；文獻［13］通過最小化活動虛擬機的數量，降低了部署成本；文獻［14］提出了一種基于加權圖匹配的匹配算法以提高資源利用率，并通過VNF遷移的方法關閉空閑服務器，以降低服務器成本；文獻［15］針對實時VNF部署和遷移，使用供需模型量化VNF干擾，提出一種實時自適應感知算法以最大化總收益；文獻［16］提出一種在線擴展算法，調整VNF實例部署以平衡VNF運營成本、VNF實例維護成本和VNF部署成本，但沒有考慮請求時延，忽略了用戶的QoS；文獻［17］提出基于時間窗的虛擬網絡批處理映射策略，以減少虛擬網絡映射成本和功耗；文獻［18］通過減少部署網絡服務的計算和帶寬資源消耗來降低運營成本；文獻［19］提出了一種新的VNF 部署策略，解決了VNF部署位置不確定性導致的帶寬資源浪費。

以上研究均為單個目標優化。在最小化SFC 端到端時延時沒有考慮VNF實例的部署成本，這增大了運營成本，因為為了滿足時延需求，VNF實例盡可能地部署在源端和目的端的最短路徑上，部分VNF實例所占據的服務器資源并沒有得到合理的利用。如果服務器的計算能力足以支持VNF需求，則不同服務鏈上相同類型的VNF可以共享該VNF實例［20］，提高資源利用率，減少VNF實例的部署成本，但這也會帶來轉發路徑的增長，從而導致流量開銷變大的問題，同時可能無法滿足SFC的時延要求。由此可見，鏈路分配和VNF實例部署之間的相互作用在VNF編排中起著重要作用。隨著網絡狀態的變化，在滿足資源需求和服務質量（如時延）的前提下，如何平衡VNF實例部署成本和鏈路轉發成本是目前亟待解決的問題。

目前SFC部署問題在現有工作中可以定義為具有不同目標的優化問題，為此提出了不同的解決方案?，F有工作中，精確求解方案可以提供最優解，但其很大程度上受網絡規模的影響，如文獻［21］利用 CPLEX 等計算工具得到小規模網絡下的精確求解，但在大規模網絡下運算會導致執行時間過長。而啟發式算法可以在短時間內提供近似最優解，且通常不受網絡規模的影響?，F有工作為了實現優化目標，通常會將線性規劃，如整數線性規劃（integer linear programming，ILP）或者混合整數線性規劃（mixed integer linear programming，MILP），結合啟發式算法進行求解。例如，文獻［22］建立了整數線性規劃模型，在有線和無線混合網場景下，基于資源感知的節點選取算法和帶寬最小的虛擬鏈路映射方案，提出了一種面向移動邊緣計算網絡的SFC高效可靠的部署方法。文獻［23］為了實現服務功能鏈的低成本高效率部署，提出了一種基于改進麻雀搜索算法的服務功能鏈優化映射算法，但其容易陷入局部最優。文獻［24］提出了一個聯合SFC部署和路由的優化問題。鑒于該問題是NP-hard，設計了一種候選路徑選擇的近似算法，提升了求解效率。文獻［9，25］提出一種基于深度強化學習的SFC映射算法，通過適當的獎勵設計、狀態和動作空間公式來決定服務鏈中各VNF的部署位置。但是在采用智能學習算法解決SFC部署問題時，現有工作的狀態空間定義較為簡單，但在實際情況下需要考慮的特征變量很多，這也會導致狀態空間求解復雜度提升。

不同于已有的研究工作，本文基于VNF實例共享，綜合考慮鏈路分配和VNF部署的問題，提出了一種SFC部署和路徑選擇算法以最小化運營成本。此外，鏈路分配（就路徑長度而言） 和VNF實例部署（就共享VNF實例的數量而言） 之間的關系在部署中是不穩定的，且在多目標多約束下求解部署策略已被證明為NP-hard問題［26］。本文的主要貢獻有：a）針對VNF-FG構建了一個基于VNF實例共享的SFC部署模型，并利用ILP模型對問題進行建模，在滿足用戶QoS要求的前提下最小化營運成本；b）考慮到實例部署成本和鏈路轉發成本之間的矛盾性，提出了基于VNF實例共享的服務功能鏈部署算法，通過預估路徑長度上限并在路徑長度約束下最大化可共享的VNF實例數量，以平衡鏈路和VNF實例的部署，從而最小化運營成本。

1 問題描述與系統模型

1.1 問題描述

1.2 系統模型

1.2.1 底層物理網絡模型

1.2.2 服務功能鏈

1.2.3 運營成本

1.2.4 時延

1.2.5 優化目標

2 基于VNF共享的服務功能鏈部署算法

2.1 算法描述

綜上所述，本文提出基于VNF共享的服務功能鏈部署算法，如算法3所示。依次遍歷每條SFC的轉發路徑，計算路徑長度上限（第5行），根據SFC的網絡資源需求，在物理網絡中查找源端到目的端的路徑，篩選出符合路徑長度上限和時延需求的可行路徑（第6行），遍歷可行路徑，調用算法1計算可支持部署的VNF數量和重用因子，比較各路徑的重用因子與物理路徑長度的比值，取比值最高的物理路徑，調用算法2進行部署（第10～18行）。若無法給SFC提供服務，則SFC被拒絕（第20～22行）。更新網絡資源后（第23行），繼續下一條SFC的部署。

2.2 算法復雜度分析

3 仿真與性能分析

本章對提出的基于VNF共享的服務功能鏈部署算法進行仿真和性能分析，并與兩種啟發式算法進行比較，從運營成本、VNF利用率和服務接受率進行分析。

3.1 實驗方法及仿真參數設置

本文采用含有 58個節點、87條鏈路的網絡拓撲，這個網絡拓撲來源于一項致力于收集各國不同網絡拓撲的研究［28］。每個的CPU資源為 100%，而物理鏈路的帶寬為10 Gbps［29］，物理鏈路的延遲在2～4 ms［30］。

3.2 實驗結果與分析

由于缺乏相關標準數據，策略目標不同，現有理論文獻也存在方法難以橫向比較等問題［31］。為了評估本文算法的性能，本文與文獻［15］中兩種啟發式方法進行比較：a）shortest path heuristic（SPH），沿著源端和目的端之間的最短路徑部署SFC的每個VNF-FP；b）greedy on used server（GUS），優先在可共享的VNF中放置，以避免占用額外的未使用服務器。

a）運營成本。作為本文的優化目標，運營成本即為VNF部署成本和鏈路轉發成本之和。在仿真中，本文將α1、α2均設為1，這意味著鏈路和VNF實例部署一樣重要。為了清晰地觀察各個算法的結果，本文對數據進行了歸一化處理，結果在［0，1］內。如圖4所示，相對于另外兩種算法，本文算法的總運營成本最低，其中SPH和GUS所需要的平均總成本分別高于本文算法6.6%和12.15%。其中鏈路轉發成本如圖5所示，GUS的平均鏈路轉發成本高于本文算法50.38%，該算法為了盡可能地共享VNF實例，不可避免地增加了路徑長度。對于VNF實例部署成本，如圖6所示，SPH的部署成本最高，高于本文算法33.94%，因為每個SFC都貪婪地部署在最短路徑上，而忽略了共享VNF實例。通過比較，本文基于VNF共享的服務功能鏈部署算法很好地平衡了鏈路轉發成本和部署成本，能夠有效降低運營成本。

b）利用率。如圖7所示，由于GUS優先考慮VNF實例共享，其VNF實例利用率最高，高于本文算法42.4%，而SPH優先考慮最短路徑部署，考慮較少的VNF實例共享，所以它的利用率最低，低于本文算法23.82%。雖然本文的利用率低于GUS，但是犧牲了部分VNF實例部署成本，從而避免了鏈路轉發成本的過度增長。

c）接受率。如圖8所示，當SFC數量增大時，本文基于VNF共享的服務功能鏈部署算法服務接受率均高于SPH和GUS，如當SFC數量達到75時，SPH和GUS的服務接受率分別為84%和86.67%，而本文算法的服務接受率為89.33%。因為SPH優先考慮最短路徑部署，導致網絡中存在VNF實例獨占服務器資源，而GUS雖然共享了VNF實例，但是因為路徑不可避免地增長，使鏈路帶寬資源無法滿足后續SFC，所以本文算法在網絡中可以支持更多的SFC。

4 結束語

針對SDN/NFV架構下SFC部署成本優化問題，本文首先將問題建模為多目標和多約束問題模型，該模型以最小化VNF實例部署成本和鏈路轉發成本為目標，同時受限于每條SFC時延、物理鏈路帶寬資源和服務器CPU資源約束；其次為每條VNF-FP設置路徑長度上限，以平衡鏈路和VNF實例的使用；最后提出基于VNF共享的服務功能鏈部署算法，聯合 SFC 放置和路徑選擇問題，以節省鏈路轉發成本并有效地重用 VNF實例。仿真結果表明，與SPH和GUS算法相比，本文的算法可以更好地管理鏈路和VNF實例之間的關系，顯著地降低了運營成本，并且可以使用有限的資源來服務更多的服務SFC。在未來，將考慮結合VNF實例的水平擴展和垂直擴展，開展基于深度強化學習的服務功能鏈部署方法的研究。

參考文獻：

［1］Hu Fei，Qi Hao，Bao Ke.A survey on software-defined network and OpenFlow：from concept to implementation［J］.IEEE Communications Surveys amp; Tutorials，2014，16（4）：2181-2206.

［2］王進文，張曉麗，李琦，等.網絡功能虛擬化技術研究進展［J］.計算機學報，2019，42（2）：415-436.（Wang Jinwen，Zhang Xiaoli，Li Qi，et al.Network function virtualization technology：a survey［J］.Chinese Journal of Computers，2019，42（2）：145-436.）

［3］Mijumbi R，Serrat J，Gorricho J L，et al.Network function virtualization：state-of-the-art and research challenges［J］.IEEE Communications Surveys amp; Tutorials，2015，18（1）：236-262.

［4］Cao Jiuyue，Zhang Yan，An Wei，et al.VNF-FG design and VNF placement for 5G mobile networks［J］.Science China Information Sciences，2017，60（3）：article No.040302.

［5］Bari F，Chowdhury S R，Ahmed R，et al.Orchestrating virtualized network functions［J］.IEEE Trans on Network and Service Management，2016，13（4）：725-739.

［6］Yang Binxu，Chai W K，Xu Zichuan，et al.Cost-efficient NFV-enabled mobile edge-cloud for low latency mobile applications［J］.IEEE Trans on Network and Service Management，2018，15（1）：475-488.

［7］Huang Meitian，Liang Weifa，Ma Yu，et al.Maximizing throughput of delay-sensitive NFV-enabled request admissions via virtualized network function placement［J］.IEEE Trans on Cloud Computing，2019，9（4）：1535-1548.

［8］Xia Ming，Shirazipour M，Zhang Ying，et al.Network function placement for NFV chaining in packet/optical datacenters［J］.Journal of Lightwave Technology，2015，33（8）：1565-1570.

［9］金明，李琳琳，張文瑾，等.基于深度強化學習的服務功能鏈映射算法［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 Compu-ters，2020，37（11）：3456-3460，3466.）

［10］Mebarkia K，Zsóka Z.Service traffic engineering：avoiding link overloads in service chains［J］.Journal of Communications and Networks，2019，21（1）：69-80.

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

［12］唐倫，賀蘭欽，連沁怡，等.基于改進深度強化學習的虛擬網絡功能部署優化算法［J］.電子與信息學報，2021，43（6）：1724-1732.（Tang Lun，He Lanqin，Lian Qinyi，et al.Virtual network function placement optimization algorithm based on improve deep reinforcement learning［J］.Journal of Electronics amp; Information Technology，2021，43（6）：1724-1732.）

［13］Aklamanu F，Randriamasy S，Renault E.Utility and A*-based algorithm for network slice placement and chaining［C］//Proc of IEEE Global Communications Conference.Piscataway，NJ：IEEE Press，2019：1-6.

［14］Chen Xiaoxiao，Shi Jiugen，He Yong，et al.Deployment strategy of resource optimized service function chain in NFV environment［C］//Proc of International Conference on Cryptography，Network Security，and Communication Technology.Bellingham：SPIE Press，2022：130-137.

［15］Zhang Qixia，Liu Fangming，Zeng Chaobing.Online adaptive interfe-rence-aware VNF deployment and migration for 5G network slice［J］.IEEE/ACM Trans on Networking，2021，29（5）：2115-2128.

［16］Luo Ziyue，Wu Chuan.An online algorithm for VNF service chain scaling in datacenters［J］.IEEE/ACM Trans on Networking，2020，28（3）：1061-1073.

［17］柴蓉，謝德勝，陳前斌.基于成本及功耗聯合優化的SDN虛擬網絡映射算法［J］.電子學報，2021，49（8）：1615-1624.（Chai Rong，Xie Desheng，Chen Qianbin.Cost and power consumption joint optimization based virtual network embedding algorithm for software-defined networking［J］.Acta Electronica Sinica，2021，49（8）：1615-1624.）

［18］Liu Junjie，Lu Wei，Zhou Fen，et al.On dynamic service function chain deployment and readjustment［J］.IEEE Trans on Network and Service Management，2017，14（3）：543-553.

［19］Wang Fangxin，Ling Ruilin，Zhu Jing，et al.Bandwidth guaranteed virtual network function placement and scaling in datacenter networks［C］//Proc of the 34th International Performance Computing and Communications Conference.Piscataway，NJ：IEEE Press，2015：1-8.

［20］Beck M T，Botero J F.Coordinated allocation of service function chains［C］//Proc of IEEE Global Communications Conference.Piscataway，NJ：IEEE Press，2015：1-6.

［21］Bari F，Chowdhury S R，Ahmed R，et al.Orchestrating virtualized network functions［J］.IEEE Trans on Network and Service Management，2016，13（4）：725-739.

［22］陳嘉亮，王豐，張瀟.移動邊緣計算網絡下的服務功能鏈部署優化設計［J］.計算機應用研究，2022，39（10）：3108-3113.（Chen Jialiang，Wang Feng，Zhang Xiao.Optimization design of service function chain deployment undermobile edge computing network［J］.Application Research of Computers，2022，39（10）：3108-3113.）

［23］朱國暉，景文煥，李世昌.基于改進麻雀搜索算法的服務功能鏈優化映射算法［J］.計算機應用研究，2022，39（7）：2120-2123，2131.（Zhu Guohui，Jing Wenhuan，Li Shichang.Optimized mapping algorithm of service function chain based on improved sparrow search algorithm［J］.Application Research of Computers，2022，39（7）：2120-2123，2131.）

［24］Shang Xiaojun，Liu Zhenhua，Yang Yuanyuan.Network congestion-aware online service function chain placement and load balancing［C］//Proc of the 48th International Conference on Parallel Proces-sing.New York：ACM Press，2019：1-10.

［25］Shah H A，Zhao Lian.Multiagent deep-reinforcement-learning-based virtual resource allocation through network function virtualization in Internet of Things［J］.IEEE Internet of Things Journal，2020，8（5）：3410-3421.

［26］Cong Peijin，Xu Guo，Wei Tongquan，et al.A survey of profit optimization techniques for cloud providers［J］.ACM Computing Surveys，2020，53（2）：article No.26.

［27］Zhang Qixia，Liu Fangming，Zeng Chaobing.Adaptive interference-aware VNF placement for service-customized 5G network slices［C］//Proc of IEEE Conference on Computer Communications.Piscataway，NJ：IEEE Press，2019：2449-2457.

［28］Knight S，Nguyen H X，Falkner N，et al.The Internet topology Zoo［J］.IEEE Journal on Selected Areas in Communications，2011，29（9）：1765-1775.

［29］Luizelli M C，Bays L R，Buriol L S，et al.Piecing together the NFV provisioning puzzle：efficient placement and chaining of virtual network functions［C］//Proc of IFIP/IEEE International Symposium on Integrated Network Management.Piscataway，NJ：IEEE Press，2015：98-106.

［30］Huang Meitian，Liang Weifa，Xu Zichuan，et al.Throughput maximization in software-defined networks with consolidated middleboxes［C］//Proc of the 41st Conference on Local Computer Networks.Piscataway，NJ：IEEE Press，2016：298-306.

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