Carleton University
Technical Report TR-95-16
June 1995
Multipacket Hot-Potato Routing on Processor Arrays
Christos Kaklamanis & Danny Krizanc
Abstract
In this paper, we consider the problems of multipacket batch and balanced routing on d-dimensional (constant d ≥ 2) torus and mesh connected processor arrays. We present new “hot-potato” routing algorithms which achieve the best known average-case and worst-case time bounds for both problems on all such networks.