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

Ning Wang, Jie Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication19th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, WoWMoM 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Print)9781538647257
DOIs
StatePublished - Aug 28 2018
Externally publishedYes
Event19th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, WoWMoM 2018 - Chania, Greece
Duration: Jun 12 2018Jun 15 2018

Publication series

Name19th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, WoWMoM 2018

Conference

Conference19th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, WoWMoM 2018
Country/TerritoryGreece
CityChania
Period6/12/186/15/18

All Science Journal Classification (ASJC) codes

  • Media Technology
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Latency Minimization Through Optimal User Matchmaking in Multi-Party Online Applications'. Together they form a unique fingerprint.

Cite this