摘 要

随着互联网用户的爆炸式增长以及互联网服务的快速发展，网络僵化问题越来越严重。网络虚拟化为解决这一问题提供了有效途径，其中主要问题为虚拟网络映射问题，即如何利用有限的物理资源容纳更多的虚拟网络。由于网络服务的多元化发展，往往需要多个底层网络提供商合作部署虚拟网络；另外，由于底层网络故障不可避免，如何保障映射到底层网络的虚拟网络的可生存性以降低由此造成的经济损失十分重要。

针对单链路故障情况下跨域映射的虚拟网络可生存性问题，本文提出一种基于蚁群算法的跨域虚拟网络映射算法。首先，为确保域间映射的虚拟链路的可生存性，需要在单链路故障时维持虚拟网络域间链路部分的可连通性，在虚拟网络拓扑分割时，将为同一虚拟网络中跨域映射的所有虚拟链路选择一条域间路径且虚拟链路与其域间路径一一对应作为前提条件，使用蚁群算法寻找域间链路映射成本最小的虚拟网络拓扑分割方案。其次，为确保域内映射的虚拟链路的可生存性，将物理链路发生故障次数作为物理链路可靠性度量指标，根据物理节点可用计算资源、邻接链路可用带宽资源与邻接链路可靠度对物理节点进行排序，然后采用虚拟节点与链路协同映射的方法进行域内映射；为域内映射的虚拟链路提供备份资源，采用K最短路径法构建虚拟链路备用路径集合，单链路故障时，选取备用路径集合中剩余带宽资源最丰富的物理路径重映射失效虚拟链路。仿真结果表明，本文算法提高了长期平均收益与开销比。

关键词：虚拟网络映射；跨域映射；可生存性；蚁群算法；单链路故障

Abstract

With the explosive growth of the population of Internet users and the rapid development of Internet services, the problem of ossification has become more and more serious. The network virtualization technology provides an effective method to this problem. Virtual network embedding is the key problem of network virtualization, which studies how to use limited substrate network resources to support more virtual network. In some cases, it’s necessary for multiple domains to collaborate to map the same virtual network due to diversified development of the network. In addition, it’s significant to guarantee the survivability of the virtual network embedded on the substrate network as the substrate network fault is unavoidable.

This thesis proposes a multiple domain virtual network embedding algorithm based on ant colony algorithm against single link failure. First, the thesis keeps the connectivity of the inter-embedded virtual network to insure the survivability of the inter-embedded virtual link; then uses ant colony algorithm to search a virtual network decomposition solution with the minimum inter cost, under the condition that each virtual link in the same virtual network has a unique inter path. Then, the thesis uses fault numbers to measure the reliability of a substrate link; puts forward a substrate node sort method considering node usable resources, adjacency links’ available band resources and reliability, then the intra domain virtual network is embedded using node-link collaborative mapping method.; then provides each intra-embedded virtual link a path backup, in which the back path with the most abundant available resources will be chosen to map the fail virtual link against single link failure. As the simulation results shows, the algorithm improves the long-term average revenue and cost radio.

Key words: virtual network embedding; multiple domains; survivability; ant colony algorithm; single link failure

目录

第1章 绪论 1

1.1 国内外研究现状 1

1.2 主要工作 3

1.3 论文内容安排 3

第2章 网络模型 4

2.1 物理信息描述 4

2.2 网络模型描述 4

2.2.1 物理网络模型 4

2.2.2 虚拟网络模型 4

2.2.3 集中式跨域虚拟网络映射算法举例 5

2.3 评价指标 6

2.4 本章小结 7

第3章 基于蚁群算法的跨域虚拟网络映射算法设计 8

3.1 算法简介 8

3.2 蚁群优化算法 9

3.3 基于蚁群算法的虚拟网络拓扑分割算法 10

3.3.1 构建边界节点候选集 10

3.3.2 域间链路映射 10

3.3.3 虚拟网络拓扑分割 11

3.4 基于蚁群算法的域内映射算法 15

3.4.1 构建候选物理节点集合 15

3.4.2 节点映射和链路映射 16

3.4.3 虚拟链路恢复机制 19

3.5 本章小结 21

第4章 仿真与分析 23

4.1 仿真环境 23

4.2 对比算法介绍 23

4.3 仿真结果分析 24

4.3.1 虚拟网络拓扑分割时间对比 24

4.3.2 虚拟网络请求映射成功率 25

4.3.3 长期平均收益开销比 26

4.4 本章小结 27

第5章 总结 29

参考文献 30

致谢 32

第1章 绪论

1.1 国内外研究现状

随着网络用户的发展和用户对网络服务需求的增加，传统网络僵化问题造成的影响日益凸显。网络虚拟化技术为解决该问题提供了有效途径，其核心问题是虚拟网络映射(VNE)，VNE问题已被证明是NP-Hard问题。传统的互联网服务提供商在网络虚拟化技术中被分为底层基础设施提供商（Infrastructure Provider ,InP）和服务提供商（Service Provider ,SP），InP负责底层网络物理资源的维护并为虚拟化网络服务提供物理资源的支持，SP租用InP向网络用户提供虚拟化网络服务。

目前，关于VNE问题，很多研究以提高底层网络运营商的收益为目标，致力于提高VNE的成功率和底层物理资源利用率。然而，一旦底层物理网络因自然灾害或人为因素发生节点或链路故障，将导致在故障节点或链路上映射的虚拟网络请求（Virtual Network Request ,VNR）服务失败，这将造成严重的损失。为了确保虚拟网络的可靠性映射，现阶段研究人员主要提出了保护和恢复两种机制；保护机制预先提供备份资源，而恢复机制则在故障发生后利用剩余物理资源对失效的虚拟节点或虚拟链路进行重映射；现有的可生存性虚拟网络映射算法（Survivable Virtual Network Embedding , SVNE）主要根据是否提供备份资源进行分类，主要解决SVNE问题的方法是提供备份资源，提供备份方法又根据备份资源分配时间划分为映射前预留和映射中分配备份资源两种方法。文献将物理链路资源预先分为主用资源和备用资源，通过调整主用资源和备用资源的比例来寻求最低映射费用；另外文献利用多区域灾难评估模型评价链路潜在故障，仅对主用路径不满足可靠性要求的虚拟链路寻找备用路径。文献使用映射中在重映射阶段为虚拟节点和虚拟链路构建备份集合，以缩短重映射时间。文献使用映射中分配备份资源的方法，在VNR到之前采用路径选择算法，为每个物理链路构建备份路由集以缩短链路重映射时延。备份机制与恢复机制各有利弊，使用备份机制会导致提前占用物理资源，降低虚拟网络的映射成功率；而在故障后再寻找一条新的路径，会由于物理资源的不足，找不到合适的物理路径，提高虚拟网络重映射的失败率。另外，很多研究在提供备份资源的同时，提出了评估物理链路和物理节点的方法，以选择可靠性较高的节点进行映射。文献在VNE映射阶段都重新定义了节点计算资源，融合了物理节点邻接链路资源如可用带宽资源、链路故障等因素。