Rapport du stage de fin d’études Les Abstractions de Communication dans les Jeux en Réseaux Mobiles Réalisé par LE Van Tuan Promotion 8, IFI Encadrant Antoine BEUGNARD Département Informatique Ecole National Supérieur des Télécommunications de Bretagne France, Oct 2004 TIEU LUAN MOI download : skknchat@gmail.com Remerciements Je tiens à remercier particulièrement Monsieur Michel SIMATIC, responsable du projet MEGA, de m’avoir accueilli au sein de son équipe. Je tiens à remercier sincèrement Monsieur Charles DURAND, directeur de l’IFI, de m’avoir aidé à préparer le stage. Je tiens à exprimer toute ma sincère reconnaissance à Monsieur Antoine BEUGNARD, enseignant-chercheur au Département Informatique, Ecole National Supérieur de Télé- communication de Bretagne, de m’avoir bien encadré pendant toute la durée de mon stage. Je remercie vivement tous les personnels de l’IFI, qui m’ont aidé pendant mon cursus d’études.
Finalement, un grand merci à tous les personnels du Département Informatique de l’ENST Bretagne, à toutes les membres du projet MEGA, notamment aux stagiaires au laboratoire informatique, ENST Bretagne, qui m’ont porté leur amitié. 1 TIEU LUAN MOI download : skknchat@gmail.com Résumé Notre travail est mené dans le cadre du projet de recherche MEGA (Mobile Multi- PlayEr Game Architecture) qui a pour but de réaliser une infrastructure visant aux dé- veloppeurs des jeux massivement multijoueurs, particulièrement dans les environnements mobiles. Dans les jeux massivement multijoueurs, plus la communication entre les joueurs est efficace, plus de joueurs peuvent participer au jeu. Ainsi, la communication est un des points cruciaux pour le succès d’un jeu.
L’implémentation du modèle de communication Client/Serveur a montré les limitations pour les jeux en ligne, et plus spécialement dans le contexte mobile. Le système Publish/Subscribe augmente le découpage d’espace d’in- teraction entre les participants, ainsi facilite la reconfiguration et l’évolution du système. Il est donc considéré comme une architecture d’intergiciel valable pour les applications fonctionnant en se basant sur les événements (c’est le cas de jeu multijoueur). Il existe dans la littérature des implémentations du Publish/Subscribe pour les jeux multijoueurs, mais restant dans les systèmes statiques plutôt que mobile.
Nous proposons donc d’utiliser ce modèle de communication pour les jeux multijoueurs en réseau mobile. Dans ce rapport, nous présentons le processus de réification d’abstractions de commu- nication du modèle Publish/Subscribe. Nous proposons également deux choix de concep- tion du système sous forme d’un médium. D’autre part, un algorithme pour le support de l’itinérance spécifique à la conception distribuée est discuté.
Mots-clés : Abstractions de communication, architecture et composant, support de la mobilité dans Publish/Subscribe , jeux multijoueurs, service de notification. 2 TIEU LUAN MOI download : skknchat@gmail.com Abstract Our work is undertaken within the framework of the research project MEGA (Mobile MultiplayEr Game Architecture), of which the purpose is to build a middleware aiming to the developers of the game multiplayer, particularly in the mobile environments. In the game multiplayer, more the communication between the players is effective ; more the players can take part in the play. Therefore, the communication is one of the crucial points for the success of the game.
The implementation of the model communi- cation Client/Server showed the limitations for the online game, and more specially in the mobile context. The Publish/Subscribe system increases cutting space of interaction between the participants, hence facilitates the reconfiguration and the evolution of the system. It is thus regarded as a valuable middleware architecture for the event-driven applications (it is the case of the multiplayer game). In the literature, there exist im- plementations of Publish/Subscribe for the game multiplayer, but remains in the static systems rather than mobile.
We thus propose to use this model of communication for the game multiplayer in mobile network. In this report, we present a process of reification of communication abstractions of the model Publish/Subscribe. We also propose two choices of systems design in the form of a medium. In addition, an algorithm for the support of the roaming specific to the distributed design is discussed.
Keywords : Abstractions of Communication, Structures and Composing, Support of Mobility in Publish/Subscribe, Game Multiplayer, Service of Notification. 3 TIEU LUAN MOI download : skknchat@gmail.com Table des matières 1 Introduction 7 1.1 Contexte du stage .2 L’objectif du stage .3 Le Médium et le processus de réification d’Abstractions de Communication 8 1.4 Organisation du document. 9 2 État de l’Art 10 2.1 Les types des jeux en ligne .1 Topologie de réseau .2 Modèle Publish/Subscribe .1 La latence dans les jeux en ligne .2 Synchronisation et consistance .1 Dead reckoning - DR .2 Bucket Synchronization avec DR (BS) et Stop-and-wait Synchronization (SWS) .3 Time Warp Synchronization (TWS) et Trailing State Syn- chronization (TSS) .4 Les plates-formes existantes. 25 3 Environnements mobiles et Modèle de Communication 26 3.
27 4 TIEU LUAN MOI download : skknchat@gmail.com TABLE DES MATIÈRES 5 3.1 Réseau sans fils .2 Architecture des réseaux WLANs .3 Modèle de calculs mobiles .4 Caractéristiques des environnements mobiles .2 Le modèle Publish/Subscribe .1 Les éléments dans un système publish/subscribe .2 Modèle de souscription .1 Modèle basé sur sujet .2 Modèle basé sur contenu .3 Modèle basé sur type .3 Architecture du système .1 Topologie hiérarchique .2 Architecture pair-à-pair .3 Spécification abstrait du médium PublishSubscribeMedium .1 Description informelle et listes des services .2 Diagramme de collaboration du médium Publish/Subscribe .3 Spécification OCL. 42 4 Processus de raffinement 43 4.1 Première étape : introduction des gestionnaires de rôle .2 Deuxième étape : Choix de conception .1 Gestion centralisée des souscriptions .1 Diagramme de collaboration .2 Gestion distribuée des souscription .1 Algorithme de routage .2 Diagramme de collaboration .3 Spécification OCL. 52 5 Conclusion 59 Annexe 1 : Spécification OCL des services après la première étape 60 Annexe 2 : Spécification OCL des services du médium, version centralisée 62 Annexe 3 : Discussion supplémentaire sur la table de routage 64 Bibliographie 66 TIEU LUAN MOI download : skknchat@gmail.com Table des figures 2.1 Topologies de réseaux .2 L’effet de la latence .3 L’exécution du remorquage d’état de synchronisation dans TSS (Quake) .4 L’architecture en couche de Continuum.5 Les composants dans un jeu construit sur TerraPlay .6 Une architecture typique d’un jeu sur TerraPlay .7 La communication dans système TerraPlay .8 Architecture de ButterFly .1 Modèle de calcul mobile .2 Modèle Publish/Subscribe de base .3 découpage de l’espace d’interaction dans un système Publish/Subscribe .4 découpage d’écoulement .5 découpage de temps .6 Architecture hiérachique .7 Architecture pair-à-paire acyclique et pair-à-pair générale .9 Diagramme de collaboration du médium Publish/Subscribe .10 Vue dynamique du médium Publish/Subscribe .1 Introduction des gestionnaires sur le diagramme de collaboration .2 Vue dynamique après l’introduction des gestionnaires .3 Première choix de conception : gestion centralisée .4 Vue dynamique de version centralisée : le cas de service subscribe .5 Vue dynamique de version centralisée : le cas de service publish .6 La relation entre des cuortiers dans la topologie hiérachique et pair-à-pair acyclique .7 La construction de la table de routage en pair-à-pair acyclique .8 La construction de la table de routage en hiérachique .9 Second choix de conception : gestion distribuée .10 Vue dynamique de la version distribuée, le cas de message subscribe. 52 6 TIEU LUAN MOI download : skknchat@gmail.com Chapitre 1 Introduction 1.1 Contexte du stage Aujourd’hui les dispositifs mobiles et sans fils sont omniprésents, avec de nombreuses applications.
Il apparaı̂t rapidement et clairement que le divertissement sera une de ces applications majeures des futurs réseaux mobiles. Néanmoins, la plupart des jeux actuelle- ment offerts sur mobiles sont des jeux monojoueurs. Pour les jeux multijoueurs, il en existe sur internet de nombreux exemples, mais ils restent limités en nombre de joueurs (tout au plus quelques centaines)[46]. Ici, nous nous intéressons au domaine des jeux sur mobile et massivement multijoueurs (plusieurs milliers voire dizaines de milliers de joueurs).
Afin de réduire le travail de développement des jeux multijoueurs, on voudrait être capable de spécifier et réaliser une infrastructure logicielle (un intergiciel), gérant les pro- blèmes concernant les communications réseaux, ainsi que les gestion des données, ou bien le passage à l’échelle, etc. Pour permettre aux développeurs de jeux de ne pas s’écarter de leur métier de base (le jeu). Le projet Mega (commun à CEDRIC-CNAM , l’ENST, l’ENST Bretagne, et France Télécom R&D, l’INT et l’UBS) a pour objectif de définir une telle infrastructure. Ce projet vient de débuter, un état de l’art de l’offre des intergiciels existants (Butterfly, Continuum, Terraplay, etc.) est donc nécessaire, l’idéal étant de s’appuyer sur une norme des notions offertes (inexistante actuellement) [45].2 L’objectif du stage Le travail sera, dans un premier temps, la réalisation d’un état de l’art sur la commu- nication des plateformes intergiciels existantes.
Le stage qui s’en suivra devra mettre en évidence et spécifier des abstractions de communications nécessaires dans ce type d’application. Les spécifications feront apparaı̂tre des parties fonctionnelles qu’on décrira le plus précisément possible (causalité, équité, etc.) et non fonctionnelles (robustesse, efficacité, etc. 7 TIEU LUAN MOI download : skknchat@gmail.3 Le Médium et le processus de réification d’Abstractions de Communication Dans un système distribué, les composants échangent, ou partagent les informations nécessaires à l’aide de composants de communication. Afin de différencier des autres com- posants du système (les composants métiers, ou les composants fonctionnels, etc.), Antoine Beugnard et Eric Cariou [20] appellent ces composants de communication des médiums, dont la définition est : (( Un médium est une composant logiciel de communication ou d’interaction qui réifie1 une abstraction de communication )).
Un médium peut implé- menter une abstraction de communication, un protocole consensus par exemple. Dans la suite du stage, nous allons (( réifier )) des abstractions de communication dans les jeux en réseau mobile selon le processus également proposé par A. Ce processus consiste à transformer des abstractions de communication, à partir de niveau conception le plus abstrait, sous forme de composants logiciels. Quelque soit le niveau de manipulation, il permet de réserver l’unité et la cohérence d’une abstraction d’interaction pendant tout le cycle de développement d’une application.
Le premier pas de ce processus est de déterminer les services que ce composant met- tra à disposition des autres composants ; et aussi les services requis par le médium pour fonctionner. C’est ainsi que la façon dont les entités logicielles communiquent est abs- traite de sorte que (( les détails sont cachés )) et non pas (( la notion est floue et mal définie ))[21]. Dans ce pas, le médium est vu comme un unique entité qui fait partie du système. Le processus de raffinement suivant consiste à transformer cette spécification abs- traite à plusieurs variantes d’implémentation en fonction du contexte d’utilisation, à tous les niveaux du cycle de vie du logiciel, en continuellement respectant le contrat d’usage du médium déterminé lors du niveau le plus abstrait.
Il s’agit là du contrat de la réalisation en terminologie de UML Component. Voici trois étapes du processus de réification des abtractions : – Introduction des gestionnaires de rôle : la première étape du processus de raffinement a pour but de faire apparaı̂tre les types de gestionnaires de rôle qui forment le médium lors de déploiement. – Choix de conception : le résultat de cette étape est une spécification d’implémenta- tion. – Choix de déploiement : il s’agit de définir l’architecture de déploiement des gestion- naires du médium.
A chaque étape de ce processus, des diagrammes de collaboration UML sont utilisés pour décrire l’aspect structurel du médium, mettre en évidence la sémantique et le com- portement dynamique de chacun des services du médium au niveau spécification. Dans la dernière étape, le diagramme de déploiement est employé pour chaque type de déploie- ment défini. Outre, des contraintes OCL, des diagrammes d’états sont utilisés en plus 1 La réification est l’opération de transformation en quelque chose de concret. TIEU LUAN MOI download : skknchat@gmail.
INTRODUCTION 9 pour une spécification plus claire du médium. Dans le cardre du stage, nous ne réaliserons que deux premiers étapes.4 Organisation du document L’état de l’art dans le chapitre 2 donne une vue générale sur la situation actuelle des jeux multijoueurs.