Constraint Games for Stable and Optimal Allocation of Demands in SDN

Anthony Palmieri, Arnaud Lallouet, Luc PonsIJCAI 2019 · DOI

TL;DR

This paper tackles the challenge of efficiently and fairly allocating network resources in Software-Defined Networks (SDN) by modeling it as a "Constraint Game." They introduce a novel approach that combines Constraint Programming for optimal centralized solutions with Constraint Games to find stable, decentralized "Nash equilibria," showing that these decentralized solutions are surprisingly close to optimal.

What Problem Does This Paper Address?

Modern networks, especially with the rise of the Internet of Things (IoT), are experiencing a massive increase in data traffic. Software-Defined Networking (SDN) offers a promising solution by enabling centralized control and flexible network reconfiguration. A key problem within SDN is the "multi-commodity flow routing," where multiple data demands (commodities) need to be routed across the network. This routing must consider not only minimizing overall network cost but also dealing with "congestion," where link costs increase as more traffic uses them. Furthermore, for a good user experience, the routing should be "stable," meaning no individual user can improve their own situation by unilaterally changing their path. This paper addresses the challenge of finding routing solutions that are both globally optimal and individually stable, especially in scenarios with many competing demands.

Methods

The authors propose a two-pronged approach:

  • Constraint Programming (CP) for Optimal Centralized Routing: They model the multi-commodity path routing problem (MCPRP) with congestion as a Constraint Programming problem. This allows them to find the absolute best (optimal) routing solution if a central controller makes all decisions. They introduce specific heuristics for variable and value selection within the CP solver, including strategies like "Max Bandwidth" (MB) and "Shortest Path" (SP), and a novel branch-and-bound technique that incorporates lower bounds derived from Dijkstra's algorithm to prune the search space more effectively.
  • Constraint Games for Stable Decentralized Routing: To address the stability aspect, they frame the problem as a "Constraint Game." In this model, each demand is treated as an independent "player" aiming to minimize its own routing cost. The goal is to find a "Nash equilibrium," a state where no player can improve their outcome by changing their strategy (path) alone. They leverage a Constraint Game solver (ConGa) to find these equilibria.

Datasets

The paper uses two sources for their benchmarks:

  • SNDlib: A library of instances for network design problems.
  • Personal Problem Generator: A custom generator to create instances that are closer to real-world scenarios.

Key Insights and Ideas

  • The Power of Decentralization: The paper demonstrates that decentralized routing strategies (Nash equilibria) can achieve a quality of service remarkably close to centrally optimized solutions, even in complex scenarios with many players.
  • Congestion as a Stabilizer: The congestion model, which increases link costs with usage, plays a crucial role in both optimizing the global cost and encouraging more balanced, stable routing.
  • Heuristics Matter: The choice of heuristics in both CP and Constraint Games significantly impacts performance. The "Shortest Path" heuristic, combined with "Max Bandwidth" for demand selection, proved particularly effective.
  • Constraint Games Scale: The research shows that Constraint Games can handle surprisingly large-scale problems, solving games with up to 1482 players to optimality, which is a significant advancement for game theory solvers.

Key Results

  • CP Performance: The proposed CP approach, particularly with the MB/SP/SP heuristic and improved branch-and-bound, can solve real-world size instances of the optimal centralized routing problem to optimality within a one-hour timeout.
  • Constraint Game Performance: The ConGa solver successfully found Nash equilibria for games with hundreds or even thousands of players, demonstrating the scalability of the Constraint Game framework for decentralized routing analysis.
  • Price of Anarchy/Stability: For small instances, the Price of Anarchy (PoA) and Price of Stability (PoS) were observed to be very close to 1, indicating that decentralized solutions are highly efficient and close to the centralized optimum. This suggests that decentralized algorithms could be very attractive if they can scale.

Limitations and Future Work

  • Approximating PoA/PoS: Computing the Price of Anarchy (PoA) and Price of Stability (PoS) for larger instances is challenging. The authors note that the approximation used for the longest path (via Maximum Spanning Tree) overestimates the actual cost, leading to limited pruning of the search tree and impacting computation time.
  • IBR Impact on Time: While the "Improved Branch and Bound" (IBR) technique helps find better first solutions (which are also equilibria), it was observed to slightly degrade computation time in some Constraint Game scenarios. The authors believe this might be because many initial solutions were already equilibria.
  • Future Work: The paper suggests that further research could focus on improving the PoA/PoS computation for larger instances and exploring the practical implications of these findings for real-world SDN deployments. The potential for decentralized algorithms to offer efficient and stable routing is a key area for future exploration.

Summary updated

BibTeX
@inproceedings{palmieri2019constraint,
  author = {Anthony Palmieri and Arnaud Lallouet and Luc Pons},
  title = {{Constraint Games for Stable and Optimal Allocation of Demands in SDN}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/866},
}
Figure