Online Service Function Chain Placement for Cost-Effectiveness and Network Congestion Control

The emerging network function virtualization is migrating traditional middleboxes, e.g., firewalls, load balancers, proxies, from dedicated hardware to virtual network functions (VNFs) running on commercial servers defined as network points of presence (N-PoPs). VNFs further chain up for more complex network services called service function chains (SFCs). SFCs introduce new flexibility and scalability which greatly reduce expenses and rolling out time of network services. However, chasing the lowest cost may lead to congestion on popular N-PoPs and links, thus resulting in performance degradation or violation of service-level agreements. To address this problem, we propose a novel scheme that reduces the operating cost and controls network congestion at the same time. It does so by placing VNFs and routing flows among them jointly. Given the problem is NP-hard, we design an approximation algorithm named candidate path selection (CPS) with a theoretical performance guarantee. We then consider cases when SFC demands fluctuate frequently. We propose an online candidate path selection (OCPS) algorithm to handle such cases considering the VNF migration cost. OCPS is designed to preserve good performance under various migration costs and prediction errors. Extensive simulation results highlight that CPS and OCPS algorithms perform better than baselines and comparably to the optimal solution.