Research On Algorithms For Virtual Network Embedding Problems

Network virtualization technologies realize the abstraction and isolation of the substrate network resources, and it allows multiple virtual networks independently coexist on the same underlying physical network and provides users with diversified network services. Virtual network embedding is one of the key technologies of network virtualization, and it efficiently embeds virtual network into the substrate network by dynamically assigning the substrate network resources to virtual networks.In order to improve utilization of the substrate network resources, virtual network mapping algorithm should optimize the substrate network resources allocation and efficiently embed virtual network requests into the substrate network. Due to the diverse needs of virtual network node and link resources, the residual resources of node and link at the substrate network easily become unbalanced, which is called resource fragmentation. As the fragmented resources is small and scattered, and difficult to be used, it directly decreases available resources in the substrate network. In order to solve virtual network embedding problem with resource fragmentation consideration, we propose a virtual network embedding algorithm with resource fragmentation consideration, a virtual network embedding algorithm based on topological attributes of the substrate network, and a virtual network reconfiguration algorithm based on fragmented resources. The main contribution of this paper is as follows:1) This paper firstly defines the connectivity of nodes and links that extends the conception of the connectivity in graph theory, and defines a new parameters, called RFD(Resource Fragmentation Degree), to describe the degree of resource fragmentation of the underlying physical nodes and links; we also define fragmentation cost of virtual network embedding into the substrate network based on RFD, which is also called fragmented resources.2) We then formulate virtual network embedding as a mixed integer programming problem with resource fragmentation of the underlying network consideration. The optimization objective includes minimizing fragmented resources indicated by RFD in the substrate network and real occupied resources by virtual network. In order to solve the optimization problem, an online algorithm called VNE-RFD is proposed, and its main idea is to minimize the above mentioned two parts.3) In order to better describe the degree of fragmentation of the substrate network resources, this paper formulates the connectivity relations among each substrate network element as a Markov chain that extends the above mentioned RFD. and get a GRFD(Global Resource Fragmentation Degree) derived from the steady-state connectivity. GRFD can better describe the degree of fragmentation of the substrate network resources; at the same time, it also reflects the substrate network topological features.4) Considering the dynamic characteristic of Virtual network embedding process, this paper also designs a virtual network reconfiguration algorithm based on GRFD; it can further reduce fragmented resources and improve utilization of the substrate network resources.