面向高效资源分配的虚拟网络部署问题研究

发布时间：2019-10-13 14:32

【摘要】：网络虚拟化环境中,服务提供商的需求不再是分散的计算或网络资源,而是有结构的资源组合—虚拟网络。如何在共享的物理网络之上合理地部署虚拟网络资源请求,实现高效物理资源分配,成为一个重要的研究问题。尽管已有大量研究,我们发现大部分已有工作未考虑虚拟网络的动态资源需求或虚拟机的部署位置限制需求。一方面,终端用户的随机性及程序本身的动态性,使得虚拟网络中实际被使用的物理资源量动态波动；另一方面,服务提供商常常希望部分虚拟机的物理部署位置满足某些条件,以实现安全备份或网络覆盖等应用目的。本文基于上述理解,分别对动态资源需求和位置限制需求情形下的虚拟网络资源请求的部署问题进行了较为深入的研究。此外,本文还考察如何从单个物理节点、单个物理网络及多个物理网络三个层次出发,优化虚拟网络部署性能。本文主要贡献可概括如下：(1)针对动态资源需求下的虚拟网络部署问题,提出了一种描述动态资源需求的模型,并设计了基于机会资源共享的虚拟网络部署框架ORS。ORS通过在多个服务提供商之间合理地共享资源,减少了单个服务提供商的租借费用,同时增加了基础设施提供商的收益。在宏观层面上,基于贪婪策略分别产生从虚拟机到物理机和从虚拟链路到物理路径的映射；在微观层面上,将机会资源共享问题形式化为时间片分配问题。我们通过将三划分问题规约到该问题,从而证明该问题为NP难的,并提出了基于整数线性规划的最优算法和两种分别基于冲突概率和资源需求期望的首次适应算法,并给出了后两种算法的近似比。为避免物理资源碎片化,还提出了阶段性重调整策略。仿真结果表明,相比两种经典算法,ORS能够显著提高物理资源利用率和虚拟网络请求接受率。(2)针对物理位置限制需求下的虚拟网络部署问题,提出了绝对位置需求与相对位置需求的模型,并设计了分别侧重提升物理资源利用率和提供资源分配弹性的部署算法MIPA和SAPA。算法MIPA通过引入额外的辅助节点,将部署问题转化为多商品流问题；基于容量约束、流约束和辅助节点约束等条件,建立混合整数规划模型,通过线性放松和随机取整生成部署方案。算法SAPA通过定义合理的邻居方案生成方法及能量计算方法,借助模拟退火框架给出部署方案,并允许基础设施提供商通过调整迭代次数来灵活地控制算法性能与运行时间之间的均衡。仿真结果表明了两种算法各自的特性与优势。(3)从多层次出发考察如何基于单个物理节点、单个物理网络和多个物理网络优化虚拟网络部署性能。在底层物理节点支持并行计算时,将单个虚拟机映射到多个物理节点,提出了基于并行支持的部署算法ProactiveP和LazyP;通过将来自同一个虚拟网络请求的虚拟机尽量部署在物理位置相近的区域,从而有效地减少虚拟链路在底层物理网络中的延伸,提出基于马尔可夫链的节点排序算法MCRank;在多虚拟网络资源请求和多物理网络并存的情形下,为避免虚拟网络部署请求的不稳定分配,通过构建偏好表,提出了基于proposal的虚拟网络请求分配算法PGA。仿真结果证明了所提算法的可行性与有效性。
【学位授予单位】：南京大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TP393.01

【相似文献】