LAUSR

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.