Interconnection networks based on a torus or k-ary n-cube topology are widely used as switch and router fabrics (Avici TSR), processor memory interconnect, and I/O interconnect (InfiniBand).  In many of these applications, it is essential that the interconnection network guarantee a minimal throughput regardless of the traffic pattern.  In an internet router, for example, there is no backpressure on input channels so the interconnection network used for the router fabric must handle any traffic pattern at line rate or packets will be dropped.  At the same time, an efficient interconnection network should exploit locality to achieve high performance and low power on local traffic patterns.

In this work, we explore routing algorithms called Randomized Local Balanced (RLB) algorithms.

• RLB algorithms strike a balance between the conflicting goals of exploiting locality and providing high worst-case throughput.

• At the same time, RLB algorithms provide deterministic guarantees of avoiding both deadlock and livelock in the network.

Publications:

• Singh, Arjun, Dally, William J., Towles, Brian, and Gupta, Amit K., "Locality-Preserving Randomized Oblivious Routing on Torus Networks", ACM Symposium on Parallel Algorithms and Architectures (SPAA), Winnipeg, Manitoba, Canada, August, 2002.

For problems or questions regarding this web contact btowles@cva.stanford.edu.
Last updated: May 01, 2002.