Cost-Efficient VNF Placement and Scheduling in Public Cloud Networks

Following successful adoption of cloud computing, many service providers (SPs) are now using high-performance Virtual Machines (VMs) located in large datacenters owned by public cloud infrastructure providers to deploy their virtual network functions (VNFs). Since using these VMs has a cost depending on utilization time, a complex problem of VNF placement and scheduling (VPS) must be addressed to achieve satisfactory network performance (e.g., latency) while minimizing the cost paid to lease VMs. In this study, a cost-efficient VPS scheme (CE-VPS) is proposed to address the VPS problem in public cloud networks considering dynamic requests of ordered sequences of VNFs. Our CE-VPS scheme goes beyond existing solutions as it models some important practical aspects such as an additional latency incurred by booting a VM and installing a VNF instance. Also, CE-VPS considers that VNFs can be multi-threaded or single-threaded, and that their throughput as a function of allocated computing resources must be modeled differently. CE-VPS is formulated as a mixed inter linear program (MILP) and also as an efficient heuristic algorithm. CE-VPS achieves lower cost and latency than conventional Best-Availability and Cost-Efficient Proactive VNF Placement schemes, and a better trade-off between resource consumption and latency performance than a conventional Low-Latency scheme.