Optimal oblivious routing on d-dimensional meshes

In this work we consider deterministic oblivious k-k routing algorithms with buffer size O(k). We present an asymptotically optimal O(knd) 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.