基于成本的服务链组成与部署联合优化策略

刘雅丽，史久根

（合肥工业大学计算机与信息学院，合肥 230009）

0 概述

网络功能虚拟化（Network Function Virtualization，NFV）技术将网络功能的实现从昂贵的硬件设备中转换到服务器上的虚拟设备中，旨在克服网络运营商（Internet Service Provider，ISP）日益增加的运营支出［1］（Operational Expenditure，OPEX）问题。NFV 将不同的网络功能（如防火墙、深度包检测、加密、解密等）与专用网络服务器分离，通过编排不同的虚拟网络功能（Virtual Network Functions，VNF）并将其映射到物理网络设施中以实现网络服务［2］，从而有效地提高部署和管理的灵活性［3］。但由于物理位置的选择复杂多样、VNF 改变流量的特性以及VNF 之间存在依赖关系［4］，因此充满了挑战性。

编排VNF 并将其合理部署在物理网络中是NFV 的关键技术之一［5］，现有大量研究致力于VNF网络功能的实现，其中多数仅考虑了部署问题［6-7］，例如，文献［8］制定了VNF 中间件放置问题，其目的是最大程度地减少提供特定服务的实例总数，并提出具有恒定逼近率的渐近最优贪婪算法。文献［9］提出一种渐近最优的在线算法用于服务链的准入控制和中间件的增量部署。除集中讨论部署阶段的研究外，也有部分学者考虑了组成与部署联合优化问题，文献［10］探讨VNF 资源优化的多阶段问题，研究服务功能链的协调分配和流量调度问题，提出一种基于CoordVNF 的启发式方法来协调组成和部署两个阶段。另外，文献［11］考虑并探讨了具体流量变化的影响，文献［12］则进一步分析了VNF 改变流的特性，并针对不同依赖关系状态提出了对应的放置算法。文献［13］证明了VNF 改变流量的特性对成本的影响。但这些文献都未考虑VNF 变化的相对资源需求对成本的影响，没有综合分析影响运营成本的具体因素。

为联合VNF 组成与VNF 部署两阶段共同优化，分析影响OPEX 的具体因素，本文综合考虑VNF 改变流量的特性、相对资源消耗、依赖关系以及部署方式的选择，提出一种面向成本的虚拟网络链组成和部署联合优化策略。将节点映射成本、链路映射成本、激活成本和能耗成本公式化为OPEX，建立混合整数非线性规划（Mixed-Integer Nonlinear Programming，MINLP）成本模型。根据依赖关系将请求集分成完全无序、部分有序和完全有序的VNF，并设计3 种对应的优化算法，分析影响成本的不同因素。

1 虚拟网络功能部署问题

虚拟网络功能（NFV）通过组成服务功能链（Service Function Chaining，SFC）并将其部署到物理网络中的方式来实现服务，完成了网络功能与物理设备的脱钩［14］。不同SFC 组成与部署方式对成本的影响如图1 所示（彩图效果见《计算机工程》官网HTML 版）。每个物理节点对应一个物理设备（Physical Machine，PM），如图1（a）所示，当网络功能部署到未激活的PM 上时，对应PM 需要分配一定的资源，如CPU、内存等，用以实现对应类型的虚拟设备（Virtual Machine，VM），以实例化VNF［15］。

图1 不同SFC 组成与部署方式对成本的影响Fig.1 The impact of different SFC composition and deployment methods on cost

1.1 虚拟网络功能

网络功能是执行特定功能的网络实体，本文用fi表示VNFi，F={fi|i=1,2,…,n}表示网络功能集合。VNF 多数是流处理设备，常以不同方式修改网络流［4］。例如Citrix Cloud Bridge 广域网优化器，通过压缩流量将流量减少了80%［16］。将VNF 的流量缩放比定义为λf=rout/rin，rin和rout分别为VNF 的输入、输出流。运行VNF 需要一定资源（如CPU、内存等），所需资源量dfi通常与该VNF 的相对数据速率和通过的流相关［17］为处理一个VNF 所需数据资源量。

1.2 服务功能链

服务功能链是服务流所需要遍历的一系列网络功能。假设共有K个服务请求，SFC 请求集为S={sk|k=1,2,…,K}，每 个SFC 由n种类型 的VNF 组成，即sk={fk1,fk2,…,fkn|fki∈F}。VNF 之间可能存在依赖关系：IPSec 解密器通常放置在NAT 网关之前［18］。本文用fdei≺fi表示fi依赖于fdei。为分析影响成本的不同因素，同时提高特殊依赖情况下的处理效率，本文将请求集分为完全无序、部分有序和完全有序的VNF 集合进行讨论。完全无序的请求集为{f1,f2}，部分有序的请求集为{f3,f4≺f5}，完全有序的请求集为{f6≺f7≺f8}。

1.3 问题描述

面向成本的VNF 链组成与部署问题是通过编排合适的SFC 并合理部署，从而最小化网络产生的OPEX。问题示例见图1，请求集{f1,f2,f3}完全无序，VNF 的缩放比分别为0.5、0.8、1.5，相对数据速率为10、20、30，请求初始流为1 Gb/s，源点为x1，终点为x6。各方案对应成本如图1（b）所示，通过比较可知：不同VNF 的缩放比、相对数据速率、SFC 的组成和路由选择都会对OPEX 造成影响，本文通过考虑各个因素，综合建模以优化OPEX。

2 混合整数非线性模型

将物理网络拓扑抽象表示为无向图G(E,V)，E和V分别表示物理链路和物理节点的集合。G中每个节点可以部署一定数量的虚拟机，每个虚拟机只能实例化一种类型的VNF。其中：zx∈{0,1}表示节点x∈V是否被激活∈{0,1}表示请 求k∈K的fi是否被映射到了物理节点x上；∈{0,1}表示虚拟链路(fi,fj)是否被映射到了物理链路(x,y)。OPEX中各成本描述如下：

1）节点映射成本。部署一个VNF 实例需要消耗一定成本，不同类型的VNF 有不同的资源消耗需求，本文将这种资源需求称为节点映射成本，将服务链sk中fi映射到节点所需的数据资源为部署K个服务功能链的总节点成本如下［19］：

2）链路映射成本。将虚拟链路映射到物理链路中需要消耗一定带宽资源，不同的链路组成方式、映射方式会导致不同的链路成本。部署K条服务功能链的总链路成本可以表示如下：

从式（8）可以看出：SFC 的链路成本变化仅与已部署VNF 之间的物理路径跳数hxk有关。综合式（4）、式（8）分析可知，SFC 顺序决定了节点映射成本，SFC 部署方式决定了链路映射成本。

3）激活成本。在部署VNF 之前，每个物理节点都需要消耗一定的成本来完成预配置等前提准备工作。激活成本由所激活节点的数量决定，用cx表示各节点的激活代价。总激活成本如下：

4）能耗成本。PM、VM 一旦被激活，就会消耗一定的资源用于维持自身运转［20］，而没有被激活的休眠PM、休眠VM 基本不会产生能耗，一般不考虑。活跃PM 与活跃VM 产生的总能耗成本如下：

综上，本文优化目标为最小化网络服务实现的总运营成本OPEX，表示为：

OPEX 受到以下约束：式（11）保证了每个请求的SFC 都必须被部署到网络中，并且每个VNF 只需要一个结点的虚拟机来实例化。

VNF 之间的依赖关系如式（12）所示：

每条物理链路上的流量之和不能超过其带宽容量B(x,y)，如式（13）所示：

式（14）、式（15）确保每个节点上所有VNF 的总资源消耗不应超过其资源容量，即要满足各类型虚拟机的容量和节点可供承载虚拟机的总资源量Cx的限制：

每个请求流不超过时延上限Dk，如式(16)所示：

VNF 的联合链接和部署如式(17)所示：

3 算法设计

3.1 完全无序的VNF 算法设计

由于3 种情况均需调用完全有序的VNF 放置算法（TOCP）的部署方式，本节主要描述组成方式的影响与算法设计。由上文可知，将缩小流的VNF 尽可能靠近源点放置，放大流的VNF 尽可能靠近终点放置，可以将链路成本最小化。考虑到相对数据速率影响，对部署在同一节点上的VNF 再次调整，可以在不改变链路成本的同时降低节点成本。同一节点上不同VNF 部署顺序影如图2 所示，调整节点x上的{f1→f2→f3}⇒{f3→f2→f1}，输出流量相同，节点成本从80.8 减少到了76.2。

图2 同一节点上不同VNF 部署顺序影响Fig.2 Impact of different VNF deployment orders on same node

完全无序VNF 的组成与放置算法（NOCP）设计如下：

1）将sk的所有fi根据升序排序；

2）将λf＞1 的VNF 从流路径的尾部按照λf降序预部署，将λf≤1 的VNF 从流路径的首部按照λf升序预部署；

3）对部署在同一节点上的VNF 通过全排列算法组合，并搜索具有最小的SFC；

4）通过完全有序VNF 的最短路径放置算法（TOSP）确定最终方案。

算法时间复杂度与TOSP 相同，由于篇幅限制，该部分伪代码不再赘述。

3.2 部分有序的VNF 算法设计

部分有序的VNF 需要考虑对应的依赖约束，本节主要描述部分有序VNF 的组成与放置算法（POCP）中独有的依赖关系处理算法——部分有序VNF 的SFC 组合算法（PO-C）。根据NOCP 设计原则可获得无依赖约束下的最优预部署方案，仅需对违背依赖约束的VNF 进行调整。算法按照预部署的SFC 顺序，依次将违背了依赖关系的fi紧随之后放置并组成一个新的f0，f0继承了fi和的依赖约束，将f0按 照大小插入原SFC 中即可获得新的SFC 队列，调整过程如图3所示，首先将所有VNF 按照λ排序，然后依次将违背了依赖关系的fi放到后组成新的f0，再插入原SFC，最终得到符合依赖约束的SFC 组成的预部署结果。

图3 依赖关系调整过程Fig.3 Adjustment process of dependency relation

PO-C 算法如算法1 所示，将违规重组的f0插入有序SFC 需要O(logan)，重组后的|sk|对应减少，因此将原SFC 调整为符合依赖约束的SFC，需要：O(logan)+O(loga(n-1))+…+O(loga1)＜O(nlogan)。因此，PO-C 算法低于自相关树转换算法［4］前瞻k值时的时间复杂度，且PO-C 算法不受参数k约束。POCP 其余部分与NOCP 类似，总时间复杂度与TOCP 算法的时间复杂度相同。

算法1部分有序VNF 的SFC 组合算法（PO-C）

3.3 完全有序的VNF 算法设计

完全有序VNF 组成的SFC 顺序固定，链路成本变化取决于物理链路长度，而能耗成本和激活成本则取决于激活的PM、VM 数。为优化OPEX，应尽可能地将VNF 放置在相同或相近的物理节点上。为此，TOCP 从最短路径开始，按序依次部署VNF。优先考虑复用已激活的VM、PM 数，若其剩余资源不足，再尝试开辟新的VM、PM 数，以免浪费。得到一组请求集的部署方案后，再尝试在该方案中关闭活跃度较低的节点，并迁移VM 以进一步节约成本。

分析TOCP 算法可知：寻路时使用DFS 回溯算法，时间复杂度为；预部署时间复杂度为；迭代地寻找并关闭负载低的PM，时间复杂度为因此，TOCP 总时间复杂度为

算法2完全有序VNF 的放置算法（TOCP）

4 仿真实验结果与分析

为保证模型可行性和算法的有效性，仿真实验建立在真实的网络拓扑中，数据来自SNDlib［21］。算法使用JUN 框架搭建，运行在2 个Intel Core I5-8300H 处理器和128 GB 内存的机器上。对NOCP、POCP 算法，实验选择在较大规模和流量的城域网络newyork（|V|=16，|E|=49，|S|=56）中比较；对TOCP 算法，在小型网络pdh（|V|=11，|E|=34，|S|=18）中仿真比较。由于校验和开销，用于无线通信的BCH（48，36）编码器使流量增加1.3 倍（48/36≈1.3），BCH（31，11）编码器使流量放大2.8 倍（31/11≈2.8）［22］。综合参考文献［12-13，22］，选取并设置了6 种不同VNF，对应缩放比分别为1.2、2.8、0.2、1.0、1.3 和0.8；对应数据比分别为64、32、2、8、4 和16。请求长度则按照1～6随机产生，请求流从0.01 Gb/s～2.50 Gb/s 分别进行实验。同时，实验使用对应OPEX 的4 种成本作为性能指标进行评估。节点成本为所有请求消耗的数据资源总和；链路成本为所有请求流在物理链路中的传输流量总和；激活成本为激活节点总数；能耗成本为活跃PM 与活跃VM 在运行过程中所消耗的能耗总和，其中一个PM 和VM 在活跃状态下的能耗分别为80.5 W、165.9 W［20］。

4.1 完全无序的VNF

本文引入3 种不同的算法进行比较：

1）首次适应（FF）［4］算法。从流路径的首部开始，按照缩放比升序连续放置排序后的VNF。

2）随机拟合（RF）［11］算法。在满足约束条件的前提下，随机组成并放置VNF。

3）LFGL 算法［12］。将缩减流量的VNF 从路径首部按照缩放比升序放置；其余VNF 从流路径尾部开始按照缩放比降序放置。

为减少部署方式的干扰，3 种比较算法与NOshortest 均采用最短路径算法放置，各算法性能表现如图4 所示，其中图4（a）是各算法比NOCP 多的节点映射成本，可以看到NO-shortest 各项性能均优于3 种比较算法。并且，在相同的部署方式下，不同的组成方式造成的成本差将随着请求流的增大而不断扩大。对比NO-shortest，采用不同部署方式的NOCP 仅牺牲了一点链路成本，能耗成本和激活成本上性能显著提高。

图4 完全无序VNF 仿真结果Fig.4 Simulation results of complete non-order VNF

4.2 部分有序的VNF

对于部分有序的VNF，实验假设VNF 间存在依赖关系：f1→f2，f4→f3。LFGL、FF 和RF 对比方法的依赖性调整策略采用k=2 时的自相关树转换算法，各算法性能如图5 所示，POCP 算法可以在满足NF之间的依赖约束的前提下有效降低总成本。图5 整体趋势与图4 相似，但各成本均有一定程度的增加与波动。因为相较于完全无序的VNF 而言，部分有序的VNF 在组成与部署的过程中约束更多，常常无法获得NOCP 中的较优方案。

图5 部分有序VNF 仿真结果Fig.5 Simulation results of partial-order VNF

4.3 完全有序的VNF

由于TOCP 在不同流量大小下的实验与NOCP、POCP 结果类似，本文不做赘述。本节考虑资源受限时TOCP的性能变化。由于VNF完全有序时，式（2）、式（6）为线性关系，系统模型为混合整数线性规划（Mixed-Integer Linear Programming，MILP）模型。通过采用OPL语言建模，并使用CPLEX12.7 求解得到了MILP 模型结果。同时，引入采用最大限度激活VM思想的HEU［23］算法作为对比实验进行比较。为减少不同初始SFC 设置的干扰，统一设置请求由长度为3 的SFC 组成：f1→f2→f3，初始请求流率设置为1 Gb/s。节点资源配比p=Cx/Cmin的范围设置为(0%,100%]，其中Cmin为资源不受限时请求所需的节点最小活跃VM 数。各算法的性能表现如图6 所示。从图6 可以看出：TOCP 算法的性能明显优于HEU、Shortest 算法，接近MILP 最优解；另外，当p＞50%时，TOCP 算法与最优解的差距很小，但随着节点资源的逐渐不足，部署结果产生了波动，与最优解存在一定的差距。

图6 完全有序VNF 仿真结果Fig.6 Simulation results of total-order VNF

5 结束语

网络功能虚拟化技术在实现网络灵活管理的同时降低了OPEX，对网络供应商有重要意义。本文考虑面向OPEX 的VNF 链组成与部署联合优化问题，研究不同依赖关系下的VNF 组成与放置，分析流量缩放比、相对数据率、依赖关系以及部署方式对OPEX 的影响。建立一种新的MINLP 成本模型，并根据依赖关系的不同将请求集分成完全无序、部分有序和完全有序3 种情况，设计相应的启发式算法。实验结果验证了本文算法的有效性。下一步考虑引入流量预测、网络可靠性评估、请求动态调度等算法，提高算法的可扩展性，以应对真实网络环境中的各种突发情况。