Abstraction de communication pour la synchronisation de données dans les systèmes virtuels et répartis : application aux jeux multijoueurs sur téléphone portable, Communication abstraction for data synchronization in distributed virtual environments : application to multiplayer games on mobile phones

Abdul Malik Khan

Description

Sous la direction de Guy Bernard, Antoine Beugnard
Thèse soutenue le 17 juin 2010: Institut national des télécommunications d'Evry
Dans les jeux multijoueurs, où plusieurs joueurs participent à une même partie et communiquent entre eux à travers un réseau, les joueurs peuvent avoir des visions différentes du jeu en raison des délais de communication. Ceci engendre des incohérences encore plus importantes sur les réseaux mobiles tels que les réseaux 3G où les délais de communication peuvent atteindre plusieurs secondes. Des algorithmes doivent donc être mis en place pour maintenir la cohérence entre les joueurs. Ces algorithmes sont assez complexes et difficiles à programmer et mettre au point. Le but de cette thèse est de proposer une architecture logicielle qui découple la conception du jeu, de ses besoins de communication en proposant une infrastructure de communication qui pourra être interchangeable en fonction des technologies ; cette infrastructure prend la forme originale d'un composant de synchronisation. Ainsi, les conséquences des propriétés physiques du transport des informations pourront être plus ou moins masquées en intégrant dans cette infrastructure les algorithmes adéquats.
-Jeu multi-joueurs
-Système virtuel et réparti
Multiplayer games users' have increased since the widespread use of the internet. Withthe arrival of rich portable devices and faster cellular wireless networks, multiplayer games on mobile phones and PDAs are becoming a reality. For multiplayer games to be playable, they should be highly interactive, fair and should have a consistent state for all the players. Because of the high wireless network latency and jitters, the issue of providing interactive games with consistent state across the network is non-trivial. In this thesis, we propose different approaches for achieving consistency in mobile multiplayer games in the face of high latency and large and variable jitters. Although absolute consistency is impossible to achieve because information takes time to travel from one place to another, we exploit the fact that strong consistency is not always required in the virtual world and can be relaxed in many cases. Our proposed approach uses the underlying network latency and the position of different objects in the virtual world to decide when to relax consistency and when to apply strong consistency mechanisms. We evaluate our approach by implementing these algorithms in J2ME based games played on mobile phones. The algorithms for consistency mechanism are very complex and are often intermixed with the game core logic's code, which makes it hard to program a game and to change its code in the future. We propose to separate the consistency mechanisms from the game logic and put them in a distributed component responsible for both consistency maintenance and communication over the network. We call this reusable component a Synchronization Medium.
Source: http://www.theses.fr/2010TELE0011/document

Informations

• Publié par: Thesee
• Nombre de lectures: 12
• Langue: English
• Poids de l'ouvrage: 3 Mo

Extrait

Th`ese de doctorat de l’INSTITUT NATIONAL DES TELECOMMUNICATIONS dans le cadre
de l’´ecole doctorale S&I en co-accr´editation avec
´l’Universit´e d’Evry-Val d’Essonne
Sp´ecialit´e :
Informatique
Par
M. Abdul Malik KHAN
Th`ese pr´esent´ee pour l’obtention du grade de Docteur
de l’INSTITUT NATIONAL DES TELECOMMUNICATIONS
Communication Abstraction for Data Synchronization in
Distributed Virtual Environments
Application to Multiplayer Games on Mobile Phones
Soutenue le 17 Juin 2010 devant le jury compos´e de :
Rapporteurs :
M. Salah Sadou Maˆıtre de conf´erences (HDR), Universit´e de Vannes
M. Eric Gressier-Soudan Professeur, CNAM, Paris
Examinateurs :
M. Mourad Oussalah Professeur, Universit´e de Nantes
M. Guy Bernard Professeur, T´el´ecom SudParis (Directeur de th`ese)
M. Antoine Beugnard Professeur, T´el´ecom Bretagne (co-Directeur de th`ese)
Mme Sophie Chabridon Maˆıtre de conf´erences, T´el´ecom SudParis (Encadrante)
Th`ese Num´ero : 2010TELE0011
tel-00541849, version 1 - 1 Dec 2010tel-00541849, version 1 - 1 Dec 2010Acknowledgements
I would like to express my gratitude, appreciation and sincere thanks
tomysupervisorsDr.GuyBernard,Dr.AntoineBeugnardandDr.So-
phie Chabridon, for their excellent guidance,helpful and useful discus-
sions, and continuous encouragement which made this work possible.
They always helped me with pleasure in the problems that I faced du-
ring this work.
I am deeply indebted to all professors and students in my team for
their support. I am especially grateful to Michel Simatic for his sup-
port both in terms of resources and encouragement.
DeepthankstomyfellowdoctoralstudentJ´eroˆmeSicard.Ihavealways
benefited from him through discussion both technically and socially.
He has always encouraged me to improve my french language.
I cannot forget the constant encouragment and support of my whole
family including my brothers and sisters.
I dedicate this work to my beloved mother whose constant support
and prayers are gospel of encouragement for me to keep struggling for
ambitions.
tel-00541849, version 1 - 1 Dec 2010tel-00541849, version 1 - 1 Dec 2010Abstract
Multiplayergamesusers’haveincreasedsincethewidespreaduseoftheinternet.
With the arrival of rich portable devices and faster cellular wireless networks, the
multiplayer games on mobile phones and PDAs are becoming a reality.
For multiplayer games to be playable, they should be highly interactive, fair
and should have a consistent state for all the players. Because of the high wireless
network latencyandjitters,theissueofprovidinginteractive gameswithconsistent
state across the network is non-trivial.
In this report, we propose different approaches for achieving consistency in
mobile multiplayer games in the face of high latency and, large and variable jitters.
Although absolute consistency is impossible to achieve because information takes
time to travel from one place to another because of the limited light speed, our
proposed approaches exploit the fact that strong consistency is not always required
in the virtual world and can be relaxed in many cases. Based on the underlying
network latency andthe positionof differentobjects in the virtual world, we decide
when to relax consistency and when to apply strong consistency mechanisms. We
evaluate our approach by implementing these algorithms in J2ME based games
played on mobile phones.
Also, the consistency resolution is dependent upon the choice of the network.
Games companies prefer client-server architecture for its control over the users
and its simplicity of consistency resolution. But such an architecture has some
disadvantages such as a limited scalability and a high latency. P2P architectures
ontheotherhandareopentocheatingandhavenocentralcommandoverthegame
servers. As a second contribution, we propose a hybrid architecture to achieve high
interactivity and consistency as well as game services providing companies with a
central control over the game.
The algorithms for consistency mechanism are very complex and are often in-
termixed with the game core logic’s code, which makes it hard to program a game
and to change its code over time. Our third and last contribution takes the form of
anapproachto separate consistency mechanisms fromthegame logic andputthem
in a distributed component responsible for both consistency maintenance and com-
munication over the network. We call this reusable component a ‘Synchronization
Medium’. We show the reusability of our synchronization medium by deploying
two different multiplayer games on the top of it.
Keywords: Multiplayer Games, Distributed Virtual Environments, Consis-
tency Maintenance, Architecture
tel-00541849, version 1 - 1 Dec 2010tel-00541849, version 1 - 1 Dec 2010Publications relevant to the thesis
• Khan, A. M., Chabridon, S., and Beugnard, A. (2007). Synchronization
medium: aconsistencymaintenancecomponentformobilemultiplayergames.
In Armitage, G. J., editor, Proceedings of the 6th Workshop on Network
and System Support for Games, NETGAMES 2007, Melbourne, Australia,
September 19-20, 2007, pages 99-104. ACM.
• Khan, A. M., Chabridon, S., and Beugnard, A. (2008). A dynamic approach
to consistency management for mobile multiplayer games. In CDUR’08
Workshop of NOTERE’08, 8th International conference on New technolo-
gies in distributed systems, pages 1-6, Lyon, France, June 23, ACM.
• Khan, A. M., Arsov, I., Preda, M., Chabridon, S., and Beugnard, A. (2010).
Adaptable client-server architecture for mobile multi-player games. In DI-
SIO’10: Proceedings of the Workshop on DIstributed SImulation & Online
gaming of the SIMUTools Conference, Torremolinos, Malaga, Spain, March
15.
• Khan, A. M., Chabridon, S., and Beugnard, A. (2010). A Reusable Com-
ponent for Communication and Data Synchronization in Mobile Distributed
Interactive Applications, International Workshop on Component and Ser-
vice Interoperability (WCSI-10), in conjunction with Tools 2010 Federated
Conferences, Malaga, Spain, June 29.
tel-00541849, version 1 - 1 Dec 2010tel-00541849, version 1 - 1 Dec 2010Contents
R´esum´e long iii
I Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
I.1 Probl´ematique . . . . . . . . . . . . . . . . . . . . . . . . . . iv
I.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . v
I.3 Organisation de ce r´esum´e . . . . . . . . . . . . . . . . . . . . v
´II Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
II.1 Algorithmes de maintien de la coh´erence pour les environ-
nements virtuels distribu´es . . . . . . . . . . . . . . . . . . . v
II.2 Architectures Syst`emes pour Jeux Multijoueurs . . . . . . . . vi
II.3 S´eparation de la pr´eoccupation de coh´erence de la logique du
jeu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
II.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
III Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
III.1 Algorithmes de Synchronisation pour Jeux Multijoueurs sur
T´el´ephone Mobile . . . . . . . . . . . . . . . . . . . . . . . . ix
III.2 Architecture Syst`eme pour Jeux Multijoueurs . . . . . . . . . xiii
III.3 Un M´edium de Synchronisation . . . . . . . . . . . . . . . . . xiv
IV Conclusion et Perspectives . . . . . . . . . . . . . . . . . . . . . . . . xvi
1 Introduction 1
1.1 Problem Presentation . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . 4
I State of the art 7
2 State of the Art: Synchronization In Multiplayer Games 9
2.1 Consistency Maintenance Algorithms in Distributed Virtual Envi-
ronments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
ix
tel-00541849, version 1 - 1 Dec 2010x CONTENTS
2.1.1 Conservative Approach . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Optimistic Approach . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3 Roll Back Approach . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.4 Analysis of Consistency Maintenance Algorithms . . . . . . . 19
2.1.5 Use of Synchronization Algorithms in Other Domains . . . . 19
2.2 System Architecture For multiplayer Games . . . . . . . . . . . . . . 21
2.2.1 Client-Server Architecture . . . . . . . . . . . . . . . . . . . . 21
2.2.2 Distributed Architectures . . . . . . . . . . . . . . . . . . . . 23
2.3 Separation of Consistency Issues from the Game logic . . . . . . . . 25
2.3.1 Medium: A Communication Component . . . . . . . . . . . . 25
2.3.2 Plug-Replaceable Consistency Management . . . . . . . . . . 28
2.3.3 Matrix Middleware . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
II Contribution 31
3 SynchronizationAlgorithmsforMultiplayerGamesonmobilephones 33
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 An Adaptable Approach to State Consistency in Mobile Multiplayer
Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Observations . . . . . . . . . . . . .