Virtual Network Function Placement Model for Service Chaining to Relax Visit Order and Routing Constraints

Service chaining creates a desired service by the sequential concatenation of Virtual Network Functions (VNF). Relaxing the visit order constraints of requested VNFs and allowing the creation of loops in service chaining paths enable a reduction in the number of VNFs placed on the network. However, the problem of applying both techniques at the same time has never been studied. This paper proposes a VNF placement model that minimizes the costs associated with VNF placement and link utilization while supporting partially-ordered VNFs and service chaining paths with loops. We formulate the VNF placement model as an integer linear programming problem. Simulations quantitatively show that the proposed model reduces the cost compared to the conventional model.