TL;DR
This paper tackles the inherent conflicts and inefficiencies arising from multiple overlay networks coexisting on top of an underlay network managed by a traffic engineer (TE). It proposes a novel coalition game framework, leveraging Shapley value, to achieve a more stable, efficient, and fair outcome for all participants, moving beyond the limitations of traditional game theory approaches.
What Problem Does This Paper Address?
The internet is increasingly populated by overlay networks (like CDNs, P2P systems) built on top of the existing IP infrastructure. These overlays optimize their own performance, often leading to sub-optimal outcomes for the underlying physical network managed by Internet Service Providers (ISPs) through traffic engineering (TE). Furthermore, multiple overlays competing for the same physical resources can create further conflicts. This "hybrid interaction" between overlays and TE, and among overlays themselves, can lead to inefficient equilibria, where no single player can improve their situation by unilaterally changing their strategy, but the overall network performance is suboptimal. The paper aims to model these interactions and propose a mechanism to resolve these inefficiencies.
Methods
The authors employ a multi-pronged game-theoretic approach:
- Non-Cooperative Game Theory:
- N+1 Player Non-Cooperative Game: They first model the interaction as a game where overlays and TE have equal status. They prove the existence of a Nash Equilibrium (NE) using dynamic best response, which is computed using a genetic algorithm (GA).
- 1-Leader-n-Follower Stackelberg-Nash Game: They then model a scenario where TE has higher status and acts as a leader, with overlays as followers. This Stackelberg-Nash Equilibrium (SNE) is also computed using GA. They prove that SNE offers at least as good a cost for TE as NE.
- Cooperative Game Theory:
- Coalition Game and Shapley Value: To overcome the inefficiencies of NE and SNE, they introduce a cooperative coalition mechanism. Players (overlays and TE) can form coalitions to collectively optimize their performance. The Shapley value is used to fairly allocate costs among coalition members, ensuring individual efficiency and fairness. They also model the coalition formation process itself as a non-cooperative game.
Datasets
Not discussed in the paper. The authors use a simulated 50-node physical network with three co-existing overlay networks for their experiments.
Key Insights and Ideas
- Hybrid Interaction is Inevitable and Inefficient: The core insight is that the interplay between overlays and TE, and among overlays, is a fundamental aspect of modern networks, and without proper coordination, it leads to suboptimal performance for everyone.
- Nash and Stackelberg Equilibria are Suboptimal: While these game theory concepts describe stable states, they don't guarantee the best overall outcome, especially when multiple players have conflicting objectives.
- Cooperation is Key to Efficiency: The paper strongly advocates for cooperative approaches to resolve these conflicts. By forming coalitions, players can achieve better outcomes than in non-cooperative settings.
- Shapley Value for Fair Cost Allocation: The Shapley value provides a mathematically sound and fair way to distribute costs within a coalition, considering each player's marginal contribution. This is crucial for incentivizing cooperation.
- Coalition Formation as a Game: Even the process of forming coalitions can be modeled as a game, where players iteratively decide who to cooperate with to minimize their own costs.
Key Results
- NE and SNE Convergence: The simulations demonstrate that the dynamic best response approach, implemented with genetic algorithms, successfully converges to stable NE and SNE states for both the non-cooperative and Stackelberg-Nash models.
- SNE Benefits TE: The Stackelberg-Nash Equilibrium shows that TE, by acting as a leader, can achieve a lower congestion cost compared to the Nash Equilibrium.
- Coalition Game Outperforms: The proposed coalition cooperation scheme, based on Shapley value, significantly outperforms NE, SNE, and other existing methods (like Nash Bargaining Solution) in terms of both TE's congestion cost and overlays' delay cost.
- Stable Coalition Structure Identified: In their simulation with three overlays, they identified a stable coalition structure where TE, overlay 1, and overlay 3 cooperate, while overlay 2 remains separate. This highlights that not all players may need to be in the same grand coalition for optimal outcomes.
- Malicious Traffic Impact: The study also briefly touches upon the impact of malicious traffic, showing that while it exacerbates performance issues across all schemes, the coalition cooperation scheme still offers a relatively better outcome.
Limitations and Future Work
- Non-Transferable Costs: The paper acknowledges that delay and congestion costs are inherently non-transferable. The Shapley value, while fair, requires external coordination to be fully implemented.
- Negotiation Costs: Future work could focus on reducing negotiation costs and specifying equivalent weights for different types of costs (delay vs. congestion) to further refine the coalition formation and cost allocation mechanisms.
- Complexity of Large-Scale Networks: While the paper uses a simulated network, extending the findings to very large and complex real-world networks might present computational challenges.
- Malicious Traffic Mitigation: While the impact of malicious traffic was briefly explored, a more in-depth study on how to mitigate its effects within the coalition framework would be valuable.
Summary updated