CaltechAUTHORS
  A Caltech Library Service

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

Schooler, Eve M. (2000) Why Multicast Protocols (Don't) Scale: An Analysis of Multipoint Algorithms for Scalable Group Communication. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechCSTR:2001.003

[img]
Preview
PDF - Submitted Version
See Usage Policy.

1825Kb
[img] TeX (TeX bibliography (for 09bibliography.pdf)) - Submitted Version
See Usage Policy.

13Kb
[img]
Preview
Postscript - Submitted Version
See Usage Policy.

3133Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:2001.003

Abstract

With the exponential growth of the Internet, there is a critical need to design efficient, scalable and robust protocols to support the network infrastructure. A new class of protocols has emerged to address these challenges, and these protocols rely on a few key techniques, or micro-algorithms, to achieve scalability. By scalability, we mean the ability of groups of communicating processes to grow very large in size. We study the behavior of several of these fundamental techniques that appear in many deployed and emerging Internet standards: Suppression, Announce-Listen, and Leader Election. These 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 messages from other processes. We 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 and uncorrelated loss on groups of communicating processes. As 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, we establish 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.


Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://etd.caltech.edu/etd/available/etd-08272001-155016/PublisherThesis
Additional Information:© 2000 California Institute of Technology (Defended September 19, 2000) Also published as Caltech Computer Science Technical Report. The research described in this thesis was funded in part by an Earl C. Anthony Graduate Fellowship, a Career Development Grant from the American Association of University Women, a Microsoft Graduate Fellowship, as well as the Air Force Office of Scientific Research and the National Science Foundation. I thank all of them for their generous support.
Group:Computer Science Technical Reports
Funders:
Funding AgencyGrant Number
American Association of University WomenUNSPECIFIED
Microsoft Graduate FellowshipUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)UNSPECIFIED
NSFUNSPECIFIED
Subject Keywords:multicast, distributed systems, scalability, network communication, performance analysis
DOI:10.7907/Z96W982N
Record Number:CaltechCSTR:2001.003
Persistent URL:http://resolver.caltech.edu/CaltechCSTR:2001.003
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26902
Collection:CaltechCSTR
Deposited By: Imported from CaltechCSTR
Deposited On:26 Sep 2001
Last Modified:08 Mar 2017 17:32

Repository Staff Only: item control page