Efficient bufferless routing on leveled networks

Costas Busch, Shailesh Kelkar, Malik Magdon-Ismail

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations


We give near optimal bufferless routing algorithms for leveled networks. N packets with preselected paths are given, and once injected, the packets may not be buffered while in transit to their destination. For the preselected paths, the dilation D is the maximum path length, and the congestion C is the maximum number of times an edge is used. We give two bufferless routing algorithms for leveled networks: (i) a centralized algorithm with routing time O((C + D) log(DN)); (ii) a distributed algorithm with routing time O((C + D) log2(DN)). The distributed algorithm uses a new technique, reverse-simulation, which is used to obtain a distributed emulation of the centralized algorithm. Since a well known lower bound on the routing time is Ω(C + D), our results are at most one or two logarithmic factors from optimal.

Original languageEnglish (US)
Pages (from-to)931-940
Number of pages10
JournalLecture Notes in Computer Science
StatePublished - 2005
Externally publishedYes
Event11th International Euro-Par Conference, Euro-Par 2005 - Lisbon, Portugal
Duration: Aug 30 2005Sep 2 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Efficient bufferless routing on leveled networks'. Together they form a unique fingerprint.

Cite this