Mechanisms for broadcast and selective broadcast
David W. Wall · 1980
This thesis deals with a problem the effective use of a loosely-coupled store-and-forward network like the ARPANET. Many applications assume the existence of a mechanism to send a broadcast message to every node the network, or a selective broadcast message to a specified group of nodes. Previous work this field has resulted several techniques for broadcasting to the entire network. These include an algorithm for imposing a minimum spanning tree on the network and maintaining it the face of failures and changing costs, so that a broadcast can be routed along the branches of the MST at a minimum cost to the network as a whole. I extend this work two directions. First of all, I discuss ways of adapting existing broadcast mechanisms to the more general problem of selective broadcast. In one case this involves generalizing the MST problem to the problem of finding a minimum Steiner tree, a problem which is NP-complete. I examine an existing approximation algorithm and show how to modify it for use a distributed environment. In the process I show that if we make a reasonable assumption about the way ties between edges are broken then we can considerably simplify this algorithm. Second, I propose an original broadcasting technique that forwards along the branches of a single tree the same manner as the MST-based algorithm. The tree used is a shortest-path tree for a particular node that is, some sense, in the of the network; hence this method is called center-based forwarding. Using such a tree allows us to provide a broadcast facility with a small delay rather than a small cost; unfortunately it is impossible general to minimize the delay from every source if we use only a single tree. To evaluate center-based forwarding, I define four measures of the delay associated with a given broadcast mechanism, and then propose three ways of selecting the center node. For each of the three forms of center-based forwarding, I compare the delay to the minimum delay for any broadcasting mechanism and also to the minimum delay for any single tree. In most cases, the delay on the centered tree is bounded by a small constant factor multiplied by either of these two minimum delays. When I can, I give a strict bound on the ratio between the center-based delay and the minimum delay; otherwise I demonstrate that no bound is possible. These results immediately imply bounds on how bad the three centered trees can be with respect to each other; most of these bounds are strict, and I improve the rest to bounds that are also strict. Finally I present an algorithm for maintaining the centered tree the face of changes traffic conditions and failures nodes and links. I also discuss the extension of center-based forwarding to the problem of selective broadcast.