Routing without flow control
Costas Busch, Maurice P. Herlihy, Rogert Wattenhofer · 2001
We present the first dynamic hot-potato routing algorithm that does not require any form of explicit flow control: a node may inject a message into the network (n × n mesh) whenever a link is free. In the worst case, a node may have to wait an expected Ο(n) time before it has a free link. If destinations are chosen uniformly at random, this algorithm guarantees delivery in an expected Ο(n) time steps. Both measures are optimal up to a constant factor.