安全虚拟网络映射的启发式算法

刘新波, 王布宏, 刘帅琦, 杨智显, 赵志远

(空军工程大学信息与导航学院, 陕西 西安 710077)

0 引 言

目前,网络虚拟化技术受到了学术界和工业界的高度重视,它不仅是解决当前互联网面临的僵化问题的关键技术[1],也是云计算中的核心技术。虚拟网络映射是网络虚拟化需要着重解决的问题之一,已有的研究成果证明该问题属于非确定性多项式时间(non-deterministic polynomial-time，NP)难问题[2]。现有的虚拟网络映射算法主要以提高底层物理网络的映射收益[3-5]或降低能耗[6-8]为目标,并采用启发式算法[9-10]或者元启发式算法[11-12]进行求解。然而,网络虚拟化在为网络架构带来灵活性的同时,也带来了一些新的安全问题[13]。

针对网络虚拟化所带来的安全威胁,文献[13]首次提出了安全虚拟网络映射(secure virtual network embedding, SVNE)概念,并给出了SVNE应满足的安全约束条件。在此基础上,文献[14]根据加密方式不同将虚拟网络请求(virtual network request,VNR)和底层物理网络节点设置为不同的安全等级,建立了SVNE模型,并对离线虚拟网络映射进行了仿真计算,结果表明部分情况下完成虚拟网络映射所需的时间过长。文献[15-16]将虚拟节点和物理节点的安全属性抽象为安全需求等级和安全等级,建立了SVNE混合整数线性规划模型,并采用启发式算法对在线虚拟网络映射进行了仿真计算,提高了虚拟网络映射的运算速度,但没有着重考虑虚拟节点的安全属性对映射成功率的影响。文献[17]提出了针对隐蔽信道攻击的SVNE算法,提高了虚拟节点的安全性,但该算法针对特定安全问题,其应用范围受限。

在现有研究基础上,本文主要工作包括以下几点:

(1) 对SVNE模型进行优化,以最小化物理网络的映射开销和最小化物理节点的安全属性改变量为目标函数,构建了多目标优化的SVNE混合整数线性规划模型;

(2) 针对改进的SVNE模型,提出了基于节点多属性综合评估与路径优化的SVNE算法(SVNE algorithm based on node attributes comprehensive assessment and path optimization,NP-SVNE);

(3) 编写仿真程序,对NP-SVNE算法进行仿真计算,验证了该算法在虚拟网络请求接受率和收益开销比等方面较现有算法具有较大的优越性。

1 问题描述

1.1 安全约束抽象

在网络虚拟化环境中,有些VNR对安全性要求较高,如与金钱密切相关的网上支付和网上购物等,而有的VNR对安全性要求相对较低,如在线游戏和在线视频等。因此,本文将VNR的安全属性设置为不同的安全需求等级和安全等级,而不是将虚拟网络中的每个虚拟节点都设置为不同的安全需求等级和安全等级[15-16]。同时,虚拟网络映射过程中需要满足与文献[13,15-16]相同的安全约束条件。

1.2 网络模型

1.2.1 物理网络

物理网络拓扑使用加权无向图Gp=(Np,Ep)表示,其中Np为物理节点集合;Ep为物理链路集合。物理节点np∈Np的属性取可用CPU资源cpu(np)、安全需求等级sd(np)和安全等级sl(np)。物理链链路ep∈Ep的属性取剩余带宽b(ep)。

1.2.2 VNR

使用VNRi=(Gv,ta,td)来表示第i个到达的VNR,其中Gv为虚拟网络拓扑;ta为VNR到达时间;td为VNR结束时间。虚拟网络拓扑也使用加权无向图Gv=(Nv,Ev)表示,其中Nv为虚拟节点集合;Ev为虚拟链路集合。虚拟节点nv∈Nv的属性取CPU资源需求cpu(nv)、安全需求等级sd(nv)和安全等级sl(nv),虚拟节点的安全需求等级和安全等级与相应的VNR的安全需求等级和安全等级相同。虚拟链路ev∈Ev的属性取链路带宽需求b(ev)。

1.2.3 SVNE

SVNE是一类特殊虚拟网络映射,在映射过程中除了需要满足节点资源和链路资源的约束条件外,还需要满足安全性约束条件。根据安全性约束条件限制,当虚拟节点映射至物理节点后,物理节点的安全属性可能会发生改变,从而影响其承载后续到达的虚拟网络映射请求的能力。图1为2个按时间序列到达的虚拟网络映射请求,任一节点n旁边圆括号内的数字依次代表节点的属性cpu(n)、sd(n)和sl(n),任一链路e旁边的数字代表链路的属性b(e)。如果VNR1按照方案1进行映射,则映射完成后,物理节点B、C和A的安全需求等级会升高,均变为3,使后续到达的VNR2由于无法满足安全性约束而不能成功映射。如果VNR1按照方案2进行映射,则映射完成后,物理网络中所有节点的安全属性均不发生变化,使后续到达的VNR2可以顺利完成映射,其一种可行的节点映射方案为{d→B,e→C,f→A},相应的链路映射方案为{(d,e)→(B,C),(d,f)→(B,A),(e,f)→(C,A)}。因此,在面向安全的虚拟网络映射过程中,不仅要以尽量降低物理网的络映射开销为目标,还要以尽量不改变物理节点的安全属性为目标。

图1 虚拟网络映射示例Fig.1 Example of virtual network embedding

1.3 评价指标

与文献[3-4,15-16]类似,以虚拟网络请求接受率、物理网络映射收益、物理网络映射开销和收益开销比作为SVNE算法的评价指标,并根据SVNE需要,对其进行适量修改。

虚拟网络请求接受率定义为

(1)

式中,VNRs表示映射成功的VNR;VNRa表示到达的VNR。

定义VNRi=(Gv,ta,td)在t时刻的映射收益为

(2)

式中,α(ns)=1+0.1·sd(ns)表示虚拟节点ns的单位CPU资源映射收益,其大小与虚拟节点的安全需求等级有关。

定义VNRi=(Gv,ta,td)在t时刻的映射开销为

(3)

物理网络收益开销比定义为物理网络的长时间平均收益与长时间平均开销的比值,表示为

(4)

2 多目标优化数学模型

2.1 目标函数

在SVNE过程中,不仅要尽量降低虚拟网络的映射开销,还要尽量不改变物理节点的安全属性,以便使其能够更好地承载后续到达的虚拟网络映射请求。因此,在文献[15-16]的基础上,将SVNE问题建模为多目标混合整数线性规划模型,以最小化物理网络映射开销和最小化物理节点安全属性改变量为目标函数,表示为

(5)

(6)

2.2 节点约束条件

首先,物理节点ni的剩余可用资源应不小于映射在其上的虚拟节点ns的资源需求为

(7)

其次,若虚拟节点与物理节点之间存在映射关系,则虚拟节点和物理节点的映射关系应该是一对一映射关系,需满足的约束条件为

(8)

(9)

(10)

2.3 链路约束条件

首先,任一条物理链路eij的剩余带宽应该不小于映射到其上的虚拟链路的带宽和,即

(11)

其次,需要考虑链路的连通性约束,确保将虚拟链路映射至一条无环路的物理路径上,即

∀ni∈Np,∀est∈Ev

(12)

(13)

2.4 安全性约束条件

(14)

3 NP-SVNE算法设计

3.1 节点映射

步骤1计算虚拟节点资源能力。在节点映射阶段,节点资源需求大的节点更难映射成功,应优先映射这类节点。因此,本文定义的虚拟节点资源能力属性为

(15)

式中,E(nv)是nv的邻边集合。

步骤2对虚拟节点进行排序。为了尽量使虚拟网络中相邻的节点在映射至物理网络后仍然保持邻近性,减少虚拟链路映射至物理路径的跳数,本文采用广度优先搜索算法通过构造虚拟节点的映射树来对虚拟节点进行排序,即以H(nv)最大的虚拟节点为根节点,运行广度优先搜索算法,将剩余虚拟节点按照距根节点的距离进行排序,若距根节点距离相同,则按照H(nv)值从大到小的顺序排列。

k≤sl(np)&&sd(np)≤l,np∈Np}

(16)

(17)

式中,H(np)为物理节点np的资源能力属性;Security(np)为物理节点np的安全性属性;Distance(np)为物理节点np的距离属性;ε是一个非常小的正数,避免分母为零。

(18)

式中，E(np)为np的邻接链路集合。

Security(np)=

(19)

式中,σ(0<σ<1)和λ(0<λ<1)是权重因子。

(20)

(21)

在虚拟节点映射过程中,选择NEF作为映射标准,主要基于以下3点考虑:①优先考虑可用资源大的物理节点,有利于抑制网络碎片的产生,从而可以提高虚拟网络请求接受率;②优先选择安全等级与VNR的安全需求等级相近的物理节点,可以降低映射开销;当VNR的安全需求等级大于物理节点的安全需求等级时,优先选择安全需求等级与VNR的安全需求等级相近的物理节点,可以较少地改变物理节点的安全需求等级,有利于完成后续到达的虚拟网络映射请求;③优先选择到已映射节点距离和较小的节点,可以降低链路资源消耗,提高物理网络的资源利用率。NP-SVNE的节点映射算法主要流程的伪代码如表1所示。

表1NP-SVNE的节点映射算法伪代码

Table1Pseudo-codeofNP-SVNE’snodeembeddingalgorithm

3.2 链路映射

步骤1对虚拟链路进行排序。根据虚拟链路对带宽需求的大小,将虚拟链路按降序进行排列。优先映射带宽需求大的虚拟链路。

步骤3计算候选物理路径的路径映射函数(path embedding function,PEF)值,并将虚拟链路映射至PEF值最大的物理路径。PEF的定义为

(22)

式中,b(pk)为路径pk的可用带宽；hops(pk)为路径pk的跳数。

将虚拟链路映射至PEF值最大的物理路径,可以协调物理链路资源消耗并降低映射开销。NP-SVNE的链路映射算法主要流程的伪代码如表2所示。

表2NP-SVNE的链路映射算法伪代码

Table2Pseudo-codeofNP-SVNE’slinkembeddingalgorithm

4 实验及结果分析

4.1 实验环境设置

当前,在进行虚拟网络映射算法研究时,常用的网络拓扑生成工具有佐治亚理工学院的网络拓扑模型(georgia tech internetmork topology models, GT-ITM)和Waxman网络拓扑生成器。在本文中,与文献[15-16]类似,使用GT-ITM来生成物理网络和虚拟网络的网络拓扑结构,通过控制其参数α和β来改变所生成网络中的边数和长边相对短边的比例。物理网络拓扑由100个节点和500条链路组成。另外,cpu(np)和b(ep)均服从50～100的整数均匀分布;sd(np)和sl(np)服从0～4的整数均匀分布,且每个物理节点的安全需求等级不能高于其安全等级。

VNR的到达过程和生存时间与文献[15]相同。对每个VNR来说,其节点个数服从4～10的整数均匀分布,每对节点间以0.5的概率相互连接。另外,cpu(nv)和b(ev)均服从0～50的整数均匀分布;sd(nv)和sl(nv)服从0～4的整数均匀分布,且每个虚拟节点的安全需求等级不能高于其安全等级。

本文进行了4种算法的比较。NP-SVNE是本文提出的基于节点多属性综合评估与路径优化的安全虚拟网络映射算法。NR-SVNE是文献[15]提出的基于节点排序的安全虚拟网络映射算法。TA-SVNE是文献[16]提出的基于TOPSIS多属性节点重要性排序的安全虚拟网络映射算法。G-SVNE是文献[16]提出的基于贪婪策略的安全虚拟网络映射算法。

4.2 实验结果分析

本文所对比的4种算法的虚拟网络请求接受率随时间的变化关系如图2所示。

图2 虚拟网络请求接受率Fig.2 Acceptance ratio of virtual network request

由图2可知，初始时间段4种算法的虚拟网络请求接受率都比较高,这是因为刚开始时物理网络的可用资源比较丰富。随着时间的推进和VNR的不断到来,物理网络的可用资源逐渐减少,请求接受率逐渐下降,并在约5 000个时间单元后趋于稳定。虚拟网络请求接受率稳定后,NP-SVNE算法的接受率约为90%,分别较NR-SVNE、TA-SVAE和G-SVNE算法提高了约6.4%、26.6%和37.0%。与其他算法相比,NP-SVNE算法在节点映射阶段更多的考虑了节点的安全属性和拓扑邻近性,在链路映射阶段综合考虑了路径带宽和跳数,这些措施使节点匹配更加合理,使链路映射更加优化,因此提高了虚拟网络请求接受率。

本文所对比的4种算法的平均收益随时间的变化关系如图3所示。

图3 物理网络平均映射收益Fig.3 Average embedding revenue of physical network

由图3可知，初始时间段到达的VNR数量较少,4种算法的物理网络平均收益均比较低。随着仿真时间的持续,到达的VNR数量逐渐增加,物理网络的平均收益逐渐增加,并在约5 000个时间单元后趋于稳定。由于NP-SVNE算法的虚拟网络请求接受率最高,因此在相同时间内映射成功的虚拟网络数量也最多,物理网络的平均收益也最高,约为9 983,分别较NR-SVNE、TA-SVNE和G-SVNE算法提高了约9.9%、38.5%和46.0%。

本文所对比的4种算法的平均开销随时间的变化关系如图4所示。

图4 物理网络平均映射开销Fig.4 Average embedding cost of physical network

由图4可知，仿真初始阶段到达的VNR数量较少,物理网络的映射开销较低。随着仿真时间的持续,到达的VNR数量逐渐增多,物理网络的映射开销也随之增大,并在约5 000个时间单元后趋于稳定。由于NP-SVNE算法在节点映射阶段考虑了节点之间的邻近关系和安全属性的最优匹配,因此其映射开销最低,约为17 412,分别较NR-SVNE、TA-SVNE和G-SVNE算法降低了约12.6%、8.9%和14.6%。

本文所对比的4种算法的收益开销比随时间的变化关系如图5所示。

图5 收益开销比Fig.5 Revenue/cost ratio

由图5可知，初始时间段,随时间的增加,4种算法的收益开销比均有所降低,这是因为随着VNR增加,物理网络的可用资源减少,虚拟链路映射的物理路径长度增加,从而增加了映射开销。稳定后,NP-SVNE算法的收益开销比最高,约为57%,分别较NR-SVNE、TA-SVNE和G-SVNE算法提高了约23.9%、50.0%和67.6%。

5 结束语

虚拟网络映射问题属于NP难问题,加入安全约束条件后会进一步增加虚拟网络映射的复杂程度,导致现有SVNE算法的性能不够理想。针对该问题,构建了多目标优化的SVNE混合整数线性规划模型,提出了启发式的SVNE算法NP-SVNE。该算法在节点映射阶段综合评估了节点的资源能力、拓扑邻近性和安全属性,在链路映射阶段考虑了物理路径的长度和可用带宽。仿真结果表明,NP-SVNE算法的多项评价指标(如,η和R/C等)均优于现有的SVNE算法。但该算法没有考虑映射过程中物理网络的可靠性。下一步需结合物理网络的安全等级发生改变或突然失效等情况,将可靠性引入SVNE过程,研究安全可靠的虚拟网络映射算法。

[1] ANDERSON T, PETERSON L, SHENKER S, et al. Overcoming the internet impasse through virtualization[J]. Computer, 2005, 38(4): 34-41.

[2] AMALDI E. On the computational complexity of the virtual network embedding problem[J].Electronic Notes in Discrete Mathematics,2016,52:213-220.

[3] BIANCHI F, PRESTI F L. A markov reward model based greedy heuristic for the virtual network embedding problem[C]∥Proc.of the IEEE 24th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, 2016: 373-378.

[4] CUI H Y, GAO W J, LIU J,et al. A virtual network embedding algorithm based on virtual topology connection feature[C]∥Proc.of the IEEE 16th International Symposium on Wireless Personal Multimedia Communications, 2013: 1-5.

[5] LIU X, ZHANG Z B, LI X M, et al. Optimal virtual network embedding based on artificial bee colony[J]. Eurasip Journal on Wireless Communications & Networking, 2016, 2016(1): 273.

[6] ZHANG Z B, SU S, ZHANG J C, et al. Energy aware virtual network embedding with dynamic demands:online and offline[J]. Computer Networks, 2015, 93: 448-459.

[7] TRIKI N, KARA N, BARACHI M E, et al. A green energy-aware hybrid virtual network embedding approach[J]. Computer Networks, 2015, 91: 712-737.

[8] HAN X, HAN P C, LIU Y J, et al. Green virtual network embedding with periodical sleep mechanism for fiber-wireless access network[C]∥Proc.of the Asia Communications and Photonics Conference, 2016, paper AF3E.3.

[9] LEKHA P, TRAM T H, MOHAN G. Time and bandwidth-aware virtual network embedding and migration in hybrid optical-electrical data centers[C]∥Proc.of the IEEE 31st International Conference on Advanced Information Networking and Applications, 2017: 947-954.

[10] SHAHRIAR N, AHMED R, KHAN A, et al. ReNoVatE: recovery from node failure in virtual network embedding[C]∥Proc.of the 12th International Conference on Network and Service Management (CNSM), 2016: 19-27.

[11] ZHANG Z B, SU S, LIN Y K, et al. Adaptive multi-objective artificial immune system based virtual network embedding[J]. Journal of Network and Computer Applications,2015,53:140-155.

[12] WANG C, SU Y, ZHOU L X, et al. A virtual network embedding algorithm based on hybrid particle swarm optimization[C]∥Proc.of the International Conference on Smart Computing & Communication, 2016: 568-576.

[13] FISCHER A, DE MEER H. Position paper: secure virtual network embedding[J]. Praxis der Information Sverarbeitung und Kommunikation, 2011, 34(4): 190-193.

[14] BAYS L R, OLIVEIRA R R, BURIOL L S, et al. Security-aware optimal resource allocation for virtual network embedding[C]∥Proc.of the 8th International Conference on Network and Service and Service Management, 2012: 378-384.

[15] LIU S H, CAI Z P, XU H, et al. Towards security-aware virtual network embedding[J].Computer Networks,2015,91:151-163.

[16] 龚水清,陈靖,黄聪会,等. 信任感知的安全虚拟网络映射算法[J]. 通信学报, 2015, 36(11): 180-189.

GONG S Q, CHEN J, HUANG C H, et al. Trust-aware secure virtual network embedding algorithm[J]. Journal on Communications, 2015, 36(11): 180-189.

[17] WANG Z M, WU J X, GUO Z H, et al. Secure virtual network embedding to mitigate the risk of covert channel attacks[C]∥Proc.of the IEEE Conference on Computer Communications Workshops, 2016: 144-145.