Abstract
For state-of-the-art network function virtualization (NFV) systems, it remains a key challenge to conduct effective service chain composition for different network services (NSs) with ultra-low request latencies and minimum network congestion. To this end, existing solutions often require full knowledge of the network state, while ignoring the privacy issues and overlooking the non-cooperative behaviors of users. What is more, they may fall short in the face of unexpected failures such as user unavailability and virtual machine breakdown. In this paper, we formulate the problem of service chain composition in NFV systems with failures as a non-cooperative game. By showing that such a game is a weighted potential game and exploiting the unique problem structure, we propose two effective distributed schemes that guide the service chain compositions of different NSs towards the Nash equilibrium (NE) state with both near-optimal latencies and minimum congestion. Besides, we develop two novel learning-aided schemes as comparisons, which are based on deep reinforcement learning (DRL) and Monte Carlo tree search (MCTS) techniques, respectively. Our theoretical analysis and simulation results demonstrate the effectiveness of our proposed schemes, as well as the adaptivity when faced with failures.
Introduction
In the world of Network Function Virtualization (NFV), the goal is to move away from rigid, dedicated hardware and toward flexible, software-based services. However, "chaining" these virtual functions together efficiently is an NP-hard problem, made even more difficult by the messy realities of the real world: servers crash, users drop off unexpectedly, and individual users often act in their own self-interest rather than for the good of the network.
In NFV systems, a Network Service (NS) is created by chaining together Virtual Network Functions (VNFs)—like firewalls, load balancers, and deep packet inspectors—in a specific order. The challenge is twofold:
- Complexity & Selfishness: Finding the best path through these VNFs to minimize latency and congestion is computationally expensive. Furthermore, users are "non-cooperative"; they want the best path for themselves, which often leads to resource contention.
- Unreliability: Most existing models assume a perfect network. In reality, virtual machines (VMs) crash and user connections drop. Existing solutions often require a "God's eye view" of the network, which violates user privacy and fails when the network state changes dynamically.
Methodology and Proposed Algorithms
The researchers tackle this by framing Service Chain Composition (SCC) as a non-cooperative game. They prove that this game is a weighted potential game. This is a crucial property in game theory: it means that any individual user’s attempt to improve their own cost (local improvement) is mathematically guaranteed to improve the overall system performance (global potential). This ensures that a Nash Equilibrium (NE) exists and that decentralized, selfish optimization doesn't lead to total network chaos.
The paper introduces several schemes to address these challenges:
- MA-SCCA (Markov Approximation): A distributed scheme where users interact to reach a Nash Equilibrium using a "Poisson countdown clock" mechanism.
- MH-SCCA (Metropolis-Hastings): A faster, lower-complexity variant of MA-SCCA that uses a proposal-based strategy update.
- Learning-Aided Baselines: Centralized schemes using Deep Reinforcement Learning (DRL-SCCA) and Monte Carlo Tree Search (MCTS-SCCA) for comparison.
Experimental Setup and Results
The study uses a simulation environment with servers hosting multiple VNF types and users with defined traffic rates. Survival probabilities for users and VMs were set to 0.9. Key findings include:
- Convergence & Speed: MH-SCCA converged significantly faster than the standard MA-SCCA. While it has a slightly higher computational overhead than simple "best response" baselines, it avoids getting stuck in poor local optima.
- Robustness to Failures: In simulations, when a VM failed, the system recovered to a stable, near-optimal state in less than 20 seconds. The authors found that VM failures are more damaging to system cost than user failures because a single VM crash can disrupt multiple service chains simultaneously.
- DRL vs. Distributed: The DRL-based approach achieved the absolute best performance but is "brittle" to topology changes. MH-SCCA, however, handles changes in the number of servers or users gracefully without requiring expensive re-training.
Conclusion
This work provides a robust mathematical framework to navigate the challenges of SCC using game theory and distributed algorithms. By modeling SCC as a weighted potential game, the authors demonstrate that selfish, decentralized user behavior can lead to a globally optimal network state. Future work includes addressing correlated failures and making learning models topology-agnostic to scale across massive IoT deployments.
Summary updated