Column Generation Based Service Function Chaining Embedding in Multi-Domain Networks
Rongping Lin, Yu Song, Shan Luo, Xiaoning Zhang, Jingyu Wang, Moshe Zukerman
Abstract
Network function virtualization (NFV) achieves cost-effective network service provisioning through exploitation of virtualization and automation by decoupling network functions (software) from dedicated hardware. The software of the various devices can then be hosted by low-cost general computation devices rather than by more expensive dedicated devices. To obtain a specific network service, the traffic flow is steered to go through a specific order of network functions that are hosted by cloud computing, and this network function sequence is known as a service function chaining (SFC). To allocate computation resources for network functions and bandwidth resources between network functions in a physical network is the SFC embedding problem. In this article, we consider the SFC embedding problem in multi-domain networks, where no domain information, like domain topology and network resource, is disclosed among domains. We propose a new optimization algorithm based on column generation method to solve this problem, which is distributedly computed in each domain. To further improve the scalability, we also provide two heuristic algorithms. We selected two networks one large (158 nodes) and one small (18 nodes) to numerically validate the proposed algorithms and demonstrate that the acceptance ratio obtained by the heuristic algorithms is close (within 5.6 percent) to that of the optimal algorithm.