NFV-Based Distributed Service Function Chaining with Imperfect Information

Software-defined networking (SDN) and network function virtualization (NFV) technologies have emerged as promising paradigms in recent innovations for deploying users' demanded services. In this context, service function chaining (SFC) helps telecommunication operators to provide complex network services and improve their performance. This paper first addresses the service function chain deployment problem as an integer linear programming (ILP) problem under an impractical non-causal assumption about the network information for which we provide a solution in a centralized fashion. However, in real-life networks, distributed schemes are more scalable. Also, some parameters, such as the latency of the links, fluctuate over time because of the sharing nature of cloud datacenters, and their probabilistic distributions are unknown prior to deployment. Therefore, we re-formulate the NFV -based SFC deployment problem as a noisy weighted congestion game and rely only on the actually experienced delay samples on each of the links to configure SFCs in a near-optimal fashion. In particular, we propose a multi-agent learning based algorithm using which each agent decides its VNF -based service chain only based on its own history of adopted actions and realized costs. By changing the network configuration, simulation results show that our proposed algorithm is at most 18% worse than the optimal solution, and in some situations, it behaves exactly the same as optimal results.