Randomized Multi-Packet Routing on Meshes
| Author(s) : | Jop F. Sibeyn Michael Kaufmann, |
| Publisher : | N/A |
| Publication Date : | 1991 |
| ISSN : | N/A |
| Abstract : | 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 \Delta n=2 + O((k \Delta n \Delta log n), |