Virtual network construction with K-shortest path algorithm and optimization problems for robust physical networks

Summary In network virtualization, it has been considered that virtual networks are constructed over a physical network where conventional data transmission services have been utilized. Here, virtual networks have to be constructed while keeping qualities of the conventional services. In this paper, we propose a new virtual network construction in order to construct many virtual networks while keeping the robustness of a physical network by using network resources effectively. The proposed method consists of three processes: K-shortest path algorithm and Prim's minimum spanning tree algorithm, path splitting, and path migration. In the proposed method, at first, multiple topologies are designed by using the K-shortest path algorithm and the Prim's MST algorithm according to the user's request. After the topology design is completed, an admission control with network robustness of the physical network is performed. Then, if one of the designed topologies can satisfy the construction conditions, a virtual network is constructed and provided with the user. Otherwise, the path splitting and path migration are performed. Here, the path splitting is utilized to design another topology of a virtual network and path migration is used to change the topologies of the virtual networks that have already been constructed. These processes are formulated as optimization problems and those are processed by solving the optimization problems. In numerical examples, we show that our proposed method can construct a higher number of virtual networks while keeping the robustness of a physical network by comparing with the conventional method where only the Kou–Markowsky–Berman algorithm is used. Copyright © 2015 John Wiley & Sons, Ltd.