基于结构优化的虚拟网映射算法研究

发布时间：2018-08-07 14:06

【摘要】：在最近二十多年的时间中，互联网，或者称为“网络的网络”，通过支持多种多样的网络技术和应用，在现代社会、文化、知识、商业等与人们的生活息息相关的行业中一直扮演着至关重要的角色。但是，由于它的广泛应用以及multi-provider的性质，互联网的发展只是局限于简单的更新现有设备或协议。网络虚拟化技术就是在这时被提出来的，用以应对未来互联网发展的架构。网络虚拟化能够提供一个开放的、灵活的网络环境，允许服务提供商在底层物理网络上动态地组合成多个异构的网络体系结构，也就是虚拟网络。基于这样的灵活性的网络环境，能够促进多元化的服务和应用程序的部署。网络虚拟化领域的重要挑战是虚拟网络映射问题，旨在静态或者动态地为虚拟节点和链路分配底层物理网络的节点资源和链路资源，还需要同时满足各自的资源约束。有效的利用物理资源需要高效的虚拟网络映射技术，，本文主要从资源分配的角度出发，建立相关模型，并完成了一下工作： (1)前两个章节主要叙述了网络虚拟化的研究背景、研究现状以及基本的技术特征。介绍了网络运营模式在网络虚拟化技术和传统网络技术中的不同，通过图形给出了虚拟化模型的基本结构。列举出了影响映射的几类因素，对虚拟网络映射算法进行了详细的分类。 (2)由于目前网络虚拟化研究主要放在网络映射上，而对于虚拟网络结构的构造却几近没有，本文针对这一不足，提出了利用结构优化的思想进行虚拟网映射的算法，同时进行虚拟网络的构建和映射，在考虑结构优化的同时实现虚拟网络映射，保证了虚拟网络结构在满足用户需求的情况下最优。具体来说利用双层规划的建模方法，首先虚拟网提供商从最大化自己效用的角度出发决定虚拟网扩展方案，然后用户以自私的路由策略选择路由，双方博弈达到平衡，将这个stackelberg博弈表示为一个双层规划模型，上层决策者从系统的角度考虑是虚拟网系统优化模型，下层从用户的角度考虑，利用wardrop UE模型来满足用户的自私行为，双层规划利用用户的路由选择行为将虚拟网络映射的两个部分自然地看成一个整体，通过启发式迭代算法获得了该模型的解。实验数据说明该模型具有较好的虚拟请求接受率、网络收益和资源利用率。此外，对该模型进行的扩展，增加了约束条件，使该算法更具一般性。 (3)利用Stackelberg博弈分析物理网络和虚拟网络的博弈关系，建立二者收益函数的数学模型。并在不完全信息的条件下对模型求解，通过证明虚拟网络效用函数的凹性，说明了Nash均衡点的存在性。与以往只考虑链路映射的方法不同，本文首次将节点考虑其中，同时进行节点和链路的资源分配，利用转换因子将节点映射转变成一种特殊的链路映射，最后通过仿真模拟，验证了该算法的有效性。
[Abstract]:In the last twenty years or so, the Internet, or "network of networks," has supported a wide variety of network technologies and applications in modern society, culture, and knowledge. Businesses and other industries that are closely related to people's lives have always played a vital role. However, due to its wide application and the nature of multi-provider, the development of the Internet is limited to simply updating existing devices or protocols. Network virtualization technology is proposed at this time to deal with the future development of the Internet architecture. Network virtualization can provide an open and flexible network environment, allowing service providers to dynamically combine into multiple heterogeneous network architectures on the underlying physical network, that is, virtual network. Based on this flexible network environment, it can facilitate the deployment of diversified services and applications. The important challenge in the field of network virtualization is the problem of virtual network mapping, which aims at allocating node and link resources of the underlying physical network to virtual nodes and links statically or dynamically, as well as satisfying their resource constraints at the same time. Effective use of physical resources requires efficient virtual network mapping technology. This paper mainly from the point of view of resource allocation, establish a related model, The main contents are as follows: (1) the first two chapters mainly describe the research background, research status and basic technical characteristics of network virtualization. This paper introduces the difference of network operation mode between network virtualization technology and traditional network technology, and gives the basic structure of virtualization model through graphics. This paper enumerates several kinds of factors that affect mapping, and classifies the algorithm of virtual network mapping in detail. (2) because the research of network virtualization is mainly focused on network mapping, but the construction of virtual network structure is almost non-existent. In this paper, a virtual network mapping algorithm based on the idea of structural optimization is proposed to construct and map the virtual network, which can realize the virtual network mapping while considering the structure optimization. It ensures that the virtual network structure is optimal in the case of satisfying the needs of users. Specifically, by using the modeling method of bilevel programming, firstly, the virtual network provider decides the virtual network extension scheme from the point of view of maximizing its own utility, and then the user chooses the route with selfish routing strategy, and the game is balanced. The stackelberg game is expressed as a bilevel programming model. The upper level decision makers consider the virtual network system optimization model from the system point of view, the lower layer considers from the user's point of view, and the wardrop UE model is used to satisfy the selfish behavior of the user. The two parts of the virtual network mapping are naturally regarded as a whole by using the routing behavior of the user in the bilevel programming and the solution of the model is obtained by heuristic iterative algorithm. Experimental data show that the model has good virtual request acceptance rate, network revenue and resource utilization. In addition, the expansion of the model increases the constraint conditions, which makes the algorithm more general. (3) the Stackelberg game is used to analyze the game relationship between the physical network and the virtual network, and the mathematical model of the income function of the two networks is established. Under the condition of incomplete information, the existence of Nash equilibrium point is proved by proving the concave of utility function of virtual network. Different from the previous method of only considering link mapping, this paper first considers the node and resource allocation of the node and the link, and transforms the node mapping into a special link mapping by using the conversion factor. Finally, the simulation is done. The validity of the algorithm is verified.
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.01

【参考文献】