Distributed Service Function Chaining in NFV-Enabled Networks: A Game-Theoretic Learning Approach

In network function virtualization (NFV), Service Function Chaining (SFC) provides an ordered sequence of virtual network functions (VNFs) and subsequent steering of traffic flows through them to cater to end-to-end services. This paper addresses the NP-hard problem of minimum cost SFC deployment to support customer services that access the carrier network's NFV infrastructure (NFVI) through some edge routers. To determine the mappings of VNFs to physical servers, a challenging aspect would be the inter-server latencies that may fluctuate over time because of the sharing nature of cloud data centers. To construct the SFC, we come up with three different formulations, each corresponding to a different informational assumption about the link latencies: First, a centralized integer linear programming (ILP) formulation is given under the assumption of the non-causal availability of exact and instantaneous inter-server latencies. The solution to this ILP can serve as a lower bound to benchmark more scalable and realistic schemes. Next, we give a distributed game-theoretic formulation (with service broker agents as players) which only requires the statistical knowledge of link latency fluctuations. The game provably admits a pure Nash equilibrium (NE) and can be solved iteratively through the well-known best response dynamics (BRD) algorithm. Our main novelty lies in the third formulation in which each service broker has neither instantaneous nor statistical knowledge of the latencies. Instead, it relies on a game-theoretic learning algorithm to compose its VNF chain only based on its own history of adopted decisions and experienced delays on each logical link. We prove that the proposed learning algorithm asymptotically converges to NE and evaluate its performance through simulations in terms of convergence and the impact of network parameters.