One-to-Many routing on the mesh
Kieran T. Herley, Andrea Pietracaprina, Geppino Pucci · 2001
We study the routing of messages with multiple destinations on an n-node square mesh (one-to-many routing). The obvious approach of simply replicating each message into the appropriate number of point-to-point messages and routing these independently does not generally yield optimal performance. A standard argument proves that (Ω √ n + cm) time is required to route m ⪇ n messages, where each message is generated by a distinct node and at most c messages must be delivered to any individual node. The lower bound does not depend on the number of destinations per message. We provide both randomized and deterministic algorithms for one-to-many 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 Ο (log2 n). We also describe an optimal deterministic algorithm that, however, requires large buffers of size Ο (c).