Abstract:

To reduce the cost of network embedding and promote better utilization of resource, a virtual network embedding algorithm based on bipartite graph optimal matching is proposed. First, a bipartite graph is established with the virtual nodes and physical nodes as graph vertexes. Hence the problem of node embedding is converted to the optimization of the bipartite graph. Second, the node with the highest resource value is matched with the node with the highest demand value, then the Kuhn-Munkres algorithm is used for the bipartite graph optimal matching solution, and the node embedding is completed based on the matching results. The link embedding is finally realized via the k-shortest path algorithm. Experimental results show that the proposed algorithm significantly improves the long-term average revenue to cost ratio and is more reasonable in utilizing resource while maintaining a high rate of acceptance ratio.

Key words: network virtualization, virtual network embedding, bipartite graph, optimal matching, Kuhn-Munkres algorithm