近年来，网络虚拟化^[1]作为解决网络僵化问题的关键技术受到广泛关注。它允许多个异构的虚拟网络共享底层网络资源，打破了传统网络体系结构的桎梏，为用户提供了更加灵活的服务，同时大大提高了网络资源利用效率。现已成为下一代互联网实现的关键候选技术之一。

虚拟网络映射作为虚拟网络技术实现的核心，受到高度关注^[2–4]。在提高虚拟网络映射效率方面，Yu等^[5]提出一种基于贪婪思想的节点映射算法，该算法在节点映射阶段仅考虑自身CPU资源与邻接带宽资源，未考虑网络拓扑属性。Wang等^[6]在节点排序中考虑中心度指标，从全局拓扑的角度提高虚拟网络映射性能，但因未考虑资源指标，所以算法性能受限。Gong等^[7]在考虑信任关系的基础上，将资源指标和节点中心度引入虚拟节点映射过程，综合了资源和全局拓扑指标，提升了算法性能。综上所述，上述算法均选取资源以及全局拓扑中单一或者多个指标提升虚拟网络映射效率，但是均未从局部拓扑角度进行深入研究，且未考虑底层物理节点的可靠性。

随着网络虚拟化技术研究的深入，虚拟网络生存性与可靠性成为研究热点之一。相关学者重点探讨了虚拟网络生存性模型、生存性增强方法以及故障恢复问题^[8–11]。以上文献均在虚拟网络节点映射阶段假设物理节点可靠，仅研究在虚拟网络出现故障之后如何更好地恢复，但因网络故障导致的损失却无法挽回。现实中，物理节点并非完全可靠，尤其是近年来底层网络基础设施失效事故频发，所以，提高虚拟网络映射效率的同时，在虚拟网络节点映射阶段选择可靠物理节点进行映射，可以降低虚拟网络故障概率，防患于未然。Miao^[12]、Liu^[13]等分别利用最近一次故障时刻、节点发生故障次数对物理节点可靠性进行定量评估，提出了相应的节点可靠性评估方法，但是仅考虑单一因素的节点可靠性评估方法存在较大片面性。

综上所述，现有虚拟网络映射算法忽视了局部网络拓扑对虚拟网络映射效率的影响，容易导致虚拟节点稀疏分布于底层网络，增加虚拟链路的映射成本，从而降低虚拟网络映射成功率，同时在虚拟网络可靠性方面，不考虑或者仅考虑单一节点可靠性因素，缺乏对物理节点可靠性的全面合理评估。针对上述问题，作者提出一种节点可靠感知的高效虚拟网络映射（reliability-aware efficient virtual network embedding，RA-EVNE）算法。首先，提出一种新的节点重要度排序方法，综合考虑全局和局部拓扑因素，使映射在底层网络中的虚拟节点分布更加集中，减少虚拟链路映射的资源消耗；其次，提出物理节点可靠性度量方法，分析影响物理节点可靠性的多种指标，使度量结果更加全面合理；之后，结合节点重要度与物理节点可靠度提出物理节点可靠重要度并将其作为物理节点的排序依据；最后，按照虚拟节点和物理节点排序结果进行虚拟节点映射，再从物理网络选取合适的物理链路进行虚拟链路映射。

1 网络模型与评价指标 1.1 网络模型

1）物理网络

物理网络用带权无向图 ${G_{{s}}} = \left( {{N_{{s}}},{E_{{s}}}} \right)$ 表示，其中， ${{N_{{s}}}}$ 与 ${{E_{{s}}}}$ 分别表示物理网络节点和链路集合。物理节点 ${{n_{{s}}}}$ 的基本属性有可用CPU资源 $cpu\left( {{n_{{s}}}} \right)$ ，地理位置属性 $loc\left( {{n_{{s}}}} \right)$ 和物理节点可靠度 $R\left( {{n_{{s}}}} \right)$ 。物理链路 ${{e_{{s}}}}$ 的基本属性为物理链路可用带宽资源 $bw\left( {{e_{{s}}}} \right)$ 。

2）虚拟网络

与物理网络类似，虚拟网络使用带权无向图 ${G_{{v}}} = \left( {{N_{{v}}},{E_{{v}}}} \right)$ 表示，其中， ${{N_{{v}}}}$ 与 ${{E_{{v}}}}$ 分别表示虚拟网络节点和链路集合。虚拟节点 ${{n_{{v}}}}$ 的基本属性有CPU资源需求 $cpu\left( {{n_{{v}}}} \right)$ 和地理位置需求 $loc\left( {{n_{{v}}}} \right)$ 。虚拟链路 ${e_{{v}}}$ 的基本属性为虚拟链路带宽资源需求 $bw\left( {{e_{{v}}}} \right)$ 。

3）虚拟网络映射

虚拟网络映射包括节点映射和链路映射两个阶段。图1给出了虚拟网络映射的一个可行方案，虚拟网络请求的节点映射方案为 $\left\{ {{ a} \to { A},\;{ b} \to { C},\;{ c} \to { D}} \right\}$ ，链路映射方案为 $\left\{ {\left( { a,b} \right) \to \left( { A,C} \right),\left( { a,c} \right) \to \left( { A,D} \right)},\;\left( { b,c} \right) \to \right.$ $ {\left( { C,D} \right)}$ }。

1.2 评价指标

1）映射成功率

虚拟网络映射成功率可定义为：

${\eta _{{{suc}}}} = \mathop {\lim }\limits_{T \to \infty } \frac{{NU{M_{{{vsuc}}}}}}{{NU{M_{{v}}} + \delta }}$

(1)

式中， $NU{M_{{{vsuc}}}}$ 和 $NU{M_{{v}}}$ 分别表示 $T$ 时间内成功映射的虚拟网络总数和到达的虚拟网络映射请求总数， $\delta $ 为无限接近于0的常数。

2）收益与开销

对于虚拟网络请求 ${G_{{v}}} = \left( {{N_{{v}}},{E_{{v}}}} \right)$ ，在 $t$ 时刻的收益 $R\left( {{G_{{v}}},t} \right)$ 与开销 $C\left( {{G_{{v}}},t} \right)$ 分别定义为：

$R({G_{{v}}},t) = \alpha \sum\limits_{{n_{{v}}} \in {N_{{v}}}} {cpu({n_{{v}}})} + \sum\limits_{{e_{{v}}} \in {E_{{v}}}} {bw({e_{{v}}})} $

(2)

$C({G_{{v}}},t) = \beta \sum\limits_{{n_{{v}}} \in {N_{{v}}}} {cpu({n_{{v}}})} +\sum\limits_{{e_{{v}}} \in {E_{{v}}}} {\sum\limits_{p \in {P_{{s}}}({e_{{v}}})} {hops(p)bw({e_{{v}}})} } $

(3)

式中：参数 $\alpha $ 、 $\beta $ 分别为节点与链路资源的比重参数，二者均设置为1； ${P_{{s}}}\left( {{e_{{v}}}} \right)$ 为给虚拟链路 ${{e_{{v}}}}$ 分配的路径集合； ${hops\left( p \right)}$ 为路径 $p$ 在物理网络上经过的跳数。

通常，利用长期平均收益与开销来表征网络稳定状态下收益与开销性能，长期平均收益 $R\left( {{G_{{s}}}} \right)$ 与开销 $C\left( {{G_{{s}}}} \right)$ 表示为：

$R({G_{{s}}}) = \mathop {\lim }\limits_{T \to \infty } \frac{{\displaystyle\sum\limits_{t = 0}^T {R({G_{{v}}},t)} }}{T}$

(4)

$C({G_{{s}}}) = \mathop {\lim }\limits_{T \to \infty } \frac{{\displaystyle\sum\limits_{t = 0}^T {C({G_{{v}}},t)} }}{T}$

(5)

长期平均收益开销比可定义为：

$\xi = \frac{{R({G_{{s}}})}}{{C({G_{{s}}})}} = \frac{{\mathop {\lim }\limits_{T \to \infty } \displaystyle\sum\limits_{t = 0}^T {R({G_{{v}}},t)} }}{{\mathop {\lim }\limits_{T \to \infty } \displaystyle\sum\limits_{t = 0}^T {C({G_{{v}}},t)} }}$

(6)

3）虚拟网络易损率

当物理节点可靠性低于某一阈值时，物理节点处于易损状态，而选择一定数量的易损物理节点进行映射的虚拟网络称为易损虚拟网络。易损虚拟网络可靠性很低，极易发生故障，所以利用虚拟网络易损率来衡量整体虚拟网络可靠性。

虚拟网络易损率可定义为：

$\gamma = \mathop {\lim }\limits_{T \to \infty } \frac{{NU{M_{{{vul}}}}}}{{NU{M_{{v}}} + \delta }}$

(7)

式中， ${NU{M_{{{vul}}}}}$ 为 $T$ 时间内易损虚拟网络总数。

2 节点可靠感知的高效虚拟网络映射算法

虚拟网络映射的本质是NP-hard问题，为了求其最优解，作者提出一种新型启发式算法，即节点可靠感知的高效虚拟网络映射算法。

2.1 节点重要度

节点CPU资源^[5]可表示为：

$NR({n_i}) = cpu({n_i})$

(8)

式中，节点 ${n_i}$ 既可表示物理节点 ${n_{{s}}}$ ，也可表示虚拟节点 ${n_{{v}}}$ 。

1）度中心性^[5]。即与节点相连的所有邻接链路的带宽资源之和，可定义为：

$DC({n_i}) = \sum\limits_{e \in E({n_i})} {bw(e)} $

(9)

式中， $E\left( {{n_i}} \right)$ 为节点 ${{n_i}}$ 的邻接链路集合。

2）节点中心度^[6]。节点中心度从全局拓扑的角度反映了节点重要性，可定义为：

$CC({n_i}) = \frac{1}{{\displaystyle\sum\limits_{{n_j} \in \varPsi (n)} {{d_{ij}}} }}$

(10)

式中， ${{d_{ij}}}$ 表示节点 ${n_i}$ 与 ${n_j}$ 之间的跳数距离。若 ${n_i}$ 为虚拟节点，则 $ \varPsi \left( n \right)$ 为所有待映射虚拟节点，即 $\varPsi \left( n \right) = {N_{{v}}}$ ；若 ${n_i}$ 为物理节点，则 $\varPsi \left( n \right)$ 为满足地理位置约束条件的所有物理节点,即 $ \varPsi \left( n \right) = {N_{{s}}}$ 。节点中心度越大，节点越接近网络中心，节点越重要。

3）物理节点就近距离。定义已被虚拟节点成功映射的物理节点集合为 ${S_{{{suc}}}}$ 。物理节点就近距离定义为当前待映射虚拟节点的候选物理节点 ${n_{{s}}}$ 到已被成功映射的各物理节点 ${n_{{{s}}i}}$ 的距离之和，如式（11）所示：

$LS({n_{{s}}}) = \sum\limits_{{n_{{{s}}i}} \in {S_{{{suc}}}}} {hops({n_{{s}}},{n_{{{s}}i}})} $

(11)

物理节点就近距离从局部拓扑的角度反映了节点重要性。物理节点就近距离越小，候选物理节点距已被映射的物理节点越近，对应虚拟链路占用的带宽资源越少，后续虚拟网络映射成功率越高。

定义1(节点重要度)　物理节点重要度可定义为：

$IR({n_{{s}}}) = \frac{{NR({n_{{s}}}) + DC({n_{{s}}})}}{{LS({n_{{s}}})}} \cdot CC({n_{{s}}})$

(12)

虚拟节点重要度可定义为：

$IR'({n_{{v}}}) = (NR({n_{{v}}}) + DC({n_{{v}}})) \cdot CC({n_{{v}}})$

(13)

2.2 物理节点可靠重要度

虚拟网络映射技术通过抽象、聚合、隔离等，将多个虚拟网络映射在底层公共物理网络上，使物理网络资源的利用更加高效、灵活。但是，如果承载虚拟节点的物理节点发生故障或者性能不稳定，则会对虚拟网络的正常运行造成极大影响。因此对于物理节点，除利用物理节点重要度提高虚拟网络映射效率外，还应考虑物理节点可靠性以保障虚拟网络性能的稳定发挥。

从两方面对物理节点可靠性进行度量，分别是节点自身属性和节点所处环境因素。其中：节点自身属性主要考虑节点使用度，通常新节点可靠性要高于旧节点；节点所处环境因素主要是节点最近一段时间发生故障次数以及最近一次故障时刻。通常某些节点所处环境比较恶劣或者容易损耗、受到攻击等，其发生故障次数会偏多，同时如果最后一次故障刚刚发生，则一定程度上说明节点目前所处的环境可能存在较大安全隐患。

1）物理节点使用度。物理节点的寿命，即平均无故障时间（mean time between failure，MTBF）服从Weibull分布^[14]，可以据此评估物理节点使用度。MTBF的累积分布函数如式（14）所示：

$F(x) = 1 - \exp \left( - {\left(\frac{x}{a}\right)^b}\right),\;\;\;\;x \ge 0{{ }}$

(14)

式中， $a$ 和 $b$ 为Weibull分布的两个参数， $F\left( x \right)$ 越大，物理节点已使用的时间越长，节点可靠性越低。故从物理节点使用度的角度可将物理节点 ${n_{{s}}}$ 的可靠度定义为：

$UR({n_{{s}}}) = \exp \left( - {\left(\frac{x}{a}\right)^b}\right),\;\;\;\;\;\;x \ge 0{{ }}$

(15)

2）物理节点周边环境安全系数。将物理节点周边环境安全系数定义为：

$ER({n_{{s}}}) = \left\{ \begin{aligned}& \frac{{pos[{n_{{s}}}]}}{{N \cdot k}}{{,}}\;\;\;k{{ > 0}};\\& 1{{,}}\;\;\;\;\;\;\;\;\;k{{ = 0 }}\end{aligned} \right.$

(16)

式中： $k$ 为 ${n_{{s}}}$ 在一段时间内发生故障的次数，如果 $k{{ = 0}}$ ，则将其安全系数定义为1，如果 $k > {{0}}$ ， $pos[{n_{{s}}}]$ 表示 ${n_{{s}}}$ 在所有故障节点按发生故障时间排序后的位置索引，即 ${n_{{s}}}$ 到首个故障节点的距离^[12]； $N$ 表示物理网络中发生过故障的总节点数目。物理节点近期未发生故障，或发生故障次数越少，说明物理节点周边环境安全系数越高。

定义2(物理节点可靠度)　综合考虑物理节点使用度 $UR\left( {{n_{{s}}}} \right)$ 以及周边环境安全系数 $ER\left( {{n_{{s}}}} \right)$ ，将物理节点可靠度定义为：

$\begin{array}{l} R({n_s}) = UR({n_s}) \cdot ER({n_s}) = \\ \left\{ \begin{array}{l} \exp \left( { - {{\left( {\frac{x}{a}} \right)}^b}} \right),\;\;\;\;\;\;\;x \ge 0,k = 0;\\ \exp \left( { - {{\left( {\frac{x}{a}} \right)}^b}} \right) \cdot \frac{{pos[{n_s}]}}{{N \cdot k}},\;\;x \ge 0,k > 0 \end{array} \right. \end{array}$

(17)

物理节点可靠度综合考虑了物理节点使用度、最近一次故障时刻以及节点发生故障次数，全面评价并量化了物理节点可靠度。

定义3(物理节点可靠重要度)　将物理节点可靠度引入定义1的物理节点重要度，物理节点可靠重要度可定义为：

$\begin{array}{l}SIR({n_{{s}}}) = \displaystyle\frac{{NR({n_{{s}}}) + DC({n_{{s}}})}}{{LS({n_{{s}}})}} \cdot CC({n_{{s}}}) \cdot R({n_{{s}}})\end{array}$

(18)

2.3 算法实现

提出一种RA-EVNE算法。RA-EVNE的节点映射算法步骤如下：

输入： ${G_{{s}}}$ 、 ${G_{{v}}}$

1.　for虚拟网络中每一个虚拟节点 ${n_{{v}}} \in {N_{{v}}}$

2.　　do

3.　　　计算 ${n_{{v}}}$ 的虚拟节点重要度 $IR'\left( {{n_{{v}}}} \right)$

4.　end for

5.　对待映射的虚拟节点根据 $IR'\left( {{n_{{v}}}} \right)$ 从大到小重新 排序

6.　将虚拟节点映射顺序存入链表 $VirtualNodeList$

7.　for $VirtualNodeList$ 中的每一个虚拟节点 ${{n_{{v}}}}$

8.　　do

9.　　　取满足约束条件的候选物理节点集合　　 $Can\left( {{n_{{{v}}i}}} \right)$

10.　　　候选节点集合中排除已映射物理节点

11.　　　if $Can\left( {{n_{{{v}}i}}} \right)$ 为空 then

12.　　　　return NODE_MAPPING_FAILED

13.　　　else

14.　　　for $Can\left( {{n_{{{v}}i}}} \right)$ 中每一个候选节点 ${n_{{s}}}$

15.　　　　计算 $SIR\left( {{n_{{s}}}} \right)$

16.　　　end for

17.　　　将 ${n_{{v}}}$ 映射至 $SIR$ 最高的候选节点上，并将映　　 射结果存入 $NodeMappingList$

18.　　　更新已映射物理节点集合 $OpSubNode$

19.　　end if

20.　end for

21.　return NODE_MAPPING_SUCCESS

输出： $NodeMappingList$

链路映射是指在节点映射的基础上，以满足约束条件为前提，将虚拟链路映射到底层合适的物理链路上，同时达到设定的目标函数。使用“ $k$ 最短路径”^[15]链路映射算法。

3 性能评估与分析

为验证算法性能，将本文提出的RA-EVNE算法和之前研究中提出的算法进行仿真对比实验，并从虚拟网络映射成功率、长期平均收益、开销、收益开销比和虚拟网络易损率等方面验证所提算法的性能。

3.1 仿真环境

仿真实验采用改进的Salam网络拓扑随机生成算法生成底层网络和虚拟网络请求。底层物理网络在1 000 $ \times $ 1 000范围内生成均匀分布的100个节点和501条链路。物理节点的CPU资源和物理链路的带宽资源均服从[50，100]的均匀分布。虚拟网络请求模拟泊松分布，到达时间单位为100，到达个数期望为5。虚拟网络请求的生存时间服从期望为1 000个时间单位的指数分布，虚拟节点的数目服从[2，10]的均匀分布。每个虚拟节点的CPU资源需求和链路带宽资源需求均服从[0，50]的均匀分布，假设所有虚拟节点的位置距离约束为500。

节点的总寿命设为600 000个时间单位，节点的新旧程度分为3个等级，分别为新、一般、旧，其已使用的时间分别在区间[0，180 000]、[180 000，540 000]、[540 000，600 000]内均匀分布，且3个等级所占比例分别为60%、30%、10%。式（15）中的 $a$ 、 $b$ 分别取值250 000和1.5。发生过故障的节点数设为20个，发生故障的次数在[1，5]之内服从均匀分布。虚拟网络可靠性评估时，节点可靠度低于0.03即判定为节点易损。由于虚拟节点数目服从[2，10]的均匀分布，总节点数量较少，所以当虚拟网络映射的物理节点中有一个处于易损状态时，即判定此虚拟网络为易损网络。

模拟运行50 000个时间单位。仿真实验共进行10次，取其平均值作为最终仿真结果以消除随机因素的影响。

进行了5种虚拟网络映射算法的比较。RA-EVNE算法为本文提出的节点可靠感知的高效虚拟网络映射算法；为了测试本文RA-EVNE算法的高效性，即验证虚拟节点映射阶段引入节点中心度、物理节点就近距离能否有效提高虚拟网络映射成功率等性能，本文提出一种对比算法NC-VNE，该算法仅考虑节点重要度，不考虑物理节点可靠度，即物理节点排序指标为式（12）；BL2算法^[5]在节点映射阶段采用贪婪思想，考虑资源指标；CL算法^[6]在节点映射阶段仅考虑中心度指标；TA-SVNE算法^[7]在节点映射阶段考虑资源、信任关系及节点中心度指标，采用逼近理想排序法排序。

3.2 仿真结果

图2为5种算法虚拟网络映射成功率。本文提出的NC-VNE算法因为综合考虑了资源、中心度、物理节点就近距离，尤其是中心度和物理节点就近距离缩短了底层映射的物理链路跳数，节省了大量带宽资源，所以相较于其他算法，映射成功率最高，稳定后维持在70%左右；RA-EVNE算法的映射成功率仅次于NC-VNE算法，因为考虑了节点可靠度，不可避免的会牺牲一部分映射成功率，映射成功率依旧明显高于其他3种算法，维持在65%左右；TA-SVNE算法综合考虑了资源、信任关系和中心度等因素，所以性能优于仅考虑资源的BL2算法和仅考虑中心度的CL算法；BL2算法与CL算法的映射成功率比较接近，这2种算法的性能与网络拓扑以及资源量级有关，它们的映射成功率明显低于本文提出的2种算法。

图3为5种算法的虚拟网络长期平均收益。从图3可以看出，5种算法的长期平均收益在大约10 000个时间单位后基本达到稳态，其中，NC-VNE算法最高，RA-EVNE次之，其余依次是TA-SVNE算法、CL算法、BL2算法，NC-VNE算法和RA-EVNE算法相较于BL2算法，长期平均收益分别提高了48%和37%。

图4比较了5种算法的虚拟网络长期平均开销。由于本文所提的NC-VNE算法、RA-EVNE算法的映射成功率高于其他3种算法10%以上，所以这2种算法的长期平均开销高于其他3种算法。但是本文所提的2种算法相较于BL2算法，长期平均开销也仅分别高出约6%和5%。

图5为5种算法的虚拟网络长期平均收益开销比。从图5中可以看出，本文提出的RA-EVNE算法和NC-VNE算法的长期平均收益开销比最高，分别在0.48和0.44左右，明显高于其他3种算法。所以在底层网络资源相同的情况下，NC-VNE算法和RA-EVNE算法可以更高效地对资源加以利用。

表1给出了5种算法的虚拟网络易损率。由表1可知：RA-EVNE算法的虚拟网络易损率为0.66%；BL2、TA-SVNE、CL、NC-VNE算法因未考虑物理节点可靠度，虚拟网络易损率在10%～12%之间，这会降低虚拟网络可靠性，对网络的实际运行造成较大影响；而本文提出的RA-EVNE算法综合考虑了影响物理节点可靠度的3种因素，极大提高了虚拟网络可靠性能。

为了比较本文物理节点可靠度定义中选用的3种因素与单一的故障发生次数、最近一次故障时刻对虚拟网络易损率的影响，添加另外2种对比算法，结果见表2。NC-VNE1算法是在NC-VNE算法节点映射阶段添加故障发生次数因素，NC-VNE2算法则是在NC-VNE算法的节点映射阶段添加最近一次故障时刻因素。从表2中可以看出，NC-VNE1和NC-VNE2算法映射的虚拟网络易损率为7.67%和8.05%，远高于本文提出的RA-EVNE算法。

同时综合比较表1、2可以发现，NC-VNE1、NC-VNE2算法的易损率相较于表1中除RA-EVNE算法之外的4种算法有明显降低，也证明了单一的故障发生次数、最近一次故障时刻因素可以在一定程度上降低虚拟网络易损率。

4 结　论

重点研究了虚拟网络映射效率以及虚拟网络可靠性问题，提出了一种兼顾虚拟网络映射高效性和虚拟网络可靠性的映射算法。算法首先将节点中心度、物理节点就近距离引入节点排序方法，提出节点重要度；之后，量化物理节点可靠性并提出一种新的物理节点排序指标–物理节点可靠重要度；最后，分别对虚拟节点和物理节点进行排序并进行虚拟网络映射。仿真实验表明：RA-EVNE算法提高了虚拟网络映射成功率，增加了长期平均收益与收益开销比，验证了RA-EVNE算法的高效性；同时，获得了比传统算法以及单一因素算法更低的虚拟网络易损率，验证了RA-EVNE算法的可靠性。下一步将综合考虑其他网络安全威胁，添加相应的安全约束机制，进一步提高虚拟网络可靠性。