BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CSL-TR-80-189
       ENTRY:: December 01, 1994
ORGANIZATION:: Stanford University, Computer Systems Laboratory
       TITLE:: CENTER-BASED BROADCASTING
        TYPE:: Technical Report
      AUTHOR:: Wall, David W.
      AUTHOR:: Owicki, Susan S.
        DATE:: June 1980
       PAGES:: 26
    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.
       NOTES:: [Adminitrivia V1/Prg/19941201]
         END:: STAN//CSL-TR-80-189