Store-and-Forward Multicast Routing on the Mesh |
| |
Authors: | Kieran T Herley Andrea Pietracaprina Geppino Pucci |
| |
Affiliation: | (1) Dept. of Computer Science, University College Cork, Cork, Ireland;(2) Dip. di Ingegneria dell’Informazione, Università di Padova, Padova, Italy |
| |
Abstract: | We study the complexity of routing a set of messages with multiple destinations (multicast routing) on an n-node square mesh under the store-and-forward model. A standard argument proves that
time is required to route n messages, where each message is generated by a distinct node and at most c messages are to be delivered to any individual node. The obvious approach of simply replicating each message into the appropriate
number of unicast (single-destination) messages and routing these independently does not yield an optimal algorithm. We provide
both randomized and deterministic algorithms for multicast routing, which use constant-size buffers at each node. The randomized
algorithm attains optimal performance, while the deterministic algorithm is slower by a factor of O( log 2
n). We also describe an optimal deterministic algorithm that, however, requires large buffers of size O(c).
A preliminary version of this paper appeared in Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures,
Crete, Greece, 2001. This work was supported, in part, by MIUR under project ALGO-NEXT. |
| |
Keywords: | Mesh architecture Parallel communication primitives Store-and-forward routing Multicast One-to-many routing |
本文献已被 SpringerLink 等数据库收录! |
|