@phdthesis{12764,
  author = {Knut-Helge Vik},
  title = {Group Communication Techniques in Overlay Networks},
  abstract = {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. By doing this, we want 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. We investigated membership management techniques, and evaluated both centralized and distributed approaches through empirical and experimental studies on PlanetLab. We proposed 3 membership management techniques and found that a centralized membership management approach is particularly fast and consistent when there are multiple dynamic groups. We also aimed 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. We evaluated 5 core-node selection algorithms through group communication simulations and experiments on PlanetLab. From these evaluations we found that there exist core-node selection algorithms that are able to find sufficiently well-placed nodes. We considered overlay network multicast as the better option to distribute time-dependent events in groups, and found that centralized graph algorithms are suited to meet the latency requirements put on the overlay constructions and reconfigurations. We evaluated a variety of centralized overlay construction algorithms that aim to build low-latency overlay networks. Through rather comprehensive analyses we identified suitable algorithms in the investigations. Finally, we investigated whether it is possible to obtain accurate all-to-all path latencies to be used by the centralized graph algorithms. For this, we evaluated 2 latency estimation techniques and measured their accuracy by comparing the estimates to all-to-all ping measurements. For the evaluation, we implemented a real-world system and performed group communication experiments on PlanetLab. We 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.},
  year = {2008},
  month = {December},
  publisher = {University of Oslo},
  address = {Unipub, Kristian Ottosens hus, Pb. 33 Blindern, 0313 Oslo},
}