Oblivious routing algorithms on the mesh of buses

An optimal [1.5N(1/2)] lower bound is shown for oblivious routing on the me sh of buses: a two-dimensional parallel model consisting of N-1/2 x N-1/2 p rocessors and N-1/2 TOW and N-1/2 column buses but no local connections bet ween neighboring processors. Many lon er bound proofs for routing on mesh-s tructured models use a single instance (adversary) which includes difficult packet-movement. This approach does not work in our case, our proof is one of the rare cases which really exploit the fact that the routing algorithm has to cope with many different instances. Note that the two-dimensional m esh of buses includes 2N(1/2) buses and each processor can access two diffe rent buses. Apparently the three-dimensional model provides more communicat ion facilities, namely including 3N(2/3) buses, and each processor can acce ss three different buses. Surprisingly, however, the oblivious routing on t he three-dimensional mesh of buses needs more time, i.e., Omega(N-2/3) step s, which is another important result of this paper. (C) 2000 Academic Press .