| Understanding how to build self-organizing systems is paramount for coping efficiently with the increased scale and complexity of our computing systems. Existing Grid infrastructure deployments provide a useful source of world requirements for such an exploration and can be used to evaluate solutions in realistic settings.; Multicast communication primitives have broad utility as building blocks for distributed applications. However, creating and maintaining the structures that support multicast primitives is challenging, particularly when participating resources are volatile and their characteristics are variable. Thus, multicast communication represents a good challenge problem for designing and experimenting with self-organization techniques.; We describe and evaluate UMM: a multi-source multicast system based on an unstructured overlay and a novel approach to extracting source-specific multicast trees. Experimental and analytical evaluations show that our solution achieves low communication overhead and efficient network usage compared to alternative solutions. In addition to these performance-related characteristics UMM displays four important properties. First, UMM is self-organizing: independent node decisions made based on partial, local information result in desired global system behavior. Second, UMM has the advantage of low complexity. UMM relies on soft-state and passive data collection to adapt to participating end-host and physical network dynamics. We assert that resulting low complexity is a highly desirable property of distributed, large-scale systems. Third, the state stored at each UMM node scales with the number of sources and is independent of the number of passive participants. Finally, UMM adapts to changes in underlying network topology characteristics, performs well under significant levels of churn, and recovers quickly from significant failures in the set of participating end-nodes with minimal disruption to the multicast service offered.; To demonstrate UMM's practicality when implementing higher level services, we also evaluate it in an application context. We design and evaluate a replica location service that integrates three techniques: UMM's flat overlay to obtain genuine decentralization and resilience when facing network and node failures, probabilistic representation of replica location information to achieve important space and bandwidth savings, and soft-state protocols to build a robust, loosely-coupled system. |
