Project Topics
Get Complete Project Material File(s) Now! »
Massively multiplayer online games
Maze War [60] in 1974 connected for the rst time {through ARPANET{ several players across the US in a unique virtual space. It is the game that introduced several concepts at the base of today’s virtual worlds, avatar, rst-person 3D perspective, position on a map, multi-player network game, various interactions between players (chat, shooting).
Nowadays such games are called Massively Multiplayer Online First Person Shooters (MMOFPS) and are large-scale virtual battlegrounds. Avatars have fast and precise movements and interact often. There aren’t many objects, most of them are weapons and items owned by avatars. Initially, designed to support only up to 64 players together, games as Quake [31] and Counter Strike [13] were not classi ed as massively multiplayer. Recently, they have been used as research tools for designing scalability [46, 88]. Tanks and robots uses Pikko Server to attain the world record of 1,000 players together [38].
Massively Multiplayer Online Role Playing Games, or MMORPGs, such as World of Warcraft [37], o er a rich environment, with detailed avatar customization, complex modi able objects and non-player characters (NPCs). Interactions involve avatars, NPCs, and objects in the environment, implying high requirements to simulate the world.
Ultima Online [34] was the rst MMORPG to o er a persistent world and to reach the 100,000 subscriptions, exceeding by far any game that went before it [34]. However, the number of players together in the same space has the same limitations.
Metaverses
Taking inspiration in the ’80s science ction literature, multi-user virtual worlds were designed to be fully customizable, highly interactive environments. Second Life [32] is the most successful virtual world with a million active users logging in and inhabiting the world every month [104]. It is mostly used for social activities, thus avatar-to-avatar interactions are prevalent and the scalability is of utmost importance.
In this area scalability is a well identi ed problem [77, 110]. For Second Life, research has been conducted to understand avatar behavior [88, 110], and several solutions to scale have been proposed [90, 91, 107].
OpenSimulator [29] is a free and open-source software to develop virtual worlds com-patible with Second Life clients, which attracts scalability research [87, 90, 91]. By distributing the world state among the users in a peer-to-peer architecture, Solipsis [83] is the rst virtual world that can be theoretically inhabited by an unlimited number of participants.
Mirror and hybrid worlds
Back in 1993, before the commoditization of spherical cameras, rotating lasers for 3D scanning, antennas to map the Wi hotspots, and other sensors to map the physical world, the term mirror world was coined [74]. It refers to an accurate representation of the real world in digital form. Google Street View [35], Google Earth [17], and Bing Maps [10] are among the generally known examples.
So, as these copies of the real word resemble it more and more, they are still empty, we do not see people roaming in the streets, or other users looking at the same places we are. Prototypes [61, dCDKT14] show the feasibility of a hybrid world using augmented reality and virtual spaces. Indeed, 7 billion potential users in the same virtual world exceeds by some orders of magnitude the state-of-the-art.
Scalability beyond virtual worlds
Our contribution presented in this thesis is targeted at scaling virtual worlds, and we present applications for games (Chapter 6), metaverses (Chapter 7) and hybrid worlds (Chapter 8). But the applicative scenarios that can bene t from this research is broader than this.
Location information management is a widely encountered problem in computing sys-tems. Retrieving which objects are at a speci c location or who is nearby is still a challenging issue, especially when dealing with huge amounts of entities and frequent updates. Applications include: Geographic Information System (GIS) [30] are used to nd who or what is at a speci c location. Also, they need identifying the nearest points of interest or moni-toring various geographically identi ed targets. For instance, a tourist information system may allow users to search for attractions within their vicinity.
Car eet management, for companies to know and optimize at any moment how their resources are spatially allocated. In search for a taxi for instance, the system must provide preferably the nearest one.
Local advertising and georecommendation [55]: A typical scenario is sending ads to potential customers in the vicinity of a local commerce. For instance, a restaurant with 20 meals left at 1PM decides to send 50%-o coupons by text message to phone users nearby.
Location (geo) based social gaming such as Google’s Ingress [21]. Other online and social activities are outdoor geocaching [15] or proximity dating, see Tinder [33].
Social mixed reality [18, dCDKT14]: In virtual worlds avatars are mobile objects and spatial queries are issued to determine which avatars and objects are relevant for a given user. In the case of mixed {a.k.a. hybrid{ reality, the system must represent uniformly, virtual and real objects.
All these applications need to deal with large numbers of moving objects in a timely manner. In particular, for some applications, meaningful time intervals are minutes { i.e., advertising{ while for others, events might occur every few milliseconds {see virtual worlds and social mixed reality. Also, in some scenarios the number of moving objects does not exceed a few hundreds while in others millions are expected.
A scalable application needs to take into consideration the trade-o between the number of moving objects and the frequency of their update in order to provide an adaptive solution when needed. To summarize, solutions for the scalability of virtual worlds have applications in many areas dealing with numerous mobile objects with frequent position updates. They all have to provide nearby information or to query data spatially located.
Performance evaluation of centralized solutions
Before studying state-of-the-art solutions for scalability, let’s rst analyze how well cur-rent implementations perform on one machine. In this section we describe our tests and performance on major implementations for Delaunay triangulations and R-trees.
Virtual worlds demand high responsiveness. To simulate natural human-to-human in-teraction, occurring events must be propagated timely to the users. Also, any request must be satis ed with the most up-to-date results and in a timely manner, before the state changes make the answer obsolete.
The state of a virtual world is changed mainly by the avatars that populate it. Out of these changes, the majority are position updates [57]. Therefore, the performance of each system depends on the frequency with which these updates occur. Our evaluations focus on the trade-o between frequency of updates and the number of indexed vertices.
We nally claim that a scalable solution must handle this trade-o and provide for any size of the index and any frequency of position updates. Our own contribution, Kiwano and Kwery, will be shown scalable under this requirement {we will show they are capable to dynamically self-adapt to any con guration number of avatars versus frequency of update.
These following measurements anticipate the limits of current virtual worlds and other usages. We analyze the results for some of them.
Additionally, they provide a ground result of the scalability performance of our dis-tributed solutions. As we will see in the next part of the thesis, we are actually able to provide solutions to distribute the computation for Delaunay triangulations and R-trees, with a self-adaptive load balancing. Indeed, in a distributed system a machine cannot exceed these evaluated values. Our next step is to reduce the overhead required by the load balancing procedures of the distributed data structure, such that these limits are closely approached. This subject is covered in Chapter 4 for Delaunay triangulations and in Chapter 5 for R-trees.
Tree overlays for range queries and publish-subscribe
Range queries and publish-subscribe are largely interreducible [44]. Updates correspond to publications. The di erence between queries and subscriptions is that queries are discarded as soon as they are answered while subscriptions mean that all future noti-cations will be received until the subscription is cancelled. To resolve subscriptions with an index {distributed or not{ nodes must keep the incoming queries and check if new updates match any subscription. This procedure can be launched at every new update or periodically, for the accumulated updates. In Chapter 5.6.2 we describe how we implement a publish-subscribe system for Kwery, a hierarchical distributed index with zones that reshape dynamically in order to follow the distribution of events.
Range queries Spatial indexes are used to optimize spatial queries since regular in-dexes do not e ciently handle topology issues such as proximity or containment. Data distribution commonly uses R-trees [78] or Quadtrees [72]. Many of the following exam-ples were combined with peer-to-peer overlays to build scalable distributed data struc-tures [76]. They were intended to provide:
Nodes are dynamically added to the system when needed and data is dynamically (re)distributed; For that reason, a query may land on the incorrect node and then it will be forwarded to the correct one which will respond and update the user information.
Table of contents :
Contents
List of Figures
1 Introduction
1.1 Problem statement
1.2 Contributions
1.3 Outline of the thesis
1.4 List of international publications
I State of the Art
2 Background
2.1 A taxonomy of worlds
2.1.1 Massively multiplayer online games
2.1.2 Metaverses
2.1.3 Mirror and hybrid worlds
2.2 The scalability problem
2.2.1 Context
2.2.2 Avatar mobility
2.2.3 Chalenges
2.2.4 Scalability beyond virtual worlds
2.3 Notions
2.3.1 Delaunay triangulations / graphs
2.3.2 Trees and hierarchies
3 State of the Art
3.1 Performance evaluation of centralized solutions
3.1.1 Experiments and settings
3.1.2 Delaunay triangulations
3.1.3 R-trees
3.1.4 Limits of the data structures
3.2 Interest management
3.2.1 Region-based publish-subscribe
3.2.2 Aura-nimbus
3.2.3 Summary
3.3 Data distribution
3.3.1 Shards
3.3.2 Zones
3.3.3 Tree overlays for range queries and publish-subscribe
3.3.4 Delaunay triangulations
3.3.5 Summary
3.4 Architectures
3.4.1 Server based
3.4.2 Peer-to-peer
3.4.3 Hybrid
3.4.4 Towards cloud infrastructures
3.5 Summary
II Contribution: Scalability for Virtual Worlds
4 Kiwano: Avatar Scalability and Neighborhood Updates
4.1 Avatar interest management
4.1.1 Neighborhood relation
4.1.2 Kth power of Delaunay graphs
4.2 Data structure
4.2.1 Distributed DelaunayK overlay
4.2.2 Maintaining a dynamic self-adaptive data structure
4.3 Algorithms
4.3.1 Incremental update
4.3.2 Periodical update
4.4 Architecture
4.4.1 Architectural transparency with Kiwano
4.4.2 Beta release and public API
4.5 Performance evaluation
4.5.1 Pink Banana avatar mobility model and simulator
4.5.2 Settings
4.5.3 Results
4.6 Summary
5 Kwery: Spatial Containment Queries for Moving Objects
5.1 Spatial queries in virtual environments
5.1.1 Spatial queries on moving objects
5.1.2 Interest management on dynamic objects
5.2 Distributed data structure
5.2.1 Spatial index
5.2.2 Distributed data structure
5.3 Algorithms
5.3.1 External requests
5.3.2 Internal dynamic self-organization
5.4 Architecture
5.4.1 A transparent, contiguous virtual space
5.4.2 Object management with Kwery
5.5 Evaluation
5.5.1 Setup
5.5.2 Parameters
5.5.3 Single node’s load
5.5.4 Coordinator’s load
5.5.5 Overlap rate and query performance
5.5.6 Overlap under increasing load
5.6 Extensions
5.6.1 A hierarchical architecture
5.6.2 Implementing a publish-subscribe system with Kwery
5.6.3 Minimal requirements for a distributed data structure
5.7 Summary
III Architecture and Applications
6 MMOG Case Study: Manycraft
6.1 Minecraft as research challenge
6.2 Minecraft architectural aspects
6.2.1 The server
6.2.2 The client
6.2.3 The protocol
6.2.4 Modes and their scalability requirements
6.3 Evaluating Minecraft scalability
6.3.1 Experimental setup
6.3.2 Measurements
6.3.3 Conclusion
6.4 Architecture
6.4.1 How it works
6.4.2 Manycraft Node
6.4.3 Bridging all nodes over Kiwano
6.4.4 Manycraft scalability and performance
6.5 Implementation and demo
6.6 Summary
7 Virtual World Case Study: OneSim
7.1 (Second) Life is not a game
7.2 Scalability study using OpenSim
7.2.1 Protocol messages
7.2.2 The Hypergrid, a scalable web of regions
7.3 OneSim
7.3.1 Proposed architecture
7.3.2 Implementation with Kiwano
7.3.3 Other shared data
7.3.4 Scalability and limitations
7.4 Summary
8 Interoperability for a Shared Hybrid Reality: HybridEarth
8.1 HybridEarth: Mixed reality at planet scale
8.1.1 A Mirror World based on Street View
8.1.2 Augmented Reality and Geolocation
8.2 Interoperability for virtual worlds
8.2.1 HybridEarth scalability
8.2.2 Eciency and interoperability for all virtual worlds
8.3 Summary
9 A 3 Point Perspective
9.1 Synthesis of the contribution
9.2 Future work
9.3 General perspectives
Bibliography
