【作者】 程祥；

【导师】 杨放春；

【作者基本信息】 北京邮电大学 ， 计算机科学与技术， 2013， 博士

【摘要】 互联网在经济发展、社会进步、人民生活水平提高等方面发挥着越来越重要的作用,已经成为现代社会最重要的基础设施之一。网络虚拟化允许在共享的底层物理网络基础设施之上共存多重异构的虚拟网络,使在不影响现有网络服务的前提下部署新的网络架构、协议以及应用成为可能,从而有效地支持网络技术创新。网络虚拟化提供了一条由当前互联网向未来网络演进的可行途径,是未来互联网应具备的关键特性。虚拟网络映射问题是网络虚拟化面临的主要挑战之一,已经成为网络虚拟化研究领域的热点问题,受到了学术界和工业界的普遍关注。虽然目前已经有多种虚拟网络映射算法被提出,但现有研究成果仍然存在以下几个方面的问题：(1)虚拟网络映射成功率低；(2)底层网络的资源利用效用差；(3)虚拟网络服务可靠性差。因此,针对上述问题,本文对虚拟网络映射问题进行了深入研究,并取得如下成果：(1)针对虚拟网络映射成功率低的问题,提出了一种新颖的拓扑感知的节点资源度量方法。该度量方法的特点在于它不仪能够反映网络节点的资源能力,而且还能够反映其周围网络节点的资源能力,从而为虚拟网络映射方案的构造提供更加全面的启发式信息。基于拓扑感知的节点资源度量方法,提出了虚拟节点优先映射以及虚拟节点和虚拟链路同时映射的两种新的虚拟网络映射算法。实验结果表明,基于拓扑感知节点资源度量方法设计的虚拟网络映射算法可以有效地提高虚拟网络映射的成功率(2)针对底层网络资源利用效用低的问题,以降低虚拟网络映射的底层网络资源开销为目标,建立了虚拟网络映射问题的整数规划模型。为了求解该模型,提出了一种新的基于粒子群优化的虚拟网络映射算法。实验结果表明,基于元启发式优化技术的虚拟网络映射算法具有执行速度快,求解质量高等特点,并可以有效提高底层网络资源的利用效用。(3)针对虚拟网络服务可靠性差的问题,首次提出了虚拟网络映射的路由可生存性问题,并建立了该问题的数学模型。为了求解该模型,提出了一种割集感知的虚拟网络映射算法。实验结果表明,割集感知的虚拟网络映射算法可以有效地构造路由可生存的虚拟网络映射方案。路由可生存的虚拟网络映射为被映射的虚拟网络提供了一种新的轻量级的可靠性保障手段,补充了现有的对虚拟网络映射可靠性的研究。更多还原

【Abstract】 The Internet plays an increasingly important role in economic development, social progress and improvement of people’s living standard, which has become one of the most important infrastructures of modern society. Network virtualization allows multiple heterogeneous virtual networks to coexist over a shared substrate network infrastructure, which enables the deployment of new network architectures, protocols, and applications without affecting the existing network service and thus make network innovations easier. Network virtualization provides a viable way to evolve to the future network, and it also should be the key feature of the future Internet.Virtual network (VN) embedding is a major challenge faced by network virtualization. It has become a hot research topic and draws more and more attention from both academic and industrial communities. Although a large body of VN embedding algorithms has been proposed, there is still room for improvement in the following three aspects:(1) VN request acceptance ratio;(2) the utilization of the substrate network resources;(3) the reliability of the embedded VNs. Therefore, through in-depth study of the VN embedding problem from these three aspects, we made the following major contributions:(1) To increase the VN request acceptance ratio, we propose a novel topology-aware node resource ranking measure. Since this measure can reflect not only the resource quality of the node itself but also the resource quality of its neighbors, it provides better heuristic information for the construction of the VN embedding solution. Based on the topology-aware node ranking measure, we propose two new VN embedding algorithms. Both two-stage and one-stage mapping strategies are investigated. The experimental results show that the proposed topology-aware VN embedding algorithms can increase the virtual network acceptance ratio.(2) Aiming at increasing the utilization of the substrate network resource, we first model the VN embedding problem as an integer linear programming and consider the resource cost of VN request as the fitness function. Then, we propose a new VN embedding algorithm based on particle swarm optimization for solving this problem. The experimental results demonstrate that the proposed meta-heuristic based algorithm can generate near-optimal solution without consuming much running time and thus increase the utilization of the substrate network resource.(3) To improve the reliability of the embedded VNs, we introduce the survivable routing problem of VN embedding and establish a mathematical model for this problem. To address this problem, we put forward a heuristic algorithm called cut-aware VN embedding. The experimental results show that the proposed cut-aware VN embedding algorithm can effectively obtain the VN embedding solution with survivable routing. VN embedding with survivable routing provides a new and lightweight way to guarantee the reliability of the embedded VNs, which makes a complementary to the previous studies on the reliability of VN embedding.更多还原