基于核心节点的虚拟网络嵌入算法

杨 杰,赵成贵

(云南财经大学 信息学院,云南 昆明 650221)

网络虚拟化技术[1]作为未来互联网最有前景的技术之一越来越受到重视.网络虚拟化技术是对目前网络改善的1个重要性工具,但是实现这个工具还面临着1个重大的挑战：即怎样合理高效的把物理网络中的资源分配给虚拟网络.把虚拟网络嵌入到物理网络的过程称为虚拟网络嵌入(virtual network embedding, VNE)问题[2].VNE问题被证明是NP-Hard问题[4],目前学术界的研究工作重点是启发式或元启发式方法.针对VNE问题,文献[5-7]利用线性规划的方法协调节点和链路进行求解.Chowdhury等[5-6]通过放松整数约束获得线性规划方法来协调节点和链路映射,采用确定性和随机舍入方法分别提出了D-VINE和R-VINE算法来达到在线的虚拟网络嵌入过程.但是由于使用了一些其他的约束条件来进行嵌入,增加了嵌入所需时间.Hu等[7]为了使得嵌入成本最低化,通过对 P-VNE 模型的双重表述的分析提出了一个列生成过程,通过逐步的更新新路径来解决嵌入过程.但也正是由于不断地更新路径,从而导致了算法的灵活性受限导致嵌入时间不断增加.文献[8-9]把VNE问题解耦为节点映射和链路映射两部分来进行求解.Yao等[8]设计并实现了一个基于强化学习的策略网络,利用贪婪策略做出节点映射决策,通过策略梯度来实现基于虚拟网络请求的历史数据的策略网络自动优化.Nguyen等[9]提出云网络状态下的RT-VNE算法：在节点映射阶段利用时间窗口技术集中处理每个时间窗口内的虚拟网络请求,链路映射阶段通过k-最短路径进行贪婪映射过程.由于采用时间窗口过程不能及时处理最新的虚拟网络嵌入过程,在一定程度上降低了用户服务质量.

上述算法在虚拟网络嵌入的不同指标上进行了优化,但是这些算法往往以牺牲算法运行时间或者以牺牲用户体验度为代价.因此,提高VNE算法嵌入效率,同时缩短算法运行时间,使得用户在最短时间内获得服务则是本文研究的重点.无论是在物理网络中还是在虚拟网络中,不难发现总是存在着一些非常重要的网络节点,如果从整个网络中删除这些节点,那么此网络的完整性就会遭到破坏.基于这些思想,本文提出了核心节点的查找方法,利用寿纪麟等[3]提出的重权集概念,同时引入割点来对物理网络和虚拟网络节点分别进行核心节点的查找,设计出相应的算法.在节点映射阶段,利用核心节点来进行节点映射,与大多数的节点映射算法不同的是在核心节点的基础上,不仅仅考虑到节点CPU资源约束问题,本文引入了节点的平均链路资源概念,对节点的嵌入过程同时考虑节点CPU资源约束和链路带宽资源的约束.实验表明,在保证了虚拟网络请求嵌入成功率的同时,嵌入所需的时间同时也明显优于已有的嵌入方法.

1 网络模型和问题描述

1.1 底层物理网络

把位于底层的物理网络抽象成无向加权图GS=(NS,ES),NS代表物理节点集,ES代表物理链路集.其中集合中每个物理节点nS∈NS具有的CPU资源权值定义为c(nS),连接任意节点i与j的物理链路eS∈ES的带宽权值定义为wi,j(eS).同时,定义节点的平均链路带宽资源w(nS).

图1(a)给出了1个底层物理网络的实例,包含5个网络节点和7条物理链路.其中,链路旁边的数字代表链路的带宽资源约束,节点附近方框中数字表示节点的CPU资源约束.

1.2 虚拟网络

虚拟网络同样可以抽象成无向加权图GV=(NV,EV) ,NV为虚拟节点集,EV为虚拟链路集,每个虚拟节点和节点之间的虚拟链路都具有相应的权值(即c(nV)和wi,j(eV))表示它所需要的资源.虚拟网络节点n的平均链路带宽资源用w(nV)表示.图1(b)与图1(c)分别列举除了2个不同的虚拟网络.

1.3 VNE问题描述

当有一个或者多个虚拟网络发出请求服务时,即虚拟网络请求,网络服务商需要利用已有的物理网络来分配相应的资源用以支持虚拟网络的运行.把虚拟网络嵌入定义为GV=(NV,EV)→GS=(NS,ES),这个过程包括节点映射和链路映射两部分.图1(b)和图1(c)给出了2个不同拓扑结构的虚拟网络,当这2个虚拟网络发出请求后，在物理节点CPU资源和物理链路带宽资源满足网络请求所需要的资源的情况下：虚拟网络1的3个虚拟节点a、b、c被映射到物理网络中的节点C、D、A中,虚拟网络链路(a,b)和(a,c)被映射到物理链路(C,D)和(C,A)中.虚拟网络2中的3个虚拟节点d、e、f分别被映射到物理节点B、A、E中,虚拟链路(d,e),(d,f)以及(e,f)被映射到物理链路(B,A),(B,E)和(A,E)中.其中,节点c和e占用节点A的CPU资源为35 < 80.其它的物理节点CPU和链路带宽资源在2个虚拟网络嵌入后仍有剩余,所以2个虚拟网络可以嵌入到物理网络中并使用.

2 基于核心节点的VNE算法

基于核心节点的VNE算法以查找网络图中的重要节点为首要任务,通过查找网络图的割点集以及重权节点集来构建核心节点集；最后,通过考虑链路带宽资源约束对于VNE的影响而引入核心节点的平均链路带宽资源,以此来提高节点映射成功后的链路映射阶段的成功率.

2.1 割点集

本文引入了割点集的概念,来对网络形象化的抽象为无向图,从而查找到网络中至关重要的节点的集合并保存后续使用.如图2(a)所示的1个简易网络图,我们可以观察到.当删除a节点后,这个网络会被分割成如图2(b)所示的有2个连通分支({b,d,e}和{c})的情形,图的连通性则被破坏.同样的,如果删除节点b,则网络图会被分割为如图2(c)所示的{a,c}、{d}和{e}3个部分,图的连通性同样被破坏.

在无向连通图G= (V,E)中,V和E分别表示图G的顶点集和边集.定义ω(G)为图G的连通分支数,若∃cn∈V(G),使得ω(G-cn)>1,则cn称作图G的1个割点.本文设计的查找网络的割点集的算法是在著名的Tarjan算法的基础上进行改进,并利用深度优先搜索来对网络图中各个节点进行割点判断.查找核心节点集算法具体步骤如下.

Step 1 对每1个物理/虚拟网络中的节点进行初始化标记,从网络中取出一个节点n.

Step 2 根据深度优先搜索思想进行深度优先搜索,并记录相应的信息：如遍历顺序,可到达节点的最小遍历顺序值等.

Step 3 对于网络图中的每1条以n为起点的边(n,v),如果v被访问过,进行Step 4.否则跳转Step 2.

Step 4 若v节点可到达节点的最小遍历顺序值x1不小于n节点的遍历顺序值x2,核心节点集C=Cn.否则更新n的可到达节点的最小遍历顺序值为min(x1,x2).

割点是1个图中起着至关重要的节点.但是在实际情况中,大多数情况下1个图割点的数量非常少,甚至可能为0.为了避免图中割点为0情况下导致节点嵌入过程直接失败,引入重权集来进行核心节点的优化.

2.2 重权集

把相应的网络抽象成无向加权图G=(V(G),E(G)),其中V(G)={n1,n2,…,nm} .考虑到链路带宽资源约束对于嵌入的影响,我们引入重权集[3]的概念来进行对网络中重权节点的查找.其中,网络中节点ni的CPU资源约束表示为c(ni).

Step 1 根据公式计算物理/虚拟网络图的平均CPU权数.对于网络图中的每1个节点进行Step 2.

Step 2 对于节点n,判断其CPU资源是否大于A,大于则重权集WeightSubset=WeightSubset∪n.

Step 3 核心节点集C=C∪WeightSubset.

2.3 核心节点优化

核心节点进行查找并统计后,单一的考虑节点CPU资源的映射算法并不能够比较好的进行虚拟网络嵌入.在节点映射完成后,链路映射过程中链路的带宽则是决定着虚拟网络能否嵌入成功的关键因素.单一的考虑节点的CPU资源约束已经不能适应VNE的实际应用需求,因此在节点映射阶段加入对链路映射阶段的预处理是必要的.

w(f)=k1*(wf,d+wf,e)/2+k2*wc,d+k3*(wa,c+wb,c)/2.

(1)

w(o)=k1*(wo,p+wo,r+wo,q)/3.

(2)

3 实验

3.1 实验方案设置

文中实验算法依托慕尼黑大学Beck等提供的模拟框架Alevin[12]进行实验.实验中的物理网络和虚拟网络均在此框架下动态随机生成,其中物理网络设置100个节点,节点计算CPU资源和链路的带宽资源均在[10,100]随机分布.虚拟网络设置为10个,每个网络的节点在[3,15]随机分布,节点的CPU资源在[1,10]随机分布,链路带宽资源在[1,10]随机分布.物理网络和虚拟网络相邻节点之间生成链路的可能性均为0.5.在实验中将对比算法DViNE-SP,RW-MM-SP,GAR-SP 3个算法,如表1所示.为了避免实验结果的偶然性,将进行50次循环实验.

表1 实验对比的算法

3.2 实验结果及分析

为了验证BC-VNE算法性能,本文使用虚拟网络请求的接受率,运行时间,嵌入成本与收益的比重,物理节点使用情况4个性能参数来对实验结果进行评价.根据实验数据结果分析如下所示.

1) BC-VNE相比于其他算法,提高了嵌入效率.图4给出了每次对比算法实验的运行时间,在图中相比于其他2种算法,BC-VNE算法和GAR-SP算法明显在运行时间上很短.

同时,结合表2给出的算法50次实验平均结果中实验的平均运行时间,可以看出在同样的条件下,DViNE-SP算法运行时间为85.34 s, RW-MM-SP算法运行时间为55.10 s,BC-VNE算法的运行时间为0.15 s,相比于这2种算法BC-VNE运行时间缩短了100倍以上.同时,BC-VNE算法相比于GAR-SP算法,运行时间也缩短了大约1倍.所以在相同条件下,BC-VNE算法运行时间少于其他算法,极大的提高了VNE的运行效率并且能够减少用户请求服务时间从而提供更高效的用户服务质量.

表2 对比算法50次实验平均结果

2) BC-VNE在提高嵌入效率的条件下,同时也提高了虚拟网络请求的接受率.图5给出了每次实验的虚拟网络请求接受率的结果,图中,BC-VNE算法的接受率明显优于GAR-SP算法和DVINE-SP算法接受率.从表2的中各个算法平均的接受率来看,BC-VNE算法的接受率为45.20%优于RW-MM-SP算法接受率43.40%.

结合图5和表2分析,而虽然在一定条件下BC-VNE算法的接受率不如RW-MM-SP算法的接受率,但是总体来说BC-VNE算法的虚拟网络请求接受率要优于后者.这是因为本文设计的BC-VNE算法是基于核心节点的嵌入算法,一旦核心节点的CPU资源全部被使用,则后续的虚拟网络请求就不能利用核心节点,则可能造成嵌入失败.虽然会存在偶然条件下的嵌入失败过程,但是整体来说,BC-VNE不仅提高了嵌入效率,而且使得嵌入质量也取得了一定的提升.

3) BC-VNE算法相比于其他算法,具有更好的综合效率.图6给出了算法实验的成本与收益的比率,可以看出在BC-VNE的表现比GAR-SP和DViNE-SP要好.结合表2中平均实验结果数据可知,BC-VNE和RW-MM-SP算法的成本/收益比率相差不大,但是总体上BC-VNE表现更加出色.

图7和图8分别给出了VNE算法节点使用率和链路使用率情况,可以看出BC-VNE算法能够极大化节点的使用率,但是在链路使用率上表现欠佳.这是由于BC-VNE算法时基于核心节点的启发式嵌入算法,主要考虑节点的映射过程,从而在链路使用率方面表现不如DViNE-SP和RW-MM-SP算法.其中,在节点(链路)使用率比较上,GAR-SP算法由于多次实验的嵌入成功率为0无参考性而不作节点(链路)使用率比较.结合图4～图8分析,在虚拟网络请求接受率上BC-VNE和RW-MM-SP算法比其他2种VNE算法更加符合网络服务商利益需求.同时, BC-VNE算法和RW-MM-SP算法两者的成本/收益、节点利用率、接受率这些指标相差不大,但是BC-VNE算法在算法的运行时间上相比于RW-MM-SP更加高效,能够使得用户更快的得到所需要的网络服务.所以相比于其他3种算法,在不降低虚拟网络请求接受率和其他评价指标的情况下,BC-VNE算法能够取得比较优秀的虚拟网络嵌入结果,具有更好的综合性能.

4 结语

本文研究了基于核心节点的VNE算法,针对网络中核心节点的查找做出相应的算法设计.实验表明,BC-VNE算法通过利用割点集和重权集的核心节点的嵌入,缩短了虚拟网络嵌入所需要的时间,同时提高了虚拟网络请求接受率.算法所涉及的核心节点利用割点和重权集查找具有一定的局限性,不能够很好地代表整个网络图的重要节点.为此,在后续工作中,将进一步研究发现网络中更重要的核心节点用来进行虚拟网络嵌入.