Oblivious Routing Algorithms on the Mesh of Buses

An optimal ⌈1.5N^1/2⌉ lower bound is shown for oblivious routing on the mesh of buses: a two-dimensional parallel model consisting of N^1/2×N^1/2 processors and N^1/2 row and N^1/2 column buses but no local connections between neighboring processors. Many lower bound proofs for routing on mesh-structured 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 mesh of buses includes 2N^1/2 buses and each processor can access two different buses. Apparently the three-dimensional model provides more communication facilities, namely including 3N^2/3 buses, and each processor can access three different buses. Surprisingly, however, the oblivious routing on the three-dimensional mesh of buses needs more time, i.e., Ω(N^2/3) steps, which is another important result of this paper.