On Dynamic Mapping and Scheduling of Service Function Chains in SDN/NFV-Enabled Networks

Software-defined networking (SDN) and network function virtualization (NFV) together form a promising paradigm that enables the slicing of heterogeneous network resources for agile and efficient service customization. Among other techniques, virtual network function (VNF) mapping and scheduling are crucial to the deployment of SDN/NFV-enabled network services. In this paper, to enhance the performance of service provisioning, dynamic VNF mapping and scheduling are jointly investigated. Specifically, to achieve load balancing with QoS guarantee, we first formulate the VNF mapping and scheduling problem as a mixed integer linear programming (MILP). We then propose a two-stage online algorithm to address the NP-hardness of the MILP. In particular, when new service arrives, we map and schedule the VNFs on a service function chain (SFC) by greedily minimizing the waiting time of VNFs. If the delay requirement cannot be satisfied after the first stage, a delay-aware rescheduling scheme is triggered, in which selected existing VNFs are remapped and rescheduled. The proposed dynamic approach achieves flexible function placement and increases service acceptance ratio. Simulation results are provided to validate the effectiveness of the proposed algorithm.