Paper Info
Title
Optimal oblivious routing on d-dimensional meshes
Abstract
In this work we consider deterministic oblivious k-k routing algorithms with buffer size O(k). We present an asymptotically optimal O(k√nd) step oblivious k-k routing algorithm for d-dimensional n × .... × n meshes of nd processors for all k ≥ 1 and d 1. We further show how the algorithm can be used to achieve asymptotically optimal oblivious k-k routing algorithms on other networks.
Year
DOI
Venue
2003
10.1016/j.tcs.2004.04.016
Theoretical Computer Science - Foundations of software science and computation structures
Keywords
DocType
Volume
parallel algorithm,d-dimensional mesh,deterministic oblivious k-k,oblivious routing,asymptotically optimal,optimal oblivious routing,buffer size o,constant buffer,constant buffer size,asymptotically optimal oblivious k-k,n mesh,nd processor,oblivious k-k,d -dimensional mesh,d-dimensional n
Conference
333
Issue
ISSN
Citations 
3
0304-3975
0
PageRank 
References 
Authors
0.34
12
1
Name
Order
Citations
PageRank
Andre Osterloh1104.49