Constraint Games for Stable and Optimal Allocation of Demands in SDN

Constraint Games for Stable and Optimal Allocation of Demands in SDN

Anthony Palmieri, Arnaud Lallouet, Luc Pons

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Best Sister Conferences. Pages 6216-6220. https://doi.org/10.24963/ijcai.2019/866

Software Defined Networking (or SDN) allows to apply a centralized control over a network of computers in order to provide better global throughput. One of the problem to solve is the multi-commodity flow routing where a set of demands (or commodities) have to be routed at minimum cost. In contrast with other versions of this problem, we consider here problems with congestion that change the cost of a link according to the capacity used. We propose here to study centralized routing with Constraint Programming and selfish routing with Constraint Games. Selfish routing reaches a Nash equilibrium and is important for the perceived quality of the solution since no user is able to improve his cost by changing only his own path. We present real and synthetic benchmarks with hundreds or thousands players and we show that for this problem the worst selfish routing is often close to the optimal centralized solution.
Keywords:
Constraints and SAT: Constraints: Applications
Agent-based and Multi-agent Systems: Algorithmic Game Theory