PhD thesis abstracts

• Cheng Wei
• Matteo Varvello
• Sonja Bergsträsser

Cheng Wei

Streaming of High-Resolution Progressive Meshes over the Internet

High-resolution 3D meshes are increasingly available in networked applications, such as digital museum, online game, and virtual reality. The amount of data constituting a high-resolution 3D mesh can be huge, leading to long downloading time. To reduce the waiting time of users, a common technique for remote viewing is progressive streaming, which allows a low-resolution version of the mesh to be transmitted and rendered with low latency. The quality of the transmitted mesh is incrementally improved by continuously transmitting the refinement information.

Progressive mesh is commonly used to support progressive streaming. Streaming of high-resolution progressive meshes is considerably different to video streaming, which has been extensively studied. Frames of a video are usually sent following the time order. Vertex splits of a progressive mesh, however, can be sent in various orders. New research problems arise due to the flexibility in sending order of vertex splits. In this thesis, three such problems are addressed.

First, the progressive coding of meshes introduces dependencies among the vertex splits, and the descendants cannot be decoded before their ancestors are all decoded. Therefore, when a progressive mesh is transmitted over a lossy network, a packet loss will delay the decoding of any following vertex split that depends on a vertex split in this lost packet. Hence, the effect of dependency needs to be considered in choosing the sending order of vertex splits. In this thesis, an analytical model is proposed to quantitatively analyze the effects of dependency by modeling the distribution of decoding time of each vertex split as a function of mesh properties and network parameters. Consequently, different sending orders can be efficiently evaluated without simulations, and this model can help in developing a sending strategy to improve the quality curve during transmission. The accuracy of the analytical model proposed in this thesis is validated under a variety of network conditions, including bursty losses, fluctuating RTT, and varying sending rate. The values predicted from our model match the measured value reasonably well in all cases except when losses are too bursty.

Second, to improve the quality of rendered image in the receiver side quickly, the viewpoint of the user can be considered in deciding the sending order. In existing solutions of view-dependent streaming, the sender decides the sending order. The sender needs to maintain the rendering state of each receiver to avoid sending duplicate data. Due to the stateful design, the sender-driven approach cannot be easily extended to support many receivers with caching proxy and peer-to-peer (P2P) system, two common solutions to scalability. In this thesis, a receiver-driven protocol is proposed to improve the scalability. In this protocol, the receiver decides the sending order and explicitly requests the vertex splits, while the sender simply sends the data requested. The sending order is computed at the receiver by estimating the visibility and visual contributions of the refinements. The sender becomes stateless, so caching proxy and P2P streaming systems can be applied to improve the scalability without adding more servers.

Third, based on the receiver-driven protocol we proposed, P2P techniques are applied to view-dependent progressive mesh streaming in this thesis. In the implementation of P2P mesh streaming system, two issues are considered: how to partition a progressive mesh into chunks and how to lookup the provider of a chunk. For the latter issue, we investigated two solutions, which trade off server overhead and response time. The first uses a simple centralized lookup service, while the second organizes peers into groups according to the hierarchical structure of the progressive mesh to take advantage of access pattern. We have implemented a prototype and test its performance with synthetic traces we generated based on real traces logged from 37 users. Simulation results show that our proposed systems are robust under high churn rate. It reduces the server overhead by more than 90%, keeps control overhead and average response time low.

Matteo Varvello

A Peer-to-Peer Architecture for Networked Virtual Environments

A Networked Virtual Environment (NVE) is a synthetic world where human-controlled avatars can interact. Multiplayer on-line games such as Quake and World of Warcraft are the most popular applications for NVEs. In early 2003, Second Life (SL), a NVE where avatars can invent a new social life, was launched. The main innovative feature of SL is user-generated content: avatars participate in the development of the virtual environment by creating objects such as cars, trees, and buildings. SL rapidly became the most popular NVE, reaching more than 16 million registered users in September 2009.

The state of the art for NVEs design is a Client/Server architecture where multiple servers maintain the state of the virtual world and distribute it to the users. This architecture is very expensive as large amount of servers need to be deployed, operated and maintained. Moreover, scalability is an issue. These drawbacks motivate alternative designs such as Peer-to-Peer (P2P). Ideally, a P2P virtual world can scale with the number of its users as each user dedicates some of its resources (storage, CPU, bandwidth) to the management of the virtual world. Moreover, P2P can dramatically cut server and network cost for the virtual world provider.

The contribution of the thesis is threefold. First, due to the lack of publicly available data about NVEs such as avatar movement patterns or object distribution, we perform an extensive analysis of SL. We deploy a crawler and a player application and monitor objects, avatars, user Quality of Experience and servers performance in the public part of SL over one month.

Second, we design and build a distributed objectmanagement for user-generated NVEs. We first integrate this distributed object management on the top of KAD, the P2P network that supports millions of eMule users, and perform large-scale experiments. Then, we propose Walkad, a structured P2P network designed to manage user-generated objects in P2P-based NVEs.

Third, we investigate the feasibility of a distributed avatar management using the Delaunay triangulation. To start with, we evaluate the performance of the Delaunay triangulation via realistic experiments performed in SL using a modified client we developed. Then, we design two optimizations for Delaunay triangulation: (1) a clustering algorithm to efficiently handle large avatar groups, and (2) a secured extension to the Delaunay triangulation that leverages the social component of NVEs.

Sonja Bergsträsser

Virtual Context Based Services - Definition, Description and Utilization of Context in Virtual Worlds

The importance of virtual worlds is steadily growing both in general as well as from an economical perspective and they register increasing member counts. The virtual worlds observed in research most often nowadays are the very popular gaming worlds of Multiplayer Online Games (MOGs). They are among the most popular collaborative applications and are often referred to as cutting edge in cooperative online worlds. In virtual worlds of Multiplayer Online Games, millions of gamers from all over the world meet and establish social networks. Multiplayer Online Games are the core of a complex, networked, technical and social structure with interaction being a fundamental aspect. This includes cooperation, community, exchange and learning with specifically informal learning being of great importance. Mixed collaborative spaces, as they are provided by Multiplayer Online Games, are also suited to provide a common platform for other areas like interdisciplinary research.

The interaction of gamers is central in Multiplayer Online Games. Cooperation between gamers evolves and gamers create groups. Gamers and especially groups of gamers interact not only inside the virtual game worlds, but also outside of the game, in the community formed around a game.

This thesis is based on the observation that different information and functions are used in addition to the game. This happens because corresponding information and functions are not available inside the game and thus gamers need additional services. Around the game, a game environment is formed which is maintained by the community of the game, including different applications and artefacts. For example, the organization of groups partly takes place outside of the game, because most games do not support this sufficiently.

Services in the game environment are provided by different independent internet applications. In order to use such a service, switching from the game to the respective application is required, causing an interruption of the game experience. A comprehensive support of gamers inside virtual worlds contributes to an improvement of the game experience. Thus the goal of this thesis is to make a comprehensive user support in virtual worlds possible. This support will be enabled by the integration of external services into virtual worlds.

To achieve this goal, we conduct a comprehensive analysis of virtual worlds. Based on the findings of this analysis we transfer the concept of context, as it is known in the area of context aware services, to virtual worlds and introduce and define the concept of virtual context. Other results of our analysis include the development of a generic interaction model for virtual worlds and the definition of virtual context information based on virtual parameters. In order to capture virtual context and make it technically usable, we develop a description language for virtual context. Based on the findings of the analysis we introduce and define the concept of virtual context based services that allows for a situation-dependent user support in virtual worlds.

The connection and integration of the external services into virtual worlds is enabled through the realisation of an information exchange between virtual worlds and other internet applications. This information exchange is based on the concept of virtual context based services and enables the controlled forwarding of information from the virtual world to applications in the game environment. This information exchange includes the acquisition of virtual context information, its distribution to external services in use, as well as the integration of the resulting service data into the virtual world.

We conceptually develop, implement and evaluate a middleware-architecture for the provision of context based services and the realisation of the information exchange. The middleware comprises of components for the capturing of context information in virtual worlds, for processing and dissemination of context and for the provision of external services in virtual worlds.

The evaluation of the implemented middleware shows that the developed concept of virtual context based services is valid and that the developed middleware is a successful implementation of an architecture for the realisation of an information exchange based on context based services. With the definition of virtual context, its description and its utilization, based on the concept of virtual context based services, this thesis lays the foundations for situation-dependent user support in virtual worlds and the integration of external services into virtual worlds.