Hierarchical virtual network mapping algorithm for large-scale network virtualisation

Virtual network(VN) mapping deals with the allocation of network resources from the shared physical substrate to individual VNs is one of the key challenges for the application of realising network virtualisation. Whereas a variety of state-of-the-art algorithms have attempted to address this issue from different aspects, the challenge still remains for mapping VNs across multiple network domains which only maintain partial information of the overall substrate network. A novel hierarchical algorithm to address this issue by formulating such VN mapping problem as a hierarchical linear programme model has been presented. Through the use of the primal decomposition and subgradient optimisation technique, in conjunction with the proposed hierarchical algorithm, the substrate network resource can be appropriately allocated to the VN instances with enhanced scalability, because of the parallelism in individual domains. In addition, the algorithm could find the best trade-off between the number of optimisation iterations (computation time) and cost by selecting an appropriate number of iterations. The proposed method has been assessed through a collection of numerical simulation experiments for a range of network scenarios and the result shows that nearly optimal performance as well as improved VN mapping request acceptance ratio and revenue can be achieved.