基于拓扑预配置的公平虚拟网络映射算法

王 聪 苑 迎 彭三城 王兴伟 王翠荣 万 聪

1(东北大学秦皇岛分校计算机与通信工程学院 河北秦皇岛 066004)2(广东外语外贸大学思科信息学院 广州 510420)3 (东北大学软件学院 沈阳 110819)(congw@neuq.edu.cn)

基于拓扑预配置的公平虚拟网络映射算法

王 聪1苑 迎1彭三城2王兴伟3王翠荣1万 聪1

1(东北大学秦皇岛分校计算机与通信工程学院 河北秦皇岛 066004)2(广东外语外贸大学思科信息学院 广州 510420)3(东北大学软件学院 沈阳 110819)(congw@neuq.edu.cn)

虚拟网络映射是实现云环境下资源多租赁运营及弹性计算资源服务的关键基础环节，其目的是在满足虚拟网络资源需求的前提下将虚拟网络植入到合适的底层物理节点和链路.现有虚拟网络映射算法的研究成果大多以极大化物理资源利用率为目标，对虚拟网络请求排队中的公平性问题考虑较少.为此提出了一种基于虚拟拓扑预配置及可重用技术的虚拟网络映射算法以提高映射公平性.将虚拟网路映射过程分为2步骤：拓扑预配置过程和映射过程.1)对在线队列中较大的虚拟网络拓扑进行等价变换，将其变换为节点及链路数目更小的拓扑，减少虚拟网络请求在拓扑上的差异从而提高公平性；2)建立形式化的虚拟网络映射模型，并利用离散粒子群算法对优化模型进行求解；为了充分利用可重用技术能在求解过程中节省带宽资源的特性，引入粒子位置分配增强机制以提高物理网络资源利用率.仿真实验结果表明：提出的算法在物理网络资源利用率、收益成本比及虚拟网络接受公平性等方面均优于已有同类算法.

网络虚拟化；虚拟网络映射；节点可重用；虚拟拓扑预配置；离散粒子群优化算法

云计算最大的特点是使得IT资源可以像水、电、天然气一样按需租赁并计费.从物理资源所有角度，云环境下的市场被分为2部分：基础设施提供商和服务提供商[1].基础设施提供商是资源所有者，其资源将被动态、实时、按需地租赁给IT市场中的任意用户；服务提供商根据实际需求按需租赁基础设施提供商的硬件资源，从而构建定制的虚拟网络，向端用户提供IT服务.这种典型的云环境下的多租赁市场运营机制，对于企业节省成本及提高资源利用率具有极大意义[2].

租赁的实现离不开虚拟化技术的支持，主要手段是通过虚拟化技术，包括软件、操作系统、存储、网络和管理的虚拟化把物理资源集中在一起形成共享虚拟资源池[3]，进而实现虚拟资源动态分配的多租赁特性.目前基础设施提供商仅能实现主机资源的动态分配和计费，如Amazon的EC2[4].然而，用户的实际需求包含虚拟主机和虚拟链路组成的虚拟网络.随着高带宽业务的发展，以虚拟网络为控制管理单位的资源租赁机制的需求变得愈加迫切.

Fig. 1 Diagram of virtual network embedding图1 虚拟网络映射示意图

如图1所示，网络虚拟化技术允许在共享的底层物理网络之上共存多重异构的虚拟网络.以网络虚拟化技术为基础，为服务提供商的带有节点(CPU、内存、存储)和链路资源(带宽)约束条件的虚拟网络分配物理底层网络资源的问题称为虚拟网络映射(嵌入)问题[5].虚拟网络映射问题已经被证明是NP难问题，即使在所有的虚拟节点已被映射后，映射具有带宽资源约束的虚拟链路仍然是NP难的[6].因此，目前已有的研究成果大都采用智能算法来解决虚拟网络映射问题.

在虚拟网络映射的相关技术中，可重用技术的产生对于资源利用率的提高有较大意义.如图1中虚拟网络2的映射方案所示，可重用技术是指同一虚拟网络的不同节点可以映射到同一物理节点上.这样做的目的是可以将虚拟节点之间的链路直接映射到内存中，用内存数据交换来替代网络交换，从而节省一部分带宽资源.目前的主机虚拟化平台软件如VMware，Xen等均支持虚拟机间利用内存通信的技术[7].

现有虚拟网络映射算法研究成果大都以最大化资源利用率为目标[5]，当有空闲物理资源时就对在线排队的虚拟网络请求进行筛选，尽可能接受更多的虚拟网络.在这样的情况下，虚拟网络拓扑的差异性将导致规模较大的虚拟网络请求很难被接受.为此，本文提出了拓扑预配置机制，对虚拟网络拓扑进行等价变换以减少虚拟拓扑间的差异性，并且结合可重用技术设计了一种以最大化物理网络收益为目标并兼顾排队公平性的虚拟网络映射算法.

1 相关工作

云环境下资源租赁的管理粒度正从物理主机、虚拟主机过渡到虚拟网络，后者对资源租赁的抽象更加合理，兼具高效和灵活性.目前的研究成果可划分为虚拟网络映射和运行时重配置两大类，这两类其实属于资源租赁的2个不同阶段.前者研究虚拟网络在被映射到物理网络上时的资源分配和收益优化问题；后者通过调度物理网络内运行的虚拟网络，对虚拟链路和节点进行迁移、调整，以减少资源“碎片”，提高资源利用率.本文主要针对虚拟网络映射问题，但是借鉴了重配置对虚拟拓扑进行调整的思路.下面对目前已有的研究成果做简要论述.

在解决虚拟网络映射问题时，往往通过简化问题或增加假设来缩小搜索空间获取优化解.研究思路是首先给出映射模型及约束条件，然后出优化目标，最后利用智能算法进行求解[6].因此，现有的解决方案可分为限制问题空间的映射算法[8-10]和不限制问题空间的映射算法[11-15].

由于同时存在节点和链路的资源限制，并且每个虚拟网络请求的到达时间、资源需求信息都是不可预知的，在不破坏底层资源约束的前提下实现多个不同拓扑的虚拟网络的映射是一个巨大的挑战.文献[8]在忽略节点资源限制、忽略准入控制和假设已知所有虚拟网络请求的前提下，将虚拟网络请求的拓扑局限在Internet骨干网络拓扑，使用线性规划和混合整数2次规划进行问题求解.文献[9]在忽略节点资源限制和忽略准入控制的前提下，将小型网络的通信矩阵建模成连续时间的Markov决定过程，通过模拟退火算法寻找最优解.文献[10]在忽略准入控制和假设已知虚拟网络请求信息的前提下，将虚拟网络请求切割成多个星状拓扑的子请求之后，根据节点潜能使用自适应的贪婪算法进行求解.

文献[11-15]在不限制问题空间的前提下，寻找映射虚拟网络的解决方案.这类方法又可以细分为一阶段映射算法和二阶段映射算法.一阶段映射算法是在映射过程中同时考虑节点和链路的资源限制，即映射一个虚拟节点，不但需要考虑节点资源需求，而且要考虑与已映射的虚拟节点之间的链路资源需求.在所有资源需求得到满足之后，才能映射下一个虚拟节点. 一阶段算法往往使用回溯法进行试探.文献[11]在假定底层物理网络资源无限的前提下，提出了一种分布式的虚拟网络映射算法，通过多代理机制同时映射虚拟节点和链路.文献[12]设计了基于子图重构的虚拟网络映射算法，算法逐步映射节点和链路并引入回溯算法以扩大搜索空间，当下一步的映射方案无法满足约束时则回溯到上一步，为虚拟节点重新选择映射的物理节点.

二阶段算法将虚拟网络的映射算法分为节点映射阶段和链路映射阶段.在节点映射阶段，映射算法选出满足各个虚拟节点资源需求的物理节点进行节点映射；在链路映射阶段，映射算法在已经映射的物理节点之间寻找1条或多条无环路径以映射相应的虚拟链路.文献[13]提出的二阶段映射方案首先根据约束映射节点，然后将虚拟链路映射问题看成多商品流问题进行求解.较传统一阶段算法，二阶段算法提高了虚拟网络的接受率和底层物理网络的收益.文献[14]使用贪心算法尽可能为虚拟节点选择负载较轻的物理节点，然后通过最短路径算法寻找2个物理节点间的链路以映射虚拟链路.文献[15]提出了一种增强的虚拟网络映射算法，首先利用离散粒子群算法映射节点，然后再根据最短路径映射边.在粒子初始化中设计了可行性检验机制以过滤掉不可行的候选物理节点，以实现加速算法收敛的目的.该算法相较以前的算法可以获得更好的收益和虚拟网络接受率，但是没有考虑公平性问题和可重用技术的应用，群体初始位置的优化也仍有提高空间.

虚拟网络的重配置是指通过对运行时的虚拟网络进行调度管理，合理地迁移虚拟机和虚拟链路从而优化物理网络的资源利用率.该问题考虑的是如何调度已出租的资源来满足后续虚拟网络接入的需求[16]，比虚拟网络映射问题更加复杂.当底层物理网络资源稀缺时，重配置算法通过周期性地改变运行时虚拟网络的映射方案来获得更多的可用资源.文献[16]针对虚拟网络资源分配产生的底层物理网络资源碎片问题，用已知信息预测资源重配置时间间隔，解决了传统预配置周期固定的问题.文献[17]进一步细化检测机制，定位需要调整的节点和链路，提高了虚拟网络重配置的效率，并且提出了虚拟机的动态迁移机制以保证服务的连续性.文献[18]提出的重配置机制通过迁移代价最小节点来调整虚拟网络拓扑，减少了迁移开销.上述虚拟网络重配置算法通过对运行虚拟网络的映射方案进行调整实现了提高资源利用率的目标，本质是对运行时的虚拟网络拓扑进行变换，但是尽管设计了各种可行的机制，虚拟网络的实时迁移仍然会存在一定的开销.

综上所述，已有的虚拟网络映射方案没有考虑接收公平性问题，这点在实际需求中是应当被关注的.另外，虚拟网络重配置的研究成果对映射问题也有一定启发：可以利用拓扑等价变换的思路，对映射前的虚拟网络进行预配置来减少差异性，这样不仅可以提高资源利用率，还可以解决排队公平性问题.为此，区别于前人工作，本文针对虚拟网络请求的排队公平性问题，借鉴重配置的思路提出了一种虚拟拓扑预配置机制，即在虚拟网络映射前就对其拓扑进行变换从而提高虚拟网络接受公平性及资源利用率.

2 虚拟网络映射问题描述

Fig. 2 Virtual network pre-configuration (merging threshold is 6)图2 虚拟拓扑预配置示意图(该合并阈值为6)

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

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

∀ew∈EV,∀(i,j)∈pi j,ew→pi j,

(1)

∀ew∈EV,ew→pi j,∀i,j∈NS,

(2)

式(1)中第1个约束条件是主机资源约束需满足的条件，即目标物理节点的空闲资源要大于待映射虚拟节点请求的资源；第2个约束条件是物理带宽约束，即虚拟边映射到的每条物理链路的空闲带宽必须大于虚拟链路所请求的带宽.

3 虚拟拓扑预配置机制

现有的虚拟网络映射方案没有考虑虚拟网络请求排队的公平性问题.为了同时映射更多的虚拟网络，算法需要在等待队列中搜索尽可能多的虚拟网络请求.而用户对资源需求的不同会导致其请求的虚拟网络在规模上存在差异，这将导致较小的虚拟网络更容易被映射.虚拟拓扑差异过大也会带来底层物理资源“碎片”而降低资源利用率.现有的重配置方案为了获得更多空闲物理资源，在大虚拟网络无法映射时对已运行的虚拟网络进行迁移，这部分开销完全可以通过对待映射虚拟网络拓扑进行预配置来减轻或避免.

近几年出现的虚拟机间内存交换通道代替网络链路的可重用技术，为虚拟网络拓扑进行节点合并提供了技术原理上的支持.预配置的主要目的是对虚拟网络拓扑进行修剪，以使得队列中的虚拟网络在节点数量上的差别尽可能缩小.预配置的手段是利用物理节点可重用的思想，将虚拟节点数过多的拓扑进行节点合并，达到缩小拓扑规模差异的目的.变换后的虚拟拓扑与原拓扑等价，但节点数更少，从而能够避免公平性问题，也可以减轻物理资源“碎片”的产生并提高利用率.

预配置的实例如图2所示，在不超过给定的合并阈值(CPU、带宽资源需求不得大于6)的情况下尽量合并虚拟拓扑中连通度大的节点，将数个小节点合并成一个大节点以降低较大虚拟网络拓扑的规模，从而缩小虚拟拓扑在规模上的差异.合并后的节点在物理上包含多个虚拟节点，但从资源需求角度考虑，逻辑上变成单个节点，在映射步骤中将作为单个节点被映射.除了能够提高接受公平性，虚拟拓扑预配置的另一个好处就是带宽资源的节省.在图2中，利用虚拟机间的内存交换技术，深色节点的合并令原本存在的部分虚拟链路消失，节点间转为内存直接交换数据，这就使得它们之间的链路对于物理网络带宽资源的需求可以被消除.通过图2的3次拓扑变换，共节省了14单位的带宽资源.

预配置算法设计思路是：首先对等待队列中的虚拟网络请求进行筛选，对于节点数过大(大于给定的节点数限制)的虚拟网络进行拓扑等价变换，以减少队列中虚拟网络请求的拓扑差异.拓扑的变换以尽量消除虚拟链路为目标，利用递归算法，首先定位虚拟拓扑中连通度最大的节点,对该节点的边，根据带宽资源降序排序；然后在不超过合并阈值的情况下对节点进行合并；再进行下一次递归，直至拓扑中所有节点无法再进行合并.预配置具体算法如算法1所示：

算法1. 虚拟网络拓扑预配置算法.

输入：虚拟网络拓扑请求VNRi；

输出：预配置后的拓扑RCVNRi.

① 计算VNRi中的节点数n；

② Ifn>nodes_thresholdthen

③ 找到具有最大连通度的节点vn′；

④ 对于vn′的虚拟边，按照带宽资源请求降序排序，将另外的端点加入待合并节点队列sorted_nodes；

⑤ 依次合并sorted_nodes中节点，合并后的节点CPU资源不得超过C_threshold；由于节点合并而产生的虚拟链路带宽资源不得超过B_threshold；

⑥ 如果新拓扑仍能被合并, 跳转至步骤③；

⑦ End If

⑧ ReturnRCVNRi.

在算法1中，nodes_threshold是拓扑规模阈值，即节点数大于该值的虚拟拓扑需要被预配置；C_threshold和B_threshold分别是CPU合并阈值和带宽合并阈值，即在预配置环节限定合并后的节点CPU和链路带宽资源额度的上限.需要注意的是，阈值对于算法效率存在影响，阈值越小虚拟拓扑的合并程度越小；阈值越大虚拟拓扑合并程度越高，但是合并后的虚拟网络各个节点的资源需求更高，这可能导致后续映射算法在搜索可行解上存在困难.

4 基于DPSO的虚拟网络映射算法

离散粒子群(discrete particle swarm optimization, DPSO)算法是基于群体智能的启发式全局优化技术，群体中的每一个粒子代表待解决问题的一个候选解，算法通过粒子间信息素的交互发现复杂搜索空间中的最优区域，其具有收敛速度快、算法简单、搜索效率高等特点[19].对于式(1)，本文采用离散粒子群算法对其进行求解.本节首先描述映射优化问题的离散粒子群求解算法，然后给出针对强化节点可重用的群体位置分配算法以形成整体算法.

4.1 虚拟网络映射问题的离散粒子群求解算法

(3)

由于离散粒子群的特性，其位置和速度更新公式中的符号需要重新定义以切合实际问题的特点，为此还需给出下列运算符的定义：

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

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

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

根据上述定义及式(3)可以逐轮计算粒子的位置.在此还要给出粒子的适应度计算方法以评判解是否为最优：如果当前粒子的位置代表的解不满足式(1)中的约束条件，则其适应度fitness将被置为+∞；如果当前位置是1个可行解，那么开始进行虚拟边的映射.本文算法在该阶段采用FloydWarshall最短路径算法，同样如果虚拟边映射不成功则适应度置为+∞；如果成功则按照式(3)计算适应度fitness值，即计算虚拟网络在物理网络中占用的总带宽.虚拟网络映射算法如算法2所示：

算法2. 虚拟网络映射算法.

输入：虚拟网络GV；物理网络GS；

输出：映射方案solution.

① 对GS中实时空闲资源的节点队列和链路队列，移除其中空闲资源小于GV中最小节点CPU和链路带宽需求的物理节点和物理链路；

② 对每个粒子，调用位置初始化函数initial-position()；

③ For(inti=0;i

④ 计算每个粒子的适应度值，计算个体最优位置，并调用函数updatePosition()更新粒子速度和位置；

⑤ 如果该粒子处在群体最优位置，则更新群体最优位置gBest和最优适应度值gfitness；

⑥ 如果群体最优位置连续10轮不变则算法终止；}

⑦ 如果群体最优位置存在则返回该位置作为映射方案.

在算法2中，移除空闲资源小于最小请求额度的物理节点和链路是为了尽量缩小算法搜索空间.算法结束的条件是群体最优位置gBest在10轮内不变或者迭代轮数超过给定的最大迭代次数MaxItCount.粒子种群大小的选取是关于求解效率及解优化程度的折中问题，较大的群规模能充分探索解空间，但需要更多的计算时间.种群大小一般取20～50，对于大部分问题，20个粒子已经能取得足够好的结果[20].算法2中的2个粒子位置分配函数updatePosition()和initialposition()将在4.2节进行详细介绍.

4.2 强化可重用的粒子位置分配机制

位置的初始化及更新机制对于粒子群算法的收敛速度有着重要影响.在算法2中，与位置分配相关的函数是updatePosition()和initialposition().在传统算法中，位置的分配只能随机选取物理节点编号，为了充分发挥可重技术能够节省物理带宽消耗的优势，应当把尽量多的同一虚拟网络的节点映射到同一物理节点上.因此有必要在算法的位置更新及初始化过程中加入可重用特性强化机制.

在粒子位置分配强化过程中，既要保证尽量发挥可重用的特性，又不能使得虚拟节点过度集中于某几个物理节点.因为如果在位置初始化时就令虚拟节点过度集中，那么很可能每个粒子都不会获得可行解，即不满足式(1)的约束条件.在没有可行解的情况下无法获得最优适应度值，也就无法获得群体最优位置，这将会导致映射算法无法返回可行的映射方案.另外还要考虑在虚拟网络映射问题中，每个虚拟网络请求的节点数量都不相同，在每个维度上重复分配同1个物理节点的次数应当与虚拟节点的数量、资源请求额度及当前物理节点的平均资源利用率建立动态对应关系.既要保证粒子多样性，又要强化可重用机制，为此引入动态强化因子：

(4)

(5)

其中,GS′是当前虚拟网络映射的搜索空间，即算法2步骤①中获得的子图.对于粒子位置向量的每个维度来说，如果其维度n模k等于0，则重新随机选择1个物理节点，否则保持前一维度所选择的物理节点.这样既可以强化可重用特性，又不至于使得搜索空间被限制，令过大的虚拟网络因为收缩到少数物理节点而找不到可行解.以位置初始化算法initialposition()为例，其伪代码如算法3所示：

算法3. 粒子位置初始化函数initialposition().

输入：物理网络节点数numofsnodes、虚拟网络节点数numofvnodes；

输出：粒子位置position.

① 按照式(4)求k值；

② 随机选取1个搜索空间内的物理节点，将其编号赋值给maph；

③ For (i=0;i

④ If (i%k==0) then 重新选择物理节点并赋值给maph;

⑤position.put(i,maph)；}

⑥ Returnposition.

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

5 实 验

实验采用CloudSim3.0.3[21]仿真平台，硬件平台为IBM X3650服务器.为了仿真拓扑多样性，在CloudSim中用Java语言为底层物理网络和虚拟网络编写了1个拓扑生成器，以连通概率、资源需求边界、节点数量范围作为输入参数生成随机拓扑.式(3)中涉及到的权重设定为φ1=0.1，φ2=0.2，φ3=0.7；离散粒子群算法的终止条件是10轮没有改变全局最优位置或者总迭代次数超过30轮.当有虚拟网络生存周期结束释放资源时，算法搜索等待队列中前20个虚拟网络请求并尝试寻找映射方案.

实验比较了本文提出的基于预配置的算法(PrC-DPSO)与文献[15]中的VNE-UEPSO映射算法的性能表现.比较的参数包含收益成本比、物理网络资源利用率及虚拟网络接受公平性.收益成本比(RC)的定义如式(6)所示：

(6)

其中,Revenue(GV)表示1个虚拟网络请求的CPU资源和带宽资源之和；Co(GV)表示底层物理网络分配给虚拟网络请求的CPU资源和带宽资源之和；T表示时间.实验中，物理网络和虚拟网络的基本参数如表1所示：

Table1 The Basic Experimental Parameter Settings

在表1中，形如100～500的参数设定表示的是虚拟网络中链路的带宽资源在100～500单位之间均匀分布.在本文实验中，每个实验测试1 000个虚拟网络请求的映射，每个实验运行10轮映射，对最终结果求平均值，以保证实验结果的普遍性.

实验1. 比较了不同虚拟链路参数设置下的物理网络收益成本比和资源利用率随时间变化趋势.其中时间的单位为CloudSim中的单位时间.从图3可以看出，本文提出的算法可以显著提高物理网络的收益成本比.单就节点CPU资源来说其收益成本比恒为1，但从链路资源分配的角度考虑，由于可重用机制的应用，在虚拟拓扑预配置及映射过程中都可以将不同节点映射到同一物理节点之上，从而抵消部分虚拟边，因此能够节省物理网络资源的消耗.在2种虚拟网络资源需求参数下，本文提出的PrC-DPSO算法均能够获得大于1的收益成本比.另外从图3中可以看出，对于本文提出的算法，虚拟网络对于带宽的需求参数越高，收益成本比提高越大.1 500时间单位时，在100～200和200～100两种带宽需求参数下，算法的收益成本比分别提高约29%和57%.说明本文提出的预配置算法和可重用强化机制能够起到节省物理网络带宽资源的作用.

Fig. 3 RC of substrate network under different virtual request parameters图3 不同虚拟链路参数下物理网络收益成本比

Fig. 4 Physical node utilization under different virtual link parameter图4 不同虚拟链路参数下物理网络节点资源利用率

实验2. 不同虚拟链路需求参数设定下物理网络资源利用率的比较.从图4可以看出本文提出的算法能够提高物理节点资源利用率，这也可以说明结合预配置机制后，可以减少底层物理网络的资源“碎片”问题，使得底层物理网络可以同时接受更多的虚拟网络.另外，2个算法在虚拟链路带宽需求较低时(100～500)可以获得更好的资源利用率，主要原因是对于虚拟网络映射问题来说，虚拟链路映射要比节点映射更难以找到最优解，但本文算法由于加入了预配置机制，通过降低虚拟拓扑的差异减少了链路映射的难度，因此获得了更好的节点利用率.

Fig. 5 Average nodes number of accepted virtual networks changing over time图5 虚拟网络平均节点数随时间变化趋势

实验3. 虚拟网络排队公平性方面的比较分析.为了突出预配置机制对公平性的提高，实验中虚拟网络链路资源需求设定为250～2 500间均匀分布.实验运行1 000个虚拟网络的映射仿真，统计了每轮被接受的虚拟网络的平均节点数随时间变化的趋势.结果如图5所示，由于本实验设定的虚拟网络的节点个数在2～10之间随机均匀分布，因此2个算法的平均节点数围绕6上下波动.VNE-UEPSO算法没有考虑公平性问题，在映射过程中，较大的虚拟网络很难被接受，只有在物理网络空闲资源较大时才能够被映射，所以平均节点数随时间呈上升趋势，说明较大虚拟网络需要更多排队时间.其后期平均节点数显著上升，最后4轮接受的均是节点数为10的最大虚拟网络，而此时物理网络的利用率较低才有足够空闲的资源来运行较大虚拟网络.相对VNE-UEPSO算法来说，本文提出的PrC-DPSO算法因为加入了预配置机制，可以减少虚拟网络拓扑差异性，这使得在映射方案搜索时不存在过于复杂的拓扑，因此本文所提出算法的平均节点曲线略平滑，且不会在后期显著上升.另外，从图5中还可以看出，得益于拓扑预配置机制的应用，在同样条件下本文提出的算法完成同样数量的虚拟网络请求所用时间更短(节省约11%的总运行时间)，因此本文提出的虚拟网络映射算法在提供接受公平性的同时也节省了物理网络的总运行时间.

6 结束语

本文从提高虚拟网络接受公平性和物理网络收益角度出发，提出了基于虚拟拓扑预配置及可重用技术的虚拟网络映射算法.在虚拟网路映射前加入拓扑预配置机制以减少虚拟拓扑的差异性，避免了较大虚拟网络难以求解映射方案的问题，从而提高了接受公平性.在预配置和映射阶段均采用了可重用技术，提高了物理网络的资源利用率.本文所提出的算法在支持相同数量及结构的虚拟网络时产生的开销更小，并且能够提供更好的公平性支持；另外，得益于预配置及粒子初始位置的强化机制，本文所提出的算法也有助于提高物理网络资源利用率.

[1]Chowdhury N M M K, Boutaba R. Network virtualization: State of the art and research challenges[J]. IEEE Communications Magazine, 2009, 47(7): 20-26

[2]Shi Xuelin, Xu Ke. Utility maximization model of virtual machine scheduling in cloud environment[J]. Chinese Journal of Computers, 2013, 36(2): 252-262 (in Chinese)(师雪霖, 徐恪. 云虚拟机资源分配的效用最大化模型[J]. 计算机学报, 2013, 36(2): 252-262)

[3]Deng Gang, Gong Zhenghu, Wang Hong. Characteristics research on modern data center network[J]. Journal of Computer Research and Development, 2014, 51(2): 395-407 (in Chinese)(邓罡, 龚正虎, 王宏. 现代数据中心网络特征研究[J]. 计算机研究与发展, 2014, 51(2): 395-407)

[4]Vidya K B, Ajit S M. Cloud resource provisioning for Amazon EC2[C]Proc of the 4th IEEE Conf on Computing Communications and Networking Technologies. Piscataway, NJ: IEEE, 2013: 1-7

[5]Cheng Xiang, Zhang Zhongbao, Su Sen, et al. Survey of virtual network embedding problem[J]. Journal on Communications, 2011, 32(10): 143-141 (in Chinese)(程祥, 张忠宝, 苏森, 等. 虚拟网络映射问题研究综述[J]. 通信学报, 2011, 32(10): 143-141)

[6]Li Xiaoling, Wang Huaimin, Ding Bo, et al. Research and development of virtual network mapping problem[J]. Journal of Software, 2012, 23(11): 3009-3028 (in Chinese)(李小玲, 王怀民, 丁博, 等. 虚拟网络映射问题研究及其进展[J]. 软件学报, 2012, 23(11): 3009-3028)

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

[8]Lu Jing, Turner J. Efficient mapping of virtual networks onto a shared substrate, WUCSE-2006-35[R]. Washington: Department of Computer Science and Engineering, Washington University, 2006

[9]Fan J, Ammar M. Dynamic topology configuration in service overlay networks: A study of reconfiguration policies[C]Proc of the 25th IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2006: 1-12

[10]Zhu Y, Ammar M. Algorithms for assigning substrate network resources to virtual network components[C]Proc of the 25th IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2006: 21-32

[11]Ines H, Wajdi L, Djamal Z. A distributed virtual network mapping algorithm[C]Proc of the IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2008: 5634-5640

[12]Jens L, Holger K. A virtual network mapping algorithm based on subgraph isomorphism detection[C]Proc of the ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures. New York: ACM, 2009: 81-88

[13]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

[14]Yong Z, Mostafa A. Algorithms for assigning substrate network resources to virtual network components[C]Proc of the 25th IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2006: 1-12

[15]Zhang Zhongbao, Cheng Xiang, Su Sen, et al. A unified enhanced particle swarm optimization-based virtual network embedding algorithm[J]. Internet Journal of Communication Systems, 2013, 26(8): 1054-1073

[16]Zhang Shunli, Qiu Xuesong,Pan Yalian, et al. Forecast-based resource reconfiguration algorithm for network virtualization[J]. Journal on Communications, 2011, 32(7): 57-70 (in Chinese)(张顺利, 邱雪松, 潘亚莲, 等. 网络虚拟化环境下基于预测的资源重配置算法[J]. 通信学报, 2011, 32(7): 57-70)

[17]Bassem W, Nancy S, Ahmed K. Substrate network house cleaning via live virtual vetwork migration[C]Proc of 2013 IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2013: 2256-2261

[18]Samantha L, Mostafa A, Ellen Z. Design and analysis of schedules for virtual network migration[C]Proc of the International Federation for Information Processing Networking Conf. Piscataway, NJ: IEEE, 2013: 1-9

[19]Ma Xuan, Liu Qing. Particle swarm optimization for multiple multicast routing problem[J]. Journal of Computer Research and Development, 2013, 50(2): 260-268 (in Chinese)(马炫, 刘庆. 多组播路由问题的粒子群优化算法[J]. 计算机研究与发展, 2013, 50(2): 260-268)

[20]Wang Weibo, Lin Chuan, Zheng Yongkang. The experiment and analysis of parameters in particle swarm optimization algorithm[J]. Journal of Xihua University: Natural Science Edition, 2008, 27(1): 76-80

[21]Rodrigo N C, Rajiv R, Anton B, et al. CloudSim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software: Practice and Experience, 2011, 41(1): 23-50

Wang Cong, born in 1981. PhD and lecturer in Northeastern University at Qinhuangdao. Member of CCF. His main research interests include virtual network embedding, resource allocation in data center.

Yuan Ying, born in 1981. PhD and lecturer in Northeastern University at Qinhuangdao. Member of CCF. Her main research interests include virtual network embedding, virtual resource allocation in cloud computing (yuanying1121@163.com).

Peng Sancheng, born in 1974. PhD and professor in Guangdong University of Foreign Studies. Senior member of CCF. His main research interests include network and information security, trusted computing, and mobile computing (psc346@aliyun.com).

Wang Xingwei, born in 1968. PhD, professor and PhD supervisor in Northeastern University. Senior member of CCF. His main research interests include future Internet, cloud computing, network security and information security.

Wang Cuirong, born in 1963. PhD and professor in Northeastern University at Qinhuangdao. Member of CCF. Her main research interests include routing protocol, network security and sensor networks (wcr@mail.neuq.edu.cn).

Wan Cong, born in 1983. PhD and lecturer in Northeastern University at Qinhuangdao. Member of CCF. His main research interests include cloud computing, parallel algorithm design (wancong@neuq.edu.cn).

Fair Virtual Network Embedding Algorithm with Topology Pre-Configuration

Wang Cong1, Yuan Ying1, Peng Sancheng2, Wang Xingwei3, Wang Cuirong1, and Wan Cong1

1(CollegeofComputerandCommunicationEngineering,NortheasternUniversityatQinhuangdao,Qinhuangdao,Hebei066004)2(CiscoSchoolofInformatics,GuangdongUniversityofForeignStudies,Guangzhou510420)3(SoftwareCollege,NortheasternUniversity,Shenyang110819)

Virtual network embedding (VNE) is critical fundamental technology to archive multi resource tenancy in cloud environment. It aims to embed virtual networks into appropriate underlying physical substrate network under the premise of satisfying the resource demand of virtual networks. Most research achievements of the existing VNE algorithms aim at maximizing the physical resource utilization, but consider less about the fairness problem in virtual network request reception. This paper puts forward a pre-configured virtual network mapping algorithm to improve the mapping of fairness, in which the mapping process are divided into two steps: topology pre-configuration phase and embedding phase. In pre-configuration phase, larger virtual network topologies are transformed to equivalent but smaller ones with less number of nodes and links. Such mechanism can reduce differences between virtual network requests so as to improve reception fairness. In mapping phase, we establish a formal VNE model, and use the discrete particle swarm optimization algorithm to solve the model. In order to improve the physical network resource utilization, a particle position enhancement mechanism is introduced leveraging node repeatable technology to save bandwidth resource. Simulation results show that the proposed algorithm is superior to the existing similar algorithms in physical network resource utilization, revenuecost ratio and reception fairness.

network virtualization; virtual network embedding; node reusable; virtual topology pre-configuration; discrete particle swarm optimization algorithm

2015-09-01；

2016-06-02

国家杰出青年科学基金项目(61225012，71325002)；国家自然科学基金项目(61300195，61379041)；河北省自然科学基金项目(F2014501078，F2016501079) This work was supported by the National Natural Science Fund for Distinguished Young Scholars of China (61225012, 71325002)，the National Natural Science Foundation of China (61300195, 61379041), and the Natural Science Foundation of Hebei Province of China (F2014501078, F2016501079).

王兴伟(wangxw@mail.neu.edu.cn)

TP393.02