【作者】 卿苏德；

【导师】 廖建新；

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

【摘要】 作为一个可以解决现有互联网僵化问题的利器,网络虚拟化技术在学术界和工业界吸引了越来越多的关注。为了将网络虚拟化技术融入下一代互联网架构中,需要克服一个严峻的挑战,即将多个异构的虚拟网络同时映射至底层共用的基础设施中。这个问题被称为虚拟网络映射问题。由于存在多个维度的资源限制,虚拟网络映射问题属于NP困难问题,相关的解决方案大多依赖于启发式算法。本文专注于虚拟网络映射算法的改进,主要工作包括以下四个方面：(一)对虚拟网络映射算法的最新进展做了详细的综述,并将现有的映射算法进行分类。现有的映射算法可以分为基于单个基础设施提供商的算法和基于多个基础设施提供商的算法。基于单个基础设施提供商的算法可以进一步按问题空间是否受限和映射过程是否完整进行细分；基于多个基础设施提供商的算法可以根据水平维度和垂直维度进行细分;在文章的结论部分,对该领域的研究方向提出了展望。(二)提出了基于截止时间优先的混合式虚拟网络映射算法。不限制问题空间的映射算法可以细分为一阶段的映射算法和两阶段的映射算法,这两类算法各有优劣。通过k核分解技术,将虚拟网络划分为核心网络和边缘网络,并在这两类子网中分别应用两阶段的映射算法和一阶段的映射算法。此外,当一个虚拟网络请求的生命周期结束时,底层物理网络将释放其占用的资源。结合这个特点,使用基于截止时间优先的队列调度机制,进一步改进了映射算法的性能。(三)提出了基于贝叶斯网络推理的拓扑感知型映射算法。基于马尔科夫随机游走模型,拓扑感知型的虚拟网络映射算法对节点的资源能力进行排名,通过改变节点之间的匹配关系,改进映射算法的性能。然而,节点排名采用的资源评价标准并不合理。此外,由于忽视了已选节点对待选节点的影响,节点的贪婪匹配映射规则会导致不必要的带宽浪费。因此,本文从统计学的角度重新思考虚拟网络的映射过程,通过收集虚拟网络映射的历史信息,生成两个关联矩阵,分别代表底层网络中节点的重要度和节点之间的关联度。基于这些关联矩阵,在节点映射过程中,始终采用贝叶斯网络推理技术选择与已选节点关联最大的节点进行映射。大量的仿真实验结果表明,新提出的虚拟网络映射算法在长期运行过程中具有更好的映射性能。(四)提出了基于布隆过滤器的分布式映射算法。基于单个基础设施提供商的映射算法大多属于集中式的映射算法,容易产生系统单点故障问题。借助机器学习和推理技术,在没有底层资源更新消息的条件下对资源能力进行评价,并依赖节点的自主映射实现整个虚拟网络的映射。此外,采用布隆过滤器实现底层信息的同步,有效规避了采用洪泛而导致的大量通信开销。最后,将集中式映射算法和分布式映射算法的性能做了对比。仿真实验结果表明,相对于集中式映射算法,分布式映射算法具有可接受、甚至更好的映射性能。更多还原

【Abstract】 Network virtualization is promoted as a powerful vehicle to solve the ossification of the Internet architecture so that it has attracted increasing attention in both academia and industry. To integrate network virtualization into the future Internet architecture, a big challenge, how to map multiple heterogenous virtual networks onto the shared substrate network, known as virtual network embedding problem, should be solved. Due to multi-dimensional resource constraint, virtual network embedding problem is NP-hard so that its solutions almost rely on heuristic-based algorithms. Our work focuses on improving the performance of virtual network embedding algorithm. Our paper presents the following four major contributions:(1)A survey of the latest research progress of virtual network embedding algorithm is conducted in detail to divide current virtual network embedding algorithms into two categories, i.e., algorithms based on one infrastructure provider and algorithms based on multiple infrastructure providers. Within an infrastructure provider, virtual network embedding algorithms can be subdivided further in terms of whether the problem space is constrained and the number of mapping stages. Within multiple infrastructure providers, virtual network embedding algorithms can be subdivided according to the relationship among multiple infrastructure providers in the horizontal and vertical dimension. Moreover, this survey sheds light on the potential future research directions in the conclusion. (2) We propose a hybrid virtual network embedding algorithm with time-oriented scheduling policy. Without reducing any problem space, current virtual network embedding algorithms can be simply classified as one-stage mapping algorithm and two-stage mapping algorithm. However, every coin has two sides. To exploit the respective advantage of the two classes of algorithm, the virtual network is decomposed into core network and edge netwok, while two-stage algorithm and one-stage algorithm are applied in the core network and edge network, respectively. Moreover, a time-oriented scheduling policy is introduced to improve the mapping performance by leveraging the fact that the occupied substrate resource will be released after virtual network departs.(3) We propose a topology-aware virtual network embedding algorithm based on Bayesian network analysis. Topology-aware virtual network embedding algorithms efficiently improve the performance by leveraging a node ranking method based on Markov random walk model. However, as the basis of node ranking, the resource evaluation of node may be incorrect. Moreover, a greedy matching strategy is always applied in the node mapping stage, which may lead to unnecessary bandwidth consumption by ignoring the relationships between the mapped substrate nodes and the mapping one. Therefore, we rethink the topology-aware virtual network embedding from a statistical perspective. A statistical method is proposed to generate two dependency matrices, respectively representing the importance of every node and the relationships between every two nodes in the substrate network. Based on these dependency matrices, Bayesian network analysis is adapted to iteratively select the substrate node which has the closest relationship with the mapped nodes to achieve node mapping process. Extensive simulations were conducted and the results show that the long-term average performance of our proposed algorithm is better.(4) We propose a distributed virtual network embedding algorithm based on Bloom filter. Current solutions are almost provided in a centralized way within an infrastructure provider, which may have hot spot problem. In this paper, by leveraging the learning and inference technology, a novel resource evaluation method is proposed without the updated message in the substrate network and virtual network is mapped in a peer-to-peer way according to its own resource evaluating table. Moreover, instead of flooding which generates massive communication overhead, Bloom filter is introduced to synchronize the mapping information. Finally, explicit comparisons between the centralized algorithms and our distributed algorithm are conducted for the first time and the results show that our proposed algorithm has acceptable, even better performance in terms of long-term average revenue and long-term average acceptance ratio.更多还原