Efficient Virtual Network Embedding for Variable Size Virtual Machines in Fat-Tree Data Centers

Network virtualization is the enabling technology for sharing resources on cloud. The efficiency of virtual network embedding determines the expense and revenue ratio of a data center. In this paper, we consider the virtual network embedding problem in fat-tree data centers. We design various schemes to embed Nonblocking Multicast Virtual Networks (NMVNs) which are dedicated to deliver premium experience to cloud users. In each NMVN, there is a free combination of virtual machines selected from variable sizes. The bottleneck of communications between these virtual machines is removed so that they can always send data at full bandwidth of their network interface, even if data is simultaneously sent to multiple destinations. In addition, the high performance of NMVNs is guaranteed at the wellcontrolled low network hardware cost. We design two embedding schemes for NMVNs, named Static NMVN Embedding (SNE) and Dynamic NMVN Embedding (DNE). Both schemes support the nonblocking properties for multicast. Besides, each of the two schemes has its unique features. The SNE scheme provides an interference-free solution, in the sense that a virtual network is not aware of the existence of other virtual networks during its lifetime. The DNE scheme has lower hardware cost than SNE and provides higher flexibility to cloud users by possible reconfigurations when necessary. Additionally, we show through theoretical analysis and simulations to validate that the overhead of DNE is minimal thus acceptable to most cloud applications.