Scalable inter-domain network virtualization

To realize inter-domain network virtualization for hybrid cloud, the following challenges must be resolved. (1) Scalability. The network virtualization system should allow tenant virtual networks to use on-demand addressing schema and span multiple domains. This requirement, combined with the expansion of the network scale, can lead to a rapid increase in flow rule consumption, posing a significant challenge for network scalability. (2) Inter-domain network flow scheduling. To allocate bandwidth for inter-domain network flows with low cost and guaranteed bandwidth is complex (NP-hard). Existing researches fail to address this problem in a flexible yet efficient manner. This paper proposes a network virtualization solution that jointly considers the two challenges. Towards the scalability challenge, we use MAC translation to encode location hierarchy and tenant information into MAC addresses, thereby enabling L2 forwarding rule aggregation on each switch. Besides, we offload the L3 virtual network rules onto the first hop software switches and tackle L3 routing through VMAC-based forwarding. We formally prove that our approach can bound the worst-case rule consumption by combining these two techniques. Towards the second challenge, we formulate the inter-domain network flow scheduling (INFOS) problem into an integer linear programming (ILP) problem and prove its NP -hardness. We also propose a heuristic algorithm that can guarantee bandwidth lower-bound while avoiding causing significant profit loss or introducing too many network updates. Evaluation shows that our approach can reduce the average flow rule consumption significantly, compared with state-of-the-art approaches. Besides, towards the same bandwidth guarantee target, we can avoid up to 94.4% of the network update operations.