Virtual network embedding with border matching

A major challenge in virtual network embedding is to find an efficient mapping of each virtual network (VN) to the nodes and links in the substrate network (SN) so that the residual SN can host as many VN requests as possible. This network optimization problem has been shown to be NP hard. In this paper we propose a “border matching” mechanism in VN embedding, which is shown to outperform a number of existing VN embedding algorithms. In particular, we devise an iterative algorithm called “VNE-B”. Typical VN embedding algorithms may cause fragmentations of the substrate network, i.e. the substrate resources are fragmented into small isolated pieces, making it unable to meet larger future VN requests. VNE-B starts the mapping from the “border” nodes of both VNs and the SN for reducing fragmentation of SN resources. Our experimental evaluations show that VN embedding algorithms with VNE-B result in more efficient mappings and thus fewer rejections for VN requests. We also visualize the residual SN to demonstrate the effectiveness of VNE-B.