基于蚁群算法的虚拟网络映射研究

发布时间：2019-05-22 08:07

【摘要】：随着计算机网络在近几年的迅猛发展,存在于现有互联网架构中的问题日益显著,例如可扩展性、可控可管性、服务质量保证、绿色节能等方面。为了彻底解决这些问题,学术界提出了对未来网络“从头再来(clean-slate)"的设计思想,希望能够摆脱现有互联网约束,重新设计能够适应未来网络的体系架构。网络虚拟化是构建新一代互联网体系架构的核心技术,它允许多个网络应用能同时共享在一个底层物理网络上,并能够为用户提供多样化的定制服务。在网络虚拟化中,网络实体分为物理网络和虚拟网络。多个不同的虚拟网络根据服务需求,需要不同的网络资源包括充足的网络节点数和足够的网络链路带宽。虚拟网络上的节点和链路能够在物理网络上创建、删除。网络虚拟化已经被应用于数据中心解决扩展性、复杂性、资源利用率等问题。另外,在云计算环境中,为了实现计算资源的共享、分离与聚合以及资源的易管理性,网络虚拟化成为解决这些问题的关键技术。虚拟网络映射问题(VNE)是网络虚拟化在资源分配的核心问题。将不同虚拟网络的资源包括节点资源和链路资源映射到物理网络上。其中,节点资源一般有CPU、内存、地理位置等；链路资源有延迟、带宽等。虚拟网络映射的目标是在满足虚拟网络资源约束的前提下,将虚拟网络嵌入到合适的底层物理网络上。在保证虚拟网络资源请求的情况下,尽可能的降低虚拟网络请求的拒绝率,同时提高底层物理网络的资源收益。虚拟网络映射不仅要解决准入控制、请求排队、资源约束问题,还要解决拓扑多样性等多方面的问题。由于应用场景、优化目标、映射方式和约束条件的不同,虚拟网络映射又分为不同类型的优化问题。本文基于蚁群算法分别对离线虚拟网络映射ACO-VNE和在线虚拟网络映射提出了相应的映射算法VNE-CACO.对于ACO-VNE算法,属于两阶段映射算法,首先进行节点映射,然后进行链路映射。通过判断映射结果的好坏,蚂蚁将信息素分布于节点上。蚂蚁之间通过信息素进行学习,学习前代蚂蚁的映射经验,另外将节点的资源情况作为启发式因子。蚂蚁通过轮盘赌选择节点映射方案,然后再进行链路的映射。直到蚁群算法收敛或者达到设定的运行次数上限即得到映射解。针对在线虚拟网络映射,我们提出了VNE-CACO。VNE-CACO是一种一阶段的协同映射算法。一方面,该算法将物理网络拓扑上的关键路径作为稀有资源尽量保留,来应对后续的虚拟网络请求。另一方面,该算法通过蚂蚁之间对映射解空间的探索所遗留的信息素,然后结合启发式因子信息,不断的向最优解靠拢。算法直到收敛或者达到运行的最大代数停止,获得最终解。本文对两种算法均做了详细的仿真实验,实验结果表明蚁群算法在解决虚拟网络映射问题中具有优秀的表现。
[Abstract]:With the rapid development of computer network in recent years, the problems existing in the existing Internet architecture are becoming more and more obvious, such as scalability, controllability, quality of service assurance, green energy saving and so on. In order to solve these problems thoroughly, the academic circles put forward the design idea of "starting from scratch (clean-slate)" for the future network, hoping to get rid of the existing Internet constraints and redesign the architecture that can adapt to the future network. Network virtualization is the core technology to build a new generation of Internet architecture, which allows multiple network applications to share on one underlying physical network at the same time, and can provide users with a variety of custom services. In network virtualization, network entities are divided into physical network and virtual network. According to the service requirements, many different virtual networks need different network resources, including sufficient number of network nodes and sufficient network link bandwidth. Nodes and links on virtual networks can be created and deleted on physical networks. Network virtualization has been used in data centers to solve scalability, complexity, resource utilization and other issues. In addition, in order to realize the sharing, separation and aggregation of computing resources and the ease of management of resources, network virtualization has become the key technology to solve these problems in cloud computing environment. Virtual network mapping problem (VNE) is the core problem of network virtualization in resource allocation. The resources of different virtual networks, including node resources and link resources, are mapped to the physical network. Among them, node resources generally have CPU, memory, geographical location and so on; link resources have delay, bandwidth and so on. The goal of virtual network mapping is to embed the virtual network into the appropriate underlying physical network under the premise of satisfying the constraints of virtual network resources. Under the condition of ensuring the virtual network resource request, the rejection rate of the virtual network request is reduced as much as possible, and the resource income of the underlying physical network is improved at the same time. Virtual network mapping not only solves the problems of admission control, request queuing, resource constraints, but also solves the topology diversity and so on. Due to the different application scenarios, optimization objectives, mapping methods and constraints, virtual network mapping is divided into different types of optimization problems. In this paper, the corresponding mapping algorithms VNE-CACO. for offline virtual network mapping ACO-VNE and online virtual network mapping are proposed based on ant colony algorithm. For ACO-VNE algorithm, it belongs to two-stage mapping algorithm, first node mapping, and then link mapping. By judging the quality of the mapping results, ants distribute pheromones on the nodes. Ants learn from each other through pheromones to learn the mapping experience of the previous generation of ants. In addition, the resource situation of nodes is used as a heuristic factor. Ants select node mapping scheme through roulette, and then map the link. Until the ant colony algorithm converges or reaches the set upper limit of running times, the mapping solution is obtained. For online virtual network mapping, we propose that VNE-CACO.VNE-CACO is a one-stage collaborative mapping algorithm. On the one hand, the algorithm preserves the critical path in the physical network topology as a rare resource as much as possible to cope with the subsequent virtual network requests. On the other hand, the algorithm is based on the pheromones left behind by the exploration of mapping solution space between ants, and then combines the heuristic factor information to get close to the optimal solution. Until the algorithm converges or reaches the maximum algebra to stop, the final solution is obtained. In this paper, the two algorithms are simulated in detail, and the experimental results show that ant colony algorithm has excellent performance in solving the problem of virtual network mapping.
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.01;TP18

【参考文献】