Report Number: CSL-TR-80-189
Institution: Stanford University, Computer Systems Laboratory
Title: Center-based broadcasting
Author: Wall, David W.
Author: Owicki, Susan S.
Date: June 1980
Abstract: We consider the problem of routing broadcast messages in a
loosely-coupled store-and-forward network like the ARPANET.
Dalal discussed a solution to this problem that minimizes the
cost of a broadcast; in contrast, we are interested in
performing broadcast with small delay. Existing algorithms
can minimize the delay but seem unsuitable for use in a
distributed environment because they involve a high degree of
overhead in the form of redundant messages or data-structure
space. We propose the schemes of center-based forwarding; the
routing of all broadcasts via the shortest-path tree for some
selected node called the center. These algorithms have small
delay and also are easy to implement in a distributed system.
To evaluate center-based forwarding, we define four measures
of the delay associated with a given broadcast mechanism, and
then propose three ways of selecting a center node. For each
of the three forms of center-based forwarding we compare the
delay to the minimum delay for any broadcasting scheme and
also to the minimum delay for any single tree. In most cases,
a given measure of the delay on the centered tree is bounded
by a small constant factor relative to either of these two
minimum delays. When it is possible, we give a tight bound on
the ratio between the center-based delay and the minimum
delay; otherwise we demonstrate that no bound is possible.
These results give corollary bounds on how bad the three
centered trees can be with respect to each other; most of
these bounds are immediately tight, and the rest are replaced
by better bounds that are also shown to be tight.