A max-flow/min-cut theory based multi-domain virtual network splitting mechanism

In network virtualization environment, if a virtual network (VN) needs to be deployed across multiple infrastructure domains, a splitting scheme of the VN should be found. With the goal of minimizing embedding cost, the existing methods solve VN splitting by linear programing. However, since the VN splitting problem is NP-Hard, these methods will take a lot of computing time when the problem scale gets bigger. In this paper, a max-flow/min-cut theory based VN splitting mechanism is proposed. The proposed method first creates a binary tree of the InPs by system clustering method, based on which the multidomain VN splitting problem is decomposed into several two-domain VN splitting problems. Then the method transforms each two-domain splitting problem into a max-flow/min-cut problem, and solves it by the shortest augmenting path algorithm efficiently. Simulations show that the proposed mechanism can improve the efficiency of VN splitting steadily and save the embedding cost.

I. Introduction

Network virtualization is one of the most promising future network forms. It supports the deployment of multiple virtual networks (VNs) that carry independent services and applications on the same substrate network (SN). By this way, the utilization of the substrate resources can be improved, and network services can be created flexibly [1]. Virtual network embedding (VNE) is a key to network virtualization, which aims to find the appropriate substrate nodes and paths for the virtual nodes and links of a VN. However, due to some objective constraints (e.g. resource location, type), one single InP may not be able to provide sufficient resources for a VN. According to the number of InPs that participate in VNE, there are two kinds of VNE: single-domain VNE (only one InP) and multi-domain VNE (more than one InPs). There are many effective methods for the single-domain VNE [2]–[3]. However, there are few good methods for multi-domain VNE, so many researchers pay attention to the multi-domain VNE [4]–[7].