Latency Minimization Through Optimal User Matchmaking in Multi-Party Online Applications

To improve the user experience in multi-party online applications, i.e., low gaming lag in online gaming, the maximum latency between any pair of users should be minimized. Considering the multiple preferences of users, i.e., which group a user can join, we address the User Latency Minimization (ULM) problem by performing an optimal matchmaking. This paper proves that the ULM problem is NP-hard if users have more than two preferences. We prove that the ULM problem has the sub-modular property and we apply the classic greedy algorithm with an approximation ratio of 1+ n, where n is the number of users with multiple preferences. Furthermore, we observe that a matchmaking priority for users in different locations exists and thus we propose a revised greedy algorithm with an approximation bound and discuss its performance in the tree structure and the general structure. Specifically, the revised greedy algorithm achieves an approximation ratio of m/2 with lower complexity in the tree structure, where m is the number of preferences in the general structure. Finally, we develop a disstributed greedy approach which converges quickly. Extensive trace-driven experiments from Internet measurements demonstrates that our schemes achieve good performances.