On Algorithm of Functions Dynamic Orchestration in Virtualized Network

早期的虚拟网络功能管理，主要集中在云服务的包管理方法方面^[2].这种包的管理是通过研究不同网络运营商的经验来减轻当今企业网络中出现的管理复杂性. Stratos^[13]和OpenNF等^[14]提出了对NFV的更进式的管理方法. Stratos通过处理负载工程，提出了水平缩放等方式将虚拟化的网络功能存放在远程云平台中. OpenNF通过扩展集中式SDN模式为虚拟化的网络功能和网络转发平面提出了融合控制平面^[12].最近关于虚拟化的网络功能管理的一些工作侧重于流量工程问题，例如通过一些现有的虚拟化的网络功能序列来引导流量^[4].当一些虚拟化的网络功能修改分组报头时，从而改变流量特征，这个问题变得更具挑战性. Qazi^[4]和Fayazbakhsh提出了基于标记的机制，以在其生命周期中识别流量，并且还跟踪虚拟化的网络功能的访问序列.这些工作专注于确定虚拟化的网络功能链的布局和流量路由路径，而基于标记的方法可用于在虚拟网络中部署虚拟化的网络功能链.

Mehraghdam等^[13]提出了一种用于指定虚拟化的网络功能链的方法，同时提出了虚拟化的网络功能链放置的数学模型.然而，求解方法是非线性的，不允许多个租户之间的虚拟化的网络功能共享.文献[14]基于LP松弛，提出了一种用于查找数据间中心虚拟化的网络功能链放置的方法，然而，由于LP松弛，文献[14]上限超过了低层最多16个物理资源的能力.文献[15]提出了自动化虚拟化的网络功能布局的编排架构，但作者没有提供任何具体的编排算法.

将物理网络表示为无向图$\overline{G}=(\overline{S}, \overline{L}), \overline{S}$表示交换机的集合，$\overline{L}$表示链路的集合.假设虚拟网络功能可以部署在位于网络内的服务器上，这些网络位置传统上称为“点”$\overline{n}$.集合$\overline{N}$用二进制变量$\overline{h}_{\overline{ns}} \in\{0, 1\}$代表这些服务器$\overline{n} \in \overline{N}$是否附加到交换机$\overline{s} \in \overline{S}$，如(1)式所示：

令R表示由每个服务器提供资源集合(CPU，内存，磁盘等)，$c_{\overline{n}}^{r}\in {{\mathbb{R}}^{+}}$表示服务器$\overline{n}$的资源容量，${{\beta }_{\overline{uv}}}\in {{\mathbb{R}}^{+}}$，$\delta_{\overline{uv}} \in \mathbb{R}^{+}$表示带宽容量和物理链路$(\overline{u}, \overline{v}) \in \overline{L}$的传播延迟，定义$\eta(\overline{u})$作为交换机$\overline{u}$的集合，则存在(2)式的约束关系.

不同类型的虚拟网络功能集在现实网络中进行配置，虚拟网络功能的类型用集合p表示.用$D_{\mathfrak{h}}^{+}, \kappa_{\mathfrak{h}}^{r} \in \mathbb{R}^{+}(\forall r \in R)$，c_p(Mbps)，δ_p(ms)表示每个虚拟功能的类型p的部署成本，资源需求、处理能力和处理延迟如下所述：

部署成本：在服务器上传输和部署虚拟服务功能p的成本.

资源需求：必须分配给类型p的虚拟网络功能的类别r的资源量.

处理能力：表示虚拟网络功能可以处理的流量(以Mbps为单位).

处理延迟：是通过类型p的虚拟网络功能时数据包遇到的平均延迟(以ms为单位).

上述数量的实际值取决于很多因素，在这里，假设用这些属性的近似值来简化数学模型，可能存在某些硬件要求，会阻止服务器运行特定类型的虚拟化的网络功能.此外，网络管理员可以具有在特定服务器集上提供特定类型的虚拟化的网络功能的偏好.因此，假设对于每个虚拟化的网络功能类型都有一组服务器可以在其上进行配置，使用下面二进制变量表示此关系：

假设网络运营商正在接收用于设置不同类型业务的路径的请求.负载请求由6元组$t=\left\langle\overline{u}^{t}, \overline{v}^{t}, \psi^{t}, \beta^{x}, \delta^{t}, \omega^{t} \rangle\right.$，表示，其中$\overline{u}^{t}, \overline{v}^{t} \in \overline{S}$表示入口和出口开关，${{\beta }^{\mathit{t}}}\in {{\mathbb{R}}^{+}}$是负载需求的带宽， δ^t是根据服务水平协议允许的最大传播延迟，ψ^t是负载虚拟网络功能必须有序通过序列，lψ^t是ψ^t的长度，ω^t表示确定服务级目标违规的政策违规处罚.

此数学模型中，将虚拟网络功能序列ω^t转换为有向无环图G^t=(N^t，L^t)，其中N^t表示一组业务节点(虚拟网络功能，入口和出口的交换机)，L^t表示它们之间的链路，以这种方式建模负载流使得配置过程容易，以确保其通过正确的虚拟网络功能序列.还定义η^t(n₁)来表示n₁∈N^t的邻居：

不失一般性，在原有向图Gt中，如果n₂出现在n₁之后，考虑n₂>n₁(n₁，n₂∈N^t)，接着定义一个二进制变量g_np^t∈{0，1}表明节点n∈N^t的类型.

考虑一个运营网络正在服务一组流量的场景，它已经部署了一套虚拟化的网络功能并且还提供了业务的路由路径.现在，网络运营商正在接收新的流量请求，并希望为它们提供所需的虚拟化的网络功能和路由路径，网络运营商可以一次选择为一个流量请求提供资源，也可以选择通过累积多个流量请求并分批提供资源来利用查找间隔.在获得物理网络拓扑、虚拟化的网络功能规范、当前网络状态和一组新的流量请求条件下，通过测量空闲资源的百分比来计算物理资源碎片用于活动的服务器和链接，希望最大限度地减少碎片，实现提供最佳数量的虚拟化的网络功能，将其放置在最佳位置，以及为每个流量请求找到最佳路由路径，同时尊重容量约束，并确保流量通过适当的虚拟化的网络功能序列的目标.

与传统的虚拟网络嵌入问题相比，虚拟化的网络功能编排是一个NP难问题^[16]，虚拟网络嵌入中没有节点排序要求，而在虚拟化的网络功能编排中，需要保留虚拟化的网络功能的排序.此外，在虚拟化的网络功能编排中，需要尊重服务器和部署的虚拟化的网络功能的处理能力约束，要部署的虚拟化的网络功能数量并不是提前知道的，而是优化过程的结果.集装箱问题可以用来解决虚拟化的网络功能编排，但是在这里将最终得到一个嵌套的集装箱问题.在第一层中，流量需要打包成虚拟化的网络功能，下一层需要将虚拟化的网络功能打包到物理服务器中.事实上，虚拟化的网络功能的数量和位置预先不知道，导致资源容量的二次约束.

转换物理网络以生成增强的虚拟网络，从而降低虚拟网络功能编排的复杂性，在以下两个步骤中进行转换处理：

物理网络拓扑如图 1(a)所示.在这里，有3个开关(s1，s2和s3)和连接到开关s2的服务器n2，通过查找最大数量，此步骤中的所有可能的虚拟化的网络功能可以部署在任意服务器上，根据资源的能力来计算这个数字服务器和一种虚拟化的网络功能的资源需求.例如，如果一个服务器有16个内核，防火墙和IDS分别需要4核和8核，可以在其上部署4个防火墙或2个IDS.在图 2(b)中显示枚举了服务器n2的虚拟化的网络功能.

定义M为虚拟网络功能集，每个虚拟网络功能m∈M隐含地附加到服务器$\overline{n} \in \overline{N}$，还将两个附加的伪虚拟化的网络功能附加到每个服务器以表示流量的入口和出口点请求，使用函数ξ(m)表示上面的映射.

定义函数Ω($\overline{n}$)来表示在相反的方向映射：

定义q_mp∈{0，1}来表示虚拟化的网络功能的类型：

定义返回虚拟化的网络功能m类型的函数τ(m).

如前所述，可以部署给定类型的虚拟化的网络功能一组特定的服务器，为了确保这一点，必须有：

虚拟化的网络功能只是代表可以提供特定类型的网络功能的地方，y_m∈{0，1}表示虚拟化的网络功能是否有效

接下来通过在每个虚拟化的网络功能和它所连接的原始交换机之间添加虚拟交换机来再次增加物理拓扑，该过程如图 1(c)所示.执行此步骤以简化网络流量守恒约束的表达式，这个过程不会增加解决方案空间的大小，因为仅考虑流动守恒约束.

定义决策变量x_nm^t以表示业务节点到虚拟化的网络功能的映射：

定义另一个变量来表示物理网络中负载节点和交换机之间的映射

${z}_{n \overline{s}}^{t}$不是决定变量，它可以从x_nm^t中导出

因此，也可以从x_nm^t导出变量y_m

假设$\hat{x}_{mn}^{t}$表示最后一个负载调配事件的x_nm^t的值，为了确保先前提供的负载的资源不被释放，必须具有$x_{m n}^{t} \geqslant \hat{x}_{m m}^{t}$，$\forall t \in \hat{T}, n \in N^{t}, m \in M$.现在定义$\hat{y}_{m} \in\{0, 1\}$，表示最后一个负载的y_m值配置事件如下：

确保前面提供的负载资源不分配，必须满足$y_{m} \geqslant \hat{y}_{m}$，$\forall m \in M$.接下来需要确保虚拟化的网络功能容量不会过高，活动虚拟化的网络功能的处理能力必须大于或等于通过总量，约束如下：

为了确保物理服务器容量的限制不被部署的虚拟化的网络功能影响，存在约束如下：

负载的每个节点必须映射到适当的虚拟化的网络功能类型，该约束表示如下：

需要确保每个流量节点被配置，并且只需要一个虚拟化的网络功能.

定义的第二个决策变量来表示流量模型中的链路与物理网络中的链路之间的映射.

也假设$\hat{w}\frac{tn}{uv}{{1}^{{{n}_{2}}}}$表示在最后一个流量配置事件$w\frac{tn}{uv}{{1}^{{{n}_{2}}}}$的值，为了确保以前配置的流量的资源在当前的迭代中不被释放，定义如下约束

为了确保流量请求中的每个定向链路都未映射到物理链路的两个方向，必须具有：

物理链路的容量约束：

确保物理网络中每个交换机的负载在入口和出口交换机之外是相等的：

确保流量请求中的每个链接都在物理网络中的路径上进行配置：

本文的目标是找到服务器的最佳数量和位置的最小化，再就是虚拟化运营成本和物理资源及网络中的碎片最小化.

虚拟化的网络功能的部署成本可以表示如下：

在不失一般性的情况下，假设服务器的能耗与正在使用的资源数量成正比，然而，即使在空闲状态下，服务器也通常会消耗电力，因此，计算服务器的功耗如下：

r_t和r_c分别表示总资源和消耗的资源. e_idle^r和e_max^r分别表示资源r的空闲和峰值消耗状态中的能量成本.因此，总能源成本是

负载转发成本：假设通过网络中的一个链路转发1 Mbit数据的成本是σ(以美元计)，可以计算流量转发的总成本如下：

服务级目标违规处罚：可以计算实际流量经历的传播延迟如下：

令ρ^t(ω^t，δ^t， δ_a^t)作为计算服务级目标违规惩罚的函数，给定了判定罚分(ωt)的政策，预期传播延迟(δ^t)和实际传播延迟(δ_a^t)，所以违反服务级目标违规的总成本可以表示如下：

第二个目标是尽量减少活动服务器和链接的资源(服务器和链路)碎片，使用与上述费用相同的单位来表达.为此，假设p^r表示r∈R型单位资源的价格，也将ρ^β表示为单位带宽的价格.如果物理服务器至少有一个活动的虚拟化的网络功能，则该物理服务器被认为是活动的，二进制变量${{a}_{\overline{n}}}$捕获此属性：

类似地，物理链路$(\overline{u}, \overline{v})$被认为是活动的，如果它承载至少一个业务流，使用二进制变量$f_{\overline{u v}}$表示：

资源碎片的总成本如下

第一项表示服务器资源分片的成本(CPU、存储器、磁盘等)，第二项表示链路带宽分段的成本，目标是最小化网络运营成本和资源分割的总和，这可以表示为上述成本的加权和.

α，β，γ，λ，μ是用于调整成本组件的相对重要性的加权因子.

(37) 式的求解是一个NP难问题.将虚拟化的网络功能编排转化为单源限制容量工厂位置问题的NP难问题^[17].在文献[17]中，给出了一套具有固定成本和容量的生产工厂的潜在位置，由这些工厂生产的商品将提供给具有固定需求和相关运输成本的一组客户.此外，每个客户必须由一个工厂服务，目标是找到应该运行的平台的小部分，以尽量减少成本，而不会违反能力和需求限制.考虑到文献[17]的一个实例，可以通过以下方式将其转换为虚拟化的网络功能编排的实例：①对于每个客户，创建链→工厂→客户，其中创建链是虚拟入口交换机，客户是出口交换机，工厂是虚拟化的网络功能；②将链路的带宽设置为等于客户需求；③使用运输成本作为流量转发成本；④配置每台物理机器部署单个虚拟化的网络功能的工厂；⑤将每个工厂的加工能力设定为等于其生产能力.这些操作可以在问题大小的多项式时间内执行.现在，如果可以解决这个虚拟化的网络功能编排实例，也会得到一个文献[17]的解决方案.然而，文献[17]是NP-hard，虚拟化的网络功能编排也是NP-hard.

在本节中，提出一个启发式算法来解决虚拟化的网络功能编排.给定网络拓扑，一组中间件规范和一批流量请求，启发式查找以最小营运成本部署网络所需的不同类型的虚拟化的网络功能的数量和位置，没有指明用简单而快速的启发式算法来处理资源碎片的问题.然而，实验结果表明，即使这种简化，启发式产生非常接近最优的解决方案.启发式运行两个步骤，首先，将虚拟化的网络功能编排建模为具有相关成本的多阶定向图.然后，通过运行算法，从多级图中找到一个接近最优的虚拟化的网络功能位置^[18].

对于给定的负载请求$t=\left\langle\overline{u}^{t}, \overline{v}^{t}, \psi^{t}, \beta^{\prime}, \delta^{t}, \omega^{t}\right\rangle$，用l_ψ^t+2阶段将t表示为多阶段图.起始和终端阶段(i.e.，l_ψ^t+2)代表入口和出口交换机，这两个阶段只包含一个节点$\overline{u}^{t}, \overline{v}^{t}$.任意阶段i(i∈{2，…(l_ψ^t+1)})表示业务请求中的第(i-1)个虚拟化的网络功能，并且该阶段内的节点表示可以放置该类型的虚拟化的网络功能的可能的服务器位置，每个节点的部署与虚拟化的网络功能部署成本和能量成本相关联.

这个多阶图中的边($\overline{v}_{i}, \overline{v}_{j}$)表示虚拟化的网络功能在连接到交换机$\overline{v}_{j}$的服务器上的位置，假设序列中的虚拟化的网络功能部署在连接到交换机$\overline{v}_{i}$的服务器上，在i和i+1阶段的所有节点对之间设置一个有向边，将两个成本与每个边缘相关联：转发流量的成本(31)式和违反服务级目标违规的惩罚(33)式，流量转发成本与交换机之间的加权最短路径(以延迟为单位)成比例，通过以下过程获得对服务级目标违规行为的处罚：

1) 同样划分阶段之间的最大允许延迟；

2) 为多阶段图表中的两个连续阶段之间的转换分配服务级目标违规成本，每当导致由于节点处的流量传输和处理而导致的分配延迟.

通过对(37)式之后的节点和边缘成本相加来计算两个连续阶段之间的转换的总成本.最后，从第一阶段的节点到最后阶段的节点的路径代表了虚拟化的网络功能的放置，我们的目标是在多阶段图中找到产生最小营运成本的路径.

算法1给出了启发式解决方案的伪码，将负载请求t作为输入，并以每个交换机的资源容量注释网络拓扑图$\overline{G}$，保留成本和π两个表，以跟踪中间件展示位置的成本和顺序. cost_i，j表示在中间件序列ψ^t中将第j个中间件部署到连接有交换机i的服务器的成本，使用一些帮助程序来实现.第一个帮助程序“IsResourceAvailable”检查是否可以在交换机i上放置用于流量请求t的中间件mbox，以满足最低带宽和资源要求.第二个帮助者GetCost计算在连接到交换机j的服务器上为流量请求t放置中间件mbox的成本.在考虑到j时产生当前节点的最小成本，先前节点k由条目π_k，j跟踪，最后，使用π中的条目来追溯以获得所需的中间件序列.

拓扑数据集：我们把虚拟化的小范围网络称为Internet2. ①Internet2研究网络(12个节点，15个链路)，②大学数据中心网络(23个节点，42个链路)，③Rocketfuel拓扑数据集(79个节点，147个链路)的自治系统3967(AS-3967)^[19].

业务数据集：使用实际跟踪和综合生成的流量进行评估.使用流量矩阵跟踪Internet2拓扑生成的时变流量，该跟踪包含12×12流量矩阵的快照并显示流量的变化.最后，对于Rocketfuel拓扑结构，使用FNSS工具生成了一个合成的时变流量矩阵^[20]，它遵循文献[19]的分布并显示时间效应.

中间件和成本数据：根据文献[4]和文献[8]中提供的数据，为每个流量生成了一个长度为3的中间件序列.已经使用制造商和服务提供商的公开数据表来选择和推断服务器能源成本，服务级目标违规成本(违反最大延迟时间)，软件资源需求中间件及其处理能力，还从流行的网络设备制造商那里获得了硬件中间件的能耗数据.

虚拟化的网络功能和硬件中间件放置位置的拓扑特性如图 2-图 4所示，入口交换机和中间件之间跳数CDF如图 2所示.与硬件中间件相比，80%的虚拟化的网络功能位于入口交换机的2跳内(大多数为1跳)，只有4%的虚拟化的网络功能位于4跳距离，这说明将虚拟化的网络功能放置更远的地方，可以通过降低能源成本来减少营运成本.

对于中间件和出口开关之间的跳跃距离获得类似的结果(图 3).这两个数字也表明了CPLEX在入口和出口交换机之间的路径上以更平衡(对称)的方式放置中间件.

硬件中间件和虚拟化的网络功能的路径迁移性能如图 4所示.虚拟化的网络功能比硬件中间件具有更高的迁移性，因为虚拟化的网络功能位置不像硬件中间件固定，它们可以在任何服务器上进行配置以减少营运成本.

图 5显示了Internet2拓扑的平均利用率，VNF的平均利用率高于硬件中间件的平均利用率，VNF中间件在更高的流量期间通过部署更多的虚拟化的网络功能来降低营运成本，VNF中间件的代价是使用了更多的服务器，实现了资源利用率是硬件中间件的1.1倍.

图 6显示了数据中心网络的服务器资源利用相关的结果，在数据中心网络的情况下，VNF的利用率也更高.

Internet2和数据中心网络的中间件部署的拓扑特性如图 7-图 9所示，图 7显示了从入口交换机到虚拟化的网络功能中间件的跳线距离的CDF，数据中心网络的VNF的跳跃距离非常接近于最优解，在数据中心网络的情况下，存在较大的差距，这是由于数据中心网络提供的更高的路径分集，每对节点具有多于一个相等的成本路径.数据中心网络的VNF通过探索所有这些解决方案找到最佳，每对节点具有多于一个相等的成本路径.然而，启发式总是选择第一条最短路径，它没有探索将执行时间保持在实际限制之内的备选路径.

对于出口情况，观察到类似的结果(图 8).从图 7和图 8可以看出，CDF非常相似，这意味着VNF均匀地放置在入口和出口交换机之间的路径上.

路径迁移如图 9所示.如前所述，数据中心网络的VNF的性能接近于最优解，在数据中心网络的情况下，启发式方法具有较大的迁移性.

在本文中，提出了虚拟化的网络功能编排问题的两个解决方案：小型网络最佳解决方案和大型网络(数据中心)的启发式算法.仿真结果表明，所提出的启发式算法可以降低网络运营成本，相关性能优于传统的硬件中间件方法.下一步工作的重点是通过部署备份虚拟化的网络功能来提高故障恢复能力，并加强现有算法性能，进一步减少最优解的运行时间.