Survivable network virtualization for single facility node failure: A network flow perspective

摘要

Network virtualization facilitates the technology advancement via decoupling the traditional Internet Service Providers (ISPs) into the infrastructure provider (InP) and the service provider (SP). Revolutionary technologies hence can be easily employed by the SP and transparently mapped to the physical network managed by the InP after resolving the network embedding problem. In this work, we target on importing resilience to the virtualization context by solving the survivable network embedding (SNE) problem. We view the SNE problem from a multi-commodity network flow perspective, and present an Integer Linear Programming (ILP) model for both splittable and non-splittable flow to achieve joint optimal allocation for the working and backup resources. For large-scale problems, we propose two efficient heuristic algorithms for the case with splittable and non-splittable flow, respectively. Our performance evaluation shows that the splittable mapping outperforms the non-splittable mapping in terms of the consumed resources, while the latter bears the advantage of consistent QoS guarantee.