Throughput-Centric Routing Algorithm Design

D. Towles, W. Dally, and S. Boyd

Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 200–219, June 2003.

The increasing application space of interconnection networks now encompasses several applications, such as packet routing and I/O interconnect, where the throughput of a routing algorithm, not just its locality, becomes an important performance metric. We show that the problem of designing oblivious routing algorithms that have high worst-case or average-case throughput can be cast as a linear program. Globally optimal solutions to these optimization problems can be efficiently found, yielding provably good oblivious routing algorithms.