On distributed selfish routing

Project Type: Master/Diploma Thesis
Student: Wolkersdorfer Martin
Mentor: Gernot Kubin

 

 In this work we investigate several strategies for distributed optimization of multi-agent systems on the basis of the optimal routing problem in data networks. While a classical objective is to break the problem up into several, in parallel solvable optimization problems, the game-theoretical approach is to design mechanisms which render the actions of by assumption selfish and rational agents optimal. Recently several traffic engineering algorithms were proposed which build upon evolutionary game theory. In this context we study the application of the projected gradient algorithm for selfish routing on different levels of parallelization and compare it to the famous replicator dynamic and the GLP- gradient projection algorithm by flow-based simulations in scale-free networks. Many algorithms that are derived from game theory show lower complexity in terms of communication overhead, where the sub-optimality of selfish routing is negligible in realistic scenarios. Most notably, we derive a time-convergence bound for path-based projected gradient routing dependent on network parameters. Specifically the convergence time increases with increasing path-interdependence. Furthermore, we obtain a novel, practically applicable, node-based routing scheme which builds upon ideas from evolutionary game theory.