Optimal many-to-one routing on the mesh

We present randomized and deterministic algorithms for many-to-one routing on an n-node two-dimensional mesh under the store-and-forward model. We consider a general instance of the problem, where each node is source (resp., destination) of l (resp., k) packets, for arbitrary values of l and k. All our algorithms run in optimal O (√lkn) time and use queues of only constant size at each node to store packets in transit. The randomized algorithms, however, are simpler to implement. Our result closes a gap in the literature, where time-optimal algorithms using constant-size queues were known only for the special cases l = 1 and l = k.