Take the road back: a different way to study the NFV service chaining problem

The Network Function Virtualization (NFV) service chaining problem, which involves locating Virtual Network Functions (VNFs) in an NFV-enabled network and routing network demands through their required VNFs, is key to the success of NFV. Solving the chaining problem can efficiently reduce required network resources, and thus reducing capital expenditures (CAPEX) and operational expenditures (OPEX). Previous works mainly focus on finding heuristic solutions, rather than investigating the intrinsic features of the problem. In this paper, we investigate the features of the problem from both theoretical and numerical points of view, by shrinking the NFV service chaining problem into a particular version and conducting tests to study what makes the NFV service chaining problem fundamentally difficult to solve. Results reveal that the demand routing part of the problem has a significant impact on solving the mathematical formulated problem, i.e., finding a feasible routing can be time-consuming. We further propose constructive methods that improve upon the mathematical formulation, which make the time of finding the optimal solution be reduced in most cases.