Why Multicast Protocols (Don't) Scale: An Analysis of Multipoint Algorithms for Scalable Group Communication

摘要

With the exponential growth of the Internet, there is audcritical need to design efficient, scalable and robust udprotocols to support the network infrastructure. A new udclass of protocols has emerged to address these challenges,udand these protocols rely on a few key techniques, or udmicro-algorithms, to achieve scalability. By scalability, udwe mean the ability of groups of communicating processesudto grow very large in size. We study the behavior ofudseveral of these fundamental techniques that appear in udmany deployed and emerging Internet standards: udSuppression, Announce-Listen, and Leader Election.ududThese algorithms are based on the principle of efficient multipoint communication, often in combination with periodic messaging. We assume a loosely-coupled communication model, where acknowledged messaging among groups of processes is not required. Thus, processes infer information from the periodic receipt or loss of udmessages from other processes.ududWe present an analysis, validated by simulation, of the performance tradeoffs of each of these techniques. Toward this end, we derive a series of performance metrics that help us to evaluate these algorithms under lossy conditions: expected response time, network usage, memory overhead, consistency attainable, and convergence time. In addition, we study the impact of both correlated anduduncorrelated loss on groups of communicating processes.ududAs a result, this thesis provides insights into the scalability of multicast protocols that rely upon these techniques. We provide a systematic framework for calibrating as well as predicting protocol behavior over a range of operating conditions. In the process, weudestablish a general methodology for the analysis of these and other scalability techniques. Finally, we explore a theory of composition; if we understand the behavior of these micro-algorithms, then we can bound analytically the performance of the more complex algorithms that rely upon them.