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

Fair Virtual Network Embedding Algorithm with Topology Pre-Configuration

作　　者：王聪[1] 苑迎[1] 彭三城[2] 王兴伟[3] 王翠荣[1] 万聪[1] 

机构地区：[1]东北大学秦皇岛分校计算机与通信工程学院,河北秦皇岛066004 [2]广东外语外贸大学思科信息学院,广州510420 [3]东北大学软件学院,沈阳110819

出　　处：《计算机研究与发展》2017年第1期212-220,共9页Journal of Computer Research and Development

基　　金：国家杰出青年科学基金项目(61225012;71325002);国家自然科学基金项目(61300195;61379041);河北省自然科学基金项目(F2014501078;F2016501079)~~

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

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

分 类 号：TP393.1[自动化与计算机技术—计算机应用技术]