| Network virtualization has been identified as a promising technology to overcome the current ossification of the Internet by running multiple network services and experiments simultaneously on the same substrate network. It could even become the basis of the future Internet. Virtual Network Embedding (VNE) solves the problem of mapping virtual resources to physical resources, which is led to by applying virtualization of network resources. Its main object is to assign the virtual network requests reasonably to the substrate network while satisfying node and link constraints. Multiple service providers (SPs) will be able to provide the customized end-to-end services to the end users without vast investment on physical infrastructure in the network virtualization environment (NVE). They will lease shared resources from different infrastructure providers (InPs) to build the heterogeneous virtual networks (VNs).The virtual network (VN) embedding/mapping problem is recognized as an essential question of network virtualization. The VN embedding problem is a major challenge in this field. Its target is to efficiently map the virtual nodes and virtual links onto the substrate network resources. Due to multiple objectives and multiple constraints, finding the optimal solution turns out to be a very difficult problem. It should consider the random physical failures during the virtual network embedding. It should improve its adaptability while saving computation time and space by considering the topology characteristics of the virtual requests. We build a research platform of virtual network mapping which contains many kinds of algorithms, achieve an effective, efficient, robust and feasible virtual network mapping solution and provide reference for the future research. The main innovations proposed in this paper are as follows:1) The target of Virtual network embedding is to map the virtual network requests to the substrate network effectively, efficiently and robustly. Previous research focused on designing heuristic-based algorithms or attempting two-stage solutions by solving the node mapping in the first stage and then the link mapping in the second stage. In this study, we propose a new virtual network embedding algorithm based on integer programming. We build a model of an augmented substrate graph, and formulate the virtual network embedding problem as an integer program with an objective function and some constraints. A factor of topology-awareness is added to the objective function. It solves the virtual network embedding problem in one stage. Simulation results state clearly that our algorithm greatly enhances the performance of the acceptance ratio, increases the revenue/cost (R/C) ratio and the revenue while decreasing the cost of the virtual network embedding problem.2) Network virtualization is a promising way to overcome the current ossification of the Internet. To find an effective, efficient and robust embedding algorithm for recovering virtual network is an essential challenge in this field. The virtual network mapping algorithm based on Integer Programming which was recently proposed by us; and it is an effective and efficient embedding algorithm. But it had not considered the situation of the faults of physical network resources, which is called survivable virtual network embedding problem. Previous strategies for enabling survivability in network virtualization focused on providing protection for the physical network or enhancing the virtual networks by providing backup physical resources in advance, and treated all types of physical failures as link failures. We propose the dynamic recovery method to solve the survivable virtual network embedding problem based on the Integer Programming VNE algorithm. Firstly, the dynamic recovery method doesn’t need to backup physical resources and it makes more substrate resources can be used in the embedding. Secondly, the dynamic recovery process will be activated only when physical failures occur. Finally, it uses different algorithms to recovery node and link failures. Simulation results show that our method has succeeded to recover almost all of physical failures by finding the substitute nodes and paths; further, its performance is very close to that of pure VNE method without considering physical failures.3) In order to improve the adaptability of the virtual network mapping algorithm and the success rate of the virtual network mapping while saving computation time and space, we porpose an improved virtual network mapping algorithm which will subdivide the virtual network requests with a big number of nodes into serveral subVNs and then to be mapped in trun. First of all, the paper analyzes the complexity of the virtual network mapping algorithm based on integer programming. Second, subdivide the virtual networks with a certain scale into several virtual subVNs. Finally, separately each subVN is embedded in the virtual network operation and merging the results. Simulation results show that the method has been compared with the original virtual network embedding algorithms based on interger programming, improves the acceptance ratio of the virtual network embedding, saves the computation time. Therefore, partitioning the big virtual network graphs and then virtual network mapping can refer to the improvement direction for virtual network embedding. |
PDF Full Text Request