Concurrent multicast in weighted networks

Concurrent multicast is the problem of information dissemination from a set of sourer nodes to a set of destination nodes in a network with cost funct ion: Each source node s needs to multicast a block of data B(s) to the set of destinations. We are interested in protocols for this problem which have minimum communication cost. We consider both the usual case in which any t ransmitted message can consist of an arbitrary number of data blocks and th e case in which each message must consist of exactly one block of data. The problem of determining the minimum cost to perform concurrent multicast fr om a given set of sources to a set of destinations is NP-hard under both as sumptions. We give approximation algorithms to efficiently perform concurre nt multicast in arbitrary networks. We also analyze the communication time and communication complexity, i.e., the product of the communication cost a nd time, of our algorithms. (C) 2001 Elsevier Science B,V. All rights reser ved.