基于網絡資源相關性的虛擬網絡映射算法

摘 要：針對網絡虛擬化環境中資源利用率較低的問題，通過建立資源相關性度量模型，刻畫虛擬節點和物理頂點之間的匹配程度，根據虛擬節點和物理頂點之間的資源相關性，將虛擬節點映射到資源相關性較強的物理頂點上；為了降低虛擬鏈路的映射路徑長度，通過建立節點間鄰接關系模型，將相鄰的虛擬節點映射到鄰接的物理頂點上。實驗結果表明，提出的虛擬網絡映射算法均衡了物理網絡資源的分布狀態，降低了虛擬網絡映射的資源代價，提高了虛擬網絡請求接受率。

關鍵詞：網絡虛擬化；虛擬網絡映射；相關性；資源分配

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

文章編號：1001－3695（2023）03－040－0885－05

doi：10.19734/j.issn.1001-3695.2022.06.0383

Network resource correlation-aware virtual network mapping algorithm

Sun Suyun1，Peng Limin2

（1.School of Information Technology，Guangdong Industry Polytechnic，Guangzhou 510300，China；2.College of Mathematics amp; Informa-tics，South China Agricultural University，Guangzhou 510642，China）

Abstract：Aiming at the problem of low resource utilization in network virtualization environment，this paper proposed a resource correlation measurement model for measuring the fitness degree between virtual node and substrate vertex，then it mapped virtual node to substrate vertex having strong resource correlation value，which was the resource correlation between virtual node and substrate vertex.In order to reduce the mapping path length of virtual links，it mapped the adjacent virtual node to the adjacent substrate vertex by using the adjacency relationship model between nodes.Experimental results show that the distribution of substrate network resource is balanced，the resource cost of virtual network mapping is reduced，and the acceptance rate of virtual network requests is improved effectively by using the proposed virtual network mapping algorithm.

Key words：network virtualization；virtual network mapping；correlation；resource allocation

網絡虛擬化（network virtualization，NV）被視為構建新一代Internet 體系架構的重要技術［1］。虛擬網絡映射是網絡虛擬化中關鍵的研究問題，它負責將虛擬網絡映射到底層物理網絡中，并根據虛擬網絡請求的資源需求分配網絡資源［2］。在網絡虛擬化環境中，基礎設施提供商負責維護底層物理網絡，用戶通過租賃網絡資源創建虛擬網絡。由于虛擬網絡請求的多樣性和動態性，虛擬網絡請求具有不同的資源需求量、拓撲結構和生存時間等，如何在滿足虛擬網絡資源需求的前提下，提高網絡資源的利用率是一個具有挑戰性的研究問題。

由于創建虛擬網絡需要多種類型的網絡資源，如CPU資源、內存資源、存儲資源和帶寬資源等，特別是虛擬網絡具有多樣化的拓撲結構，在網絡虛擬化環境中，網絡資源的利用率低于30%［3］。文獻［4］通過實驗結果發現，當物理鏈路帶寬資源的利用率為18%時，虛擬網絡請求的拒絕率達到99%。本文通過深入研究發現，現有的虛擬網絡映射算法在分配網絡資源時，沒有考慮網絡資源的相關性，容易出現資源分配不均衡問題，如頂點CPU資源量很多、頂點鄰接鏈路帶寬量很少，或者頂點鄰接鏈路帶寬量很多、頂點CPU資源量很少，嚴重影響了資源的利用率，降低了虛擬網絡請求接受率。在現有研究的基礎上，本文通過對資源相關性問題進行分析，建立資源相關性度量模型，提出一個基于資源相關性的虛擬網絡映射算法，動態地將網絡資源分配給虛擬網絡請求，以此提高網絡資源的利用率。

1 相關研究

近幾年，學者們提出了很多虛擬網絡映射算法，如文獻［5］根據節點的CPU資源量、鏈路帶寬量和節點度數屬性，采用節點排名方法將虛擬節點依次映射到物理頂點上，然后使用最短路徑算法將虛擬鏈路依次映射到物理路徑上（該文將虛擬網絡中的節點稱為虛擬節點，節點之間的連接邊稱為虛擬鏈路；物理網絡中的節點稱為物理頂點，頂點之間的連接邊稱為物理邊）。低虛擬網絡算法的執行時間，文獻［6］首先采用節點排名方法映射虛擬節點，然后采用分布式并行遺傳算法映射虛擬鏈路。針對某些虛擬網絡請求的高帶寬需求，文獻［7］根據鏈路帶寬量、鏈路傳輸時延和鏈路能耗屬性，采用鏈路排名方法將虛擬鏈路依次映射到物理路徑上，并同步完成虛擬節點的映射操作。為了降低虛擬網絡映射的資源代價，文獻［8］采用圖的廣度優先搜索遍歷方法，依次將相鄰的虛擬節點映射到鄰接的物理頂點上。針對虛擬網絡映射的高能耗問題，文獻［9］根據網絡設備的能耗特性，將虛擬節點和虛擬鏈路映射到能耗最優的物理頂點和物理路徑上。文獻［10］針對網絡資源過度飽和問題，根據節點的資源豐富度和拓撲屬性對節點進行排序，將排序最高的虛擬節點映射至排序最高的物理節點。針對虛擬網絡的動態資源需求，文獻［11］通過建立局部適應度（local fitness）和全局適應度（global fitness）模型，將虛擬節點和虛擬鏈路動態地映射到資源適應度最優的物理頂點和物理路徑上。針對多個虛擬網絡請求動態到達的網絡場景，文獻［12］聯合考慮虛擬網絡映射的資源代價和能耗開銷問題，提出一種基于成本及功耗聯合優化的虛擬網絡映射算法，文獻［13～15］通過研究發現，資源碎片問題是引起資源利用率較低的原因，并分別采用關鍵節點、關鍵鏈路進行保護的策略和虛擬網絡重構方法，降低網絡資源的碎片率，盡管文獻［5～15］提出的算法改善了虛擬網絡映射的性能，但都沒有考慮資源相關性問題，導致物理網絡中資源分布不均衡且資源的利用率較低。文獻［16］根據虛擬機和服務器之間的資源互補關系，依次將虛擬機放置到互補的服務器中，使服務器呈現負載均衡分布狀態，但該算法沒有考慮節點位置關系，導致相鄰的節點映射到物理網絡后相距較遠，浪費鏈路帶寬資源。

2 問題描述與網絡模型

虛擬網絡映射是指將虛擬網絡請求部署到底層物理網絡上，并根據虛擬網絡請求的約束條件，將虛擬節點映射到物理網絡中的物理頂點上，將虛擬鏈路映射到物理網絡中的物理路徑上，并為虛擬節點和虛擬鏈路按需分配網絡資源。

2.1 問題描述

定義1 物理網絡（substrate network，SN）。采用無向帶權圖Gs=（Ns，Ls，RNs，RLs）表示物理網絡。其中，Ns為物理頂點集合；Ls為物理邊集合；RNs為物理頂點的可用資源矢量，如CPU資源量、內存容量、磁盤容量等；RLs為物理邊的可用資源矢量，如傳輸時延、可用帶寬量等。如圖1（b）所示，頂點A可用的CPU 資源量為70單位、可用的磁盤容量為80單位，物理邊e（A，B）可用的帶寬量為90單位。

定義2 虛擬網絡（virtual network，VN）。類似地，虛擬網絡也采用無向帶權圖Gv=（Nv，Lv，RNv，RLv）表示。其中：Nv為虛擬節點集合；Lv為虛擬鏈路集合；RNv為虛擬節點的資源需求矢量，如CPU資源量、內存容量、磁盤容量等；RLv虛擬鏈路的資源需求矢量，如傳輸時延、可用帶寬量等。如圖1（a）所示，節點a的CPU 資源需求量為10單位、磁盤容量為3單位，虛擬鏈路L（a，b）的帶寬需求量為8單位。

定義3 虛擬網絡映射（virtual network mapping，VNM）。它包含兩個基本操作：a）將虛擬節點映射到滿足資源約束的物理頂點上；b）將虛擬鏈路映射到滿足資源約束的物理路徑上，且物理路徑不構成環路。如圖1所示，虛擬節點a、b、c和d分別映射到物理頂點A、B、F和D上，虛擬鏈路L（a，b）、L（a，c）和L（c，d）分別映射到物理路徑P（A，B）、P（A，E，F）和P（F，D）上，并按需分配CPU資源、磁盤資源和帶寬資源。

3 網絡資源相關性虛擬網絡映射算法（NRC-VNM）

虛擬網絡映射算法的主要目標是提高網絡資源的利用率。本文主要根據虛擬節點和物理頂點的資源相關性，將待映射的虛擬節點映射到資源相關性最強的物理頂點上，均衡底層物理網絡資源的分布水平，以此提高網絡資源的利用效率。另一方面，由于物理網絡規模通常較大，低效的虛擬網絡映射算法可能使虛擬鏈路的映射路徑長度較長，增加虛擬網絡映射的資源開銷。針對這個問題，本文在虛擬網絡映射時充分考慮網絡的拓撲屬性，使用節點間鄰接關系度量模型，將相鄰的虛擬節點映射到鄰接的物理頂點上，從而降低虛擬網絡映射的資源開銷。

3.1 研究動機

在進行虛擬網絡映射時，需要滿足虛擬網絡請求的資源約束條件，這些資源包括CPU資源、內存資源、磁盤資源和帶寬資源等。如圖2所示，橫坐標表示帶寬資源量，縱坐標表示CPU資源量，假設物理頂點A和B初始CPU權重量、帶寬權重量均為30單位，運行一段時間后，物理頂點A可用CPU資源量為20單位、帶寬資源量為12單位，物理頂點B可用CPU資源量為5單位、帶寬資源量為12單位。假定虛擬網絡請求中某個虛擬節點的CPU需求量為4單位、帶寬需求量為12單位。當虛擬節點映射到物理頂點A后，物理頂點剩余的帶寬資源量為0、剩余的CPU資源量為16單位，由于物理頂點A的帶寬資源量為0，所以，物理頂點A剩余的16單位CPU資源量無法再被利用，此時物理頂點A帶寬利用率為100%、CPU利用率為46.667%、資源平均利用率為73.333%、資源利用率最大偏差為26.667%。當虛擬節點成功映射到物理頂點B后，物理頂點剩余的帶寬資源量為0、剩余的CPU資源量為16單位，由于物理頂點B的帶寬資源量為0，所以，物理頂點B剩余的1單位CPU資源量也無法再被利用，此時物理頂點B帶寬利用率為100%、CPU利用率為96.667%、資源平均利用率為98.333%、資源利用率最大偏差為1.667%。圖2中，虛擬節點和物理頂點A資源呈負相關，虛擬節點和物理頂點B資源呈正相關，很顯然，將虛擬節點映射到物理頂點B比映射到物理頂點A更合適，從而表明了高效的虛擬網絡映射算法可以有效地提高網絡資源的利用效率。

3.2 網絡資源相關性度量模型

從圖2可以看出，當虛擬節點的資源需求量和物理頂點的可用資源量在各個資源維度上呈正相關時，物理網絡中資源利用率最大偏差較低。本文使用皮爾森（Pearson）相關系數來度量虛擬節點和物理頂點之間的匹配程度。

算法1分兩步完成虛擬網絡映射操作。首先根據節點間鄰接關系度量模型和網絡資源相關性模型，將虛擬節點映射到物理頂點上，然后使用k-最短路徑算法［17］將虛擬鏈路映射到物理網絡中。步驟8中Mj表示物理網絡中適合映射虛擬節點vj的候選物理頂點集合，Mj中頂點個數α可根據網絡資源狀態進行動態調整。步驟9表示虛擬節點vj在候選頂點集Mj選擇資源相關性最強的物理頂點sj。節點映射算法的時間復雜度為Ο（|Nv|·|Ns|·|Mj|）。其中：|Nv|是虛擬網絡中節點個數；|Ns|是物理網絡中頂點個數；|Mj|默認值為10。步驟17～27表示使用k-最短路徑算法將虛擬鏈路映射到滿足帶寬需求的物理路徑上。虛擬鏈路映射算法的時間復雜度為O（|Lv|（|Ls|+|Ns|log|Ns|+k））。其中：|Lv|為虛擬網絡中的虛擬鏈路數；|Ls|是物理網絡中的物理邊數；|Ns|是物理網絡中的頂點數；k表示最短路徑個數，可根據網絡資源狀態進行調整，默認為5。

4 實驗結果與分析

為了驗證NRC-VNM算法的網絡性能，將NRC-VNM算法與文獻［6］的NTANRC-GA算法和文獻［15］的VNE-RFD算法進行性能比較。采用資源利用率最大偏差、網絡收益與資源代價比、虛擬網絡請求接受率、算法的執行時間作為性能評價指標。NTANRC-GA采用節點排名方法映射虛擬節點，然后使用分布式并行算法映射虛擬鏈路；VNE-RFD首先建立節點/鏈路的資源碎片度量模型，然后使用廣度/深度優先搜索遍歷算法，將相鄰的虛擬節點映射到鄰接的物理頂點上，并同步映射虛擬鏈路，通過保證物理網絡的連通性解決網絡資源碎片問題。

4.1 實驗參數設置

實驗使用GT-ITM生成虛擬網絡請求和物理網絡，具體實驗參數如表1所示。

4.2 資源利用率最大偏差

采用資源利用率最大偏差描述物理網絡中資源的負載均衡狀態。如圖3所示，三種算法的資源利用率最大偏差都隨運行時間的增加而不斷增大，NTANRC-GA增長最快，NRC-VNM增長較慢。其主要原因是NTANRC-GA在映射節點和鏈路時沒有考慮負載均衡問題，所以，NTANRC-GA的負載均衡性能較差。雖然VNE-RFD考慮了資源碎片問題，但是，VNE-RFD僅考慮了CPU資源和鏈路帶寬資源，忽視了內存資源。NRC-VNM通過使用資源相關性模型，綜合地考慮了網絡中各種資源的狀態，因此，NRC-VNM的負載均衡性能最好。

4.3 網絡收益與資源代價比

如圖4所示，三種算法的網絡收益與資源代價比隨時間增加而不斷下降，其中，VNE-RFD下降較慢，NTANRC-GA下降較快，其主要原因是NTANRC-GA充分地考慮了節點間的鄰接關系，相鄰虛擬節點映射到鄰接的物理頂點之上，虛擬網絡映射消耗的鏈路帶寬資源量大大減少。盡管NRC-VNM算法也考慮了網絡拓撲屬性，但NRC-VNM算法綜合考慮了節點間的資源相關性，增加的虛擬鏈路的映射路徑長度較大。NTANRC-GA沒有考慮節點間鄰接關系，導致虛擬鏈路的映射路徑長度較大，因此，NTANRC-GA的網絡收益與資源代價比最小。

4.4 虛擬網絡請求接受率

如圖5所示，三種算法的虛擬網絡請求接受率隨時間增加而不斷下降，其中，NTANRC-GA下降較快，NRC-VNM下降較慢，其主要原因是NTANRC-GA沒有考慮網絡資源的負載狀態，易引起資源碎片問題，導致虛擬網絡請求無法獲得足夠的網絡資源而被拒絕。VNE-RFD在虛擬網絡映射時沒有考慮資源的相關性，導致物理頂點上多種資源呈現不均衡分布，影響了虛擬網絡映射的網絡性能。

4.5 算法的執行時間

如圖6所示，VNE-RFD的執行時間最長，NTANRC-GA的執行時間最短，其主要原因是NTANRC-GA采用并行算法同步映射虛擬鏈路，減少了虛擬鏈路映射的執行時間。NRC-VNM采用k-shortest分步映射虛擬鏈路，相對NTANRC-GA而言，增加了算法的執行時間。VNE-RFD采用廣度/深度優先搜索遍歷算法，同步映射虛擬節點和鄰接的虛擬鏈路，特別是VNE-RFD映射過程中采用回溯方法，增加了算法的執行時間，因此，VNE-RFD的執行時間最長。

4.6 不同參數α對映射性能的影響

NRC-VNM中候選頂點個數α與網絡資源狀態有關，很顯然，α取值越小，虛擬網絡映射時節點鄰接關系一致性越強，虛擬網絡映射的資源開銷量越小，但虛擬節點和物理頂點間的資源相關性可能變弱，網絡資源均衡分布性能越差。在實驗中，分別測試了α取3個不同值時NRC-VNM的性能。如圖7所示，當α=5時，在實驗前期虛擬網絡請求接受率較高，但隨著仿真時間增加，虛擬網絡請求接受率下降較快，在實驗后期虛擬網絡請求接受率最低。從圖7可以看出，NRC-VNM算法α取10比較合適，因此，在NRC-VNM算法中α默認取值為10。

5 結束語

本文通過對現有的虛擬網絡映射算法進行分析，提出了一個兩階虛擬網絡映射算法。在節點映射階段，首先根據節點間鄰接關系度量模型，為虛擬節點查找距離較近的候選物理頂點，然后根據資源相關性模型，將虛擬節點映射到最優的物理頂點上；在鏈路映射階段，使用k-最短路徑算法，依次將虛擬網絡映射到最短的物理路徑上。實驗結果表明，本文提出的虛擬網絡映射算法取得了較好的網絡性能，該算法能很容易地擴展到更多的資源維度，因此，本文提出的NRC-VNM算法可應用于真實的網絡虛擬化環境中，提高網絡資源的利用率。

參考文獻：

［1］Yang Song，Li Fan，Trajanovski S，et al.Recent advances of resource allocation in network function virtualization［J］.IEEE Trans on Pa-rallel and Distributed Systems，2021，32（2）：295－314.

［2］Wu Shengchen，Yin Hao，Cao Haotong，et al.Node ranking strategy in virtual network embedding：an overview［J］.China Communications，2021，16（6）：114-136.

［3］Al-Tarazi M，Chang J M.Performance-aware energy saving for data center networks［J］.IEEE Trans on Network and Service Ma-nagement，2019，16（1）：206－219.

［4］Fajjari I，Aitsaadi N，Pujolle G，et al.VNR algorithm：a greedy approach for virtual networks reconfigurations［C］//Proc of IEEE Global Telecommunications Conference.Piscataway，NJ：IEEE Press，2011：1－6.

［5］Hashmi A，Gupta C P.VNE-NR：a node-ranking method for perfor-ming topology-aware and resource-driven virtual network embedding［C］//Proc of International Conference on Computing and Networking Technology.Piscataway，NJ：IEEE Press，2020：1－6.

［6］Nguyen K，Lu Qiao，Huang Changcheng.Efficient virtual network embedding with node ranking and intelligent link mapping［C］//Proc of the 9th IEEE International Conference on Cloud Networking.Pisca-taway，NJ：IEEE Press，2020：1－5.

［7］Sahoo P K，Dehury C K，Veeravalli B.LVRM：on the design of efficient link based virtual resource management algorithm for cloud platforms［J］.IEEE Trans on Parallel and Distributed Systems，2018，29（4）：887－900.

［8］彭利民.基于廣度優先搜索的虛擬網絡映射算法［J］.四川大學學報：工程科學版，2015，47（2）：117-122.（Peng Limin.Virtual network embedding algorithm based on breadth-first search［J］.Journal of Sichuan University：Engineering Science Edition，2015，47（2）：117-122.）

［9］彭利民.拓撲一致性綠色虛擬網絡映射算法［J］.小型微型計算機系統，2016，37（5）：1079-1083.（Peng Limin.Topology-aware green virtual network embedding algorithm［J］.Journal of Chinese Computer Systems，2016，37（5）：1079-1083.）

［10］朱國暉，張茵，劉秀霞，等.節點拓撲感知的高效節能虛擬網絡映射算法［J］.計算機科學，2020，47（9）：270-274.（Zhu Guohui，Zhang Yin，Liu Xiuxia，et al.Energy efficient virtual network mapping algorithms based on node topology awareness［J］.Computer Science，2020，47（9）：270-274.）

［11］Dehury C K，Sahoo P K.DYVINE-fitness-based dynamic virtual network embedding in cloud computing［J］.IEEE Journal on Selected Areas in Communications，2019，37（5）：1029-1045.

［12］柴蓉，謝德勝，陳前斌.基于成本及功耗聯合優化的SDN虛擬網絡映射算法［J］.電子學報，2021，49（8）：1615-1624.（Chai Rong，Xie De-sheng，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.）

［13］Lu Meilian，Lian Yuanxiang，Cheng Yanming，et al.Collaborative dynamic virtual network embedding algorithm based on resource importance measures［J］.IEEE Access，2018，12（6）：55026－55042.

［14］劉新波，王布宏，楊智顯，等.一種碎片感知的安全虛擬網絡重構方法［J］.電子與信息學報，2019，41（4）：995-1001.（Liu Xinbo，Wang Buhong，Yang Zhixian，et al.A fragment-aware secure virtual network reconfiguration method［J］.Journal of Electronics amp; Information Technology，2019，41（4）：995-1001.）

［15］Lu Hancheng，Zhang Fangyu.Resource fragmentation-aware embedding in dynamic network virtualization environments［J］.IEEE Trans on Network and Service Management，2022，19（2）：936－948.

［16］孫素云.基于互補機制的虛擬機放置算法［J］.中山大學學報：自然科學版，2020，59（3）：150-158.（Sun Suyun.Virtual machine placement algorithms based on complementary mechanism［J］.Acta Scientiarum Naturalium Universitatis Sunyatsenti，2020，59（3）：150-158.）

［17］Eppstein D.Finding the k shortest paths［C］//Proc of the 35th An-nual Symposium on Foundations of Computer Science.Piscataway，NJ：IEEE Press，1994：154-165.

收稿日期：2022－06－20；修回日期：2022－08－16 基金項目：國家自然科學基金資助項目（61103037）；廣東輕工職業技術學院科研項目（KJ2021-15）

作者簡介：孫素云（1977－），女，廣東廣州人，副教授，碩士，主要研究方向為分布式計算；彭利民（1976－），男，廣東廣州人，副教授，博士，主要研究方向為網絡功能虛擬化（sunsy81@126.com）.