UNLV ECG 702 - Multicasting in Heterogeneous Networks (6 pages)

Previewing pages 1, 2 of 6 page document View the full content.
View Full Document

Multicasting in Heterogeneous Networks



Previewing pages 1, 2 of actual document.

View the full content.
View Full Document

Unformatted text preview:

Multicasting in HeterogeneousNetworks Amok Bar Nay Sudipto Guhst Joseph Seffi Nao6 Baruch Schieber 5 in many applications a node in the network may wish to send a messageto a subset of the nodes where some of them are not connectedto the senderdirectly Due to the significance of this operation it is important to design efficient algorithms for it Abstract In heterogeneousnetworks sending messagesmay incur different delays on different edges and each processormay have a different switching time betweenmessages The well studiedTelephonemodel is obtainedwhen all edgedelays and switching times areequal to one unit Broadcastandmulticast operationsarefrequently usedin many applications for message passing systems see S It is also provided as a communicationprimitive by severalcollective communication libraries such asExpressby Parasoft 6 and the Message PassingLibrary MPL I 21of theIBM SP2pamllel systems This operationis also included as part of the collective communication routines in the Message Passing Interface MPI standardproposal S Application domainsthat use broadcastand multicast opcmtions extensivelyinclude scientific computations network managementprotocols databasetransactions andmultimedia applications We investigate the problem of finding the minimum time required to multicast a messagefrom one sourceto a subsetof the processorsof size k The problem is NP hard even in the basic Telephonemodel We presenta polynomial time algorithm that approximatesthe minimum multicasttime within a factor of O log k Our algorithm improveson the bestknown approximationfactor for the Telephonemodel by a factor of 0 e No approximation algorithms were known for the general model consideredin this paper There are two basic models in which trivial optimal solutions exist In the first model all nodes are assumedto be connected and it takes one unit of time round for a messageto cross a link Therefore in each round the number of nodesreceiving the messagecanbe doubled If the targetset



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Multicasting in Heterogeneous Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Multicasting in Heterogeneous Networks and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?