Routing without flow control

C. Busch, M. Herlihy, R. Wattenhofer

Research output: Contribution to conferencePaperpeer-review

13 Scopus citations


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 O(n) time before it has a free link. If destinations are chosen uniformly at random, this algorithm guarantees delivery in an expected O(n) time steps. Both measures are optimal up to a constant factor.

Original languageEnglish (US)
Number of pages10
StatePublished - 2001
Externally publishedYes
Event13th Annual Symposium on Parallel Algorithms and Architectures (SPAA 2001) - Crete Island, Greece
Duration: Jul 3 2001Jul 6 2001


Conference13th Annual Symposium on Parallel Algorithms and Architectures (SPAA 2001)
CityCrete Island

ASJC Scopus subject areas

  • Software
  • Safety, Risk, Reliability and Quality


Dive into the research topics of 'Routing without flow control'. Together they form a unique fingerprint.

Cite this