Virtual network function placement and routing for multicast service chaining using merged paths Abstract   This paper proposes a virtual network function placement and routing model for multicast service chaining based on merging multiple service paths (MSCM). The multicast service chaining (MSC) is used for providing a networkvirtualization based multicast service. The MSC sets up a multicast path, which connects a source node and multiple destination nodes. Virtual network functions (VNFs) are placed on the path so that users on the destination nodes receive their desired services. The conventional MSC model configures multicast paths for services, each of which has the same source data and the same set of VNFs in a predefined order. In the MSCM model, if paths of different services carry the same data on the same link, these paths are allowed to be merged into one path at that link, which improves the utilization of network resources. The MSCM model determines the placement of VNFs and the route of paths so that the total cost associated with VNF placement and link usage is minimized. The MSCM model is formulated as an integer linear programming (ILP) Problem. We prove that the decision version of VNF placement and routing problem based on the MSCM model is NPcomplete. A heuristic algorithm is introduced for the case that the ILP problem is intractable. Numerical results show that the MSCM model reduces the total cost required to accommodate service chaining requests compared to the conventional MSC model. We discuss directions for extending the MSCM model to an optical domain.

Costefficient virtual network function chaining over NFVbased telecommunications networks Network Function Visualization (NFV) enables the softwarization of network functions on standardized commodity hardware, which is promising to help the network carriers to achieve a lower investment cost, a shorter time to deployment, as well as a more flexible and dynamic way of network configuration and management. One of the key challenges is how to efficiently place and chain the softwarebased virtual network functions in the physical substrate to provision the requested network service while minimizing the physical network cost. In this paper, we mathematically formulate the virtual network function chaining problem using Integer Linear Programming (ILP), in order to facilitate an optimal solution. In addition, we propose a set of heuristic algorithms to efficiently solve this problem. The proposed Close To Destination (CTD) algorithm can achieve a nearoptimal physical network cost that is close to the optimal result obtained from the ILP solution, but with a very low computational complexity. Comprehensive simulations are conducted to evaluate the proposed approaches, and the results demonstrate the effectiveness of the proposed CTD algorithm.