In Network Function Virtualization (NFV), a series of Virtual Network Functions (VNFs) organized in a specific order (called Service Function Chain, SFC) could offer an end-to-end network service for a network flow. Recently, with the new results of the exploration of VNF parallelism, hybrid SFC (SFC contains parallel VNFs) is proposed to reduce the SFC execution delay. However, it remains challenging and open to optimally embed multiple hybrid SFCs into the network. In this paper, we target at the optimal embedding problem of multiple hybrid SFCs with the purpose of minimizing the cost in an online scenario. Specifically, we propose SFT-Box, an online approach that can respond to hybrid SFC embedding requests in real-time. SFT-Box is designed to i) transform SFCs from the traditional sequential form to a standardized hierarchical Service Function Tree (SFT) form, ii) calculate and store the low-cost sub-solutions of embedding common SFTs, and iii) provide prompt solution response based on stored sub-solutions. To the best of our knowledge, this is the first work to address the online optimal embedding problem of multiple hybrid SFCs. With extensive evaluations, we demonstrate that, compared with the benchmark methods, SFT-Box can achieve up to 30% cost-saving and at least$22\times $latency reduction in enabling real-time response.

As the development of new generation mobile communication technology, the mobile core network also needs to be upgraded by new network technologies, e.g., software defined networking (SDN) and network function virtualization (NFV). With NFV, virtual network functions (VNFs) can be deployed on commodity devices to support various network function requirements and attain system's flexibility and elasticity in network edge. Meanwhile, a set of selected VNFs are usually chained as a service function chain (SFC) to serve a given flow in a specified order. Since the devices have heterogeneous execution environments and the VNFs have various requirements, one fundamental challenge is how to embed SFC for each flow on the shared NFV infrastructure (NFVI) with the goal of minimizing the flow completion time. Furthermore, multiple flows always compete for resources of those devices hosting SFCs. In this general setting, there is an urgent need to study efficient scheduling mechanism to minimize the total completion time of all flows. In this paper, by jointly considering VNF placement and flow scheduling, we first formulate this problem as an integer programming problem, and further prove that it is NP-hard in general case. We then design a PDG method to find the optimal solution in single flow case and an LRD method to achieve a high-quality feasible solution in multiple flows case. The extensive experiment results indicate that our LRD method can reduce the total completion time of all flows by 22.04, 60.99 and 39.95, percent against three compared methods, respectively.

Usually, a data flow needs to traverse a series of network functions, which is called a service function chain (SFC), before reaching its destination. The emergence of network function virtualization (NFV) makes the embedding solution of the SFC flexible as far as the deployment location is concerned. When providers embed the SFC into a substrate network, they will hope to minimize the setup cost of the SFC and link connection cost toward clients. For unicast, since there is one path connecting the source node to the destination node, all functions of the SFC are just needed to be deployed along the path. However, when embedding the SFC for a multicast task, the topology of the SFC may change because the function deployment locations have impacts on the traffic delivery cost. Thus, a service function tree (SFT) may be a better choice. Given the huge space of SFT embedding solutions, however, it is extremely hard to find the optimal one such that the total traffic delivery cost is minimized. In this paper, we tackle the optimal SFT embedding problem in the NFV enabled multicast task. Specifically, we formally define the problem and formulate it with an integer linear programming (ILP), which turns out to be NP-hard. Then, a two-stage method is proposed to deal with the problem with an approximation ratio of$1+\rho $, where$\rho $is the best approximation ratio of Steiner tree and can be as small as 1.39. With extensive experimental evaluations, we demonstrate that by applying our SFT embedding solution, the delivery cost of multicast traffic can be reduced by 22.05% at most against three benchmarks.

In network traffic engineering, multicast is designed to deliver the same content from a single source to a group of destinations. Recently, NFV enabled multicast has been developed by deploying virtual network functions (VNFs) over the target network. To fulfill the multicast task with a service function chain (SFC) requirement, a service function tree (SFT) embedded in the shared multicast tree has to be built. Given the huge space of SFT embedding solutions, however, it is extremely hard to find the optimal one such that the total traffic delivery cost is minimized. In this paper, we tackle the optimal SFT embedding problem in NFV enabled multicast task. Specifically, we formally define the problem and formulate it with an integer linear programming (ILP), which turns out to be NP-hard. Then, a two-stage algorithm is proposed to deal with the problem with an approximation ratio of 1+p, where p is the best approximation ratio of Steiner tree and can be as small as 1.39. With extensive experimental evaluations, we demonstrate that by applying our SFT embedding solution, the cost saving of multicast traffic delivery can be up to 22.41%, compared with the random SFT embedding strategy.

Network Function Virtualization (NFV) is an emerging technology, which enables service agility, flexibility and cost reduction by replacing traditional hardware middleboxes with Virtual Network Functions (VNFs) running on general-purpose servers. Service Function Chain (SFC) constitutes an end-to-end service by organizing a series of VNFs in a specific order. Particularly, hybrid SFC (SFC with parallel VNFs) is proposed to much reduce the traffic delay in sequential SFCs. Nevertheless, how to strategically select VNF instances and links in hybrid SFC embedding remains an open problem. In this paper, we target at the cost minimization and address the optimal hybrid SFC embedding problem. Specifically, we first develop a novel abstraction model for the hybrid SFC with Directed Acyclic Graph (DAG), which helps convert diverse hybrid SFCs to the standardized DAG-SFC form. Then, we formulate the optimal DAG-SFC embedding problem as an integer optimization model and propose a greedy method (called BBE) to solve the NP-hard problem. MBBE method is developed upon BBE method to further cut down the computation complexity in model solving. Extensive simulation results demonstrate the effectiveness of our approach for cost reduction in hybrid SFC embedding.