Abstract
Simple Algorithms for Multimessage Multicasting With Forwarding
by: Teofilo F. Gonzalez
Abstract:
We consider Multimessage Multicasting over the $n$ processor complete (or fullyconnected) static network ($MM_{C}$) when the Forwarding of messages isallowed. We present an efficient algorithm that constructs for every degree$d$ problem instance a communication schedule with total communication time atmost $2d$, where $d$ is the maximum number of messages that each processor maysend (receive). Our algorithm consists of two phases. In the first phase aset of communications are scheduled to be carried out in $d$ time periods insuch a way that the resulting problem is a multimessage unicasting problem ofdegree $d$. In the second phase we generate a communication schedule for thisproblem by reducing it to the Makespan Openshop Preemptive Scheduling problemwhich can be solved in polynomial time. The final schedule is theconcatenation of the communication schedules for each of these two phases. For$2 \\le l \\le d$ we present an algorithm to generate a communication schedulewith total communication time at most $\\lfloor ( 2 - \\frac{1}{l} ) d \\rfloor+1$, for problem instances where each processor needs to send messages to atmost $ld$ destinations.
Keywords:
Approximation Algorithms, Multimessage Multicasting, DynamicNetworks, Parallel Iterative Methods, Communication Schedules,Forwarding
Date:
December 1997
Document: 1997-24
