A lower bound for elementary oblivious routing on three-dimensional meshes

This paper shows an important exception to the common perception that three -dimensional meshes are more powerful than two-dimensional ones. Let N be t he total number of processors. Then permutation routing over three-dimensio nal mesh computers needs Theta (N-2/3) steps: while it takes Theta (N-1/2) steps over two-dimensional ones under the following conditions: (1) The pat h of each packet must be determined solely by its initial position and dest ination, i.e., the algorithm must be oblivious. (2) Each path must be "elem entary i.e. it must be shortest and as straight as possible. Thus the condi tions, under which, somewhat surprisingly, three-dimensional meshes are sig nificantly less powerful than two-dimensional ones for the fundamental netw ork operation, are quite reasonable in practice, (C) 2001 Academic Press.