VHub: Single-stage virtual network mapping through hub location

Network virtualization allows multiple networks with different protocol stacks to share the same physical infrastructure. A key problem for virtual network providers is the need to efficiently allocate their customers’ virtual network requests to the underlying network infrastructure. This problem is known to be computationally intractable and heuristic solutions continue to be developed. Most existing heuristics use a two-stage approach in which virtual nodes are first placed on physical nodes and virtual links are subsequently mapped. In this paper, we present a novel approach to virtual network mapping that simultaneously maps virtual nodes and links onto the network infrastructure. Our VHub technique formulates the problem of mapping a virtual network request as a mixed integer program that is based on the p-hub median problem. Results from extensive simulations with synthetic and real virtual network requests show that our solution outperforms existing heuristics, including subgraph isomorphism backtracking search. Our approach requires fewer physical resources to accommodate virtual networks and is able to balance load more evenly across the network infrastructure.