Towards efficient virtual network embedding across multiple network domains

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.