One-to-many routing on the mesh

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 (&OHgr; √ 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 &Ogr; (log2 n). We also describe an optimal deterministic algorithm that, however, requires large buffers of size &Ogr; (c).