虚拟网络映射模型及优化算法研究

摘要

网络虚拟化被认为是最可能有效解决网络僵化问题的技术方案之一。网络僵化指的是，传统的网络体系结构受制于固有的基于TCP/IP模式的数据传输方式，将无法始终满足日益增长的、具有多种不同服务质量需求(QoS)的数据传输的要求。为了突破网络僵化带来的限制，网络虚拟化技术方案尝试将互联网中服务供应商(ISP)所提供的功能分成两部分:其一是基础设施供应商(InP)功能，它负责建立与维护底层物理网络基础设施;另一部分是服务供应商(SP)功能，负责租用底层物理网络的基础设施资源来提供数据传输服务。SP根据所需传输的数据的服务质量需求的不同，从InP处租赁使用部分底层物理网络资源，如底层物理网络结点的CPU计算资源和底层链路的带宽资源，来搭建并部署所需的虚拟网络，运行指定的协议以完成既需的数据传输服务。作为网络虚拟化技术方案中所包含的难点之一，虚拟网络映射(VNE)问题研究的是如何有效地将SP通过整合资源需求所抽象出的不同虚拟网络部署到底层物理网络拓扑中，使得数据传输的服务质量需求能够得以满足的前提下，提升收益并使得租赁代价最小。虚拟网络映射问题包括结点映射以及链路映射两个阶段，并且两个阶段都可以被归约成NP-难问题。解决NP-难问题我们经常需要使用启发式算法或者近似算法。
　　链路映射阶段的主要任务，是在满足带宽、延迟等需求的前提下，将虚拟结点间存在的虚拟链路，部署到已对应好的物理结点间的一条或多条路径上。根据映射到的底层路径的条数不同，链路映射阶段所采用的算法可以被划分成两类，即单路径映射和多路径映射。单路径映射是指，对应底层结点间，只允许一条物理路径承担一条虚拟链路中的全部流量资源需求。而多路径映射是指，一条虚拟链路的流量需求可以被拆分开并分别被部署在底层对应结点间的多条路径上。单路径映射的优势是可以降低虚拟网络的链路映射代价，并且尽可能少占用底层资源以留备后续虚拟请求的使用。而可能存在的问题之一，是使用最短路径进行映射时，可能造成局部优质链路被频繁使用而形成资源瓶颈。多路径映射的优势是可以充分利用多条路径资源，通过流量分割将单条带宽需求过高而不能完成映射的链路安排到多条路径中去，从而提高映射成功率。而可能出现的问题之一，是被映射到的底层结点，若其之间的链路资源不充足，便无法支持多路径映射的完成。由于上述提到的两种映射中可能出现的问题均是由于结点映射位置不当所致，因此，如何合理完成结点映射，使得上述单路径以及多路径映射中存在的问题得以有效解决，是本文讨论的重点。另外，衡量底层路径优劣的指标有多种，如带宽、延迟、跳数等。由于链路映射时算法往往会将虚拟链路映射到底层质量较高的路径上，以提供高质量的数据传输服务。因此，对路径质量的评价会影响到虚拟网络映射效果。如何在多种指标共存的度量环境中推荐出待选的优质路径，也是本文讨论的重点。
　　本文的研究工作有三个方面:一是在分析虚拟网络映射领域已有工作的基础上，发现并提出单路径映射中存在的最短路径瓶颈问题，并使用重新定义的度量值路径相关性，结合蚁群智能算法，尝试给出相应的结点映射算法ACO-PR。二是尝试提出最大邻接容量这一新的结点邻域资源度量值，并尝试提出解决多路径映射中存在的，链路丰富度不足导致多商品流MCF算法失效的MARANK算法，并分析算法重新计算时机对最终接受率的影响。三是尝试提出基于路径代数框架的虚拟网络映射算法GBPA，测量将不同跳数距离之内的邻居加以考虑而量化的邻域资源与最终映射效果之间的关系并将路径代数框架引入虚拟网络链路映射阶段，以解决路径质量评价问题。仿真结果显示，文章中所提出的两种虚拟网络结点映射算法ACO-PR以及MARANK结合多商品流算法与最短路径算法，以及基于路径代数的映射算法GBPA，均在提高虚拟请求接收率、提升映射收益方面有着提升的表现。

目录

声明

摘要

1．1 课题的研究背景及意义

1．2 国内外研究现状

1．3 本课题的研究内容

1．4 论文的组织结构

第2章 虚拟网络映射模型及相关研究

2．1 虚拟网络映射模型介绍

2．2 虚拟网络映射模型评价指标

2．3 虚拟网络映射相关研究分析

第3章 一种基于路径相关性的虚拟网络结点映射算法

3．1 算法动机

3．2 算法描述

3．2．1 新的结点映射结果度量值--路径相关性

3．2．2 基于路径相关性的蚁群结点映射算法

3．3 算法仿真与评价

第4章 一种基于最大邻接容量的虚拟网络结点映射算法

4．1 算法动机

4．2 算法描述

4．2．1 新的结点邻域资源丰富度度量值—最大邻接容量

4．2．2 基于最大邻接容量的虚拟网络结点贪婪映射算法

4．2．3 算法重新计算时机

4．3 算法仿真与评价

第5章 一种基于宽度优先搜索和路径代数的虚拟网络映射算法

5．1 算法动机

5．2 算法描述

5．2．1 基于宽度优先搜索的邻域资源定义

5．2．2 基于宽度优先搜索的虚拟网络贪婪结点映射算法

5．2．3 基于路径代数的虚拟网络链路映射算法

5．3 算法仿真与评价

第6章 结论

参考文献

致谢

攻读学位期间发表的学术论文目录