Caltech Library System

About | Browse | Search | Caltech Student Instructions

Type of Document	Dissertation
Author	Schooler, Eve Meryl
Author's Email Address	eve_schooler AT acm.org
URN	etd-08272001-155016
Persistent URL	http://resolver.caltech.edu/CaltechETD:etd-08272001-155016
Title	Why multicast protocols (don't) scale: an analysis of multipoint algorithms for scalable group communication
Degree	PhD
Option	Computer Science
Advisory Committee	Advisor Name Title K. Mani Chandy Committee Chair Alain Martin Committee Member Deborah Estrin Committee Member Jason Hickey Committee Member Jehoshua Bruck Committee Member
Keywords	distributed systems performance analysis network communication scalability multicast
Date of Defense	2000-09-19
Availability	unrestricted
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.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    00ch0.pdf 144.14 Kb 00:00:40 00:00:20 00:00:18 00:00:09 < 00:00:01   01ch1.pdf 102.06 Kb 00:00:28 00:00:14 00:00:12 00:00:06 < 00:00:01   02ch2.pdf 449.14 Kb 00:02:04 00:01:04 00:00:56 00:00:28 00:00:02   03ch3.pdf 334.14 Kb 00:01:32 00:00:47 00:00:41 00:00:20 00:00:01   04ch4.pdf 277.78 Kb 00:01:17 00:00:39 00:00:34 00:00:17 00:00:01   05ch5.pdf 299.18 Kb 00:01:23 00:00:42 00:00:37 00:00:18 00:00:01   06ch6.pdf 38.72 Kb 00:00:10 00:00:05 00:00:04 00:00:02 < 00:00:01   07appendixA.pdf 60.33 Kb 00:00:16 00:00:08 00:00:07 00:00:03 < 00:00:01   08appendixB.pdf 58.68 Kb 00:00:16 00:00:08 00:00:07 00:00:03 < 00:00:01   09bibliography.pdf 56.60 Kb 00:00:15 00:00:08 00:00:07 00:00:03 < 00:00:01   thesis.pdf 1.87 Mb 00:08:39 00:04:27 00:03:53 00:01:56 00:00:09