Virtual Network Embedding Based On Simple Method And Genetic Algorithm

Due to the increasing personalized network service requirements, the ossification issue of traditional Internet become more and more significant. Network virtualization technology, the effective technology of creating the Clouding Computing Eco-system, is considered as the most promising technology for the future Internet. One of the most crucial problems of network virtualization is Virtual Network Embedding, That is to say, embedding multiple virtual networks onto one physical network through resource allocation. The existing researches on embedding problem mainly focus on how to select nodes and links to meet the business request, decrease the cost and increase revenue. However, the questions of how to effectively utilize physical resources, improve revenue of the underlying infrastructure provider and increase resource utilization which are considered the essential problem of embedding have not achieved an unified agreement.Based on the traditional virtual network embedding algorithm, firstly we analysis and summarize the existing virtual network embedding models and algorithms, then find out flaws of the existing virtual network embedding algorithms. In this thesis, we focus on the improvement of the original embedding algorithms and analyze the problems exist in the original embedding algorithms, such as premature convergence. Then we introduce Simplex Method (SM), which has high local search ability, into Genetic Algorithm (GA) and use Mixed Integer Programming (MILP) model for optimal resource allocation problem. Based on the above model, we develop a hybrid algorithm, which combines Genetic Algorithm (GA) and Simplex Method (SM) for virtual network (NVE-M-GA), and verify the effectiveness of this algorithm by simulation experiments.By analysis of flaws in Simplex Method(SM) algorithm, such as the sensitivity to initial value, the linear search, etc., we improve the SM algorithm by classifying populations into subgroups and then propose VNE-SM_HGA algorithm. Specifically, we make full use of the direction of simplex, improve search efficiency as much as possible, reduce simplex search calculation, and then improve the convergence speed of algorithm.Simulation experiment results show that the underlying network provider’s revenue increases through using VNE-M-GA and VNE-SM-HGA algorithm. The improved genetic algorithm with the simplex method speeds up the convergence effectively.