Multicasting in Heterogeneous Networks Amok Bar-Nay* Sudipto Guhst Joseph (Seffi) Nao6 Baruch Schieber 5 Abstract In heterogeneous networks sending messages may incur dif- ferent delays on different edges, and each processor may have a different switching time between messages. The well studied Tele- phone model is obtained when all edge delays and switching times are equal to one unit. We investigate the problem of finding the minimum time re- quired to multicast a message from one source to a subset of the processors of size k. The problem is NP-hard even in the basic Telephone model. We present a polynomial time algorithm that ap- proximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the Telephone model by a factor of 0 (e). No approximation algorithms were known for the general model considered in this paper. 1 Introduction The task of disseminating a message from a source node to the rest of the nodes in a communication network is called bruudcczsting. The goal is to completethetask as fast as possible assuming all nodes in the network participate in the effort. When the message needs to be disseminated only to a subset of the nodes this task is referred to as mulricarring. Broadcasting and multicasting are important and basic communication primitives in many multiprocessor systems. Current networks usually provide point-to-point communication only between some of the pairs of the nodes in the network. Yet, *Electrical Engineering Department, Tel Aviv University, Tel Aviv 69978, Israel. E-mti amotz@ea~.mu.ac.i tComputer Science Dep&ent, Stanford University, Stanford, CA 9.%305. Stmorted bv an AR0 hfURI Grant DAAH@!-96-1- 0007 and NSF A&d CCR:9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. E-mail: [email protected]. tcomputer Science Department, Technion. Haih 32000, Israel. E-mail: naorQcs.technion.ac.il. fIBhi T.J. Watson Research Center, PO. Box 215, Yorktown Eeights, NY 10598. E-maiil: [email protected]. in many applications, a node in the network may wish to send a message to a subset of the nodes, where some of them are not connected to the sender directly. Due to the significance of this operation, it is important to design efficient algorithms for it. Broadcast and multicast operations are frequently used in many applications for message-passing systems (see [S]). It is also pro- vided as a communication primitive by several collective commu- nication libraries, such as Express by Parasoft [6] and the Message PassingLibrary (MPL) [I, 21 of theIBM SP2pamllel systems. This operation is also included as part of the collective communication routines in the Message-Passing Interface (MPI) standard proposal [S]. Application domains that use broadcast and multicast opcm- tions extensively include scientific computations, network manage- ment protocols, databasetransactions, and multimedia applications. There are two basic models in which trivial optimal solutions exist. In the first model, all nodes are assumed to be connected and it takes one unit of time (round) for a message to cross a link. Therefore, in each round the number of nodes receiving the message can be doubled. If the target set of nodes is of size k, then this process terminates in [logkj rounds. In the second model the communicationnehvorkis representedby an arbitrary graph, where each node is capable of sending a message to all of its neighbors in one unit of time. Here, the number of rounds required to deliver a message to a subset of the nodes is the maximum distance from the source node to any of the nodes in the subset. The model in which a node may send a message to at most one other node in each round is known as the Telephone model, It is known that for arbitrary communication graphs, the problem of finding an optimal broadcast in the Telephone model is NP- hard 191, even for 3-regular planar graphs [17]. It is not hard to verify that in the Telephone model two trivial lower bounds hold for the minimum broadcast time. The first one is [log tal, where n denotes the number of nodes in the graph, and the second one is the maximum distance from the source node to any of the other nodes. Research in the past three decades has focused on finding optimal broadcast algorithms for various classes of graphs such as trees, grids, and hypercubes. Also, researchers have looked for graphs with minimum number of edges for which a broadcast time of rlognl can be achieved from any sourcenode. Problems related to broadcast which were extensively investigated are the problems of broadcast multiple messages, gossiping, and computing certain functions on all n inputs in a network. See, e.g., [4, 10, 11,12,16, 19,21,22]. An assumption central to the Telephone model is that both sender and receiver are busy during the whole sending process, That is, only after the receiver received the message, both ends may 448ocnd the message to other nodes, More realistic models in this con- text are the Postal model (see [3]) and the LogP model (see [15]). The idcn there is that the sender may send another message before Ihc mcosagc is completely received by the receiver, and the receiver la free during the early stages of the sending process. We note that in both the Postal model and the LogP model it is assumedthat the dclny of n meosngc between any pair of nodes is the same. Optimal solutions for broadcast in the Postal model are known for lhe cnsc of a complete graph, and for some other classes of Brapho, However, not much is known for arbitrary graphs. In the Poatnl model, researchers have also concentrated on other dissemi- nation primitives nnd almost always assumed that the communica- tion graph is complete. 1,l Our reoulto In lhls paper we dclinc n more general model basedon the Postal model and cnll it the heterogeneouspostal model. Assume node u acnds n message to node w at time 0 and the message arrives at u at lime X,*, The nssumption is that 41 is free to send a new message at time ou, and w Is free from time 0 to time X,, - r,,. We call L (he delay of the link (96, u), s,, the sending (or switching) time of tl, and rv the receiving time of w). By definition, both s,, and rv are amaller than Xuv. A common assumption is that r,, = 3% for alI nodes 46, Observe thnt when the delay, sending time, and receiving Ilmc are nil cqunl to 1, we