基于离散粒子群的节点可重用虚拟网络映射算法*

刘向东，刘 奎，王 聪

(东北大学秦皇岛分校计算机与通信工程学院，河北 秦皇岛 066004)

1 引言

随着互联网的快速发展，现有的互联网架构已经难以满足互联网新型应用的发展，在一定程度上呈现出僵化现象。更重要的是随着云计算技术的出现，迫切要求能够将物理网络内的资源灵活、动态地租赁给若干用户使用。网络虚拟化[1]被认为是解决网络僵化及多租赁问题的重要途径，其中的虚拟网络映射问题研究如何将具有虚拟节点需求(如CPU)和虚拟链路需求(网络带宽)的用户虚拟网络映射到资源有限的基础设施网络中，是网络虚拟化的基础问题[2]。在进行虚拟网络映射时需要同时考虑资源约束、拓扑多样性等多方面的问题，这样的优化问题已经被证明是NP困难的[3]，研究思路是先给出映射模型及约束条件，再给出优化目标，然后利用智能算法进行求解。

目前，已有一些虚拟网络映射算法，根据是否将节点映射和链路映射分离可以分为一阶段算法和两阶段算法。在一阶段算法中，Ines H等人[4]在假定底层物理网络资源无限的前提下，提出了一种分布式的虚拟网络映射算法，通过多代理机制同时映射虚拟节点和链路。Jens L等人[5]设计基于子图重构的虚拟网络映射算法，逐步映射节点和链路并引入了回溯算法，以扩大搜索空间，当下一步的映射方案无法满足约束时回溯到上一步重新选择映射的物理节点。在两阶段算法中，Minlan Y等人[6]提出的两阶段映射方案首先根据约束映射节点，然后将虚拟链路映射问题看成多商品流问题进行求解，相较传统一阶段算法，该算法提高了虚拟网络的接受率和底层物理网络的收益。Yong Z等人[7]使用贪心算法尽可能为虚拟节点选择负载较轻的物理节点，然后通过最短路径算法构建两个物理节点间的链路以映射虚拟链路。Cheng Xiang等人[8]提出了基于粒子群的虚拟网络映射算法，同样是先映射节点再根据最短路径映射边，该算法相较以前的算法可以获得更好的收益和虚拟网络接受率，但是没有考虑节点可重用技术也没有对群体初始位置进行优化。另外，当前主机虚拟化技术已较为完备，VMware、Xen等产品均已支持驻留在同一物理主机上的虚拟机之间可以通过内存交换代替虚拟链路上的数据交换[9]，这为虚拟网络映射问题带来了新的解决思路，即同一物理网络上的虚拟机可以映射到同一个物理主机上，这样可以抵消掉一部分链路带宽需求，这种技术称为节点可重用技术。

本文在Cheng Xiang等人[8]工作的基础上引入了节点可重用技术，重新规划了优化模型并设计了增强型粒子初始位置分配机制。利用可重用技术能够以虚拟机间内存数据交换代替网络数据交换的优点，通过在求解时对粒子群的初始位置进行有针对性的赋值，尽量将同一虚拟网络的节点映射到同一物理网络节点之上，从而节省物理网络的带宽。本文算法的目的是进一步提高底层物理网络的资源利用率，从而获得更好的性能和虚拟网络接受率。

2 虚拟网络映射问题描述

虚拟网络映射的目标是在尽可能多地接受虚拟网络请求的前提下，使用最少的物理网络资源，从而使得底层网络所有者的成本最小化。对于主机资源如CPU、内存、硬盘等资源来说，需求和成本永远相等，在构建优化模型时这部分的成本可以不予考虑，仅需考虑资源是否满足约束条件；而由于采用了可重用技术，可以用内存交换替代网络交换以节省物理网络的带宽资源，那么映射方案的好坏对于网络资源的成本支出是有影响的，因此对于每个虚拟网络请求，其映射优化问题可以描述为：

s.t. ∀n∈NV, ∀j∈NS

∀w∈EV, ∀(i,j)∈pS,

(1)

(2)

优化问题(1)中的第一个约束条件是主机资源约束需满足的条件，即当前物理节点的空闲资源要小于待映射虚拟节点请求的资源；第二个约束条件是物理带宽约束，即虚拟边的映射方案占用的每条物理链路的空闲带宽必须大于虚拟链路请求的带宽。

3 基于粒子群的虚拟网络映射算法

对于优化问题(1)，可以采用离散粒子群DPSO(Discrete PSO)[8]算法进行求解。离散粒子群算法是传统粒子群算法的变种，由于虚拟网络映射问题是离散问题，而传统的粒子群算法具有连续的本质，不太适合求解离散问题，因此将传统算法离散化是必要的。本节首先描述映射优化问题的离散粒子群求解算法，然后给出针对节点可重用的群体位置初始化算法，以形成整体算法。

3.1 针对虚拟网络映射问题的离散粒子群算法

Xk+1=Xk⊕Vk+1

(3)

定义1位置的减法X*-X：结果是一个新的位置向量X′，表示虚拟网络映射方案X*和X的差异。如果X*和X在相同维度上的值相同，则新向量对应维度上的值为1，否者为0。

定义2位置的和φ1X′+φ2X″：结果是一个速度向量，其中φ1、φ2为常数，且φ1+φ2=1。φ1X′+φ2X″的运算定义为：如果X′和X″在相同维度上值相同，则新速度在相应维度上的值保持不变，否则，以φ1的概率保持X′，以φ2的概率保持X″。

定义3位置和速度的和Xk⊕Vk：结果是一个新的位置向量，即当前映射方案Xk按照Vk调整虚拟节点的映射位置，如果Xk对应的Vk相应维度上的值为1，意味着当前位置需要保留，为0时需要为当前维度所代表的虚拟节点重新随机选择一个满足主机资源约束条件的物理节点。

DPSO_Mapping (GV,GS){

输入：虚拟网络GV, 物理网络GS;

输出：最优映射方案 solution。

移除空闲资源小于 GV中最小节点CPU和链路带宽需求的物理节点和物理链路;

for(int i=0; i

particle[i].initialposition();}

for(int i=0; i

gbestpre=particles.getgBest();

for(int j=0; j

particle[j].calculateFitness();

particle[j].updateSpeed();

particle[j].updatePosition();}

if(gbestpre==particles.getgBest()){

numofit++;}

else{numofit=0;}

if(numofit==10){break;}

}

if(particles.getgBest()!=+∞){

solution=Particle.getGbsolution();}

return solution;

}

在算法中，移除空闲资源小于最小请求的节点和边的目的是为了尽量缩小搜索空间。算法结束的条件是群体最优位置gbestpre 在10轮内不变或者计算轮数超过给定的最大迭代次数MaxItCount。

3.2 针对可重用的粒子位置分配机制

位置的初始化及更新机制对于粒子群算法的收敛速度有着重要影响，特别是在针对实际问题的离散粒子群求解过程中更加重要。在3.1节的算法中，与位置相关的关键函数是updatePosition()和initialposition( )，只随机选取物理节点的编号不利于节省带宽资源。为了充分发挥可重用能够节省物理带宽消耗的优势，应当尽量把每个虚拟网络的虚拟节点映射到同一物理节点上。为此需要对算法的位置更新及初始化函数针对可重用特性进行强化。

在强化过程中，既要保证尽量发挥可重用的特性又不能使得虚拟节点过度集中于某几个物理节点。因为如果在位置初始化的时候就令虚拟节点过度集中，那么很可能每个粒子都不会获得可行解，在没有可行解的情况下无法获得最优适应度的fitness值，也就无法获得群体最优位置，这将会导致粒子无法更新自己的位置。另外还要考虑，在虚拟网络映射问题中，每个虚拟网络请求的节点数量都不相同，在每个维度上重复分配同一个物理节点的次数应当与虚拟节点数量建立动态对应关系。本文采用动态机制结合虚拟网络节点数来强化可重用特性，为此引入因子k=(rnd.nextInt(numofpynodes)+m)/m，对于粒子位置向量的每个维度来说，如果其维度n模k等于0，则重新随机选择一个物理节点，否则保持前一维度所选择的物理节点。通过调整m的值可以获得合理的k值，这样可以将映射方案控制在一个比虚拟节点数小的物理节点集合之内，也就意味着可以充分发挥可重用特定而又不会导致群体无解的情况发生。以位置初始化算法initialposition( )为例，其伪代码如下所示：

initialposition(VNR) {

//numofsnodes:物理网络节点数;

//numofvnodes:虚拟网络节点数；

k=(rnd.nextInt(numofvnodes)+m)/m;

maph=rnd.nextInt(numofsnodes);

for(i=0; i

if(i%k==0){

maph=rnd.nextInt(numofsnodes);}

position.put(i, maph);}

}

位置更新函数updatePosition ( )与上述初始化函数类似，需要注意的是在位置更新时只更新那些对应速度向量维度为0的位置，为它们随机选取物理节点并通过强化机制发挥可重用优势。

4 实验

实验采用CloudSim 3.0.1[10]仿真软件平台，硬件平台为IBM X3650服务器。在CloudSim中用Java为底层物理网络和虚拟网络编写了一个随机的拓扑生成器。映射算法中涉及到的参数设定为φ1=φ2=0.5，位置分配算法中m=2，虚拟网络的生存周期在100～1 000时间单位中均匀分布，如果10轮没有改变全局最优位置或者计算次数超过30轮则粒子群算法终止。实验比较了本文提出的算法采用/不采用增强位置分配与文献[8]中的VEN-R-PSO映射算法在底层物理网络开销及计算效率上的表现。在物理网络开销实验中，底层物理网络为100个节点，连通概率为0.2。虚拟网络节点数为4，连通概率为0.4。实验每次仿真2 000个虚拟网络的映射，共运行10次,然后计算接受同样节点数后物理网络累积开销的平均值，由于虚拟网络不可能同时被接受，大部分网络需要排队等候，因此实验能够起到检验作用。

由于虚拟网络的连通概率大于底层物理网络，对于不可重用的映射算法可能存在无解的虚拟网络，即那些含有连通度大于物理网络最大节点连通度的虚拟节点的虚拟网络无法被接受，因此实验只给出了1 500个虚拟网络的映射结果。从图1可以看出，本文提出的算法接受同样的虚拟网络时底层物理网络开销更小，主要原因是可重用技术的使用可以节省物理链路带宽的分配，那些被映射到同一物理主机上的虚拟网络没有开销产生。特别是加入位置强化机制后能够节省很大的开销，这主要是由于初始位置设定对于粒子群寻找最优解有极大帮助，针对可重用特性的强化机制能够尽量把同一虚拟网络的节点放到相同的物理节点之上。

Figure 1 Cost of substrate network to accept same number of virtual networks图1 接受相同数量虚拟网络时的物理网络开销

第二个实验将物理网络的节点数分别设为60、80、100，测试了完成前1 000个虚拟网络所需的时间。同样每次实验运行10次，共运行30次仿真。如图2所示，物理网络节点数越少，完成1 000个虚拟网络的时间越多，使用位置分配强化机制的效果越明显。原因在于m值对于群体求解效率具有影响，实验中三种物理拓扑均采用m=2，对于规模大的物理网络，由于搜索空间更大也就更不容易发挥可重用特性，此时应该选择大一些的m值。m值的选取除了考虑对可重用程度及求解效率有影响之外，还应考虑搜索空间大小，即物理网络节点的个数，因此m值的选取应当参考实际情况进行合理选择。

Figure 2 Completion time of 1 000 virtual networks on substrate networks with different node numbers图2 不同节点数量物理网络拓扑上1 000个虚拟网络完成时间

5 结束语

本文针对网络虚拟化应用中的虚拟网络映射问题，提出了一种物理节点可复用的虚拟网络映射算法，该算法在尽可能缩小搜索空间的基础上采用节点可复用方法，以内存交换代替虚拟链路，从而减少了物理链路资源的开销。针对粒子群初始位置及位置更新设计了强化机制，有助于算法求解效率的提高，对求解的优化程度能够起到良好促进作用。仿真实验表明，本文提出的算法在支持相同数量及结构的虚拟网络时产生的开销更小，特别是位置强化分配机制能够实现更小的开销和更高的求解效率。

[1] Chowdhury N.M. M K,Boutaba R.A survey of network virtualization[J].Computer Networks,2010,54:862-876.

[2] Li Xiao-ling,Wang Huai-min,Ding Bo,et al.Research and development of virtual network mapping problem[J].Journal of Software,2012,23(11):3009-3028.(in Chinese)

[3] Cai Zhi-ping,Liu Qiang,Lu Pin,et al.Virtual network mapping model and optimization algorithms[J]. Journal of Software, 2012, 23(4):864-877. (in Chinese)

[4] Ines H,Wajdi L,Djamal Z. A distributed virtual network mapping algorithm[C]∥Proc of the IEEE International Conference on Communications (ICC’08), 2008:5634-5640.

[5] Jens L,Holger K.A virtual network mapping algorithm based on subgraph isomorphism detection[C]∥Proc of the 2009 ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures (VISA’ 09),2009:81-88.

[6] Minlan Y,Yung Y,Jennifer R,et al.Rethinking virtual network embedding:Substrate support for path splitting and migration[J]. ACM SIGCOMM CCR,2008,38(2):17-29.

[7] Yong Z,Mostafa A. Algorithms for assigning substrate network resources to virtual network components[C]∥Proc of the 25th IEEE International Conference on Computer Communications (INFOCOM’06), 2006:1-12.

[8] Cheng Xiang, Zhang Zhong-bao,Su Sen,et al.Virtual network embedding based on particle swarm optimization[J]. Acta Electronica Sinica,2011,39(10):2240-2244.(in Chinese)

[9] Jian W,Kwame-Lante W,Kartik G. XenLoop:A transparent high performance inter-VM network loopback[J].Cluster Computing,2009,12(2):141-152.

[10] CloudSim:A framework for modeling and simulation of cloud computing infrastructures and services[EB/OL].[2013-02-16].http://www.cloudbus.org/cloudsim/2013.

附中文参考文献：

[2] 李小玲,王怀民,丁博,等.虚拟网络映射问题研究及其进展[J].软件学报,2012,23(11):3009-3028.

[3] 蔡志平,刘强,吕品,等.虚拟网络映射模型及其优化算法[J].软件学报,2012,23(4):864-877.

[8] 程祥，张忠宝，苏森，等.基于粒子群优化的虚拟网络映射算法[J].电子学报，2011,39(10):2240-2244.