虚拟网映射问题的计算复杂性分析

Computational Complexity Analysis of Virtual Network Mapping Problem

虚拟网映射是实现网络虚拟化的关键环节,其任务是在满足虚拟网构建约束的前提下,把虚拟网的虚拟节点和虚拟链路分别映射到底层物理网的节点和路径上。文中根据虚拟节点映射是否已知、物理网是否支持路径分割、物理节点是否支持重复映射等特征,对虚拟网映射问题进行分类,并针对一般网络拓扑模型和某些特殊网络拓扑模型完成各类虚拟网映射可行问题和优化问题的计算复杂性分析。

Virtual network mapping plays a central role in network virtualization,which maps the virtual nodes and virtual links to the underlying substrate network nodes and paths,respectively,while satisfying the constraint of virtual network construction.This paper categorized the virtual network mapping problem according to whether all the virtual nodes are already mapped,whether the substrate network supports path splitting and whether the substrate nodes support repeatable mapping,and then completed the computational complexity analysis of the feasibility and optimization problem of various virtual network mapping for the general network topology model and some special network topology models.