基于时变资源的容器化虚拟网络映射算法

邓伟健，陈 曦，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 平台容器化的虚拟网络设备时变资源的特点，给大规模网络实验平台在进行虚拟网络切块映射部署时提供了一种新思路。实验结果表明，在静态与动态部署场景中，基于时变资源模型的广度优先搜索算法，在底层资源利用率和网络性能等方面更有优势。下一步的工作是尝试使用机器学习算法，对不同网元资源的使用特征进行学习，对其下一时段的资源使用进行预测，进一步提高映射算法对底层资源的利用率与算法的可靠性。