Near-optimal worst-case throughput routing for two-dimensional mesh networks

Minimizing latency and maximizing throughput are important goals in the design of routing algorithms for interconnection networks. Ideally, we would like a routing algorithm to (a) route packets using the minimal number of hops to reduce latency and preserve communication locality, (b) deliver good worst-case and average-case throughput and (c) enable low-complexity (and hence, low latency) router implementation. In this paper, we focus on routing algorithms for an important class of interconnection networks: two dimensional (2D) mesh networks. Existing routing algorithms for mesh networks fail to satisfy one or more of design goals mentioned above. Variously, the routing algorithms suffer from poor worst case throughput (ROMM by Nesson, and Johnsson (1995), DOR by Sullivan and Bashkow, 1977), poor latency due to increased packet hops (VALIANT by Valiant and Brebner (1981)) or increased latency due to hardware complexity (minimal-adaptive by Duato, (1993), Upadhyay, Varavithya and Mohapatra, (1997)). The major contribution of this paper is the design of an oblivious routing algorithm-O1TURN-with provable near-optimal worst-case throughput, good average-case through-put, low design complexity and minimal number of network hops for 2D-mesh networks, thus satisfying all the stated design goals.