Randomized single-target hot-potato routing
Ishai Ben Aroya, Ilan Newman, Assaf Schuster · 2002
We present randomized hot-potato routing algorithms on d-dimensional meshes and on the n-dimensional hypercube. The algorithms are designed for routing many packets to a single destination, or a relatively small number of destinations. The important feature, which was not obtained previously, is that the algorithms utilize the higher in-degree of the nodes and are asymptotically optimal.>