Multi-objective optimization of multicast overlays for collaborative applications

Current real-time collaborative application implementations use dedicated infrastructure to carry out all communication and synchronization activities. Specifically, they require all end nodes to communicate directly with and through the central server. In this paper, we investigate scenarios in which the most resource intensive functionality of continuous communication among collaborators to disseminate changes is decentralized, utilizing the end users themselves as relays. We observe that communication characteristics of real-time collaboration makes use of existing multicast mechanisms unsuitable. As collaborative editing sessions are typically long and repeated, it is possible to gather and leverage node behavior (their instabilities and frequency of sending updates) and communication links (latencies and average costs). Several criteria to determine the quality of a multicast tree can be identified: cost, latency and instability. In this paper, we analyze the complexity of the problem of finding optimal communication topologies, and propose approximate algorithms to optimize the same. We also consider the multiobjective problem in which we search for a topology that provides good trade-off between these sometimes conflicting measures. Validation of our proposed algorithms on numerous graphs shows that it is important to consider the multiobjective problem, as optimal solutions for one performance measure can be far from optimal for the other metrics. Finally, we briefly present an implementation of a communication library that uses the proposed algorithms to periodically adjust the dissemination tree. (C) 2010 Elsevier B.V. All rights reserved.