OPTIMIZED BROADCASTING AND MULTICASTING PROTOCOLS IN CUT-THROUGH ROUTED NETWORKS

This paper addresses the one-to-all broadcasting problem and the one-t o-many broadcasting problem, usually simply called broadcasting and mu lticasting, respectively. Broadcasting is the information disseminatio n problem in which a node of a network sends the same piece of informa tion to all the other nodes. Multicasting is a partial broadcasting in the sense that only a subset of nodes forms the destination set. Both operations have many applications in parallel and distributed computi ng. In this paper, we study these problems in both line model, and cut -through model. The former assumes long distance calls between nonneig hboring processors. The latter strengthens the line model by taking in to account the use of a routing function. Long distance calls are poss ible in circuit-switched and wormhole-routed networks, and also in man y networks supporting optical facilities. In the line model, it is wel l known that one can compute in polynomial time a [log(2)n]-round broa dcast or multicast protocol for any arbitrary network. Unfortunately, such a protocol is often inefficient from a practical point of view be cause it does not use the resources of the network in a balanced way. In this paper, we present a new algorithm to compute broadcast or mult icast protocols. This algorithm applies under both line and cut-throug h models. Moreover, it returns protocols that efficiently use the band width of the network. From a complexity point of view, we also show th at most of the optimization problems relative to the maximization of t he efficiency of broadcast or multicast protocols in terms of switchin g time or vertex load are NP-complete. We have, however, derived polyn omial efficient solutions for tree-networks.