Oblivious Routing Algorithms on the Mesh of Buses

✍ Scribed by Kazuo Iwama; Eiji Miyano

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 226 KB
• Volume: 60
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1999.1597

✦ Synopsis

An optimal W1.5N 1Â2 X 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 threedimensional mesh of buses needs more time, i.e., 0(N 2Â3 ) steps, which is another important result of this paper.