Deep Multi-Agent Reinforcement Learning with Minimal Cross-Agent Communication for Service Function Chain Embedding

Network Function Virtualization (NFV) promotes the use of virtual network functions (VNFs), which can be grouped to form a service function chain (SFC). A critical challenge within NFV is SFC embedding (SFC-E), which is mathematically expressed as a graph-in-graph embedding problem. Given its NP-hardness, SFC-E is commonly solved by approximation methods. Yet, the relevant literature exhibits a gradual shift towards data-driven SFC-E frameworks, namely deep reinforcement learning. In this article, we initially identify crucial limitations of existing SFC-E approaches. In particular, we identify that most of them have their grounds, not on the algorithmic framework per se, rather on its exercise in a centralized fashion. Thereby, we devise a cooperative deep multi-agent reinforcement learning (DMARL) scheme for decentralized SFC-E, which fosters the efficient communication of neighboring agents. Our simulation-based experimentation (i) demonstrates that DMARL outperforms a state-of-the-art double deep Q-learning algorithm, (ii) unfolds the fundamental behaviors learned by the team of agents, (iii) highlights the importance of information exchange between agents, and (iv) showcases the implications stemming from various network topologies on the DMARL efficiency.