开放科学（资源服务）标志码（OSID）：

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.1 虚拟网络功能

网络功能是执行特定功能的网络实体，本文用$ {f}_{i} $表示$ \mathrm{V}\mathrm{N}\mathrm{F}i $，$ F=\left\{{f}_{i}\right|i=\mathrm{1, 2}, \cdots , n\} $表示网络功能集合。VNF多数是流处理设备，常以不同方式修改网络流^[4]。例如Citrix Cloud Bridge广域网优化器，通过压缩流量将流量减少了80%^[16]。将VNF的流量缩放比定义为$ {\lambda }_{f}={r}_{\mathrm{o}\mathrm{u}\mathrm{t}}/{r}_{\mathrm{i}\mathrm{n}} $，$ {r}_{\mathrm{i}\mathrm{n}} $和$ {r}_{\mathrm{o}\mathrm{u}\mathrm{t}} $分别为VNF的输入、输出流。运行VNF需要一定资源（如CPU、内存等），所需资源量$ {d}_{{f}_{i}} $通常与该VNF的相对数据速率$ {d}_{{f}_{i}}^{\mathrm{r}\mathrm{e}\mathrm{l}} $和通过的流相关^[17]，$ {d}_{f}={r}_{\mathrm{i}\mathrm{n}}\cdot {d}_{f}^{\mathrm{r}\mathrm{e}\mathrm{l}} $为处理一个VNF所需数据资源量。

1.2 服务功能链

服务功能链是服务流所需要遍历的一系列网络功能。假设共有K个服务请求，SFC请求集为$ S=\left\{{s}_{k}|k=\mathrm{1, 2}, \cdots , K\right\} $，每个SFC由n种类型的VNF组成，即$ {s}_{k}=\left\{{f}_{1}^{k}, {f}_{2}^{k}, \cdots , {f}_{n}^{k}|{f}_{i}^{k}\in F\right\} $。VNF之间可能存在依赖关系：IPSec解密器通常放置在NAT网关之前^[18]。本文用$ {f}_{i}^{\mathrm{d}\mathrm{e}}\prec {f}_{i} $表示$ {f}_{i} $依赖于$ {f}_{i}^{\mathrm{d}\mathrm{e}} $。为分析影响成本的不同因素，同时提高特殊依赖情况下的处理效率，本文将请求集分为完全无序、部分有序和完全有序的VNF集合进行讨论。完全无序的请求集为$ \left\{{f}_{1}, {f}_{2}\right\} $，部分有序的请求集为$ \left\{{f}_{3}, {f}_{4}\prec {f}_{5}\right\} $，完全有序的请求集为$ \left\{{f}_{6}\prec {f}_{7}\prec {f}_{8}\right\} $。

1.3 问题描述

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

2 混合整数非线性模型

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

1）节点映射成本。部署一个VNF实例需要消耗一定成本，不同类型的VNF有不同的资源消耗需求，本文将这种资源需求称为节点映射成本，将服务链$ {s}_{k} $中$ {f}_{i} $映射到节点所需的数据资源为$ {d}_{{f}_{i}}^{k} $。部署K个服务功能链的总节点成本如下^[19]：

$ {C}_{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}}=\sum\limits_{k}\sum\limits_{i-1}^{n}{d}_{{f}_{i}}^{k} $

(1)

$ {d}_{{f}_{i}}^{k}={r}_{({f}_{i-1}, {f}_{i})}^{k}{d}_{{f}_{i}}^{\mathrm{r}\mathrm{e}\mathrm{l}}={r}_{0}^{k}\prod \limits_{j}{\lambda }_{{f}_{j}}{d}_{{f}_{i}}^{\mathrm{r}\mathrm{e}\mathrm{l}}, \forall j < i $

(2)

其中：$ {r}_{({f}_{i-1}, {f}_{i})}^{k} $为请求$ k\in K $的虚拟链路$ ({f}_{i-1}, {f}_{i}) $上的流量。假设服务链的源节点为$ {f}_{0} $，$ {r}_{0}^{k} $表示虚拟链路$ ({f}_{0}, {f}_{1}) $上的流量，为请求的初始流量。通过分析影响节点映射成本的具体因素，将$ {d}_{{f}_{i}}^{k} $取对数$ w\left({d}_{{f}_{i}}^{k}\right)=\mathrm{l}\mathrm{n}\left({d}_{{f}_{i}}^{k}\right) $可得到：

$ w\left({d}_{{f}_{i}}^{k}\right)=\mathrm{l}\mathrm{n}\left({r}_{0}^{k}\right)+\mathrm{l}\mathrm{n}\left({d}_{{f}_{i}}^{\mathrm{r}\mathrm{e}\mathrm{l}}\right)+\sum\limits_{j < i}\ln\left({\lambda }_{{f}_{i}}\right) $

(3)

$ \sum\limits_{i}^{n}w\left({d}_{{f}_{i}}^{k}\right)=n\mathrm{l}\mathrm{n}\left({r}_{0}^{k}\right)+\sum\limits_{i}^{n}\ln\left({d}_{{f}_{i}}^{{\rm{rel}}}\right)+\sum\limits_{i}^{n-1}\left(n-i\right)\ln\left({\lambda }_{{f}_{i}}\right) $

(4)

由式（4）可知：SFC的节点成本变化与流和VNF无关，仅与VNF间的相对顺序$ i $有关。当$ {\lambda }_{{f}_{i}} > 1 $时，VNF增大流，对应$ \mathrm{l}\mathrm{n}\left({\lambda }_{{f}_{i}}\right) > 0 $；当$ {\lambda }_{{f}_{i}} < 1 $时，VNF减小流，对应$ \mathrm{l}\mathrm{n}\left({\lambda }_{{f}_{i}}\right) < 0 $；当$ {\lambda }_{{f}_{i}}=1 $时，VNF不改变流，对应$ \mathrm{l}\mathrm{n}\left({\lambda }_{{f}_{i}}\right)=0 $。所以，$ {\lambda }_{{f}_{i}} > 1 $的VNF放置顺序越大，$ {\lambda }_{{f}_{i}} < 1 $的VNF对应放置顺序越小，节点成本也越小。

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

$ {C}_{\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{k}}=\sum\limits_{k}\sum\limits_{(x, y)\in {p}_{k}}{r}_{(x, y)}^{k} $

(5)

$ {r}_{(x, y)}^{k}={r}_{0}^{k}\prod \limits_{{f}_{i}}{\lambda }_{{f}_{i}},\;\forall {x}^{{'}}, (x, y)\in {P}_{k}, {x}^{{'}}\prec y, {\alpha }_{{f}_{i}, x\mathrm{{'}}}^{k}=1 $

(6)

其中：$ {r}_{(x, y)}^{k} $为物理链路$ (x, y) $消耗的带宽资源量，表示请求$ {s}_{k} $部署在$ (x, y) $上产生的链路成本。同样地，为分析影响链路成本的具体因素，将$ {r}_{(x, y)}^{k} $取对数$ w\left({r}_{(x, y)}^{k}\right)=\mathrm{l}\mathrm{n}\left({r}_{(x, y)}^{k}\right) $，可得^[13]：

$ w\left({r}_{(x, y)}^{k}\right)=\mathrm{l}\mathrm{n}\left({r}_{0}^{k}\right)+\sum\limits_{{\alpha }_{{f}_{i}, x}^{k}=1}\ln\left({\lambda }_{{f}_{i}}\right), \forall {x}^{{'}}\prec y $

(7)

$ \sum\limits_{(x, y)\in {p}_{k}}w\left({r}_{(x, y)}^{k}\right)=\left(\left|{p}_{k}\right|\mathrm{l}\mathrm{n}\right({r}_{0}^{k})+\sum\limits_{{\alpha }_{{f}_{i}, x}^{k}=1}\left(\left|{p}_{k}\right|-{h}_{xk}\right)\mathrm{l}\mathrm{n}({\lambda }_{{f}_{i}}) $

(8)

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

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

$ {C}_{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{v}}=\sum\limits_{x}{z}_{x}{c}_{x} $

(9)

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

$ {C}_{\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{y}}=\sum\limits_{x}\left({\mathrm{e}}^{\mathrm{P}\mathrm{M}}{z}_{x}+\sum\limits_{i}{\mathrm{e}}^{\mathrm{V}\mathrm{M}}{\eta }_{x}^{{f}_{i}}\right) $

(10)

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

$ {C}_{\mathrm{O}\mathrm{P}\mathrm{E}\mathrm{X}}={\mu }_{1}{C}_{\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{x}}+{\mu }_{2}{C}_{\mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}}+{\mu }_{3}{C}_{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{v}}+{\mu }_{4}{C}_{\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{y}} $

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

$ \sum\limits_{x}{\alpha }_{{f}_{i}, x}^{k}=1, \forall k\in K, {f}_{i}\in F $

(11)

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

$ i < j, \forall {f}_{i}\prec {f}_{j} $

(12)

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

$ \sum\limits_{k}\sum\limits_{i}{r}_{(x, y)}^{k}{\beta }_{(x, y)}^{({f}_{i-1}, {f}_{i}), k}\le {B}_{(x, y)} $

(13)

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

$ \sum\limits_{k}{d}_{{f}_{i}}^{k}{\alpha }_{{f}_{i}, x}^{k}/{C}_{\mathrm{v}\mathrm{m}}^{{f}_{i}}\le {\eta }_{x}^{{f}_{i}}, \forall k\in K, {f}_{i}\in F $

(14)

$ \sum\limits_{i}{C}_{\mathrm{v}\mathrm{m}}^{{f}_{i}}\le {z}_{x}{C}_{x}, \forall k\in K, {f}_{i}\in F $

(15)

每个请求流不超过时延上限$ {D}_{k} $，如式$ \left(16\right) $所示：

$ \left|{p}_{k}\right|\le {D}_{k}, \forall k\in K $

(16)

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

$ {\alpha }_{{f}_{i-1}, x}^{k}+{\alpha }_{{f}_{i}, y}^{k}\le {\beta }_{(x, y)}^{({f}_{i-1}, {f}_{i}), k}+1 $

(17)

3 算法设计 3.1 完全无序的VNF算法设计

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

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

1）将$ {s}_{k} $的所有$ {f}_{i} $根据$ {\lambda }_{{f}_{i}} $升序排序；

2）将$ {\lambda }_{f} > 1 $的VNF从流路径的尾部按照$ {\lambda }_{f} $降序预部署，将$ {\lambda }_{f}\le 1 $的VNF从流路径的首部按照$ {\lambda }_{f} $升序预部署；

3）对部署在同一节点上的VNF通过全排列算法组合，并搜索具有最小$ \sum\limits_{x}{d}_{x} $的SFC；

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

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

3.2 部分有序的VNF算法设计

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

PO-C算法如算法1所示，将违规重组的$ {f}_{0} $插入有序SFC需要$ O\left(\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}n\right) $，重组后的$ \left|{s}_{k}\right| $对应减少，因此将原SFC调整为符合依赖约束的SFC，需要：$ O\left(\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}n\right)+O\left(\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}\right(n-1\left)\right)+\cdots +O\left(\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}1\right) < O\left(n\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}n\right) $。因此，PO-C算法低于自相关树转换算法^[4]前瞻k值时的时间复杂度，且PO-C算法不受参数k约束。POCP其余部分与NOCP类似，总时间复杂度与TOCP算法的时间复杂度相同。

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

输入  请求$ {s}_{k} $

输出  符合约束的有序SFC队列$ {s}_{k} $

1.将$ {\mathrm{s}}_{\mathrm{k}} $的所有$ {\mathrm{f}}_{\mathrm{i}} $根据$ {\rm{ \mathsf{ λ} }}_{{\mathrm{f}}_{\mathrm{i}}} $升序排序，$ {{\mathrm{s}}_{\mathrm{k}}}^{\mathrm{{'}}}\leftarrow {\mathrm{s}}_{\mathrm{k}} $

2.for each $ {\mathrm{f}}_{\mathrm{i}} $ do

3.if $ {{\mathrm{f}}_{\mathrm{i}}}^{\mathrm{d}\mathrm{e}}\ne \mathrm{n}\mathrm{u}\mathrm{l}\mathrm{l} $ then

4.$ {\mathrm{f}}_{\mathrm{i}}\leftarrow \mathrm{g}\mathrm{e}\mathrm{t}\mathrm{N}{\mathrm{F}}_{0}({\mathrm{s}}_{\mathrm{k}}^{\mathrm{{'}}}, {\mathrm{f}}_{\mathrm{i}}) $，$ {{\mathrm{f}}_{\mathrm{i}}}^{\mathrm{d}\mathrm{e}}\leftarrow \mathrm{g}\mathrm{e}\mathrm{t}\mathrm{N}{\mathrm{F}}_{0}({\mathrm{s}}_{\mathrm{k}}^{\mathrm{{'}}}, {{\mathrm{f}}_{\mathrm{i}}}^{\mathrm{d}\mathrm{e}}) $

5.if $ \mathrm{I}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}({\mathrm{s}}_{\mathrm{k}}^{\mathrm{{'}}}, {\mathrm{f}}_{\mathrm{i}}) > \mathrm{I}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}({\mathrm{s}}_{\mathrm{k}}^{\mathrm{{'}}}, {{\mathrm{f}}_{\mathrm{i}}}^{\mathrm{d}\mathrm{e}}) $ then

6.$ {\mathrm{f}}_{0}=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{N}{\mathrm{F}}_{0}({{\mathrm{f}}_{\mathrm{i}}}^{\mathrm{d}\mathrm{e}}, {\mathrm{f}}_{\mathrm{i}}) $，$ {\rm{ \mathsf{ λ} }}_{{\mathrm{f}}_{0}}={\rm{ \mathsf{ λ} }}_{{{\mathrm{f}}_{\mathrm{i}}}^{\mathrm{d}\mathrm{e}}}\times {\rm{ \mathsf{ λ} }}_{{\mathrm{f}}_{\mathrm{i}}} $

7.$ \mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{D}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{e}({\mathrm{s}}_{\mathrm{k}}^{\mathrm{{'}}}, {\mathrm{f}}_{\mathrm{i}}) $，$ \mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{D}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{e}({\mathrm{s}}_{\mathrm{k}}^{\mathrm{{'}}}, {{\mathrm{f}}_{\mathrm{i}}}^{\mathrm{d}\mathrm{e}}) $

8.$ \mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{I}\mathrm{n}\mathrm{s}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{B}\mathrm{y}\mathrm{R}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}({\mathrm{s}}_{\mathrm{k}}^{\mathrm{{'}}}, {\mathrm{f}}_{0}) $

9.$ \mathrm{I}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}({\mathrm{s}}_{\mathrm{k}}^{\mathrm{{'}}}, {\mathrm{f}}_{\mathrm{i}})=\mathrm{I}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}({\mathrm{s}}_{\mathrm{k}}^{\mathrm{{'}}}, {\mathrm{f}}_{0}) $

10.$ \mathrm{I}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}({\mathrm{s}}_{\mathrm{k}}^{\mathrm{{'}}}, {{\mathrm{f}}_{\mathrm{i}}}^{\mathrm{d}\mathrm{e}})=\mathrm{I}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}({\mathrm{s}}_{\mathrm{k}}^{\mathrm{{'}}}, {\mathrm{f}}_{0}) $

11.end if

12.end if

13.end for

14.return $ {\mathrm{s}}_{\mathrm{k}}\leftarrow {\mathrm{s}}_{\mathrm{k}}^{\mathrm{{'}}} $

3.3 完全有序的VNF算法设计

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

分析TOCP算法可知：寻路时使用DFS回溯算法，时间复杂度为$ O(\left|V\right|+\left|E\right|) $；预部署时间复杂度为$ O\left(n\left|{V}_{\mathrm{P}\mathrm{M}}\right|\right) $；迭代地寻找并关闭负载低的PM，时间复杂度为$ O\left(\left|{S}_{k}\right|\left|{P}_{k}\right|\right) $。因此，TOCP总时间复杂度为$ O\left(n\left|{S}_{k}\right|\left|{P}_{k}\right|\left|{V}_{\mathrm{P}\mathrm{M}}\right|\right) $。

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

输入  $ G(V, E) $$ S $$ {l}_{k} $

输出  $ \mathrm{V}{\mathrm{M}}_{x} $，$ \mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{S}\mathrm{F}{\mathrm{C}}_{k}〈i\in {N}^{\mathrm{*}}, {f}_{i}\in F, x\in V〉 $，$ {R}_{k} $

1.$ \mathrm{V}{\mathrm{M}}_{\mathrm{x}}\leftarrow {\varnothing } $，$ \mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{S}\mathrm{F}{\mathrm{C}}_{\mathrm{k}}\leftarrow {\varnothing } $

2.while $ {\mathrm{s}}_{\mathrm{k}}\in \mathrm{S} $ do

3.获取从$ {\mathrm{x}}_{1}^{\mathrm{k}} $到$ {\mathrm{x}}_{\mathrm{t}}^{\mathrm{k}} $时延$ {\mathrm{l}}_{\mathrm{k}} $内的路径集合$ {\mathrm{P}}_{\mathrm{k}} $，并排序

4.while $ {\mathrm{p}}_{\mathrm{k}}=\left\{{\mathrm{x}}_{1}^{\mathrm{k}}, {\mathrm{x}}_{2}^{\mathrm{k}}, ..., {\mathrm{x}}_{\mathrm{t}}^{\mathrm{k}}|{\mathrm{x}}_{\mathrm{j}}^{\mathrm{k}}\in {\mathrm{p}}_{\mathrm{k}}\right\}\in {\mathrm{P}}_{\mathrm{k}} $ do

5.i=1，j=1，$ \mathrm{p}\mathrm{r}\mathrm{e}\mathrm{S}\mathrm{F}{\mathrm{C}}_{\mathrm{k}}\leftarrow {\varnothing } $

6.while $ \mathrm{i}\le \mathrm{n} $ and $ {\mathrm{x}}_{\mathrm{j}}\in \mathrm{p} $do

7.if $ \mathrm{c}\mathrm{l}\mathrm{o}\mathrm{s}{\mathrm{e}}_{{\mathrm{x}}_{\mathrm{j}}}==\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e} $ then

8.j++，continue；

9.end if

10.if $ {\mathrm{f}}_{\mathrm{i}}\in \mathrm{V}{\mathrm{M}}_{\mathrm{x}} $ and $ \sum\limits_{\mathrm{k}}{\mathrm{d}}_{{\mathrm{f}}_{\mathrm{i}}}^{\mathrm{k}}{\rm{ \mathsf{ α} }}_{{\mathrm{f}}_{\mathrm{i}}, \mathrm{x}}^{\mathrm{k}} > {\mathrm{C}}_{\mathrm{v}\mathrm{m}}^{{\mathrm{f}}_{\mathrm{i}}}{{\rm{ \mathsf{ η} }}}_{\mathrm{x}}^{{\mathrm{f}}_{\mathrm{i}}} $

11.$ \mathrm{p}\mathrm{r}\mathrm{e}\mathrm{S}\mathrm{F}{\mathrm{C}}_{\mathrm{k}}\bigcup \left\{\left\langle {{\rm{i}},{{\rm{f}}_{\rm{i}}},{\rm{x}}} \right\rangle \right\} $

12.else if $ \left|\mathrm{V}{\mathrm{M}}_{\mathrm{x}}\right| < {\mathrm{C}}_{\mathrm{x}} $

13.$ \mathrm{V}{\mathrm{M}}_{\mathrm{x}}\cup \{{\mathrm{f}}_{\mathrm{i}}\} $，$ \mathrm{p}\mathrm{r}\mathrm{e}\mathrm{S}\mathrm{F}{\mathrm{C}}_{\mathrm{k}}\bigcup \{ < \mathrm{i}, {\mathrm{f}}_{\mathrm{i}}, \mathrm{x} > \} $，$ {{\rm{ \mathsf{ η} }}}_{\mathrm{x}}^{{\mathrm{f}}_{\mathrm{i}}} $=1

14.i++；

15.end if

16.end while

17.if $ \left|\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{S}\mathrm{F}{\mathrm{C}}_{\mathrm{k}}\right|==\left|{\mathrm{M}}_{\mathrm{k}}\right| $ the

18.$ \mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{S}\mathrm{F}{\mathrm{C}}_{\mathrm{k}}\leftarrow \mathrm{p}\mathrm{r}\mathrm{e}\mathrm{S}\mathrm{F}{\mathrm{C}}_{\mathrm{k}} $，$ {\mathrm{R}}_{\mathrm{k}}\leftarrow \mathrm{P}\mathrm{a}\mathrm{t}{\mathrm{h}}_{\mathrm{k}} $；break

19.end if

20.end while

21.end while

22.寻找虚拟机数最少且出入度最小的活跃节点$ {\mathrm{x}}_{\mathrm{j}} $

23.while $ {\mathrm{x}}_{\mathrm{j}}\ne \mathrm{n}\mathrm{u}\mathrm{l}\mathrm{l} $ do

24.$ \mathrm{c}\mathrm{l}\mathrm{o}\mathrm{s}{\mathrm{e}}_{{\mathrm{x}}_{\mathrm{j}}}\leftarrow \mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e} $；//返回step2

25.end while

26.return $ \mathrm{V}{\mathrm{M}}_{\mathrm{i}} $，$ \mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{S}\mathrm{F}{\mathrm{C}}_{\mathrm{k}} $，$ {\mathrm{R}}_{\mathrm{k}} $；

4 仿真实验结果与分析

为保证模型可行性和算法的有效性，仿真实验建立在真实的网络拓扑中，数据来自SNDlib^[21]。算法使用JUN框架搭建，运行在2个Intel Core I5-8300H处理器和128 GB内存的机器上。对NOCP、POCP算法，实验选择在较大规模和流量的城域网络newyork（$ \left|V\right| $=16，$ \left|E\right| $=49，$ \left|S\right| $=56）中比较；对TOCP算法，在小型网络pdh（$ \left|V\right| $=11，$ \left|E\right| $=34，$ \left|S\right| $=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种比较算法与NO-shortest均采用最短路径算法放置，各算法性能表现如图 4所示，其中图 4（a）是各算法比NOCP多的节点映射成本，可以看到NO-shortest各项性能均优于3种比较算法。并且，在相同的部署方式下，不同的组成方式造成的成本差将随着请求流的增大而不断扩大。对比NO-shortest，采用不同部署方式的NOCP仅牺牲了一点链路成本，能耗成本和激活成本上性能显著提高。

4.2 部分有序的VNF

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

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组成：$ {f}_{1}\to {f}_{2}\to {f}_{3} $，初始请求流率设置为1 Gb/s。节点资源配比$ p={C}_{x}/{C}_{\mathrm{m}\mathrm{i}\mathrm{n}} $的范围设置为$ \left(0\mathrm{\%}, 100\mathrm{\%}\right] $，其中$ {C}_{\mathrm{m}\mathrm{i}\mathrm{n}} $为资源不受限时请求所需的节点最小活跃VM数。各算法的性能表现如图 6所示。从图 6可以看出：TOCP算法的性能明显优于HEU、Shortest算法，接近MILP最优解；另外，当$ p > 50\mathrm{\%} $时，TOCP算法与最优解的差距很小，但随着节点资源的逐渐不足，部署结果产生了波动，与最优解存在一定的差距。

5 结束语

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