虚拟网络映射策略与算法研究

发布时间：2018-05-29 07:25

本文选题：网络虚拟化 + 虚拟网络映射　；参考：《北京邮电大学》2014年博士论文

【摘要】：网络虚拟化是克服当前互联网发展和创新“僵化”困局的有效途径,并不断地得到新技术、新应用的支持,吸引了越来越多的关注。网络虚拟化的目标是要通过抽象、分配和重构等方法在公共的底层物理网络之上构建出完全虚拟化的网络环境。在虚拟网络环境中,虚拟化平台屏蔽底层基础网络的具体实现,在其之上构建虚拟网络环境,控制可用的虚拟资源,根据业务和需求定制网络架构和网络协议并实时地、动态地调用和调节底层网络资源。作为实现未来网络的关键技术,网络虚拟化技术有助于解决当代网络的现有问题,并将新技术的实验和应用成为可能,具有很大的灵活性。网络虚拟化技术对于未来网络的发展有着重要的意义：其一、它通过创建未来网络的实验平台,能够支持更加有效地验证最新提出的新技术和新架构,使得多种创新型的网络架构可以在同一个共享的物理基础设施上并行运行而互不干扰；其二,它能够实现数据平面和控制平面的分离,这体现了其本质特征是要对物理资源和行为进行抽象化,这种特征也正在逐渐成为未来网络体系结构的一个基本功能。虚拟网络映射问题是指,将从不同用户收集到的虚拟网络请求有效、高效和健壮的分配到给定的实体网络上,并且能够满足这些虚拟请求对于物理资源(比如节点计算能力、链路带宽等)的要求。虚拟网络映射算法的性能和效果对于网络虚拟化技术的实用化和产业化有学术上的指导意义,具有重要的研究价值。本文将对虚拟网络的映射策略和映射算法进行专题的研究和探讨,以虚拟网络请求的接受率、实体网络资源利用率、算法实时性等指标作为评价指标,提出有效和高效的新算法,并扩展应用到更加实际的网络环境中,推进不断的改进和优化,进而构建一个包含多种算法的虚拟网络映射研究平台和一整套有效、高效、健壮和可行的虚拟网络映射解决方案,利于开展进一步的研究工作。本文的主要创新包括以下几个方面： 1)虚拟网络映射的目标是有效地、高效地和健壮地将虚拟网络请求的虚拟节点和虚拟链路映射到实体网络的资源上。以前的研究侧重于设计基于启发式算法或尝试通过两个阶段解决方案求解,节点映射是第一阶段,链路映射是第二阶段。我提出一个新的基于整数规划的虚拟网络映射算法。通过建立一个增强的实体网络模型来将虚拟网络映射问题定义为由一个目标函数和一些约束组成的整形规划问题,求解这个数学问题就可以得到最优化的映射结果。一个拓扑相关的因子将被添加到目标函数中。此方法在一个步骤内解决了虚拟网络映射问题。仿真结果清楚地表明,这个算法大大提高了性能的接受率,增加了收益/成本比和收益的同时减少了虚拟网络映射的成本。 2)基于整数规划的虚拟网络映射算法是一个有效和高效的映射算法。但这个算法的的应用场景没有考虑物理网络资源可能发生故障的情形,这就是所谓可生存的虚拟网络嵌入问题。过去的网络虚拟化的可生存策略,通过提供预先备份的物理资源,并将所有类型的物理故障作为一个或者多个链路故障处理。在本文中,我提出了动态恢复(Dynamic Recovery)方法并来解决可生存的虚拟网络映射问题,这个方法是基于整数规划的虚拟网络嵌入算法之上运用的。首先,动态恢复算法不需要提前备份物理资源,使得在嵌入的时候有更多的物理资源可以使用。其次,只有当物理故障发生时动态恢复过程才会被激活。最后,它分别使用不同的算法来恢复节点故障和链路故障。仿真结果表明,该方法能够成功地通过寻找替代节点和路径恢复绝大多数的物理故障,而且它的各项性能非常接近不考虑物理故障的纯虚拟网络映射的试验结果。 3)为了提高虚拟网络映射算法的适应性,节省计算时间和计算空间并提高虚拟网络映射的成功率,我提出了一个将大的虚拟网络请求提前进行分割为多个子网络然后再依次进行映射的虚拟网络映射改进策略。首先,说明提出改进策略的动机。其次,对于达到一定规模的虚拟网络图形进行分割为数个虚拟网络子图subVNs。最后,分别对每个子图进行虚拟网络嵌入操作并合并得到的结果。仿真结果表明,该方法提高了虚拟网络嵌入的接受率,节省了运算时间。通过分割网络拓扑,使得将较大较复杂的虚拟网络请求更容易映射成功,甚至可以满足虚拟节点数大于实体节点数的虚拟网络映射条件。因此,分割大的虚拟网络图形再进行虚拟嵌入的方式是虚拟网络映射一个可以参考的改进方向。
[Abstract]:Network virtualization is an effective way to overcome the "rigid" dilemma of the current Internet development and innovation, and the support of new technologies and new applications has attracted more and more attention. The goal of network virtualization is to build a completely virtualized network on the public underlying physical network through the methods of abstraction, distribution and reconstruction. In the virtual network environment, the virtualization platform shields the concrete realization of the underlying underlying network, constructs a virtual network environment on it, controls the available virtual resources, customize the network architecture and network protocols according to business and requirements, and dynamically invoke and adjust the underlying network resources in real time as the key to the realization of the future network. Technology, network virtualization technology can help solve the existing problems of contemporary network, and make the experiment and application of new technology possible. It has great flexibility. The network virtualization technology has important significance for the development of the future network. First, it can support more effective verification by creating the experimental platform of the future network. The latest technology and new architecture make a variety of innovative network architectures run parallel to the same shared physical infrastructure and do not interfere with each other; secondly, it can separate the data plane from the control plane, which embodies the essence of the abstraction of physical resources and behavior. It is becoming a basic function of network architecture in the future.
Virtual network mapping problem is that virtual network requests collected from different users are effective, efficient and robust on a given entity network, and can meet the requirements of these virtual requests for physical resources such as node computing power, link bandwidth, etc. the performance and effect of the virtual network mapping algorithm are on the network. The practical and industrialization of virtualization technology has academic guiding significance. It has important research value. This paper will study and discuss the mapping strategy and mapping algorithm of virtual network, take the acceptance rate of the virtual network request, the utilization rate of the entity network resources, the real time of calculation and so on as the evaluation index, and put forward the effectiveness. And high efficient new algorithms, and extended to a more practical network environment, and promote continuous improvement and optimization, and then build a virtual network mapping research platform containing a variety of algorithms and a set of effective, efficient, robust and feasible virtual network mapping solutions for further research. This paper is the main part of this paper. The innovation includes the following aspects:
1) the goal of virtual network mapping is to effectively and effectively map virtual nodes and virtual links of virtual networks to the resources of the entity network. The previous research focused on the design based on heuristic algorithms or attempts to solve the solution through two stages. The node mapping is the first stage and the link mapping is the second order. I propose a new virtual network mapping algorithm based on integer programming. By establishing an enhanced entity network model, the virtual network mapping problem is defined as a plastic planning problem composed of a target function and some constraints. The optimal mapping results can be obtained by solving this mathematical problem. A topology phase can be obtained. The relational factor will be added to the target function. This method solves the virtual network mapping problem in one step. The simulation results clearly show that the algorithm greatly improves the performance acceptance rate, increases the revenue / cost ratio and the revenue, and reduces the cost of the virtual network mapping.
2) the virtual network mapping algorithm based on integer programming is an efficient and efficient mapping algorithm. However, the application scenario of this algorithm does not take into account the possible failure of physical network resources. This is the so-called survivable virtual network embedding problem. The survivability strategy of the past network virtualization is provided by providing pre backup. In this paper, I proposed the dynamic recovery (Dynamic Recovery) method to solve the survivable virtual network mapping problem. This method is based on the virtual network embedding algorithm based on integer programming. First, dynamic recovery. The algorithm does not need to backup physical resources in advance, so that more physical resources can be used when embedded. Secondly, only the dynamic recovery process will be activated only when the physical failure occurs. Finally, it uses different algorithms to restore node failure and link fault. Finding alternative nodes and paths to restore most of the physical failures, and its performance is very close to the test results of a pure virtual network mapping that does not consider physical failures.
3) in order to improve the adaptability of the virtual network mapping algorithm, save computing time and computing space and improve the success rate of virtual network mapping, I propose an improved strategy for the virtual network mapping of a large virtual network request to be divided into multiple subnetworks in advance and then mapping in turn. First, the improvement strategy is presented. Secondly, the virtual network graph which reaches a certain scale is divided into several virtual network subgraphs subVNs. at the end, and each subgraph is embedded in the virtual network and the results are merged respectively. The simulation results show that the method improves the acceptance rate of the virtual network embedded and saves the operation time. Through the segmentation network, the simulation results show that the method can save the operation time. Topology makes it easier to map the larger and more complex virtual network requests more easily, and can even satisfy the virtual network mapping condition that the number of virtual nodes is larger than the number of entity nodes. Therefore, the way of virtual network embedding of large virtual network graphics is an improved direction for virtual network mapping.
【学位授予单位】：北京邮电大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TP393.01

【参考文献】