Research Seminar - Feb 14, 2000

Abstract

Packet Routing is a basic problem to be solved in computer networks. In an h-h problem each processor contains h packets initially and finally. In this talk we present a fundamental method for solving h-h routing and sorting problems on meshes and related networks. By the help of all-to-all mappings, we can design algorithms which asymptotically match the trivial lower bisection-bound. This method also works for higher-dimensional meshes and tori, for grids with diagonals and for reconfigurable meshes. Further, it can be used to improve runtimes on more sophisticated architectures like multi-meshes.