Service Function Chain Optimal Composition and Embedding: A Systematic Survey of Optimisation Approaches (to appear)

Abstract

Service Function Chains (SFCs) support computer networks to keep pace with increasing user numbers and changing usage patterns by enabling network programmability. SFCs virtualise network functions, such as firewalls, enabling them to be programmatically embedded on servers and linked, creating a chain of virtual network functions. Optimally composing and embedding SFCs on physical networks is an NP-hard optimisation problem. Since 2016, there has not been a comprehensive literature survey of approaches to optimally compose and embed SFCs across all application domains.

In this work, we survey the literature, identify, and analyse 209 papers based on their title, abstract and content. We then develop an analytical framework to extract data from the curated papers. Based on the data, we propose an update to the existing three-stage definition of the optimal SFC composition and embedding problem, factoring in recent technological advancements and approaches. We analyse the extracted data in terms of use cases, including optimisation objectives, application domains, physical network topologies, algorithms used, their scalability, their adaptability to a dynamic network environment, and the evaluation mechanisms used. Based on this analysis, we finally present emerging trends and identify research gaps in the literature.