T.F. Gonzalez (USA)
Approximation Algorithms, Multimessage Multicasting, Forwarding, Buffers, Fully Connected Networks.
We consider the multimessage multicasting over the n pro cessor complete (or fully connected) static network when there are l incoming buffers to each processor. We present an efficient distributed algorithm to route the messages for every degree d problem instance with total communica tion time d2 /l + l − 1, where d is the maximum num ber of messages that each processor may send (or receive). Our algorithm takes linear time with respect to the input length. When l = d our algorithm generates communica tion schedules with smaller total communication time than previous algorithms, even when forwarding is allowed. Furthermore, such schedules can be constructed in linear time. For l = 1, d/2, and d we present lower bounds for the total communication time. The lower bounds match the upper bounds for the schedules generated by our algorithm when l = 1 and l = d, and are within 25% when l = d/2.
Important Links:
Go Back
