Randomized multi-packet routing on meshes
Michael Kaufmann, Jop F. Sibeyn · 1991
We present algorithms for routing packets on a two-dimensional array of processors in the so-called k-k routing model. Each processor sends and receives exactly k packets. Using new techniques for the performance analysis we show that a simple randomized three phase algorithm performs optimally: For all k ≥ 8, the k-k routing problem is solved with k·n/2 + O((k·n·log n)^1/2) routing steps and constant size queues with very high probability, which nearly matches the lower bound of k·n/2 steps. For k < 8 we present refined algorithms which come close to optimal. In addition, we prove interesting results for cut-through routing: the same randomized algorithm routes packets consisting of k flits each with k·n/2 + n/k + 3/2·k + O(k·(n·log n)^1/2) routing steps with very high probability. We can generalize the algorithm for routing on meshes of arbitrary dimension and nearly reach the trivial lower bounds for both classes of problems. For routing on meshes with wrap-around connections we present a four phase algorithm which can be generalized easily for routing on meshes with wrap-around connections of arbitrary dimension. The performance is close to optimal...