基于時變資源的容器化虛擬網絡映射算法

鄧偉健，陳 曦，2*

（1.西南民族大學計算機科學與工程學院，成都 610041；2.電子科技大學信息與通信工程學院，成都 611731）

0 引言

新網絡協議、算法、架構的先期研發依賴于網絡模擬仿真環境來開展，通過在硬件開發前對設計的協議及算法進行嚴格測試，來確保其能在實際網絡環境中運行。由于容器保留了基本完整的網絡協議棧，且相較于虛擬機，容器具有更高效的啟動和更少的性能開銷［1-2］，使得容器化技術開始流行起來，并為網絡實驗平臺的構建提供了新的思路。在本文的前期工作中，結合Docker［3］和OVS（Open vSwitch）［4］技術設計并初步實現了容器化的網絡實驗平臺，成功構建容器化虛擬網絡，并將其部署在物理宿主機上，用于高保真、易編程的網絡仿真。然而，在計算、網絡、存儲資源受限的物理宿主機上，要基于Docker+OVS 實現大規模網絡仿真［5］，網絡實驗平臺需要在虛擬網絡拓撲與物理宿主機計算集群之間進行合理、自動、高效地映射和必要的切塊部署，以保證分布式網絡仿真資源需求與負載平衡，提升網絡仿真的性能。因此，虛擬網絡映射算法設計是網絡實驗平臺設計的關鍵［6］。

事實上，學術界對相關問題已有相關研究，虛擬網絡映射（Virtual Network Embedding，VNE）問題［7-8］的求解具有相當高的復雜性甚至NP（Non-deterministic Polynomial）難［9］。早期學者通過純啟發式的方法對該問題進行求解［8］，但由于純啟發式求解可能會得到局部最優解，利用元啟發式求解能有效解決局部最優解問題，如文獻［10］提出一種基于蟻群元啟發式算法的可擴展映射策略；文獻［11］提出一種結合GRASP（Greedy Randomized Adaptative Search Procedure）和RVNS（Reduced Variable Neighborhood Search）元啟發式算法的混合算法，以及一種在線策略，該策略考慮了虛擬網絡映射的執行速度，以確保最小的延遲，在多域環境中提供了快速的解決方案。近些年也有部分學者將強化學習應用到該問題上，如文獻［12］將虛擬網絡映射問題建模為馬爾可夫決策過程（Markov Decision Process，MDP），提出了一種基于時間差分學習（一種強化學習方法）的虛擬神經網絡算法VNETD（Virtual Network Embedding base on Temporal-Difference learning）；文獻［13］針對云數據中心之間虛擬網絡映射的復雜性，設計了基于強化學習的預測模型。

現有文獻中的映射算法主要面向基于虛擬機的應用場景，主要從虛擬機資源分配高效性及映射成功率方面進行設計。本實驗平臺以Docker 技術構建虛擬網絡，除了要考慮資源分配高效性和映射成功率之外，映射算法還需要結合Docker 自身的技術特點進行設計與優化：1）Docker 容器模擬的虛擬網絡節點在宿主機上表現為低開銷進程，粒度更細，時變性更為明顯，因此要求映射算法具有更好的動態性，需對資源消耗及變化敏感、敏捷；2）Docker 作為輕量級虛擬化技術，不僅有利于構建規模更大的虛擬網絡，還有望部署在多臺低配X86 宿主機上，兩者均要求充分考慮宿主機的資源受限特征，靈活地對虛擬網絡進行自動優化切塊和映射；3）需結合OVS 等虛擬交換機的技術特征，對映射算法進行協同優化，做到實際可部署。

因此，本文首先通過對松散的虛擬網絡設備進行聚合預處理；然后利用一種評分機制對聚合后的虛擬網絡節點進行選擇，利用廣度優先與貪心策略將其映射到資源匹配的物理主機中；通過上述步驟使虛擬網絡切塊映射后更為緊湊；最后通過對已部署虛擬網絡的持續監控，定時將資源利用情況反饋給映射模型，對虛擬網絡映射模型作運行時調整，以此提高物理資源利用率。

1 問題及模型描述

為方便闡述，這里以一個實例來介紹虛擬網絡切塊、映射、部署的流程。

1）虛擬網絡的拓撲結構描述。假設用戶想要部署一個如圖1（a）所示的虛擬網絡（虛擬網絡規?？梢院艽?，這里為方便闡述，僅繪制一個2 個端系統、2 個路由器的拓撲結構），該虛擬網絡可以采用JSON 文件格式描述，并由前端界面通過圖形化拖拽生成。

2）虛擬網絡的切塊與映射。①算法輸入，將JSON 文件作為算法的輸入，算法讀取虛擬網絡的拓撲結構之后，根據現有各物理宿主機的剩余計算、網絡、存儲資源情況，決定是否對該虛擬網絡進行切塊和映射（若單臺宿主機能夠容納整個虛擬網絡則無需切塊和映射）、怎樣進行切塊和映射（具體算法后詳）。②算法輸出，若需要切塊和映射，則生成若干切塊JSON 文件，如圖1（b）部分所示。

3）虛擬網絡的部署。各物理宿主機收到切塊JSON 文件，各自按照JSON 的描述，利用Docker、OVS 等技術生成各類虛擬網元。這將涉及到網絡虛擬化，主要包括兩個方面：①節點虛擬化，使用Docker 容器模擬端系統、路由器等多層設備；使用OVS 技術模擬二層交換設備。②鏈路虛擬化，使用veth-pair［14］技術連接利用節點虛擬化得到的各類虛擬網元。

4）虛擬網絡的重新連接。虛擬網絡經過切塊和映射之后，不同的切塊分別部署在不同的宿主機，在某些鏈路上破壞了虛擬網絡原有的拓撲結構。因此，需要對其原有的拓撲結構進行跨宿主機的重新連接，主要采用OVS+VXLAN（Virtual eXtensible Local Area Network）［15］通過隧道技術實現，如圖1 虛擬網絡切塊部分所示?？紤]到OVS+VXLAN 隧道會造成一定的網絡性能損耗［15-16］，為了使虛擬網絡有較高的保真度，算法設計使應盡可能使同一次部署的虛擬網絡緊湊，減少跨底層物理主機鏈路，即：本算法不宜將原有的虛擬網絡切得過“碎”。

圖1 虛擬網絡切塊、映射、部署流程示意圖Fig.1 Schematic diagram of virtual network segmentation，mapping，and deployment process

1.1 物理網絡

本文網絡驗證平臺中，作為部署載體的底層物理環境具有較高的性能和一致性，其物理拓撲如圖2，由物理主機和交換機組成，各物理機連接到交換機上，構成星型物理拓撲。將物理拓撲表示為無向圖Gp={Np，Lp}，其中Np=表示物理主機集合，Lp=表示物理鏈路集合。對于每臺物理主機，定義為物理主機擁有的可用資源矢量和，包括CPU、內存、磁盤等；鏈路擁有的可用資源矢量和，如帶寬等。

圖2 物理網絡拓撲示意圖Fig.2 Schematic diagram of physical network topology

1.2 容器化虛擬網絡

為便于闡述，圖3 為一個較小規模的虛擬網絡拓撲，該網絡拓撲包含路由器、端系統、二層交換機等設備（亦稱網元），多個虛擬網絡設備組成局域網，局域網間通過域間路由設備連接。可見，該虛擬網絡能較為真實地反映現實網絡。利用本文網絡實驗平臺進行模擬仿真時，可多次部署不同的虛擬網絡拓撲，與物理網絡類似，采用無向圖表示第i次實驗部署的虛擬網絡，其中：表示第i次實驗部署的虛擬網絡設備集合；表示第i次實驗部署的虛擬鏈路集合。

圖3 虛擬網絡拓撲示意圖Fig.3 Schematic diagram of virtual network topology

1.3 虛擬網絡映射模型

虛擬網絡映射問題的本質［12］是在物理資源受限的條件下將虛擬網絡拓撲圖映射到物理基礎設施拓撲圖中，即：將每個虛擬網絡設備映射到物理基礎設施，并實現虛擬網絡設備間虛擬鏈路與物理鏈路的映射。

綜上所述可以得出一個簡單的虛擬網絡映射模型：

其中：R(Gp)≥。

對于每臺物理主機與物理鏈路：

約束條件為：

1.4 基于時變資源的虛擬網絡映射模型

上述簡單模型中并沒有考慮到容器化輕量級虛擬網絡在運行過程中資源的動態變化情況：同一虛擬網絡設備在不同時段運行的業務不同，導致在不同時段對資源矢量的需求不同。僅為實驗前測量的理論值，由于Docker 的特殊性，其值在容器運行時并不恒為該值，甚至可能出現個別虛擬網絡設備實際運行時資源需求值與實驗前測量理論值相差較大的情況，因此，在下文模型中引入時間變量。

對于物理拓撲，R(Np，T)表示T時Np擁有的資源矢量，即在ti時擁有的資源矢量；同理，在ti時擁有的資源矢量。對于虛擬網絡拓撲，表示T時第i次實驗部署的需要的資源矢量；表示T時第i次實驗部署的需要的矢量和；表示為初始資源需求上限值，也稱理論值。

為了能更準確反映虛擬網絡設備在運行時的資源需求量實際值，對虛擬網絡設備運行時資源矢量占用量進行計算時可采用均值的方式。若tk時刻資源矢量占用為，每間隔Δt進行資源占用量記錄，則在tk+1時刻進行實際資源占用量計算時可采用如下方式：

綜上，可以得出如下映射時變模型：

對于每臺物理主機與物理鏈路：

約束條件為：

其中：α為理論值與實際值的平衡因子，根據Pareto 定律，在實際中可設定資源矢量負載因子為0.8。

1.5 優化目標

由于跨物理主機鏈路映射時會造成網絡性能的損失，算法設計時，在符合約束條件情況下，應該使同一虛擬網絡內的網元盡可能映射到同一物理主機，使得虛擬網絡設備的映射盡可能緊湊，因此以下給出模型優化目標。

定義3跨主機鏈路占比Φ=，跨主機鏈路數=。

定義4Γ為映射到物理網絡拓撲中虛擬總虛擬網元數量，即虛擬網絡規模。

2 算法設計

本文通過對大規模虛擬網絡進行預處理，將網絡拓撲進行簡化；在對虛擬網絡設備進行映射時，先計算其聚集程度，將聚集程度高的優先部署到資源最空閑的物理主機；通過廣度優先對整個預處理后的虛擬網絡拓撲進行遍歷，完成每個虛擬網絡設備的映射。

2.1 虛擬網絡聚合

在本文的虛擬網絡實驗中，通常為一個三層網絡拓撲（如圖3 所示）。因此，可以以虛擬路由設備為基節點，將與路由網元連接的二層及以下的設備抽象聚合形成一個以虛擬路由設備為基節點的抽象聚合虛擬節點，如圖4 所示。

圖4 虛擬網絡聚合示意圖Fig.4 Schematic diagram of virtual network aggregation

設C(i，j)為以路由網元為基點的抽象聚合網元，則：

在對虛擬網絡進行預處理后，跨物理主機鏈路數量遠少于在同一主機內虛擬鏈路數量，且物理鏈路的模擬仿真能力遠遠超于虛擬鏈路。為了進一步簡化算法，提高虛擬網絡映射效率，跨物理主機虛擬鏈路在預處理后可暫時不考慮。

2.2 虛擬聚合節點聚集度

經上述對虛擬網絡拓撲進行預處理后，需要建立抽象聚合虛擬節點與物理主機之間的映射關系。為了使虛擬網絡設備盡可能緊湊，下文將引入聚集程度來對虛擬節點的重要性進行描述。

抽象聚合虛擬節點C(i，j)聚集程度計算公式如下：

其中：ρ(i，j)表示C(i，j)的聚集程度；D(i，j)為C(i，j)無向圖的度；D(i，k)為C(i，j)鄰接抽象聚合網元的度；Di為第i次部署的整個虛擬網絡的度。

通過以上步驟計算每個抽象聚合虛擬節點的聚集程度，對抽象聚合虛擬節點按其聚集程度進行排序，聚集程度越高，則認為該抽象聚合虛擬節點越重要，在映射時進行優先選擇。

2.3 基于時變資源模型的廣度優先搜索算法

廣度優先搜索（Breadth First Search，BFS）算法通過先訪問圖中的節點x，隨后依次將x鄰接節點中沒有被訪問過的節點加入后續訪問隊列中，然后分別從這些節點出發，依次訪問隊列中各節點的鄰接節點，直到圖中所有已被訪問的節點的鄰接節點都被訪問過。如果上述過程結束后，依然有節點未被訪問，就選擇圖中一個未被訪問的節點作為初始節點y，重復上述過程，直到圖中所有節點都被訪問。

可見使用廣度優先搜索算法對聚集程度高的聚合虛擬節點進行優先搜索后，可以使得虛擬網絡中節點的映射更加緊湊，使虛擬網絡中相鄰的節點在被映射后仍然保持鄰接關系，也達到減少跨物理主機虛擬鏈路的目的，降低虛擬網絡性能的損耗。基于時變資源模型的廣度優先搜索（Time Varying-BFS，TV-BFS）算法中，初始聚合虛擬節點和物理主機的選擇是關鍵。在虛擬網絡拓撲進行預處理后，通過計算抽象聚合虛擬節點的聚集程度，選擇聚集程度高的抽象聚合虛擬節點為廣度優先搜索的初始點，選擇該時刻時變資源模型中，擁有資源矢量最多的物理主機為映射的初始對象。

綜上所述，下面給出基于時變資源模型的廣度優先搜索算法（TV-BFS）偽代碼。

3 實驗與結果分析

對上述虛擬網絡映射算法進行性能測試，評價指標除了部署的網元數量外，還包含網元間網絡性能（如抖動、丟包率等）指標；并同基于廣度優先搜索的映射方法［17］、基于遺傳算法（Genetic Algorithm，GA）的映射方法［18］、基于粒子群優化（Particle Swarm Optimization，PSO）算法的映射方法［19］進行了性能對比。

3.1 實驗環境

實驗通過本平臺的前端系統設計生成大規模虛擬網絡拓撲，網絡拓撲中包含多種網元，包括二層交換設備、路由設備、運行不同業務的服務器、客戶端等，且每類網元對資源的需求不相同，相同種類網元運行的業務也可能不相同。圖5為本實驗平臺的架構簡圖。

圖5 網絡實驗平臺架構簡圖Fig.5 Diagram of network test platform architecture

圖5 中：

1）Topology-design 為前端拓撲設計；

2）Docker-Registry 為各類型虛擬網絡設備鏡像倉庫；

3）VNE 為虛擬網絡映射算法；

4）Worker-Monitor 為監控模塊，包括物理主機和容器及網絡的監控；

5）Container-Monitor 為監控運行時的容器及其網絡；

6）Topology-Build 為拓撲構建模塊，完成虛擬網絡拓撲的實際部署。

為了更直觀地展現基于時變模型的廣度優先搜索算法，本次實驗中通過以下兩種方式部署不同的虛網絡拓撲：1）一次性部署不同規模的虛擬網絡拓撲，即每次部署完成后先將上一次部署的網絡拓撲銷毀，再進行更大規模的部署，直至到達物理宿主機能容納的虛擬網絡規模上限為止，該部署方式對應靜態部署場景；2）多次地追加部署虛擬網絡拓撲，即不銷毀之前部署的網絡拓撲，追加地部署新的網絡拓撲，直至到達物理宿主機能容納的虛擬網絡規模上限為止，該部署方式對應多用戶同時部署或單用戶多次部署的動態部署場景。實驗平臺監控模塊，每20 s 更新一次監控數據，即Δt=20。部署完成后采用iperf、ping 等工具對網絡性能進行測試。

在進行虛擬網絡部署前需要獲取各類網元在虛擬網絡運行時所需的初始資源矢量（即理論值）。本文通過在表1 規格的物理主機中部署相當規模的網絡拓撲并在網元中運行業務后，進行數據收集得到如表2，該表表明了生成虛擬網絡網元時，CPU 及內存的初始配置，實際運行中該值不固定，根據虛擬網元運行的業務和應用按需分配，具有時變特征。

表1 物理主機配置Tab.1 Configuration of physical hosts

表2 部分網元資源使用理論值數據Tab.2 Part theoretical value data of network element resource usage

3.2 實驗結果與分析

在實驗過程中，由于Docker 采用輕量級虛擬化技術對網絡節點進行構建，內含較完整的TCP/IP 協議棧，即基于Docker 構建的虛擬網絡也是一個實際運行著的網絡，具有高保真特性，完整地再現了網絡的整個流程（包括DHCP 的IP地址分配、路由發現等控制平面行為），其代價就是在配置較低的物理宿主機上部署時間為分鐘級。盡管如此，如圖6（a）和圖7（a）可見，部署100 個節點左右的網絡僅5～8 min，考慮到其高保真的良好特性，可以較好地用于網絡研究，該部署時間在可接受范圍；同時，利用更高配置的物理宿主機將較好地改善該問題。以下通過不同的實驗場景來對四種虛擬網絡映射算法結果進行分析。

3.2.1 靜態部署

圖6 為在靜態部署場景下四種映射算法的實驗結果，該場景下部署的虛擬網元資源初始估值均以計算。可以看到隨著虛擬網絡規模的增長，底層物理資源使用量均呈上升態勢。TV-BFS 和BFS 算法在680 網元左右開始出現跨宿主機鏈路，即虛擬網絡開始進行分布式部署，而兩種啟發式算法（PSO 和GA）則在400 網元左右開始進行虛擬網絡分布式部署。盡管PSO 和GA 擁有更為均衡的資源利用，且在部署時間上有一定的優勢，但在同等規模虛擬網絡拓撲中PSO 和GA 需要建立更多的跨宿主機鏈路（即Φ更大）；因此，從圖7 靜態場景下，向虛擬網絡中注入流量后網絡性能比較中可以看到，PSO 和GA 網絡抖動上升較TV-BFS 和BFS 更快，網絡抖動曲線位于后兩者上方，在虛擬網絡規模為300網元后尤為明顯：網絡規模從400 網元增加到860 過程中，TV-BFS 網絡抖動從0.014 ms 上升到0.039 ms，此時PSO 和GA 分別從0.038 ms、0.03 ms 上升到0.097 ms、0.093 ms。隨著網絡規模的增大，差距越明顯。這表明僅僅簡單地對資源進行分布式部署，而不考慮跨宿主機鏈路的資源損耗，將對用戶在虛擬網絡上進行高保真的網絡實驗帶來不利的影響。尤其是，用戶在實驗過程中看到的是一體化的虛擬網絡，分布式映射和部署對于用戶而言是透明的，過多的跨宿主機鏈路造成的時延等方面額外損耗可能和實際的網絡性能表現有較大出入。因此TV-BFS 和BFS 在較少額外部署時間開銷的情況下，在實驗性能的保真度上更具優勢。

圖6 網絡靜態部署實驗Fig.6 Network static deployment experiment

圖7 網絡動態部署實驗Fig.7 Network dynamic deployment experiment

3.2.2 動態部署

圖8 為在動態部署場景下四種映射算法的實驗結果。在該實驗中初次部署100 多網元的虛擬網絡拓撲，隨后每次追加約為100 網元規模的不同類型（如星型、樹型等）的虛擬網絡拓撲。可以看出，TV-BFS 能部署1 400 多網元的虛擬網絡拓撲，而兩種啟發式算法（PSO 和GA）部署1 000 多網元的虛擬網絡拓撲，BFS 部署900 多網元虛擬網絡拓撲；即TVBFS 更能充分利用底層物理資源，在同等規格的物理資源條件下，部署更大規模的虛擬網絡（即Γ更大），同時幾種映射算法的部署時間也大致相同。從圖9 動態場景下向，虛擬網絡注入流量后網絡性能比較中可以看到，即使TV-BFS 部署了更大規模的虛擬網絡，但其網絡性能仍優于其余三種算法，在網絡規模為500 多網元后，其網絡抖動曲線明顯位于最下方。而兩種啟發式算法（PSO 和GA）隨著網絡規模的增大，網絡抖動變化越劇烈。網絡規模從400 網元上升到860過程中，TV-BFS 網絡抖動從0.015 ms 上升到0.03 ms，此時PSO 和GA 分別從0.04 ms、0.038 ms 上升到0.1 ms、0.12 ms，且在網元數量超過1 300 時，TV-BFS 網絡抖動仍然維持在0.1 ms 以下。

圖8 流量注入網絡性能比較（靜態部署）Fig.8 Comparison of traffic injection network performance（static deployment）

圖9 流量注入網絡性能比較（動態部署）Fig.9 Comparison of traffic injection network performance（dynamic deployment）

從上述兩種部署場景可以看出，在靜態場景下，TV-BFS通過虛擬網元聚合的前置處理能保證具有緊密關系間的網元盡可能緊湊，減少了跨宿主機鏈路的建立，使網絡性能得到保障；而在動態場景下，TV-BFS 通過對時變模型中資源評估進行動態調節，將網元實際的資源消耗量與理論資源消耗量進行加權調整，能更有效利用底層物理資源，相比其余三種映射算法能部署更大規模的虛擬網絡。PSO 和GA 盡管能獲得更均衡的負載，但也增加了跨主機鏈路數，導致網絡性能下降，因此，采用TV-BFS 能很好地兼顧網絡性能與底層物理資源使用率。

4 結語

本文提出的基于時變資源的容器化虛擬網絡映射模型，用于解決容器化虛擬網絡模擬仿真實驗平臺中大規模網絡切塊映射部署問題，結合容器平臺資源需求動態變化特征，可有效提高底層物理資源的利用率，同時使虛擬網絡的網絡性能得到有效保證。

由于大規模模擬仿真實驗中的虛擬網絡映射問題涉及到單個虛擬網絡設備與周邊虛擬網絡設備協同優化的問題，本文基于時變資源的容器化虛擬網絡映射模型考慮了虛擬網絡設備及其鄰接設備的關系，同時也考慮了Docker 平臺容器化的虛擬網絡設備時變資源的特點，給大規模網絡實驗平臺在進行虛擬網絡切塊映射部署時提供了一種新思路。實驗結果表明，在靜態與動態部署場景中，基于時變資源模型的廣度優先搜索算法，在底層資源利用率和網絡性能等方面更有優勢。下一步的工作是嘗試使用機器學習算法，對不同網元資源的使用特征進行學習，對其下一時段的資源使用進行預測，進一步提高映射算法對底層資源的利用率與算法的可靠性。