PhD thesis abstracts

PhD thesis abstracts

• Behnoosh Hariri
• Dewan Tanvir Ahmed
• Eva Hörster
• Jens Brandt
• Sebastien Mondet

Behnoosh Hariri

Overlay Routing Architectures for Massively Multiuser Virtual Environments

Massively Multiuser Virtual Environments (MMVE) are network applications that simulate the experience of real-time interaction among multiple users distributed all over the internet. In order to share the common sense of time and place, multiple entities interacting in the shared virtual environment must be aware of the modifications or interactions within the shared environment. This is achieved through the distribution of update messages. As the number of users and entities increases, there is a considerable increase in the amount of update messages exchanged among the users and entities. Supporting the large of update messages, especially in massive environments, is one of the most important challenges in the design of MMVEs. The use of a distributed architecture allowing users to handle the traffic among each other in a peer to peer (P2P) fashion is one solution to this problem. However, such solution must in turn deal with a variety of challenges related to the non-centralized nature of the protocol.

This dissertation proposes a number of distributed architectures for MMVEs in an attempt to provide an efficient infrastructure for update message distribution. Simulation has also been used to demonstrate the functionality and performance of the proposed approaches. Contributions include:

• Analytical modeling of the update exchange problem in MMVEs
• Proposing new architectures for update message exchange in MMVEs dealing with the following two challenges:
  • Distributed architecture
  • Latency aware message delivery
• Designing the following architectures for distributed MMVE application where no centralized control/data switching point is required:
  • DHT architecture where exchange of delay-sensitive-data is supported.
  • Hilbert Curve architecture based on mapping and routing over 3D Hilbert Curve.
  • KD Tree architecture based on mapping over Z curve and routing based on KD tree.
  • Geometric Routing architecture inspired by the concept of geometric routing in wireless networks, and adapting it to the wired networks and MMVE specific requirements.
• Designing resilient algorithms in the presence of user churn and mobility
• Application of the concept of fast search in multi-dimensional databases to latency-aware routing in distributed networks.

Dewan Tanvir Ahmed

Architectural Challenges and Solutions for Peer-to-Peer Massively Multiplayer Online Games

Massively Multiplayer Online Games (MMOG), now supporting millions of simultaneous participants on a regular basis, have become a significant contributor in human-to-human communications. While originally designed for games, they have now moved into serious realms of socialization, business, commerce, scientific experimentation, and others. As more and more people participate in these massive environments, the underlying infrastructure is starting to exhibit shortcomings that limit the progress, practicality, and applicability of MMOGs. This thesis explores various architectural challenges inherent in MMOGs and offers effective solutions in the context of a hybrid model. The key objective of this hybrid model, realized in a Massively Multiuser VIrtual Simulation Architecture (MM-VISA), is to form a stable and scalable collaboration platform that economically combines the resources of both servers and player peers, incorporating the advantages of a centralized architecture and a scalable Peer-to-Peer distributed system, which in turn leads to improved support for the participating masses.

Synchronous communication among massive number of users in an MMOG is a prime concern, and difficult and/or expensive to support. This massiveness causes challenges that cannot be solved with conventional techniques used in traditional collaborative environments. Massive number of players' frequent and random movements in the virtual environment and zone-switching can break synchronous communication and cause strain on the underlying system, networking, and service infrastructure. To alleviate such problems, this thesis proposes a model consisting of interest-driven zone crossing, dynamic shared regions, clustering of players based on their attributes, multilevel multiphase load-balancing with several plug-able solutions, hybrid routing based on a combination of centralized and Peer-to-Peer (P2P) networking, and interest-management techniques considering dynamics of the area of interest. The model is shown to significantly improves overall system performance and enhances infrastructure stability in terms of load, network overlay, and other performance characteristics.

In MM-VISA, a set of master nodes regulate the operation of the MMOG, while each individual master also provides overlay services with the active participation of the players in its zone. In that sense, the system is hybrid as it combines the benefits of both centralized and distributed systems. In this model, most of the visibility issues and game functionalities are solved by the local ALM structure and through the master, who is also a member of the ALM tree. In addition, the master can learn the state of other zones through the exchange of explicit messages with other masters when needed. The thesis also makes the following contributions in the context of its proposed hybrid architecture:

• Clustering of Players: within the same zone, players of different type are grouped together in order to stabilize the P2P trees inside that zone.

• Message Overhead Reduction: bandwidth and processing is reduced by eliminating message delivery between players who, even though they are in the same group, are not within each other's visibility radius.

• Zone Crossing: connection/disconnection rate between a player and multiple masters is stabilized when the player crosses a given zone boundary back and forth repeatedly, which can happen during a battle in repeated shoot-and-run, return and shoot-and-run, ...

• Visibility: a player to see inside another zone when the player's visibility crosses into that zone.

• Seamless Player Handoff: how two masters should hand of a player from one master to the other without the player noticing any discontinuity or losing any updates.

• Expedited State Sharing: to allow for faster message propagation in the system.

• Load Balancing: three load-balancing techniques are presented - two for uniform and one for non-uniform zonal MMOGs.

Eva Hörster

Topic Models for Image Retrieval on Large-Scale Databases

With the explosion of the number of images in personal and on-line collections, efficient techniques for navigating, indexing, labeling and searching images become more and more important. In this work we will rely on the image content as the main source of information to retrieve images. We study the representation of images by topic models in its various aspects and extend the current models. Starting from a bag-of-visual-words image description based on local image features, images representations are learned in an unsupervised fashion and each image is modeled as a mixture of topics/object parts depicted in the image. Thus topic models allow us to automatically extract high-level image content descriptions which in turn can be used to find similar images. Further, the typically low-dimensional topic-model-based representation enables efficient and fast search, especially in very large databases.

In this thesis we present a complete image retrieval system based on topic models and evaluate the suitability of different types of topic models for the task of large-scale retrieval on real-world databases. Different similarity measure are evaluated in a retrieval-by-example task.

Next, we focus on the incorporation of different types of local image features in the topic models. For this, we first evaluate which types of feature detectors and descriptors are appropriate to model the images, then we propose and explore models that fuse multiple types of local features. All basic topic models require the quantization of the otherwise high-dimensional continuous local feature vectors into a finite, discrete vocabulary to enable the bag-of-words image representation the topic models are built on. As it is not clear how to optimally quantize the high-dimensional features, we introduce different extensions to a basic topic model which model the visual vocabulary continuously, making the quantization step obsolete.

On-line image repositories of the Web 2.0 often store additional information about the images besides their pixel values, called metadata, such as associated tags, date of creation, ownership and camera parameters. In this work we also investigate how to include such cues in our retrieval system. We present work in progress on (hierarchical) models which fuse features from multiple modalities.

Finally, we present an approach to find the most relevant images, i.e., very representative images, in a large web-scale collection given a query term. Our unsupervised approach ranks highest the image whose image content and its various metadata types gives us the highest probability according to a the model we automatically build for this tag.

Jens Brandt

Multidimensional Transcoding for Adaptive Video Streaming

The prominence of digital video on the Internet is rising constantly. Faster Internet connections and more powerful devices make video streaming over the Internet more and more popular. With mobile devices, however, the usability of digital videos that are streamed over a wireless network connection is still limited by the available resources. Mobile devices are often not capable of receiving and decoding high quality video streams from the Internet because of their limited resources as well as due to the limitations of a wireless network connection. The presentation, for instance, of a video stream with 1920x1080 pixels on a screen with a resolution of only 320x240 pixels is not possible without a high amount of processing power at the receiving device. The transmission of such a high quality video stream over a wireless link may additionally consume a large part of the available network capacity, which then may interfere active network connections of other devices. A limited network capacity may additionally prevent the device from decoding and displaying the video stream at all. One solution of these problems is to perform an adaptation of the video stream to the requirements of mobile devices during the transmission of the stream to the client.

In this work we investigated different protocols and mechanisms that allow for dynamic adaptation of video streams to the requirements of mobile devices. Therefore, we developed a multimedia gateway system that provides video adaptation during the transmission of a stream to the client. This gateway system is working completely transparent for the user because the gateway can be discovered automatically by the client. For the process of video adaptation itself we concentrate on compressed domain video transcoding mechanisms that avoid a time-consuming complete decoding and encoding of the video stream.

An adaptation of solely the spatial resolution of the stream is typically not sufficient to meet the requirements of the requesting device. On the contrary, the spatial and the detail resolution may also need to be updated. Existing approaches, however, are mainly restricted to the adaptation of only one of these aspects. In this work we investigated the impact of different adaptation dimensions on the visual quality of the adapted stream. Based on these results, we were able to give a clear recommendation for a multidimensional adaptation of video streams. To be able to perform such an adaptation of video streams, we developed a novel transcoding architecture that facilitates a smart combination of existing one-dimensional transcoding mechanisms. By the use of this video transcoding approach at the proposed gateway system, individual and dynamic video adaptation services can be provided to mobile devices.

Sebastien Mondet

Adaptive Modeling and Distribution of Large Natural Scenes

This thesis deals with the modeling and the interactive streaming of large natural 3D scenes. We aim at providing techniques to allow the remote walkthrough of users in a natural 3D scene ensuring botanical coherency and interactivity.

First, we provide a compact and progressive representation for botanically realistic plant models. The topological structure and the geometry of the plants are represented by generalized cylinders. We provide a multiresolution compression scheme, based on standardization and instantiation, on difference-based decorrelation, and on entropy coding.

Then, we study efficient transmission of these 3D objects. The proposed packetization scheme works for any multiresolution 3D representation. We validate our packetization scheme with extensive experiments over a WAN (Wide Area Network), with and without congestion control (Datagram Congestion Control Protocol).

Finally, we address issues on streaming at the scene-level. We optimize the viewpoint culling requests on server-side by providing an adapted datastructure and we prepare the ground for our further work on scalability and deployment of distributed 3D streaming systems.

The thesis was part of the NatSim French research project (Natural Simulations) and benefited from a collaboration with the National University of Singapore (Cheng Wei and prof. Wei Tsang Ooi).