Knut-Helge Vik

Group Communication Techniques in Overlay Networks

Supervisor(s) and Committee member(s): Paal Halvorsen (supervisor), Carsten Griwodz (supervisor), Roger Zimmermann (opponent), Utz Roedig (opponent)


One type of Internet services that have recently gained much attention are services that enable people around the world to communicate in real-time. Such services of real-time interaction are offered by applications most commonly referred to as distributed interactive applications. Concrete examples of distributed interactive applications are multiplayer online games, audio/video conferencing, and many virtual-reality applications linked to education, entertainment, military, etc. A time-dependent requirement generally applies to all distributed interactive applications that aim to support real-time interaction, and is usually in terms of a few hundred milliseconds. The latency requirements are manifested in terms of event-distribution, group membership management, group dynamics, etc., far exceeding the requirements of many other applications.

One general focal point in this thesis is to enable scalable group communication for managing dynamic groups of clients that interact in real-time. This is meant to enable people around the world to dynamically join networks of participants and interact with them in real-time. The main contributions of the thesis are a number of investigations of a wide variety of group communication techniques. The results from the investigations form a foundation to identify the techniques that are particularly suitable for distributed interactive applications.

This thesis investigates membership management techniques, and evaluates both centralized and distributed approaches through empirical and experimental studies on PlanetLab. It proposes 3 membership management techniques and finds that a centralized membership management approach is particularly fast and consistent when there are multiple dynamic groups.

The thesis aims to identify well-placed nodes in the application network that yield low pair-wise latencies to groups of clients. These may, for example, be used for membership managing tasks. It evaluates 5 core-node selection algorithms through group communication simulations and experiments on PlanetLab. From these evaluations it is found that core-node selection algorithms exist that are able to find sufficiently well-placed nodes.

The thesis considers overlay network multicast as the better option to distribute time-dependent events in groups, and finds that centralized graph algorithms are suited to meet the latency requirements put on the overlay constructions and reconfigurations. It evaluates a variety of centralized overlay construction algorithms that aim to build low-latency overlay networks.

Finally, the thesis investigates whether it is possible to obtain accurate all-to-all path latencies to be used by the centralized graph algorithms. For this, 2 latency estimation techniques are evaluated and their accuracy measured by comparing the estimates to all-to-all ping measurements. A real-world system was implemented to perform group communication experiments on PlanetLab. It was found that when latency estimates are used by core-node selection algorithms and overlay construction algorithms, they are sufficiently accurate such that the graph algorithms still find solutions that are close to the real-world.



Increasing heterogeneity of end-systems and the increasing speed of consumer access networks make large scale distributed multimedia applications such as streaming, gaming and Internet telephony increasingly popular. Higher bandwidth, interactivity and more symmetrical traffic patterns change the challenges that lie in developing and operating an affordable infrastructure. Users' demands for quality of service remain, as does the lack of end-to-end resource reservation. RELAY investigates system-level approaches that provide quantifiable better support for a class of distributed systems in spite of the lack of control over the infrastructure, at a predictable cost.

RELAY designs, implements and evaluates mechanisms and tools to improve resource utilization, increase throughput, reduce/hide latency and support soft QoS. One of RELAY's main goals is to integrate and combine mechanisms to get more scalable, less resource demanding, high performance systems for time-dependent large-scale distributed multimedia systems. RELAY considers architectural, kernel and protocol support for reduced resource consumption in servers and intermediate systems, algorithms for the allocation of data and functions to servers and intermediate systems, and investigate combinations of performance-enhancing mechanisms such that they do not counteract each other.

Bookmark the permalink.