Concurrent multicast is a problem of information dissemination from a set of source nodes to a set of destination nodes in a network with cost function: 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 minium communication cost. We consider both the classical case in which any transmitted message can consist of an arbitrary number of data blocks and the case in which each message must consist of exactly one block of data. We show that the problom of determining the minimum cost to perform concurrent multicast is NP-hard under both assumptions. We also give approximation algorithms to efficiently perform concurrent multicast in arbitrary networks.
展开▼
