虚拟网络映射算法研究开题报告

全文总字数：4027字

1. 研究目的与意义（文献综述）

随着网络用户的发展，网络僵化问题影响了用户体验，制约了互联网架构的创新和发展。网络虚拟化技术被视为解决网络僵化问题的有效途径，其核心问题是虚拟网络映射(vne)，vne问题已被证明是np-hard问题。网络虚拟化环境下，传统的互联网服务提供商被分为底层基础设施提供商（inp）和服务提供商（sp），inp维护并部署底层网络资源，sp租用inp向网络用户提供虚拟化网络服务。目前，关于vne问题，很多研究以提高底层网络运营商收益为目标，致力于提高vne的成功率和底层物理资源利用率。然而，一旦底层物理网络因自然灾害或人为因素发生节点或链路故障，在故障节点或链路上映射的虚拟网络请求（vnr）服务失败，这将造成严重的损失。针对虚拟网络的可靠映射问题，目前主要有两种机制，分别是保护和恢复机制，保护机制预先准备备份资源，恢复机制在故障发生后启动备份恢复机制；而现有的可生存性虚拟网络映射算法（svne）根据是否提供备份资源进行分类，但主要解决svne问题的方法是提供备份资源[1]。文献[2,3]将物理链路资源预先分为主用资源和备用资源，通过调整主用资源和备用资源的比例来寻求最低映射费用；另外文献[3]利用多区域灾难评估模型评价链路潜在故障，对主用路径不满足可靠性要求的虚拟链路寻找备用路径。文献[4]在重映射阶段为虚拟节点和虚拟链路构建备份集合，以缩短重映射时间。文献[5]在vnr到之前采用路径选择算法，为每个物理链路构建备份路由集以缩短链路重映射时延。其实，很多研究在提供备份资源的同时，提出了评估物理链路和物理节点的方法，以选择可靠性较高的节点进行映射。文献[2-5]在vne映射阶段都重新定义了节点计算资源，融合了物理节点邻接链路资源如可用带宽资源、链路故障等因素。

以上算法主要针对单域映射，文献[2]提出了跨域映射算法，以保证虚拟节点找到满足计算资源等条件的物理节点。然而该文献所提算法没有考虑vne映射在不同inp上带来的问题。跨域映射可以有效地解决单域映射内因物理节点资源不足导致的vnr映射失败的问题。目前跨域预映射算法主要分为集中式和分布式两类，集中式引入虚拟网络提供商（vnp）作为中间角色与各inp协商并从sp处接受vnr，各inp向vnp提供的资源信息有限，具体为域内节点静态信息（可用计算资源、地理位置、价格）、对等链路信息（顶点、可用带宽资源、单价）、域内链路的单价、接入点层次拓扑结构；而分布式跨域算法不泄露各inp的所有信息，引入竞价机制分配vnr[7,8]。目前关于跨域网络中的svne算法研究主要使用集中式跨域映射。文献[8]主要针对如何保障域间链路的可生存性进行研究，应用以下思想：当且仅当虚拟网络的每个原始割集中至少有一条链路不经过失效链路时，该虚拟网络具有可生存性。文献[9]提出了全局资源容量评价物理节点。文献[10]引入安全等级，根据虚拟节点和链路的安全等级将它们分配到不同安全级别的云上，且备份资源与主用资源部署在不同的云中。文献[11]对域间和域内链路分别使用优化离散粒子群和基于kruskal最小生成树算法进行映射。文献[12]使用优化人工蜂群算法完成域间请求到域内请求的划分，每个inp对应的子vnr即为一个蜜源，由蜜源对应的雇佣蜂根据蜜源选择准则寻找最优的映射方案。近年来，研究者利用演进算法有效的解决了包括np-hard问题在内的计算复杂的问题，且基于演进算法的跨域虚拟网络映射算法相比于其他集中式跨域映射算法更有优势[7]。

本设计对多域环境下虚拟网络的可生存性展开研究，以提高多域虚拟网络的可生存能力，减少网络故障对inp造成的损失。且多域环境中可以有效解决单个物理网络中找不到合适物理资源的问题，提高vnr接受率。

2. 研究的基本内容与方案

提出一种基于蚁群优化的多域可生存性虚拟网络映射算法。首先明确最基本的映射目标为保证虚拟网络的可生存性，映射方案引入备份机制，将物理资源分为主用流和备用流资源，将虚拟节点尽可能映射到既满足计算资源需求且可靠性又比较高的物理节点上，为虚拟链路提供主用路径的同时提供备份路径[2-6]。为了保障在多个物理网络上映射的虚拟网络的可生存性，采用集中式跨域映射算法，引入VNP作为中间角色，根据文献[7,8]各InP能够向VNP提供的信息有：域内节点信息（节点资源、位置、价格）、对等节点信息、域内链路单价、对等链路（可用资源、顶点、单价）。由于评估物理节点及链路需要更多的网络拓扑信息，采用文献[15]中的由VNP依次指定各InP映射其域内及其对等节点链路的方法，由各InP单独映射与之相关的VNR部分。VNR的分解主要是针对虚拟节点的分解，在满足节点需求的同时使节点映射费用尽可能小，VNP根据这一要求分解VNR并分配给相应的InP[8]。每个InP进行节点映射时，引入文献[6]物理节点可靠度和虚拟节点重要度概念，分别对物理节点和虚拟节点进行排序，使用蚁群算法完成节点的映射，然后将节点映射结果反馈给VNP。InP按照域内虚拟节点重要度总和由高到低的顺序依次进行链路映射，根据[15]，VNP会为当前进行映射的InP提供剩余物理网络的简化拓扑结构包括其他InP上虚拟节点的映射信息以及域间节点或链路信息和与该InP有关的虚拟链路要求，使用文献[2]提出的GSVNE算法为虚拟链路寻找主用路径和备用路径。

3. 研究计划与安排

第1-3周：完成开题报告；

第4周：进一步学习现有的蚁群优化算法，提出具体的节点映射方案；

第5-6周：完善提出的虚拟网络映射算法，完成算法的编程实现；

4. 参考文献（12篇以上）

[1]黄丽萍,杨龙祥.可生存性虚拟网络映射算法的研究[j].计算机技术与发展,2018,28(07):144-148.

[2]肖宪翠. 可生存性虚拟网络映射模型及算法研究[d].山东师范大学,2017.

[3]陈德润. 弹性光网络的多故障生存性虚拟网络映射方法研究[d].重庆邮电大学,2019.