skip to main content
10.1145/1005847.1005880acmconferencesArticle/Chapter ViewAbstractPublication PagesmmsysConference Proceedingsconference-collections
Article

Adaptive server selection for large scale interactive online games

Published: 16 June 2004 Publication History

Abstract

In this paper, we present a novel distributed algorithm that dynamically selects game servers for a group of game clients participating in large scale interactive online games. The goal of server selection is to minimize server resource usage while satisfying the real-time delay constraint. We develop a synchronization delay model for interactive games and formulate the server selection problem, and prove that the considered problem is NP-hard. The proposed algorithm, called zoom-in-zoom-out, is adaptive to session dynamics (e.g. clients join and leave) and lets the clients select appropriate servers in a distributed manner such that the number of servers used by the game session is minimized. Using simulation, we present the performance of the proposed algorithm and show that it is simple yet effective in achieving its design goal. In particular, we show that the performance of our algorithm is comparable to that of a greedy selection algorithm, which requires global information and excessive computation.

References

[1]
J. Bar-Ilan and D. Peleg. Approximation algorithms for selecting network centers. In Proc. 2nd Workshop on Algorithms and Data Structures, Lecture Notes in Comput. Sci. 519 pages 343--354, 1991.
[2]
D. Bauer, S. Rooney, and P. Scotton. Network infrastructure for massively distributed games. In NetGames'02 April 2002.
[3]
P. Bettner and M. Terrano. 1500 archers on a 28.8: Network programming in age of empires and beyond. In Game Developers Conference 2001.
[4]
BRITE. http://www.cs.bu.edu/brite/
[5]
Butterfly.net. http://www.butterfly.net/
[6]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms MIT Press, second edition, 2001.
[7]
E. Cronin, B. Filstrup, and A. Kurc. A distributed multiplayer game server system, technical report, Univ. of michigan. Technical report, May 2001.
[8]
C. Diot and L. Gautier. A distributed architecture for multiplayer interactive applications on the internet, IEEE networks magazine, vol. 13, no. 4, July/August 1999.
[9]
Y.-J. Lin and S. P. Katherine Guo. Sync-MS: Synchronized messaging service for real-time multi-player distributed games. In Proceedings of 10th IEEE International Conference on Network Protocols (ICNP 2002), November 2002.
[10]
M. Mauve, S. Fischer, and J. Widmer. A generic proxy system for networked computer games. In NetGames'02 April 2002.
[11]
M. Parsa, Q. Zhu, and J. J. Garcia-Luna-Aceves. An iterative algorithm for delay-constrained minimum-cost multicasting. IEEE/ACM Transactions on Networking 6(4), August 1998.
[12]
PlanetSide. http://www.planetside.com/
[13]
L. Qiu, V. Padmanabham, and G.Voelker. On the placement of web server replicas. In Proc. 20th IEEE INFOCOM 2001 August 2001.
[14]
D. Saha, S. Sahu, and A. Shaikh. A service platform for online games. In NetGames'03 May 2003.
[15]
H. F. Salama, D. S. Reeves, and Y. Viniotis. An Efficient Delay-Constrained Minimum Spanning Tree Heuristic, Technical Report TR-96/46, North Carolina State University. Technical report,1996.
[16]
Terazona. http://www.zona.net/
[17]
D. G. Thaler and C. V. Ravishankar. Distributed center-location algorithms. IEEE Transactions on Selected Areas in Communications, vol. 15, issue 3 April 1997.

Cited By

View all

Index Terms

  1. Adaptive server selection for large scale interactive online games

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    NOSSDAV '04: Proceedings of the 14th international workshop on Network and operating systems support for digital audio and video
    June 2004
    168 pages
    ISBN:1581138016
    DOI:10.1145/1005847
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    In-Cooperation

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 16 June 2004

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. MMOG
    2. distributed algorithm
    3. server selection
    4. synchronization delay model

    Qualifiers

    • Article

    Conference

    NOSSDAV04
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 118 of 363 submissions, 33%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)4
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 16 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2015)The service overlay network design problem for interactive internet applicationsComputers and Operations Research10.1016/j.cor.2014.11.00357:C(73-82)Online publication date: 1-May-2015
    • (2014)Synchronization in Multiplayer Online GamesHandbook of Digital Games10.1002/9781118796443.ch7(175-196)Online publication date: 7-Mar-2014
    • (2011)The Challenge of Service Level Scalability for the CloudInternational Journal of Cloud Applications and Computing10.4018/ijcac.20110101031:1(34-44)Online publication date: 1-Jan-2011
    • (2011)On the game server network selection with delay and delay variation constraints2011 Third International Conference on Communication Systems and Networks (COMSNETS 2011)10.1109/COMSNETS.2011.5716473(1-10)Online publication date: Jan-2011
    • (2010)Mobile real-time group communication serviceProceedings of the 29th conference on Information communications10.5555/1833515.1833591(376-380)Online publication date: 14-Mar-2010
    • (2010)Mobile Real-Time Group Communication Service2010 Proceedings IEEE INFOCOM10.1109/INFCOM.2010.5462210(1-5)Online publication date: Mar-2010
    • (2010)Server selection with delay constraints for online games2010 IEEE Globecom Workshops10.1109/GLOCOMW.2010.5700451(882-887)Online publication date: Dec-2010
    • (2008)Intelligent Synchronization for Mirrored Game Servers: A Real Case StudyJournal of Advanced Computational Intelligence and Intelligent Informatics10.20965/jaciii.2008.p013212:2(132-141)Online publication date: 20-Mar-2008
    • (2008)Relative Network Positioning via CDN RedirectionsProceedings of the 2008 The 28th International Conference on Distributed Computing Systems10.1109/ICDCS.2008.54(377-386)Online publication date: 17-Jun-2008
    • (2007)AN OPTIMISTIC OBSOLESCENCE-BASED APPROACH TO EVENT SYNCHRONIZATION FOR MASSIVELY MULTIPLAYER ONLINE GAMESInternational Journal of Computers and Applications10.2316/Journal.202.2007.1.202-185529:1Online publication date: 2007
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media