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, N^1/2 row and N^1/2 column buses but no local connections between neighbouring 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 the first which exploits 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