Contact: Nicolas Gast
Let us consider a simple scenario. There is a high number of connections available and users that want to access these connections. If each user chooses the least load connection among two or more, the situation is known to be greatly improved compared to a case where each user chooses one connection at random [1]. Recent studies on multi-path routing have shown that an a posteriori choice of route improves the situation even more [2].
The goal of this project is to study the effect of geometry on these randomized load balancing strategies: instead of choosing two connections at random, the user chooses two neighboring connections (this might be due to locality constraints, for example if the connections are wireless connections). Two directions will be explored. A first step will be to write a simulator and obtain numerical insights. The second part will be more theoretical. The goal will be be to extend mean field techniques [3] to obtain analytical results, using approximation techniques such as pair approximation [4].
Some references:
[1] M. Mitzenmacher, A. Richa, and R. Sitaraman, The Power of Two Random Choices: A Survey of Techniques and Results. Handbook of Randomized Computing, 2001.
[2] P. Key, L. Massoulie, D. Towsley; Path Selection and Multipath Congestion Control. Infocom 2007.
[3] M. Benaïm and J.-Y. Le Boudec. A class of mean field interaction models for computer and communication systems. Performance Evaluation, 2008.
[4] H. Ohtsuki1, C. Hauert, E. Lieberman, and M. Nowak. A simple rule for the evolution of cooperation on graphs and social networks. Nature, 2006.