1.   引 言

在支持网络功能虚拟化(Network Function Virtualization, NFV)的软件定义网络(Software Defined Networks, SDNs)中，为实现可靠、安全及可扩展传输等目的，用户请求流通常需要依序遍历由多个虚拟网络功能(Virtual Network Functions, VNFs)组成的服务功能链(Service Function Chain, SFC)^[1]。对于单播请求流， SFC可以直接沿着单播路由路径依次选择嵌入节点进行VNF部署，目前已有大量文献对这一工作进行了研究，特别是文献[2]利用拉格朗日对偶理论^[3]设计松弛算法求解了具有多资源多QoS约束的单播SFC嵌入问题，具有典型的代表性。多播通过共享的多播树进行多路复用，与单播相比，可以减少骨干网50%以上的带宽消耗^[4]。2022年至2028年，全球视频流媒体市场预计将以21.0%的复合年增长率扩张^[5]，这些视频流大多以多播的形式向用户提供服务。在SDN/NFV架构中具有SFC需求的多播请求流(Multicast Request flows, MRs)是将流量从源点转发到多个目的节点，每个源-目的对之间需要根据SFC的要求依序遍历多个VNFs实例，这将形成一个虚拟网络功能转发图^[6]。图1为该文构建的一条多播流从源点s依序经过由防火墙(FW)、入侵检测系统(IDS)、入侵阻止系统(IPS)组成的3条相同SFC后到达各个目的节点的示意。显然这3条SFC共同组成了一颗多播服务功能树(Service Function Tree, SFT)。联合考虑网络中各种资源及QoS约束条件，为多播请求流嵌入SFC是一个巨大的挑战。

图 1  多播服务功能树

下载: 全尺寸图片 幻灯片

目前，在SDN/NFV架构中，研究多播SFT嵌入的文献比较少。文献[7-9]研究了在已经放置了多个VNF实例环境中MRs的路由问题，但文献[7]没有考虑路由过程中VNF的动态部署，文献[8]考虑了VNF的运行和动态部署成本，但没有联合考虑网络中交换节点的转发成本，并且，它们都以多播源-目的对之间的单条SFC进行嵌入。文献[9]重点关注多播业务链的迁移调整，文献[10]则基于预测的方式对多播流的SFC进行动态嵌入，上述工作没有基于多播服务功能树(SFT)对SFC进行灵活整体嵌入，会造成网络资源分配不均衡。文献[11,12]研究了SFT的动态编排和整体嵌入，但文献[11]假设所有VNFs都部署在一个NFV功能节点中，文献[12]则要求多播分发点只能在部署的最后一个VNF节点之后进行，限制了SFT嵌入的灵活性和可扩展性，从而降低了网络资源的使用效率。

此外，对于视频会议、多人游戏等实时性要求较高的多播应用，对时延和抖动有严格要求。文献[13-17]研究了SFT的灵活嵌入和部署问题，但文献[13,14]没有考虑多播延迟和抖动约束，文献[15-17]考虑了端到端的延迟约束，但没有考虑多播目的节点之间的抖动约束，上述工作会影响多播用户的服务体验质量。文献[18]考虑用户的移动性及加入退出机制，研究了NFV网络中多播SFC的嵌入，调整和扩展问题。文献[19]是在无线Mesh网络中，考虑无线信号干扰和资源受限的情况下，以最小化链路成本为目标研究多播服务功能树的嵌入问题。上述工作同样没有考虑多播SFT时延和抖动约束，且和本文的研究场景不同。

综上所述，当前还没有相关工作联合考虑多VNFs实例环境下VNF的动态放置、网络资源约束及网络负载均衡等因素，研究具有严格时延和抖动感知的SFT灵活嵌入和多播路由算法。因此，本文在已有研究基础上，提出一种基于最优链路选择函数进行深度优先搜索构建具有严格时延和抖动约束的多播SFT嵌入算法。具体内容为：

(1)联合考虑VNF动态放置，多资源约束(包括SDN交换机的转发表容量、链路的带宽、功能节点的CPU容量)及网络负载均衡因素正式定义并用ILP模型刻画了延迟和抖动感知的动态SFT嵌入和路由问题(the Delay and Jitter Aware Dynamical SFT embedding and Routing Problem, DJA-DSRP)。(2)设计辅助边权图，将资源消耗及时延指标转化为边权图中的权值降低问题复杂性，提出最优链路选择函数构建SFT嵌入算法(SFT-EA)求解原问题。(3)将提出的SFT-EA算法与现有算法进行性能对比，结果表明SFT-EA不仅较优地解决了多资源及时延和抖动联合约束下的多播SFT嵌入问题，且在流接受率、网络吞吐量和负载平衡方面具有更好的性能。

2.   系统模型

2.1   物理网络

将SDN/NFV网络表示为$G = \left( {N,L} \right)$，其中$N,L$分别表示节点和链路的集合。用$u,v \in N$和$< u,v > \in L$分别表示物理节点和物理链路，为方便起见，后文用$uv \in L$表示物理链路。网络中有两种节点类型，一种是负责转发数据的交换节点${N}_{s}\in N$，另一种是由一台或多台服务器组成的功能节点${N}_{f}\in N$，$N={N}_{s}\cup {N}_{f}$。$G$中有一台SDN控制器，为每条多播请求流执行动态的VNF放置和路由路径选择。图2为网络示例，其中节点${v_1},{v_3},{v_4}$为功能节点，其余为交换节点。

图 2  SDN/NFV网络示例

下载: 全尺寸图片 幻灯片

用${\text{M}}{{\text{R}}_i}$表示第$i$条具有SFC请求的多播流。其中$i$为整数。当路由${\text{M}}{{\text{R}}_i}$时，在节点$u$上，流表容量和剩余流表项的比率用$C_u^{{\text{ft}}}$和$r_{i,u}^{{\text{ft}}}$表示。用$C_u^{{\text{cpu}}}$和$r_{i,u}^{{\text{cpu}}}$表示节点$u$上的CPU容量和剩余比率。物理链路${\text{uv}} \in L$的带宽容量、剩余带宽比率、传输时延分别用$C_{{\rm{uv}}}^{{\text{bw}}}$, $r_{i,{\rm{uv}}}^{{\text{bw}}}$, $\delta _{{\rm{uv}}}^{{\text{delay}}}$表示。用$\eta (u)$表示节点$u$的邻居节点集合。

2.2   虚拟网络功能

网络中可能的VNF类型用集合$P$表示。每种VNF类型$p$都有特定的部署成本、CPU需求、处理延迟，分别表示为${D_p}$, $k_p^{{\text{cpu}}}$, $\delta _p^{{\text{delay}}}$。具有SFC要求的多播流请求${\text{M}}{{\text{R}}_{{i}}}$表示为

${s_i}\;$和${D_i}$分别表示源节点和目的节点集， ${\text{S}}{{\text{C}}_i} = \left\{ {{\text{S}}{{\text{C}}_i}(1)} \right.,{\text{S}}{{\text{C}}_i}(2),\; \cdots ,\left. {{\text{S}}{{\text{C}}_i}(l)} \right\}$表示${\text{M}}{{\text{R}}_i}$中每个源目的对必须升序遍历的VNF 集合，即SFC，$l = \left| {{\text{S}}{{\text{C}}_i}} \right|$为SFC的长度，即${\text{M}}{{\text{R}}_i}$中每个源目的对需要经过的VNF实例总数。其中$R_i^{{\text{bw}}}$, $R_i^{{\text{cpu}}}$, $R_i^{{\text{Delay}}}$, $R_i^{{\text{Jitter}}}$分别表示带宽需求、CPU需求、任意源目的对节点的最大容忍延迟和最大容忍抖动。

为处理顺序约束，使用有向无环服务功能图${\bar G_i} = \left( {{{\bar N}_i},{{\bar L}_i}} \right)$来描述有序的VNF序列${\text{S}}{{\text{C}}_i}$。其中${\bar N_i}$表示入口节点、VNF节点、出口节点集合，${\bar L_i}$表示这些节点之间的路径，分别用$\overline{u},\overline{v}\subset {\overline{N}}_{i}$, $\overline{u}\text{ }\overline{v}\subset {\overline{L}}_{i}$表示${\bar G_i}$上的两个节点$\bar u$和$\bar v$以及它们之间的链路。图1展示了一颗多播服务功能树，在到达目的节点之前，多播流必须遍历由3个VNFs 组成的服务链：即SFT 中的FW, IDS 和IPS。

定义${\eta _i}\left( {{{\bar u}_1}} \right)$来表示${\bar u_1} \in {\bar N_i}$的邻居节点。

2.3   问题定义

在SDN/NFV中，延迟和抖动感知的多播服务功能树动态嵌入和路由问题(DJA-DSRP) 是为${\text{M}}{{\text{R}}_i}$寻找或构建一颗多播树SFT，满足各链路带宽，流表容量和CPU资源约束的同时，任何一条源目的节点对的端到端延迟和任意源目的对路径之间的最大时延抖动分别不大于给定的阈值${R}_{i}^{\text{delay}}$和${R}_{i}^{\text{Jitter}}$，且多播树的实现代价最小并可以自动保证网络的负载均衡。

2.4   问题刻画

2.4.1   物理网络转换

在实际网络中，各功能节点允许部署的VNF类型可能不同。为了方便地表达这个约束并降低问题的复杂性，将通过枚举的方式将原来的物理网络转换成一个扩展的伪网络。即根据一种类型的VNF$p$的CPU需求和功能节点的CPU容量，列举所有可以部署在每个功能节点${N}_{{\rm{f}}}$上的VNF。这些枚举的VNF称为伪VNF，它们的集合记作$M$。用$m \in M$表示第$m$个VNF，用$r_{i,m}^{{\text{cpu}}}$表示路由${\text{M}}{{\text{R}}_i}$时，第$m$个VNF上剩余CPU的比率。假如VNF m的类型为$p$时，定义函数$\tau \left( m \right)$返回VNF$m$的类型

2.4.2   相对成本的定义

$G$中资源使用的一个重要特征是，边际成本会随着资源负载的增加而非线性膨胀。比如，与轻负载链路相比，重负载链路将花费更多的成本来处理传入的网络数据包^[2]。为了描述这一特性且自动保证网络资源负载均衡，利用相对成本来刻画资源的使用成本并将链路带宽、交换节点和VNF上CPU资源的相对代价分别定义为

其中，${\omega _{{\text{bw}}}}$, ${\omega _{{\text{ft}}}}$和${\omega _{{\text{cpu}}}}$均为大于1的常数，$r_{{\rm{uv}}}^{{\text{bw}}}$,$r_u^{{\text{ft}}}$和$r_m^{{\text{cpu}}}$分别为链路上带宽资源、交换节点上流表资源和VNF上CPU资源的剩余率。

2.4.3   ILP模型

确保在部署新的VNF实例$m$时不会违反CPU容量限制，则需满足

其中0,1变量$x_m^u = 1$表示VNF$m$的实例部署在节点$u$上，否则$x_m^u = 0$，$y_m^u = 1$表示功能节点$u$上可以部署VNF$m$，否则$y_m^u = 0$，$k_m^{{\text{cpu}}}$表示部署VNF$m$所需的CPU资源量。

为确保交换节点上的流表容量约束，需满足式(10)。用0,1变量$z_{i,d,u}^{{{\bar {{u}}\bar {{v}}}}} = 1$来表示${\text{M}}{{\text{R}}_i}$到达目的节点$d \in {D_i}$时，${{\bar {{u}}\bar {{v}}}} \in \overline {{L_i}}$是经过节点$u$的，否则$z_{i,d,u}^{{{\bar {{u}}\bar {{v}}}}} = 0$。

为确保不会违反物理链路上的带宽容量约束，式(11)应被满足。其中$R_{i,{\rm{uv}}}^{{{\bar {{u}}\bar {{v}}}}}$表示${{\bar {{u}}\bar {{v}}}}$通过物理链路${{uv}}$的带宽。

值得注意的是，每个源目的对必须由SFT中的一个SFC服务。由于多播的多路复用特性，流在到达目的节点前可能经过相同的VNF 实例。因此，使用式(12)来保证面向每个目的节点的流只访问SFT中同类型的VNF 1次。

其中$\theta _{d,u}^m$为0,1变量，$\theta _{d,u}^m = 1$表示流向目的节点$d$的流是在功能节点$u$上获得 VNF$m$的服务，否则$\theta _{d,u}^m = 0$。使用以下约束来确保流向每个目的节点的流只能从源节点流出。

为了保证流的守恒和严格的顺序要求，需满足

其中，0,1变量$z_{i,d,{\rm{uv}}}^{{{\bar {{u}}\bar {{v}}}}} = 1$表示${\text{M}}{{\text{R}}_i}$到达目的节点$d \in {D_i}$时，${{\bar {{u}}\bar {{v}}}} \in \overline {{L_i}}$经过物理链路${{uv}}$,否则$z_{i,d,{\text{uv}}}^{{{\bar {{u}}\bar {{v}}}}} = 0$。

使用0,1变量$\varphi _{i,{\rm{uv}}}^{{{\bar {{u}}\bar {{v}}}}} = 1$表示流向每个目的节点的${\text{M}}{{\text{R}}_i}$通过链路${{uv}}$来获得$\bar u$和$\bar v$的服务，否则$\varphi _{i,{\rm{uv}}}^{{{\bar {{u}}\bar {{v}}}}} = 0$。因此，需满足约束

用$D_i^t$来表示${\text{M}}{{\text{R}}_i}$从${s_i}$经过SFT到$t \in {D_i}$的延迟

其中${\text{δ }}_{i,d{{,{\rm{uv}}}}}^{{\text{delay}}}$和${\text{δ }}_{i,d{{,{\rm{t}}(\bar {\rm{u}})}}}^{{\text{delay}}}$分别表示从${s_i}$到$d$的流在链路${\rm{uv}}$上的传播延迟和VNF上的处理延迟，函数$\tau (\bar u)$负责返回$\bar u$的VNF类型。以下约束确保${\text{M}}{{\text{R}}_{\text{i}}}$的任何源目的节点之间端到端的延迟满足阈值

此外，为确保${\text{M}}{{\text{R}}_i}$中任意源目的地对不违反最大时延抖动，需满足

综上，构建多播树的成本计算为

优化问题为

min 式(19)

s.t. Eq.(8)—(15), (17)—(18)

3.   启发式优化算法

由于在网络中嵌入多播服务功能树是NP难的^[13]，为降低问题求解复杂度，将功能节点中的CPU资源消耗和转发节点中流表资源消耗转化为边上的权值进行表示。因此，本节将$G$转化为辅助边权图$G_i^\prime$，然后再将$G_i^\prime$转换为具有相对成本的VNF分裂多阶段边权图${\hat G_i}$，最后基于${\hat G_i}$利用启发式算法对问题进行求解，具体过程如下。

3.1   辅助边权图构建

辅助边权图$G'_i = \left( {V'_i\;,E'_i\;;{w_{i,{e'}}}} \right)$的构造：将每个交换节点$v \in {N_s}$拆分为两个节点，记作$v'$和$v''$，并将它们添加到${V_i}^\prime$中。然后向${E_i}^\prime$添加一条有向边$\left\langle {v',v''} \right\rangle$。对于功能节点中的每个VNF$m$，将$m$分裂成两个节点$m'$和$m''$，并将它们添加到${V_i}^\prime$中，有向边$\left\langle {m',m''} \right\rangle$被添加到边集${E_i}^\prime$。为保证一致性，在$m''$和$m'$之间增加一条高速链路，不考虑这条链路的容量和延迟约束。对于每条链路${{{\rm{uv}}}} \in L$，为${E_i}^\prime$添加一条边$\left\langle {u'',v'} \right\rangle$，图3为构造$G_i^\prime$的示例。

图 3  辅助边权图$G_i^\prime$的构造

下载: 全尺寸图片 幻灯片

按式(20)和(21)为${e^\prime } \in E_i^\prime$分配成本和延迟权重，特别地，假如${\text{ }}{e^\prime } = \left\langle {{m^\prime },{m^{\prime \prime }}} \right\rangle \in E_i^\prime \;, \;\hat y_m^a = 0,y_m^a = 1$，表明VNF$m$是新部署的，则$\omega _{i,{e^\prime }}^{{\text{cost}}} = {({\omega _{{\text{cpu}}}})^{1 - r_{i,m}^{{\text{cpu}}}}} + {D_{\tau (m)}}$，由于VNF$m$在一个功能节点上，将$\left\langle {m'',m'} \right\rangle$的成本权重设置为0。由于软硬件的性能越来越好，将边$\left\langle {{v^\prime },{v^{\prime \prime }}} \right\rangle$的延迟权重设为0。

3.2   多阶段边权图构建

为确保${\text{M}}{{\text{R}}_i}$中每条源目的候选路由路径满足预定义的VNF顺序要求，进一步将$G'_i$转换为一个由入口节点、满足严格顺序约束的候选VNF实例和出口节点组成的有向无环图${\hat G_i} = \left( {{{\widehat V}_i},{{\widehat L}_i}\;;{w_{i,\hat e}}} \right)$，其中$\hat u,\hat v \in {\widehat V_i}$表示两个节点，$\hat e = \left\langle {\hat u,\hat v} \right\rangle \in {\widehat L_i}$和${w_{i,\hat e}}$分别表示链路和边的权重。通过以下两个阶段来构造${\hat G_i}$。

第1阶段是查找${\text{M}}{{\text{R}}_i}$所需的所有VNF节点，并将它们按照预定义的顺序排列并进行分裂。第2阶段是生成链路。首先，把入口节点${s_i}$与${\text{S}}{{\text{C}}_i}{(1)'}$列中的所有节点连接起来，然后将${\text{S}}{{\text{C}}_i}{(1)'}$列中的节点$\hat u'$与${\text{S}}{{\text{C}}_i}{(1)^{''}}$列中的节点$\hat u''$一一连接。接着将${\text{S}}{{\text{C}}_i}{(1)^{''}}$列中的每个节点$\hat u''$与${\text{S}}{{\text{C}}_i}{(2)'}$中所有节点$\hat u'$一一连接。接下来，依次执行相同的操作。最后，将${\text{S}}{{\text{C}}_i}{(l)^{''}}$列中所有节点$\hat u''$连接到$t \in {D_i}$。并且${D_i}$中的目的节点是相互连接的。图4为一个示例。

图 4  在图${\hat G_i}$中解决DJA-DSPR

下载: 全尺寸图片 幻灯片

在${\hat G_i}$中，将每条链路的成本和延迟权重按以下公式进行设置，其中${p_i}({u{''}}{v'})$表示$G'_i$中两个节点之间的最短路径。

3.3   启发式算法SFT-EA

基于$G$,$G'$和${\hat G_{}}$之间的关系，网络中资源消耗的相对成本都被转换为$\hat G$上的链路进行表示。由于${\text{M}}{{\text{R}}_i}$的所有候选VNF实例都按预定顺序放置在$\hat G$上，因此，原问题转化为在$\hat G$上找一棵满足式(24)的多播树。用${T_i} = \left\{ {V_i^T,E_i^T} \right\}$表示该多播树，其中$V_i^T \supseteq \{ {s_i}\} \in {D_i}$，相邻节点之间的链路记为$\hat e = \left\langle {\hat u,\hat v} \right\rangle \in {\widehat L_i}$, $d(\hat e) = w_{i,\hat e}^{{\text{delay}}}$表示链路$\hat e$上的延迟， ${\hat p_i}({s_i},\hat u)$表示${T_i}$上从源节点${s_i}$到节点$\hat u$的路径。${s_i}$到节点$\hat u$的延迟用$D(\hat u)$表示

基于以下思路设计服务功能树嵌入算法(Service Function Tree Embedding Algorithm, SFT-EA)来解决式(24)。定义${\Delta _T} \in {R^ + }$为实际多播树${T_i}$中源目的对路径的最大延迟，即

显然，

此外，如果$\hat u \in {D_i}$，称$\hat u$为目的节点；如果$\hat u \notin {D_i}$，但$\hat u \in {T_i}$，则称$\hat u$为中继节点。

将$\displaystyle\sum\nolimits_{\hat e \in {{\hat p}_i}({s_i},\hat v)} d (\hat e)$表示为$D(\hat u) + d(\hat u,\hat v)$，根据式(25)可以得到

显然，

根据式(27)、 式(28)可以得到

首先使用KruskalMST最小生成树算法计算${\hat G_i}$上的最小时延树(LDT) ${T_{{\text{LDT}}}}$，假设${T_{{\text{LDT}}}}$上每个源目的对之间路径的最大延迟为${D_{{\text{max}}}}$，则有${D_{{\text{max}}}} \le {\Delta _T}$。另外，$R_i^{{\text{Jitter}}} \le {\Delta _T}$，否则延迟抖动约束无效。为了保证多播树${T_i}$中的源目的对路径满足实际的时延和时延抖动要求，结合式(26)，可以得到${\Delta _T}$的取值范围为

SFT-EA的主要思想是在${\Delta _T}$的范围内从小到大取值，将每一个值作为当前构造的多播树中路径的时延上限。算法首先初始化一棵只包含多播源节点的多播树，然后逐个贪婪地加入${\hat G_i}$中的节点。在节点加入的过程中，使用式(31)中定义的最佳链路选择函数来选择具有最小值的节点$\hat v$，并将该节点对应的边添加到当前多播树${T_i}$中，然后，将$\hat v$作为当前节点，重复上述过程。如果找不到符合条件的节点$\hat v$，则回溯到当前节点的父节点并继续上述过程。最后，若在${\Delta _T}$时延范围内找不到包含所有目的节点的多播树，则多播树构造失败，结束算法。

在式(31)中，$f(\hat u,\hat v) = \dfrac{{\omega _{i,\hat u,\hat v}^{{\text{cost}}}}}{{{\Delta _T} - D(\hat u) - d(\hat u,\hat v)}} + \dfrac{{{\Delta _T} - D(\hat u) - d(\hat u,\hat v)}}{{\omega _{i,\hat u,\hat v}^{{\text{cost}}}}}$

SFT-EA算法的伪代码如算法1：

算法1 SFT-EA算法
输入： $G(N,L)$，流请求${\text{M}}{{\text{R}}_i}$，资源容量，资源剩余率，最大迭 　代次数$K$。
输出：多播树$T$。
1. 根据2.4.1枚举$G$中功能节点上所有可能的VNFs
2. 根据3.1构造$G_i^\prime$
3. 基于$G_i^\prime$构造${\hat G_i}$
4. 求最小时延树${T_{{\text{LDT}}}}\leftarrow$KruskalMST(${\hat G_i}$)
5. if${D_{ {\text{max} } } }\;{\rm{in}}\;{T_{ {\text{LDT} } } } > R_i^{ {\text{delay} } }$则算法结束
6. else
7. while$(({\Delta _T} \in [\max \left\{ {{D_{\max }},R_i^{{\text{jitter}}}} \right\},R_i^{{\text{delay}}}])$且$k \le K$)//算法最多迭代$K$次
8. ${T_i} \leftarrow s;V[\hat u] = 0;L[\hat u][\hat v] = 0;V[s] = 1$，//数组$V$和$L$分别用于记录节点和链路是否已被访问
${{Pre} }({{s} }) = \emptyset ;\hat u = {\text{s} };{\Delta _T} = \max \left\{ { {D_{\max } },R_i^{ {\text{jitter} } } } \right\}$//$pre()$函数表示一个节点的前驱
9. 　while $L[\hat u][\hat v] \ne 1$
10. 　　if $\hat v \notin {D_i} \cup \{ s\}$ and $D(\hat u) + d(\hat u,\hat v) \leqslant {\Delta _T}$
11. 　　$N = N \cup \{ \hat v\}$//$N$记录候选节点
12. 　　else if $\hat v \in {D_i}$且${\Delta _T} - R_i^{ {\text{Jitter} } } \le D(\hat u) + d(\hat u,\hat v) \le {\Delta _T}$
13. $N = N \cup \{ \hat v\}$
14. 　　end if
15. 　　　if $N \ne \emptyset$
16. 　　　　for each $\hat v \in N$
17. 　　　　　if $D(\hat u) + d(\hat u,\hat v) = = {\Delta _T}$
18. 　　　　　　if $\hat v \in {D_i}$
19. 　　　　　$V[\hat v] = 1;L[\hat u][\hat v] = 1;{T_i} = {T_i} \cup \{ \hat v\}$
20. 　　　　　else $L[\hat u][\hat v] = 1$
21. 　　　　end if
22. 　　　　else if $D(\hat u) + d(\hat u,\hat v) < {\Delta _T}$
23. 选择$f(\hat u,\hat v)$中最小的节点$\hat v$
24. 　　　　${T_i} = {T_i} \cup \{ \hat v\} ;V[\hat v] = 1;L[\hat u][\hat v] = 1;Pre(\hat v) = \hat u$; 　　　　　　 $\hat u = \hat v;L[\hat u][\hat v] = 0;$
25. 　　　　end if
26. 　　　end for
27. 　　　else 将$L[\hat u][\hat v]$为0的链路设置为1，$\hat u = pre(\hat u)$
28. 　　end if
29. 　　end while
30. for each $\hat v \in {D_i}$
31. if 所有$V[\hat v] = = 1$ 则转到36
32. else ${\Delta _T} + + ;k + +$;break;
33. end if
34. end for
35. end while
36. if ${T_i}$包含${D_i}$中的所有目的节点
37. 通过将${T_i}$中的每条边替换为其在$G$中对应的路径来映射多播 　树$T$，并更新$r_{i,{\rm{uv}}}^{ {\text{bw} } }\;,r_{i,u}^{ {\text{ft} } }\;,r_{i,u}^{ {\text{cpu} } }$和$r_{i,m}^{{\text{cpu}}}$
38. else 路由失败，${\text{M}}{{\text{R}}_i}$请求被拒绝，Return
39. end if
40. end if

下载: 导出CSV 

| 显示表格

定理1　SFT-EA的时间复杂度为$O(K|N{|^3})$。

证明　执行SFT-EA时，枚举VNF的时间复杂度为$O(|{V_f}|)$。计算${G'}$中链路和节点的相对成本的复杂度为$O(|{V_s}| + |M| + |L|)$。最坏情况下，所有类型的VNF实例都可以部署在每个功能节点上，将执行$\left| {{V_f}} \right| + (l - 1){\left| {{V_f}} \right|^2} + \left| {{V_f}} \right|\left| {{D_i}} \right|$次SP算法为$\hat G$生成链路，通常是${V_f} < < {D_i}$，因此执行SP算法的次数约为$\left| {{V_f}} \right|\left| {{D_i}} \right|$。${G'}$上SP的复杂度为$O(|L| + |V|\log |V|)$，$\hat G$最多有$2l\left| {{V_f}} \right| + 1 + {D_i}$个节点和$(l - 1){\left| {{V_f}} \right|^2} + l\left| {{V_f}} \right| + \left| {{V_f}} \right| + \left| {{V_f}} \right|\left| {{D_i}} \right|$条链路，因此，建立$\hat G$的时间复杂度是：$O(\left| {{V_f}} \right|\left| {{D_i}} \right|(|(l - 1){\left| {{V_f}} \right|^2} + l\left| {{V_f}} \right| + \left| {{V_f}} \right| + \left| {{V_f}} \right|\left| {{D_i}} \right||| + |(2l$$\left| {{V_f}} \right| + 1 + {D_i})|{\log _2}|(2l\left| {{V_f}} \right| + 1 + {D_i})|))$=$O(|{V_f}{|^2} |{D_i}{|^2}$$+ |{D_i}{|^2}|{V_f}|{\log _2}|{D_i}|)$。KruskalMST计算${T_{{\text{LDT}}}}$的复杂度为$O({V^2}) = O((2l\left| {{V_f}} \right| + 1 +$${D_i}{)^2}) = O({D_i}^2)$，在算法中(第10～27行)，当没有回溯时，时间复杂度为$O({V^2})$，当有回溯时，时间复杂度为$O({V^3})$。用于确定是否访问了所有目的地节点的时间复杂度为$O({D_i})$(第30～34行)，在最坏情况下，SFT-EA将迭代$K$次，路径映射和资源更新的复杂度为$O(1)$。$l$的值很小。因此，SFT-EA的算法复杂度是$O(K((|{V_f}|) + (|{V_s}| + |M| + |L|) + (|{V_f}{|^2}|{D_i}{|^2} + |{D_i}{|^2}$$|{V_f}||{\log _2}|{D_i}|)$=$O$$(K|{D_i}{|^3})$。在最坏的情况下，网络中除源节点外的所有节点都是多播目的节点，所以，SFT-EA的复杂度为$O(K|N{|^3})$。 证毕

图4中的红色粗线给出了具有3个目的节点和3个VNF顺序请求SFT的算法运行示例。

4.   性能仿真分析

4.1   仿真设置

在Intel(R) Core(TM) i7-8550U CPU @ 1.80 GHz, 32.0 GB RAM的计算机上，用NetworkX3.1 Library^[20]生成 Palmethone网络^[21]对提出的算法进行评估。网络中，选择按节点度降序排序的30%的节点作为功能节点。考虑6种类型的VNFS ^[2]。${D_p}$的取值为Uniform[0,10]×$R_i^{{\text{cpu}}}$。每条链路的带宽(Gbps)为Uniform[1,10]。交换节点的流量表容量设置为800个单元^[2]，功能节点上的CPU容量设置为8000MIPS。$\delta _p^{{\text{delay}}}$(ms)设为Uniform[0.002,0.003] ×$R_i^{{\text{cpu}}}$，链路的延迟(ms)为Uniform[2,5] ^[2]。${w_{{\text{bw}}}}, {w_{{\text{ft}}}},{w_{{\text{cpu}}}}$设置为2|V|^[11]。

对于每条多播流，从目标网络中随机选择源节点和目的节点。为了评估多播规模的影响，将|D|/|V|值设置为0.3，$R_i^{{\text{bw}}}$(Mbps)为Uniform[10,120]^[13]。$R_i^{{\text{cpu}}}$(MIPS)为Uniform[0,10] ×$R_i^{{\text{bw}}}$，$R_i^{{\text{delay}}}$(ms)为Uniform [50,100]，$R_i^{{\text{jitter}}}$(ms)为Uniform[30,50] ^[2]。此外，将SFC的长度和SFT-EA的迭代最大次数$K$分别设置为4和10。取30次实验结果的平均值作为结果输出。

4.2   对比算法

选用SDN/NFV网络架构中与本文研究方向紧密相关且最新的对比算法进行仿真对比。

(1)STB^[22]：用传统经典的Steiner树算法构造一个覆盖多播所有目的节点的Steiner树，并找到将源节点连接到该树的最小代价路径。然后沿着该路径嵌入所需的SFC。STB只考虑链路和节点资源的成本；

(2)TSA^[13]：通过考虑链路和节点资源成本得到SFC嵌入的初始方案，然后通过添加新的VNF实例逐步构建多播服务功能树(SFT)，该算法不考虑流表成本及路径抖动约束；

(3)HAJPR^[16]：根据网络中的关键NFV节点构造多径多播树，并且考虑物理资源和延迟约束，不考虑抖动约束，且没有解决VNF的动态嵌入。

4.3   性能比较

图5为平均流接受率的比较。SFT-EA的性能最好。当传入MRs的数量为5000时，它接受的MR比HAJPR多约6%，比TSA高约13%，比STB高约17%。在SFT-EA中，实现了VNF的动态放置和负载均衡，提供了更好的性能。HAJPR考虑多路径路由，其性能优于TSA和STB。

图 5  平均流接受率

下载: 全尺寸图片 幻灯片

图6展示了平均吞吐量的比较。当MR的数量为4000时，SFT-EA的吞吐量比HAJPR高约5 Gbps，比TSA高约14 Gbps，比STB高约20 Gbps。性能和流接受率相符。

图 6  平均吞吐量

下载: 全尺寸图片 幻灯片

图7展示了当4000条MRs进入网络时链路平均剩余带宽的累积分布。从图中可看出，STB和TSA有大约5%和3%的瓶颈链路。对于SFT-EA，剩余带宽为6G和3G的链路分别约占71%和17%，因此，网络中约有54%的链路剩余带宽在3 Gbps到6 Gbps之间，对于HAJPR, TSA和STB，其剩余带宽在3 Gbps到6 Gbps之间的链路分别约为51%、32%和27%。显然，SFT-EA中使用指数函数来表示链路带宽成本，使其对链路资源的利用比其他算法更加均衡。

图 7  剩余带宽累积分布

下载: 全尺寸图片 幻灯片

图8描述了4000条MRs进入网络时平均剩余流表条目的累积分布。可以看到，TSA和STB有大约3%和5%的交换节点瓶颈。从图中剩余流表条目为400个单位看，STB大约有60%的交换机节点，其剩余流表条目小于400个单位，TSA为49%，HAJPR为35%，SFT-EA为30%， SFT-EA算法的性能优于其他算法。

图 8  剩余流表累积分布

下载: 全尺寸图片 幻灯片

图9显示了当4000条MRs进入网络时，功能节点上平均剩余CPU的累积分布。由于STB和TSA不能保证功能节点上CPU的均衡使用，分别有约4%和2%的瓶颈节点。对于SFT-EA，剩余CPU为1600 MIP的功能节点大约占10%，剩余CPU为4000 MIPS的功能节点大约占85%，因此，约75%的功能节点的剩余CPU在1600～4000 MIPS，而HAJPR, TSA和STB在这区间的剩余CPU分别约为63%、49%和45%。SFT-EA比其他算法更均衡。

图 9  剩余CPU的累积分布

下载: 全尺寸图片 幻灯片

图10展示了不同长度SFC下流接受率的变化。由于MR消耗的网络资源随着SFC长度的增加而增加，因此，流接受率随SFC长度的增加而降低。因STB和TSA无法平衡带宽、流表和CPU资源的利用率，因此它们的性能较差。虽然HAJPR不考虑资源平衡，但由于采用多径路由，且不考虑时延抖动约束，因此性能略高于SFT-EA。

图 10  平均流接受率随SFC长度的变化

下载: 全尺寸图片 幻灯片

图11显示了不同比例功能节点下网络的平均流接受率。功能节点的比例越高，可以动态部署VNF实例的节点就越多，MR可以选择冗余的VNF实例来满足其预定顺序，因此，这些算法的平均流接受率就越高。同理，虽然HAJPR不考虑资源平衡，但由于采用多径路由，且不考虑时延抖动约束，因此性能略高于SFT-EA。

图 11  不同功能节点数下的平均流接受率

下载: 全尺寸图片 幻灯片

图12给出了多播目的节点数$|D| \in [5,25]$时，算法的运行时间比较，随着多播目的节点数的增加，4种算法的执行时间都会增加。因SFT-EA需要考虑抖动约束，算法运行时间约高于HAJPR。

图 12  不同目的节点数下算法的执行时间

下载: 全尺寸图片 幻灯片

5.   结束语

本文基于SDN/NFV架构，研究了延迟和抖动感知的多播服务功能树嵌入和路由问题。首先将其建模为ILP模型。然后，利用节点分裂，将节点资源成本转换为边的思想，并设计了一个最优链路选择函数和基于辅助边权图的SFT嵌入算法SFT-EA来解决该问题。最后通过实验仿真对算法的性能进行了评价。结果表明，所提算法在吞吐量、流接受率和网络负载均衡方面比现有算法有更好的性能，为虚拟网络环境下具有延迟和抖动约束的多播流调度提供了有价值的参考。