Towards efficient virtual network embedding across multiple network domains

Abstract

Network virtualization provides a promising way to run multiple virtual networks (VNs) simultaneously on a shared infrastructure. It is critical to efficiently map VNs onto substrate resources, which is known as the VN embedding problem. Most existing studies restrict this problem in a single substrate domain, whereas the VN embedding process across multiple domains (i.e., inter-domain embedding) is more practical, because a single domain rarely controls an entire end-to-end path. Since infrastructure providers (InPs) are usually reluctant to expose their substrate information, the inter-domain embedding is more sophisticated than the intra-domain case. In this paper, we develop an efficient solution to facilitate the inter-domain embedding problem. We start with extending the current business roles by employing a broker-like role, virtual network provider (VNP), to make centralized embedding decisions. Accordingly, a reasonable information sharing scheme is proposed to provide VNP with partial substrate information meanwhile keeping InPs' confidential information. Then we formulate the embedding problem as an integer programming problem. By relaxing integer constraints, we devise an inter-domain embedding algorithm to handle online VN requests in polynomial time. Simulation results show that our solution outperforms other counterparts and achieves 80%-90% of the benchmarks in an ideal scenario where VNP has complete knowledge of all substrate information.