Multicasting in heterogeneous networks
Amotz Bar-Noy, Sudipto Guha, Joseph Seffi Naor, Baruch Schieber · 1998
In heterogeneous networks sending messages may incur different delays on different edges, and each processor may have a different switching time between messages.The well studied Telephone model is obtained when all edge delays and switching times are equal to one unit.We investigate the problem of finding the minimum time required 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 approximates 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. IntroductionThe 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,