Multiservice Function Chain Embedding With Delay Guarantee: A Game-Theoretical Approach

Through network function virtualization (NFV), virtual network functions (VNFs) can be mapped onto substrate networks as service function chains (SFCs) to provide customized services with guaranteed Quality of Service (QoS). In this article, we solve a multi-SFC embedding problem by a game-theoretical approach considering the heterogeneity of NFV nodes, the effect of processing-resource sharing among various VNFs, and the capacity constraints of NFV nodes. Specifically, each SFC is treated as a player whose objective is to minimize the overall latency experienced by the supported service flow, while satisfying the capacity constraints of all NFV nodes. Due to processing-resource sharing, additional delay is incurred and incorporated into the overall latency for each SFC. The capacity constraints of NFV nodes are considered by adding a penalty term into the cost function of each player, and are guaranteed by a prioritized admission control mechanism. We prove that the formulated resource-constrained multi-SFC embedding game (RC-MSEG) is an exact potential game admitting at least one pure Nash equilibrium (NE) and has the finite improvement property (FIP). Two iterative algorithms are developed, namely, the best response (BR) algorithm with fast convergence and the spatial adaptive play (SAP) algorithm with great potential to obtain the best NE. Simulations are conducted to demonstrate the effectiveness of the proposed game-theoretical approach.